4 ms·
I think this is the essential paragraph: > What the attacker hopes to find inside the AES attack is a key collision. This means that a key guessed by the attac
by agwa 10y ago
I think this is the essential paragraph:
> What the attacker hopes to find inside the AES attack is a key collision. This means that a key guessed by the attack matches a key chosen by a user. Any particular guessed key has chance only 1/2^128 of matching any particular user key, but the attack ends up merging costs across a batch of 2^40 user keys, amplifying the effectiveness of each guess by a factor 2^40
If the attacker has collected 2^40 instances of some known plaintext, such as "GET / HTTP/1.1\r\n", encrypted under 2^40 unknown AES-128 keys (and it doesn't matter how those keys were generated), then the attacker can generate a key randomly, encrypt the known plaintext under that key, and see if it matches any of the target ciphertexts. The chance of guessing one of the 2^40 keys successfully this way is 1/2^(128-40) = 1/2^88. This means that attacking one of the keys requires far less than the 2^128 operations that one might expect would be required to attack AES-128. DJB argues that this makes AES-128 ill-matched with elliptic curves that provide a 128-bit security level, thus motivating a cipher with 256 bit keys instead, such as AES-256 or ChaCha20.
In practice, the first 32 bits of the GCM nonce used by TLS are derived during the handshake, so the attacker has to do 2^32 more computations (since there are 2^32 different ways a known plaintext could be encrypted with a given key). So perhaps AES-128 is actually fine with TLS. But the point still stands that there is a justification for preferring AES-256 over AES-128.
- tptacek 10y agoMy undertstanding is that's the basic, very impractical attack illustration the article opens up with, so that the reader groks how batch attacks work. But most of the article is about the surprising ways in which public key algorithms take that attack into the realm of practicality.
- agwa 10y agoDJB has espoused this point repeatedly - it's more than a motivator for the rest of the article.
- tptacek 10y agoI guess we can agree to disagree about whether this attack is an illustration of how treacherous it is to reason about key sizes or a practical attack on TLS.
- caf 10y agoDJBs point is summarised by the last point from the slides: "Bottom line: 128-bit AES keys are not comparable in security to 255-bit elliptic-curve keys. Is 2²⁵⁵−19 big enough? Yes. Is 128-bit AES safe? Unclear."