Right now, cyberspace has exploded with info, tweets, opinions and general discussion around the the Ashley Madison breach. For those who don’t know, AshleyMadison is the world’s largest “affair portal” where consenting adults can reach out (literally and figuratively) to others on the interwebs to have a casual fling. The tagline of their website is “Life is short, have an affair”. As you can gather, this is risqué stuff. In July 2015, AshleyMadison was hacked by a group called “Impact Team”. Details are yet to surface, but they probably used a combination of SQL Injection, spear phishing and account compromises. Impact Team had threatened the company with a public release of their data. Last week, they made good on their promise. They released around 30GB of database dumps, emails and source code from the site. Among the data dumps were great gory details of usernames, emails, addresses, credit card information (tokenized/truncated) and passwords.
This was of great interest to me. Most sites that claim to be “great at security” do a really bad job of protecting passwords (with cryptography). Some of them use poor quality encryption (like Adobe with its disastrous practice of 3DES with ECB Mode, and the password hint in plaintext), Linkedin with or like RockYou use no encryption (plaintext passwords) or like in the case of most sites I see, MD5 hashes (mostly without salts). I was expecting to see similar results in the AshleyMadison Breach. However, that was not to be….
Surprisingly, AshleyMadison has used a much stronger standard to protect its passwords called bcrypt. And this is the purpose of this article. I want to explore a few different ways to protect passwords in the DB, as an alternative to traditional encryption or hashing.
One of the most pervasive issues with hashing as a means to protect user passwords is with the fact that hashes were not meant to protect confidentiality, as much as they were designed to protect integrity. Hashes are typically used as integrity verification mechanisms to identify instances of tampering, corruption and so on. However, hashes have become a standard for several websites to protect user passwords. The reasons are pretty simple. Hashes are extremely fast (0.004 seconds to generate a SHA1 hash of the password “admin123”), very simple to implement. However, hashes can be broken with a pretty good GPU system. For instance, oclHashCat (a hash cracking tool) with 8x AMD R9 290X at stock core clock, computes 162 billion MD5 hashes/second, 11 billion SHA-256 hashes/second and 797 million SHA-512 hashes/second. To break this down to simple password mathematics, if your users have a lowercase, alphanumeric password, which is about 6 chars long, every single password hash combination of MD5 can be performed within 40 seconds. And this is with basic computing power. You can add an additional layer of protection by salting password hashes, but unique password hashes have to be stored, and this in itself creates a possible vulnerability. The biggest problem with hashing passwords is that an attacker can attempt to “crack” the hashes at an extremely accelerated rate, because the process of hashing is innately fast and even adding a salt (that is stored) can be combined to perform extremely quick dictionary/brute-force attacks against hashed passwords.
bcrypt is actually a pretty strong cryptographic implementation to protect passwords stored in databases. Bcrypt actually uses a variant of Bruce Schneier’s algorithm Blowfish.
The implementation is designed to be slow due to Blowfish’s Key expansion and key stretching phase. The thing with bcrypt is that it implements a “work factor” or “cost” factor in the algorithm. This “cost” is essentially the number of times the key is expanded, so for instance if the work factor/cost parameter is 10, the key expansion is 2^10 rounds (1024 rounds) of key expansion. I know this sounds like gibberish, but Key expansion essentially ensures that calculating all possible values would take a long time, a really long time.
bcrypt is a key derivation function. It takes in the password (plaintext), a salt (can be system generated), and a cost factor (number) to derive a bcrypt hash. This hash is much more secure against bruteforce or dictionary attacks because of what I mentioned above. For instance, a bcrypt operation on the password “admin123” took a whopping 0.8 seconds with 10 rounds of work factor. In 2012 when Linkedin passwords (protected with SHA1 were compromised) it took a researcher about 6 days to crack 6.5 million hashes, with bcrypt, the same effort would have run into a few centuries.
bcrypt is adaptive, so with increasing power of computing, it can adapt based on higher work factor.
PBKDF2 (Password Based Key Derivation Function)
PBKDF2 is similar in some ways to what bcrypt tries to achieve. PBKDF2 is a key derivation function similar to bcrypt, however, PBKDF2 uses a pseudorandom function (hash, cipher, HMAC) with the plaintext password, a salt, number of iterations (like work factor) and the length of the key.
Derived Key = PseudoRandomFunction + Plaintext Password + Salt + Number of Iterations + Length.
Unlike bcrypt, PBKDF2 does not use a Blowfish cipher to perform Key expansion. PBKDF2 is also much faster than bcrypt, thereby being the choice of systems that require great scale, especially in the cloud. The time taken to generate a PBKDF2 hash of the same password “admin123” with 1000 iterations takes about 0.08 seconds to output the Derived Key (Hash), hence making it much much faster than bcrypt. This is ery useful for systems that need scale and low compute time. NIST SP 800-132 recommends PBKDF2, however there are loyalists on both sides of the spectrum for both bcrypt and PBKDF2.
Protecting passwords against compromise is becoming an increasingly difficult task, especially with lower cost of hardware and increasing computing power. This effectively renders typical techniques such as hashing nearly powerless against dictionary/brute-force attacks. Both bcrypt and PBKDF2 present a viable alternative to protecting passwords stored at rest. While AshleyMadison is undergoing a massive storm right now, there is a silver lining in that their users are relatively safe against password cracking attempts which could have an even bigger implication than it is currently.