Modern cryptography

Secure cryptosystems

As mentioned before, most of the ciphers we have examined are not really cryptographically secure, although they may have been adequate prior to the widespread availability of computers. A cryptosystem is called secure if a good cryptanalyst, armed with knowledge the details of the cipher (but not the key used), would require a prohibitively large amount of computation to decipher a plaintext. This idea (that the potential cryptanalyst knows everything but the key) is called Kerckhoff's Law or sometimes Shannon's Maxim.

Kerckhoff's Law at first seems unreasonably strong rule; you may be thinking that, given a mass of encrypted data, how is the cryptanalyst to know by what means it was encrypted? If you are encrypting your own files for personal use and writing your own software which you keep under lock and key, this assumption is not unreasonable. But today, most encryption is done by software or hardware that the user did not produce himself. One can reverse engineer a piece of software (or hardware) and make the cryptographic algorithm apparent, so we cannot rely on the secrecy of the method alone as a good measure of security. For example, when you make a purchase over the internet, the encryption method that is used between your browser and the seller's web server is public knowledge. Indeed, it must be public: if not, only those privy to the secret could create web browsers or web servers. The security of the transaction depends on the security of the keys.

There are several widely used ciphers which are believed to be fairly secure. We will not go into the details of any of these; most of the algorithms are quite involved and require manipulations at the bit level-- Maple is not really the appropriate tool for them. Implementations are widely available, both commercially and as free public software (see, for example, the International Cryptography page).

Probably the most commonly used cipher today is DES (the Data Encryption Standard), which was developed in the 1970s and has been adopted as a standard by the US government. The standard implementation of DES operates on 64-bit blocks (that is, it uses an alphabet of length 2⁶⁴-- each ``character'' is 8 bytes long), and uses a 56-bit key. Unfortunately, the 56-bit key means that DES, while secure enough to thwart the casual cryptanalyst, is attackable with special hardware by governments, major corporations, and probably well-heeled criminal organizations. One merely needs to try a large number of the possible 2⁵⁶ keys.^4.27 This is a formidable, but not insurmountable, computational effort. A common variation of DES, called Triple-DES, uses three rounds of regular DES with three different keys (so the key length is effectively 168 bits), and is considerably more secure.

DES was originally expected to be used for ``only a few years'' when it was first designed. However, due to its surprising resistance to attack it was generally unassailable for nearly 25 years. The powerful methods of linear and differential cryptanalysis were developed to attack block ciphers like DES.

In the January of 1997, the National Institute for Standards and Technology (NIST) issued a call for a new encryption standard to be developed, called AES (the Advanced Encryption Standard). The requirements were that they operate on 128-bit blocks and support key sizes of 128, 192, and 256 bits. There were five ciphers which advanced to the second round: MARS, RC6, Rijndael, Serpent, and Twofish. All five were stated to have ``adequate security''- Rijndael was adopted as the standard in October of 2000. Rijndael was created by the Belgian cryptographers Joan Daemen and Vincent Rijmen; the underlying mathematics is the algebra of polynomials in the finite field GF(2).

