Re: triple DES with different keys, is it 2E112 or 2E168 to break?

From: Markus Romanoff (romanoff_at_bellsouth.net)
Date: 06/18/04 

Date: Fri, 18 Jun 2004 09:33:24 -0400

Would there be an appreciable increase in security if one were to
create a triple AES (Rijndael)?? or would the same attack scenarios
for triple DES apply?

On Thu, 17 Jun 2004 14:04:54 +0200, Ernst Lippe
<ernstl-at-planet-dot-nl@ignore.this> wrote:

>On Wed, 16 Jun 2004 11:02:50 -0700, Austin Lesea wrote:
>
>> John,
>>
>> Been there, done that. The birthday attack, is the same as the meet in
>> the middle attack (App. Crypt. Schneier, pg 358).
>>
>> "The Meet-in-the-middle attack is a cryptographic attack which makes use
>> of a space-time tradeoff. It is also known as the birthday attack since it
>> exploits the mathematics behind the birthday paradox. Specifically, if a
>> function yields any of n different outputs with equal probability and n is
>> sufficiently large, then after evaluating the function for about ?n
>> different arguments we expect to have found a pair of arguments x1 and x2
>> with f(x1) = f(x2)."
>>
>> from http://www.worldhistory.com/wiki/M/Meet-in-the-middle-attack.htm
>This is not a good explanation of a meet-in-the-middle attack.
>
>> So, if 3DES is not a group, then there is no guarantee that there exists
>> an x1 and x2 such that f(x1)=f(x2) so it is 2E168 (3 times 56 = 168, not
>> 156).
>>
>> So, anyone?
>Just read John's answer very carefully.
>Whether DES or 3DES is a group is completely irrelevant,
>he described how you can crack a 3 key 3DES encrypted message,
>so there always exists three keys that satisfy the requirement.
>
>Ernst Lippe
>
>
>> John Savard wrote:
>>> The reason triple-DES with three different keys is considered to be
>>> 2^112 to break and not 2^168 (2E112 stands for 2*10^112, incidentally)
>>> isn't the birthday attack, but the meet-in-the-middle attack.
>>>
>>> If you had a massive amount of memory, and more than one block of known
>>> plaintext (say 2 blocks), if you decrypt the known ciphertext with each
>>> of the 2^112 possible combinations of the last two keys, and encrypt the
>>> known plaintext with each of the 2^56 possibilities for the first key,
>>> you've done 2*2^56 + 2*2^112 encryptions; this is just a little over
>>> 2^113, and is still well below 2^156.
>>>
>>> The next step is to look for a match between what is enciphered and what
>>> is deciphered.
>>>
>>> John Savard
>>> http://home.ecn.ab.ca/~jsavard/index.html