[1125] in cryptography@c2.net mail archive
Re: cracking n-DES?
daemon@ATHENA.MIT.EDU (Bill Stewart)
Sun Jun 29 18:09:44 1997
Date: Sun, 29 Jun 1997 01:05:23 -0700
To: David Wagner <daw@cs.berkeley.edu>
From: Bill Stewart <stewarts@ix.netcom.com>
Cc: cryptography@c2.net, cme@cybercash.com
In-Reply-To: <199706280821.BAA00727@joseph.cs.berkeley.edu>
des | trans | des | trans | des
At 01:21 AM 6/28/97 -0700, David Wagner wrote:
>You exploit a lack of diffusion. You put in a one-byte difference
>in the plaintext (say). Each ECB-DES layer can only increase the
>number of bytes that differ by a factor of 8 (and then the trans
>re-shuffles them around). After two des|trans passes, you've only
>got 8^2 = 64 bytes differing, out of a total of 8192 bytes per "trans
>permutation block" -- that's very minimal avalanche.
Perhaps I'm mis-remembering trans, but if it doesn't work
the way I think it does, it could :-), and it's much stronger.
Let Permute(String, Key) be a permutation on String, pseudo-randomly
driven by Key, where typically Key = Hash(String),
and String is large, e.g. 1KB or 8KB.
Let Hash(String) be a hash function invariant over Permute, i.e.
Hash(String) == Hash(Permute(String, Key)) for any value of Key.
For example, Permute could shuffle the String around in 16-bit blocks,
and Hash could be the XOR of all 16-bit subblocks in the String.
Then, changing one byte of String changes 8 bits of Key, which
may change as many as all the bytes of Permute(String,Hash(String)).
If any 64-bit block of four 16-bit blocks has a different member than before,
the 64-bit output of DES on that block should be totally different -
and most blocks will have had at least one 16-bit change,
so you should have a near-total avalanche after one round of trans|des.
Here's pseudo-code for a potential Permute:
Let PRNG(x) : 1..4096 -> 1..4096 be a boring linear congruential generator.
Let String be 8192 bytes long.
Hash(String) { byte a, b; int i;
for (i=0; i<8191; i+=2) { a ^= String[i]; b^= String[i+1]; }
return (a*256+b);
}
Permute(String, Key) { // Permute String in place
int i, x;
x = Key % 4096;
for (i=0 ; i<8191; i+=2) {
swap( String[i], String[2*x] );
swap( String[i+1], String[2*x+1] );
x = PRNG(x);
}
}
# Thanks; Bill
# Bill Stewart, +1-415-442-2215 stewarts@ix.netcom.com
# You can get PGP outside the US at ftp.ox.ac.uk/pub/crypto/pgp
# (If this is a mailing list or news, please Cc: me on replies. Thanks.)
