Recover a Lost Secret Salt

by Steve on April 1st, 2019
updated on April 5th, 2019 [current] [orig] [diff]

TL;DR

Run the password KDF with standard salts, no secret salt, and a short salt that is never saved. Recovery is cracking the short salt. Aiming for a day with Argon2d (t=3, p=1, m=256MiB) the short salt is 18 bits. The tag is 4 bits less. Tag is given to the user to rule out wrong salts. Keys are then used in random order with a PAKE (like SPAKE2+EE with blind salt). You can limit the number of PAKE attempts to 50.

What is a secret salt?

For an encrypted cloud service this is a value store on a user's device that is never shared with the server. The secret salt is combined with the user's password and depending on use also a user's id specific to the service (eg [username]@[service name]), a public salt, and/or blind salt. Then key stretched with a password KDF like Argon2. This secret salt prevents a server breach from being able to make password guesses.

A secret salt is sometimes called account key, device key, key file, or secret key. But I like "secret salt" because one it's a salt and two it's a secret.

Recovering a lost secret salt, doesn't that defeat the purpose of a secret salt?

"Yes", but you'll see it's not that practical to guess passwords against this recovery method.

Setting up the recovery method

Establish a client-server encrypted tunnel with the normal login PAKE. Then server generates the blind salt server value and applies it to client's blinded password hash (H(password, user Id, server Id)). Client runs password KDF (password Kdf(password, user Id, server Id, blind Salt, guessing Salt, settings)) and generates three keys: authentication, encryption, and tag. Auth key generates the recovery PAKE data and sends it to the server through the encrypted tunnel. Client now forgets the "guessing Salt". "Guessing salt" is a small salt that is guessed at a later time. "Tag" is a smaller size than the guessing salt. If the tag is smaller than the guessing salt by 4 bits then the only info leakage is being able to rule out at most 1 in about 8,886,111 (e ** 16) passwords. Also you can limit the number of PAKE attempts to 50. Since chances of more than 50 attempts is 1 in about 4.2 trillion.

C<>S: session Key = pake(password, secret Salt, ...)
C:    r = random()
C:    R = H(password, user Id, server Id) ** r
C->S: encrypt(session Key, R)
   S: salt = random()
   S: R' = R ** salt
C<-S: encrypt(session Key, R')
C:    blind Salt = R' ** (1/r)
C:    guessing Salt = random()
C:    auth Key, encryption Key, tag =
          password Kdf(password, user Id, server Id, blind Salt, guessing Salt, settings)
C:    Delete guessing Salt
C:    pake Data = generate Pake Data(auth Key)
C:    encrypted Secret Salt = encrypt(encryption Key, secret Salt)
C->S: encrypt(session Key, (pake Data, tag, encrypted Secret Salt))
   S: Store: salt, pake Data, tag, encrypted Secret Salt

Using the recovery method

User proves identity somehow and service gives the user a recovery token after a day or so of inactivity on the user's account. User sends the recovery token, does the blind salt thing, and server returns the tag. Note the server only does the blind salt once per recovery token. The user then brute forces the guessing salt and keeps the auth and encryption keys of the ones that match the given tag. Once done the client uses recovery token and tries each of the auth keys in random order in a PAKE to the server. Random order prevents an attacker listening to traffic from learning which tag collision is the correct one. On success the server returns the encrypted secret salt through the encrypted tunnel that was just set up from the successful PAKE. User then decrypts secret salt with the associated encryption key. The secret salt is now recovered and the user can login. Once logged in the user should change their password and secret salt.

C->S: Please let me recover "I'm me"
C<-S: OK but come back in a day and I'll give you a token

** Day later **

C:    r = random()
C:    R = H(password, user Id, server Id) ** r
C->S: user Id, R, recovery Token
   S: R' = R ** salt
   S: Revokes recovery Token
C<-S: R', tag, recovery Token 2
C:    blind Salt = R' ** (1/r)
C:    For each guessing Salt
C:      auth Key[guessing Salt], encryption Key[guessing Salt], tag[guessing Salt]
            = password Kdf(password, user Id, server Id, blind Salt, guessing Salt, settings)

** After a day or so of guessing the guessing Salt **

C->S: user Id, recovery Token 2
C:    For each in random order where tag == tag[guessing Salt]
C:      Try session Key = pake(auth Key[guessing Salt])
   S: On successful PAKE
C<-S: encrypt(session Key, encrypted Secret Salt)
C:    secret Salt = decrypt(encryption Key, encrypted Secret Salt)

Password KDF

You should use Argon2id or Argon2d with time=3, parallelism=1, and memory should be high at least 256 MiB and probably 512 MiB if the device has enough memory. Don't worry so much about how long it takes as this is only done once during the set up.

Guessing salt size

Aim for about a day of computation on a new mid range computer. This would currently be dual channel DDR4 and 3GHz 6 core with AVX2. My guess is this will be about 4 guesses/second for Argon2d t=3, p=1, m=256MiB. log2(24*3600*4) is 18.3. So guessing salt size should be 18 bits. For Argon2d t=3, p=1, m=512MiB guessing salt size should be 17 bits. In general log2(24*3600*4*256MiB/m) bits. Don't forget the tag is always 4 bits fewer than the guessing salt. Also DDR5 is expected to be available sometime in 2019 or 2020 and guessing speed will probably double to 8 guesses/second. Thus increasing the guessing salt size by a bit.

Why don't you have the secret salt be small like the guessing salt and forgo the guessing salt?

You can make this recovery method optional. You probably don't want to use Argon2 settings that are this high for the normal login PAKE. Also this is only accessible after going through the time delayed recovery process. On a server breach it acts the same as just using a small secret salt, but should nearly eliminate online guessing vs using a small secret salt.