Adobe leaked credentials checker

What is this about?

Adobe got hacked and about 150 million people’s account details have been leaked.

Why does this matter?

Adobe didn’t store the passwords securely and you should work on the assumption that they have been cracked.

Popular wisdom suggests people use the same password on multiple websites. This is confirmed by many of the “password hints” in the leak.

Some notes about false positives

The original leak is about 9.3GB uncompressed, of which 3.3GB is email addresses. This is too big to fit in memory (the backend for this site runs on cheap commodity hardware) and too slow to search from disk.

Instead, this site uses a bloom filter backed by a single redis bitmap. This means the data can fit into 512MB (i.e. 232 bits) of memory and allows us to perform lookups in constant time. Email addresses are turned into twenty 32-bit hashes using the MurmurHash3 hashing algorithm and all twenty hashes must be present in the bitmap for a positive result to be returned. However, this necessarily means there will be some false positives.

To estimate the probability of false positives, we first calculate the expected occupancy of the bitmap (i.e. the expected number of distinct hashes). For a number of items $i$ and a number of boxes $b$, this is given by the recursive formula:

$$occupancy(i,b) = \begin{cases}0 & ,\ i=0\\1 & ,\ i=1\\occupancy(i-1,b)+1-\frac{occupancy(i-1,b)}{b} & ,\ i\ge2\end{cases}$$

i.e. the same occupancy as the previous bitmap with probability $p$ and one more than the occupancy of the previous bitmap with probability $(1-p)$, where $p$ is the previous occupancy expressed as a proportion of the number of boxes $b$ (i.e. the probability that a randomly chosen element in the bitmap is already 1, which would not result in the occupancy increasing).

Note that this is like the birthday problem but instead of calculating the collision probability we are calculating the expected occupancy (the expected number of distinct birthdays for a given number of people).

Treating $occupancy$ as a recurrence relation, we can then obtain the closed form:

$$\begin{align*} occupancy(i,b) &= b-\frac{(b-1)^i}{b^{i-1}}\\ &= b\left[1-\left(1-\frac{1}{b}\right)^i\right] \end{align*}$$

The probability of getting a false positive with a $k$-hash bloom filter holding $i$ items in a length $b$ bitmap is then $occupancy(ki,b)^k$, i.e. the probability of hitting all 1s when choosing $k$ elements at random from a bitmap populated with $ki$ items. (This assumes the four words that comprise a 128-bit MurmurHash3 are independent of each other, which is not too unreasonable.) The optimal number of hash functions $k^*$ is then the value of $k$ which minimises this expression, and occurs when the expected occupancy is $b/2$, at which point the false positive rate is $2^{-k}$.

This site uses $i$ = 152,472,417, $b$ = 232, $k$ = $k^*$ = 20. This means the probability of false positives is about 0.0001%. For comparison, a binary tree of hashes which occupies the same amount of memory (512MB) would have a 56% false positive rate, and it would need 840MB of memory to reduce this to our 0.0001%. An optimal bloom filter which is allowed to occupy 840MB would have practically no false positives at all.