Other commonly used ciphers are IDEA (the International Data Encryption Algorithm, developed at the ETH Zurich in Switzerland), which uses 128-bit keys, and Blowfish (developed by Bruce Schneier), which uses variable length keys of up to 448 bits. Both of these are currently believed to be secure. Another common cipher, RC4 (developed by RSA Data Security) can use variable length keys and, with sufficiently long keys, is believed to be secure. Some versions the Netscape web browser used RC4 with 40 bit keys for secure communications. A single encrypted session was broken in early 1995 in about 8 days using 112 networked computers (see Damien Doligez's web page about cracking SSL for more details); later in the same year a second session was broken in under 32 hours. Given the speed increases in computing since then, it is reasonable to believe that a 40-bit key can be cracked in a few hours. Notice, however, that both of these attacks were essentially brute-force, trying a large fraction of the 2⁴⁰ possible keys. Increasing the key size resolves that problem. Nearly all browsers these days use at least 128-bit keys.

There are, of course, many other ciphers in common use, and more being developed all the time.

Message digests

Related to encryption are message digests, or cryptographic hash functions. A message digest takes an arbitrary length string and computes a number, or hash, from it. Changing the string changes the value of the hash. Hashing functions also play a major role in searching and sorting, and hence in computer databases. While it is obvious that several plaintexts must correspond to the same hash value, it is a difficult problem in general to construct such a plaintext from the value of the hash alone. Thus, one can use a good message digest to authenticate a message-- appending an encrypted version of the hash to an otherwise clear text message can act as a seal, showing that the message was not otherwise tampered with, since it would be infeasably hard to construct a different message with the same hash.

Some commonly used Message digests are MD5 (developed by RSA Data Security), and SHA or SHS (the Secure Hash Algorithm/Standard, developed by the US government).

It is worth remarking here that computer systems can use a cryptographic hash function as a way to store a password (for example, Linux allows the use of MD5 for passwords). A computer password never need be decrypted; it only needs to be verified. Instead of storing the password itself, or an encrypted version of it, the computer stores the corresponding hash. Then, when a user signs in, the password is hashed and compared to the stored value. If they match, the user typed the right password (or managed to find another password with the same hash, which is computationally impossible).

Public Key cryptography

All of the ciphers so far discussed are symmetric encryption routines (also called secret-key or traditional ciphers): if one knows the key used to encode the message, one also can decrypt the message without too much work. For example, in an affine cipher x $\mapsto$ ax + b mod p (see §7), if we know the values of a and b used to encode the message, we can quickly compute the deciphering key 1/a mod p, - b/a mod p. By the same token, the ability to decrypt the message usually also yields the key used for encryption.^4.28

This was true of all cryptosystems up until the mid 1970s: knowledge of how to encode a message allowed one also to decipher it. However, in 1976 Whitfield Diffie and Martin Hellman invented public key cryptography [DH76]. In a public key system, someone who knows how to encipher a message cannot determine how to decipher the message without a prohibitively large computation. That is, given the enciphering transformation f_key : $\cal{P}$ $\mapsto$ $\cal{C}$, discovering f_key^-1 is not computationally realistic. It is important to realize that there may be a procedure for doing so, but to carry out this process would take a prohibitively long time (say, hundreds of years on the fastest known computers). Such a function is sometimes called a one-way function. However, to be usable for public key cryptography, it must be possible to find the inverse of the function provided you have some extra information. This extra information is referred to as a trapdoor (like a trapdoor that a magician would use to escape from a ``sealed'' box), resulting in a trapdoor one-way function.

What good is a public key cryptosystem? Since knowledge of the encoding key K_E does not give information about the decoding key K_D, the encoding key K_E can be made public (hence the name public key). This allows anyone to encode messages that only the recipient can decode. For example, suppose you want to make a credit card purchase over the Internet. Data sent across the Internet unencrypted is not secure: someone with access to the transmission lines can listen in and capture sensitive data.^4.29However, if the merchant provides a public key, you can encrypt your credit card number and transmit it without worry. Only the merchant can decrypt the message, even though anyone may send one.^4.30

Another feature of public key cryptography is authentication. In many public key systems, either the enciphering key K_E or the deciphering key K_D may be made public without revealing the other one. In order to digitally sign a message, I could append my name encrypted with my enciphering key, which I keep secret. I could also make public the deciphering key K_D. Then anyone can check that I was the actual sender, because only I could have encoded my name. Of course, to stop someone from merely appending a valid encrypted signature to a forged message, I should also encrypt something specific to that message, such as a message digest (see §9.2) computed on its contents. This feature is commonly used to digitally sign email by software such as PGP.

Public-key cryptography is very computationally intensive, so typically its use is limited to allow for the secure transmission of a secret key; this secret key is then used to encrypt the rest of the message using a symmetric encryption method such as AES, triple-DES or IDEA.

A common public key system in current use is RSA (named for its inventors: Ronald Rivest, Adi Shamir and Leonard Adelman), which we will look at in detail in §11. Others are the Diffie-Hellman key exchange system, El Gamal, Subset-sum (or Knapsack) systems, and systems based on elliptic curves. We will not discuss these here.

Footnotes

... keys.^4.27

that is, 72,057,594,037,927,936 keys.

... encryption.^4.28

A story related to this appears in Casanova's memoirs (1757) (quoted in [Kahn]). He was given an encrypted manuscript by a Madame d'Urfé, which he deciphered. From deciphering, he determined the key used to encipher the manuscript. Later, upon learning this, Madame d'Urfé was incredulous, believing he must have learned the keyword in order to decode the message.

I then told her the key-word, which belonged to no language, and I saw her surprise. She told me that it was impossible, for she believed herself the only possessor of that word which she kept in her memory and which she had never written down.

I could have told her the truth-- that the same calculation which had served me for deciphering the manuscript had enabled me to learn the word-- but on a caprice it struck me to tell her that a genie had revealed it to me. This false disclosure fettered Madame d'Urfé to me. That day, I became the master of her soul, and I abused my power. Every time I think of it, I am distressed and ashamed, and I do penance now in the obligation under which I place myself of telling the truth in writing my memoirs.

... data.^4.29

This is not as hard as you might expect. In many places, such as universities, portions of the network backbone pass through public places like dormitories or classrooms. One merely needs to attach a computer to the network lines to ``sniff'' the network traffic. This will, of course, be limited to users communicating to or from that location, but that can be quite a lot. This same problem occurs with some cable-modem providers: appropriate software can detect the network traffic of one's neighbors. Also, there are many segments of the Internet which consist of microwave links. To listen in on a huge part of network traffic, all you need is an appropriately placed receiver.

... one.^4.30

Of course, you should still only deal with reputable merchants. You probably wouldn't give your credit card number to a guy selling stuff on the street; neither should you automatically trust anyone with a web site.