1993-10-14 - DES: breaking, attacking

Header Data

From: Karl Lui Barrus <klbarrus@owlnet.rice.edu>
To: cypherpunks@toad.com
Message Hash: 1b5315ec3067fd40f129740683cf482a349a74ab0a66a7284a655b01e30710d1
Message ID: <9310140317.AA06605@flammulated.owlnet.rice.edu>
Reply To: N/A
UTC Datetime: 1993-10-14 03:19:59 UTC
Raw Date: Wed, 13 Oct 93 20:19:59 PDT

Raw message

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


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

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

Karl Barrus <klbarrus@owlnet.rice.edu>

Version: 2.3a