Re: MITM attack on 3TDES

["Saqib Ali" <docbook.xml () gmail com>]

Alexander,

Thanks for the response. This is a very good explanation. Another
interesting was posted on USENET by Mark Mark Wooding on sci.crypt.
See below:

---------------
Triple DES involves three keys, K1, K2, K3.  Write
single-DESencryption with a key K and plaintext block x as E(K, x),
and decryption as D(K, x).  Triple DES encryption is E(K3, D(K2,
E(K1,x))).

Suppose you're given a plaintext block x and corresponding ciphertext
y.  For each possible K3, compute D(K3, y), and store the result in a
table.  This takes about 2^56 work, and uses 2^56 blocks of memory.

Now, for each pair K1, K2, compute D(K2, E(K1, x)).  If this matches
one of the values in the table, find the corresponding K3, and test
the whole key against some other plaintext/ciphertext pairs.  Continue
until you're done.  This step takes no extra memory and requires 2^112
time.

On 9/11/06, Alexander Klimov <alserkli () inbox ru> wrote:
> On Wed, 6 Sep 2006, Saqib Ali wrote:
>
> > Can anyone explain how the MITM works on 3TDES (three distinct keys)?
> > I am typically interested in finding out why 3TDES has effective
> > key-length of 112-bit
>
> Get a (plain text, cipher text) pair (m,c) encrypted with some unknown
> key (k1,k2,k3):
>
>  s = E(k1,m)
>  t = E(k2,s)
>  c = E(k3,t)
>
> For all possible (k1,k2) pairs (2^112 possibilities) calculate
>
>  t' = E(k2,E(k1,m))
>
> For all possible k3 (2^56 possibilities) calculate
>
>  t'' = D(k3,c)
>
> Sort the sets of t' and t'' and find (k1,k2) and k3 such that t'=t''
>
> Check each such (k1,k2,k3) with several additional (plain text, cipher
> text) pairs to find the right key.
>
> --
> Regards,
> ASK


--
Saqib Ali, CISSP, ISSAP
Support http://www.capital-punishment.net
-----------
"I fear, if I rebel against my Lord, the retribution of an Awful Day
(The Day of Resurrection)" Al-Quran 6:15
-----------

---------------------------------------------------------------------------
This list is sponsored by: Norwich University

EARN A MASTER OF SCIENCE IN INFORMATION ASSURANCE - ONLINE
The NSA has designated Norwich University a center of Academic Excellence 
in Information Security. Our program offers unparalleled Infosec management 
education and the case study affords you unmatched consulting experience. 
Using interactive e-Learning technology, you can earn this esteemed degree, 
without disrupting your career or home life.

http://www.msia.norwich.edu/secfocus
---------------------------------------------------------------------------