54

When studying Dan Boneh's slides for 'Session Management and User Authentication' (2011) he mentions 'secret salts' on the slide 'Further defences' (slide 48 out of 58).

He suggest to store in the datbase:

Alice|SA|H(pwA , SA , rA)

In which Alice is the username, SA the salt associated with Alice and H(pwA , SA , rA) the result of hashing Alice's password pwA together with the salt and a small random value rA.

I don't understand why adding a short random value r (8 bits) slows the verification down by a factor of 128 while an attacker is slowed by a factor of 256.

  • Possible duplicate of Why are salted hashes more secure for password storage? – Rоry McCune Dec 6 '16 at 17:21
  • 28
    Not a duplicate, I don't think, since the question is about creating a secret salt specifically. – Xiong Chiamiov Dec 6 '16 at 17:35
  • 22
    This type of salt is called "pepper", because IT naming conventions or something. en.m.wikipedia.org/wiki/Pepper_(cryptography) – StarWeaver Dec 7 '16 at 12:20
  • Can this increase the risk of collision? Say H('abc', SA, 11) = H('xyz', SA, 214). – Bent Dec 7 '16 at 22:26
  • Another thing to point out: an attacker might check all bits meanwhile the software has a tendency to pick low secret salt values. In essence, the factor for an attacker is always 256 whereas the average factor for users is the expected value for the probability distribution of the random secret salt. If it isn't 128 (but in fact lower) you might on average have less of a slowdown. Plus, it won't slow you down much seeing as how you only run the login once whereas an attacker runs it millions of times. – The Great Duck Dec 8 '16 at 6:26
101

This would probably be explained in the auditory lecture that these slides accompany.

My guess is that he's calculating this assuming that users generally enter their correct passwords. You only need to cycle through options for r until you find one that produces a correct hash.

If you've been given the correct password, then you will come across an r that produces a correct hash; when exactly this happens will vary (since it's random), but on average you'll go through half the total options (2**8 = 256, 256/2 = 128) before finding it.

However, the attacker will usually be trying incorrect passwords. This means they'll have to try every single option of r, which is the full 256.

  • 8
    Also, that's for an attacker hitting a single target. If the attacker were trying to go through a whole DB dump they'd be hurting from that extra computation. – d1str0 Dec 6 '16 at 18:36
  • 5
    Wont this create a timing attacks? Since the whole point is that a correct password can be tested faster than a wrong password. – Taemyr Dec 7 '16 at 8:05
  • 3
    That's a good point, and yes, I think it would (although if what you're protecting against is an attack on determining r, you could mitigate that by choosing your r candidates in a randomized order). In most password-cracking scenarios, though, we're talking about an offline attack against a copy of the database, not an online attack that uses the application itself to check authentication. – Xiong Chiamiov Dec 7 '16 at 8:09
  • 28
    @Taemyr A timing attack on what? Testing with the correct password produces the knowledge that the password is correct, anyway. - A timing attack would, in my opinion, only work, if incorrect passwords would be handled faster by the legitimate system, too! But then there would be no knowledge to gain by the attacker, anyway. – Alexander Kosubek Dec 7 '16 at 8:11
  • 4
    One point here is the note about the live system mostly checking correct passwords. There is a failure rate from real users fat-fingering things, as well as active attacks. Since every mistake forces checking the whole 256 set, I would expect that average number of checks per password attempt on the production server to be well above 128... perhaps as high as 150 or even 180, though that's just a guess. It's still better than the near-256 attempts for an attacker, but it won't be the 2:1 ration he proposes. – Joel Coehoorn Dec 8 '16 at 16:27
15

Just to add something more to Xiong's answer:

In case of a database compromise an attacker will try to recover all the passwords (Or at least the most interesting ones), meaning he needs to try each candidate password with each possible "secret salt", which is quite expensive

Meanwhile the server just needs to iterate through the possible "secret salt" with the password entered by the user. Not only the password is likely to be correct, also it's only one for each user login in

  • 2
    That doesn't explain anything about why the secret salt hurts the attacker by a higher factor than it hurts us. – user2357112 Dec 8 '16 at 22:43
  • 1
    How does it not explain it? I explain what the attacker would do to recover a password, how the server verifies it and the difference between both scenarios. If you mean the math behind it and why the attacker is slowed by a factor of 256 and the server by a factor of 128 average, then you should read Xiong's answer as I said at the begining – Mr. E Dec 9 '16 at 15:04
0

In addition to the above:

protection against Rainbow Tables and (Distributed) Bruteforce attacks.

Rainbow tables hold the results of any given hash, meaning if you have one for a given hashing type (sha1 for example). You can just look up the result and 'decrypt' a set of hashes fairly easily. Which does not work if you has blocks of hashes or every individual hash on itself salted.

The same goes for Distributed Bruteforce attacks. If you attempt to reverse engineer/back guess a hash results (using security weaknesses in a hashing algorithm) you can use these to quicken up similar hashes. Using multiple machines (the distributed part) that start looking at a further offset, greatly increases the chance on a hit. If the hit can occur on anywhere on a given range, the chance on a hit greatly increases if you start on multiple offsets at the same time. Plus any discovered hash can again be tested against the other hashes inside the set you are trying to bruteforce.

This is all rendered useless when you salt a hash, as the result is not longer linear, predictable or searchable.

  • 2
    OP is not talking about clasic salts (Which prevent the attacks you mentioned), he's talking about a non-stored random value that the server (Or the attacker) needs to iterate through until some of its values makes the hash match (Correct password + secret value) or the iterator exhausts (Wrong password). Also rainbow tables doesn't hold the result of every hash, instead it stores part of the hash (For example last 32 bits) linked to all the passwords that generate that hash, when the ending part matches the attacker just iterates through the linked passwords until entire hash matches – Mr. E Dec 7 '16 at 14:25
  • Doesn't explain the secret hash (rA) that the question is about. – Tom Dec 9 '16 at 6:17

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.