1
`
`EX 1025
`IPR of Pat. No. 6,892,304
`
`

`
`Publisher: Katherine Schowalter
`Editor: Phil Sutherland
`Assistant Editor: Allison Roarty
`Managing Editor: Robert Aronds
`Text Design & Composition: North Market Street Graphics
`
`Designations used by companies to distinguish their products are often claimed as trademarks. In all
`instances where John Wiley & Sons, Inc. is aware of a claim, the product names appear in initial capital
`or all capital letters. Readers, however, should contact the appropriate companies for more complete
`information regarding trademarks and registration.
`
`This text is printed on acid—free paper.
`
`Copyright © 1996 by Bruce Schneier
`Published by John Wiley & Sons, Inc.
`
`All rights reserved. Published simultaneously in Canada.
`
`This publication is designed to provide accurate and authoritative information in regard to the subject
`matter covered. It is sold with the understanding that the publisher is not engaged in rendering legal,
`accounting, or other professional service. If legal advice or other expert assistance is required, the services
`of a competent professional person should be sought.
`
`In no event will the publisher or author be liable for any consequential, incidental, or indirect damages
`(including damages for loss of business profits, business interruption, loss of business information, and
`the like) arising from the use or inability to use the protocols and algorithms in this book, even if the pub-
`lisher or author has been advised of the possibility of such damages.
`
`Some of the protocols and algorithms in this book are protected by patents and copyrights. It is the
`responsibility of the reader to obtain all necessary patent and copyright licenses before implementing in
`software any protocol or algorithm in this book. This book does not contain an exhaustive list of all appli-
`cable patents and copyrights.
`
`Some of the protocols and algorithms in this book are regulated under the United States Department of
`State International Traffic in Arms Regulations. It is the responsibility of the reader to obtain all neces-
`sary export licenscs before implementing in software for export any protocol 01' algorithm in this book.
`
`Reproduction or translation of any part of this work beyond that permitted by section 107 or 108 of the
`1976 United States Copyright Act without the permission of the copyright owner is unlawful. Requests
`for permission or further information should be addressed to the Permissions Department, John Wiley &
`Sons, Inc.
`
`Library of Congress Cataloging-in-Publication Data:
`Schneier, Bruce
`Applied Cryptography Second Edition : protocols, algorithms, and source code in C
`/ Bruce Schneier.
`p.
`cm.
`Includes bibliographical references (p. 675).
`ISBN 0-471-128457 [cloth : acid—free paper). — ISBN
`O—47l—l l 709-9 (paper : acid—free paper)
`1. Computer security.
`2. Telecommunication—~Security measures.
`3. Cryptography.
`I. Title.
`QA76.9.A25S35
`1996
`O05.8'2—dc2O
`
`95-12393
`CIP
`
`Printed in the United States of America
`20 19
`
`2
`
`

