55

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.

Improve this question
5
  • Possible duplicate of Why are salted hashes more secure for password storage?
    – Rory McCune
    Dec 6, 2016 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, 2016 at 17:35
  • 22
    This type of salt is called "pepper", because IT naming conventions or something. en.m.wikipedia.org/wiki/Pepper_(cryptography)
    – Weaver
    Dec 7, 2016 at 12:20
  • Can this increase the risk of collision? Say H('abc', SA, 11) = H('xyz', SA, 214).
    – Bent
    Dec 7, 2016 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.
    – user64742
    Dec 8, 2016 at 6:26

3 Answers 3

Reset to default
100

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.

Improve this answer
6
  • 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, 2016 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, 2016 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, 2016 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.
    – I'm with Monica
    Dec 7, 2016 at 8:11
  • 5
    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, 2016 at 16:27
14

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

Improve this answer
2
  • 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, 2016 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, 2016 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.

Improve this answer
2
  • 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, 2016 at 14:25
  • Doesn't explain the secret hash (rA) that the question is about.
    – Tom
    Dec 9, 2016 at 6:17

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .