- ....
`
`•
`
`Repelling the Wily Hacker
`William R. Cheswick
`Steven M. Bellovin
`
`SAMSUNG EX. 1025 - 1/12
`
`

`

`RISC/os is a trademark of MIPS Computer Corporation. Sun OS is a trademark of Sun
`RSAREF is a trademark of RSA Data Security, Inc. SPARCstation is a
`trademark of SPARC International, Inc. PostScript is a registered trademark of Adobe
`Systems, Inc. Ethernet is a trademark of Xerox Corporation. The X Window System and
`Kerberos are trademarks of the Massachusetts Institute of Technology. Datakit VCS is a
`registered trademark of AT&T. UNlX is a technology trademark of X/ Open Company, Ltd.
`S/Key is a trademark of Bell core.
`
`The publisher offers discounts on this book when ordered in quantity for special sales. For
`more information please contact:
`Corporate & Professional Publishing Group
`Addison-Wesley Publishing Company
`One Jacob Way
`Reading, Massachusetts 01867
`
`Library of Congress Cataloging-in-Publication Data
`Cheswick, William R.
`Firewalls and Internet Security : repelling the wily hacker I
`William R. Cheswick, Steven M. Bellovin.
`p. em.
`Includes bibliographical references and index.
`ISBN 0-201-63357-4
`l. Internet (Computer networks)
`measures. I. Bellovin, Steven M.
`TK5105.875.I57C44 1994
`005.8--dc20
`
`2. Computer networks--Security
`II. Title.
`
`94-10747
`CIP
`
`Copyright © 1994 by AT&T Bell Laboratories, Inc.
`All rights reserved. No part of this publication may be reproduced, stored in a retrieval
`system, or transmitted, in any form, or by any means, electronic, mechanical, photocopy-
`ing, recording, or otherwise, without the prior consent of the publisher. Printed in the
`United States of America. Published simultaneously in Canada.
`This book was typeset by the authors in 10-point Times-Roman, Michael Urban's Tengwar
`font, and Joel Hoffman's Hclassic Hebrew font, using 0-TEX, a fair amount of hacking.
`and a plethora of .sty files snarfed from the internet.
`
`ISBN 0-201-63357-4
`
`Text printed on recycled paper.
`3 4 56 7 8 9 10-CRW-97969594
`Third Printing, July 1994
`
`SAMSUNG EX. 1025 - 2/12
`
`

`

`13
`Secure Communications over
`Insecure Networks
`
`13.1 An Introduction to Cryptography
`It is sometimes necessary to communicate over insecure links without exposing one's systems.
`Cryptography-
`the art of secret writing-is the usual answer.
`The most common use of cryptography is, of course, secrecy. A suitably encrypted packet is
`incomprehensible to attackers. In the context of the Internet, and in particular when protecting
`wide-area communications, secrecy is often secondary. Instead, we are often interested in the
`implied authentication provided by cryptography. That is, a packet that is not encrypted with the
`proper key will not decrypt to anything sensible. This considerably limits the ability of an attacker
`to inject false messages.
`Before we discuss some actual uses for cryptography, we present a brief overview of the
`subject and build our cryptographic toolkit. It is of necessity sketchy; cryptography is a complex
`subject that cannot be covered fully here. Readers desiring a more complete treatment should
`consult any of a number of standard references, such as [Kahn, 1967], [Denning, 1982], [Davies
`and Price, 1989], or [Schneier, 1994].
`We next discuss the Kerberos Authentication System, developed at MIT. Apart from its own
`likely utility-
`the code is widely available and Kerberos is being considered for adoption as an
`Internet standard-it makes an excellent case study, since it is a real design, not vaporware, and
`has been the subject of many papers and talks and a fair amount of experience.
`Selecting an encryption system is comparatively easy; actually using one is less so. There are
`myriad choices to be made about exactly where and how it should be installed, with trade-offs in
`terms of economy, granularity of protection, and impact on existing system. Accordingly, Sections
`13.3, 13.4, and 13.5 discuss the trade-offs and present some security systems in use today.
`In the discussion that follows, we assume that the cryptosystems involved-that is, the crypto-
`graphic algorithm and the protocols that use it, but not necessarily the particular implementation-
`
`211
`
`SAMSUNG EX. 1025 - 3/12
`
`

`

