Can a universe-sized computer crack an SMS-sized password?

[queerismyfavouritecrayon]

Hi, I'm new to cryptography so I don't trust my own calculations. I was hoping you folks could tell me if I'm off the mark.

The question is: if you turned the entire universe into a computer and devoted all of its resources to brute forcing an 160-character password consisting entirely of lower-case letters, would you succeed before your cosmic computer succumbed to entropy?


The hypothesis in question:

-Any computation that can be performed must be a "subroutine" in the overarching computation of the universe. Therefore, the computational capacity of the whole universe places a safe limit (though not an absolute, incontrovertible one) on brute force attacks.

-Seth Lloyd says that, so far, the universe has performed no more than 10^120 operations (http://arxiv.org/abs/quant-ph/0110141). I've also heard 10^123 operations so I'll use that figure just to make this estimate slightly more conservative.

-I'll assume one password guess-attempt in a brute force attack is 1 operation. (Could a guess conceivably be less than 1 operation?)

-According to Wikipedia (http://en.wikipedia.org/wiki/Future_of_an_expanding_universe#Dark_Era), when the universe is 10^100 years old, "Photons, neutrinos, electrons, and positrons will fly from place to place, hardly ever encountering each other." Presumably this makes any meaningful computation impossible, including a brute force attack.

-The way I interpret Seth Lloyd's paper (though it's confusing) is that the universe has so far performed no more than 10^123 operations in its 13.7 billion year history. For simplicity though, I'll assume that the universe is capable of 10^123 operations annually. (If I'm doing all these steps correctly, this significantly overattributes processing power to the universe.) Therefore I'll multiply 10^123 operations * 10^100 years to get 10^223 total operations throughout the course of the universe.

-An 160-letter password (the same size as a text message) using only lower case would have 26^160 combinations.

