Subject: RE: [Cfrg] A good code for SHA etc.

From: csjutla <[email-masked]>
Date: Fri, 7 Oct 2005 13:13:42 -0400 (EDT)

May I divert your attention to a new paper we have written
(as promised earlier) which proves a useful theorem and does 
interesting analysis in support of the claim that 
SHA-1 with its message expansion code replaced by a new good code
(i.e. SHA1-IME) is collision resistant.

Tha paper titled "Is SHA-1  conceptually sound?"
can be found at http://eprint.iacr.org/2005/350

Thanks,

Charanjit Jutla

Scott Fluhrer writes:
 >  
 > 
 > > -----Original Message-----
 > > From: csjutla [mailto:[email-masked]] 
 > > Sent: Friday, August 12, 2005 10:21 AM
 > > To: Scott Fluhrer
 > > Cc: 'Charanjit Jutla'; [email-masked]
 > > Subject: RE: [Cfrg] A simple and provably good code for SHA 
 > > Message Expansion
 > > 
 > > 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. 
 >  
 > > 
 > > 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.
 > 
 > > 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?
 > 
 > > 
 > > -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
 > >  > >
 > >  >
 > >  > _______________________________________________
 > >  > Cfrg mailing list
 > >  > [email-masked]
 > >  > https://www1.ietf.org/mailman/listinfo/cfrg
 > > 
 > 
 > _______________________________________________
 > Cfrg mailing list
 > [email-masked]
 > https://www1.ietf.org/mailman/listinfo/cfrg

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