A message digest is simply a one-way cryptographic hash of a message. In theory, the results cannot be reversed; i.e., retrieving the message from the hash (hence, this is not a form of encryption, but a check). Message digests are commonly used to, e.g., sign messages, validate downloads, and protect passwords (in legacy instances – for the current NIST approved approach, see Secure password hashing). In this post, we will follow the latter.
In addition to hashing the message, we “salt” it with user-specific, random bytes. Adding a salt increases the cryptographic strength of the message by appending or intermixing additional characters. Upon account generation, each user should be assigned a random salt that is then stored with their credentials. While a global salt is better than none, once a single message is broken (a computationally intensive task), one can easily extract the salt, thus reducing the complexity of future attacks. The following will illustrate this process:
Let salt s be jI&6 – an 8-byte sequence (4 Java chars). This adds 264 bits of strength to any message (if we assume ASCII only, then every other byte will be zero, effectively adding only 232 bits of strength). Let message m be a password with value password – an easy one to crack using, in this case, as simple dictionary attack. Assuming an appended salt, the new message ms is passwordjI&6, which is very difficult to crack with brute force.
So how does this decrease the likelihood of hash reversion (i.e., guessing a message by converting textual attempts to hashes and comparing until a match is found)? Simple, it considerably increases the difficulty of guessing that message. In a basic brute force attack, the complexity would increase from 268 = 208,827,064,576 (assuming we know the message is of length 8 and composed of all lower-case characters) to 9512 = 540,360,087,662,636,962,890,625 (12 characters composed of lower, upper, number, and special character sets). If a message were previously broken and the global salt extruded, the complexity would return to it original value. However, if each user is assigned a unique salt, cracking one message will not assist is breaking others.
Another common tool for cracking hashes are rainbow tables. These tables, essentially, pre-compute message-hash pairs to attack common algorithms (e.g., MD5 and SHA-1). Adding a salt makes this process far more challenging because the rainbow tables will have to be incredibly large (TBs-PBs) to accommodate the complexity.
import java.io.UnsupportedEncodingException;
import static java.lang.System.err;
import static java.lang.System.out;
import java.security.MessageDigest;
import java.security.NoSuchAlgorithmException;
import java.security.SecureRandom;
import java.util.Arrays;
import java.util.Base64;
import java.util.HashMap;
import java.util.Random;
/**
* Message digest class.
* @author Ray Hylock
*/
public class MD {
// temporary users for this example - use database in production
private HashMap<String, User> users = new HashMap<String, User>();
private static final int SALT_BYTES = 32;
/** Java 7+ compliant message digest algorithms. */
public static enum Algorithms {
MD2("MD2"), MD5("MD5"), SHA1("SHA-1"), SHA256("SHA-256"),
SHA384("SHA-384"), SHA512("SHA-512");
String name;
Algorithms(String algorithm){ name = algorithm; }
}
/** Constructor. */
public MD(){}
/**
* Adds a user to the system.
* @param username username
* @param password password
* @param algorithm hashing algorithm from {@link Algorithms}
*/
public void addUser(String username, String password, Algorithms algorithm){
if(users.containsKey(username)) err.println("The user already exists.");
else {
byte salt[] = randomSalt();
byte hash[] = getMD(password, salt, algorithm);
users.put(username, new User(username, hash, salt));
}
}
/**
* Checks if the passed credentials are valid.
* @param username username
* @param password password
* @param algorithm hashing algorithm from {@link Algorithms}
* @return {@code true} if valid, {@code false} otherwise
*/
public boolean isValid(String username, String password, Algorithms algorithm){
User u = users.get(username);
if(u != null) return u.validate(getMD(password, u.getSalt(), algorithm));
else return false;
}
/**
* Returns the message digest given the password, salt, and hashing algorithm.
* @param password password
* @param salt user-specific salt
* @param algorithm hashing algorithm from {@link Algorithms}
* @return message digest as {@code byte[]}
*/
private byte[] getMD(String password, byte[] salt, Algorithms algorithm){
try {
// convert to bytes and merge with salt
byte up[] = password.getBytes("UTF8");
byte message[] = new byte[up.length + salt.length];
System.arraycopy(up, 0, message, 0, up.length);
System.arraycopy(salt, 0, message, up.length, salt.length);
// create message digest and return
MessageDigest md = MessageDigest.getInstance(algorithm.name);
return md.digest(message);
} catch (NoSuchAlgorithmException ex) {
err.println("Failed to get algorithm instance.\n" + ex.getMessage());
} catch (UnsupportedEncodingException ex) {
err.println("UTF8 encoding error.\n" + ex.getMessage());
}
return null;
}
/**
* Creates a random salt.
* @return random salt as a {@code byte[]}
*/
private byte[] randomSalt(){
final Random r = new SecureRandom();
byte salt[] = new byte[SALT_BYTES];
r.nextBytes(salt);
return salt;
}
/**
* For testing only, this will print user specific information.
* @param username username for which the data will be printed
*/
public void printUser(String username){
if(users.get(username) != null) users.get(username).print();
else err.println("User " + username + " does not exist");
}
/**
* This class stores user information necessary for creating and testing
* message digest hashes. For testing, this is just a simple populated
* class. In practice, this will more than likely be a database table.
*/
class User {
private String username;
private byte[] hash;
private byte[] salt;
/**
* Instantiate a new user.
* @param username username
* @param hash message digest hash
* @param salt personalized salt
*/
public User(String username, byte[] hash, byte[] salt){
this.username = username;
this.hash = new byte[hash.length];
System.arraycopy(hash, 0, this.hash, 0, hash.length);
this.salt = new byte[salt.length];
System.arraycopy(salt, 0, this.salt, 0, salt.length);
}
/**
* Validates a passed message digest hash.
* @param hash hash to validate
* @return {@code true} if valid, {@code false} otherwise
*/
public boolean validate(byte[] hash){
return Arrays.equals(this.hash, hash);
}
/**
* Get the user-specific salt.
* @return the salt for the user
*/
public byte[] getSalt(){
return salt;
}
/**
* For testing only, this will print the username, salt, and hash.
*/
public void print(){
out.println("Username: " + username);
out.println("Salt: " + Base64.getEncoder().encodeToString(salt));
out.println("Hash: " + Base64.getEncoder().encodeToString(hash));
}
}
}The following is an example implementation of the MD class that (1) sets a user, (2) trys to login with incorrect credentials, and (3) trys to log with correct credentials.
import static java.lang.System.out;
public class MDTest {
private static MD md;
public static void main(String[] args) {
// setup
md = new MD();
String username = "username", password = "password";
MD.Algorithms algorithm = MD.Algorithms.SHA512;
// add user and print stored information
out.println("Adding user: "+username+"/"+password+" - "+algorithm.name);
md.addUser(username, password, algorithm);
md.printUser(username);
// compare with incorrect username
out.println("\nValidating: "+username+"1/"+password+" - "+algorithm.name);
validate(username+"1", password, algorithm);
// compare with correct username
out.println("\nValidating: "+username+"/"+password+" - "+algorithm.name);
validate(username, password, algorithm);
}
/**
* Validate the user.
* @param username username
* @param password password
* @param algorithm hashing algorithm from {@link Algorithms}
*/
private static void validate(String username, String password,
MD.Algorithms algorithm){
boolean valid = md.isValid(username, password, algorithm);
if(valid) out.println("Successfully validated");
else out.println("Invalid credentials.");
}
}Output from the example class:
Adding user: username/password - SHA-512
Username: username
Salt: rev2OpTPPl3A8kAZbA2qHfmKzjByVwNP6KDGtUgnyiY=
Hash: Y8+OLeMr5y5QmI/c4mfbrszx+wF+p0z3nBUAaAyXHKZ0mU5qDJioMl3Iu2/Do0a2twrxekC0xvXFvULWhNiSIA==
Validating: username1/password - SHA-512
Invalid credentials.
Validating: username/password - SHA-512
Successfully validated