Time Memory Trade-Off Attacks

Question

Given, we want to crack a password. With Time Memory Trade-Off Attacks one tries to find the right balance between time to compute hashes for all possible passwords. And the used memory to store all password hash tuples, where a lookup would be instantaneous.

(I know about some additional security mechanisms like salting, peppering, two factor authentication, ...)

But what I don't understand, that trade-off happens at attack-time. But usually one hears time for cracking good passwords in between human lifetimes, centuries or even the lifetime of the sun.

So the generation of such tables is still only feasible for short passwords, right?

For example I used zxcvbn and got the following results for a 9 character long password.

password:   evhtsxuko
entropy:    42.304
crack time (seconds):   271475183.949
crack time (display):   10 years

So with bcrypt being a slow hash function and is around for about 15 years, is it safe to assume that even for the NSA a 10 character password hashed with bcrypt is impossible to crack?

Answer 1

"Time-Memory Trade-Off" is the generic terminology for an algorithm which improves (shorten) running time by using more space (memory); or, similarly, that improves memory usage (i.e using less RAM or disk, or using it "better", e.g. with sequential access instead of random access) at the expense of more computing time.

In the case of password hashing, the main TMTO algorithm is due to Hellman back in 1980; a number of local improvements were later discovered, resulting in what is colloquially known as rainbow tables. We can get a conceptual view of rainbow tables by considering the two endpoints of the spectrum:

• Exhaustive search is about trying all potential passwords, hashing them all and comparing the value with the one that is to be cracked. This has the highest computational cost (average N/2 hashes to compute for N potential passwords with uniform probability) but uses only negligible RAM.

• A precomputed table contains the hashes of N potential passwords, and a single lookup needs to be done. We don't count the effort of building the table because it can presumably be reused for multiple attacks, possibly by multiple attackers. The size of the table is proportional to N, but the computational effort is negligible (well, about O(log N), which is small).

Rainbow tables will fit in between. When the table is built, you choose a parameter t called the "average chain length". The table size will be proportional to N/t: it is reduced by a factor of t, compared to the precomputed table. On the other hand, each attack will imply a computational effort proportional to t² hash computations, and t lookups. Depending on the operational conditions, the lookups or the computations will be the bottleneck (e.g. it depends a lot on whether the table are in RAM, on a SSD, or on a set of mechanical hard disks).

Salts completely thwart precomputed tables, including rainbow tables. Building a precomputed table for N passwords has cost N; building a rainbow table for the same N passwords has even higher cost (about 1.7*N). This is worth the effort only if the table can be used at least twice, to attack two distinct hash values; a one-shot table (rainbow or not) is not competitive with exhaustive search. But the point of salts is that there is not one function; in fact, there is a big family of functions, and the salt value tells you which one is actually used. A table built for a specific salt has absolutely no value in breaking a hash value for any other salt.

Bcrypt uses salts, so no tables, and no TMTO. Attackers are back to exhaustive search. Bcrypt also has weapons against exhaustive searches, namely a configurable slowness, obtained through a huge number of internal iterations: from the user point of view, there is not much a difference between a hash computation which takes 1 microsecond, and one which takes 100 milliseconds; but for the attacker, the latter means 100000 times the effort for his exhaustive search.

See this answer for more on secure password hashing. Short summary: if your password is strong (i.e. has high entropy), then even powerful agencies won't be able to obtain it by breaking the bcrypt hash upfront (they'll get it by breaking your kneecaps, but that's another story).

Answer 2

Bcrypt uses a "work factor"; higher work factors lead to more processing required for a given keyspace.

As far as the "time" estimation, what resources is the attacker projected to have? If the estimate is based on N resources, and the attacker throws 1000N resources at it, then the attacker can exhaust the keyspace or run through their rules-based dictionary attack in 1/1000th the time.

As far as actual time/memory tradeoffs, if you have a long random salt, there's no reasonable way to generate precomputed lists for every possible value of salt, so it's all runtime work. WPA lists can be generated because the salt is the SSID, which is rarely random.

Note also that if your password isn't truly random, then rules-based dictionary attacks are the worst danger, not pure brute force or even Markov chains.

Also, does that strength estimate take into account Moore's Law (or some other exponential increase factor)? All of the "lifetime of the sun" estimates fail to account for attackers buying new hardware after it gets better.

Answer 3

Bcrypt takes two parameters: a password and a work factor. The work factor tells it how long to spend on the problem.

Different work factors give different results, so the work factor acts as a sort of secondary salt. You don't normally think of it that way, but its part of why you rarely see bcrypt in hash databases. In order to match the hash, you need both the password and he correct work factor. So your database needs a separate set of bcrypt hashes for every potential work factor.

As for whether the NSA will ever be able to crack 10-char bcrypt hashes, its on the very far side of probability but not entirely off the deep end of possibility. Jump up to 14 chars and you pretty much have it.