`212
`
`Secure Communications
`
`are sufficiently strong, i.e., we discount almost completely the possibility of cryptanalytic attack.
`Cryptographic attacks are orthogonal to the types of attacks we describe elsewhere. (Strictly
`speaking, there are some other dangers here. While the cryptosystems themselves may be perfect,
`there are often dangers lurking in the cryptographic protocols used to control the encryption. See,
`for example, [Moore, 1988]. Some examples of this phenomenon are discussed in Section 13.2
`and in the box on page 213.) A site facing a serious threat from a highly competent foe would need
`to deploy defenses against both cryptographic attacks and the more conventional attacks described
`elsewhere.
`One more word of caution: in some countries the export, import, or even use of any form of
`cryptography may be regulated by the government. Additionally, many useful cryptosystems are
`protected by a variety of patents. It may be wise to seek competent legal advice.
`
`13. 1 .1 Notation
`Modem cryptosystems consist of an operation that maps a plaintext (P) and a key (K) to a
`ciphertext (C). We write this as
`
`Usually, there is an inverse operation that maps a ciphertext and key K- 1 to the original plaintext:
`
`The attacker's usual goal is to recover the keys K and K- 1• For a strong cipher, it should be
`impossible to recover them by any means short of trying all possible values. This should hold true
`no matter how much ciphertext and plaintext the enemy has captured.
`It is generally accepted that one must assume that attackers are familiar with the encryption
`function; the security of the cryptosystem relies entirely on the secrecy of the keys. Protecting them
`is therefore of the greatest importance. In general, the more a key is used, the more vulnerable it is
`to compromise. Accordingly, separate keys, called session keys, are used for each job. Distributing
`session keys is a complex matter, about which we will say little; let it suffice to say that session
`keys are generally transmitted'encrypted by a master key, and often come from a centralized Key
`Distribution Center.
`
`13:1 .2 Private-Key Cryptography
`In conventional cryptosystems-sometimes known as secret-key or symmetric cryptosystems-
`there is only one key. That is,
`
`writing out K- 1 is simply a notational convenience to indicate decryption. There are many
`different types of symmetric cryptosystems; here, we will concentrate on the Data Encryption
`Standard (encryption, DES) [NBS, 1977] and its standard modes of operation [NBS, 1980]. Note,
`though, that most things we say are applicable to other modem cipher systems, with the obvious
`exception of such parameters as encryption block size and key size.
`
`SAMSUNG EX. 1025 - 4/12
`
`

`

`An Introduction to Cryptography
`
`213
`
`Types of Attacks
`Cryptographic systems are subject to a variety of attacks. It is impossible to give a
`complete taxonomy-but we discuss a few of the more important ones.
`Cryptanalysis: Cryptanalysis is the science-or art-of reading encrypted traffic without
`prior knowledge of the key.
`"Practical" cryptanalysis: "Practical" cryptanalysis is, in a sense, the converse. It refers
`to stealing a key, by any means necessary.
`Known-plaintext attack: Often, an enemy will have one or more pairs of ciphertext and a
`known plaintext encrypted with the same key. These pairs, known as cribs, can be
`used to aid in cryptanalysis.
`Chosen-plaintext: Attacks where you trick the enemy into encrypting your messages with
`the enemy's key. For example, if your opponent encrypts traffic to and from a file
`server, you can mail that person a message and watch the encrypted copy being
`delivered.
`Exhaustive' search: Trying every possible key. Also known as brute force
`Passive eavesdropping: A passive attacker simply listens to traffic flowing by.
`Active attack: In an active attack, the enemy can insert messages and-in some variants-
`delete or modify legitimate messages.
`Man-in-the-middle: The enemy sits between you and the party with whom you wish to
`communicate, and impersonates each of you to the other.
`Replay: Take a legitimate message and reinject it into the network at a later time.
`Cut-and-paste: Given two messages encrypted with the same key, it is sometimes possible
`to combine portions of two or more messages to produce a new message. You may
`not know what it says, but you can use it to trick your enemy into doing something
`for you.
`Time-resetting: In protocols that use the current time, try to confuse you about what the
`correct time is.
`Birthday attack: An attack on hash functions where the goal is to find any two messages
`that yield the same value. If exhaustive search takes 2n steps, a birthday attack
`would take only 2n/2 tries.
`
`SAMSUNG EX. 1025 - 5/12
`
`

`

