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?
$\begingroup$
$\endgroup$
1
asked May 11, 2012 at 10:13
-
$\begingroup$ 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. $\endgroup$– sharptoothMay 12, 2012 at 7:18
Add a comment
|
4 Answers
$\begingroup$
$\endgroup$
8
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 ever found a SHA-1 collision The only concrete SHA1 collision to date was Google's on February 23rd, 2017 (found here). 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. Currently, however, 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.
answered May 11, 2012 at 10:35
-
2$\begingroup$ 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? $\endgroup$ May 11, 2012 at 13:44
-
$\begingroup$ 2^51 sounds computationally feasible. Why haven't we seen any collisions yet? $\endgroup$ May 11, 2012 at 18:17
-
$\begingroup$ 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). $\endgroup$– user991May 12, 2012 at 7:37
-
2$\begingroup$ $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. $\endgroup$– ThomasMay 12, 2012 at 8:55
-
$\begingroup$ Thanks all. Note that I'm not worried about deliberate attempts at causing collisions, just likelihood of them occurring by chance. $\endgroup$ May 12, 2012 at 11:46
$\begingroup$
$\endgroup$
4
Answer through experiment and observation.
i hashed:
- all 216,553 words in the English language
- uppercase form of all 216,553 words in the English language
- 216,553 type 1 ("sequential") uuids
- 216,553 type 4 ("random") uuids
- all numbers from
"1"to"216553"
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:
cataractcollides withperitiroquettecollides withskivieshawlcollides withstormbounddowlasescollides withtramontanecricketingscollides withtwangerlonganscollides withwhigs
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
-
1$\begingroup$ 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. $\endgroup$ May 13, 2012 at 9:47
-
$\begingroup$ @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. $\endgroup$– Ian BoydMay 13, 2012 at 13:28
-
$\begingroup$ 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. $\endgroup$ May 13, 2012 at 14:22
-
$\begingroup$ In general, the collision probability for a dictionary of words (the majority being 8 characters or less) is likely to be different (perhaps lower) than for longer strings like the pathnames that the OP asked about. Indeed, it wouldn't surprise me if all possible 8-byte strings had already been checked for collisions before SHA-1 was even published (A collision for such short strings would have been downright embarrasing for a cryptographic hash...) $\endgroup$– QwertieAug 11, 2014 at 23:18
$\begingroup$
$\endgroup$
If you want an absolute guarantee of no collisions, then use a cipher, not a hash. Encrypt the numbers 0, 1, 2, ... 99998, 99999, 100000 and the outputs are guaranteed to be unique for a given key. Convert to hex or Base64 for incorporation into a filename. Hasty Pudding cipher can be set for any desired range of numbers, or use DES for 64 bit numbers. You could even roll your own simple Feistel cipher with an 18 bit block size if security is less important than uniqueness.
$\begingroup$
$\endgroup$
5
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.
-
$\begingroup$ 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). $\endgroup$ May 12, 2012 at 11:45
-
$\begingroup$ 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. $\endgroup$– ZeroOneMay 12, 2012 at 12:48
-
$\begingroup$ 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). $\endgroup$ May 13, 2012 at 9:51
-
$\begingroup$ 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. $\endgroup$ May 13, 2012 at 14:28
-
$\begingroup$ Combining of multiple hashes works and there are save ways to do that, but it is far from trivial. In the worst case, you get the security (collision resistance) of the weakest one, and then having MD5 is a terrible way. Anyway, suggesting MD5 for anything is really bad, unless you are absolutely sure you understand when and how the weaknesses of MD5 can be exploited. There are algorithms, where MD5 can still be used - but they are rare and require careful consideration. $\endgroup$– tyloApr 28, 2015 at 12:49