Given the impossibility of finding keys in this lifetime, we need to look at other methods an attacker might use to discern plaintext from ciphertext. These techniques include the use of mathematical tools and techniques, as well as plain old analytical reasoning, patience, and determination. Some techniques may never be known (that is, the U.S. Government has still not declassified cryptanalysis techniques used to break codes during World War II).

The security community refers to the different types of attacks as follows:

•  Ciphertext Only. The cryptanalyst has a copy of the ciphertext and a copy of the algorithm. In this case, the cryptanalyst will most likely be unable to decipher the text for the reasons just described.

•  Known plaintext. The cryptanalyst has a copy of the ciphertext, a copy of the algorithm, as well as some plaintext messages and the ciphertext of those messages. In this case, the cryptanalyst can evaluate the original plaintext, the algorithm, and the resulting ciphertext. In another scenario, the cryptanalyst already knows some text patterns in the ciphertext and can analyze the ciphertext knowing that those patterns exist in it.

•  Chosen plaintext. The cryptanalyst is able through some means to get a message inserted into the plaintext before it is converted to ciphertext. The cryptanalyst can then work at finding a key to decrypt the ciphertext. In some cases, the information inserted into the plaintext can provide a pattern that helps reveal the key more easily.

•  Adaptive chosen plaintext. The cryptanalyst uses a relatively new technique called differential cryptanalysis, which is an interactive and iterative process that works through many rounds using the results of previous rounds until the key is identified. Basically, the cryptanalyst analyzes the “evolution of the differences between two related plaintexts as they are encrypted under the same key,” according to RSA Laboratories.

The best examples of known plaintext are files created by various word processors that contain hidden formatting codes and file header information. Documents also contain company names and addresses, copyright notices, form field names, and other information that a cryptanalyst can probably obtain with ease. In fact, many documents used in electronic commerce (i.e., fund transfers) have standard header information that is used to identify the document to other computers. The cryptanalyst may be able to discover a key by analyzing how the algorithm converts the known plaintext.

Here are some of the techniques that have been used by cryptanalyst to attack ciphertext:

•  Differential cryptanalysis. As mentioned previously, this technique uses an iterative process to evaluate cipher that has been generated using an iterative block algorithm (such as DES). Related plaintext is encrypted under the same key. The difference is analyzed and probably keys are identified through numerous iterations. This technique was used successfully against DES, FEAL-4, and some hash functions.

•  Linear cryptanalysis. This technique was also used successfully against DES and FEAL-4. Pairs of plaintext and resulting ciphertext are analyzed and a linear approximation technique is used to determine the behavior of the block cipher.

•  Algebraic attacks. This technique exploits mathematical structure in block ciphers. If the structure exists, a single encryption with one key might produce the same results as a double encryption with two different keys. The cryptanalyst will take advantage of this weakness.

In general, the cryptanalyst needs time and resources. As computers become more powerful, will they have more resources at hand? That is unlikely since the algorithm and encryption techniques will also benefit from technology improvements. Also as mentioned, every bit added to the key size on the encryption side doubles the work required by the cryptanalyst to break ciphertext.

Although attacks on DES have been successfully mounted, the attacks are not easy or cheap. The fastest method has been a brute force attack that took 3.5 hours on a million dollar computer. Differential cryptanalysis was used in one attack in which 247 encryptions were performed on chosen plaintext, but the attack was so difficult that it is not considered practical. In another attack, linear cryptanalysis was used to recover a DES key in 50 days using 12 computer workstations. Refer to the aforementioned RSA Laboratories paper for more details.

The RSA public key system involves a mathematical method for creating separate but linked public and private keys as discussed previously under “Asymmetric (Public-Key) Cryptography.” Two large prime numbers are multiplied together to produce a product called the modulus. Further calculations from this produce the public and private key.

An attacker will attempt to factor the modulus to restore the original prime number. Factoring is a calculation that splits an integer into smaller integers that can be multiplied together to obtain the original integer. Because RSA uses prime numbers, prime factorization is necessary, meaning that the integer must be split into prime numbers, something that is very difficult.

If factoring is successful, the attacker can obtain the private key, and once that happens, the game is over for the owner of the key. The attacker can decrypt captured messages and forge signatures.

RSA Laboratories notes that hardware improvements will not weaken RSA but increase its security. While an attacker will get a better chance at factoring numbers that are a few bits longer, the user can simply choose new keys that are dozens of digits longer without loosing performance (that is, multiplying is easy, factoring is difficult). RSA recommends using large key sizes to protect against attackers in the future who run very fast computers.

Especially curious readers who want to explore all of these techniques further can check out the web sites listed in the next section.