-According to Wikipedia (http://en.wikipedia.org/wiki/Password_strength#Entropy_as_a_measure_of_password_strength), "On average, an attacker will have to try half the possible passwords before finding the correct one." So we'll change that to (26^160 / 2).

-Since (26^160 / 2) - (10^223) yields a huge positive number (see the math: http://goo.gl/dhygG), I conclude that if you used all the computation power in the universe to try to crack this password, you would have a negligible chance of succeeding before the whole thing goes up in smoke (or, rather, Hawking radiation).

So, is this conclusion correct, or is there a mistake here?


Known flaws:

-Doesn't take into account quantum computation
-Assumes present-day heat death predictions are accurate
-Ignores possibility of a multiverse
-It's unrealistic to remember an 160-letter password unless it consists of words, in which case it would be subject to a much faster, dictionary attack


P.S. Sorry, it's my first post to the forum, I couldn't figure out how to make hyperlinks

[Yakk]

Doesn't set off my "off by a lot"-meter.

There are also thermodynamic limits on computation based on temperature and energy that are useful. So you can work out similar problems on how much computation a type-2 civilization could do before its star ran out of fuel.

[Sagekilla]

By the raw numbers, the number of possible passwords (26^160) is equal to about 10^(226.396). Since you're assuming you can do 10^223 passwords, you'll only be able to try 0.04% of the possible passwords.
Equivalently, there's 1243.67 times as many passwords as you can check.

[naschilling]

I have to admit, this is one of the best questions, albiet most random, questions I've ever heard.

According to Tom's Hardware using a single modern computer with a few beefy graphics card, they can check around 1,000,000 (10^6) passwords per second. For a moment, let's try to crack that 160-character password with that. It should not surprise anyone that 10^226.4 passwords checked 10^6 passwords per second would need 10^220.4 seconds to crack it. For comparison, the CURRENT age of the universe is 10^18 seconds old, and the OP cites that the maximum age of the universe is 10^100 years, which is 10^107.5 seconds. It doesn't look like we'll make it.

Using the processing rate of 10^120 calculations so far that your cite, it would produce 10^102 calculations per second. Multiply by the maximum age of the universe (10^107.5 seconds) and you get 10^209.5 calculations, which is less than the 10^226.4 passwords that are possible.

Maybe if we built a better universe...

[MHD]

<Off topic post>

I must compliment the OP.
Keep doing this and you will go far

Also, welcome to XKCD.

</Off topic post>

[queerismyfavouritecrayon]

Since you're assuming you can do 10^223 passwords, you'll only be able to try 0.04% of the possible passwords. Equivalently, there's 1243.67 times as many passwords as you can check.

Wow, you would actually have a lot higher chance of cracking it than I thought! To me a 1 in (1243.67 / 2) chance or even a 1 in 10,000 chance is not a "negligible" chance. See, I told you I didn't know anything about cryptography!


A few more problems:

Someone told me that when I subtracted "(26^160 / 2) - (10^223)", I should have divided them (but coincidentally I got the same result anyway? huh?)

They also pointed out that if you are using 256-bit encryption, an attacker would just go for the key (1.16*10^77 combinations) rather than the password (26^160 combinations). I guess this could be resolved by using a key with more than 26^160 combinations, but to my knowledge you can't really implement this today -- nor use a password over 64-characters.

I don't really understand the physics behind Seth Lloyd's paper. I especially didn't consider this: just because so far the universe has performed no more than 10^123 operations doesn't mean its computation capacity will remain static for the rest of time. This is a major problem with any conclusions you might want to draw!

It should not surprise anyone that 10^226.4 passwords checked 10^6 passwords per second would need 10^220.4 seconds to crack it.

Actually, you would only need half as long.

see http://en.wikipedia.org/wiki/Password_strength#Entropy_as_a_measure_of_password_strength


I started off on this cosmic computer thought experiment because I saw a flaw in the standard "this password would take a 100 years to crack" line of thinking. (I wanted to find a password that would be truly secure for 100 years.) Those calculations don't account for Moore's Law, which means that the cracking time gets cut in half every 2 years. In 20 years, your "100-years safe" password will be crackable in 36 days!

I started off with contemporary supercomputers and distributed computing systems, then tried to factor in how long a password would be secure as these computers got exponentially faster. I started with (extremely optimistic) estimates for Moore's Law running out of steam in 80 years (http://www.physorg.com/news174750105.html) or 600 years (http://arxiv.org/abs/astro-ph/0404510) but quickly realized this was inadequate. Moore's Law only accounts for the increase in the processing speed of X amount of computing hardware (e.g. a PC, a supercomputer, $1000 worth of computing power, etc). If you only factor in Moore's Law, you are ignoring any possibility of the overall volume of computing increasing! You are not even considering that the world's population might increase, or that a higher proportion of the world's population might get computers. I think most people would agree: in the future, there will be more computers!

So, not only is the standard "this password would take X long to crack" woefully misguided, even if you factor Moore's Law into these calculations they still give you a false sense of security. Yakk, you were a lot more on the money by asking how many guess-attempts a Type II-civilization would be capable of. I didn't think of that, so I went after larger limits.

[Yakk]

You could also try using the future light-and-return-cone of your password, and factor in a cosmic inflation model. That'll give you a finite energy budget bound. You can use the increasingly chill CMB as a temperature limit. The amount of computation you can do may actually diverge, but it would be an interesting problem to work through.

[Thesh]

Someone told me that when I subtracted "(26^160 / 2) - (10^223)", I should have divided them (but coincidentally I got the same result anyway? huh?)

If you got the same result, you made a mistake.

They also pointed out that if you are using 256-bit encryption, an attacker would just go for the key (1.16*10^77 combinations) rather than the password (26^160 combinations). I guess this could be resolved by using a key with more than 26^160 combinations, but to my knowledge you can't really implement this today -- nor use a password over 64-characters.

That's actually not a problem. You can use an algorithm like Threefish which allows block sizes and keys up to 1024 bits. For 26^160, a 768 bit key will be large enough. This algorithm is probably too new to rely on right now, but there are other options as well.

Another thing you can do is expand the password to a 1280 bit key using a hash algorithm and encrypt each block multiple times. Encrypting five times with five different 256 bit keys is equivalent to encrypting once with a 768 bit key (more precisely log_2( 2^768+2^512) bits) due to a meet in the middle attack. The meet in the middle attack requires known plain texts, and you brute force decrypting one half and encrypting the other half until you find a match. This is generally considered infeasible for key sizes this large due to the storage space required, but if we are talking universe sized computers...


Also, I don't know the physics of that paper, however in the past I thought about necessary key length in this way:

If all the mass in the universe was converted to computers with the mass of an electron, and each computer could test 10^20 keys per second (arbitrary, chosen because that's around the frequency that gamma rays start), then you need a 400 bit key so that you can't brute force it in less than the current age of the universe. Then expand that to 512 bits, just because it's a power of two and adds an extra security margin in case the algorithm has a weakness.

[mfb]

Seth Lloyd does a bit more than giving a number: He gets a formula to calculate the possible number of operations for all times. It is \#ops \approx \rho \,c^5 t^4 / \hbar. As we already know the value for the current age of 10^10 years, it is easy to scale it up to 10^100 years: \#ops \approx 10^{480}. More than enough for the sms-sized password. The important point here is that with increasing age, we have a larger volume (~t^3) to do calculations in.
To reach 26^160 = 10^226 calculations, we have to wait for about 10^26 times the current age of the universe, so ~10^36 years. Chances are good that even if protons are unstable, most of them will survive long enough to finish your computation with something baryonic. Any ideas how to use that theoretical computing power in a controlled way?
Searching for the lower bound for the proton lifetime, my browser suggested visiting the URL http://de.wikipedia.org/w/index.php?title=Proton&stable=1

Maybe it is possible to crack every (reasonable, e.g. storable on computers) password in polynominal* time if time loop logic works.
*checking a password of some TB size with appropriate encryption algorithms will take some time, too.

[lightvector]

If the password cracking really can only be treated as a black box (that is, the only way is to literally just try each password), then this looks reasonable. Exponentiation is really really powerful.

But once you have a password with anywhere near this many bits, your primary weakness is not the lifetime of the universe, or a cosmic-sized computer, or any sort of exotic physical limits. Rather, the primary weakness is that someone will eventually discover an exploitable flaw in the underlying algorithm or system, allowing it to be cracked far more easily than brute forcing. If, for example, your password was hashed by ROT13, then you could have millions of letters, rather than just 160, and it still would not be secure.

Using a lot of bits or letters is easy. Establishing the security of the underlying cryptography is the hard part.

[WarDaft]

Maybe it is possible to crack every (reasonable, e.g. storable on computers) password in polynominal* time if time loop logic works.
*checking a password of some TB size with appropriate encryption algorithms will take some time, too.

Actually, with time loop logic, you can obtain any answer in time proportional to the length of the answer (because that's the minimum possible time to read the answer.) You just have to use time loop recursion.

[mfb]

I think you still have to check if it is the correct password - otherwise you cannot determine what to send back in time.
Ok, a trickier version of that would split up the check in several cycles of the same slice in time (or somewhere in the past or the future). But then you need polynomial computing power or polynomial integrated computing time.

And finally, linear is just a special case of polynomial. If it is linear will depend on the algorithm (good: not linear?).

[queerismyfavouritecrayon]

Seth Lloyd does a bit more than giving a number: He gets a formula to calculate the possible number of operations for all times. It is \#ops \approx \rho \,c^5 t^4 / \hbar. As we already know the value for the current age of 10^10 years, it is easy to scale it up to 10^100 years: \#ops \approx 10^{480}. More than enough for the sms-sized password. The important point here is that with increasing age, we have a larger volume (~t^3) to do calculations in.

Okay, I definitely missed that. Back to the drawing board.

[WarDaft]

I think you still have to check if it is the correct password - otherwise you cannot determine what to send back in time.
Ok, a trickier version of that would split up the check in several cycles of the same slice in time (or somewhere in the past or the future). But then you need polynomial computing power or polynomial integrated computing time.

And finally, linear is just a special case of polynomial. If it is linear will depend on the algorithm (good: not linear?).

Yes, you have to check that the answer is correct before you send it back to complete the loop. But that doesn't mean you can't use it in the mean time. The time to obtain the answer is thus always linear in the size of the answer. Even if the question is halts(x).

[mfb]

Well, with time machines, you can get the answer at any time - even before you get the problem. So in my opinion, the interesting quantity is the total amount of necessary calculations.

[queerismyfavouritecrayon]

Can anyone help me find a way to practically implement this? I was working on a toy version but ran into some immediate limits. TrueCrypt allows for a maximum of 64-character passwords. I generated a 2200-character password using pseudo-random and allegedly truly random data that I would like to use. Moreover, 2^256 < 10^480. I need something like a 2048-bit symmetric key.

[Thesh]

Well, if you do use a 2048 bit key, then you are going to run into a situation where it's much easier to brute force the key than the password. For your key generation, you can do something like this where + is concatenation:

Code: Select all

a = ""
x = sha512(password)
FOR i = 1 to 4
   x = sha512(x + password)
   a = a + x
ENDFOR


[queerismyfavouritecrayon]

Why is the key easier to brute force than the password?

[Thesh]

http://www.wolframalpha.com/input/?i=lo ... %5E2200%29

That 2200 character password is equivalent to a 10341 bit key. That assumes all lower case characters as used in your example. It will be significantly more if you allow uppercase, numbers, and special characters.

[Goplat]

Can anyone help me find a way to practically implement this?

When you're talking about making passwords strong enough to resist someone who can "turn the entire universe into a computer", practicality has already been thrown out the window. Anyone who has the resources to break even a 20-letter password by brute force (let alone 160-letter) will also have access to much easier means of getting whatever information you want to keep secret:

[queerismyfavouritecrayon]

True Goplat, but if it's relatively easy to implement a standard that is theoretically secured by physical limits, why not do it? Why keep incrementally upgrading encryption strength as Moore's Law goes along?

[undecim]

True Goplat, but if it's relatively easy to implement a standard that is theoretically secured by physical limits, why not do it? Why keep incrementally upgrading encryption strength as Moore's Law goes along?

You're assuming a few things:

1) That encryption is only broken by brute force
2) That a single operation of the universe corresponds to a single operation of conventional computers (think quantum computers)

[Thesh]

True Goplat, but if it's relatively easy to implement a standard that is theoretically secured by physical limits, why not do it? Why keep incrementally upgrading encryption strength as Moore's Law goes along?

Moore's law isn't our problem right now. Upgrading algorithms doesn't just mean increasing key length, it means providing protection from new cryptanalysis. 128 bit keys are more than sufficient to protect us from Moore's law for the foreseeable future in terms of brute force. For example, this is distributed.net's page for trying to brute force a 72 bit key in distributed.net:

http://stats.distributed.net/projects.php?project_id=8

3204 days so far, and they've searched less than 2% of the key space. Now, a 128 bit key has 2^56 times as many keys. So it will take you 72 quadrillion, 57 trillion, 594 billion, 37 million, 927 thousand and 936 times as long to brute force. Algorithms with 256 bit keys are common as well, so key length is definitely not a concern right now.

So how are algorithms broken? By finding weaknesses in the algorithm that allows you to recover the key or find an alternate algorithm to decrypt the ciphertext. This is what cryptographers are focused on preventing now, and this is far more important than key length. Now, it's easy to make an algorithm that is resistant to cryptanalysis, but the problem comes in that we not only need to be resistant to cryptanalysis, we also need the algorithm to be efficient. For example, you can easily take an algorithm and double the number of rounds, but in doing so you cut the throughput in half.

Now, even though you can't brute force a 128 bit key, there can still be advantages to going to a 256 bit key. If a flaw is found in the algorithm that allows key recovery, there is a good chance that it will take significantly longer to recover larger keys (but this is not always the case). For example, if an attack allowed a 128 bit key to be broken in 2^38 operations, the same algorithm with a 256 bit key might take 2^100 operations to complete. Also, if it's a known plaintext attack against a particular algorithm, when using a 128 bit key it might require a 2^20 known plaintexts to break while if you are using it with a 256 bit key it might require 2^48 known plaintexts.

Currently Twofish is a very fast algorithm in which there are no known breaks on more than 6 rounds (the full version as 16 rounds), so unless some major advancements are made in cryptanalysis the only way to break it is through a brute force.

[queerismyfavouritecrayon]

undecim: yeah, granted, brute force is not the only way to crack encryption keys or passwords. there are other forms of vulnerability we need to worry about, but why not at least get brute force defense right? In terms of passwords: at some point in my lifetime a 20-character alphanumericsymbolic password may be crackable in about 90 minutes. your second point ties into this: it is especially imprudent to use the minimal encryption you think you can get away with in your era because quantum computing might come along sooner than expected nullify all your security.

the first thing quantum computing would do would be to cut the keyspace it needed to search for your key/password in half. news articles often use the buzzphrase "a quantum computer could do more calculations in an instant than there are atoms in the universe". if we interpret this perhaps too literally as 10^80 calculations per nanosecond, and account for the keyspace being halved, we can begin to do a sketch calculation for what would be strong enough to withstand a quantum brute force attack. let's suppose that a quantum computer is in fact a universe of 10^80 processors that are each 1 billion times faster than all of the world's current top 500 classical supercomputers combined (i.e. each processor can do 60 quadrillion calculations per nanosecond). so a quantum computer, we are assuming, can do 10^80 * 10^80 * 60 quadrillion calculations per nanosecond. let's assume we have a supercomputing grid of quantum computers where each atom in the universe is a quantum computer. so our grid has 10^80 computers. our grid is capable of less than 10^374 calculations before Heat Death (see calculations, and feel free to point out errors: http://bit.ly/oZvqih). a 250-character alphanumericsymbolic password would have a negligible chance of yielding to that brute force attack (http://bit.ly/o2i43R). 4096-bit key, suffused with sufficient entropy (e.g. air turbulence recorded from microphone, mouse movement, atmospheric white noise) would also be safe (http://bit.ly/oUFZm8).

(EXTREME SCENARIO IF YOU'RE NOT CONVINCED: Now, every operation in each of the processors is a Seth-Lloyd-universe going from Big Bang to Heat Death: http://bit.ly/nJNUTv. A 600-char password would do: http://bit.ly/r8ArU8. You'd need to double your key again, to 8192 bits.)

4096 bits is four times as large as what Threefish does. 250-characters is a lot, but there are still practical applications for it, e.g. you can use a password manager on your desktop and email encrypted messages to an interlocutor, who also has a password manager on her hard drive that contains the 25-char password (you could apply this too arbitrarily long passwords, including the 600-char password from the extreme scenario). Say you're a political activist and you're worried about the NSA intercepting your messages through e-mail. Taking not-so-extreme measures, you can be sure that even an organization with the most extreme computing resources could not through brute force decrypt your messages. On a secure computer running Ubuntu, use an encrypted virtual Ubuntu operating system, and within that virtual operating system keep the password manager (also using 4096-bit encrypted, protected with a reasonable password, e.g. 80 alphanumericsymbolic characters) and encrypt messages. Assuming you don't need to keep messages, merely communicate, this will work. If you suspect there is a risk of your computer being apprehended, securely erase the virtual operating system (or, if you're in a hurry, just the password manager). If your interlocutor does the same, your entire exchange of messages -- even though the third party has a copy of each message -- gets thrown into a black hole, never to return. At least until someone cracks all the encryption algorithms you used, or reverse engineers the hash function(s), or exploits a weakness in the software.

Maybe this wouldn't be the best thing, though, because in a case of extortion you would have no way of meeting your extorter's demands or proving you didn't have the password anymore...

[Thesh]

Well, if you are going to do all that, why not just use a infinite improbability computer? No matter what your key length, I can describe a computer that can break it. As a more realistic (but still completely unrealistic) way to think of it is this: if you convert the mass of the observable universe to supercomputers with the mass of a neutrino (the lightest known massful particle) and they can all test one key for every unit of Planck time (theoretically smallest unit of time measurable), a 512 bit key is sufficient to protect against brute force over the age of the universe. With Grover's algorithm you might be able make a 512 bit key effectively a 256 bit key, and then a 1024 bit key is still sufficient over the age of the universe, but none of this matters in reality because computers of the speed I described will not happen ever.

[lojbrent]

at some point in my lifetime a 20-character alphanumericsymbolic password may be crackable in about 90 minutes.

Any clue how long that thing takes now on a standard computer. I was trying to crack a password on a Zip archive once. I had brute force app running about 30 sessions on a machine, one with 2 characters, one with 3, one with 4 and so on. That ran for 6 days I think without a single hit.

[wumpus]

at some point in my lifetime a 20-character alphanumericsymbolic password may be crackable in about 90 minutes.

Any clue how long that thing takes now on a standard computer. I was trying to crack a password on a Zip archive once. I had brute force app running about 30 sessions on a machine, one with 2 characters, one with 3, one with 4 and so on. That ran for 6 days I think without a single hit.

A 20 char password (assuming 32 possible characters) is 100 bits (120 if 64 possible characters).
This is roughly twice the size of DES. In 2008 the time to break DES on ideal hardware (RIVYERA) was one day (no idea if enough RIVYERA machines have shipped to break in 90 minutes, but assume that is close enough).
If it took 40 years to go from first chips to 56 bits, assuming Moore's law (note, there was a specific revision slowing it down in 1990, and it keeps getting more expensive to obey Moore's law) it will take another 40 years to brute force 112 bits.

