From: Karl Lui Barrus <klbarrus@owlnet.rice.edu>
Date: Wed, 13 Oct 93 20:19:59 PDT
To: cypherpunks@toad.com
Subject: DES: breaking, attacking
Message-ID: <9310140317.AA06605@flammulated.owlnet.rice.edu>
MIME-Version: 1.0
Content-Type: text/plain


-----BEGIN PGP SIGNED MESSAGE-----

On the method Douglad Holland posted about breaking the DES... an
interesting property of DES is that of complimentation.  That is, if
encryption of plaintext P under key K produces ciphertext T, then
encryption of plaintext P' under key K' produces ciphertext T', where
the primes (') mean bitwise complement.

If:       T  = DES(P ,K)
then      T' = DES(P', K')

Cryptanalysis can exploit this if two pairs are available such that 
T' = T or P' = P.

What this boils down to is a 50% reduction in work.  So now instead of
taking 10 billion years it'll just take you 5 billion :-) Complexity
wise, it's just 2^55 steps instead of 2^56, so it may not buy you too
much.

A more interesting attack I read of is a probabilistic attack against
DES.  Suppose you encrypt sensitive data, and change keys once a
month.  I can attack you by trying as many decryptions as possible
within the month.  Sure, I am not guarenteed success, but the point is
that if I do this month after month, I have a decent chance of success
at some point during the year.  And if the information you encrypt is
valuable, once success during the year is all I'll need.

An upcoming book on cryptanalysis details this attack; the author
calculates success rates given various estimates for hardware (speed
and number) and frequency of key shifting.  It is quite arresting:
even if you change keys every week, if I can muster enough computer
power to give me a 1% chance of success, the chances are "good" that
at some time during the year I'll succeed in decrypting a message.

For example, if I can be guarenteed of breaking your DES encrypted
message in a year (say I can mount a brute force attack that does 2^56
encryptions and takes a year), there is an 8% chance the key will be
recovered in one month.  So even if you change your key every month, I
have an 8% chance of success.  If your key is needed to conduct
financial transactions and you are a bank, I can profit greatly from
one success.

So basically, DES is looking more and more disadvantaged with its
relatively small key size (64 bits, of which 8 are predictable parity
bits).

Karl Barrus <klbarrus@owlnet.rice.edu>



-----BEGIN PGP SIGNATURE-----
Version: 2.3a

iQCVAgUBLLzEJ4OA7OpLWtYzAQHE7AP7BpG0k0bOjLbTPJbiaMzEFSZuquo/te0w
EeD4cC22jru8jXCEtM6AUHp94UJucAXDzY7szDhNlcMY5uv0OIXaFyoohPxBDEw5
CxKKUt0TxpqFdGwwkW8jpPMoBtZa8rGu/yPEZJ9CmcuHDANbEnVlQ9w8weMTWDHD
qqCSlsuziOs=
=hS3G
-----END PGP SIGNATURE-----