[cryptography] How big a speedup through storage?

Jeffrey Goldberg jeffrey at goldmark.org
Fri Jun 20 18:35:29 EDT 2014


On 2014-06-20, at 4:30 PM, grarpamp <grarpamp at gmail.com> wrote:

> On Fri, Jun 20, 2014 at 3:23 PM, Jeffrey Goldberg <jeffrey at goldmark.org>
> wrote:

>> As {Bogdanov, Andrey and Khovratovich, Dmitry and Rechberger, Christian}
>> say in Biclique Cryptanalysis of the Full AES (ASIACRYPT 2011) [PDF at
>> http://research.microsoft.com/en-us/projects/cryptanalysis/aesbc.pdf ]

>> "This approach for 8-round AES-128 yields a key recovery with computational
>> complexity about 2^125.34, data complexity 2^88, memory complexity 2^8, and
>> success probability 1.”

8 rounds, lot more to go.

It looks like I quoted from the wrong part of the paper. Take a look at Table
1. They claim that for 10 round, AES-128, The data is 2^88 (and now that I re-
scanned the paper, these are plaintext-ciphertext pairs, so 32 bytes per pair),
computations are 2^126.18 and memory is 2^8.

It’s not clear to me whether all of those 2^88 plaintext-ciphertext pairs need
to be stored. So this might not actually be a storage issue. Just a boatload
of oracle calls.

(I hope it is clear that I do not think of this as anything like a practical
threat to AES. I had just remembered this paper, with its enormous data
requirements when I saw original question.)

>> Any (reliable) estimates on how big?

> $10M in drives at consumer pricing will get you a raw 177PB, or 236PB at
> double the space and power. Or $1B for 17EB. Budget is an issue.

As always, let’s go with the high estimate in the hands of the attacker. We
are still far far short of the storage requirements for this particular attack
(and all for less than a 2-bit gain).

So I think that it is safe to say that all that data storage is not an attempt
to use the particular attack I cited.

Cheers,

-j



More information about the cryptography mailing list