2
$\begingroup$

Does SHA-1 meet the strict avalanche criterion? I've been looking for a paper to cite on this, but haven't found one.

It's something that seems to be easy to check (in "On the Design of S-Boxes", Webster & Tavares lay out how it can be done), so it is surprising to not find a paper on it. Has it been put down as a small result in some other paper? Or has the SAC been discarded as a useful metric? Or have I somehow missed the relevant paper (accept my apologies if so!)? Any pointers would be gratefully appreciated.

Edit: is Hash function balance and its impact on birthday attacks relevant? Is the "balance" metric simply a better/different way of expressing the SAC?

Improve this question
$\endgroup$
5
  • $\begingroup$ Did you do the math on how much computation you would need to do for SHA1 given that its input space consist of all message whose length is smaller than 2^64 ? $\endgroup$
    – Alexandre Yamajako
    Commented Jul 7, 2015 at 11:02
  • $\begingroup$ @AlexandreYamajako I'm aware of that, but it's entirely unnecessary. Webster & Tavares point to an alternative method (see end of p.2 & start of p.3) which can be repeated as often as desired with different random starts until one is satisfied. But has anyone actually done this? $\endgroup$
    – Rhyme
    Commented Jul 7, 2015 at 11:08
  • $\begingroup$ I haven't and I don't really see the point : You're only ever going to look at a infinitely small portion of the input space. What this means is that this method doesn't answer your original question which was : "Does SHA-1 meet the strict avalanche criterion?" $\endgroup$
    – Alexandre Yamajako
    Commented Jul 7, 2015 at 17:10
  • $\begingroup$ @AlexandreYamajako I'm not sure what you're saying here. Because you can't get all the data, you shouldn't get any data? Yes, you will look at an infinitely small portion (though you need only look at 447-byte inputs, not 2^64, if the compression function interests you). That's how sampling works, and sampling is a well-established technique for achieving some level of confidence under these circumstances. $\endgroup$
    – Rhyme
    Commented Jul 8, 2015 at 10:29
  • 1
    $\begingroup$ This technique is efficient to weed out very bad hash function candidates but I doubt it will tell you anything about SHA-1. There was a lot of work put in finding flaws in SHA-1 by actually looking at SHA-1. I don't think you can really expect finding anything looking at SHA-1 as a black box. $\endgroup$
    – Alexandre Yamajako
    Commented Jul 9, 2015 at 9:36

1 Answer 1

Reset to default
2
$\begingroup$

There is a paper "SHA-1 and the Strict Avalanche Criterion."

From the abstract:

This work provides a working definition of the SAC, describes an experimental methodology that can be used to statistically evaluate whether a cryptographic hash meets the SAC, and uses this to investigate the degree to which compression function of the SHA-1 hash meets the SAC. The results (P<0.01) are heartening: SHA-1 closely tracks the SAC after the first 24 rounds, and demonstrates excellent properties of confusion and diffusion throughout.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Welcome to Cryptography, if you find more of this old gold questions, don't hesitate to answer them. By the way, your avatar strongly makes me think about surfing @ Beg ar Raz :) $\endgroup$
    – Maarten Bodewes ♦
    Commented Jan 14, 2020 at 10:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.