Re: [Cfrg] matching AES security

[Johannes Merkle <[e-mail]>]

Blumenthal, Uri - 0558 - MITLL wrote on 30.07.2014 19:49:
> On 7/30/14 8:33 , "D. J. Bernstein" <[e-mail]> wrote:
>> There are standard attacks that break _all_ of 2^50 AES-128 keys using a
>> _total_ of 2^128 easy computations. Even worse, there are standard
>> attacks that find _at least one_ of the keys using just 2^78 easy
>> computations, a feasible computation today.
> 
> Could you please point me at a decent reference/description of this attack?
> 

The attack is very simple:
- Gather a list of 2^N cipher texts resulting from the _same_ plain text encrypted under 2^N random keys.
- For 2^(128-N) randomly chosen (different) keys, encrypt the known plain text and check if the resulting cipher text
matches one of the gathered cipher texts

Assuming the cipher to be a random permutation, a collision occurs with probability 1 - (1-2^(-N))^N which approximates
1-1/e. If you have sorted the list of gathered cipher texts, the attack takes 2^(128-N)*log(N) steps (and 2^N space).


-- 
Johannes