Subject: RE: [Cfrg] A simple and provably good code for SHA Message Expansion

From: Charanjit Jutla <[email-masked]>
Date: Sun, 14 Aug 2005 01:02:56 -0400

> >Scott Fluhrer writes:
> > > >
> > > >
> > > > -----Original Message-----
> > > > From: [email-masked] 
> > > >[mailto:[email-masked]] On  > > Behalf Of Charanjit 
> > > >Jutla  > > Sent: Friday, August 12, 2005 1:17 AM  > > To: 
> > > >[email-masked]  > > Cc: [email-masked]  > > Subject: 
> > > >[Cfrg] A simple and provably good code for SHA  > > Message 
> > > >Expansion  > >  > >  > > This new paper with the above title 
> > > >maybe of interest to CFRG.
> > > > The authors are myself (Jutla, IBM) and Anindya Patthak 
> > > > (UT Austin).
> > > > It is posted on eprint archive: 
> > > >http://eprint.iacr.org/2005/247  > >  > > Abstract: We 
> > > >develop a new computer assisted technique for  > > lower 
> > > >bounding the minimum distance of linear codes similar  > > to 
> > > >those used in SHA-1 message expansion. Using this  > > 
> > > >technique, we prove that a modified SHA-1 like code has  > > 
> > > >minimum distance at least 82, and that too in just the last  
> > > > 64 of the 80 expanded words. Further the minimum weight 
> > > >in  > > the last 60 words (last 48 words) is at least 75 (52  
> > > > respectively). We propose a new compression function 
> > > >which is  > > identical to SHA-1 except for the modified 
> > > >message expansion  > > code.We argue that the high minimum 
> > > >weight of the message  > > expansion code makes the new 
> > > >compression function resistant  > > to recent differential attacks.
 
> > > Question: what is the minimum weight, if you consider only 
> > >at the output  > bits 0-30 of each word?  Here's why I am 
> > >asking: when SHA-1 stirs in the  > expanded message, it uses 
> > >the relative nonlinearity of add and xor to do  > that in a 
> > >nonlinear fashion.  However, bit 31 acts perfectly linearly, 
> > > and  > >so an active bit there, at least in the initial add of 
> > >the round, acts  > perfectly predictably (both in terms of an 
> > >xor and an additive  > differential).
 
> > Hi Scott,
> >I think it does not matter. The overall weight is what 
> >counts, as all we care is average 2^{-2.5} per disturbance 
> >bit, and even in XOR rounds  it is at least  2^{-1}.  So, 
> >since we show a lower bound of
> >82 in last 64 words, and 75 in last 60 words, it is way above 
> > what one gets with birthday bound.

> Please correct me if you have done a more thorough analysis, but just
> counting 'active elements' as a differential flows through the SHA-1 round
> structure doesn't appear to be sufficient.  Each primitive within the SHA-1
> structure (add, xor, rotate, majority and select) has probability 1
> differentials.  You need to show (at the very least) that, even taking these
> into account, a differential with N active bits in the expanded message has
> to hit enough other structures with lower probability differentials. 

Yes, we have done a more thorough analysis. Thats part of the argument which is
to appear. If you want I can explain it in more detail. But clearly,
the original concern you had (about distrubance bits starting in bit 31, and your
claim that somehow they are taken care of by prob 1 is wrong, as probably
you forgot that the difference is not quelled in one step, it goes to B and then
gets rotated by 2 and goes to C, where now the carry cant just overflow...) is a
non-issue.
 
> >
> >In fact, I will go on a limb here, and claim that this makes 
> >the the modified SHA  as unbreakable as say RSA-(2048 bits), 
> >as both rely on assumptions -- infact the latter relies on an 
> >assumption which is not even  known to be NP-hard, whereas 
> >this modified SHA (we will argue in an upcoming paper) is 
> >more or less a general form of the Polynomial Constraint 
> >Satisfaction Problem over GF2 (which is known to be NP-hard 
> >even with degree two polynomials).

> Ummm, no.  It is not "a general form" of SAT, it is a specific instance of
> SAT.  That SAT has hard problem instances does not imply that the specific
> instance of SAT you have is hard.

Of course, SAT has easy instances. Thats why SHA-0 and SHA-1 got broken, as when
the expansion code is bad, you end up with a system with a sparse set of equations,
which leads to good randomized algorithms on such easy instances. But, the REAL
argument is that when the code is good, you get a dense system... and every instance
with a good code is equally difficult... there is no proof of this, as also there
is no proof that RSA or Discrete Log is secure on average (on which most of
public key cryptography is based). There are other deeper complexity theory
results on this issue, and I will pass on them here for the moment.

> >However, as I said 
> >earlier, our  confidence in this claim is not perfect yet, 
> >and we are working on various technical details to give a 
> >reasonable argument.

> BTW: are you working on an argument or a proof?
Mostly it will be an argument, but we will try to prove what can be proven.

> >
> >-Charanjit
> >
> >
>  >
>  > > >
>  > > >Synopsis:
>  > > >Basically, the code (of length 80 Words)  is given by 
> > > > the  > > following parity check equations:
> > > >
> > > > W_i = (W_{i-3} xor W_{i-8} xor W_{i-14} xor W_{i-16}) xor 
> > > > >      ((W_{i-1} xor W_{i-2} xor W_{i-15}) <<<13)   for i= 
> > > > [16..35],  and
> > > > W_i = (W_{i-3} xor W_{i-8} xor W_{i-14} xor W_{i-16}) xor
> > > > >      ((W_{i-1} xor W_{i-2} xor W_{i-15} xor W_{i-20}) <<<13) 
> > > > for i= [36..79].
> > > > 
> > > > >  -Charanjit Jutla
> > > >
> > > > _______________________________________________

_______________________________________________
Cfrg mailing list
[email-masked]
https://www1.ietf.org/mailman/listinfo/cfrg