6

A system I'm studying uses the following mechanism: a 19-digit integer is hashed via the MD5 algorithm and the salt of the integer is shown in plain sight to the user before they take an irreversible action relevant to trying to guess the first 2 digits of said number.

My intuition is that this is not secure. With 10^19 possible results for each particular implementation and a 2-minute lifetime of a single entry, as well as capabilities of modern GPUs, I just don't feel giving the okay to rolling this out.

I tried to use a hashcat mask bruteforce with a somewhat high-end graphics card off my personal computer give very reassuring results of a time way exceeding two minutes, yet intuition seems to hint at something I'm missing.

Am I?

Rodrigo de Azevedo
  • 242
  • 2
  • 13
Ivan T.
  • 1,053
  • 1
  • 6
  • 12
  • this is related to (in)security of salted MD5 https://security.stackexchange.com/questions/19906/is-md5-considered-insecure – LLub Oct 17 '19 at 11:04
  • This speaks of collision attacks, which the system is safe from. There are no collisions in the range due to MD5 length exceeding salted integer length. – Ivan T. Oct 17 '19 at 11:11
  • I don't get the "trying to guess the first 2 digits of said number"? That's the weak part IMO: just retry this process by using "42" as your guess, and you'll succeed pretty soon (70 tries to have 50% of guessing right at least one time and 500 tries to get below 1% chance of never guessing right). Besides, an offline attack on N consecutive `hash + salt` can give you the N consecutive integers, and *could* be used to recover the pseudo-random-function used (maybe, but way harder than 70 consecutive tries) – Xenos Oct 17 '19 at 15:21
  • *"There are no collisions in the range due to MD5 length exceeding salted integer length."* That doesn't tell you whether a collision exists or not. Hashing 10^19 messages (with or without a salt) puts you in birthday paradox territory for MD5. Rule of thumb says that, for an n-bit hash, collisions are probable after processing 2^(n/2) distinct inputs. (You may find no collisions. You could also find more than one pair of colliding inputs.) MD5 only has 128-bit output and 10 digits is just under 64 bits. – Future Security Oct 20 '19 at 01:59
  • Collisions are not relevant in this case (possibly), though not because of the ease or difficulty of finding a collision. If the only thing the hash is used for is verifying that the number is correct, then the only things you need are pre-image resistance and salting. But ***if you can't tolerate collisions, then MD5 is definitely a bad choice***. Any 128-bit hash would be. MD5 even more so, because it's already weak security claims are broken. (The length of the input is definitely still irrelevant to whether collisions could exist, though.) – Future Security Oct 20 '19 at 02:19
  • Oops. 19 digits, of course. Not 10... – Future Security Oct 20 '19 at 20:10

1 Answers1

9

This very high end GPU cracker performs 200GH/s:

https://gist.github.com/epixoip/a83d38f412b4737e99bbef804a270c40

That's 200 billion hashes per second (2e11 hashes/s). With a search space of 1e19 possible numbers, that means it will take ~500,000 seconds (about 1.5 years) to exhaustively search parameter space. Of course on average you'll find a match in half of that time.

In short, MD5 is a fast algorithm, which normally means brute force is easy. However in this case the large size of your search space negates a lot of that.

Depending on what happens for a successful user though, MD5 still might not be the best choice. A top end hashing rig is too slow by a factor of ~200,000. That seems like a lot, but you're basically asking "How long until my hardware might be 200,000x faster?". While the growth pace of computer hardware has slowed, it's not unrealistic to expect that gap to shrink substantially in just a few years.

Finally, you also have to be concerned about weaknesses in pre-image resistance. I haven't "checked in" on MD5's status in a while, but last I heard MD5 was still pre-image resistant. Other aspects of MD5's cryptographic security have been broken (aka it is no longer collision resistant, although that is not relevant here). Therefore, while MD5 is still pre-image resistant, that could change any day. Without pre-image resistance an attacker might come up with a technique to find a payload that gives the same hash as your number, without having to actually brute-force the number.

In short, you are safe at the moment. The safety margin though is perhaps not that high. Whether or not you need to take action depends on what you are securing on the other side of this.

Conor Mancone
  • 29,899
  • 13
  • 91
  • 96