Cryptanalysis

Cryptanalysis is the subfield of cryptology concerned with how to "break" cryptosystems. Usually this means breaking a code or cipher in such a way that you can decrypt arbitrary messages that you intercept.

Cryptanalysis is in essence the study of extracting information about something unknown. In the traditional sense, this means extracting the message from the ciphertext without knowing the key. However the term cryptanalysis applies equally well to deciphering an ancient codex written in a long-dead language.

The important part about cryptanalysis is the analysis. A cryptanalyst deems it a success if they can extract even partial inforation from a ciphertext. For example, knowing when the same encrypted message is sent twice can be helpful. If your enemy mounted a major attack after receiving the message 1 20 20 1 3 11, you definitely want to know when that same message is transmitted again!

The fact is, modern cryptanalysis almost never fully breaks a cipher! Cryptographers these days are that good.

David Kahn's masterpiece The Codebreakers is universally acknowledged as the definitive history of cryptanalysis. It is a fascinating read and covers topics such as the Navajo code talkers of World War 2.

Cryptanalytical techniques are often called attacks, which gives rise to the picturesque jargon surrounding this otherwise rather
technical and complicated branch of mathematics:

• known (chosen) plaintext attack
• known (chosen) ciphertext attack
• adaptively chosen plaintext attack
• etc...

And speaking of picturesque, let's not forget that cryptanalysis is often termed a black hat activity...except when our side is doing it,
in which case it becomes white hat. For instance the cryptanalysis of the Enigma coding machine carried out by Alan Turing and
others during World War II was undoubtedly white hat...
(And if you're asking yourself: "Enigma, isn't it the machine that valiant american sailors captured on a Nazi submarine?" the answer
is: "No". That was a Hollywood movie, and a historical lie. The Brits made almost all of it by themselves. Sorry, folks.)

As previously noted, cryptanalysis is all about the methods for breaking cryptosystems. Of course, since modern cryptography uses much mathematics that is not particularly well understood yet, the rules for what it means for a cryptanalytic attack to be successful are relaxed a fair bit. In academic cryptography, a successful attack doesn't necessary mean that it is a practical method of recovering the plaintext or the secret key from the ciphertext. To be considered successful, it is merely necessary for an attack to find a weakness in the structure of the cipher that can be exploited to attack the cipher with effort less than brute force. Never mind if a brute force attack would require 2²⁵⁶ (10⁷⁷) encryptions; if an attack requiring 2²²⁴ (10⁶⁴) encryptions is found it would be considered a "successful" attack, as it shows that the cipher does not work exactly as advertised. Of course, both types of attacks are equally infeasible even if every sub-atomic particle making up the entire Virgo supercluster of galaxies were a computer capable of doing a billion encryptions a second.

Other types of cryptanalytic attacks, specifically on iterated block ciphers, attack reduced-round variants of the cipher, e.g. Counterpane published a successful break of six rounds of Rijndael, while that algorithm recommends at least ten rounds of the cipher. Again, it shows that there might be a structural weakness in the mathematics of the cipher that can be exploited. Such attacks may later be extended to the full cipher. Other cryptanalytic results require unrealistic amounts of known or chosen plaintext: the linear cryptanalysis method against DES requires 2⁴⁷ known plaintexts to recover the key for instance (gee, that's 2048 terabytes of known plaintext!).

These types of attacks, however, could conceivably be extended into actual, practical attacks that can decipher arbitrary ciphertext using only realistic resources if gaps in mathematical knowledge can be filled (or perhaps given something already known to the National Security Agency)...

Modern and (practical) cryptanalysis also involves such diverse techniques which might once have been considered "cheating" by cryptanalysts of old, such as side-channel attacks that take advantage of weaknesses in the physical impelementation of a cryptosystem, perhaps even rubber-hose cryptanalysis :).

Sources:

Mitsuru Matsui, "Linear Cryptanalysis Method for the DES Cipher", EUROCRYPT '93.

Bruce Schneier, "A Self-Study Course in Block Cipher Cryptanalysis", http://www.counterpane.com/self-study.html

Bruce Schneier, Applied Cryptography

N. Ferguson, J. Kelsey, S. Lucks, B. Schneier, M. Stay, D. Wagner, and D. Whiting, "Improved Cryptanalysis of Rijndael", http://www.counterpane.com/rijndael.html