Password Salting Methods

[Ken Raeburn]

On May 29, 2008, at 22:22, Michael B Allen wrote:
> Is there a reference anywhere that outlines the different password
> salting methods used by different KDCs?

There are RFCs 3961, 3962, and 4757, which outline how salt strings  
are incorporated in the string-to-key conversion function for each  
cryptosystem.  RC4 ignores it, the others actually use it.

How the salt string is determined is separate.

According to RFC 4120, the default salt string is generated by joining  
the realm and principal components without separators.  If another  
string is to be used, it must be indicated by some sort of preauth  
data like ETYPE-INFO2.

The MIT KDC has support for some specific variations on salt strings,  
such as using only the realm, only the principal name without the  
realm, "v4" (i.e., no salt string at all, or rather an empty string),  
and "special" (a string stored in the principal record in the database  
with the key).

Using the principal name as a salt string makes it more difficult for  
an attacker to precompute a dictionary of keys derived from a  
dictionary of pass phrases.  Instead of generating a single complete  
dictionary, the attacker must pick a principal name (more to the  
point, a specific salt string) to use in the dictionary generation.   
Or, the attacker could multiply the pass phrase dictionary size by a  
set of principal names (salt strings) to be attacked, which increases  
the work to be done by that multiplier.

Someday I'd like to see us have a flag in the database to indicate  
that random salt strings should be generated at every password  
change.  Then even if a user keeps picking passwords that are in the  
attacker's dictionary, a dictionary built based on one salt string  
will be useless as soon as the password is changed.  It probably would  
help to make them long, with comparable random bits to the key size  
itself, rather than a set of short alphanumeric strings as usernames  
often are.  Then the distribution of password-generated keys, over a  
large set of users and password changes, is spread out over the entire  
key space.  Someday....

Anyways, the enctype specification for the MIT KDC also indicates the  
salt type to use for each, when creating principal entries or changing  
passwords.

> AFAICT AD w/ RC4 doesn't actually use a salt. Heimdal seems to just
> use the realm and principal name concatenated together without any
> separators.

Right, that's the RC4 behavior, and the default salt as specified in  
the protocol.

> What does MIT do?

As above...

> What does Windows 2008 w/ AES use?
> Windows 2000?

I can't tell you for sure offhand, but I would assume it probably  
either uses the default per RFC 4120, or sends ETYPE-INFO(2) to  
indicate no salt string is used.

> Do the salt values change depending on the enctype?

The default is protocol-wide.  However, the database could store  
different salt strings for different encryption types.

I'd have to think a bit to figure out if it's valid for the database  
to have different salts for a single encryption type, with the KDC  
randomly choosing between them.  I don't know if that would break any  
interesting assumptions that client software might reasonably make.

> I'm interested in knowing to what degree salts can be predicted given
> only the information a client preparing to issue an AS-REQ would have.

Obviously you can guess that it'll use the default...  You could also  
cache the value from the previous time.

Ken