5 ms·

> A "salt" is a small random value used to vary KDF output with the same password input. No salt means that any two users with the same passphrase will have the

by jules 14y ago

> A "salt" is a small random value used to vary KDF output with the same password input. No salt means that any two users with the same passphrase will have the same KDF output. Where would you get this salt from on the client side? That salt has to be the same every time a user tries to access their data from a different computer, otherwise you wouldn't be able to decrypt your files with the derived key right? So how is this salt magically transferred from one computer to another? The alternative is that you get the salt from the server along with the encrypted file, but then I don't see how that improves security. Or perhaps what I'm saying here is pure nonsense, in that case I'd very much appreciate a clarification.

zcid 14y ago
In this case, I believe the [server provided] salt would be used solely as a precaution against rainbow tables, but there may be additional benefits of which I am unaware.
rarrrrrr 14y ago
Great question. In the recommendations, we're suggesting using two salts. One for deriving the key, and one just for challenges. Both of them are stored plaintext on the server. The salt itself does not need to be kept secret -- it's purpose is just to mitigate pre-computation attacks on the password and the resulting derived key. Both salts are created by the client from random data at the time the account is created, and saved to the server. So when a user wants to authenticate, you can just give them the plaintext of the challenge salt along with the issued challenge. There's no harm since it's just random data and shouldn't help them to calculate an answer to the challenge if they don't know the pass phrase. (Note that you only give them the challenge salt, not both salts.) If you want the server to avoid disclosing the existence/non-existence of an account with a particular name (wise!) then just give them a made up random string as a challenge for non-existent accounts. Cache it somewhere so you can be consistent. Always rate limit login attempts. Hope that makes more sense. :)
- jules 14y ago
  It does so far, and I see how this does no harm (as you say), but I also don't see how it improves security? Can you give an attack that would work against the unsalted system which wouldn't work against the salted system?
  - jfarmer 14y ago
    Without a salt one can pre-compute all the KDF (input, output) pairs and store them in a dictionary (essentially). This single dictionary now acts as a kind of master key. By including a random per-user salt, even assuming the attacker has access to the salt, the output of the KDF now varies on both a per-user and per-password basis. Two users with the same password have different keys under this design, so pre-computing something that works for all users becomes infeasible. If the KDF is weak in other ways, e.g., it is so fast that one doesn't need to pre-compute anything, that's a separate issue.
    - jules 14y ago
      I see, so the conditions for this attack are: 1. You have a whole bunch of encrypted files from different users. 2. The KDF is slow compared to checking if decryption with a given output of the KDF is successful. With a salt this will take time nm(T + Q) where n is the number of files, m is the number of different passwords and T is the time it takes to execute the KDF and Q is the time it takes to try to decrypt with a derived key. Without a salt you can amortize the KDF executions for a total time of mT + nmQ. In particular it doesn't help you decrypt one specific file, and the total time is still on the order of n*m, so unless Q is very cheap compared to T this won't help much (obviously still a good idea to do the salting though).
      - jfarmer 14y ago
        I think you're confusing encryption and KDFs. Encryption is meant to be reversible, KDFs are not. In this context, a KDF is used for verifying that a message is valid. I have a derived key, you give me a key, and I verify that key by running it through the KDF. If KDF(your_key) == derived_key then we have "proven" that your_key is valid. Another way of thinking about it is that the image of a KDF should map low-entropy input to high-entropy output. Depending on what we're using the KDF for, we might also want it to have other properties, e.g., intentionally slow, intentionally memory intensive, etc. This is different than you encrypting something, sending me the encrypted message, and me decrypting it using a shared secret. http://en.wikipedia.org/wiki/Key_derivation_function http://en.wikipedia.org/wiki/Key_derivation_function http://en.wikipedia.org/wiki/Rainbow_table http://en.wikipedia.org/wiki/Rainbow_table

by jules 14y ago

zcid 14y ago

In this case, I believe the [server provided] salt would be used solely as a precaution against rainbow tables, but there may be additional benefits of which I am unaware.

rarrrrrr 14y ago

Great question. In the recommendations, we're suggesting using two salts. One for deriving the key, and one just for challenges. Both of them are stored plaintext on the server. The salt itself does not need to be kept secret -- it's purpose is just to mitigate pre-computation attacks on the password and the resulting derived key. Both salts are created by the client from random data at the time the account is created, and saved to the server. So when a user wants to authenticate, you can just give them the plaintext of the challenge salt along with the issued challenge. There's no harm since it's just random data and shouldn't help them to calculate an answer to the challenge if they don't know the pass phrase. (Note that you only give them the challenge salt, not both salts.) If you want the server to avoid disclosing the existence/non-existence of an account with a particular name (wise!) then just give them a made up random string as a challenge for non-existent accounts. Cache it somewhere so you can be consistent. Always rate limit login attempts. Hope that makes more sense. :)

jules 14y ago
It does so far, and I see how this does no harm (as you say), but I also don't see how it improves security? Can you give an attack that would work against the unsalted system which wouldn't work against the salted system?
- jfarmer 14y ago
  Without a salt one can pre-compute all the KDF (input, output) pairs and store them in a dictionary (essentially). This single dictionary now acts as a kind of master key. By including a random per-user salt, even assuming the attacker has access to the salt, the output of the KDF now varies on both a per-user and per-password basis. Two users with the same password have different keys under this design, so pre-computing something that works for all users becomes infeasible. If the KDF is weak in other ways, e.g., it is so fast that one doesn't need to pre-compute anything, that's a separate issue.
  - jules 14y ago
    I see, so the conditions for this attack are: 1. You have a whole bunch of encrypted files from different users. 2. The KDF is slow compared to checking if decryption with a given output of the KDF is successful. With a salt this will take time nm(T + Q) where n is the number of files, m is the number of different passwords and T is the time it takes to execute the KDF and Q is the time it takes to try to decrypt with a derived key. Without a salt you can amortize the KDF executions for a total time of mT + nmQ. In particular it doesn't help you decrypt one specific file, and the total time is still on the order of n*m, so unless Q is very cheap compared to T this won't help much (obviously still a good idea to do the salting though).
    - jfarmer 14y ago
      I think you're confusing encryption and KDFs. Encryption is meant to be reversible, KDFs are not. In this context, a KDF is used for verifying that a message is valid. I have a derived key, you give me a key, and I verify that key by running it through the KDF. If KDF(your_key) == derived_key then we have "proven" that your_key is valid. Another way of thinking about it is that the image of a KDF should map low-entropy input to high-entropy output. Depending on what we're using the KDF for, we might also want it to have other properties, e.g., intentionally slow, intentionally memory intensive, etc. This is different than you encrypting something, sending me the encrypted message, and me decrypting it using a shared secret. http://en.wikipedia.org/wiki/Key_derivation_function http://en.wikipedia.org/wiki/Key_derivation_function http://en.wikipedia.org/wiki/Rainbow_table http://en.wikipedia.org/wiki/Rainbow_table