Key recovery

A distinguisher is only half the story. Let's go after the key.

Turning distinguishers into keys

Fundamentally, a distinguisher tells us that a cipher exhibits a distinguishable property after $n$ rounds. On its own, this can be useful for e.g. telling apart cipher encryption from random output. More interestingly, this can be used to mount a key recovery attack.

The idea is founded in the fact that the specifics of the distinguisher change from round to round. If we could guess the last round key, we could easily reverse the last round and verify whether the distinguisher holds.

In many ciphers, retrieving a single round key is as good as retrieving the entire key. Intuitively, this makes sense: for an $n$-bit key, we have $n$ bits of entropy in the entire cipher. Were it not so, it would imply the round keys to be quite weak.

Reversing a round

For a cipher with $n$ rounds, the idea is as follows.

• Find a $n-1$ round distinguisher and identify the active bits
• Guess bits of the round key so as to reverse the final round and note the active bits
• If the distinguisher holds with notable probability, the guessed bits are the actual bits

Sometimes, we can recover a good chunk of the round key by doing so, but not enough that a brute force for the remaining bits is feasible. In such cases, we look for a new differential trail, and apply it, slowly recovering the entire key.

TODO: Remote task here. Idea: low rounds with limited queries to force good differentials, repeated round key