<div dir="ltr"><br><div class="gmail_extra"><br><div class="gmail_quote">On Sat, Nov 21, 2015 at 8:23 PM, Christian Huitema <span dir="ltr"><<a href="mailto:huitema@huitema.net" target="_blank">huitema@huitema.net</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><span class="">On Saturday, November 21, 2015 2:53 PM, Watson Ladd wrote:<br>
><br>
> On Sat, Nov 21, 2015 at 5:23 PM, Phillip Hallam-Baker<br>
> <<a href="mailto:phill@hallambaker.com">phill@hallambaker.com</a>> wrote:<br>
</span>> ...<br>
<span class="">> > OK to explain further. Yes, you have to do 2^128 operations but we are<br>
> > not doing 2^128 crypto operations, we are just looking for ciphertext<br>
> > blocks that match our cribs.<br>
><br>
> To compare two lists with 2^64 elements requires only 2^64 operations,<br>
> not 2^128. Furthermore, using distinguished point methods there are<br>
> further savings. What DJB points out is that standard methods for<br>
> reversing some values of a one-way function<br>
> can be applied to AES(K, 0).<br>
<br>
</span>I get the reasoning, but I am not so sure of the applicability. The attack that DJB explains appears to be a known plain text attack. If I get 2^N targets to encrypt the same known plain text, then I have about 50% chance of finding one match after 2^(128-N) trials. If the plain text is not known, the odds are much worse. But if we admit that this is a known plaintext attack, we get a practicality issue. How often can the attacker predict the plaintext? </blockquote><div><br></div><div>Probably more often than you would want. Known plaintext is fairly rare but very guessable plaintext is much more common and using that only adds a little to the complexity of the attack.</div><div><br></div><div> </div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">Don't modern algorithm use some kind of IV to defeat such attacks?<br>
<span class="HOEnZb"><font color="#888888"><br>
-- Christian Huitema<br>
<br>
<br>
<br><br></font></span></blockquote><div><br></div><div>The point here is that I don't just get the decrypt of one block, I can work out the key used to encrypt that block. And if I know that, I can (usually) work back to figure out what the original key was.</div><div><br></div><div>There are a couple of ways to defeat this type of attack. One would be to effectively randomize the plaintext by pre-encrypting with something like RC4. This would make it much harder to use the 'guessable plaintext' attack.</div></div><br></div></div>