[RC5] Solutions for a faster DES-II-3

Pete Krawczyk petek at mc.net
Fri Jul 31 14:37:12 EDT 1998

Date: Fri, 31 Jul 1998 10:22:27 -0600
From: gindrup at okway.okstate.edu
Subject: Re: [RC5] Solutions for a faster DES-II-3

}     Clients that do not receive the ciphertext block should perform 
}     *forward* encryptions of the known plaintext with the blocks they 
}     have and return those to a special proxy/server that will compare 
}     the returned blocks with the known ciphertext *and* send the 
}     ciphertext to the reporting client.

There's just one problem with this.

In theory, it's a good idea.  However, in reality, it fails since the
plaintext is first xor'd with an IV before being encrypted.  So you're
doing zero useful work because you don't know the IV.

In order to pre-calculate the possible keys, knowing only the data that
will be originally on the line, you need 2^56 IV's and then 2^56
encryptions on each IV.  This produces 2^112 total calculations that need
to be done.  Then, you need to search through this array first to find
what IV was used, then look though all the encrypted strings to see which
one matches the encrypted string given, then cross-reference with the key.

Yeah, right.

You'd need an absolute minimum 2^112 bits of storage space to keep all
possible IV's and keys corresponding to a given initial 8 characters.
This is 20282409603651670423947251286016 bytes (20.2 nonillion) of
storage.  This would take 2^64 1 TB disks just to store the data.

Not likely.

You can't do it backwards because you don't know the encrypted text and
you don't know what the resultant (text xor IV) is.

Thus, you really can't do anything until you have the data.

-Pete K
Pete Krawczyk  pkrawczy at uiuc dot edu -or- petek at mc dot net
 http://www.uiuc.edu/ph/www/pkrawczy  Finger for PGP public key
If you attempt to mail me at pkrawczy at mc.net, I will not get it.

To unsubscribe, send 'unsubscribe rc5' to majordomo at lists.distributed.net
rc5-digest subscribers replace rc5 with rc5-digest

More information about the rc5 mailing list