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

From: Charanjit Jutla <[email-masked]>
Date: Fri, 12 Aug 2005 04:16:43 -0400

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. 

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

---

From: David McGrew <[email-masked]>
Date: Fri, 12 Aug 2005 07:37:58 -0700

Hi Charanjit,

this is interesting work.  I haven't read through the analysis on the 
bounds yet, but the intuition looks good.  I have a few comments and 
questions.

1. It looks like an excellent speed-security tradeoff compared to SHA1, 
at least to me (and it would be good to hear from some of the people 
who have attacked that function).  I assume that you'll be presenting 
this work at the upcoming NIST workshop.

2. If I understand correctly, your proposal is to modify the FIPS-180-1 
algorithm by changing Step B in Section 7, but leaving all other steps 
unchanged.  Is that right?  If so, I think that it would be useful to 
state it that way.

3. Do you have test vectors?  It might be useful to allow others to 
verify implementations, to test performance if nothing else.  (I 
slapped an implementation together in ~15 minutes FWIW).

4. Why is the extra W[i−20] term present in the computation of W[t] for 
36 <= t <= 79, but not 0 <= t <= 35?  Is this just to cut down on 
computational cost by adding strength only where it is needed, for 
higher t values?  (If there is a more mathematical reason, I may have 
missed it for not reading the analysis yet.  I guess that the term 
never includes any of the "message symbols" for the code, perhaps that 
matters.)  Obviously the term can't be present for 16 <= t <= 19, so I 
guess that there is a need to have a case statement in the equation for 
W[i].

David

---

From: "Scott Fluhrer" <[email-masked]>
Date: Fri, 12 Aug 2005 09:28:21 -0700

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

---

From: csjutla <[email-masked]>
Date: Fri, 12 Aug 2005 13:21:27 -0400 (EDT)

> perfectly predictably (both in terms of an xor and an additive

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. 

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

-Charanjit

---

From: "Scott Fluhrer" <[email-masked]>
Date: Sat, 13 Aug 2005 17:05:10 -0700

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