Explicit Key SHA-1

Question

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)

Answer 1

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.