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.

Xiong Chiamiov
  • 9,384
  • 2
  • 34
  • 76
harm
  • 593
  • 1
  • 5
  • 7
  • Possible duplicate of [Why are salted hashes more secure for password storage?](http://security.stackexchange.com/questions/51959/why-are-salted-hashes-more-secure-for-password-storage) – Rory McCune Dec 06 '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 06 '16 at 17:35
  • 22
    This type of salt is called "pepper", because IT naming conventions or something. https://en.m.wikipedia.org/wiki/Pepper_(cryptography) – StarWeaver Dec 07 '16 at 12:20
  • Can this increase the risk of collision? Say H('abc', SA, 11) = H('xyz', SA, 214). – Bent Dec 07 '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. – user64742 Dec 08 '16 at 06:26

3 Answers3

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.

Xiong Chiamiov
  • 9,384
  • 2
  • 34
  • 76
  • 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 06 '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 07 '16 at 08: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 07 '16 at 08: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 07 '16 at 08:11
  • 1
    To be precise, the average slowdown factor for correct passwords is (1+256)/2 = 128.5, because you do have to try at least one (and at most 256) secret salts to find the correct one. Of course, for an 8-bit secret salt, the difference between 128 and 128.5 is negligible, but it's the reason why you can't reduce the secret salt length to, say, 1 bit (or even 0 bits!) and still get the same benefit. – Ilmari Karonen Dec 07 '16 at 14:00
  • 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 08 '16 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

Community
  • 1
Mr. E
  • 1,954
  • 9
  • 18
  • 2
    That doesn't explain anything about why the secret salt hurts the attacker by a higher factor than it hurts us. – user2357112 Dec 08 '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 09 '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.

RC NL
  • 9
  • 4
  • 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 07 '16 at 14:25
  • Doesn't explain the **secret** hash (rA) that the question is about. – Tom Dec 09 '16 at 06:17