LivingSocial is the latest in a growing line of organisations suffering a calamitous breach in which customer login data has been exposed. It involved 50m LivingSocial usernames and passwords.

Only the hash values of the LivingSocial passwords were exposed, not the plaintext. A hash value is created by passing the plaintext password through a one-way cryptographic function. This results in a unique, fixed-length, sequence of characters, for each plaintext entry. The organisation then stores this hash value rather than the original plaintext password. Minor differences in the plaintext original results in vast differences to the hash value. It is not feasible to reverse a hash value to compute the plaintext.

In this way, a hash is like an omelette – it cannot be unmade to get back to it’s egg-in-a-shell form. The only way of figuring out a plaintext password from it’s hash value, is to guess. A cracker will guess the plaintext password, generate the hash value of this guess using the same one-way cryptographic function used by the organisation, and see whether the hash is the same as the stolen hash value. He then repeats this process until the guess is correct.

LivingSocial utilised the SHA1 cryptographic function to generate their hash values. This function is designed to be fast and use very little computational resources. However, this means that a cracker can test many guesses in a short period. In 2012 LinkedIn were victim of a breach in which 6m passwords were exposed. LinkedIn’s passwords were also stored as hash values using SHA1. A researcher tested how long it would take to crack these passwords from the hashes. Because the cryptographic function used was SHA1, the cracker was able to cycle through 15 billion options every second. At that pace, 20% of the 6m passwords were cracked in the first 30 seconds. These were the more obvious, shorter passwords. After two hours, over half the passwords were cracked and after one day this had risen to 64%. After only 6 days, 90% of the passwords were cracked.

Password crackers use a variety of methods to speed up the process. Each year about 100m stolen passwords are placed online. Crackers learn the popular words used for passwords and are also able to figure out the patterns that people use for passwords. Some typical patterns include:
– Capital letters generally only used at the start of words
– Numbers and non-alphanumeric characters (such as “!*&%$”) generally used at the end
– Typical interchanged characters include “$” for “S”, “3” for “E”, “1” for “l”, etc.
– First names followed by years are common, such as “James1964”
– Mirror-image words are sometimes used, such as “secretterces”

Password crackers also make use of rainbow tables to speed up the processing. These are useful for cracking passwords comprising 7 or 8 characters.

The LivingSocial passwords were also salted. Salting is a process of appending unique random characters (known as the “salt”) to the plaintext password before hashing. The unique salt for each user needs to be stored. Salting ensures that the hash for each user is unique even if the password is not unique. Salting requires each hash to be cracked separately.

LivingSocial have now announced that they are changing their one-way cryptographic function from SHA1 to Bcrypt. This would require a cracker to use far more processing power to crack. The researcher mentioned above who could cycle 15b SHA1 options every second, would only manage 1,750 per second using Bcrypt, using the same computing power. Bcrypt thus raises the security bar quite considerably.

Faster computing resources obviously make it easier to crack hashed values. Speeds which will be attainable after the advent of quantum computing will be a complete game-changer for cracking hashed values, and for encryption in general.

Individuals wanting to protect their passwords should:
– Ensure a different password is used for different sites. This is only practical using a password manager.
– Use a password generator that does not utilise dictionary words. Most good password managers incorporate password generation functionality.
– Passwords of 9 characters or longer are currently difficult to brute-force crack.

The obvious message for organisations from the LivingSocial experience is that they should change their hash function to Bcrypt or something such as SH512CRYPT, or Scrypt, or PBKDF2 – before the calamitous breach event.