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?

| improve this question | |
$\endgroup$
  • $\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♦ Oct 10 '16 at 15:16
  • $\begingroup$ @fgrieu Thanks for that update. I cited the above attack only as an example. $\endgroup$ – RPK Oct 10 '16 at 15:18
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.

| improve this answer | |
$\endgroup$
  • $\begingroup$ Edited OP. Changed time-frame to operations. $\endgroup$ – RPK Oct 10 '16 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♦ Oct 10 '16 at 16:27
  • $\begingroup$ After reading this I am a bit worried on any claim that AES is secure: propublica.org/article/… $\endgroup$ – RPK Oct 10 '16 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♦ Oct 10 '16 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 Oct 11 '16 at 10:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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