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.

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.
