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.
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.
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."
