<div dir="ltr"><div class="gmail_extra"><div class="gmail_quote">2014-06-20 21:46 GMT+02:00 Greg Zaverucha <span dir="ltr"><<a href="mailto:gregz@microsoft.com" target="_blank">gregz@microsoft.com</a>></span>:<br><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex">

<div id=":26x" class="" style="overflow:hidden">Hi Lodewijk<br>
Here are some relevant references.<br></div></blockquote><div><br></div><div>Thanks!</div><div> </div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex">

<div id=":26x" class="" style="overflow:hidden">A cryptanalytic time-memory trade-off.<br>
ME Hellman - IEEE Transactions on  Information Theory, , 1980<br>
<a href="http://www.cs.miami.edu/home/burt/learning/Csc609.122/doc/36.pdf" target="_blank">http://www.cs.miami.edu/home/burt/learning/Csc609.122/doc/36.pdf</a></div></blockquote><div><br></div><div>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.</div>

<div><br></div><div>It's also important to remember that whatever tricks will be used they are most likely not public knowledge.</div><div> </div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex">

<div id=":26x" class="" style="overflow:hidden">Making a Faster Cryptanalytic Time-Memory Trade-Off.<br>
P. Oechslin.  CRYPTO 2003<br>
<a href="http://lasec.epfl.ch/pub/lasec/doc/Oech03.pdf" target="_blank">http://lasec.epfl.ch/pub/lasec/doc/Oech03.pdf</a></div></blockquote><div><br></div><div>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.</div>

<div><br>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".</div>

<div> </div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex"><div id=":26x" class="" style="overflow:hidden">

Understanding brute force.<br>
Daniel J. Bernstein<br>
<a href="http://cr.yp.to/snuffle/bruteforce-20050425.pdf" target="_blank">http://cr.yp.to/snuffle/bruteforce-20050425.pdf</a></div></blockquote></div><br></div><div class="gmail_extra">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.</div>

<div class="gmail_extra"><br></div><div class="gmail_extra">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.</div>

<div class="gmail_extra"><br></div><div class="gmail_extra">It also has a more general comment;" “<i>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.” </i>". 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.</div>

<div class="gmail_extra"><br></div><div class="gmail_extra"><br></div><div class="gmail_extra">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.</div>

<div class="gmail_extra"><br></div><div class="gmail_extra">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).</div>

<div class="gmail_extra"><br></div><div class="gmail_extra">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.</div>

<div class="gmail_extra"><br></div><div class="gmail_extra">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.</div>

<div class="gmail_extra"><br></div><div class="gmail_extra">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 their mutations should leave a certain pattern. Etc. etc. I could go on and try to work this out, I don't have time now.</div>

<div class="gmail_extra"><br></div><div class="gmail_extra">Short: There may be patterns between different decodings. There is ways that a parallel computation does not need longer-term memory to store intermediate results, and that could be much faster. There is potentially profit in decoding many messages truly simultaneously. There is less research into parallel algorithms than in sequential algorithms, so we might just not know so well. There may be heuristic manners in intermediate AES decodings that we have not yet found. Etc.</div>

<div class="gmail_extra"><br>I'm more interested in finding out how well it's been thought trough than in rambling about transcendent patterns and wild ideas as I did above. It's interesting to think of how to solve hard problems, but really hard to communicate (that's why papers are so hard to read) and to prove/test (that's why papers need to be so hard to read) a theory. Let alone actually do it! But the agency has a history of doing just that, without anybody outside the agency knowing about it.</div>

<div class="gmail_extra"><br></div><div class="gmail_extra">If indeed the agency would like to spend so much on so complicated a machine then it would prefer to lift part of it's veil then to let speculation run wild. If Area 51 was publicly exposed to be a ridiculously expensive airplane-testing facility then it wouldn't be so interesting, and discussion would be about the price not "alien technology in aircraft". To use an analogy: the trick of good magicians isn't that they hide their movement so well, it's that they divert attention from the movements. If the agency hadn't leaked to use that they want a sort of Tempest (UK program keeping all Internet traffic for 3 days) we would be lyrical and frantic about what's going to happen in that facility.</div>

<div class="gmail_extra"><br>Let's consider something else it might be. Maybe we'll learn something about crypto just trying to see how they'd want to do it!  :)</div></div>