`214
`
`Secure Communications
`
`DES is a form of encryption system known as a block cipher. That is, it operates on fixed-size
`blocks. It maps 64-bit blocks of plaintext into 64-bit blocks of ciphertext and vice versa. DES
`keys are 64 bits long, including 8 seldom-used parity bits.
`Encryption in DES is performed via a complex series of permutations and substitutions. The
`result of these operations is exclusive-OR'd with the input. This sequence is repeated 16 times,
`using a different ordering of the key bits each time. Complementing one bit of the key or the
`plaintext will flip approximately 50% of the output bits. Thus, almost no information about
`the inputs is leaked; small perturbations in the plaintext will produce massive variations in the
`ciphertext.
`DES was developed at IBM in response to a solicitation for a cryptographic standard from
`the National Bureau of Standards (NBS, now known as the National Institute of Standards and
`Technology or NIST). It was originally adopted for nonclassified federal government use, effective
`January 15, 1978. Every five years, a recertification review is held. The last one, in 1993,
`reaffirmed DES for financial and authentication use. It is unclear what will happen in 1998.
`IDEA [Lai, 1992] is similar in overall structure to DES. It derives its strength from its use of
`three different operations-exclusive-OR, modular addition, and modular multiplication-in each
`round, rather than just using exclusive-OR. Additionally, it uses a 128-bit key to guard against
`exhaustive search attacks. The IDEA algorithm is patented, but the patent holders have granted
`blanket permission for noncommercial use. Although IDEA appears to be a strong cipher, it is
`relatively new, and has not been subject to much scrutiny as yet. Some caution may be in order.
`Recently, a new block cipher, Skipjack, was announced by NIST. Skipjack is used in the
`so-called Clipper and Capstone encryption chips [Markoff, 1993a; NIST, 1994b]. These chips
`are controversial not because of their technical merits (though those are as-yet largely classified),
`but because the chips implement a key escrow system. Transmissions contain an encrypted header
`containing the session key; government agencies with access to the header-encryption keys will
`be able to decrypt the conversation. The government claims that a court order will be required for
`such access.
`Politics aside, Skipjack appears to be a conventional block cipher. It uses a 64-bit block size,
`an 80-bit key size, and 32 internal rounds. Because of the requirement for the escrow mechanism,
`only hardware implementations of Skipjack will be available. An outside review panel concluded
`that the algorithm was quite strong and that ''There is no significant risk that Skipjack can be
`broken through a shortcut method of attack" [Brickell et al., 1993].
`
`13.1.3 Modes of Operation
`Block ciphers such as DES, IDEA, and Skipjack are generally used as primitive operators to
`implement more complex modes of operation. The four standard modes are described next. All
`of them can be used with any block cipher, although we have used DES in the examples.
`
`Electronic Code Book Mode
`The simplest mode of operation, Electronic Code Book (ECB) mode, is also the most obvious:
`DES is used, as is, on 8-byte blocks of data. Because no context goes into each encryption, every
`
`SAMSUNG EX. 1025 - 6/12
`
`

`

