0

There are a number of hashing functions in wide spread use now. Seems the general range of bits is from 128 (MD5) to 512 (SHA-2).

To prevent different types of hash collisions, what are the recommended & minimum number of bits?

Collisions:

  • Identifiers (PGP keys, bitcoin addresses, etc...)
  • Files (integrity checks)
  • HMAC (transmission integrity)
  • ?

closed as too broad by Steffen Ullrich, Serge Ballesta, Tobi Nary, TheJulyPlot, Rory Alsop Mar 31 '18 at 22:02

Please edit the question to limit it to a specific problem with enough detail to identify an adequate answer. Avoid asking multiple distinct questions at once. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

  • With HMAC and file integrity check collision is usually not the problem which need to get addressed. Identifiers are different but here it depends on how many identifiers in total you expect. In other words: collision is not the problem for two of your options and amount of resistance required is impossible to say without more details for the third option. Maybe you should ask instead a real problem you actually have with enough detail. – Steffen Ullrich Mar 22 '18 at 17:35
  • What application do you have in mind? – Cowthulhu Mar 22 '18 at 18:05
  • @Cowthulhu I don't have a specific problem in mind. I've been writing software for a long time and generally their are space requirements (minimum size) or future-proofing (recommended size) for tasks like de-duping files or referencing all possible ids. Having a reference of bit-sizes like this would be helpful. – Xeoncross Mar 22 '18 at 18:08
  • @Xeoncross: Note that de-duping files would require resistance against accidental collision (which is different from collisions on purpose). But de-duping is not the same as file integrity which you mention in your question and it also has different requirements. In other words: the actual requirements depend on the actual problem and there is no general rule. – Steffen Ullrich Mar 22 '18 at 18:24
2

A perfect hashing algorithm will output random bits for any unique input. Assuming a perfect hashing algorithm and an infinite amount of memory, the number of hashes you can generate before you will (on average) observe a duplicate, is around 1.2*sqrt(2^bits). A hashing algorithm with a digest length of 32 bits, will probably produce a duplicate after 77000 hashes. Or, if you want to have a chance of only 0.0001% that you find a duplicate, you may only generate 93 hashes using that algorithm. That's definitely possible with current hardware.

An algorithm with 64 bits output can already be used for over 6 million outputs before you have a chance higher than 0.0001% that a duplicate is produced. But still, 6 million we can do.

So to have a high level of confidence and still being able to generate as many hashes as you like, you need a certain number of bits. But how many bits you need depends on what confidence level you want to achieve. 128 bits is a good level for almost anything.

Another consideration is resilience against attacks. Often, an algorithm is not completely broken but only weakened more and more, until it becomes feasible to do realistic attacks in real-time (if ever). If your hashing algorithm is weakened, you will still want to have enough confidence remaining. That's why most protocols output a little more than necessary, such as 256 bits.

More about the math: https://en.wikipedia.org/wiki/Birthday_attack

  • I think OP is specifically asking about attacks, not accidental collisions (in which case a CRC is likely the way to go, since it can, depending on the polynomial, guarantee a different output for a certain number of changed bits in the input). Also oops, I think my editing the math notation messed up a simultaneous edit. Didn't realize you had just posted this! – forest Mar 23 '18 at 9:57
  • @forest I am talking about attacks. If someone has a reasonable chance of generating collisions after doing a bunch of hashing operations (still assuming infinite memory), then they can attack it... And as for math notation (your edit), I prefer code notation because it's more clear, particularly when there's no LaTeX mode available and it's just makeshift with superscript and unicode. – Luc Mar 23 '18 at 10:09
  • Thank you! I'm interested in both. Attacks simply cause accidental collisions to be more likely by adding intelligence to interfere with randomness. – Xeoncross Mar 23 '18 at 17:43
  • I believe your first sentence is incorrect. A secure (unclear if this is what you mean by "perfect") hash function's output ("digest") is deterministic (not random) for any given input, is difficult to generate a preimage for (can't take a digest and produce a message that hashes to that digest), and difficult to produce a collision for (can't find two different messages that have the same digest). However, that does not require that the digest be unpredictable (random)! For example, see en.wikipedia.org/wiki/Length_extension_attack – CBHacking Mar 25 '18 at 7:48
  • @CBHacking I tried to keep it understandable. If you find a hashing algorithm which gives output that does not look like very high entropy (i.e. random bits), it can definitely be broken. By saying "for any unique input" I tried to make clear that it is deterministic, i.e. unique (new) input will give you a new output, and that output is unpredictable in the sense that it looks random (a change in one bit of input, will not give you a chance of one bit in output). I could have phrased it more correctly, but I think that would have been at the cost of length and readability. – Luc Mar 25 '18 at 9:46
2

Any unbroken n-bit cryptographic hash function has a collision resistance of 2n/2. This means that, if you want to have a 2128 collision resistance, you need to use, at minimum, a 256-bit hash function. As 264 operations are achievable, you would not want to use a 128-bit hash. A 160-bit hash (that is, a 280 security level) is borderline. Using a 256-bit hash will give you a 2128 security level, which should be completely fine for the foreseeable future. Sometimes, weaknesses in the hash function itself result in it being easier to break than the output digest would suggest. The SHA-2 family of hashes is one example that is currently unbroken. SHA-1 on the other hand is broken. It has a 160-bit output but "only" a 263 security level against collisions, rather than 280.

I suspect you may be mixing up collision attacks with other types of attacks. A collision attack will not allow an attacker to find input that hashes to an arbitrary value. The formal definitions:

  • Preimage attack - Given h where f(m) = h, find any m' such that f(m') = h.
    "Find input that hashes to an arbitrary value."

  • 2nd preimage attack - Given f(m) = h, find any m' such that m ≠ m' and f(m') = h.
    "Modify an input without changing the resulting hash."

  • Collision attack - Find any pair of m and m' such that m ≠ m' and f(m) = f(m').
    "Find any two inputs that have the same hash."

Each attack has different implications. A collision attack is problematic for certificates, as they can be used in signatures that are valid for both benign and malicious versions of the same software. A preimage attack is problematic for verification. Imagine if an attacker could modify an executable without changing its hash. Clearly, a preimage attack is far more severe than a collision attack, but it is also thankfully far more difficult to pull off. The infamously insecure MD4 algorithm, for example, is so bad at collision resistance that it is cheaper to find a collision than it is to run the hash function itself twice. However, as broken as it is, preimage attacks against it are highly theoretical.

If, on the other hand, you simply want to check for accidental corruption and are not intending to protect against an active attacker, then a CRC with a properly-selected polynomial would be ideal. A CRC can actually guarantee error detection up to a point.

  • 1
    You should probably include the mention that this is when no known weaknesses exist in the hash function. SHA-1 is a 160-bit hash function, but the Shattered Attack took "only" 2^63 operations to find a collision. – David Mar 23 '18 at 15:35

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