0
$\begingroup$

I have identified a password hashing algorithm that uses a truncated MD5 hash to compare user passwords.

This means that any password whose hash matches the same first 23 hex chars (11.5 bytes or 92 bits) will authenticate the user.

How big is this keyspace? I believe it is 2^92 which is still quite a large key space to bruteforce a valid password for.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
4
$\begingroup$

Yes, given a random 92-bit string, you will on average need to perform $2^{92}$ MD5 calculations to find a password whose MD5 hash begins with that 92-bit string.

However, if the passwords are not salted before they're hashed, then attacking multiple password hashes in parallel is only slightly less efficient than attacking one hash. Indeed, if you only care about finding one of the passwords, having $n$ different hashes to target actually makes the attack about $n$ times faster.

Also, if the passwords are chosen by users, simply generating and testing strings that resemble common password choices will likely turn up the correct password in far less than $2^{92}$ attempts. While it's possible to generate and memorize a password with 92 bits of entropy*, few people will actually take the time to do that.

(If the hashing scheme is indeed just plain (truncated) MD5, you may also be able to just look up the prefixes in a precomputed table of MD5 hashes of common passwords, several of which can be found online.)

This, not the size of the theoretical keyspace, is the reason for the recommendation to use a key-stretching KDF (like PBKDF2 or scrypt or Argon2) for password hashing. Basically, it doesn't really matter if the hashes are 92 or 128 or 256 or 512 bits long, if the passwords they're computed from only have less than 30 bits of entropy.

*) For example, a seven word Diceware passphrase would have a little over 90 bits of entropy, while adding an eighth word would push it well over 100 bits.

Improve this answer
$\endgroup$
4
  • $\begingroup$ Not OP, but are there any MD5-specific attacks that would be relevant here? $\endgroup$
    – Awn
    Sep 28, 2017 at 15:43
  • 1
    $\begingroup$ @Awn As far as I can tell, no. What you'd need would be a partial preimage attack, and so far there don't seem to be any for MD5. $\endgroup$
    – Ilmari Karonen
    Sep 28, 2017 at 16:28
  • $\begingroup$ In your second paragraph it seems as if you say if the passwords are not salted, you can make the attack n times faster if you have n different hashes. This sounds fine but you also say that it is slightly less efficient? Can you clarify? $\endgroup$
    – deed02392
    Oct 2, 2017 at 10:07
  • 1
    $\begingroup$ @deed02392: It's typically not exactly $n$ times faster, since there's usually some overhead in looking up each candidate hash in a table of $n$ potential matches, as opposed to just doing a simple string comparison. Especially so if $n$ is so huge that you can't fit all the hashes comfortably in memory. But it's still pretty negligible in practice, compared to the $n$-fold speedup. $\endgroup$
    – Ilmari Karonen
    Oct 2, 2017 at 10:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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