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

From: Ernst Lippe (ernstl-at-planet-dot-nl_at_ignore.this)
Date: 06/17/04 

Date: Thu, 17 Jun 2004 14:04:54 +0200

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

Quantcast