8.2. A Very High Security Cryptographic Key

Assume that a very high security key is needed for symmetric encryption/decryption between two parties. Assume also that an adversary can observe communications and knows the algorithm being used. Within the field of random possibilities, the adversary can try key values in hopes of finding the one in use. Assume further that brute force trial of keys is the best the adversary can do.

8.2.1. Effort per Key Trial

How much effort will it take to try each key? For very high-security applications, it is best to assume a low value of effort. Even if it would clearly take tens of thousands of computer cycles or more to try a single key, there may be some pattern that enables huge blocks of key values to be tested with much less effort per key. Thus, it is probably best to assume no more than a couple of hundred cycles per key. (There is no clear lower bound on this, as computers operate in parallel on a number of bits and a poor encryption algorithm could allow many keys or even groups of keys to be tested in parallel. However, we need to assume some value and can hope that a reasonably strong algorithm has been chosen for our hypothetical high-security task.)

If the adversary can command a highly parallel processor or a large network of work stations, 10^11 cycles per second is probably a minimum assumption today. Looking forward a few years, there should be at least an order of magnitude improvement. Thus, it is reasonable to assume that 10^10 keys could be checked per second, or 3.610^12 per hour or 610^14 per week, or 2.4*10^15 per month. This implies a need for a minimum of 63 bits of randomness in keys, to be sure that they cannot be found in a month. Even then it is possible that, a few years from now, a highly determined and resourceful adversary could break the key in 2 weeks; on average, they need try only half the keys.

These questions are considered in detail in "Minimal Key Lengths for Symmetric Ciphers to Provide Adequate Commercial Security: A Report by an Ad Hoc Group of Cryptographers and Computer Scientists" [KeyStudy] that was sponsored by the Business Software Alliance. It concluded that a reasonable key length in 1995 for very high security is in the range of 75 to 90 bits and, since the cost of cryptography does not vary much with the key size, it recommends 90 bits. To update these recommendations, just add 2/3 of a bit per year for Moore's law [MOORE]. This translates to a determination, in the year 2004, a reasonable key length is in the 81- to 96-bit range. In fact, today, it is increasingly common to use keys longer than 96 bits, such as 128-bit (or longer) keys with AES and keys with effective lengths of 112-bits with triple-DES.

8.2.2. Meet-in-the-Middle Attacks

If chosen or known plain text and the resulting encrypted text are available, a "meet-in-the-middle" attack is possible if the structure of the encryption algorithm allows it. (In a known plain text attack, the adversary knows all or part (possibly some standard header or trailer fields) of the messages being encrypted. In a chosen plain text attack, the adversary can force some chosen plain text to be encrypted, possibly by "leaking" an exciting text that is sent by the adversary over an encrypted channel because the text is so interesting.

The following is an oversimplified explanation of the meet-in-the-middle attack: the adversary can half-encrypt the known or chosen plain text with all possible first half-keys, sort the output, and then half-decrypt the encoded text with all the second half-keys. If a match is found, the full key can be assembled from the halves and used to decrypt other parts of the message or other messages. At its best, this type of attack can halve the exponent of the work required by the adversary while adding a very large but roughly constant factor of effort. Thus, if this attack can be mounted, a doubling of the amount of randomness in the very strong key to a minimum of 192 bits (96*2) is required for the year 2004, based on the [KeyStudy] analysis.

This amount of randomness is well beyond the limit of that in the inputs recommended by the US DoD for password generation and could require user-typing timing, hardware random number generation, or other sources of randomness.

The meet-in-the-middle attack assumes that the cryptographic algorithm can be decomposed in this way. Hopefully no modern algorithm has this weakness, but there may be cases where we are not sure of that or even of what algorithm a key will be used with. Even if a basic algorithm is not subject to a meet-in-the-middle attack, an attempt to produce a stronger algorithm by applying the basic algorithm twice (or two different algorithms sequentially) with different keys will gain less added security than would be expected. Such a composite algorithm would be subject to a meet-in-the-middle attack.

Enormous resources may be required to mount a meet-in-the-middle attack, but they are probably within the range of the national security services of a major nation. Essentially all nations spy on other nations' traffic.

8.2.3. Other Considerations

[KeyStudy] also considers the possibilities of special-purpose code-breaking hardware and having an adequate safety margin.

Note that key length calculations such as those above are controversial and depend on various assumptions about the cryptographic algorithms in use. In some cases, a professional with a deep knowledge of algorithm-breaking techniques and of the strength of the algorithm in use could be satisfied with less than half of the 192 bit key size derived above.

For further examples of conservative design principles, see [FERGUSON].