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

[Phillip Hallam-Baker]

On Sat, Nov 21, 2015 at 5:15 PM, Phillip Hallam-Baker
<phill at hallambaker.com> wrote:
> On Sat, Nov 21, 2015 at 10:31 AM, Tamzen Cannoy <tamzen at cannoy.org> wrote:
>> -----BEGIN PGP SIGNED MESSAGE-----
>> Hash: SHA1
>>
>> Break a dozen secret keys, get a million more for free
>>
>> http://blog.cr.yp.to/20151120-batchattacks.html
>>
>> Tamzen
>>
>>
>>
>>
>> -----BEGIN PGP SIGNATURE-----
>> Version: PGP Universal 3.3.0 (Build 9060)
>> Charset: us-ascii
>>
>
> Oh @(@#$@#(*$%!!!!
>
> Its obvious, isn't it. To break AES at 128 bit strength:
>
> 1) compile yourself the biggest rainbow table you can - say 2^64
> plaintext, ciphertext blocks.
>
> 2) Troll through 2^64 blocks of ciphertext, looking to see if anything
> becomes recognizable.
>
> 3) Repeat
>
> Chances are that you will get a match that you can leverage further at
> least 1% of the time.
>
> So anyone using less than AES 256 is making a big mistake. In fact all
> block ciphers are vulnerable to this form of meet in the middle.
>
> @@#(@#*$(*~~~!!!!!
>
> !


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.

What we did to prime the attack is to start by encrypting a set of
chosen plaintexts that we know recur in the messages. Setting up a
finite recognizer to decrypt those messages is then fairly
straightforward.

Yes, you are only going to decrypt a small percentage of the messages.
But that might well be enough.