Difference between revisions of "Projects/Random Salt Generation"

Latest revision as of 12:26, 22 September 2011

Summary

The idea of this project is to deprecate the notion of "salt type" and generate a random salt for all new principals. Because of the associated complications, there are no resources allocated to the project at this time.

Background

When Kerberos keys are derived from password, they are usually combined with a salt, to prevent attackers from building up a pre-calculated dictionary of keys based on common passwords. The default salt is specified by RFC 4120 as "the concatenation of the principal's realm and name components, in order, with no separators" but the KDC can also provide an alternate salt to the client in an AS-REP. Note that RC4 keys are are an exception; they depend only on the password, not on a salt.

The MIT KDC has an internal concept of "salt types" defined by the DB abstraction layer. A salt type of SPECIAL indicates that the salt is stored in the database alongside the key; other salt types indicate various ways of computing the salt from the principal. NORMAL indicates the default salt, but as of 1.7, the KDC explicitly communicates the salt to the client even if the salt type is NORMAL. Salt types can be determined using enctype:salttype pairs either in the supported_enctypes krb5.conf variable or in the -e option to the add_principal or change_password kadmin commands.

Benefits

Generating random salts for keys has the following benefits:

• Easier principal renaming -- currently when a principal with a computed salt is renamed, the old salt must be computed and stored in the DB entry. This would be unnecessary for principals created with random salts. Of course, the code to compute and store the old salt would still be necessary because of legacy DB entries.
• If a principal is renamed, the stored old value of the default salt would expose the old name of the principal. In general this would not be sensitive information, but in rare cases it might be. Randomly generated salts would avoid this exposure.
• Simpler principal canonicalization -- randomly generated salts avoid any ambiguity when a principal is canonicalized or a key set is shared between multiple canonical principal names.
• Simpler configuration -- without the concept of salt types, supported_enctypes can be a list of enctypes just like the other enctype variables. This would allow supported enctypes to take advantage of the syntax extensions from Projects/Enctype_config_enhancements.

Complications

• Our password history checking currently does not work if the salt changes (except for RC4 keys which are salt-independent); it only compares new keys against old keys. This is arguably a bug; in any event, it would have to be changed to try generating keys with the new password and old salts to match against old keys.
• Although RFC 4120 cautions that "it is not possible to generate a user's key reliably given a pass phrase without contacting the KDC, since it will not be known whether alternate salt or parameter values are required," we have a ktutil command to do so anyway, which assumes the default salt. This would need to be addressed, perhaps by making ktutil acquire credentials to determine the salt.
• Cross-realm TGTs are typically entered into both KDC databases using the same password. If they use different salts, they won't have the same keys, and won't work. This would have to be addressed, perhaps via an option to add_principal to use a fixed salt or the default salt.
• There may also be an issue with the creation of machine and service accounts for Windows, according to http://mailman.mit.edu/pipermail/krbdev/2009-July/007839.html

Salt generation

Salts should use only printable ASCII characters, as they must be transmitted to the client in a KerberosString. (Non-printable ASCII characters are probably okay, but in debugging situations it is convenient to be able to examine salts without resorting to hex conversion.)

Ken Raeburn made the following notes about the length of the salt:

• DES string-to-key uses a fan-fold technique that's likely to make some of the salt bits cancel each other out, depending on the password length; I'd suggest at least 112 bits but you can probably stare at it and figure it out for sure.
• DES3 uses 168-fold, where the efficacy of the mixing is again determined in part by the password length. It's better, but I'm not convinced 168 random bits expanded to a salt string will let you cover the whole possible key space (which I think would be desirable... though I suppose not absolutely required). I looked at it a while back but don't remember the specifics. It may just be that when password+salt has a length that's a multiple of 168 the fixed bits due to use of printable ASCII are just doomed to line up and cut powers of 2 off the possible generated key space.
• AES uses PBKDF2 with SHA-1; that's probably fine with 160 random bits. (Even for a 128-bit key, I'd probably use 160 random bits, to try to get maximum coverage of the output space for a given password before the truncation, but haven't thought about it much. It's not like it couldn't be changed later if more careful analysis determines that 128 random bits are sufficient.)
• Hm.. for DES I take it back -- you don't need 112 random bits, but 16 randomized printable-ASCII bytes; more than that and the non-fixed bits just start getting xor'ed with each other and don't help. You could tune it a bit by looking at the bit-value probabilities for printable ASCII and where they're going to get xor'ed, and see if you can guarantee that at least one of the bits going in has exactly 0.5 probability of being set.
  • After some more contemplation, I think 16 characters where the low four bits are randomly chosen and the upper bits fixed (e.g., 0x40-0x4F), 64 random bits total, after the fan-fold and XOR, may suffice to guarantee complete possible coverage of and flat distribution over the 56-bit intermediate key space; half the bytes will be bit-reversed for the XOR, randomizing the upper bits of the intermediate result, and while we don't know which ones, we can show that for 16 bytes, exactly one will contribute normally and exactly one bit-reversed will contribute to a given byte of the intermediate output. It may be that only, say, the even bytes need four random bits and odd ones can get away with three (because we're reversing and combining 7-bit "bytes"), getting us down to 56 random bits of input, but that should be analyzed more closely to be sure. But, see below re: "whatever" and not caring too much. :-) --KenRaeburn 03:31, 26 July 2009 (EDT)
• (In case it's not clear why I'm thinking about that, consider two-bit values permitted to vary from 0 to 2. Chosen randomly from the range, the low bit has a 2/3 probability of being set. If you xor two of these together, the low bit has a 2*2/3*1/3 = 4/9 probability of being set, giving uneven distribution across the possible resulting 2-bit strings. For printable ASCII, c&0x70 will range from 2-7 and 0x7f will presumably be left out; it's not as skewed as my example, but it's not an even distribution. Then again, DES is being phased out, and choosing 16 bytes randomly from 0x20-0x7e is still a lot better than what we have now, so, whatever.)
• And on the more general salt-length issue, I think I've mentioned it before, but if the salts are big enough to ensure coverage of most or all of the possible key space even with weak passwords, an attacker can't effectively build up dictionaries of common passwords plus all possible salts, or cutting large ranges of possible keys out of a brute-force search. It's probably true that multiplying the work factor by 2**64 or less would be adequate, as long as we can be confident that there aren't classes of salt strings or salt+password combinations that the attacker can handle efficiently for certain cryptosystems (e.g., because certain pairs of bits only influence the result via their xor, making them effectively single bits). Like I already said, the details can be tuned later depending on risk analysis. And sending more bits rather than fewer until the analysis is done doesn't really cost much.