|Previous||Table of Contents||Next|
Alice and Bob have a secure communications system. They play mental poker, simultaneously sign contracts, even exchange digital cash. Their protocols are secure. Their algorithms are top-notch. Unfortunately, they buy their keys from Eves Keys-R-Us, whose slogan is You can trust us: Security is the middle name of someone our ex-mother-in-laws travel agent met at the Kwik-E-Mart.
Eve doesnt have to break the algorithms. She doesnt have to rely on subtle flaws in the protocols. She can use their keys to read all of Alices and Bobs message traffic without lifting a cryptanalytic finger.
In the real world, key management is the hardest part of cryptography. Designing secure cryptographic algorithms and protocols isnt easy, but you can rely on a large body of academic research. Keeping the keys secret is much harder.
Cryptanalysts often attack both symmetric and public-key cryptosystems through their key management. Why should Eve bother going through all the trouble of trying to break the cryptographic algorithm if she can recover the key because of sloppy key storage procedures? Why should she spend $10 million building a cryptanalysis machine if she can spend $1000 bribing a clerk? Spending a million dollars to buy a well-placed communications clerk in a diplomatic embassy can be a bargain. The Walkers sold U.S. Navy encryption keys to the Soviets for years. The CIAs director of counterintelligence went for less than $2 million, wife included. Thats far cheaper than building massive cracking machines and hiring brilliant cryptanalysts. Eve can steal the keys. She can arrest or abduct someone who knows the keys. She can seduce someone and get the keys that way. (The Marines who guarded the U.S. Embassy in Moscow were not immune to that attack.) Its a whole lot easier to find flaws in people than it is to find them in cryptosystems.
Alice and Bob must protect their key to the same degree as all the data it encrypts. If a key isnt changed regularly, this can be an enormous amount of data. Unfortunately, many commercial products simply proclaim We use DES and forget about everything else. The results are not very impressive.
For example, the DiskLock program for Macintosh (version 2.1), sold at most software stores, claims the security of DES encryption. It encrypts files using DES. Its implementation of the DES algorithm is correct. However, DiskLock stores the DES key with the encrypted file. If you know where to look for the key, and want to read a file encrypted with DiskLocks DES, recover the key from the encrypted file and then decrypt the file. It doesnt matter that this program uses DES encryptionthe implementation is completely insecure.
Further information on key management can be found in [457,98,1273,1225,775,357]. The following sections discuss some of the issues and solutions.
The security of an algorithm rests in the key. If youre using a cryptographically weak process to generate keys, then your whole system is weak. Eve need not cryptanalyze your encryption algorithm; she can cryptanalyze your key generation algorithm.
DES has a 56-bit key. Implemented properly, any 56-bit string can be the key; there are 256 (1016) possible keys. Norton Discreet for MS-DOS (versions 8.0 and earlier) only allows ASCII keys, forcing the high-order bit of each byte to be zero. The program also converts lowercase letters to uppercase (so the fifth bit of each byte is always the opposite of the sixth bit) and ignores the low-order bit of each byte, resulting in only 240 possible keys. These poor key generation procedures have made its DES ten thousand times easier to break than a proper implementation.
Table 8.1 gives the number of possible keys with various constraints on the input strings. Table 8.2 gives the time required for an exhaustive search through all of those keys, given a million attempts per second. Remember, there is very little time differential between an exhaustive search for 8-byte keys and an exhaustive search of 4-, 5-, 6-, 7-, and 8-byte keys.
All specialized brute-force hardware and parallel implementations will work here. Testing a million keys per second (either with one machine or with multiple machines in parallel), it is feasible to crack lowercase-letter and lowercase-letter-and-number keys up to 8 bytes long, alphanumeric-character keys up to 7 bytes long, printable character and ASCII-character keys up to 6 bytes long, and 8-bit-ASCII-character keys up to 5 bytes long.
Number of Possible Keys of Various Keyspaces
|Lowercase letters (26):||460,000||1.2*107||3.1*108||8.0*109||2.1*1011|
|Lowercase letters and digits (36):||1,700,000||6.0*107||2.2*109||7.8*1010||2.8*1012|
|Alphanumeric characters (62):||1.5*107||9.2*108||5.7*1010||3.5*1012||2.2*1014|
|Printable characters (95):||8.1*107||7.7*109
||ASCII characters (128):
||8-bit ASCII characters (256):
Exhaustive Search of Various Keyspaces (assume one million attempts per second)
|Lowercase letters (26):||.5 seconds||12 seconds||5 minutes||2.2 hours||2.4 days|
|Lowercase letters and digits (36):||1.7 seconds||1 minute||36 minutes||22 hours||33 days|
|Alphanumeric characters (62):||15 seconds||15 minutes||16 hours||41 days||6.9 years|
|Printable characters (95):||1.4 minutes||2.1 hours||8.5 days||2.2 years||210 years|
|ASCII characters (128):||4.5 minutes||9.5 hours||51 days||18 years||2300 years|
|8-bit ASCII characters (256):||1.2 hours||13 days||8.9 years||2300 years||580,000 years|
|Previous||Table of Contents||Next|