0
$\begingroup$

I'm reading “Collision-Resistant Hashing? Towards Making UOWHFs Practical” and in the Section 2 it says:

Hash functions like MD5 or SHA-1 have no explicit key. But no notion of collision-freeness has been offered for such a keyless setting. To get a sense why this is so, suppose $f$ is a function $f:\sum^*\rightarrow\sum^c$ for some integer $c$. We would like to say it is collision-free if there is no efficient program that can find collisions in $f$ But in fact, no matter what is $f$, there is such a program. Clearly there exists a pair $M,M'$ which is a collision for $f$, and hence there exists a program which very quickly finds collisions, namely the program that has the description of $M,M'$ embedded in its code and just outputs $M,M'$. While in practice it may be difficult to explicitly find this program a formalization in terms of the existence of collision-finding programs is ruled out. It seems the natural way to get a meaningful notion of security is to talk about families of functions

I have the following questions:

  • Why does it say that SHA-1 has no explicit Key? I remember that SHA-1 has a initial value into code, then the answer could be: because no external key is passed by argument to SHA-1

  • I don't understand the relation between the example and why not be offered to SHA-1 and MD5 the notion: collision-freeness (maybe I don't understand the English in that paragraph)

$\endgroup$
5
  • $\begingroup$ Answer to Q1 is probably "correct". Personally, I have trouble reading your second question, could you try and update the answer? $\endgroup$
    – Maarten Bodewes
    Nov 11, 2013 at 20:21
  • $\begingroup$ Am I crazy, or is that paper saying that there is a function to find collisions because there are collisions. That is certainly true, but the question remains how to find a function to create a collision. Sounds very chicken-egg to me. I wonder if the stance of the authors would be different now SHA-2 seems reasonably secure. $\endgroup$
    – Maarten Bodewes
    Nov 11, 2013 at 20:24
  • 2
    $\begingroup$ "is that paper saying that there is a function to find collisions because there are collisions" - I think you've got it right. If a hash function isn't keyed, then there are trivially collisions and you can't claim collision freeness, therefore the proofs have deal with families of hash functions and reduce that to unkeyed instantiations. Rogaway explains this in Formalizing Human Ignorance: Collision-Resistant Hashing without the Keys. $\endgroup$
    – archie
    Nov 11, 2013 at 20:38
  • $\begingroup$ @archie What's a suggest to read that papers? Do you think that first I must read "Formalizing Human Ignorance: Collision-Resistant Hashing without the Keys" and secondly “Collision-Resistant Hashing? Towards Making UOWHFs Practical”? $\endgroup$
    – juaninf
    Nov 11, 2013 at 21:33
  • $\begingroup$ @archie understand, ... now my question is Why Ruled out collision-finding programs for formalization? $\endgroup$
    – juaninf
    Nov 11, 2013 at 23:34

1 Answer 1

3
$\begingroup$

SHORT:

  • SHA-1 does not have explicit key. HMAC is the way to construct keyed hash from SHA-1.
  • Collision free means that there is no different inputs known to hash which give the same result.

DETAILED

The most of the currently used cryptographic hash functions have some specific initial values embedded within them. Usually Nothing up my sleeve numbers are used for initial values. It can be estimated that if those initial values were substituted with some other random values, the resulting function would be another hash function (often) of similar strength than the original function.

SHA-1 does not have explicit key, as changing the explicit initial value would not result in what keyed hash usually means. The aforementioned article in Wikipedia explains hash-based message authentication codes, sometimes called keyed hash. You ordinarily should use HMAC with SHA-1 if you want keyed hash.

Substituting initial value with your own key material would produce mac function is vulnerable to attack known as length extension, just like e.g. $H(key || message)$ construct. This is why you should not try to use alternative initial value as key.


Collision-free means property that there exists no same value for hash, e.g. $SHA1(a) = SHA1(b)$, assuming a and b are different bit strings. This property is not true for MD5 hash, because for MD5 there are known collisions. For SHA-1, there are very efficient algorithms for trying to discover collisions and in near future likely some SHA-1 collision will be public known. It is well possible that large organizations like NSA or some foreign governments had already discovered some SHA-1 collisions.

BTW, SHA-2 family hashes are nowadays by many experts recommended over SHA-1, mainly because SHA-1 is too close to having collisions. SHA-2 hashes are fairly similar to SHA-1. Currently it is not known that anybody would know any collision in any SHA-2 family hash.

$\endgroup$
3
  • $\begingroup$ Then Why hash function than SHA-1, SHA-2 are considered cryptographic hash function if these are not keyed? $\endgroup$
    – juaninf
    Nov 11, 2013 at 21:39
  • 1
    $\begingroup$ Hash function never takes a key. Please, read cryptographic hash function for basic explanation what hash function is. $\endgroup$
    – user4982
    Nov 11, 2013 at 22:31
  • $\begingroup$ but then How I will be able to formalize SHA-1? $\endgroup$
    – juaninf
    Nov 12, 2013 at 13:52

Your Answer

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

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