Post banner
Cloud Security 6 Min Read

Optimizing Detection of Breached Passwords

In the increasingly difficult times of protecting our own digital life or helping others protect theirs, we must be ever vigilant about ensuring that we have strong passwords. When building systems to manage passwords, there are common and time-tested algorithms for checking the strength of a password so you can warn users about weak ones and how they can make them stronger. Some properties of a strong password are not so straightforward to build a check for, or it is difficult to implement a check to run with real-time performance. In this post we present an approach that has performed well for detecting one aspect of a strong password — whether it has been breached or not.

What makes a strong password

First, a reminder about what makes a strong password. There are a lot of theories and research on this, but most of them boil down to one concept — passwords should be hard for another human or a computer to guess. The basic properties in order of effectiveness are that they should be as long as possible, should be either randomly generated characters or be a passphrase, and should never be shared across multiple online accounts or services. Ignoring any of these important recommendations increases the likelihood that another person or computer will guess your password — and before you know it, your email and password are victims of high profile breaches that expose sensitive personal or company data.

Standards?

Speaking of breaches, the federal government publishes authentication guidelines in a publication called NIST 800-63B: Digital Identity Guidelines. The document contains best practices to follow when authenticating users and creating passwords, and guides implementation for many companies and organizations. One of the guidelines says that when verifiers (your application) establish or change a password on your behalf, they “SHALL compare the prospective secrets against a list that contains values known to be commonly-used, expected, or compromised.” So if a password has been identified as compromised, you must block the user from establishing it (such as part of creating a new account), and you cannot allow them to change their current password to one that has been compromised either. When hackers breach the data of an online service, especially if it is a large enough breach involving thousands or millions of user accounts, it will eventually be disclosed to the public and even made available on search engines so you can see whether your email or password has been compromised in any breaches.

HaveIBeenPwned

One such service that maintains a database of compromised, or “pwned”, email addresses and passwords is HaveIBeenPwned. Once a year or so, a new data set is published on the site and you can search by email or password to see if it has been pwned and which breaches they were pwned in. The latest data set size for passwords is over 555 million in size. The website offers an API you can call to determine whether a password has been pwned. They will charge you a small monthly fee for the API. If you don’t want to be rate limited, subject to their terms of use policy, or just don’t want to pay the fee, you can download the full SHA-1 hashed list of passwords that is currently about 10GB compressed. This uncompresses to a file that is over 20GB.

Querying against 555 million passwords

If you choose to search the data dump of 555 million passwords, your next challenge is how to do this in a reasonable amount of time and use a reasonable amount of resources to do it. Searching the uncompressed file for a single hashed password can take several seconds or minutes depending on the CPU and I/O resources available to you. Loading the data set into a SQL database might be enticing, but you then need to maintain and operate a database, and it would need all hashed passwords inserted from the data set. You might not want the overhead of the network calls to the database either. Loading the whole 20GB file into memory is not a great option either since your app may not have that much memory available to it, and even if it does, that typically puts you into a much more expensive asset class for a host deployed on the cloud. So how do we do this, for example, when only 4GB or 8GB of RAM is available to your app?

Enter the Bloom Filter

What we really need in order to search through the whole data set for one hashed password is to load a version of the data set into memory that is both indexed so searching is faster and that takes no more memory than will fit into our 8GB of RAM. This is where Bloom Filters offer a great solution. A Bloom Filter is a structure that loads data into a fast, searchable index. However, to achieve minimal use of memory, the index is lossy. To save space, not every item is represented in the index. So if a search in the filter indicated that an item is present, it may or may not actually be there with a certain probability. If a search indicates that an item is not present, it is definitely not present and with 100 percent confidence. The False Positive Probability (FPP) determines the chance that if an item search returns success, that it is actually there. The FPP is tweaked up or down based on acceptable tolerance. A higher FPP will yield a greater chance that a matched item is actually there, but the lookup takes more time and results in a larger index that uses more memory. A lower FPP does just the opposite. So you must strike a balance between all these factors to satisfy the needs of your particular situation. For more information on how Bloom Filters work, along with a tutorial, see Bloom Filters by Example. Here is a great image taken from Wikipedia on querying for a string in a Bloom Filter that has been initialized with a small set of strings. It shows no match because the search didn’t show a 1 bit set in all the hashed positions.

Source – Wikipedia – Bloom filters in bioinformatics 

How Threat Stack Does It

For Java or Java-based languages, like Scala, one such open source library for using Bloom Filters is the BloomFilter class in the Google Guava library. In the case of searching a HaveIBeenPwned password data set, there are two pieces to the solution. 

First, write a small utility program that loads the data set into a Bloom Filter and then saves it to disk. With the Google Guava library, that looks something like this:

Second, your app loads the Bloom Filter from the file into memory. Then you can search the Bloom Filter for any hashed password you need.

We use such a solution to determine whether user-supplied passwords are known to be compromised. Playing with various values for FPP, we found that a value of 0.00125 (0.125 percent change of false positive) was a satisfactory probability that yielded search times of only 1ms to 2ms on an index that is 1GB in size. On an AWS host that is a t2.large (8GB RAM), this leaves enough heap and stack space for the rest of your app to function. If a user is trying to create or change a password that results in a false positive of being compromised, a 0.125 percent chance of that happening is low enough that there is only a very small chance a user will have to pick another password to use.

Further Work and Considerations

So if you do choose to implement compromised password checks in your application, using Bloom Filters with the HaveIBeenPwned password data set is a very reasonable solution. Use a Bloom Filter library that works for your language of choice and tweak the FPP as necessary based on your performance and memory constraints.

On a different but very relevant note, it should be pointed out that 555 million breached passwords is an alarming number. It speaks to the fact that maybe we are not all using passwords that are as strong as we think they are. For example, passwords that really are strong but that get reused across online accounts are vulnerable to credential stuffing attacks after hackers have harvested enough of your breached passwords. So there may be a lot of value in educating or reminding those who have a digital life how to protect their passwords. Make them long, random, and hard to guess. Using a password manager will help you do this, and you don’t even need to remember your passwords. Finally, make sure to enable multi-factor authentication everywhere it is available in the event that your password does get breached.  With all these good practices, there is a much better chance you won’t end up on a public breach data set and get “pwned.” (For a discussion of best practices for using passwords, have a listen to my recent podcast: Encouraging Strong User Passwords.)