# How to be sure to retrieve the good key when brute-forcing a cipher?

Imagine the case of the one-time pad. It is proved to be secure because the key could be everything. We have no guarantee that this key or that key was the one used while encrypting our data. Wikipedia says: "a ciphertext can be translated into any plaintext of the same length, and all are equally likely.".

What about block ciphers like AES, Serpent, Twofish and the others ?

Imagine we found a ciphertext like this: 0102030405060708090A0B0C0D0E0F10 and we know that this ciphertext comes from an AES-128 encryption. Then, we want to force-brute it, force the cipher to reveal itself.

Let's suppose that with the key 10F0E0D0C0B0A0908070605040302010, the decryption gives us as output: "This is secret !" and with the key 102030405060708090A0B0C0D0E0F010, the decryption yields "15zefD1p1wA2kvCC".

The plaintext was "This is secret !" or "15zefD1p1wA2kvCC". How could we know ? And what I mean is that even if a decryption leads to gobbledygook, what tells us that the plaintext wasn't gobbledygook itself ?

How can we be sure that key we've just tried while brute-forcing the cipher is the good one ? Why is there AN ONY key possible and not an infinity like with the one-time pad ?

• To put it bluntly, nobody cares about this sort of attack anymore. – fkraiem May 30 '18 at 12:25
• Sure but that's the same problem with other types of attack right ? – Tom Clabault May 30 '18 at 12:29
• Anything wrong with the classic: verify some characteristic of real plaintext, such as having all high-order bit of bytes clear (ASCII); failing with high confidence a chi-squared test of equidistribution of bytes; being compressible by gzip? – fgrieu May 30 '18 at 13:54

From the defender's perspective, we accept a cipher as secure if the best known adversary at a game called IND-CCA2 has negligible probability of success even if the adversary can choose what structure to exploit.

Here's the IND-CCA2 game, short for indistinguishability under adaptive chosen-ciphertext attack:

1. The adversary queries an oracle to learn the decryption of arbitrary ciphertexts of their choosing. The ciphertexts they choose may depend on earlier plaintexts they received.

2. The adversary submits to the challenger two messages $m_0 \ne m_1$ with any relations they want as long as the messages are not equal and not already obtained from the decryption oracle, and learns the encryption $c$ of $m_i$ where $i \in \{0,1\}$ is the outcome of a fair coin toss that the challenger keeps secret from the adversary.

3. The adversary queries an oracle to learn the decryption of arbitrary additional ciphertexts of their choosing, except for $c$.

4. The adversary makes a guess for $i$, the outcome of the coin toss, and wins if their guess is correct.

If all cost-limited adversaries have negligible chance of winning this game, then it doesn't matter what structured data the defender puts in their messages. If there were any structure that an adversary could exploit, such as US-ASCII text, then that adversary could exploit that to win the game with nonnegligible probability, and the cipher would fail to have IND-CCA2 security.

From the attacker's perspective trying to (say) recover a key, we have to exploit additional information about the plaintexts to verify a guess. If the defender encrypted a uniform random string of 128 bits $P$ and revealed $C = \operatorname{AES-256}_k(P)$ to the attacker, the attacker has no way to distinguish $k$ from $k' \ne k$ because every ciphertext is the encryption of some plaintext. But if the distribution might have been nonuniform and its nonuniformities are predictable, e.g. if the defender encrypted US-ASCII text or an XML document or what-have-you, then the attacker can exploit that information.

Often, many of these nonuniform distributions on messages will lead to a nonuniform distribution on (say) octets, which we can trivially distinguish with an undergraduate statistician's favorite (or only) tool: a $\chi^2$ test against the null hypothesis of a uniform distribution on octets. There are many other statistical tests that might have power to distinguish the random noise produced by the wrong key from the defender's plaintexts produced by the right key.

Nothing in general can be said in cryptography, though, because we design ciphers so that it doesn't matter what distribution the defender uses; the attacker still has no hope of distinguishing ciphertexts for different plaintexts even if they can choose the plaintexts to maximize their chances of winning.

In Classical terms you are asking for the Unicity Distance of the system: how much plaintext must be recovered to be certain we have found the right key. As Squeamish Ossifrage notes, this depends on your ability to distinguish plaintext, which ultimately comes down to (what I'll call) "semantic redundancy".

In any event, with modern block ciphers the Unicity Distance is effectively one block.