The abstract of the Biclique Attack paper claims:
The first key recovery attack on the full AES-128 with computational complexity $2^{126.1}$.
What does $2^{126.1}$ mean in this context? And where does this value come from?
$\begingroup$
$\endgroup$
5
-
$\begingroup$ Do you want to know what $2^{126.1}$ means, or what the significance of this attack is? $\endgroup$– Paŭlo EbermannApr 29, 2012 at 16:10
-
$\begingroup$ the meaning of $2^{126.1}$.. it will be good if you will add to your answer the significance of the attack for additional information. :) $\endgroup$– goldrogerApr 29, 2012 at 16:15
-
2$\begingroup$ I looks like you need some mathematical background reading: en.wikipedia.org/wiki/Exponentiation (especially part 3, rational exponents). $\endgroup$– Paŭlo EbermannApr 29, 2012 at 16:18
-
$\begingroup$ I know the base and the exponent, but where 2 and 126.1 came from... $\endgroup$– goldrogerApr 29, 2012 at 16:22
-
2$\begingroup$ It looks like you'll have to read the paper here to know the details. It is just an attack which takes a bit less work than the full $2^{127}$ test encryptions/decryptions of a brute force attack. $\endgroup$– Paŭlo EbermannApr 29, 2012 at 17:01
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
The usual convention on attack cost is the following: "the cost is N" means that running the attack, with a success probability of at least 50%, requires no more than:
- N bits of memory space (RAM),
- N plaintext/ciphertext pairs,
- N*x clock cycles, where x is the number of clock cycles to compute one instance of the attacked algorithm (in the case of AES, "one instance" is encrypting one block).
The generic exhaustive key search (aka "brute force") on AES-128 has cost 2127, and that's entirely CPU cost (when trying many keys, you do not need much RAM, and one plaintext/ciphertext pair is sufficient). The cost is 2127 because trying out half of the possible keys is enough to make the success probability exceed 50%. Correspondingly, no attack can be deemed "real", in an academic way, unless it does better than that.
The biclique attack pretends to do better, with a cost of 2125.1, which is about 73% less than 2127 (if you prefer, the biclique attack is about 3.7 times more efficient than exhaustive key search). But note that nobody is talking about actually running it ! This kind of comparison is mostly formal, which is why we allow ourselves to consider that having N bits of RAM, obtaining N plaintext/ciphertext pairs, and computing N times the block encryption, have the same cost. This does not make practical sense.
(Note: in a previous version of this answer, I had used 2126.1, which is the figure with the article, but Christian Rechberger pointed out to me that it was computed for 100% success rate, and it scales like brute force. For 50% success rate, the complexity is 2125.1.)
For instance, buy a simple PC, and you'll be able to compute 248 AES encryptions per week, but 248 bits is 32 terabytes: that could prove a bit expensive. And convincing your target to encrypt 4096 terabytes worth of data might be somewhat challenging. That's comparing apples with oranges, and also with pickled herrings. Academics can get away with it because they are playing a game which has only indirect links with reality. It is about computing a lower bound for security.
When security is down to the realm of the potentially feasible, the proper measure is not the number of encryption or the RAM size, but the dollar.
Also, note that the biclique attack lowers security by less than two bits. This means that learning two bits of the key (by some leak) actually gives the attacker a bigger advantage than the biclique attack. This is why this attack is not scary. It is academically interesting, but not a danger in any way.
answered Oct 14, 2012 at 16:09