Re: [cryptography] How big a speedup through storage?
Date: Sat, 21 Jun 2014 03:10:58 -0400 From: grarpamp grarp...@gmail.com To: Crypto discussion list cryptography@randombit.net Cc: cypherpu...@cpunks.org, cryptography cryptogra...@metzdowd.com Subject: Re: [cryptography] How big a speedup through storage? Message-ID: cad2ti2_dcrqrnp30qjjdoh95zcf2e7qh1nw_lrn9v-0nv5o...@mail.gmail.com Content-Type: text/plain; charset=UTF-8 [...] I meant as answer 'estimates on how big' question. Take what we know about storage, figure in some good efficiencies for the 'storage only' case. And figure what can be bought and operated year on year per foot. You could hide/support $1B + $1B/year but $10B/yr would be hard given entire intel budget is $80B, or $50+B if you drop mil. So... 1) How big can you get within budget? 2) What can you do with it re: a) crypto, or b) otherwise? https://en.wikipedia.org/wiki/United_States_intelligence_budget https://en.wikipedia.org/wiki/United_States_Intelligence_Community http://www.martingrandjean.ch/data-visualization-top-secret-us-intelligence-budget/ In re the Bluffdale facility, it has about 100,000 square feet of actual data warehouse, and is equipped to support a 65 megawatt power demand and uses 1.7 million gallons of water per day for cooling. This gives a baseline for estimating the power density and processing capacity of the largest (known) U.S. TLA data center. An open question: Is all that space for long term storage enabling retroactive surveillance of future enemies of the State, or is some portion of its capacity dedicated to cryptography? http://www.wired.com/2012/03/ff_nsadatacenter/all/1 ___ cryptography mailing list cryptography@randombit.net http://lists.randombit.net/mailman/listinfo/cryptography
Re: [cryptography] How big a speedup through storage?
On Fri, Jun 20, 2014 at 6:35 PM, Jeffrey Goldberg jeff...@goldmark.org wrote: (I hope it is clear that I do not think of this as anything like a practical threat to AES. Of course, 8 rounds at 2^unreachable is not practical. 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. I meant as answer 'estimates on how big' question. Take what we know about storage, figure in some good efficiencies for the 'storage only' case. And figure what can be bought and operated year on year per foot. You could hide/support $1B + $1B/year but $10B/yr would be hard given entire intel budget is $80B, or $50+B if you drop mil. So... 1) How big can you get within budget? 2) What can you do with it re: a) crypto, or b) otherwise? https://en.wikipedia.org/wiki/United_States_intelligence_budget https://en.wikipedia.org/wiki/United_States_Intelligence_Community http://www.martingrandjean.ch/data-visualization-top-secret-us-intelligence-budget/ ___ cryptography mailing list cryptography@randombit.net http://lists.randombit.net/mailman/listinfo/cryptography
Re: [cryptography] How big a speedup through storage?
2014-06-20 21:46 GMT+02:00 Greg Zaverucha gr...@microsoft.com: Hi Lodewijk Here are some relevant references. Thanks! 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 This is pretty basic. It's become common knowledge, apparently a valueable paper then :). This one is a little more archaic than my current timespan allows me to process properly. It's also important to remember that whatever tricks will be used they are most likely not public knowledge. Making a Faster Cryptanalytic Time-Memory Trade-Off. P. Oechslin. CRYPTO 2003 http://lasec.epfl.ch/pub/lasec/doc/Oech03.pdf Ah yes, rainbow tables :) I remember making one for MD5 in school with PHP and MySQL. Worked decently, but not enough storage/preprocessing time to really get further than those available for free online. Good fun though. PHP is very easy to just use. I think mine wasn't as good as it could've been if I'd had proper references. No way to dig it up though. Some funny stuff here too; They present a detailed analysis which is backed up by simulation in a purpose-built FPGA.. What is a purpose-built FPGA? FPGA's are adaptable, that's the whole point! If it were purpose built it'd be an ASIC, and not an FPGA at all. Nice paper, but already more or less common knowledge. Understanding brute force. Daniel J. Bernstein http://cr.yp.to/snuffle/bruteforce-20050425.pdf First line hits home There is a widespread myth that parallelizing a computation cannot improve its price-performance ratio.. The term price-performance is accurate, but price no longer means what it should for the scale of the agency concerned. It's more about humanly possible, I think. It's interesting that the whole paper comes no futher than showing that the myth does not hold true. That's good, but it does not go as far as it could at all. It also has a more general comment; “*But 256-bit AES deliberately uses 14 rounds to keep us secure against non-brute-force attacks!” some people will argue. “There’s an 8-round attack taking time only 2 204 , for example. Okay, okay, that’s on a machine with 2 104 bits of memory, but maybe some additional ideas will produce a 10-round attack more efficient than a 256-bit parallel brute-force key-search attack.” *. It is my understanding that the rounds are required for diffusing the input. Using less rounds than a certain threshold fails to achieve sufficient blending of the input, and creates strong patterns in the output. In other words: it completely breaks diffusion. Therefore the detriment to the security factor of AES is much stronger than is suggested in this alinea, as patterns arise where there previously weren't. The type of attack that I see the most profit in would be one that adopts a variant of a meet in the middle attack. It moves away futher from the centralized point of execution. We have a function family generator F(key, step) that can create a function to be performed on a cyphertext C(step), where key is a random-walk-value used in the attempted decryption and the step is a class. The function will only execute on programs with the right class. F's results are compared to succesfully completed decryptions, possibly seeded with foreknowledge. F is supposed to generate/consist of functions that find patterns or perform mutations. In a serial machine this would be completely unfeasible, not unlike Neural Network simulation is uninteresting. But in this parallel machine transient paths will be untangled by converging on a nearby physical location. IOW: the result of a function generated by F determines the next function to be executed, and the functions are mapped out over the machine. The machine will thus automatically bring similar results closer together which allows for deduplication. If one is able to deduplicate with a known-decypherment then a more serial/central process is supposed to take note of that, and test a key coming forth from that or at least shift the probability of working with a certain class of keys (that share a property extracted by the functions). This is a meet in the middle attack because in the end there will have to be brute forcing, but the intermediate results are an optimization of it. Additionally there will be many middle points floating around the machine at any given point in time. This is not the whole story however. The really interesting trick is that many different cyphertexts will propagate through the machine at the same time. Not only are middlepoints matched within a certain cyphertext, but also across multiple cyphertexts. This could be especially interesting when the key is (partially) shared. The really hard thing is the construction of F. F will have to generate functions with an understanding of how patterns should arise given certain steps, and how they shouldn't. There's an advantage to integrating common plaintexts, as
Re: [cryptography] How big a speedup through storage?
On 2014-06-19, at 10:42 PM, Lodewijk andré de la porte l...@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@randombit.net
http://lists.randombit.net/mailman/listinfo/cryptography
Re: [cryptography] How big a speedup through storage?
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-boun...@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...@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@randombit.net
http://lists.randombit.net/mailman/listinfo/cryptography
___
cryptography mailing list
cryptography@randombit.net
http://lists.randombit.net/mailman/listinfo/cryptography
Re: [cryptography] How big a speedup through storage?
On 2014-06-20, at 4:30 PM, grarpamp grarp...@gmail.com wrote:
On Fri, Jun 20, 2014 at 3:23 PM, Jeffrey Goldberg jeff...@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
___
cryptography mailing list
cryptography@randombit.net
http://lists.randombit.net/mailman/listinfo/cryptography
[cryptography] How big a speedup through storage?
With common algorithms, how much would a LOT of storage help? I know this one organization that seems to be building an omnious observation storage facility, even though omnious observation has very mixed effectiveness (read: not really worth it), and I'm wondering; is the NSA planning on using it to assist breaking the vital data? I'm not sure distributed processing and huge datastorage has been as fully evaluated as computational finding has been. It's conspiracy thinking, of course, but it seems so strange to me that they let us know what they're building the facility for. Maybe it's something stranger? Something they needed a huge cover for? Something they could cover given circumstances? ___ cryptography mailing list cryptography@randombit.net http://lists.randombit.net/mailman/listinfo/cryptography