`An Introduction to Cryptography
`
`217
`
`How Secure Is DES?
`There has been a fair amount of controversy about DES over the years; see, for example, [Diffie and
`Hellman, 1977]. Some have charged that the design was deliberately sabotaged by the National
`Security Agency (NSA), or that the key size is just small enough that a major government or large
`corporation could afford to build a machine that tried all 256 possible keys for a given ciphertext.
`That said, the algorithm has successfully resisted attack by civilian cryptographers for almost two
`decades. Moreover, recent research results [Biham and Sharnir, 1991, 1993] indicate that the basic
`design of DES is actually quite strong, and was almost certainly not sabotaged. If your enemy
`does not have significant resources, DES is adequate protection.
`However, a design has recently been presented for an "economical" DES-cracker based on
`exhaustive search [Wiener, 1994]. Wiener estimates that a machine can be built for $1,000,000
`that will find any DES key in about 7 hours; an average search would take half that time. The
`design scales nicely in both directions; a $10,000,000 version would find any key in 0.7 hours, or
`42 minutes, while a smaller $100,000 machine would succeed in 70 hours, which is quite adequate
`in many cases.
`Clearly, it is worth taking extra precautions with sensitive information, especially when using
`master keys. An enemy who cracks a session key can read that one session, but someone who
`cracks a master key can read all traffic, past, present, and future. The most sensitive message of
`all is a session key encrypted by a master key, since two brute force attacks-first to recover the
`session key and then to match that against its encrypted form- will reveal the master [Garon and
`Outerbridge, 1991]. Accordingly, triple encryption is recommended if you think your enemy is
`well financed.
`To perform triple encryption, use two DES keys, K 1 and K 2 :
`c <-- KI[K;_- 1[KI[P)]].
`Note that the middle encryption is actually a decryption. This is done for two reasons. First, it was
`originally suggested that double encryption with two keys K 1 and K 2 might actually be equivalent
`to simple encryption with a third key, K 3 , unknown to the legitimate recipients but recoverable by a
`cryptanalyst. It is now known that that is not possible: there is no such K3 [Campbell and Wiener,
`1993]. Second, and more important, by setting K 1 = K2, we have backward compatibility with
`systems that only do single encryption.
`This form of triple encryption gives you 112 bits of key strength. Simply doing double
`encryption isn't as strong against an enemy who can afford lots of storage [Merkle and Hellman,
`1981]. You can make triple encryption even stronger by choosing three independent keys K 1, K 2,
`and K 3. Again, there is compatibility with single encryption if the three keys are equal.
`13.1 .4 Public Key Cryptography
`With conventional cipher systems, both parties must share the same secret key before communica-
`tion begins. This is problematic. For one thing, it is impossible to communicate with someone for
`whom you have no prior arrangements. Additionally, the number of keys needed for a complete
`communications mesh is very large, n 2 keys for an n-party network. While both problems can be
`
`SAMSUNG EX. 1025 - 7/12
`
`

`

`218
`
`Secure Communications
`
`solved by recourse to a trusted, centralized KDC, it is not a panacea. If nothing else, the KDC
`must be available in real time to initiate a conversation. This makes KDC access difficult for
`store-and-forward message systems.
`Public key, or asymmetric, cryptosystems [Diffie and Hellman, 1976] offer a different solution.
`In such systems, K =f:. }(- 1• Furthermore, given K, the encryption key, it is not feasible to discover
`the decryption key K- 1• We write encryption as
`
`and decryption as
`
`for the keys belonging to A.
`Each party publishes its encryption key in a directory, while keeping its decryption key secret.
`To send a message to someone, simply look up their public key and encrypt the message with that
`key.
`The best known, and most important, public key cryptosystem is known as RSA, for its
`inventors, Ronald Rivest, Adi Sharnir, and Leonard Adleman [Rivest et al., 1978]. Its security
`relies on the difficulty of factoring very large numbers. It is protected by a U.S. patent. Legal
`commercial versions are available; there is also a free but licensed package, RSAREF, that is
`available on the Internet. Commercial use of RSAREF is barred, as is export from the United
`States. Other significant restrictions apply as well; you should check the latest version of the
`RSAREF license before using the code.
`To use RSA, pick two large prime numbers p and q; each should be at least several hundred
`bits long. Let n = pq. Pick some random integer d relatively prime to (p - 1)(q - 1), and e such
`that
`ed = 1 (mod (p- 1)(q - 1)).
`That is, when the product ed is divided by (p - 1)(q - 1), the remainder is 1.
`We can now use the pair ( e, n) as the public key, and the pair ( d, n) as the private key.
`Encryption of some plaintext P is performed by exponentiation modulo n:
`C +--- p e (mod n).
`Decryption is the same operation, with d as the exponent:
`p +--- cd (mod n)
`(Pe)d (mod n)
`p ed (modn)
`P (mod n).
`No way to recover d from e is known that does not involve factoring n, and that is believed to be
`a very difficult operation.
`Public key systems suffer from two principal disadvantages. First, the keys are very large
`compared with those of conventional cryptosystems. This might be a problem when it comes to
`entering or transmitting the keys, especially in secure mail messages (discussed later). Second,
`
`=
`
`SAMSUNG EX. 1025 - 8/12
`
`

`

`An Introduction to Cryptography
`
`219
`
`encryption and decryption are much slower. Not much can be done about the first problem. The
`second is dealt with by using such systems primarily for key distribution. Thus, if A wanted to
`send a secret message M to B, A would transmit something like
`EB[K],K[M]
`(13.1)
`where K is a randomly generated session key for DES or some other conventional cryptosystem.
`
`13.1.5 Exponential Key Exchange
`A concept related to to public-key cryptography is exponential key exchange, sometimes referred
`to as Diffie-Hellman [Diffie and Hellman, 1976]. Indeed, it is an older algorithm; the scheme
`was first described in the same paper that introduced the notion of public-key cryptosystems, but
`without providing -any examples. 1
`Exponential key exchange provides a mechanism for setting up a secret but unauthenticated
`connection between two parties. That is, the two can negotiate a secret session key, without fear of
`eavesdroppers. However, neither party has any strong way of knowing who is really at the other
`end of the circuit.
`In its most common form, the protocol uses arithmetic operations in the field of integers modulo
`some large number /3. When doing arithmetic (mod /3), you perform the operation as usual, but
`then divide by /3, discarding the quotient and keeping the remainder. In general, you can do the
`arithmetic operations either before or after taking the remainder. Both parties must also agree on
`some integer a, 1 <a< /3.
`Suppose A wishes to talk to B. They each generate secret random numbers, RA and RB.
`Next, A calculates and transmits to B the quantity
`aRA (mod /3).
`
`Similarly, B calculates and transmits
`
`aR8 (mod /3).
`Now, A knows RA and aRB (mod /3), and hence can calculate
`aRBRA (mod /3)
`(aRB )RA (mod /3)
`aRARB (mod /3).
`Similarly, B can calculate the same value. But an outsider cannot; the task of recovering RA
`from aRA (mod /3) is believed to be very hard. (This problem is known as the discrete logarithm
`problem.) Thus, A and B share a value known only to them; it can be used as a session key for a
`symmetric cryptosystem.
`Again, caution is indicated when using exponential key exchange. As noted, there is no authen-
`tication provided; anyone could be at the other end of the circuit, or even in the middle, relaying
`
`1 Exponential key exchange is protected by a patent in the United States.
`
`SAMSUNG EX. 1025 - 9/12
`
`

`

`262
`
`BIBLIOGRAPHY
`
`[Curry, 1992] David A. Curry. UNIX System Security: A Guide for Users and System Adminis-
`trators. Addison-Wesley, Reading, MA, 1992. Cited on: xiii.
`[Davies and Price, 1989] Donald W. Davies and Wyn L. Price. Security for Computer Networks.
`John Wiley & Sons, second edition, 1989. Cited on: 122, 211.
`A guide to deploying cryptographic technology.
`[Deering, 1989] Steve Deering. Host extensions for IP multicasting. RFC 1112, August 1989.
`Cited on: 46.
`[Denning, 1982] Dorothy E. Denning. Cryptography and Data Security. Addison-Wesley, Read-
`ing, MA, 1982. Cited on: 211.
`[Denning, 1993] Dorothy E. Denning. To tap or not to tap. Communications of the ACM,
`36(3):26-33, March 1993. Cited on: 220.
`A defense of the U.S. government's key escrow initiative.
`[Denning and Sacco, 1981] Dorothy E. Denning and Giovanni M. Sacco. Timestamps in key
`distribution protocols. Communications of the ACM, 24(8):533- 536, August 1981. Cited on:
`123, 223.
`Some weaknesses in [Needham and Schroeder, 1978].
`[Diffie, 1988] Whitfield Diffie. The first ten years of public key cryptography. Proceedings of the
`IEEE, 76(5):560-577, May 1988. Cited on: 121.
`An exceedingly useful retrospective.
`[Diffie and Hellman, 1976] Whitfield Diffie and Martin E. Hellman. New directions in cryptog-
`raphy. IEEE Transactions on Information Theory, IT-11:644-654, November 1976. Cited on:
`34, 2I8, 219, 225.
`The original paper on public-key cryptography. A classic.
`[Diffie and Hellman, 1977] Whitfield Diffie and Martin E. Hellman. Exhaustive cryptanalysis of
`the NBS data encryption standard. Computer, 10(6):74-84, June 1977. Cited on: 216.
`The original warning about DES's key length being too short.
`[DoD, 1985a] DoD trusted computer system evaluation criteria. DoD 5200.28-STD, DoD Com-
`puter Security Center, 1985. Cited on: 8, 162.
`The famous "Orange Book." Available forftp from FrP.CERT.ORG as /pub/ info /
`orange-book. Z.
`[DoD, 1985b] Technical rationale behind CSC-STD-003-83: Computer security requirements.
`DoD CSC-STD-004-85, DoD Computer Security Center, 1985. Cited on: 8.
`
`SAMSUNG EX. 1025 - 10/12
`
`

`

`272
`
`BIBLIOGRAPHY
`
`[Postel, 1982] Jon Postel. Simple mail transfer protocol. RFC 821, August 1982. Cited on: 29.
`[Postel and Reynolds, 1985] Jon Postel and Joyce Reynolds. File transfer protocol. RFC 959,
`October 1985. Cited on: 39.
`[Presotto, 1985] David L. Presotto. Upas- a simpler approach to network mail. In USENIX
`Conference Proceedings, pages 533-538, Portland, OR, Summer 1985. Cited on: 30.
`[Presotto and Ritchie, 1985] David L. Presotto and Dennis M. Ritchie. Interprocess communica-
`tion in the eighth edition unix system. In USENIX Conference Proceedings, pages 309-316,
`Portland, OR, Summer 1985. Cited on: 125.
`[Rago, 1990] Stephen Rago. A look at the Ninth Edition Network File System. In A. G. Hume
`and M.D. Mcilroy, editors, UNIX Research System: Papers, Volume II, pages 513- 522. AT&T
`Bell Laboratories, Murray Hill, NJ, tenth edition, 1990. Cited on: 81, 108.
`[Ranum, 1992] Marcus J. Ranum. A network firewall. In Proc. World Conference on System
`Administration and Security, Washington, D.C., July 1992. Cited on: 75.
`A description of Digital's firewall.
`[Reiher eta!., 1993] Peter Reiher, Jeff Cook, Thomas Page, Jr., Gerald Popek, and Stephen D.
`Crocker. Truffles- Secure file sharing with minimal system administrator intervention. In
`World Conference On System Administration, Networking, and Security, Arlington, VA, 1993.
`Cited on: 81.
`[Rekhter eta!., 1994] Yakov Rekhter, Robert G. Moskowitz, Daniel Karrenberg, and Geert Jan
`de Groot. Address allocation for private intemets. RFC 1597, March 1994. Cited on: 73.
`[Riordan, 1992] Mark Riordan. RIPEM user's guide, December 1992. Cited on: 233.
`Available with the RIPEM package, but not export-restricted.
`[Rivest, 1992] Ronald Rivest. The MD5 message-digest algorithm. RFC 1321, April1992. Cited
`on: 222, 247.
`[Rivest and Sharnir, 1984] Ronald L. Rivest and Adi Sharnir. How to expose an eavesdropper.
`Communications of the ACM, 27(4):393-395, 1984. Cited on: 219.
`[Rivest eta!., 1978] Ronald L. Rivest, Adi Sharnir, and Leonard Adleman. A method of obtaining
`digital signatures and public-key cryptosystems. Communications of the ACM, 21(2):120-126,
`February 1978. Cited on: 218.
`The original RSA paper.
`[Rochlis and Eichin, 1989] J. A. Rochlis and M. W. Eichin. With microscope and tweezers: The
`worm from MIT's perspective. Communications of the ACM, 32(6):689- 703, June 1989. Cited
`on: 30, 161, 198.
`
`SAMSUNG EX. 1025 - 11/12
`
`

`

`* QuantuM Books *
`Phoae: 617-494-5042
`4 C•ft•rld,e CeDter
`ftA 02142
`t
`e ftail:
`202
`FTRF.WALLS INTERNET SECURITY
`ililltlll iii* NC
`CHESWICK
`INTERNET
`ADDISO
`$1
`
`Tlil
`
`SAMSUNG EX. 1025 - 12/12
`
`