[cryptography] How big a speedup through storage?

Jeffrey Goldberg jeffrey at goldmark.org
Fri Jun 20 15:23:01 EDT 2014


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




More information about the cryptography mailing list