# What is meant by - computational complexity $2^x$?

Recently Bi-clique Cryptanalysis allowed to obtain following results on full AES ES that claim to have

• The first key recovery attack on the full AES-128 with computational complexity $2^{126.1}$
• The first key recovery attack on the full AES-192 with computational complexity $2^{189.7}$
• The first key recovery attack on the full AES-256 with computational complexity $2^{254.4}$

What is meant by $2^{126.1}, 2^{189.7}, 2^{254.4}, ...$ and if I happen to create a crypto algorithm on my own (which I know is not a good idea) how can I measure it's strength?

• one can recover the AES-128 key by calling AES-128 $2^{126.1}$ times with well-formed input. The complexity (of the algorithm) can be measured as a run-time (what speed do you reach with your implementation), the strength of an algorithm can be measured by the complexity of the best known attack.
– SEJPM
Jun 5 '15 at 11:27
• I quickly edited your question so that exponents actually look like exponents. And as it's about cryptanalytic results I've added the "cryptanalysis" tag. You may want to replace "complexity" in your last sentence with "strength" (see my above comment)
– SEJPM
Jun 5 '15 at 11:31

The "many attacks" you're referring to, don't exist.
There are two main attacks on AES. One needs related keys and drops security level signifantly (to about the half of the bits).
You're referring to the other one, the biclique attack on AES.

This is the first attack on the full-rounded version of AES (without related keys) that performs better than brute-force. It weakens AES, but only by a mere 2 bits, which is negligible for practical applications.

What is meant by $2^{126.1},...$?

These numbers identify the workload the attack requires. You need to perform $2^{126.1}$ "steps" to recover the AES-128 key. One step usually means one call to AES-128. The same applies for the other numbers and AES versions.

EDIT: The following paragraph was obsoleted by an edit to the question. The paragraph after this one now fully applies.

How can I measure it's [my algorithm's] complexity?

First, I think you're using the wrong term. The complexity of an algorithm usually means the run-time the algorithm needs to be performed. (like ~3.5 cycles for AES with AES-NI). The complexity can aswell mean "how complex is it to describe the algorithm", which is usually measured in lines of code.

But from the context you give I assume you mean "How can I measure my algorithm's strength?".
The strength of an algorithm usually is equal to the complexity of the best known attack. So initially this is brute-force making an 128-bit keyed algorithm having a stength of 128-bit or $2^{128}$. Usually attacks sooner or later lower this boundary, whereas usually the impact on homebrew algorithms is rather severe against the moderate advances in the cryptanalysis against AES.