The SSHA Password Storage Scheme

In an earlier post I discussed the various mechanisms that we have in place for protecting passwords in the Directory Server. One of the forms of protection that we provide comes in the form of password storage schemes, and the default and most secure storage scheme currently included is the SSHA scheme. This is a salted version of the SHA-1 message digest algorithm, and it provides a level of protection against dictionary attacks.

One-way message digest algorithms like SHA-1 and MD5 are intentionally designed so that it's not possible to determine the original cleartext value from the hash value. However, they are also designed so that the same cleartext always hashes to exactly the same digest. Therefore, if I know that the cleartext "password" always generates a base64-encoded SHA-1 hash of "W6ph5Mm5Pz8GgiULbPgzG37mj9g=", then every time I see that encoded value, I know that the cleartext value was "password". If I create a dictionary of pre-hashed values that maps to them to the cleartext used to generate the hashes, I can use that to help me quickly break any commonly-used passwords.

The introduction of a salt into the encoding process is enough to render precomputed dictionaries useless. It works by adding a random element to the digest process so that a given cleartext value does not always generate the same encoded value. If I use SSHA to encode the cleartext "password" five times, then I wil get five different encoded values. In fact, because we use a 64-bit salt there are 18,446,744,073,709,551,616 different ways of encoding the same clear-text value. This makes creating a dictionary completely infeasible because of the sheer volume that would be required to hold even all encodings for a single value.

I've previously stated that there is no reason for a client to know how passwords are encoded in the server, and I stick by that. Any client that attempts to verify passwords externally is broken, since it can't abide by the configured password policy, and because it will stop working if the storage scheme is changed in the future. Similarly, allowing applications to pre-encode passwords before sending them to the server can also bypass password policy restrictions. Nevertheless, we frequently find that people are curious as to exactly how SSHA works, so I'll describe it here for informational purpopses only.

The algorithm that we use is actually very simple:
  1. Generate eight bytes of random data to use as the salt
  2. Append the salt bytes to the bytes that make up the cleartext password
  3. Generate the SHA-1 digest of the password+salt
  4. Append the salt bytes to the SHA-1 digest
  5. Base64-encode the resulting digest+salt bytes and append that to the string "{SSHA}"

When a user attempts to bind to the Directory Server, the server validates the clear-text password provided by the user in the following way:
  1. Get the encoded password from the user's entry
  2. Read the string inside the curly braces and use it to determine which password storage scheme was used to encode the password (in this case, we'll assume it was "SSHA")
  3. Remove the "{SSHA}" prefix and base64-decode the remaining value
  4. Remove the last eight bytes from the decoded value to use as the salt
  5. Append the salt to the clear-text password from the bind request
  6. Generate the SHA-1 digest of the password+salt and compare it against the password+salt portion (i.e., all but the last eight bytes) from the base64-decoded value found in step #4

To better illustrate this process, I've created a very simple Java class that can be used to either encode a clear-text password using SSHA or compare a given clear-text password with an encoded password to determine whether it is valid. It should be self-contained and thoroughly commented, so it may help illustrate the steps outlined above in a more programmatic manner.

Comments:

Post a Comment:
Comments are closed for this entry.
About

cn_equals_directory_manager

Search

Top Tags
Categories
Archives
« April 2014
SunMonTueWedThuFriSat
  
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
   
       
Today