1

Im doing a research assignment at Uni where i am investigating hash functions.

With SHA1 and (from what i can understand) all hash techniques there is (incredibly rarely) hash collisions. See here

Can anyove give me a figure of how likely a hashing collision occurs in NTLMv2 (used in windows 7)?

Thanks

Tom

Community
  • 1
  • 1
Tom
  • 11
  • 2
  • Probability of collisions happen randomly, or how often an attacker needs to try to get one? – CodesInChaos Dec 03 '10 at 16:05
  • Hi CodeInChaos, the probability of collisions happening randomly would be great. I know NTLMv2 uses 3 MD4 functions to achieve the hash. – Tom Dec 03 '10 at 16:17
  • And why are you interested in collisions of password hashes? That's quire irrelevant in practice. What's interesting is a pre-image attack. – CodesInChaos Dec 03 '10 at 19:31
  • Thanks for clearing things up CodeInChaos. All i was looking for is a figure to demonstrate how incredibly rare random collisions happen. Thanks Again – Tom Dec 07 '10 at 22:38

1 Answers1

1

NTLMv2 is an hmac-md5 implementation. It should be noted that collisions do not affect HMACs. In order for an attacker to generate a collision for an md5 has a complexity of (2^24.1)/2=2^23.1, however i don't believe such an attack can be mounted against NTLMv2. So iI believe the answer is (2^128)/2=2^127. This number is thinking of md5 as an ideal message digest function, and of course no such ideal function can exist.

Division by 2 is done to account for the birthday paradox.

rook
  • 66,304
  • 38
  • 162
  • 239
  • Just clarifying/extending what you said: The probability is 1/2^128 for two different inputs to have the same hash, but you only need about 2^64 hashes to get a collision(see birthday paradox) – CodesInChaos Dec 03 '10 at 19:34
  • @CodeInChaos Aaah yes you are correct about accounting for the birthday paradox. However, your math is incorrect, 1/2^128 is a very small decimal. But in fact the probability should be 1/2 of the total. – rook Dec 03 '10 at 20:30
  • What do you mean by 1/2 total? Birthday paradox doesn't divide the possibilities by half, but the bits. Since you need about Sqrt(x) hashes so for x=2^128 you need sqrt(x) = Sqrt(2^128) = 2^(128/2)=2^64 hashes. But that Sqrt is only an approximation, and you need to be able to keep 2^64 hashes saved. – CodesInChaos Dec 03 '10 at 20:47
  • @codeinchaos I still think its the 50% mark unless you have a link to back your statement. Also (1/2)^128=.00000000000000000000000000000000000000293873588. – rook Dec 03 '10 at 21:45
  • @Rook: your own link shows that it is the square root that approximates the number of hashes that need to be saved until a collision is found. – President James K. Polk Dec 04 '10 at 00:02
  • @GregS I am sorry but i do not see a square root, However I see the combinatorial 23c2. Could you be more specific. – rook Dec 04 '10 at 04:27
  • Hi everyone, thanks for your comments. Just to clarify, im not looking for the minimum required for an attack, just an indication of how unlikely a collision would happen 'out in the wild'. Thanks Again – Tom Dec 07 '10 at 22:49
  • @Tom Okay the answer is never even after many millions of years. – rook Dec 07 '10 at 22:50
  • @Rook Fair enough, Thanks Rook – Tom Dec 09 '10 at 11:38