Re: A public key authentication scheme based only on hash functions

From: jim steuert (pjsteuert@rcn.com)
Date: 03/07/03 

From: jim steuert <pjsteuert@rcn.com>
Date: Thu, 06 Mar 2003 23:21:09 -0500

Hello Francois,

   Yes, I made a hasty mistake about using SHA-1 in that manner. However,
my intention was to use SHA-1 to "hash" a larger number of bits k>160, and
yet
also output that same number of bits. In other words, how can you
safely make an n-bit hash, where n>160, from SHA-1? Do you have
a suggestion, short of using SHA-256, etc?

 And I am not convinced that cad design tools like Ever and BDD's will
not someday invert SHA-1. The fact that it did handle a huge number of
boolean terms in 160 boolean variables is significant. The fact that there
are only 5 32-bit data words W0-W4 means that
many of the 80 rounds are simpler: W0-W4 are data, W5-W15 are pad
constants, and W16-W31 are simpler expressions. The fact that
the feistel inversion "factors-out" some of the complexity
of the 80 rounds only makes it more likely that SHA-1 is
invertible on the data words.

I don't think that the feistel nature of SHA-1 necessarily
negates the primary point of Dean's thesis; that the cad tool
can be used to invert the hash.

Are you asking us to put blind faith in SHA-1? The SHA-1
compression function with 160-bits of data input (W0-W1-W2-W3-W4) is a
fairly simple multipermutation mixer.

So do we have "security by boolean obscurity"? If not blind faith,
then what feature(s) give you confidence?

 As regards the security or invertibility of SHA-1 with 160-bit input,
are you aware of the design rationales of NIST in their design choices
behind SHA-1? I have gleaned some of the following points:

     1. It is an unbalanced feistel-network with the message digest being
invertible
         for any fixed data input. ("Unbalanced Feistel Networks and
Block-Cipher
         Design" by Bruce Schneier and John Kelsey)
     2. The data words are introduced as would be the key schedule in
         a feistel block cipher. The message digest is invertible for fixed
         data input, just as is any feistel cipher with a fixed key.
     3. All mixers are multipermutations to preserve statistics of any
          given output. ("On the Need for Multipermutations:
          Cryptanalysis of MD4 and SAFER", by Serge Vaudenay)
     4. Each f-function is a balanced surjective boolean function of its
inputs.
         ("On Weaknesses of Non-surjective Round Functions",
          by Vincent Rijmen and Bart Preneel)
     5. The addition mixers spread the boolean-dependencies within 32-bit
words by virtue
          of carries (i.e. not being just bit-wise like xor).
     6. The 80 rounds insures many complex boolean relationships
          among the bits of the transformed message digest..
     7. Resistance to differential and linear cryptanalysis, is ensured
not,
         as in AES, by algebraic or GF(2^8) inversion, but by unknown means.

         ("Differential Cryptanalysis of SHA-0", by Florent Chabaud and
Antoine Joux)
     8. Diffusion is ensured not via an MDS code, as in Twofish, but
         by other means. (80-rounds...??)

This still leaves open a lot of design decisions. I am aware of
a paper by Bob Jenkins who produced a hash mixer and gave
an experimental search rationale for his choices of shifts, xors,
and additions/subtractions. The tiger hash function key schedule
also discussed the rotates, etc, but without a rationale for that
particular part of the design. There is also the recent paper:
"Cryptanalysis-tolerant Commitment and Hashing", by Amir Herzberg,
which explains advantages in some schemes to put together mixers.

Unlike Rijndael, however, the SHA-1 design decisions have not been
explained, although they do make some sense.
Indeed, in public comments for NIST fips 180-2, Jakob Jonsson
of RSA asked NIST to publish a security evaluation of SHA-256, -384,
and -512, which they did not.

  -Jim Steuert

Francois Grieu wrote:

> In article <3E63472C.B80D3DFC@rcn.com>, jim steuert <pjsteuert@rcn.com>
> wrote:
>
> > the fact that usage of the Ever language, and 120Mbytes of
> > Binary Decision Diagrams was able to invert at least the
> > (feistel-invertible but they didn't know that) 160-bit
> > version makes be uneasy about using SHA-1 in that context
> > with only a 160-bit data input.
>
> Finding a fixed point for the compression function of SHA1-1 is easy,
> and this a direct consequence of its design. That this task can be
> acomplished thru the use of Ever, 120Mbytes of BDD, etc.. as a substitue
> for a trivial program requiring almost no storage does not in any way
> reduce the confidence we can have in SHA-1; or in SHA-256, SHA-384 or
> SHA-512 which have the very same property.
>
> > Why not just do this with 320-bits using two SHA-1's and mixing?
>
> Because constructing one's cryoto primitive is problem-prone.
>
> > Let the 320-bit input be <y1 y2> where each of y parts are 160-bits.
> > Then form x1=y1 xor sha1(y2) also x2 = sha1(y1) xor y2, and
> > finally x = x1 xor x2. This give a 320-bit hash
>
> This gives a 320 -> 160-bit hash, for which it is trivial to exhibit
> collisions: any input with identical halves hashes to zero. Even if we
> change the output to x = x1 # x2 to get a 320 bits output, equality of
> halves is conserved by the transformation; and it is trivial to find y2
> for any y1 and x2 specified in advance.
>
> > One could also uses sha-256, or sha512, or any similar hash.
>
> This seems to be on the safe side.
>
> Francois Grieu

Relevant Pages

  • Re: SHA-1 and the "birthday paradox"
    ... risk of collision when using SHA-1 as a digest, or hash key, for ... identical SHA-1 digest referring to two distinct blocks rather than a ... If you find a collision on SHA-1 then you may publish it and become ... (Cost is here expressed in number of hash function computations which ...
    (comp.lang.forth)
  • Re: [Full-disclosure] Chinese Professor Cracks Fifth Data Security Algorithm (SHA-1)
    ... SHA-1 is 160 bit hash. ... MS> professor Wang Xiaoyun of Beijing's Tsinghua University and Shandong ... Wang's research focusses on hash algorithms. ...
    (Full-Disclosure)
  • Re: Cryptographic hash function for small microcontroller
    ... The microcontroller is fairly fast ... SHA-1 and related hashes all require too much RAM for this ... <Then you can't have a cryptographic hash. ... microcontroller) to a PC using a shared secret. ...
    (sci.crypt)
  • RES: sha-1 cryptography
    ... SHA-1 is not a criptographic algorithm, it's a hash algorithm, and it is known that SHA-1 just as all others SHA algorithms have a finite number os possibilities for a hash code. ... tenha recebido por engano, por favor, informe o remetente e apague-a de ...
    (Security-Basics)
  • Re: padding scheme
    ... so the program converts the password into a key for the individual algorithm. ... Blowfish Advanced CS uses a key setup in which your password (or key disk ... content) is hashed with SHA-1, ...
    (sci.crypt)