New Private eMail Software 11:09 pm Jun 13, 1991 Source: Peacenet (Fido:250/722) igc:ahoeltje Conf: ecp.news The following is an extract from the manual for a new MSDOS software product called "Pretty Good Privacy." The complete software package, including all source code written in C, is free to all who want it. Any product that promotes vital progressive social change can only fall into the category of "forbidden fruit." This is just such a product. There are elements within our government that do not want you to exchange electronic communications in private. Imagine their distress when they can no longer read your electronic "postcards" but need to employ very expen- sive techniques to read your electronic letters, securely sealed with a digital signature! Electronic mail will soon replace paper mail. We must have privacy guaranteed and in place before that happens. PGP is the first major effort in that direction. There is an urgent need to distribute this product as soon as possible. Please ask PeaceNet support how to obtain PGP. If they have decided not to supply PGP then you can get a copy of it from me. I will upload it to you or, if you insist, send you a disk. T H I S I S I M P O R T A N T S T U F F ! PLEASE READ ON! ----------------------------------------------------------------- ---------- Extract from PGPGUIDE.DOC released Wednesday, June 5, 1991 Quick Overview ============== Pretty Good(tm) Privacy (PGP), from Phil's Pretty Good Software, is a high security cryptographic software application for MSDOS. PGP allows people to exchange files or messages with privacy, authentication, and conve- nience. Privacy means only those intended to receive a message can read it. Authentication means messages that appear to be from a particular person can only have originated from that person. Convenience means that privacy and authentication are provided without the hassles of managing keys associated with conventional cryptographic software. No secure channels are needed to exchange keys between users, which makes PGP much easier to use. This is because PGP is based on an powerful new technology called "public key" cryptography. PGP combines the convenience of the Rivest-Shamir-Adleman (RSA) public key cryptosystem with the speed of fast conventional cryptographic algorithms, fast message digest algorithms, data compression, and sophisticated key management. And PGP performs the RSA functions faster than most other software implementations. PGP is RSA public key cryptography for the masses. PGP does not provide any built-in modem communications capability. You must use a separate product such as TELIX or PROCOMM for that. This document only explains how to use PGP without explaining the underly- ing technology details and data structures and cryptographic algorithms. It would help if you were already familiar with the concept of cryptography in general and RSA public key cryptography in particular. Nonetheless, here are a few introductory remarks about public key cryptography. How it Works ============ In conventional cryptosystems, such as the Federal Data Encryption Standard (DES), a single key is used for both encryption and decryption. This means that keys must be initially transmitted via secure channels so that both parties can know them before encrypted messages can be sent over insecure channels. This may be inconvenient. If you have a secure channel for exchanging keys, then why do you need cryptography in the first place? In public key cryptosystems, everyone has two related complimentary keys, a publicly revealed key and a secret key. Each key unlocks the code that the other key makes. Knowing the public key does not help you deduce the corresponding secret key. The public key can be published and widely disseminated across a communications network. This protocol provides privacy without the need for the same kind of secure channels that a conventional cryptosystem requires. Anyone can use a recipient's public key to encrypt a message to that person, and that recipient uses her own corresponding secret key to decrypt that message. No one but the recipient can decrypt it, because no one else has access to that secret key. Not even the person who encrypted the message can decrypt it. Message authentication is also provided. The sender's own secret key can be used to encrypt a message, thereby "signing" it. This creates a digital signature of a message, which the recipient (or anyone else) can check by using the sender's public key to decrypt it. This proves that the sender was the true origin of the message, and that the message has not been subsequently altered by anyone else, because the sender alone possesses the secret key that made that signature. Forgery of a signed message is infeasible, and the sender cannot later disavow his signature. These two processes can be combined to provide both privacy and authentication by first signing a message with your own secret key, then encrypting the signed message with the recipient's public key. The recipient reverses these steps by first decrypting the message with her own secret key, then checking the enclosed signature with your public key. These steps are done automatically by the recipient's software. Because the RSA public key encryption algorithm is so slow, encryption is better accomplished by using a high-quality fast conventional encryption algorithm to encipher the message. This original unenciphered message is called "plaintext". In a process invisible to the user, a temporary random key, created just for this one "session", is used to conventionally encipher the plaintext file. Then the recipient's RSA public key is used to encipher this temporary random conventional key. This RSA-enciphered conventional "session" key is sent along with the enciphered text (called "ciphertext") to the recipient. The recipient uses her own RSA secret key to recover this temporary session key, and then uses that key to run the fast conventional algorithm to decipher the large ciphertext message. RSA keys are kept in "key certificates" that include the key owner's user ID (which is that person's name), a timestamp of when the key pair was generated, and the actual key material. A key file, or "key ring" contains one or more of these key certificates. Public key certificates contain the public key material, while secret key certificates contain the secret key material. Public key rings contain only public keys, and secret key rings contain just secret keys. Secret keys are cryptographically protected by their own password. The keys are also internally referenced by a "key ID", which is an "abbreviation" of the public key (the least significant 64 bits of the large public RSA key). When this key ID is displayed, only the lower 24 bits are shown for further brevity. While many keys may share the same user ID, for all practical purposes no two keys share the same key ID. PGP uses message digests to form signatures. A message digest is a 128-bit cryptographically strong one-way hash function of the message. It is somewhat analogous to a "checksum" or CRC error checking code, in that it compactly "represents" the message and is used to detect changes in the message. Unlike a CRC, however, it is computationally infeasible for an attacker to devise a substitute message that would produce an identical message digest. The message digest gets encrypted by the RSA secret key to form a signature. The message digest algorithm used here is the MD4 Message Digest Algorithm, placed in the public domain by RSA Data Security, Inc. Documents are signed by prefixing them with signature certificates, which contain the key ID of the key that was used to sign it, an RSA-signed message digest of the document, and a timestamp of when the signature was made. The key ID is used by the receiver to look up the sender's public key to check the signature. The receiver's software automatically looks up the sender's public key and user ID in the receiver's public key ring. Encrypted files are prefixed by the key ID of the public key used to encrypt them. The receiver uses this key ID message prefix to look up the secret key needed to decrypt the message. The receiver's software automat- ically looks up the necessary secret decryption key in the receiver's secret key ring. These two types of key rings are the principal method of storing and managing public and secret keys. Rather than keep individual keys in separate key files, they are collected in key rings to facilitate the automatic lookup of keys either by key ID or by user ID. Each user keeps his own pair of key rings. An individual public key is temporarily kept in a separate file long enough to send to your friend who will then add it to her key ring. An individual key file is no different from a key ring that contains only one key. A Peek Under the Hood ===================== Let's take a look at a few internal features of PGP. Random Numbers PGP uses a cryptographically strong pseudorandom number generator for creating temporary conventional session keys. The seed file for this is called "randseed.pgp". It too can be kept in whatever directory is indicated by the PGPPATH environmental variable. If this random seed file does not exist, it will be automatically created and seeded with truly random numbers derived from timing your keystroke latencies. This generator reseeds the disk file each time it is used with new key material partially derived with the time of day and other truly random sources. It uses the conventional encryption algorithm as an engine for the random number generator. The seed file contains both random seed material and random key material to key the conventional encryption engine for the random generator. If you are a security fanatic and distrust any algorithmically derived random number source however strong, you can defeat this feature by creating an empty file named "randseed.pgp". This file must be empty or nearly empty to turn off this pseudorandom generator. In that case, every encryption session key will require a bothersome request to the user to type some text in at the keyboard to measure the keystroke intervals with a high speed timer. It would be more convenient and not that unsafe to use the strong pseudorandom generator. PGP's Conventional Encryption Algorithm PGP does not use the DES as its conventional single-key algorithm to encrypt messages. Instead it uses a custom conventional single-key block encryption algorithm. It "bootstraps" into this faster algorithm by using RSA to encipher the conventional session key. For the cryptographically curious, PGP's conventional block cipher has a 256-byte block size for the plaintext and the ciphertext. It also uses a key size of up to 256 bytes. Permutation and substitution are used on all the bits throughout the block in each round, rapidly building intersymbol dependance between the ciphertext and both the plaintext and the key. It can be configured to run from 1 to 8 rounds. It compares well with software implementations of the DES in speed. Like the DES, it can be used in cipher feedback (CFB) and cipher block chaining (CBC) modes. PGP uses it in CFB mode. PGP's conventional encryption algorithm is based in large part on cryptographer Charles Merritt's algorithms. Merritt's algorithm does have something of a track record; derivatives of it have been used for secure U.S. military communications. Merritt's original designs were refined by Zhahai Stewart and myself to improve security and to improve performance in a portable C implementation. The algorithm has not yet (in 1991) been through a formal security review and has had only limited peer review. It has been carefully scrutinized for weaknesses. A full discussion of the architecture is beyond the scope of this preliminary draft of this document. Interested parties can get design details from me or from the published source code. Data Compression PGP normally compresses the plaintext before encrypting it. It's too late to compress it after it has been encrypted; encrypted data is incompressible. Data compression saves modem transmission time and disk space and more importantly strengthens cryptographic security. Most cryptanalysis techniques exploit redundancies found in the plaintext to crack the cipher. Data compression reduces this redundancy in the plaintext, thereby greatly enhancing resistance to cryptanalysis. It seems to take longer to compress the plaintext than to encrypt it, but from a security point of view it seems worth the extra time, at least in my cautious opinion. Files that are too short to compress or just don't compress well are not compressed by PGP. If you prefer, you can use PKZIP to compress the plaintext before encrypting it. PKZIP is a widely-available and effective MSDOS shareware compression utility from PKWare, Inc (9025 N Deerwood Dr, Brown Deer, WI 53223). Unlike PGP's built-in compression algorithm, PKZIP has the nice feature of compressing multiple files into a single compressed file, which is recon- stituted again into separate files when decompressed. PKZIP also compress- es faster than the internal compression algorithm used in PGP. PGP will not try to compress a plaintext file that has already been compressed by PKZIP. After decrypting, the recipient can decompress the plaintext with PKUNZIP. If the decrypted plaintext is a PKZIP compressed file, PGP will automatically recognize this and will advise the recipient that the decrypted plaintext appears to be a PKZIP file. For the technically curious readers, PGP uses the public domain LZHuf compression routines written in Japan by Haruyasu Yoshizaki, based on the original LZSS compression routines by Haruhiko Okumura. The adaptive Huffman algorithm was added by Yoshizaki to increase speed and compression, and he used the LZHuf routines to develop the LHarc archiver. Allan Hoeltje added a run-length encoding layer for better speed. This compres- sion software was selected for PGP because of its public domain portable C source code availability, and because it has a good compression ratio. Trusting Snake Oil ================== When examining a cryptographic software package, the question always remains, why should you trust this product? Even if you examined the source code yourself, not everyone has the cryptographic experience to judge the security. Even if you are an experienced cryptographer, subtle weaknesses in the algorithms could still elude you. When I was in college in the early seventies, I devised what I believed was a brilliant encryption scheme. A simple pseudorandom number stream was added to the plaintext stream to create ciphertext. This would seemingly thwart any frequency analysis of the ciphertext, and would be uncrackable even to the most resourceful Government intelligence agencies. I felt so smug about my achievement. So cock-sure. Years later, I discovered this same scheme in several introductory cryptog- raphy texts and tutorial papers. How nice. Other cryptographers had thought of the same scheme. Unfortunately, the scheme was presented as a simple homework assignment on how to use elementary cryptanalytic techniques to trivially crack it. So much for my brilliant scheme. From this humbling experience I learned how easy it is to fall into a false sense of security when devising an encryption algorithm. Many mainstream software engineers have developed equally naive encryption schemes (often even the very same encryption scheme), and some of them have been incorpo- rated into commercial encryption software packages and sold for good money to thousands of unsuspecting users. This is like selling automotive seat belts that look good and feel good, but snap open in even the slowest crash test. Depending on them may be worse than not wearing seat belts at all. No one suspects they are bad until a real crash. Depending on weak cryptographic software may cause you to unknowingly place sensitive information at risk. You might not otherwise have done so if you had no cryptographic software at all. Perhaps you may never even discover your data has been compromised. Sometimes commercial packages use the Federal Data Encryption Standard (DES), a good conventional algorithm recommended by the Government for commercial use (but not for classified information, oddly enough-- Hmmm). There are several "modes of operation" the DES can use, some of them better than others. The Government specifically recommends not using the weakest simplest mode for messages, the Electronic Codebook (ECB) mode. But they do recommend the stronger and more complex Cipher Feedback (CFB) or Cipher Block Chaining (CBC) modes. Unfortunately, most of the commercial encryption packages I've looked at use ECB mode. When I've talked to the authors of a number of these implementations, they say they've never heard of CBC or CFB modes, and didn't know anything about the weaknesses of ECB mode. The very fact that they haven't even learned enough cryptography to know these elementary concepts is not reassuring. These same software packages often include a second faster encryption algorithm that can be used instead of the slower DES. The author of the package often thinks his proprietary faster algorithm is as secure as the DES, but after questioning him I usually discover that it's just a variation of my own brilliant scheme from college days. Or maybe he won't even reveal how his proprietary encryption scheme works, but assures me it's a brilliant scheme and I should trust it. I'm sure he believes that his algorithm is brilliant, but how can I know that without seeing it? In all fairness I must point out that these products do not come from companies that specialize in cryptographic technology. In some ways, cryptography is like pharmaceuticals. Its integrity may be absolutely crucial. Bad penicillin looks the same as good penicillin. You can tell if your spreadsheet software is wrong, but how do you tell if your cryptography package is weak? The ciphertext produced by a weak encryption algorithm looks as good as ciphertext produced by a strong encryption algorithm. There's a lot of snake oil out there. A lot of quack cures. Unlike the patent medicine hucksters of old, these software implementors usually don't even know their stuff is snake oil. They usually haven't even read any of the academic literature in cryptography. But they think they can write good cryptographic software. And why not? After all, it seems intuitively easy to do so. And their software seems to work okay. The Government has peddled snake oil too. After World War II, the US sold German Enigma ciphering machines to third world governments. But they didn't tell them that the Allies cracked the Enigma code during the war, a fact that remained classified for many years. Even today many Unix systems worldwide use the Enigma cipher for file encryption, in part because the Government has created legal obstacles against using better algorithms. They even tried to prevent the initial publication of the RSA algorithm in 1977. And they have squashed essentially all commercial efforts to develop effective secure telephones for the general public. The principle job of the US Government's National Security Agency (NSA) is to gather intelligence, principally by covertly tapping into people's private communications (see James Bamford's book, "The Puzzle Palace"). They have amassed considerable skill and resources for cracking codes. When people can't get good cryptography to protect themselves, it makes NSA's job much easier. NSA also has the responsibility of approving and recommending encryption algorithms. Some critics charge that this is a conflict of interest, like putting the fox in charge of guarding the henhouse. NSA has been pushing a new encryption algorithm that they designed, and they won't tell anybody how it works because that's classi- fied. They want others to trust it and use it. But any cryptographer can tell you that a well-designed encryption algorithm does not have to be classified to remain secure. Only the keys should need protection. How does anyone else really know if NSA's classified algorithm is secure? It's not that hard for NSA to design an encryption algorithm that only they can crack, if no one else can review the algorithm. Are they deliberately selling snake oil? I'm not as cock-sure about the security of PGP as I once was about my brilliant encryption software from college. If I were, that would be a bad sign. But I'm pretty sure that PGP does not contain any snake oil. Source code is available, so other cryptographers are welcome to review its design. It's reasonably well researched. It's based on the work of a number of reputable cryptographers. It's been years in the making. And I don't work for the NSA. I hope it doesn't require a large "leap of faith" to trust the security of PGP. Why Do You Need PGP? ==================== It's personal. It's private. And it's no one's business but yours. You may be planning a political campaign, discussing your taxes, or having an illicit affair. Or you may be doing something that you feel shouldn't be illegal, but is. Whatever it is, you don't want your private electronic mail (E-mail) or confidential documents read by anyone else. There's nothing wrong with asserting your privacy. Privacy is as apple-pie as the Constitution. Perhaps you think your E-mail is legitimate enough that encryption is unwarranted. If you really are a law-abiding citizen with nothing to hide, then why don't you always send your paper mail on postcards? Why not submit to drug testing on demand? Why require a warrant for police searches of your house? Are you trying to hide something? You must be a subversive or a drug dealer if you hide your mail inside envelopes. Or maybe a paranoid nut. Do law-abiding citizens have any need to encrypt their E-mail? What if everyone believed that law-abiding citizens should use postcards for their mail? If some brave soul tried to assert his privacy by using an envelope for his mail, it would draw suspicion. Perhaps the authorities would open his mail to see what he's hiding. Fortunately, we don't live in that kind of world. Because everyone protects most of their mail with envelopes, no one draws suspicion by asserting their privacy with an envelope. There's safety in numbers. Analogously, it would be nice if everyone routinely used encryption for all their E-mail, innocent or not, so that no one drew suspicion by asserting their E-mail privacy with encryption. Think of it as a form of solidarity. If the Government wants to violate the privacy of ordinary citizens, it has to expend a certain amount of expense and labor to intercept and steam open and read paper mail, and listen to and possibly transcribe spoken telephone conversation. This kind of labor-intensive monitoring is not practical on a large scale. This is only done in important cases when it seems worth- while. More and more of our private communications are going to be routed through electronic channels. Electronic mail will gradually replace conventional paper mail. E-mail messages are just too easy to intercept and scan for interesting keywords. This can be done easily, routinely, automatically, and undetectably on a grand scale. International cablegrams are already scanned this way on a large scale by the NSA. We are moving toward a future when the nation will be crisscrossed with high capacity fiber optic data networks linking together all our increas- ingly ubiquitous personal computers. E-mail will be the norm for everyone, not the novelty it is today. Perhaps the Government will protect our E- mail with Government-designed encryption algorithms. Probably most people will trust that. But perhaps some people will prefer their own protective measures. The 17 Apr 1991 New York Times reports on an unsettling US Senate proposal that is part of a counterterrorism bill. If this nonbinding resolution became real law, it would force manufacturers of secure communications equipment to insert special "trap doors" in their products, so that the Government can read anyone's encrypted messages. It reads: "It is the sense of Congress that providers of electronic communications services and manufacturers of electronic communications service equipment shall insure that communications systems permit the Government to obtain the plain text contents of voice, data, and other communications when appropriately authorized by law." If privacy is outlawed, only outlaws will have privacy. Intelligence agencies have access to good cryptographic technology. So do the big arms and drug traffickers. So do defense contractors, oil companies, and other corporate giants. But ordinary people and grassroots political organiza- tions mostly do not have access to affordable "military grade" public-key cryptographic technology. PGP enables people to take their privacy into their own hands. There's a growing social need for it. That's why I wrote it. Acknowledgements ================ I'd like to thank the following people for their contributions to the creation of PGP. Charlie Merritt designed the prototypic conventional encryption algorithm and taught me how to do decent multiprecision arithme- tic. Zhahai Stewart wrote some 8086 assembly primitives and gave many helpful suggestions on PGP file formats and on the conventional encryption algorithm improvements. Allan Hoeltje integrated the LZHuf compression routines into PGP. These were developed and placed in the public domain by Haruyasu Yoshizaki and Haruhiko Okumura. The MD4 routines were developed and placed in the public domain by Ron Rivest. Charlie Merritt can be reached at PO Box 317, West Fork, AR 72774. Zhahai Stewart can be reached at 6521 Old Stage Rd, Boulder, CO 80302. Allan Hoeltje can be reached at PO Box 18045, Boulder, CO 80308. About the Author ================ Philip Zimmermann is a software engineer consultant with 17 years experi- ence, specializing in embedded real-time systems, cryptography, authentica- tion, and data communications. Experience includes design and implementa- tion of authentication systems for financial information networks, network data security, key management protocols, embedded real-time multitasking executives, operating systems, and local area networks. Faster versions of RSA implementations are available from Zimmermann, as well as other cryptography and authentication products and custom product development services. His consulting firm's address is: Boulder Software Engineering 3021 Eleventh Street Boulder, Colorado 80304 USA Phone 303-444-4541 (10:00am - 7:00pm Mountain Time) FAX 303-444-4541 ext 10 Internet: prz@sage.cgd.ucar.edu