CINDY A. COHN, ESQ.; SBN 145997 McGLASHAN & SARRAIL Professional Corporation 177 Bovet Road, Sixth Floor San Mateo, CA 94402 Tel: (415) 341-2585 Fax: (415) 341-1395 LEE TIEN, ESQ.; SBN 148216 1452 Curtis Street Berkeley, CA 94702 Tel: (510) 525-0817 Attorneys for Plaintiff Daniel J. Bernstein IN THE UNITED STATES DISTRICT COURT FOR THE NORTHERN DISTRICT OF CALIFORNIA DANIEL J. BERNSTEIN ) ) C 95-00582 MHP Plaintiff, ) ) DECLARATION OF v. ) BRUCE SCHNEIER ) ) UNITED STATES DEPARTMENT OF ) STATE et al., ) ) Defendants. ) ) _________________________________________) I, BRUCE SCHNEIER declare as follows: 1. I am president of Counterpane Systems, a consulting firm specializing in cryptography and computer security. I am the author of Applied Cryptography: Protocols, Algorithms, and Source Code in C, the second edition of which was published in 1996 by John Wiley & Sons, and of E-Mail Security, published in 1995 by John Wiley & Sons. I am a contributing editor to the computer programming magazine Dr. Dobb's Journal where I have edited the "Algorithm Alley" column. I am a member of the board of directors of the International Association for Cryptologic Research. I have personal knowledge of the facts set forth herein, unless otherwise indicated, and if called as a witness could and would so testify. I executed this Declaration at Stanford, California. BASICS OF CRYPTOGRAPHY 2. The aim of encryption is to turn an otherwise intelligible message into gibberish, so that a person who intercepts the message cannot read it. Moreover, the intended recipient should be able to take that gibberish and turn it back into an intelligible message. The science of doing this sort of thing is called cryptography. 3. An example: Alice is the sender, Bob is the receiver, and Eve is the eavesdropper. Alice wants to send a message to Bob. She takes the message, also called the plaintext, and encrypts it. The encrypted message is called the ciphertext. Alice then takes the ciphertext and sends it to Bob. Eve, who intercepts the ciphertext in transmission, can't read it. But Bob, who legitimately receives the ciphertext, is able to decrypt it and recover the plaintext message. This model presupposed some arrangement between Alice and Bob that Eve is not privy to. 4. Encryption is based on two things: an algorithm and a key. An algorithm in cryptography is a mathematical transformation. It transforms plaintext into ciphertext, and it transforms ciphertext back into plaintext. When Alice encrypts a message, she uses an encryption algorithm to transform the plaintext into ciphertext. When Bob decrypts a message, he uses the corresponding decryption algorithm to transform the ciphertext back into plaintext. This encryption transformation can be preformed on the letters of the message or on the digital representation of the message. Prior to the computer age, encryption was primarily done on alphabetic characters. The encryption algorithm would turn the characters of the plaintext message into other characters, or numbers, or symbols. Then, the decryption algorithm would convert them back again. Recently, messages to be encrypted either originate from computers or are typed into computers. In this case, the computer representation of the message (the information bits themselves) are encrypted and decrypted. This generalization means that any digital data can be encrypted: text messages, computer programs, digital audio, digital video, etc. 5. Until very recently (1883 or so), the security of this operation was based on keeping the algorithm secret. If Eve knew the algorithm, she could decrypt the ciphertext just as easily as Bob. But if Alice and Bob keep the details of the algorithm to themselves, Eve won't know what to do. The best she can do is to try to figure out what the algorithm is. This is called cryptanalysis, and there was a whole lot of it going on during World Wars I and II. 6. There are problems with requiring the algorithm to remain secret. One, it is not easy to do. The militaries of the world spend a lot of time and energy keeping their algorithms secret, and still details leak across borders. If the algorithm is embedded in a piece of military hardware--e.g. a tactical radio, a computer modem, a satellite receiver--eventually the enemy will capture or steal one and reverse-engineer the algorithm. If the algorithm is in a commercial piece of software, it only takes a few hours for a clever programmer to disassemble the program and reverse-engineer the algorithm. And once the details of the algorithm ever become public, the security of the entire system is lost forever. 7. Two, if this type of system is going to work for everyone, then each pair of people will need a unique algorithm. If there are 100 people in a network, that means that there must be almost 5000 different algorithms. Each person has to know 100 of them. And he has to keep all of them secret from everyone else. Designing an encryption algorithm that is secure from cryptanalysis is a difficult task; designing 5000 of them is absurd. 8. We can get around these problems with the second basis of cryptography: the key. A key is a random string of ones and zeros (called a bit string)--sometimes a number in binary, sometimes an ASCII value, or sometimes a word or phrase that gets converted to a bit string--that is used in conjunction with an algorithm. An algorithm can take any one of a large number of possible keys. Each different key causes the algorithm to work in a slightly different way. Only two people with the identical key can encrypt and decrypt messages. Someone with one key cannot decrypt messages encrypted with a different key. 9. Think of a lock. The world doesn't need a new lock design for every front door. It's enough to have one design, and hundreds of thousands of different keys. Even if two people are using the same lock, they can't open each other's doors unless they have identical keys. 10. The important aspect of this process is that the security of the system rests primarily within the key. If Eve does not have the exact key that Alice and Bob are using, she cannot decrypt the message. We assume that Eve has complete knowledge of the algorithm. We assume that Eve has a copy of the software that Alice and Bob are using to encrypt messages. (If it is mass-market software, this is a perfectly reasonable assumption.) We can even assume that Eve knows what Alice and Bob are encrypting. (This is not always the case, but a prudent cryptographer will assume that Eve has access to some of the plaintext. In this case, she is attempting to learn the key so that she can decrypt other messages. This was true during World War II, where the British often had the plain text of weather reports and used them to determine the daily German Enigma key so that they could read more interesting messages.) Without the key, Eve cannot decrypt the message. 11. Now, the whole process of encryption is a whole lot easier. Alice and Bob do not have to keep an algorithm secret; they only have to keep a particular key secret. This key might only be twenty or thirty digits, and a whole lot easier to keep secret than an entire software program. They can choose one algorithm, one that has been published and is known to be secure, and not have to design their own. If their message key is compromised, it only compromises the messages encrypted with that key, not all messages encrypted with that algorithm. They can change the key and keep on encrypting messages; they don't have to recall all the software and design a new algorithm. And an entire network of users can communicate securely with one another using just one algorithm and many different keys. 12. This is where encryption is today. We encrypt messages using algorithms that are public and known--the Data Encryption Standard or DES, IDEA, etc.--and secret keys. Different users use different keys; smart users change keys weekly, daily, or even more frequently. Assuming those algorithms are secure, then messages encrypted with them are as secure as the key. 13. The difficulty lies in the assumption that an algorithm is secure. In general, it is impossible to prove the security of an encryption algorithm. (There is one exception known as a "one-time pad" that is not germane to this discussion.) What we have is a handful of algorithms that are believed to be secure. "Believed" is the key word in that sentence. In cryptography, it is only possible to prove that an algorithm is insecure. You can only say is that no one can break the algorithm, yet. You can say that these particular people, all intelligent cryptographers, have spent thousands of man-hours trying to break the algorithm, and they have not succeeded. You can say that there is no known attack that can break the algorithm. But you cannot say that someone won't figure out how to break the algorithm tomorrow. You can't even say that one of those military agencies mentioned above doesn't already know how to break the algorithm, because if they did they would not go public about it. 14. For the most part, the encryption algorithms used in commercial products are all published algorithms, and they are all algorithms that have undergone years of public scrutiny. While this doesn't prove anything, it does instill some confidence in the algorithms. In some cases, it puts bounds on the level of security the algorithm can deliver. This means we can make statement about the algorithm's resistance to specific known attacks. While it is certainly possible that new, unknown, attacks could be developed, it is more likely that an attacker would use known attacks. CRYPTOGRAPHY AS A COMPUTER APPLICATION 15. Cryptography is well-suited for computers. Today almost all cryptography is done by computers or dedicated computer chips. The reason for this is simple: modern cryptographic algorithms are a combination of mathematical and logical operations on bits or groups of bits. This is exactly the kind of thing that computers are so well suited for. In a computer, all information is represented as bits, regardless of what it is or how it is used. 16. An example of a basic mathematical and logical operation which is used in cryptography, but is not itself a cryptographic algorithm, is Euclid's Algorithm. This algorithm was first written down by Euclid in 300 B.C., and describes a method for finding something called a "greatest common divisor" between two numbers. This is the largest factor that they share in common. For example, the greatest common divisor of 18 and 45 is 9; the greatest common divisor of 15 and 28 is 1. Here is Euclid's algorithm being used to find the greatest common divisor of 6 and 22: 22 = 3 * 6 + 4 6 = 1 * 4 + 2 4 = 2 * 2 + 0 The final 0 means the algorithm terminates, and the solution is the third number in the last row: 2. This is Euclid's algorithm written in the C programming language. int gcd (int x, int y) { int g; if (x < 0) x = -x; if (y < 0) y = -y; if (x + y == 0) ERROR; g = y; while (x > 0) {g = x; x = y % x; y = g;} return g; } Running the above program with the inputs 6 and 22 yields the same answer: 2. 17. A more complex algorithm is the IDEA encryption algorithm. It takes a 64 bit block of plaintext and turns it into a 64-bit block of ciphertext, with the help of a 128-bit key. Remember, computers represent everything using bits, so anything in a computer can be encrypted in this manner. IDEA encrypts these bits in groups of 64 bits; this is called a block. By using basic mathematical operations like the exclusive-OR logical operation, addition, and modular multiplication, the computer combines the key and the plaintext message to produce ciphertext. It is somewhat like shuffling cards over and over again, but the cards change because you're shuffling them. A full explanation of how IDEA works is provided in my book, APPLIED CRYPTOGRAPHY (Second Edition), on pages 319-325. It's too involved to discuss here. It is possible to implement IDEA by hand, but it is enormously easier to do it on computer. Remember, computers already represent data in terms of bits, and they naturally do the mathematical operations required by the IDEA algorithm. In my book APPLIED CRYPTOGRAPHY, available in foreign countries such as the U.K. Singapore, Japan, Iran, South Africa, Germany, Russia, Korea, and Australia, I published source code for IDEA written in the C programming language. The State Department has declared that my book is in the public domain and thus freely exportable without a license. Both the description and the C code describe the same thing. They convey the same information. One is easier to read, and the other is easier to embed in a computer program. Any competent programmer can translate one into the other; no cryptographic skills are required. C code for the IDEA algorithm is also freely available on the Internet at archive sites in the U.K., Finland, Germany, New Zealand, and Italy. Internet users from all over the world can download C source code from these sites. THE SCIENCE OF CRYPTOGRAPHY 18. Modern cryptography is a mathematical science. Its practitioners often have doctoral degrees in either mathematics or theoretical computer science. Encryption algorithms are mathematical transformations of plaintext to ciphertext. Techniques to analyze and possibly break algorithms are mathematical in nature. Mathematical areas such as number theory, complexity theory, and information theory are at the heart of modern cryptography. 19. A good example is the RSA public-key cryptosystem. This cryptosystem uses a different kind of "lock" than we're accustomed to. Normally, you lock and unlock your front door with the same key. If you lose that key, the person who finds it can both lock and unlock your door. With RSA, however, there is a pair of keys, one "public" and one "private: you encrypt with the public key, and decrypt with the private key. 20. The big advantage of this "asymmetric" system is that Alice and Bob can each publish their public key. If Alice uses Bob's public key to encrypt her message to him, then Bob decrypts Alice's message using his private key. Alice can't decrypt a message encrypted with Bob's public key if she doesn't know his private key. 21. The trick to RSA is that although in theory one could figure out the private key from the public key, the mathematical relationships between them are believed to be impossible for computers to solve without taking a very long time. For example, the RSA encryption algorithm looks like this: P^E mod N = C This is a mathematical relationship between the key (E and N), the plaintext (P), and the ciphertext (C). Additional mathematical relationships determine how E and N are constructed, as well as the construction of another key: D. 22. Cryptographers believe that the security of the RSA algorithm is based on the difficulty of factoring the number N. Factoring a number means finding the prime numbers that can be multiplied to produce that number; factoring 60, for instance, means showing that 60 = 2 * 2 * 3 * 5. This looks easy, but suppose you multiply two very large prime numbers, each of more than 100 digits? Multiplying these numbers can be done quickly on a computer, but taking that product and factoring it to recover the two 100-digit prime numbers takes much longer. In 1994, a 129-digit number was factored using 600 people and 1600 computers over a period of eight months. 23. The factoring problem is one of the oldest in mathematics. The factoring of the 129-digit number described above used mathematical theory that was not state-of-the-art even at that time. The computation would have taken about one-tenth of the time using the best theory we know of today. Thus, a mathematical problem is at the heart of this encryption algorithm. 24. It is just as natural to look at the above algorithm as computer code. In the LISP programming language, RSA encryption might look like: (DEFFUN RSA-ENCRYPT (P E N) (MODULO (POWER P E) N)) 25. In the C programming language, RSA encryption might look like: number RSA_ENCRYPT (number *P, *E, *N) {return modulo (power (P,E), N) } 26. All of these three representations can be read by programmers and mathematicians, and all convey the same information. Cryptographers use different representations in different contexts. In my book, APPLIED CRYPTOGRAPHY, I used both. Some algorithms I explained using mathematical notation; others I explained using C programming notation. Both notations were intended to be read by humans, and I made my choice based on which notation could best explain the algorithm to my readers. CRYPTOGRAPHY AND EXPORT CONTROLS 27. The ITAR is deliberately vague on the subject of cryptographic research. In APPLIED CRYPTOGRAPHY, I devoted about 100 pages to source code for various cryptographic algorithms. I tried to convince my publisher, John Wiley & Sons, to put the same source code on a computer disk to be distributed with the book. Many books in the area of computers, computer science, and programming are offered with floppy disks containing programs referenced in those books. My publisher initially decided to pursue this option--books with floppy disks or CD-ROMs included tend to sell better than books without--but then backed off when informed about the ITAR. My publisher was unsure about the law, and decided that it was not worth the risk. Instead, I offer a set of disks containing many cryptographic algorithms in source code which I will mail only to addresses within the United States and Canada. Thus, I have been affected by export controls on cryptography. CRYPTOGRAPHERS AS SCIENTISTS 28. Cryptography is a science of making and breaking algorithms. Algorithms are proposed one year and broken the next. For all practical purposes, it is impossible to prove the security of an algorithm. All that you can say is: "I do not know how to break this algorithm, and all of these smart people do not either. 29. It is this reliance on peer review that makes publication and dissemination of algorithms vital to the science of cryptography. All sciences require the constant sharing, evaluating, and criticizing of new ideas, but cryptography has by its very nature an adversarial component. Cryptographic algorithms must be evaluated by other cryptographers, over the course of years, and in public settings. 30. An example is the SAFER algorithm. It was created by James Massey in Switzerland, and published in 1994. That publication included both a description of the algorithm and source code in PASCAL. C source code for SAFER and posted to the Internet. A group of cryptographers invented an alternative key schedule for the algorithm which was also posted to the Internet. Many cryptographers around the world studied the algorithm; these results were also published. More recently, Lars Knudsen of Denmark has proposed a modification to the algorithm designed to correct weaknesses that have been found. His work was completed while he was teaching at a Belgian university and was published in 1995. Source code with Knudsen's modification has already been published on the Internet. 31. Products that use proprietary algorithms, those that are not released to the academic community or to the public, are generally assumed to be weak. Popular software products that try to do this anyway have their cryptography anonymously reverse-engineered and posted to the Internet. (Two examples of this are the algorithms RC2 and RC4.) The reputation of cryptographers is based on what they publish and distribute, not on what they do in secret. 32. Publication means publication of the exact specifications of an algorithm. Sometimes the algorithm is specified in mathematical description. Sometimes it is specified in programming code. Sometimes it is written as a diagram. Sometimes multiple ways are used. 33. The U.S. government specified the DES algorithm mathematically and graphically the moment it was first proposed as a Federal Information Processing Standard. I published source code for DES in Applied Cryptography. The IDEA algorithm, written in Switzerland, was specified in words, pictures, and PASCAL code. I published my own algorithm Blowfish in Dr. Dobb's Journal in words, pictures, and PASCAL code. RC2 and RC4 were first publicly distributed in C code; descriptions followed later. 34. Source code is an especially important dissemination tool because it is exact; it is not subject to interpretation. Cryptographers often publish "reference implementations" of their algorithms. These are meant to be benchmarks against which other implementations are verified. If a cryptographer wants to study an algorithm, he often tests his own code against the reference implementation to ensure that he implemented the algorithm correctly. Reference implementations for many algorithms are available on the Internet, worldwide, for free. / / / /