3

As I understand in most security breach where the list of hashed password are compromised, attackers do use brute-force to try to find weak password and, invariably, they always find quite some (like in the recent Github breach).

If I'm not mistaken in most cases when a user creates an account, the password is sent, encrypted (due to TLS / SSL), to the website which then adds some salt and stores the hash + salt.

Even in most sophisticated cases (like when bcrypt is used), upon account creation there's one point in time at which the server does have the password in cleartext.

My question is: couldn't you use, at that very moment when you have the password in the clear that the user is trying to use for his new account, a gigantic rainbow-table on the server side to check for billions and billions of weak passwords in a split-nanosecond?

Then if you detect that a weak password is used, you'd simply tell to the user that his password is too simple and that, no, using "edcrfvtgb1" isn't smart.

I mean: if attackers manage to brute-force weak-password even though they have to deal with the problem of the salt, couldn't servers benefit from the fact that, when the users creates a new account, they do know the password in the clear to simply look it up in a big rainbow table when the user creates his account?

This doesn't seem hard to implement and seen harddisk sizes these days, it's probably not problematic to store a big rainbow table on the server side.

Am I missing something obvious or would this help catch a lot of weak passwords and, hence, mitigate the endless accounts compromise we keep seeing on a nearly daily basis?

  • Technically possible, no question. Problem could be that the result would look rather random to the user. He may get told "weak password" over and over again without any apparent reason. That may be the reason why most implementations you see prefer measurable things like length, presence of numbers and special characters and similar things where you can clearly tell what was done wrong. – thorsten müller Nov 20 '13 at 16:30
  • 9
    Why even use a rainbow table if we are talking about finding weak passwords that we already have in plain text? A rainbow table is just a key value store of hashed and unhashed passwords (so you can lookup a hashed password and find the plaintext version). It sounds like what you want is just password restrictions (minimum length, different character types, etc...). – Mike Nov 20 '13 at 16:31
  • I think your biggest issue is the lookup is a pretty hefty DB to be carrying around. But loads of sites now will stop certain weak passwords actively even if they don't have complexity requirements. – Wyatt Barnett Nov 20 '13 at 16:47
  • 1
    GitHub breach info: github.com/blog/1698-weak-passwords-brute-forced – M. Dudley Nov 20 '13 at 17:22
  • 2
    @Mike: obligatory link whenever someone mentions password restrictions: Password Strength – Marjan Venema Nov 20 '13 at 17:59
7

The lookup time would be negligible, so this is a feasible way to prevent the use of weak passwords. However as @thorsten mentions in his comment, if you're implementing this on top of other password content requirements and some user enters a password that meets those requirements but is also in your table, it would be difficult to describe to the user exactly what was wrong with the password in a way that's easy for anyone to understand.

As @Mike eluded to in a comment, this type of security measure wouldn't be implemented with a rainbow table (which as he said is a map of hashes to plaintext strings), it would be implemented with a simple list of weak passwords. You don't need the hashes in this case.

6

TL;DR - yes & no. Yes it can be done but no, it shouldn't be done as you suggest.


My question is: couldn't you use, at that very moment when you have the password in the clear that the user is trying to use for his new account, a gigantic rainbow-table on the server side to check for billions and billions of weak passwords in a split-nanosecond?

No, you can't - or at least, not as you suggested.

To make the approach you suggested viable would require compromising the security of the site. And there's better ways to accomplish what you want to do.

Why? The problem is a misunderstanding with how rainbow tables work. And here are the issues.

  • A rainbow table is precomputed
  • A the salt added to a new user's password for hashing should be random

A good salt will be at least 10 - 16 characters long (see 1, 2, 3), which will add ~80-128 bits more of entropy to the overall password. Even with a 10 character salt and an 8 character password (both weak), that's 2.2 x10^43 potential combinations. A rainbow table with that many combinations would require more disk space than most can afford.

If you used a fixed salt (which isn't recommended as it compromises the security), then you would be able to relatively easily build a rainbow table that could be used as you suggested. But a fixed salt partially defeats the purpose of using a salt to begin with.

Rainbow tables are useful attack vectors when salts aren't used or when the salt is a fixed length. Without a random salt, it's easy enough to take the hashed value from the password file and look up the cleartext password in the rainbow table.

Using random salts force an attacker to use brute force to crack the password. There's just too many combinations to be stored to make a lookup approach worthwhile. Technology advancements have also made brute force approaches more practical. As of Dec 2012, some of the fastest GPU backed brute force password cracking systems could process 350 billion passwords per second. (see here for reference) With technology advancements, that rate will only increase.

Am I missing something obvious or would this help catch a lot of weak passwords and, hence, mitigate the endless accounts compromise we keep seeing on a nearly daily basis?

Yes, you're kind of missing something about rainbow tables but we just beat that subject into the ground with the above.

As I alluded to earlier, there are easier ways to do what you're suggesting. They can even be done client side via javascript so you don't have to incur a roundtrip penalty for the server to tell the client / new user that their password is too weak.

Password vaults like KeePass* have a built in password entropy indicator. Using the "edcrfvtgb1" password example that you provided, we see it only has 50 bits of entropy which is relatively weak. Current recommendations are to have passwords with 98 to 128 bits of entropy depending upon how secure you need it to be.

KeyPass password strength

You could use a javascript plugin that measures password entropy to provide immediate feedback to the new user or a user who is changing their password. This link goes into some detail with actual code and also contrasts against older methods of handling passwords. Running a web search against javascript password strength meter comes back with more than enough hits to kickstart additional research.

So your original thought is good, and yes the broader question that you are asking can be done. From my observation, I have seen a number of sites start to incorporate password strength meters to help guide users in selecting passwords.

* I just happen to know of KeePass, there are many other excellent password vaults out there that offer the same functionality.


... and the obligatory xkcd link. Hat tip to Marjan Venema for posting it first in a comment.

Obligatory xkcd, hat tip to Marjan Venema


So just how much data would that be?

10 bytes of salt + 8 bytes of password yields 144 bits.
2^144 is ~2.2x10^43 combinations.
Each combination will need at least 18 bytes for salt+password and 60 bytes for a bcrypt hash. (see here) For a total of (at least) 78 bytes per combination.
2.2x10^42 combinations * 78 bytes = ~1.7x10^45 bytes.
Shrinking that down a bit yields: 1,438,846,037,749,345,026,048 YB (yotta bytes)

Or perhaps we could call that 1.4 penta-yotta bytes. I call it "a lot."

  • great answer... That said my 'edcrfvtgb1' example is one that follows "patterns" on the keyboard: 'e' then row below is 'd' then row below is 'c' and rinse and repeat. I was using that one because there are passwords crackers that do look for those very stupid patterns that many users are using and think they're good passwords. My idea is basically to use a password cracker to look out for all these seemingly "strong" password but which are actually totally stupid. Recent security exploits and password DB leaks have shown that there are many users using such ways to "invent" passwords. – Cedric Martin Nov 22 '13 at 16:30
  • 1
    @CedricMartin - AFAIK, the better entropy engines take keyboard position into account. I don't know of any that take into account common 1337 substitutions though. The password cracking engines definitely have those options built in. I would consider modifying an entropy engine to incorporate the additional rules you can pick up from the password crackers. – GlenH7 Nov 22 '13 at 16:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.