4.1. Salt

4.1. Salt

A salt in password-based cryptography has traditionally served the purpose of producing a large set of keys corresponding to a given password, one of which is selected at random according to the salt. An individual key in the set is selected by applying a key derivation function KDF, as

DK = KDF (P, S)

where DK is the derived key, P is the password, and S is the salt. This has two benefits:

1. It is difficult for an opponent to precompute all the keys, or even the most likely keys, corresponding to a dictionary of passwords. If the salt is 64 bits long, for instance, there will be as many as 2^64 keys for each password. An opponent is thus limited to searching for passwords after a password-based operation has been performed and the salt is known.

2. It is unlikely that the same key will be selected twice. Again, if the salt is 64 bits long, the chance of "collision" between keys does not become significant until about 2^32 keys have been produced, according to the Birthday Paradox. The fact that collisions are unlikely addresses some concerns about interactions between multiple uses of the same key that may arise when using some encryption and authentication techniques.

In password-based encryption, the party encrypting a message can gain assurance that these benefits are realized simply by selecting a large and sufficiently random salt when deriving an encryption key from a password. A party generating a message authentication code can gain such assurance in a similar fashion.

The party decrypting a message or verifying a message authentication code, however, cannot be sure that a salt supplied by another party has actually been generated at random. It is possible, for instance, that the salt may have been copied from another password-based operation in an attempt to exploit interactions between multiple uses of the same key. For instance, suppose two legitimate parties exchange an encrypted message, where the encryption key is an 80-bit key derived from a shared password with some salt. An opponent could take the salt from that encryption and provide it to one of the parties as though it were for a 40-bit key. If the party reveals the result of decryption with the 40-bit key, the opponent may be able to solve for the 40-bit key. In the case that 40-bit key is the first half of the 80-bit key, the opponent can then readily solve for the remaining 40 bits of the 80-bit key.

To defend against such attacks, either the interaction between multiple uses of the same key should be carefully analyzed, or the salt should contain data that explicitly distinguishes between different operations. For instance, the salt might have an additional, non-random octet that specifies whether the derived key is for encryption, for message authentication, or for some other operation.

Based on this, the following is recommended for salt selection:

1. If there is no concern about interactions between multiple uses of the same key (or a prefix of that key) with the password-based encryption and authentication techniques supported for a given password, then the salt may be generated at random and need not be checked for a particular format by the party receiving the salt. It should be at least eight octets (64 bits) long.

2. Otherwise, the salt should contain data that explicitly distinguishes between different operations and different key lengths, in addition to a random part that is at least eight octets long, and this data should be checked or regenerated by the party receiving the salt. For instance, the salt could have an additional non-random octet that specifies the purpose of the derived key. Alternatively, it could be the encoding of a structure that specifies detailed information about the derived key, such as the encryption or authentication technique and a sequence number among the different keys derived from the password. The particular format of the additional data is left to the application.

Note: If a random number generator or pseudorandom generator is not available, a deterministic alternative for generating the salt (or the random part of it) is to apply a password-based key derivation function to the password and the message M to be processed. For instance, the salt could be computed with a key derivation function as S = KDF (P, M). This approach is not recommended if the message M is known to belong to a small message space (e.g., "Yes" or "No"), however, since then there will only be a small number of possible salts.