Time-Hard Password Hashing in Java

Overview

So, you want to write your web application using, for example, Java, and you want to store user's credentials?

Well, standard is to hash them with bcrypt or scrypt and a random salt which is unique to each user. But, how do they actually work? Today, we'll cover hash stretching.

Any source code in this article is instructional only, use the real scrypt in production!

Onto The Rack

As mentioned above, what you should be doing is hashing the password with (for example) bcrypt and a really good unique salt. Here's a method for stretching the hash of a user's pass phrase.

The plan is to repeatedly hash the user's password and hash so that to get the user's password, they have to do a very specific (read, high) amount of work.

public class StretchedHash {
  private MessageDigest hash;

  public StretchedHash(MessageDigest hash) {
    assert hash != null : "You cannot stretch a user's password with a null hashing algorithm.";
    this.hash = hash;
  }

  public void hash(String password, String salt, Integer stretch) {
    assert stretch > 0 : "You cannot negatively stretch the hash of credentials";
    // We use funny concatenation to force a one-to-one mapping.
    byte[] digestBytes = hash.digest((salt.length().toString() +
                                      password + salt).getBytes());
    for (i = 0; i < Math.pow(2,Double.valueOf(stretch)); i++) {
      digestBytes = hash.digest(digestBytes);
    }
    return new BigInteger(digestBytes).toString(16);
  }
}

Problems?

This solution does not actually guard against GPUs very well. SHA-512 has a very small memory foot print, and so can be farmed out to GPUs nicely. Even stretching the hash doesn't help that much, the hashes can still be checked very, very fast on a rig with a few GPUs.

Even worse, many hashing algorithms (e.g. SHA1) is very small in hardware, meaning that it is trivial to implement several on an FPGA, or have them fabricated in custom silicon.

The way to make this better is to force it to require multi-megabyte amount of RAM. But not only that, this requirement should go up as time goes on -- just like the amount of CPU time required should go up.

This makes the problem evident. You are buying servers to serve your application to honest users. Your attacker is specialising in one thing: Getting your user's credentials. Unless you specialise your hardware to defend well, you're always going to be at a disadvantage.

In my opinion, shared secrets (i.e. passwords) is a soon-to-be-dead form of authentication, as there are just too many vectors of attack, and the end user will often re-use the same shared secrets for different services. People are bad at strong authentication.