SWAT MAGAZINE ISSUE EIGHTEEN: JUNE 1999 ============================================ THE CODE BREAKERS ============================================ Author : Netw0rk Bug E-Mail : bug@netw0rk.freeserve.co.uk Date : JUNE 1999 ============================================ Cryptographers have been writing codes for over 2,000 years, cryptanalysts have been trying to crack those codes for just as long. They have almost always succeeded. Although code-cracking has slightly sinister overtones, it is, in fact, a quite honorable profession and one that is necessary to provide a high level of confidence for any encryption algorithm. The strength of an encryption algorithm is measured in large part by the number and reputation of the cryptanalysts who have had a go at it and failed. While the NSA insists on keeping secret the algorithms it has designed, including parts of the DES and, most recently, SKIPJACK, cryptographers outside the NSA seem to feel you can maintain the strength of a good algorithm without secrecy, as long as you have good strong secret keys. "You can send it to your adversaries, publish it in magazines, or shout it from the rooftops," says Bruce Schneier. "It doesn't matter; even the designer of the algorithm can't decrypt messages without the key." Using Brute Force. Code-breakers, or cryptanalysts, want to recover the plaintext of a message without using the key. They may first try to recover the key, or they may go after the message itself. One common cryptanalytic technique is known as the brute force attack or an exhaustive search, where the goal is to guess the key by trying every possible combination. The success of brute force attack depends in large part on hardware. Faster processors mean testing more keys per second. Michael Weiner's proposed brute force attack on the DES using a specially designed computer has many cryptographers sounding the old standard's death knell. Also, the recent cracking of RSA-129 indicates that the combination of advanced factoring techniques and faster computers is making that algorithm look weaker than ever. The NSA, with more computing power than any entity on the planet, is the essence of brute force. Frequency Analysis Brute force is not always the most appropriate method for attacking a cipher. In very simple codes, a frequency analysis of the letters may be possible. Since the letter "e" appears most frequently in the English language and "k" appears most often in the ciphertext, a reasonable guess is k = e, and so on. Encrypted source code is particularly vulnerable to cracking because certain words, such as "#define," "struct," "else," and "return" appear regularly. Frequency analysis was first perfected by the Papal courts of the Middle Ages, which developed frequency tables for Latin and Italian. Serious cryptosystems preclude such easy solutions, however, and demand far more sophisticated cryptanalytic attacks. Trickery and Deceit While they always need a high level of mathematical and cryptographic skills, trickery and deceit have a long history in code-breaking as well. For example, if you know at least some of the content of the message, it's relatively easy to decrypt the entire message. Thus, a snoop could trick or bribe someone to encrypt and send a known message, which, when intercepted, could then be easily decrypted using standard cryptanalysis techniques. "If the time and money required to break an algorithm is more than the value of the encrypted data, then it's probably safe," says Schneier. Computers are becoming faster and cheaper while the value of data decreases over time. "It is important that these two lines never cross," he adds. The One-Time Pad It is said that given enough time and computer resources, any cipher can be broken. The only exception to this, a cipher called a one-time pad, is thought to be unbreakable, even with infinite resources. A one-time pad consists largely of a a nonrepeating set of truly random key letters or numbers. These are written on small sheets of paper and glued together in a pad. Bob uses each key letter on the pad to encrypt only one plaintext character, and Alice uses an identical pad to decrypt each letter of the ciphertext. Once a letter is used, it is torn off the pad and discarded in a secure manner. Hence, the name. The major drawback of one-time pads is their bulk. The key is always the same length as the message, making it all but impossible encrypt and send large messages. One-time pads were commonly used by Soviet spies during the Cold War. The agent would take one pad with him into the field, leaving an identical pad back at headquarters. The most famous use of a one-time pad is rumored to have been for encrypting communications on the Washington-Moscow hotline beginning in the early 1960s.