How effective have statistical methods been at breaking encryption?

Question

If we look at how statistical engines run on-line translators, and how they are built, we see that they look at a new language and run a statistical model over it searching for what's probably the correct translation for, lets say, Russian to English.

Granted, encryption isn't exactly a translation (which might be akin to obfuscation) as it is a modeled way to "scramble" data and take the "descramble"-code with it. However, when you look at the ability of these engines to build models for many languages, one could see how each language starts to look like an undiscovered key and cipher to the statistical model.

Are there any known attacks that try to use statistical models in this way to break encryption? Are they effective? What are their short-comings?

Answer 1

Short version:

• Yes, you're describing a known-ciphertext attack or statistical analysis
• They are effective on old or deficient cryptosystems, and can be considered a standard and basic test kit for new cryptosystems
• Their shortcomings are that modern cryptosystems are designed to thwart that particular attack, and the theory and practice of doing so is reasonably well understood at this time

Meandering version:

Language translation is dealing with a one-to-one or one-to-few transliteration, with rearrangements. Each language has a finite dictionary with clear correlations, and each language has rules which define the structure into which words are put. A translation engine relies upon these correlations.

This is totally dissimilar from encryption, where the goal is to mathematically break all such connections between cleartext and ciphertext. What you describe worked well with WWII-era cryptosystems, but not today. To quote Wikipedia (always dangerous, I know) "Every modern cipher attempts to provide protection against ciphertext-only attacks. The vetting process for a new cipher design standard usually takes many years and includes exhaustive testing of large quantities of ciphertext for any statistical departure from random noise.

This is not to say that statistical analysis isn't used, or that it can't succeed. For example, some of the weaknesses in WEP enable statistical attacks to recover the plaintexts. However, when it succeeds it's generally treated as a case where the encryption designer did something stupid rather than a cutting edge attack technique.

Edit - To reinforce that last sentence, let me quote from the conclusions of the WEP paper linked above: "[WEP]'s problems are a result of misunderstanding of some cryptographic primitives and therefore combining them in insecure ways." Heh.

Answer 2

Are there any known attacks that try to use statistical models in this way to break encryption?

Yes. As gowenfawr noted they are typically effective against an older class of encryption algorithms called monoalphabetic substitution ciphers. In these ciphers a letter in the alphabet is exchanged with a symbol. The same letter is always substituted with the same symbol. For example replace every a with i and replace every b with l and so on. This simple substitution preserves the statistical nature of each letter. To attack a monoalphabetic substitution cipher you just need to know the original language used and the statistical frequency of each letter. Find the most common symbol in the cipher text and replace it with the most common letter in the original language. For English the most common letter is e.

The next progression from monoalphabetic substitution is polyaphabetic substitution. This type of cipher uses a table of alphabets to choose a symol to substitute for a plain text letter. This may effectivly blunt a statistical attack (if the key is long enough) by making the substitution a function of the key and the letter instead of just the original letter.

More modern algorithms make the encipherment of each letter a function of many inputs which makes detecting a statistical pattern much harder. One of the input is a key which is usually a piece of random data. Using randomness as an input blunts the ability of a cryptoanalyst to detect a pattern.

However statistical analysis can still play a role in analyzing encrypted data. This usually comes in the form of what is called a side-channel attack. A side channel is a transmission of data that is a side effect of the transmission of the encrypted data. A recent paper "Uncovering Spoken Phrases in Encrypted VoIP Conversations" describe how variable bitrate encoding produced a side channel for the encrypted voice data.

Variable Bit Rate Encoding

When sound is converted into data it becomes bits of information. Not all words and sounds require the same amount of data to represent them. One way of transmitting the voice data is constant bit rate. FThe voice encoder (not encrypter) translates the sounds into data which is then encrypted and transmitted. For constant bit rate every second of sound produces the same amount of data. If the sounds made during that second produces less bits than need to be transmitted then the encoder fills the remaining bits with silence. So, constant bit rate has a lot of meaningless data. Variable bit rate allows the encoder to send as many bits as were generated by the sound by the size of each sample/frame of sounds must be indicated by the data. Some encryption algorithms produce encrypted data that is exactly the same size as the plaintext data. If you use a length preserving encryption algorithm with variable bit rate encoding then an attacker can see the length of each sound sample and sucessive sample lengths and use statistics about the way people talk to pick out a few phrases.

Are they effective? What are their short-comings?

Statistics can be effective in special cases. The sortcoming of statistics is that they tend to be limited to speach and plain text which are a smaller component of communications today then they used to be.