2
$\begingroup$

I have been reading about successful attacks on AES and other ciphers. One such mention is here (see excerpt below):

AES was published under the name Rijndael in 1998. Refereed cryptanalytic papers in the next three years culminated in attacks taking time "only" $2^{140}$ to break 7 rounds of 256-bit AES and "only" $2^{204}$ (with a huge amount of memory) to break 8 rounds of 256-bit AES. Subsequent work made very little progress. (Related-key attacks can break more rounds but are not of concern in any properly designed cryptographic protocol.)

I want to know:

  1. If any paper mentions attack as $2^{140}$, how the researchers determine this number of operations?

  2. Are these attacks only on paper or practically proven?

  3. Considering super-computers owned by the government, which researchers don't have access, this figure may vary? Are these attacks taking into account super-computers computing power also?

$\endgroup$
2
  • $\begingroup$ When DJB mentions attacks taking time "only" $2^{140}$ to break 7 rounds of 256-bit AES, I believe he refers to Henri Gilbert & Marine Minier's A Collision Attack on 7 Rounds of Rijndael, in proceedings of AES Candidate Conference , pp. 230-241, 2000. $\endgroup$
    – fgrieu
    Commented Oct 10, 2016 at 15:16
  • $\begingroup$ @fgrieu Thanks for that update. I cited the above attack only as an example. $\endgroup$
    – RPK
    Commented Oct 10, 2016 at 15:18

1 Answer 1

6
$\begingroup$

I'll answer your questions in order:

1. If any paper mentions attack as $2^{140}$, how the researchers determine this number of operations?

By examining the mathematical properties of the algorithm and their attack.

2. Are these attacks only on paper or practically proven?

There is no practical way to perform any operation $2^{140}$ times, so they are only on paper. But note that mathematics is one of the few sciences where we can prove things without resorting to experimentation.

3. Considering super-computers owned by the government, which researchers don't have access, this time-frame may vary? Are these attacks taking into account super-computers computing power also?

$2^{140}$ is the number of elementary operations, usually 1 operation takes a constant amount of operations of the underlying primitive, e.g. 1 AES encryption/decryption operation. The number of operations required does not depend on computer speed.

But yes, faster computers will perform the operations faster. This is however of little importance as $2^{140}$ operations together take multiple universes of time and energy to complete. Only very disruptive technology such as quantum computing or breakthroughs in mathematics could make such attacks practical.

There is always the possibility that the attack itself can be improved upon. Attacks get better, never worse.


The results on 256 bit AES with relayed keys are mainly of importance when the block cipher is used within other constructions such as pseudo random number generators. AES encryption is still considered secure.

$\endgroup$
7
  • $\begingroup$ Edited OP. Changed time-frame to operations. $\endgroup$
    – RPK
    Commented Oct 10, 2016 at 15:08
  • $\begingroup$ Added " The number of operations required does not depend on computer speed." to the answer as reaction on the edit. $\endgroup$
    – Maarten Bodewes
    Commented Oct 10, 2016 at 16:27
  • $\begingroup$ After reading this I am a bit worried on any claim that AES is secure: propublica.org/article/… $\endgroup$
    – RPK
    Commented Oct 10, 2016 at 16:47
  • 1
    $\begingroup$ Why? The Snowden documents show a lot of clandestine operations by the security services of the USA. But it doesn't seem to show any unknown cryptographic analyses of standardized ciphers - at least to my knowledge. I'm pretty sure Bruce would have something to say on that if that was the case. $\endgroup$
    – Maarten Bodewes
    Commented Oct 10, 2016 at 17:37
  • 2
    $\begingroup$ In addition to the answers, it is important to stress that even if 7-round AES would be considered insecure (and $2^{140}$ isn't), on its own that would not matter. AES 256 has 14 rounds. Attacks on reduced round versions are not attacks on the system itself, they are more indicators to what kind of attack might work. $\endgroup$
    – tylo
    Commented Oct 11, 2016 at 10:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.