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

[Watson Ladd]

On Sat, Nov 21, 2015 at 5:23 PM, Phillip Hallam-Baker
<phill at hallambaker.com> wrote:
> 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.

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).

>
> 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.
> _______________________________________________
> The cryptography mailing list
> cryptography at metzdowd.com
> http://www.metzdowd.com/mailman/listinfo/cryptography



-- 
"Man is born free, but everywhere he is in chains".
--Rousseau.