In previous blog posts, I’ve discussed authentication mechanisms and password hashing. In this post, I will demonstrate why proper implementation of authenticator storage is necessary to protect both identities and data. I will continue to talk about passwords—specifically about implementing proper password hashing. If you have not read my previous blog, I’d encourage you to do so.
The prior post discussed using a key derivation function (KDF) based hashing algorithm. KDFs make it possible to derive one or more strong secret keys from a secret value . The formula looks like this:
DK = KDF(secret, salt, iterations)
The derived key (DK) is made up of the secret material, in this case a password, a random salt and a number of iterations designed to perform for an underlying pseudorandom function (PRF). For example, the pbkdf2 algorithm (a password-based KDF hashing algorithm) can use HMAC-SHA-256 as the PRF to hash the key N times:
from hashlib import pbkdf2_hmac
pbkdf2_hmac(hash_name='sha256', password=password, salt=salt, iterations=N)
When a user first creates a password, the password is hashed with a salt to calculate the derived key. The password is then stored along with the salt in a backend database. The next time the user logs in, the user’s password will be hashed with the stored salt to calculate the derived key, then compared with the key stored in the database.
If the keys match, that means the user has submitted the correct password; if they are not the same, then the submitted password is incorrect.
Determining the Original Password
There are two types of attacks that an adversary can perform to determine the original password; online and offline.
An online attack involves a situation where the adversary does not have access to the database that stores the derived keys. Instead, a malicious actor uses automated software to continuously submit passwords live through the web server or login portal in a “brute force” fashion until the correct password is submitted. This method is limited to the resources of the web server hashing the passwords, network bandwidth and rate limiting such as account lockouts or IP blacklisting.
Offline attacks allow adversaries to try to crack the passwords with less concern about being detected or becoming restricted due to limited resources. Through an offline attack, a malicious actor can copy the derived keys (a.k.a., hashes) to a system of their choice and use its resources in isolation.
Using a fast hashing algorithm—like SHA256 by itself—an adversary with the right hardware can eventually guess the original password by trying hundreds of millions or billions of keys per second. This can be made more efficient if the attacker guesses from a dictionary of common passwords rather than trying every possible combination of characters. By increasing the number of iterations performed with a PRF, you are increasing the amount of resources and time needed to compute the derived key, effectively reducing the velocity of password guessing from billions of passwords per second to thousands or even lower.
This does come at a cost.
While you are slowing your adversary down, you are also slowing the authentication process for legitimate users. Just as you’ve impacted the ability to guess passwords by orders of magnitude, you’ve also increased the time it takes to check a password upon login. Any functional system must identify the appropriate balance between usability and strength. From this perspective, it might not make sense to perform so many iterations that it takes 30 seconds for a legitimate user to log in.
What we do at Dwolla
We suggest aiming for a speed for one password of between one tenth of a second to a second. This is tricky because hardware is constantly getting faster, so the required parameters to achieve this change over time. Additionally, these schemes typically only make sense for interactive logins. The slow-downs introduced here may be much too impactful for API-based traffic that requires low latency and high throughput.
To help illustrate this point and come up with recommended settings, I created a sample Python app. I’ve included the source code and a Docker container that you can spin up to try this yourself. Testing on my 2018-era MacBook Pro, the output below shows the average of how long it took to hash a 32-character password using different hashing functions averaged over 100 trials.
The non-KDF, fast-hashing functions MD5 and SHA-256 completed in less than a microsecond and would allow for almost two million passwords per second. On the other hand, bcrypt with a work factor of 14 would hash one password in a little under a second and pdkdf2 with one million rounds in just under half a second. As you can see there is an enormous difference between using a plain hashing algorithm and a key derivation function.
The last two algorithms—scrypt and argon2id—are composed of both computationally-hard and memory-hard elements. These incorporate iterative hashing, parallel execution and a requirement for large amounts of memory to make it difficult for an attacker to attempt more than a few hashes simultaneously. We haven’t made use of GPU-based accelerations in this analysis. However, memory-hard algorithms such as scrypt and argon2id go a long way towards negating the power a GPU can bring to bear (they have many cores, but limited memory).
Based on running these tests, Dwolla recommends the following settings for each key derivation function. This is one component of our client onboarding assessments; clients are required to use at least the minimum required parameters.
|bcrypt||Work factor 11||Work factor 14|
|pbkdf2||100,000 rounds||1,000,000 rounds|
|scrypt||N: 2^15, R: 8, P: 2||N: 2^18, R: 8, P: 2|
|argon2id||T:4, M: 2^17, P: 8||T:16, M: 2^18, P: 8|
So far we haven’t incorporated the use of password dictionaries into our analysis. To see what impact this had on the time to crack a password, I used the same machine with the suggested parameters above, while also using the password cracking tool, hashcat and the rockyou.txt dictionary of 15 million common passwords.
After two minutes, I printed out the status for each algorithm to show how long it would take to iterate through the full 15 million passwords:
As you can see, scrypt with the suggested configuration would take more than 179 days to try every combination, or 1.03 seconds per password, where bcrypt would take .29 seconds per password and pbkdf2 would take .08 seconds per password.
The amount of time to hash these passwords would decrease as you apply more advanced hardware resources. As hardware gets faster, you should re-evaluate the iterations for your key derivation function to verify that it is effective.
At Dwolla, we constantly evaluate the suggestions and update accordingly. Of course an attacker that can bring to bear more advanced computing resources may be able to speed up the numbers above by a factor of tens, hundreds or even thousands (even in the case of memory-hard algorithms; more drastically for CPU-hard algorithms).
Ultimately it’s up to your business to decide the appropriate line between impaired usability and increased security lies. Even Dwolla’s minimum suggested settings will make a big dent in offline attacks, with minimal impact to your users. Additionally supporting and encouraging users to enable multi-factor authentication can devalue the use of passwords and the effectiveness of offline attacks.