From: schneier@chinet.chinet.com (Bruce Schneier)
Date: Tue, 21 Jun 94 20:18:10 PDT
To: cypherpunks@toad.com
Subject: Thoughts on the NSA's correction to SHA
Message-ID: <m0qGIjn-0006ZmC@chinet>
MIME-Version: 1.0
Content-Type: text/plain



This is the fix to the Secure Hash Standard, NIST FIPS PUB 180:

     In Section 7 of FIPS 180 (page 9), the line which reads

     "b) For t=16 to 79 let Wt = Wt-3 XOR Wt-8 XOR Wt-14 XOR
     Wt-16."

     is to be replaced by

     "b) For t=16 to 79 let Wt = S1(Wt-3 XOR Wt-8 XOR Wt-14 XOR
     Wt-16)."

     where S1 is a left circular shift by one bit as defined in
     Section 3 of FIPS 180 (page 6):

     S1(X) = (X<<1) OR (X>>31).

This is exactly one additional line in assembly language.

The very fact that this correction had to made offers some
insights into the National Security Agency.

I believe that releasing DES to the public was the biggest
cryptography mistake that NSA ever made.  Consider the state of
research in cryptology before DES.  It was simplistic.  It was
haphazard.  There was little interest.  If any results of value
were ever discovered, the NSA could squash them with a secrecy
order.  No one cared.

Then, in the late 1970s, came DES.  Suddenly there was a an
algorithm to argue about, dissect, study, and learn from.  A
whole generation of cryptographers learned their craft from DES. 
Even today, we're still learning from DES.  We're learning new
techniques of cryptography and cryptanalysis.  DES has
transformed academic cryptology in ways the NSA never envisioned.

The NSA will not make this mistake again.  They will not release
Skipjack or any other algorithm to the public, because that could
galvanize another fifteen years of research in algorithm design
and analysis.  (Even so, I believe that Skipjack is similar in
design to DES; the NSA realizes that Clipper chips will be
reverse-engineered eventually.)

When it came time to propose an algorithm for the SHS, the NSA
chose not to use an algorithm from its own arsenal.  Instead it
chose to take an algorithm from academia, Ronald Rivest's MD4,
and modify it to produce a 160-bit hash.  While this approach did
not compromise any of NSA's work, it also short circuited NSA's
lengthy internal algorithm design and review process.  The SHA
was announced only two years after MD4.  By contrast, NSA claims
to have spent five years designing and analyzing their Skipjack
algorithm, based on an additional seven years of design.

There is no substitute for years of intense cryptanalysis, and
the flaw in SHA illustrates that.


From owner-cypherpunks  Tue Jun 21 20:47:03 1994