Saturday, November 1, 2008

Cryptography Operational Protocols and Algorithms

Leaving aside for a moment the issues of protocols and algorithms, the first choices to be made are the cryptographic strength of the system, embodied by choices of algorithm and key length, and some of the key-management questions. It is most important to choose truly random keys that are sufficiently long, keep those keys secret, and change keys "often enough." Again, this all supposes that you have selected a good cryptosystem; all the security of the system lies in the keys, and none in the algorithm itself.

We will consider key randomness and key secrecy shortly. For now, let us consider the selection of key length and the frequency of key updates.

Key Length

Given a reasonably strong algorithm, how well the data is protected depends largely on the length of the encryption key. Fundamentally, an encrypted message must remain secret for the useful life of the information. To a large extent, the value of the information in the encrypted message will govern the resources used to attack it. For example, an attacker would be foolish to spend $1 million to obtain information worth $1,000, but he might spend $1 million to obtain a secret worth $2 million. Here are some examples.

Internet 2010

Today, it is common to use 128-bit keys for symmetric algorithms, both for communications security and for the security of data to be protected for 20 years. The necessary key lengths for public-key algorithms vary considerably. The current recommendation for the RSA public-key algorithm, for example, is to use a minimum length of 1024 bits, with 2048 bits used for especially sensitive applications or longterm keys.

Key Updates

Cryptographic keys do not last forever; they need to be updated from time to time. The proper lifetime of a key is a function of the value of the items encrypted, the number of items encrypted, and the lifetime of the items encrypted. We have already discussed lifetime. If a key can be broken by a properly equipped adversary in 2 years, and the lifetime of information encrypted using the key is 6 months, then the key should be changed at least every 18 months so that an attack mounted on the first item encrypted will not succeed until after the last item encrypted loses its value.

The number of items encrypted is an issue for two reasons. First, if individual encrypted items have a market value, then the sum of the values of all encrypted items is the proper measure against which to balance the resources an attacker may bring to bear. Second, some cryptosystems can be attacked more easily when a large body of ciphertext is available. This effect is more difficult to quantify, but again, it is a good idea not to use a key for too long.

Another factor that leads to frequent key updates is paranoia. The longer a key has been in use, the greater the chance that someone has compromised the key storage system and obtained the key by subterfuge rather than by brute force attack.

It is important to note that changing a key does not increase the time that an attacker will need to find it using brute force or any other method of cryptographic attack. Changing keys does, however, limit the amount of information revealed if any particular key is found. For example, if the encryption keys are changed every month, then only one month's worth of information is disclosed if a key is discovered.

Perfect Cryptosystem One-Time Pads

Is there a perfect cryptosystem? Surprisingly, the answer is yes. It is called the onetime pad. The idea of the one-time pad is to have a completely random key that is the same length as the message. The key is never reused, and only the sender and the receiver have copies. To send, for example, a 100-bit message, the message is exclusiveORed' with 100 bits of the key. That portion of the key is crossed off, never to be used again. The receiver reverses the process, exclusive-ORing the ciphertext with her copy of the key to reveal the message. If the one-time pad key contains truly random bits, this scheme is absolutely secure. The attacker does not know what is on the pad and must guess—but there is no way to know when he is right. By changing the guess, the attacker can decode the ciphertext into any message, be it "attack at dawn" or "negotiate surrender."

Internet 2010

The one-time pad offers perfect security and is indeed used when perfect security is needed, but the system has many disadvantages.

  • The pad must be truly random. Any structure at all can be used to break the system. Creating truly random characters is difficult, and creating a vast quantity of them is more difficult.
  • The pad must never be reused. If a sheet is used twice, then the two sections of ciphertext encrypted using the same page can be compared, possibly revealing both.2 Since the pad is consumed as messages are sent, the pad has to be very long or frequently replaced.
  • The pads must be distributed, stored, and used with absolute secrecy. Because the ciphertext cannot be successfully attacked, the obvious point of attack is to copy or substitute a pad.
  • Every pair of correspondents must have a unique pad, leading to immense practical difficulties of distribution.

These practical difficulties effectively restrict the use of one-time pad systems to situations in which cost is no object. For most other situations, cryptosystems are used in which the length of the key is fixed, and the key can be attacked by exhaustive search.

Internet Blogosphere