26

Even though the current recommendation for storing passwords is the usage of a slow key derivation function such as Argon2, scrypt, PBKDF2 or bcrypt1, many websites still use the traditional hash(password + salt) method, with MD5, SHA-1 and SHA-256 being the most commonly used hash functions.

The SHA-1 hash of mySuperSecretPassword123 with the salt !8(L-_20hs is E5D0BEE0300BF17508CABA842084753685781907.

Assume an attacker would steal the salt and the first half of the hash, so E5D0BEE0300BF17508CA. We also assume that the attacker is aware that SHA-1 is being used and how the salt and the password are concatenated.

How difficult would it be for an attacker to recover the original password?


1 bcrypt technically isn't a key derivation function, but for the purposes of this question it functions identically.

  • 4
    This can depend a lot on what the input values can be - I've seen a system using MD5 with the first 3 characters removed, where the input values were 4 digit codes. It was trivial to recover the inputs, even though they were salted and had a 30 second expiry. – Matthew May 31 at 15:39
  • 1
    @Matthew For the sake of this example, it's just regular old passwords. – MechMK1 May 31 at 15:47
  • 1
    FWIW, neither MySuperSecretPassword123 nor MySuperSecretPassword has been found on haveibeenpwned.com/Passwords. However, mysupersecretpassword HAS been found by crackers. It's difficult to give you a real answer of "how long it'd take", since there's just too many factors involved. But I'd say given that someone already found a VERY SIMILAR lowercase version in actual usage, on an actual set of real passwords that this is a poor password that can, and nearly has been cracked by real attackers. – Steve Sether May 31 at 17:35
  • 11
    Why would they steal only half the hash? If they can access half of it, what could possibly prevent them from stealing the entire thing? On the contrary, since the full hash is stored as a single unit (probably a column in the DB), stealing the whole thing is probably less work. – jpmc26 Jun 2 at 0:26
  • 1
    @jpmc26 It's not a practical scenario by any means. I'm not trying to build "MySuperSecureAuthenticationSystem" based on split hashes. I just found it to be very interesting. – MechMK1 Jun 3 at 9:33
51

Actually, it's as bad as a full hash leak.


Hash-cracking is done by:

  1. Generating password candidates
  2. Hashing them
  3. Comparing the resulting hashes to the hash you want to crack

None of those steps will be slower in case of a partial hash leak, so this is very similar to a full hash leak speed-wise.


Please note that if the partial hash output is not long enough, a lot of password candidates will match. In that scenario, you can't know which candidate was the real password.

  • 15
    This is the correct answer. Even if the password inputs were uniformly random, this would be a effectively complete compromise. It's exceedingly improbable that any two candidate passwords would generate a collision in any given 80 bits. Even after a trillion guesses, you have less than a 50% chance of finding two passwords that collide in those 80 bits. But passwords aren't uniformly random; they are overwhelmingly alphanumeric and have very low entropy per bit. A trillion guesses will generate hits for upwards of 95% of your password database. – Stephen Touset May 31 at 18:16
  • @StephenTouset Since the passwords in question are salted, wouldn't that require a trillion guesses per password? Not that it matters in practice since the brute force method is reasonably fast regardless, but it's still an important distinction, I think. – jpmc26 Jun 2 at 0:29
  • 1
    @jpmc26 The OP assumes the salt has been stolen alongside the (partial) hash, so I don't think your distinction applies. – TripeHound Jun 3 at 9:19
  • I am assuming that there is some sort of threshold though? E.g. what if you only have the first quarter of the hash? What if you only have the first letter? – Raphael Schmitz Jun 3 at 9:35
  • @RaphaelSchmitz Eventually it would give you so many candidates that it would be almost as bad as having to guess the hash from start, I guess. But even a small partial hash should narrow the field a bit I'd guess. – Mast Jun 3 at 11:24
14

It depends on how good the password is, and the size of the hash prefix.

Large prefix / bad password

If we assume this is a hash of an average Joe's password which contains say 30 bits of entropy ("mySuperSecretPassword123" almost certainly contains less entropy than this), and to be conservative we follow Kerckhoffs's principle and assume the attacker knows how the password was generated, then there are only 230 possible passwords. If the prefix leaked is 80 bits from a SHA-1 hash, then it is extremely likely that there will be only one password candidate that matches the hash prefix.

Basically, if log2(password space) is smaller than the leaked prefix, you might as well consider the entire hash to have leaked.

Small prefix / good password

What if the prefix is small or the password is good(ish)? Say for example you have a password space of 250, and you've leaked a 40 bit prefix. An attacker can't just crack the password, since there will be around 210 passwords that match the hash, but this is still a problem. 250 is much too large to launch an online attack, even without rate limiting. But if an attacker can pre-filter their guesses to those that match the prefix in an offline attack, they would only need to try 210 in the online attack, which may be feasible.

If log2(password space) - prefix size > 0 then the attacker likely won't be able to crack the exact password, but if it's small enough, they can generate a pool of password candidates for use in an online attack.

Very good password

Of course, if you randomly choose from a password space larger than 2100 (to be conservative) with uniform probability, then leaking a partial or full hash is irrelevant, as it's never going to be cracked anyway.

  • For reference, an English alphanumeric password (lower case English letters, upper case English letters, and digits) of 17 characters has a password space of over 2^101.2. – jpmc26 Jun 2 at 0:33
  • @jpmc26 Assuming it's perfectly random (which should be obvious, but it might not be to some people). – AndrolGenhald Jun 2 at 2:05
  • 1
    ? Password space isn't affected by randomness. That's entropy. I just had trouble figuring out how big 2^100 actually is since we don't typically construct passwords out of an alphabet of 2 characters, so I wanted to put it in more relatable terms. – jpmc26 Jun 2 at 11:52
  • @jpmc26 Password space is affected if the password is not chosen uniformly at random. When you say password space you always assume the passwords are chosen uniformly at random and not, say, from a list which contains a subset of the password space. – Nobody Jun 2 at 19:14
  • 1
    @Nobody Unless I'm mistaken, "password space" is merely the set of all possible passwords given an alphabet and a length. I suppose the space could be constrained in other ways, eliminating some passwords from it, but the space itself is unrelated to the selection of a single password from it. Randomness is therefore irrelevant as there is no selection involved in specifying the space. If you mean something other than the random selection of a password from the space, please use the appropriate terms. – jpmc26 Jun 2 at 19:39
4

If you only have half a 160 bit hash, then that means you have 80 unknown bits. This results in $2^80 = 1.2089258196146292e+24$ possible hashes left.

That means that your password can be hashed to one of those, and that does exponentially reduce the number of possible passwords (2^80 times less), but an attacker CANNOT find your password only based on this, if we assume your password is totally random.

Obviously, that is rarely the case, so if someone was to use a modern dictionary attack that generates the password, they’d probably end up with a relatively small list of probable password. That small list of password could then be tested against the real authentication service to get the precise password.

TLDR:

  • if password is random: Should be ok
  • if password can be generated with a modern dictionary attack (e.g.:smolbanana73): Would recommend changing it.

Note: Have I Been Pwned does ask you for the first few bits of your password to check if it’s in their lists, but it’s small enough that is insignificant.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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