[Cryptography] Dan Bernstein has a new blog entry on key breaking

[Phillip Hallam-Baker]

On Sat, Nov 21, 2015 at 8:23 PM, Christian Huitema <huitema at huitema.net>
wrote:

> On Saturday, November 21, 2015 2:53 PM, Watson Ladd wrote:
> >
> > On Sat, Nov 21, 2015 at 5:23 PM, Phillip Hallam-Baker
> > <phill at hallambaker.com> wrote:
> > ...
> > > OK to explain further. Yes, you have to do 2^128 operations but we are
> > > not doing 2^128 crypto operations, we are just looking for ciphertext
> > > blocks that match our cribs.
> >
> > To compare two lists with 2^64 elements requires only 2^64 operations,
> > not 2^128. Furthermore, using distinguished point methods there are
> > further savings. What DJB points out is that standard methods for
> > reversing some values of a one-way function
> > can be applied to AES(K, 0).
>
> 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?


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.



> Don't modern algorithm use some kind of IV to defeat such attacks?
>
> -- Christian Huitema
>
>
>
>
>
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.

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.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.metzdowd.com/pipermail/cryptography/attachments/20151121/73bcbec9/attachment.html>