It is essentially impossible to brute force anything approaching 56 bits on a PC (less sure about a GPU, but still very, very slow). Best best is on some sort of distributed system or botnet.

[WarDaft]

Graphics cards have been in the multi-teraflops range for a while now, so less than a day for sure.

[wumpus]

Stop worrying about brute force. Just stop it. Also cryptanalysis is also an unreasonable thing to worry about. Key theft and plain text theft is how cryptography is broken (nobody has liked to http://xkcd.com/538/ yet? for shame). 128 bits is enough for the next 50 years. 256 is enough for less "universal" computers (ones that assume that each electron in the universe stores one bit). When you hit public key crypto, all bets are off (they tend to work on solving a "known hard problem" where the "known hard problem" isn't exactly O(e^x). Higher order "elliptical" curve cryptography might fix this).

If you are new to cryptography, try heading over to http://www.schneier.com/ (oddly enough, it was that site that introduced me to xkcd). The first thing you need to know about cryptography, is that the whole point is to create a security system to protect a secret. There are a thousand ways to get at that secret, and brute forcing is the absolute hardest one. Not only that, if the key is big enough that you have to write it on a post it (or put it on a USB stick), it becomes as easy to lose as the proverbial "tippy top secret laptop left on a train". Your ubuntu loaded computer is an insecure joke next to brute force attacks; try using SELinux, openbsd stripped down to nothing but email, and only using it for secure communication (and don't trust the machine more than the safe it is kept in). PS. Don't forget the tinfoil (seriously, there is a reason the NSA requires such things to be put in a Faraday cage, although it is likely a cover to make people assume that they lost their data through some sort of high-tech system, not that they hired a nerdy IT type who fell like a ton of bricks for this really hot spy...).

The easiest method is to break into the location of one of the communicators and look for a handy postit. Few people can handily memorize 8000 bits* of entropy (there are 35 people listed who have memorized more than 2409 digits of pi, an equal feat. For 256 bits, the number is 77 or following the xkcd example 17 arbitrary words).

An adversary with an infintely powerful computer is likely to be able to mount a Tempest attack (determine the state of your computer via EMI emitted) much, much, easier than brute forcing. I would also assume that such a computer would be of immense help in performing cryptanalysis on whatever algorithm you are using. I would also assume that the google machines know enough about me (or anyone who surfs the net) to create a "knowable password space" that is quite possible to quickly exhaust (even worse, they could break into groups of "possible password sets" that allow greater parallelization to break the passwords of anybody believed to use passwords in that set).

Key management is also an issue. How in the world did you send your 8000 bit keys to everyone you want to securely communicate with? It is far easier to intercept them than any attempt at brute force.

As mentioned above, even using an oversized key is going to be an issue. I would assume you have to simply run each password through known cryptographic algorithm until you had used up all the bits in the password. I also have to point out that this is a place where you are going backwards. If a much smaller password can not be bruteforced (or otherwise guessed), it can be expanded to a much larger key.

As Thresh pointed out, cryptography can be more easily broken by cryptanalysis than by brute force (and by various means of key theft and plaintext theft far more easily than cryptanalysis). Creating a large key out of a hash of a password might be of some value as the attacker has at least the chance of determining the key from cryptanalysis. No idea if I'll have time to work on such an idea.

Finally, if you are still certain you want oversized keys, go google key leakage (might take a few more keywords) and find out how trying to hide a large secret (even inside of your computers registers) might be harder than trying to hide a smaller (say a 256 bit key) secret. Since brute forcing each is equivilantly difficult (i.e. both are impossible), this makes the 256 bit key *more* secure if it never has to cross back and forth from memory (of course this leave unanswered (how it the world is the key not cached?).

[wumpus]

Graphics cards have been in the multi-teraflops range for a while now, so less than a day for sure.

http://mytechencounters.wordpress.com/2 ... phic-card/

This was a year ago (unlisted GPU) and he was getting 8 characters in 18 hours. I'm sure that a 7979 (or two) should be able to get ~50-64 bits in under a day by now. Also new releases of the software here:
http://www.golubev.com/hashgpu.htm

[WarDaft]

He says 5770, so yeah, a 7979 or 6990 (I don't know which is best, tomshardware says a 6990 is better than a 7970 though) should be able to rip those values apart.

And that's using no intelligent strategy at all. A distributed GPU computation project could easily make a rainbow table that leaves 14 or 15 character passwords useless.

[korona]

A rainbow table for 14 character passwords (~70 bit key strength) has more than 10^20 entries even if you assume that the password consists only of lower case letters.

[WarDaft]

You can trade off entries with acceleration in order to gain fewer characters but maintain a usable table size. A 10 gb database could make the search about a billion times faster, and thus make passwords up to 5 characters longer as easy to crack.

[korona]

I doubt that there is a way to reduce the table size from 745'058'059'696 GB to 10 GB in a way such that you get any reasonable performance advantage over brute forcing; assuming a key length of 64 bit (which is pretty low) and only lower case letters.

[WarDaft]

However many entries you have in your rainbow table, you get that much of a speedup in your search. A billion evenly spaced entries is a billion fold speedup, but you still have to actually do all the work once.

[Thesh]

You aren't going to store every single password anyway. All you need to do is get a dictionary and hash individual words, combinations of words, and permutations (e.g. append numbers, capitalize, replace o with O, etc.). That takes care of most, of them.

Of course, all you need to do to protect against rainbow tables is use a 128-bit salt, and then you can easily make your passwords require 100ms to hash, making dictionary/brute force attacks take significantly longer. If all web programmers knew/cared enough to do this and implemented a reasonable password policy, the internet would be a safer place.

Also, on the topic of GPUs, I wouldn't imagine they would show a huge advantage, as most hashes are simple integer operations.

[WarDaft]

They're massively parallel, and can also do integer operations. Actually, these days, they're made to do all kinds of operations, because games are getting more demanding and the graphics card being able to do more than floating point operations is getting better and better.

The example above shows a 1000 fold improvement over just the CPU. It's not the most tightly controlled test, but that's about 15 years as far as Moore's law is concerned.