`
` CHAPTER 2 Protocol Building Blocks
`
`(2) Bob sends Alice his public key.
`
`(3) Alice encrypts her message using Bob's public key and sends it to Bob.
`
`(4) Bob decrypts Alice's message using his private key.
`
`Notice how public-key cryptography solves the key—management problem with
`symmetric cryptosystems. Before, Alice and Bob had to agree on a key in secret.
`Alice could choose one at random, but she still had to get it to Bob. She could hand
`it to him sometime beforehand, but that requires foresight. She could send it to him
`by secure courier, but that takes time. Public—key cryptography makes it easy. With
`no prior arrangements, Alice can send a secure message to Bob. Eve, listening in on
`the entire exchange, has Bob's public key and a message encrypted in that key, but
`cannot recover either Bob's private key or the message.
`More commonly, a network of users agrees on a public-key cryptosystem. Every
`user has his or her own public key and private key, and the public keys are all pub-
`lished in a database somewhere. Now the protocol is even easier:
`
`(1) Alice gets Bob's public key from the database.
`(2) Alice encrypts her message using Bob's public key and sends it to Bob.
`(3) Bob then decrypts Alice's message using his private key.
`
`In the first protocol, Bob had to send Alice his public key before she could send
`him a message. The second protocol is more like traditional mail. Bob is not
`involved in the protocol until he wants to read his message.
`
`Hybrid Cryptosystems
`The first public—l<ey algorithms became public at the same time that DES was ‘I
`being discussed as a proposed standard. This resulted in some partisan politics in the
`cryptographic community. As Diffie described it [494]:
`
`The excitement public key cryptosystems provoked in the popular and scientific
`press was not matched by corresponding acceptance in the cryptographic estab-
`lishment, however. In the same year that public key cryptography was discovered,
`the National Security Agency (NSA), proposed a conventional cryptographic sys-
`tem, designed by International Business Machines (IBM), as a federal Data
`Encryption Standard (DES). Marty Hellman and I criticized the proposal on the
`ground that its key was too small, but manufacturers were gearing up to support
`the proposed standard and our criticism was seen by many as an attempt to dis-
`rupt the standards-making process to the advantage of our own work. Public key
`cryptography in its turn was attacked, in sales literature [1125] and technical
`papers (849, 1159] alike, more as though it were a competing product than a recent
`research discovery. This, however, did not deter the NSA from claiming its share
`of the credit. Its director, in the words of the Encyclopedia Britannica [I461],
`pointed out that ”two-key cryptography had been discovered at the agency a
`decade earlier,” although no evidence for this claim was ever offered publicly.
`
`3
`
`

`
`4
`
`

`
`CHAPTER 2 Protocol Building Blocks
`
`key is vulnerable to compromise, but it is at less risk because it is only used once per
`communication to encrypt a session key. This is further discussed in Section 3.1.
`
`Merkle’s Puzzles
`
`Ralph Merkle invented the first construction of public—key cryptography. In 1974
`he registered for a course in computer security at the University of California,
`Berkeley, taught by Lance Hoffman. His term paper topic, submitted early in the
`term, addressed the problem of ”Secure Communication over Insecure Channels”
`(1064). Hoffman could not understand Merkle’s proposal and eventually Merkle
`dropped the course. He continued to work on the problem, despite continuing fail-
`ure to make his results understood.
`Merkle’s technique was based on ”puzzles” that were easier to solve for the
`sender and receiver than for an eavesdropper. Here's how Alice sends an encrypted
`message to Bob without first having to exchange a key with him.
`
`(1) Bob generates 21°, or about a million, messages of the form: ”This is puzzle
`number X. This is the secret key number y, ” where X is a random number
`and y is a random secret key. Both X and y are different for each message.
`Using a symmetric algorithm, he encrypts each message with a different
`20-bit key and sends them all to Alice.
`(2) Alice chooses one message at random and performs a brute—force attack to
`recover the plaintext. This is a large, but not impossible, amount of work.
`(3) Alice encrypts her secret message with the key she recovered and some
`symmetric algorithm, and sends it to Bob along with X.
`(4) Bob knows which secret key y he encrypts in message X, so he can decrypt
`the message.
`
`Eve can break this system, but she has to do far more work than either Alice or
`Bob. To recover the message in step (3), she has to perform a brute—force attack
`against each of Bob's 22° messages in step (1); this attack has a complexity of 24°. The
`X values won't help Eve either; they were assigned randomly in step (1). In general,
`Eve has to expend approximately the square of the effort that Alice expends.
`This 11 to n2 advantage is small by cryptographic standards, but in some circum-
`stances it may be enough. If Alice and Bob can try ten thousand keys per second, it
`will take them a minute each to perform their steps and another minute to com-
`municate the puzzles from Bob to Alice on a 1.544 MB link. If Eve had comparable
`computing facilities, it would take her about a year to break the system. Other algo-
`rithms are even harder to break.
`
`2.6 DIGITAL SIGNATURES
`
`Handwritten signatures have long been used as proof of authorship of, or at least
`agreement with, the contents of a document. What is it about a signature that IS so
`compelling [I392]?
`
`5
`
`

`
`6
`
`

`
`CHAPTER 2 Protocol Building Blocks
`
`Is this as good as a paper signature? Let's look at the characteristics we want:
`
`1. This signature is authentic. Trent is a trusted arbitrator and Trent knows
`that the message came from Alice. Trent's certification serves as proof to
`Bob.
`
`. This signature is unforgeable. Only Alice (and Trent, but everyone trusts
`him) knows KA, so only Alice could have sent Trent a message encrypted
`with KA. If someone tried to impersonate Alice, Trent would have imme-
`diately realized this in step (2) and would not certify its authenticity.
`. This signature is not reusable. If Bob tried to take Trent's certification and
`attach it to another message, Alice would cry foul. An arbitrator (it could
`be Trent or it could be a completely different arbitrator with access to the
`same information) would ask Bob to produce both the message and Alice's
`encrypted message. The arbitrator would then encrypt the message with
`KA and see that it did not match the encrypted message that Bob gave him.
`Bob, of course, could not produce an encrypted message that matches
`because he does not know KA.
`
`. The signed document is unalterable. Were Bob to try to alter the document
`after receipt, Trent could prove foul play in exactly the same manner just
`described.
`‘
`
`. The signature cannot be repudiated. Even if Alice later claims that she
`never sent the message, Trent's certification says otherwise. Remember,
`Trent is trusted by everyone; what he says is true.
`
`If Bob wants to show Carol a document signed by Alice, he can't reveal his secret
`key to her. He has to go through Trent again:
`
`(1)
`
`(2)
`
`(3)
`
`(4)
`
`(5)
`
`Bob takes the message and Trent's statement that the message came from
`Alice, encrypts them with K3, and sends them back to Trent.
`
`Trent decrypts the bundle with K3.
`
`Trent checks his database and confirms that the original message came
`from Alice.
`
`Trent re—encrypts the bundle with the secret key he shares with Carol, KC,
`and sends it to Carol.
`
`Carol decrypts the bundle with Kc. She can now read both the message and
`Trent's certification that Alice sent it.
`'
`
`These protocols work, but they're time-consuming for Trent. He must spend his
`days decrypting and encrypting messages, acting as the intermediary between every
`pair of people who want to send signed documents to one another. He must keep a
`database of messages (although this can be avoided by sending the recipient a copy
`of the sender's encrypted message). He is a bottleneck in any communications sys-
`tem, even if he's a mindless software program.
`
`7
`
`

`
`2.6 Digital Signatures
`
`Harder still is creating and maintaining someone like Trent, someone that every-
`one on the network trusts. Trent has to be infallible; if he makes even one mistake in
`a million signatures, no one is going to trust him. Trent has to be completely secure.
`If his database of secret keys ever got out or if someone managed to modify his pro-
`gramming, everyone’s signatures would be completely useless. False documents pur-
`ported to be signed years ago could appear. Chaos would result. Governments would
`collapse. Anarchy would reign. This might work in theory, but it doesn't work very
`well in practice.
`
`Digital Signature Trees
`Ralph Merkle proposed a digital signature scheme based on secret-key cryptogra-
`phy, producing an infinite number of one-time signatures using a tree structure
`[l067,1068]. The basic idea of this scheme is to place the root of the tree in some
`public file, thereby authenticating it. The root signs one message and authenticates
`its sub-nodes in the tree. Each of these nodes signs one message and authenticates
`its sub-nodes, and so on.
`Signing Documents with Public-Key Cryptography
`There are public—key algorithms that can be used for digital signatures. In some
`algorithms—RSA is an example (see Section 19.3)—either the public key or the pri-
`vate key can be used for encryption. Encrypt a document using your private key, and
`you have a secure digital signature. In other cases—DSA is an example (see Section
`20.1)——there is a separate algorithm for digital signatures that cannot be used for
`encryption. This idea was first invented by Diffie and Hellman [496] and further
`expanded and elaborated on in other texts [1282, 1328,1024, 1283,426]. See [1099] for
`a good survey of the field.
`The basic protocol is simple:
`(1) Alice encrypts the document with her private key, thereby signing the doc-
`ument.
`
`(2) Alice sends the signed document to Bob.
`(3) Bob decrypts the document with Alice's public key, thereby verifying the
`signature.
`
`This protocol is far better than the previous one. Trent is not needed to either sign
`or verify signatures. (He is needed to certify that Alice's public key is indeed her
`public key.) The parties do not even need Trent to resolve disputes: If Bob cannot
`perform step (3), then he knows the signature is not valid.
`This protocol also satisfies the characteristics we're looking for:
`1. The signature is authentic; when Bob verifies the message with Alice's
`public key, he knows that she signed it.
`2. The signature is unforgeable; only Alice knows her private key.
`. The signature is not reusable; the signature is a function of the document
`and cannot be transferred to any other document.
`
`8
`
`

`
`CHAPTER 2 Protocol Building Blocks
`
`4. The signed document is unalterable; if there is any alteration to the docu-
`ment, the signature can no longer be verified with Alice's public key.
`5. The signature cannot be repudiated. Bob doesn't need Alice's help to verify
`her signature.
`
`Signing Documents and Timestamps
`Actually, Bob can cheat Alice in certain circumstances. He can reuse the docu-
`ment and signature together. This is no problem if Alice signed a contract (what's
`another copy of the same contract, more or less?], but it can be very exciting if Alice
`signed a digital check.
`Let's say Alice sends Bob a signed digital check for $100. Bob takes the check to
`the bank, which verifies the signature and moves the money from one account to
`the other. Bob, who is an unscrupulous character, saves a copy of the digital check.
`The following week, he again takes it to the bank (or maybe to a different bank). The
`bank verifies the signature and moves the money from one account to the other. If
`Alice never balances her checkbook, Bob can keep this up for years.
`Consequently, digital signatures often include timestamps. The date and time of
`the signature are attached to the message and signed along with the rest of the mes-
`sage. The bank stores this timestamp in a database. Now, when Bob tries to cash
`Alice's check a second time, the bank checks the timestamp against its database.
`Since the bank already cashed a check from Alice with the same timestamp, the
`bank calls the police. Bob then spends 15 years in Leavenworth prison reading up on
`cryptographic protocols.
`
`Signing Documents with Public-Key Cryptography
`and One-Way Hash Functions
`In practical implementations, public-key algorithms are often too inefficient to
`sign long documents. To save time, digital signature protocols are often imple-
`mented with one-way hash functions [432,433}. Instead of signing a document,
`Alice signs the hash of the document. In this protocol, both the one-way hash func-
`tion and the digital signature algorithm are agreed upon beforehand.
`
`(1) Alice produces a one-way hash of a document.
`(2) Alice encrypts the hash with her private key, thereby signing the docu-
`ment.
`
`(3) Alice sends the document and the signed hash to Bob.
`(4) Bob produces a one-way hash of the document that Alice sent. He then,
`using the digital signature algorithm, decrypts the signed hash with Alice's
`public key. If the signed hash matches the hash he generated, the signature
`is valid.
`
`Speed increases drastically and, since the chances of two different documents hav-
`ing the same 160-bit hash are only one in 216°, anyone can safely equate a signature
`of the hash with a signature of the document. If a non—one-way hash function were
`
`9
`
`

`
`CHAPTER 24 Example Implementations
`
`dently. Such dual control provides a high degree of assurance concerning the
`3
`integrity and pedigree of any keys introduced into the system.
`A key of type DATA is provided for compatibility with other systems. A DATA .’
`key is stored with a CV that identifies the key as a DATA key. DATA keys can have V
`broad uses and as such must be regarded with suspicion and used with care. DATA A
`keys may not be used for any key management functions.
`The Commercial Data Masking Facility (CDMF) provides an exportable version of
`CCA. It has a special feature that reduces DES keys to an effective 40 bits for export
`(see Section 15.5) [785].
`
`it
`
`24.9 ISO AUTHENTICATION FRAMEWORK
`
`Public—key cryptography has been recommended for use with the ISO authentica-
`tion framework, also known as the X.509 protocols [B04]. This framework provides
`for authentication across networks. Although no particular algorithms are specified
`for either security or authentication, the specification recommends RSA. There are‘
`
`Serial Number
`
`Algorithm Identifier:
`— Algorithm
`— Parameters
`
`Issuer
`
`Period of Validity:
`— Not Before Date
`— Not After Date
`
`Subject
`
`Subject’s Public Key:
`— Algorithm
`— Parameters
`— Public Key
`
`Signature
`
`Figure 24.2 An X.509 certificate.
`
`10
`
`

`
`24.9 ISO Authentication Framework
`
`nce concerning
`
`f systems. A D,
`)ATA keys can h
`ed with care. DA __,
`
`amework prov ve_
`thms are Specific;
`ds RgA_ There an
`
`visions, however, for multiple algorithms and hash functions. X.509 was ini-
`ly issued in 1988. After public review and comment, it was revised in 1993 to
`I crrect some security problems [1 100,750].
`
`Certificates
`The most important part of X.509 is its structure for public—key certificates. Each
`ser has a distinct name. A trusted Certification Authority (CA) assigns a unique
`ame to each user and issues a signed certificate containing the name and the user's
`ublic key. Figure 24.2 shows an X.509 certificate [304].
`The version field identifies the certificate format. The serial number is unique
`within the CA. The next field identifies the algorithm used to sign the certificate,
`together with any necessary parameters. Issuer is the name of the CA. The period of
`_ validity is a pair of dates; the certificate is valid during the time period between the
`two. Subject is the name of the user. The subject's public key information includes
`the algorithm name, any necessary parameters, and the public key. The last field is
`the CA’s signature.
`If Alice wants to communicate with Bob, she first gets his certificate from a data-
`/
`3 base. Then she Verifies its authenticity. If both share the same CA, this is easy. Alice
`simply verifies the CA’s signature on Bob's certificate.
`If they use different CAs, it's more complicated. Think of a tree structure, with
`different CAs certifying other CAS and users. On the top is one master CA. Each CA
`has a certificate signed by the CA above it, and by the CA5 below it. Alice uses these
`certificates to Verify Bob’s certificate.
`Figure 24.3 illustrates this. Alice's certificate is certified by CAA; Bob's is certified
`by CAB. Alice knows CAA’s public key. CAC has a certificate signed by CAA, so Alice
`
`-.
`
`Figure 24.3 Sample certification hierarchy.
`
`11
`
`11