From: koontzd@lrcs.loral.com (David Koontz )
Date: Thu, 14 Oct 93 08:30:00 PDT
To: cypherpunks@toad.com
Subject: DES: breaking, attacking
Message-ID: <9310141529.AA04661@nebula.lrcs.loral.com>
MIME-Version: 1.0
Content-Type: text/plain


>From: Karl Lui Barrus <klbarrus@owlnet.rice.edu>
>interesting property of DES is that of complimentation.  That is, if

Thats complementation.  T is the complement of T'.  T is not complimenting
T' on a new pair of shoes.

>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.

Whose book?

There is a recent paper on brute force DES breaking:

ripem.msu.edu:/pub/crypt/docs/des_key_search.ps, which discusses 
pipelined DES chips capable of doing 50 Million DES iterations per second.
(I believe the rate is conservative, and can be increased by 50 percent.) 

The point being that any concept of time to attack DES found in print
is in danger of being inaccurate shortly after publication.

Also DES runs 1,000 - 2,000 times faster in hardware than software 
implementations (although someone sent mail saying they had a CRAY MP
software version).

NSA tried to get DES decertified for unclassified government data in
1987-88.  I would guess they either saw the handwriting on the wall or
have a key breaking machine.  The machine in the paper cited above could
break a key in 3 1/2 hours for $1 million in hardware costs, or a few minutes 
for $10 million worth of hardware.

There are several criteria involved in cost/protection.  NSA is still
discouraging the spread of DES.  Enough people using DES everywhere would
make it harder to pick who they target, or require lots of key breaking
machines to search for keys to lots of traffic.  Assuming that an adversary
had a machine capable of doing a search in 3 1/2 minutes that he could
dedicate to finding your key, how often would you have to change keys to
make it not worth while?  If he was very interested in your traffic, it
becomes a question of volume - can he decrypt all the traffic you generate
in 24 hours in a 24 hour interval?  A dedicated target search with unlimited
money would make DES totally insecure.  If on the other hand they have
to wade through lots of encrypted traffic (Because there is no Law Enforcement
Access Field ala clipper) from various parties, and it all needs to
be decrypted, the cost/benefit ratio goes to hell.  The real world falls
somewhere in between.

Hardware key attack machines can be defeated by using variants of
the cryptographic algorithm they attack.  Most variations of DES have
been shown to be cryptographically weaker (Biham-Shamir, "Differential
Cryptanalysis of the Digital Encryption Standard", (Chap 4), Springer-Verlag
1993).  The Biham-Shamir book does point to at least one method of
modifying DES that doesn't weaken it, incidently closing the complementation
property.  A lot of people have been using triple DES for years.
There are several other schemes, or algorithms that are supposed to be
harder to break for that matter.  DES has had the lions share of non-government
attention in the last several decades.