Crash course on cryptography: Security aspects of cryptographic systems

Cryptographic systems are quite complex. This makes them vulnerable to a variety of attacks. If an attack succeeds, then Eve may be able to read Alice's and Bob's messages, or even to forge a message in their names.

The most common security problem is keeping the cryptographic keys secure. This is more difficult with secret key cryptography, since there Alice and Bob need to communicate this key to one another. However, even if Alice and Bob are very careful with their keys, the implementation of their cryptographic system may have a bug (or an intentional backdoor) that allows Eve to crack the system.

Keeping the keys secure

The best way to keep the secret key a secret is to never write it down. If Alice and Bob have agreed on a secret key to encrypt their messages, they should memorize the key so that Eve will not be able to find it if she breaks into their houses. Alice might think the risk of burglary is not very big, since she's just encrypting love letters to Bob. But Eve might be Alice's mother or roommate, allowing her to easily read all the yellow notes attached to Alice's computer monitor.

In many systems the secret key is made up on the spot and used only once. It can then safely be thrown away after use. This makes the risk that Eve can steal it much smaller.

Throwing away the key after use is not an option for public key cryptography. To protect Alice's private key, it is often stored encrypted with secret key encryption using a password supplied by Alice. If Eve now steals Alice's hard disk, she cannot use Alice's private key.

However, to decrypt and sign messages Alice's private key needs to be present in the computer's working memory in unencrypted form. At that moment Eve might be able to steal it. For example, she could have installed a program on Alice's computer that makes a copy of her entire working memory whenever Alice's public key encryption program is started. On UNIX-like systems (like Linux) applications that crash generate a copy of the contents of their working memory on the hard disk for debugging purposes (the so-called core dump). If Eve can get a copy of such a core dump, she could analyze it to find the part where Alice's private key resides.

Many operating systems use a so-called swap file in which unused portions of working memory are stored. If such a portion contains a copy of Alice's private key, Eve can recover it by examining the swap file. Programs running on such operating systems therefore should wipe the relevant portions of the working memory as soon as possible. It is sometimes also possible to mark such portions as "do not write to swap file". Alternatively, Alice might erase her swap file when the operating system shuts down. However, if she does this while the operating system is running, her computer will crash.

Smart cards

The secret key is sometimes stored on a secure storage medium such as a smart card. A smart card contains a processor and a memory for storing the secret key. It is programmed to encrypt or decrypt messages using the key stored in the memory. The smart card has an input/output port to communicate with Alice's computer, for example using the USB interface. Because the memory is embedded in the smart card, it is very difficult for Eve to read out or copy the secret key. Breaking open the smart card is usually not possible without destroying it. Activation of the smart card usually requires Alice to enter a personal identification number (PIN) or a password, or maybe to supply her fingerprint or a voice command. This way Eve cannot use the smart card if she steals it.

Smart cards can also be used to protect Alice's private key. The processor is then programmed to decrypt and sign messages using her private key. If Alice wants to read a message from Bob that was encrypted using her public key, her e-mail program transmits the encrypted message to the smart card, which decrypt it and transmits the result back to the e-mail program.

Eve now cannot obtain a copy of Alice's private key. She could however write a program that covertly transmits data to the smart card with the request to decrypt or sign it. For this reason smart cards are usually programmed to only operate after Alice enters a PIN or password, or confirms the operation by e.g. pressing a button on the device holding the smart card.

An additional advantage of using a smart card is that the secret key, or the private key, can be programmed on it beforehand. This way Alice does not have to worry about how to securely generate this key. And in many cases, Trent will not issue a certificate for Alice's public key unless he generated Alice's public and private key himself. This way he can be sure that it's really Alice's key, and that her household does not have a copy.

Key exchange

In some cases, Alice and Bob have separate key pairs for encryption and for digital signatures. Alice then uses the one private key only to decrypt messages, and the other private key only to create digital signatures on messages she sends herself. This allows Alice to protect the two key pairs in different ways. Furthermore she could use different algorithms or key lengths for decryption and for signing.

Implementation issues

Keeping the algorithm or implementation a secret

Some people think that the cryptographic algorithm or its implementation should be kept a secret. This way Eve, who is trying to listen in on Bob and Alice, will not be able to figure out how to decrypt the message. This is not a very good idea. Keeping the key a secret is difficult enough, but also guarding all information regarding the cryptographic algorithm and its implementation is much harder. Furthermore, cryptography is a complex science. Only by thoroughly reviewing the system can you be sure that there are no errors in the algorithm and the implementation.

The most popular cryptographic algorithms are public knowledge (although they may be patented) and anyone can study them to discover weaknesses or to improve them. The same goes for implementations. The most famous encryption program, called Pretty Good Privacy (PGP), has been available on the Internet including source code for more than a decade. No one has been able to find any serious flaws in this program. Some small implementation errors were found by people studying the source code. This has enabled the authors of the program to fix these errors. It is unlikely that they would have found these errors if they kept the source code a secret.

Brute force attacks: trying out all possible keys

Eve can of course try out all possible secret keys until she finds one that gives her a readable message. This is called a brute force attack or an exhaustive key search. The only way to defend against this attack is to make sure that there are so many keys that Eve cannot try them all out in any reasonable amount of time. State of the art cryptographic algorithms use keys that are 16 characters (16 bytes, or 128 bits) long. While this may seem a bit short, 16 characters allow 340,282,366,920,938,463,463,374,607,431,768,211,456 different keys. That's a three with 38 zeros. Given a specially designed chip that can try out one one thousand billion (a one with 12 zeros) keys per second, and given one thousand billion of those chips, Eve needs about 340,282,366,920,938 seconds to try all keys. Since there are about 31 million seconds in a year, this works out to slightly more than ten million years.

Right now making chips that can try out one thousand billion keys per second appears to be utterly out of the question. However, it is impossible to predict what technology might be available in 20 years. In 1977 the U.S. government developed together with IBM the Data Encryption Standard (DES). This secret key encryption algorithm uses a key that is 56 bits, or seven characters long. At the time it was believed that trying out all 72,057,594,037,927,936 possible keys (a seven with 16 zeros) would be impossible because computers could not possibly ever become fast enough. In 1998 the Electronic Frontier Foundation (EFF) built a special-purpose machine that could decrypt a message by trying out all possible keys in less than three days. The machine cost less than $250,000 and searched over 88 billion keys per second.

A difficulty in this type of attack is that computers cannot easily recognize when something is the "real" message. Ways to overcome this problem are to check the result using a dictionary, or to check whether the letter frequencies of the result corresponds to the letter frequencies in English. It could also be that part of the message is known, for example because it begins with today's date and a salutation. In that case, Eve can simply compare all possible outcomes with the known part of the message. If that part occurs in the outcome, then the key was probably correct. This was one of the tricks that helped British cryptographers decrypt messages encrypted using the German Enigma machine.

This system has two important points of failure. If the browser does not generate a good random number, Eve might be able to guess what it is and she can then read all messages. A popular way to make random (or rather: random-looking) numbers is to take the current time expressed in microseconds since January 1st 1970 combined with the process identifier of the Web server or browser. This can be guessed with some effort.

It is also possible to replace the public key of the trusted third party with another public key by overwriting the relevant portions of the browser's files as they are stored on the hard disk of the user.

And the most common way to steal information that has been transmitted using this system is to simply hack the Web server. Many Web applications receive data such as credit card numbers encrypted in this fashion and then store it on their hard disk in plain form. A hacker then merely has to read out the file containing the credit card numbers and does not have to bother with guessing the session key.

All parts