This provides a long overdue update to "Password Hash" from the Enigma Prequels (2007), where that article neglected to add salt, which is embarassing for whoever wrote that article... which was unfortunately me.

https://github.com/evanx/vellum/wiki

Password Salt: The first part of a hashed cryptrilogy, part of "The Enigma Posts"

General hashing algorithms (eg, MD5, SHA) are not recommended for password storage. Instead an algorithm specifically designed for the purpose should be used such as bcrypt, PBKDF2 or scrypt.
bcrypt is a key derivation function for passwords based on the Blowfish cipher.
PBKDF2 (Password-Based Key Derivation Function 2) is a key derivation function that is part of RSA Laboratories' Public-Key Cryptography Standards (PKCS) series.
PBKDF2 applies a pseudorandom function to the input password along with a salt value, and repeats the process many times.
Having a salt added to the password reduces the ability to use precomputed hashes (rainbow tables) for attacks.
A password-based key derivation function (password-based KDF) is generally designed to be computationally intensive, so that it takes a relatively long time to compute (say on the order of several hundred milliseconds).
Legitimate users only need to perform the function once per operation (e.g., authentication), and so the time required is negligible.
However, a brute force attack would likely need to perform the operation billions of times at which point the time requirements become significant and, ideally, prohibitive.

If each password is simply hashed, identical passwords will have the same hash. This has two drawbacks:
1. Due to the birthday paradox (http://en.wikipedia.org/wiki/Birthday_paradox), the attacker can find a password very quickly especially if the number of passwords in the database is large.
2. An attacker can use a list of precomputed hashes (http://en.wikipedia.org/wiki/Rainbow_table) to break passwords in seconds.
In order to solve these problems, a salt can be concatenated to the password before the digest operation.
A salt is a random number of a fixed length. This salt must be different for each stored entry. It must be stored as clear text next to the hashed password.
In this configuration, an attacker must handle a brute force attack on each individual password. The database is now birthday attack and rainbow crack resistant.
Note that the sources, erm, "quoted" above, have been surreptitiously paraphrased in some places, to improve readability to suit ourselves ;)

#### Base64

Since we store password hashes and their salts in an SQL database, we encode those bytes into text using Base64. For convenience, we introduce methods which delegate to our Base64 codec of choice e.g. from Apache commons, or the built-in Sun one.
import sun.misc.BASE64Decoder;
import sun.misc.BASE64Encoder;

public class Base64 {

public static String encode(byte[] bytes) {
return new BASE64Encoder().encode(bytes);
}

public static byte[] decode(String string) {
try {
return new BASE64Decoder().decodeBuffer(string);
} catch (Exception e) {
throw new RuntimeException(e);
}
}
}
Actually Apache Commons Codec is a better choice as the Sun one gives compilation warnings to the effect that the "sun.misc.BASE64Decoder is a Sun proprietary API and may be removed in a future release." But we take that with a pinch of salt, so to speak.

#### Psuedo salt

We read about SecureRandom vs Random on infosecinstitute.com, whilst enjoying Dilbert's comic RNG :) So apparently we must use SecureRandom to generate our salt, and not java.util.Random
public static final int SALT_LENGTH = 16;

public static byte[] nextSalt() {
byte[] salt = new byte[SALT_LENGTH];
SecureRandom sr = SecureRandom.getInstance();
random.nextBytes(salt);
return salt;
}
}
where our salt is a 16 byte random number. Sooo easy :) Let's immerse in Base64 salts.
@Test
public void testSaltEncoding() throws Exception {
String encodedSalt = Base64.encode(saltBytes);
System.out.println(encodedSalt);
assertEquals(encodedSalt.length(), 24);
assertEquals(encodedSalt.substring(22, 24), "==");
}
r2tWqOrfKpr64rpOwoRlcw==
So apparently a 16 byte array encoded with Base64 yields a 22 character string followed by two characters of padding. Sold!

When the user chooses a new password, we generate some salt for this specific password, and hash them together. The OWASP example presents an SQL credential table with the following columns:
SALT VARCHAR (32)

#### Crypto parameters

So let's try PBKDF2. We'll leave Bcrypt and Scrypt for another day. (Your opinions on these options, parameters and what-not, are invited, so please come to the party!)
public static final String ALGORITHM = "PBKDF2WithHmacSHA1";
public static final int ITERATION_COUNT = 8192;
public static final int KEY_SIZE = 160;

throws GeneralSecurityException {
}

int iterationCount, int keySize) throws GeneralSecurityException {
PBEKeySpec spec = new PBEKeySpec(password, salt, iterationCount, keySize);
SecretKeyFactory factory = SecretKeyFactory.getInstance(ALGORITHM);
return factory.generateSecret(spec).getEncoded();
}
...
where we give a PBEKeySpec to a SecretKeyFactory specified with thePBKDF2WithHmacSHA1 algorithm. Let's test that this salting, hashing and matching actually works.
@Test
public void test() throws Exception {
byte[] otherSaltBytes = Arrays.copyOf(salt, salt.length);
otherSaltBytes[0] ^= otherSaltBytes[0];
}
where we use the following method to authenticate a supplied password, having retrieved the hash and salt from our database.
...
byte[] salt) throws GeneralSecurityException {
}

byte[] salt, int iterationCount, int keySize)
throws GeneralSecurityException {
iterationCount, keySize));
}
}
where we must specify the PBKDF2 parameters used to create the hash in the first place. Note that we use char[] so that provided passwords can be cleared from memory, e.g. usingArrays.fill() to zero the char array.

#### Computational effort

According to the aforecited OWASP Password Storage Cheat Sheet
You should measure the time required and make sure that it's as large as possible without providing a significantly noticeable delay when your users authenticate.
Perhaps the time required to hash the password should be less than 100ms for consumer sites? And in the case of secure admin sites, a tad longer?
@Test
public void testEffort() throws Exception {
long startMillis = System.currentTimeMillis();
System.out.println("time " + Millis.elapsed(startMillis));
if (Millis.elapsed(startMillis) < 10) {
System.out.println("Ooooooo.... i'm not sure");
} else if (Millis.elapsed(startMillis) > 500) {
System.out.println("Mmmmmmm.... i don't know");
}
}
Given that CPU power is increasing every year, surely we need a dynamic solution where we can revise the parameters at a future date? So let's extend OWASP'sSQL credential table to include the PBKDF2 parameters.
SALT VARCHAR (32),
PBKDF2_ITERATION_COUNT INTEGER,
PBKDF2_KEY_SIZE INTEGER,
This would facilitate rehashing passwords on-the-fly to higher parameters when a user logs in and their actual password is thus on hand. This will be presented in the upcoming sequel entitled "Password Rehash" :)

#### Secret salt

According to the oft aforementioned OWASP Password Storage Cheat Sheet
An additional password storage defense mechanism involves storing the salt in a different location than the password hash.
Use of the server's filesystem is one commonly used mechanism for salt isolation, assuming the password hashes are stored in a different location such as a database.