Password hashing is an interesting subject, which I have been working on enhancing in FluxBB v2. Here I’m going to provide an introduction to storing passwords securely, and share some thoughts as well as our solution.
Note: I am talking about hashing opposed to encryption. Many people use the terms interchangeably, however they are very different operations and should not be confused.
- Hash functions convert variable sized data into a fixed sized result. They are deterministic and one-way – the same input always hashes to the same output, which cannot be reversed. Hashes have many more useful properties, but for storing passwords the important point is they cannot be reversed.
- Encryption is the process of transforming information to make it unreadable to anyone without the decryption key. The important difference is the ability to recover the original data given the correct decryption key.
In the situation where the database in compromised and users password hashes are exposed, it is a good bet that any decryption key we have stored could also be compromised. Since we have no need to know the users actual password (we can check for a valid login by hashing their input and comparing to the stored hash) we should never use encryption for storing passwords.
Hashing the password
At first glance password hashing seems like an incredibly simple problem – just run the password through a well known hash function and job done. Most advice these days seems to suggest the use of SHA-1 or SHA-2.
Hashing
SHA-1/2 are hash functions, designed by the NSA. Like all hash functions, they are one-way, so given a database of password hashes an attacker cannot reverse them. However passwords hashed using a simple hash function are still vulnerability to reversing using rainbow tables. Rainbow tables are mappings of resulting hash -> original password for dictionaries of common passwords, etc. To combat rainbow table attacks many people suggest the use of per-user salts.
Hashing + salt
A salt is a randomly generated string which is appended to a users password before hashing. This randomly generated string prevents the use of pre-generated rainbow tables as it increases the complexity and length of the final password, and hence the size of rainbow tables required are infeasibly large – the only solution is for an attacker to attempt a brute force attack using the correct salt.
Thanks to advances in parallel computing and graphics card technology, this is now a viable solution. Various tools such as IGHASHGPU and whitepixel now exist – with whitepixel boasting as many as 33.1 billion MD5 hashed password attempts per second using just 4 AMD Radeon 5970s.
Key stretching
Key stretching refers to techniques used to increase the time it takes to test a password – and hence decreasing the number of brute force password attempts that can be made per second. Using plain hashing algorithms we are talking one millionth of a second to generate a single hash on a regular CPU, or in the order of one billionth of a second using the above mentioned GPU software. If we can increase the time taken to generate a single attempt to 10s of milliseconds then we have effectively cut the brute force attempts by 4 or 5 orders of magnitude. In the situation where a legitimate user is attempting a login, an extra 10ms is in most cases unnoticeable.
BCrypt (Blowfish encryption)
I started this post by emphasising the difference between hashing and encryption, and stating that encryption should never be used for storing passwords – so you might be asking yourself why I am now talking about encryption?
BCrypt is an algorithm for irreversibly obscuring passwords using the blowfish encryption algorithm. It is important to understand that BCrypt does not simply encrypt passwords – the process is still a one-way process, just like hashing. BCrypt works by encryption a magic string, using a key derived from the provided password. The encrypted magic string is stored in the database, but the derived key is never stored.
The blowfish algorithm is important, as the amount of work done to encrypt a string, and hence time taken, is tuned using a cost parameter. By increasing this cost factor we can increase the time taken to test a password.
BCrypt is available as of PHP 5.3+, using the crypt function.
crypt() will return a hashed string using the standard Unix DES-based algorithm or alternative algorithms that may be available on the system.
CRYPT_BLOWFISH – Blowfish hashing with a salt as follows: “$2a$”, a two digit cost parameter, “$”, and 22 base64 digits from the alphabet “./0-9A-Za-z”. Using characters outside of this range in the salt will cause crypt() to return a zero-length string. The two digit cost parameter is the base-2 logarithm of the iteration count for the underlying Blowfish-based hashing algorithmeter and must be in range 04-31, values outside this range will cause crypt() to fail.
PBKDF2
PBKDF2 (Password-Based Key Derived Function) is a function to produce derived keys by repeatedly hashing the input many times. I’m not going to attempt to explain PBKDF2 in detail, however by tuning the number of times to repeatedly hash the input the cost can be increased, in the same way as for BCrypt. PBKF2 is used by some well known protocols/systems, such as WPA/WPA2, Grub 2, and LastPass.
Generating random data with PHP
Generating random data doesn’t sound like it should be challenging, and indeed it is not – however generating cryptographically strong random data is a bit harder.
The default random number source used by PHP is not considered to be cryptographically strong – however not to worry, there are various sources of cryptographically strong random data on most systems.
PHP 5.3+, OpenSSL extension
The OpenSSL extension, included by default in PHP 5.3+, provides a source of cryptographically strong random data.
openssl_random_pseudo_bytes — Generate a pseudo-random string of bytes
Generates a string of pseudo-random bytes, with the number of bytes determined by the length parameter.
It also indicates if a cryptographically strong algorithm was used to produce the pseudo-random bytes, and does this via the optional crypto_strong parameter. It’s rare for this to be FALSE, but some systems may be broken or old.
/dev/urandom
For Linux/UNIX systems, cryptographically strong random data is produced from the device unlocked random, /dev/urandom. This can be read using the regular file access functions in PHP.
Microsoft CSP (Cryptographic Service Provider)
The Microsoft Cryptographic Service Provider API provides a source of cryptographically strong random data on Microsoft Windows systems. It can be accessed using the COM interface.
Solution used in FluxBB v2
For FluxBB v2 I have produced a library which makes use of BCrypt when available on the system (PHP 5.3+), and falls back to PBKDF2 otherwise. Cryptographically strong random data is obtained using the OpenSSL extension if available, will fall back to /dev/urandom, or in the worse case PHPs built in non-cryptographically-strong functions.
No Comments.
Add Your Comment