Question

If a hash function reduces 264 bits to 256 (28) bits, how many collisions can be expected for any given input? Why does that number of collisions not undermine the purpose of a hash function, namely, to demonstrate that it is unlikely that an undetected change can be made?

(Computer Security II)

Answer 1

The expected number of new collisions caused at the time of inserting the k-th ball is k−1/M since it has a 1/Mcollision probability with each ball already placed.

Thus the expected number of collisions is

0/M+1/M+2M+⋯+(N−1/)M=N(N−1)/2⋅1/M

264*263/2. 1/256 = 135.6 ~ 136

In many cases the collision might be exploitable to create many other collisions. In almost all common constructions you could use the collision to build a collision of messages with arbitrary suffix. Building a usable collision for most attacks like colliding pdfs requires something about the prefix. But even without a known attack on the relevant prefix, a different exploitation scenario exists. There is an efficient way of generating collisions it's simply not public.

Furthermore the structure of the collision may give important cryptographic insights.

I would like to take an example of SHA-1 to analyse the effects of hash collisions

Currently, given the specific collision method used, the impact is quite limited. In particular, this method does not allow for an attacker to generate a collision with an existing file, where a SHA-1 hash has been provided. It wouldn't be possible, for example, to use this method to generate a malicious executable file which matched the signature provided on the legitimate distribution website.

It would be possible, in theory, for an attacker to generate two executable files which have the same SHA-1 hash, but perform different things when run. Similarly, it would be possible to generate multiple ISO images which have the same SHA-1 hash. However, in each case, other hash values would not match, and it's common for download sites to provide multiple types of hash (for example, Ubuntu provide MD5, SHA-1 and SHA256 hashes for all downloads). This can be seen with the shattered-1.pdf and shattered-2.pdf files:

# sha1sum shattered-1.pdf
38762cf7f55934b34d179ae6a4c80cadccbb7f0a  shattered-1.pdf

# md5sum shattered-1.pdf
ee4aa52b139d925f8d8884402b0a750c  shattered-1.pdf

# sha1sum shattered-2.pdf
38762cf7f55934b34d179ae6a4c80cadccbb7f0a  shattered-2.pdf

# md5sum shattered-2.pdf
5bd9d8cabc46041579a311230539b8d1  shattered-2.pdf

It may be possible to create a kind of polyglot file which produces the same hash values in both SHA-1 and MD5, but this has not been demonstrated, and would still fail, given, for example, a SHA-512 hash.

It may be possible to create a kind of polyglot file which produces the same hash values in both SHA-1 and MD5, but this has not been demonstrated, and would still fail, given, for example, a SHA-512 hash.

Similarly, for any system where a SHA-1 hash is used as a file identifier, it may be possible to get one half of a colliding pair of files into the system, then to swap it out for the other. An example of this would be a backup system which used SHA-1 on a file level for determining whether files had been copied correctly. However, it would be difficult to make a hash of the entire backup contents remain the same in this case, since the malicious file is unlikely to form the prefix for the whole backup file (it's more likely to be something identifying the whole file as a backup).

Overall, therefore, the Google announcement mostly just confirms what had been suspected for a while - SHA-1 is vulnerable to collisions, just as MD5 was, but finding them requires a lot of effort, and most of the really high profile targets (such as generating CA certificates) have mitigation in place from the very similar MD5 collisions found previously. Experts have been advising moving from SHA-1 for a while now, and this advice still stands.

Just as with MD5, however, this doesn't particularly impact the use of HMAC-SHA1, since the specific combination method used in the construction of HMAC values makes this type of collision irrelevant