Tell me more ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.
up vote 3 down vote favorite

I'm building a system that has to take file paths, and generate a unique name for each one. I'm planning on using SHA1 as the hash function. My question is: do I have to deal with possible collisions (2 different paths producing the same SHA1 value) or can I assume it won't occur?

share|improve this question
You might find this Stack Overflow question and its answers useful stackoverflow.com/q/862346/57428 It uses MD5 in the same scenario, but based on the file contents. – sharptooth May 12 '12 at 7:18

3 Answers

up vote 8 down vote accepted

The chance of a collision in such a set is approximately $ \frac{1/2 \cdot n^2}{2^{160}} $, which for n=100k evaluates to about $ 3.4 \cdot 10^{-39} $. So it is fair to say, such a collision won't occur accidentially.

AFAIK nobody has every found a SHA-1 collision. Collisions become likely once you generate about $2^{80}$ or $10^{24}$ hashes.

If cryptoanalysis advances, an attacker might be able to create inputs that deliberately collide. But currently there is no known way to do this efficiently. Of course this only applies if your application needs to protect against deliberate collisions. Many applications only require protection against accidental collisions. If you need protection against deliberate collisions, I'd prefer SHA-2 over SHA-1.

share|improve this answer
1  
Note: Deliberate SHA-1 collisions might theoretically be generated with a work factor of $2^{51}$ according to this paper: eprint.iacr.org/2008/469.pdf. It might be worth mentioning that it is also not self evident that the system described by the OP does not have to protect itself from deliberate collisions. For instance, the OP should perhaps consider the possibility that an installer for some software creates two file paths that hashes to the same value? Would that be an exploitable weakness? – Henrick Hellström May 11 '12 at 13:44
2^51 sounds computationally feasible. Why haven't we seen any collisions yet? – CodesInChaos May 11 '12 at 18:17
I haven't looked at any of the relevant pdfs, but it might be due to the algorithms being highly sequential (if they are in fact highly sequential). – Ricky Demer May 12 '12 at 7:37
1  
$2^{51}$ is not (but almost) feasible if the algorithm is iterative, I did some back of the envelope calculations and it still comes out at roughly 4 years of work on the fastest known processor on the planet (8.4GHz), assuming 10 cycles per byte for SHA-1. If it could be parallelized then the workload is trivial and would take a negligible time on a GPU cluster. – Thomas May 12 '12 at 8:55
Thanks all. Note that I'm not worried about deliberate attempts at causing collisions, just likelihood of them occurring by chance. – Denis Hennessy May 12 '12 at 11:46
show 2 more comments
up vote 0 down vote

Answer through experiment and observation.

i hashed:

In all 1,082,765 of those hashes, there were zero collisions.

This contrasts with some of the common non-cryptographic hash functions, that experience a dozen or so collisions (with a 32-bit hash, as opposed to SHA1's 160-bit hash), e.g. in Murmur2 hash:

  • cataract collides with periti
  • roquette collides with skivie
  • shawl collides with stormbound
  • dowlases collides with tramontane
  • cricketings collides with twanger
  • longans collides with whigs

A suggestion would be to construct a few billion random path strings, and see if you get any collisions. Although i can say (as long as you're dealing with items less than 264 bytes in length) that with SHA-1:

it is computationally infeasible to find two different messages which produce the same message digest

share|improve this answer
Sorry, modded down because this is not a question you should answer by performing experiment and observation. Pointing to the original security claim (from 1995) does not magically proof that SHA-1 collisions cannot be found - and with SHA-1 it is extremely likely that one will be found in the future. – owlstead May 13 '12 at 9:47
@owlstead "Is it fair to assume that SHA1 collisions won't occur on a set of <100k strings" Yes, it is fair to assume that SHA1 collisions won't occur on a set of <100k strings. – Ian Boyd May 13 '12 at 13:28
That can mean what you want it to mean, and nobody here is disputing that it's OK to assume such a thing. Your reasoning is invalid though, which is why I modded down. That said, my reasoning for the NIST paper not to be valid is not correct either; the questioner was not asking if collisions could be found or not. – owlstead May 13 '12 at 14:22
up vote 0 down vote

If you are not multi-threading, you could create unique file names by taking the current timestamp in nanoseconds and using that. Or you could use a millisecond-resolution timestamp and concatenate that with some quick hash. As a cryptographic hash the SHA-1 seems like an overkill if you use this method and you might get away with some simple CRC32 check sum, but if you want to be on the safe side you can use MD5 which is a cryptographic hash but faster than SHA1.

These methods kind of assume that the system clock is never turned back on accident or on purpose, or that the name generation process is only ran once.

share|improve this answer
Sadly, I need paths generated on different machine to hash to the same value. The creation times are not persisted to nanosecond resolution (and in any case I would think this actually has a higher chance of collision than the hash function). – Denis Hennessy May 12 '12 at 11:45
I was referring to using the current time (nanosecond timestamp) at the time of running the process that creates the unique names. Obviously no file system saves file creation time that precisely. And indeed this method is of no use if the name needs to be consistent across different systems. If you are afraid that SHA-1 is not robust enough, you could use SHA-512 or concatenate an SHA-1 and an MD5 hash. – ZeroOne May 12 '12 at 12:48
Please do not recommend the SHA-1 and MD-5 hash functions. Concatenating them may have unforseen security vulnerabilities. It's not standard practice (outside of older SSL protocols) and it is much much slower than simply using either one of the SHA-2 candidates (go for the 64 bit optimized versions on server machines, SHA-512 is a good candidate). – owlstead May 13 '12 at 9:51
Actually, time stamps have serious issues as well. You may not know the state or resolution of the clock. You may not use UTC time which means you may get overlaps, your clock may have issues with NTP. Better not rely on an "external source" if not absolutely required. – owlstead May 13 '12 at 14:28

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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