Let's talk in more detail about how keys and ciphers work together. Many digital cipher algorithms are called symmetric-key ciphers, because they use the same key value for encoding as they do for decoding (e = d). Let's just call the key k.

In a symmetric key cipher, both a sender and a receiver need to have the same shared secret key, k, to communicate. The sender uses the shared secret key to encrypt the message and sends the resulting ciphertext to the receiver. The receiver takes the ciphertext and applies the decrypting function, along with the same shared secret key, to recover the original plaintext (Screenshot 14-7).

Symmetric-key cryptography algorithms use the same key for encoding and decoding
Symmetric-key cryptography algorithms use the same key for encoding and decoding
(Screenshot 14-7.)

Some popular symmetric-key cipher algorithms are DES, Triple-DES, RC2, and RC4.

Key Length and Enumeration Attacks

It's very important that secret keys stay secret. In most cases, the encoding and decoding algorithms are public knowledge, so the key is the only thing that's secret!

A good cipher algorithm forces the enemy to try every single possible key value in the universe to crack the code. Trying all key values by brute force is called an enumeration attack. If there are only a few possible key values, a bad guy can go through all of them by brute force and eventually crack the code. But if there are a lot of possible key values, it might take the bad guy days, years, or even the lifetime of the universe to go through all the keys, looking for one that breaks the cipher.

The number of possible key values depends on the number of bits in the key and how many of the possible keys are valid. For symmetric-key ciphers, usually all of the key values are valid. An 8-bit key would have only 256 possible keys, a 40-bit key would have 240 possible keys (around one trillion keys), and a 128-bit key would generate around 262,000,000,000,000,000,000,000,000,000,000,000,000 possible keys.

There are ciphers where only some of the key values are valid. For example, in RSA, the best-known asymmetric-key cryptosystem, valid keys must be related to prime numbers in a certain way. Only a small number of the possible key values have this property.

For conventional symmetric-key ciphers, 40-bit keys are considered safe enough for small, noncritical transactions. However, they are breakable by today's high-speed workstations, which can now do billions of calculations per second.

In contrast, 128-bit keys are considered very strong for symmetric-key cryptography. In fact, long keys have such an impact on cryptographic security that the U.S. government has put export controls on cryptographic software that uses long keys, to prevent potentially antagonistic organizations from creating secret codes that the U.S. National Security Agency (NSA) would itself be unable to crack.

Bruce Schneier's excellent book, Applied Cryptography ( John Wiley & Sons), includes a table describing the time it would take to crack a DES cipher by guessing all keys, using 1995 technology and economics. Excerpts of this table are shown in Table 14-1.

Computation speed has increased dramatically since 1995, and cost has been reduced. And the longer it takes you to read this book, the faster they'll become! However, the table still is relatively useful, even if the times are off by a factor of 5, 10, or more.

Table 14-1. Longer keys take more effort to crack (1995 data, from "Applied Cryptography")

Attack cost 40-bit key 56-bit key 64-bit key 80-bit key 128-bit key
$100,000 2 secs 35 hours 1 year 70,000 years 1019 years
$1,000,000 200 msecs 3.5 hours 37 days 7,000 years 1018 years
$10,000,000 20 msecs 21 mins 4 days 700 years 1017 years
$100,000,000 2 msecs 2 mins 9 hours 70 years 1016 years
$1,000,000,000 200 usecs 13 secs 1 hour 7 years 1015 years

Given the speed of 1995 microprocessors, an attacker willing to spend $100,000 in 1995 could break a 40-bit DES code in about 2 seconds. And computers in 2002 already are 20 times faster than they were in 1995. Unless the users change keys frequently, 40-bit keys are not safe against motivated opponents.

The DES standard key size of 56 bits is more secure. In 1995 economics, a $1 million assault still would take several hours to crack the code. But a person with access to supercomputers could crack the code by brute force in a matter of seconds. In contrast, 128-bit DES keys, similar in size to Triple-DES keys, are believed to be effectively unbreakable by anyone, at any cost, using a brute-force attack.

A large key does not mean that the cipher is foolproof, though! There may be an unnoticed flaw in the cipher algorithm or implementation that provides a weakness for an attacker to exploit. It's also possible that the attacker may have some information about how the keys are generated, so that he knows some keys are more likely than others, helping to focus a brute-force attack. Or a user might leave the secret key someplace where an attacker might be able to steal it.

Establishing Shared Keys

One disadvantage of symmetric-key ciphers is that both the sender and receiver have to have a shared secret key before they can talk to each other.

If you wanted to talk securely with Joe's Hardware store, perhaps to order some woodworking tools after watching a home-improvement program on public television, you'd have to establish a private secret key between you and www.joes-hardware.com before you could order anything securely. You'd need a way to generate the secret key and to remember it. Both you and Joe's Hardware, and every other Internet user, would have thousands of keys to generate and remember.

Say that Alice (A), Bob (B), and Chris (C) all wanted to talk to Joe's Hardware ( J). A, B, and C each would need to establish their own secret keys with J. A would need key kAJ, B would need key kBJ, and C would need key kCJ. Every pair of communicating parties needs its own private key. If there are N nodes, and each node has to talk securely with all the other N-1 nodes, there are roughly N2 total secret keys: an administrative nightmare.

 


Hypertext Transfer Protocol (HTTP)