[cryptography] How big a speedup through storage?

Greg Zaverucha gregz at microsoft.com
Fri Jun 20 15:46:47 EDT 2014

Hi Lodewijk
Here are some relevant references.

A cryptanalytic time-memory trade-off.
ME Hellman - IEEE Transactions on  Information Theory, , 1980

Making a Faster Cryptanalytic Time-Memory Trade-Off.
P. Oechslin.  CRYPTO 2003

Understanding brute force.
Daniel J. Bernstein 


-----Original Message-----
From: cryptography [mailto:cryptography-bounces at randombit.net] On Behalf Of Jeffrey Goldberg
Sent: Friday, June 20, 2014 12:23 PM
To: Lodewijk andré de la porte
Cc: cryptography; Crypto discussion list
Subject: Re: [cryptography] How big a speedup through storage?

On 2014-06-19, at 10:42 PM, Lodewijk andré de la porte <l at odewijk.nl> wrote:

> With common algorithms, how much would a LOT of storage help?

Well, with an unimaginable amount of storage it is possible to shave a few bits off of AES. 

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."

It's that 2^88 that requires a LOT of storage. I'm not sure if that 2^88) is in bits or AES blocks, but let's assume bits. Facebook is said to store about 2^62 bits, so we are looking at something 2^26 times larger than Facebook's data storage.

> I know this one organization that seems to be building an omnious observation storage facility,

Any (reliable) estimates on how big?



cryptography mailing list
cryptography at randombit.net

More information about the cryptography mailing list