[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
http://www.cs.miami.edu/home/burt/learning/Csc609.122/doc/36.pdf

Making a Faster Cryptanalytic Time-Memory Trade-Off.
P. Oechslin.  CRYPTO 2003
http://lasec.epfl.ch/pub/lasec/doc/Oech03.pdf

Understanding brute force.
Daniel J. Bernstein 
http://cr.yp.to/snuffle/bruteforce-20050425.pdf

Greg

-----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?

Cheers,

-j


_______________________________________________
cryptography mailing list
cryptography at randombit.net
http://lists.randombit.net/mailman/listinfo/cryptography


More information about the cryptography mailing list