# How will security need to be changed if we can crack password hashes in quasi-polynomial time?

If we suppose that we have access to some form of generalized password hacking/cracking that can somehow find an n-bit password in time O(n^(log n)), is there need for alarm?

This question arises from some research I'm doing on SAT, the Boolean satisfiability problem. Another StackExchange question detailing a possible outcome can be found here. In short, I'm trying to determine if it's possible to solve SAT in quasi-polynomial time.

This question naively assumes that it may be possible to somehow use SAT, along with some suitable transformation of the problem, to hack passwords in relatively the same amount of time.

The time boundary stated above may unfortunately be a fairly naive assumption of the actual performance of an algorithm, which may be able to run much faster in practice. To get to this point, I am really wondering if we know some sort of threshhold (in terms of speed) where password hacking begins to get dangerous?

-
How would SAT solving translate into password cracking? Are you talking about password cracking against a black box (online attempts) or through a hashing algorithm (in which case, which hashing algorithm)? – Gilles Sep 23 '12 at 19:44
@Gilles: I'm trying to get at a worst-case scenario. I'm not totally certain which scenario would make password cracking the easiest. Using a hashing algorithm, according to D.W., seems to be the most direct and serious threat, but I'm not totally sure which hashing algorithm to use. I'm just trying to determine if this (the speedup to quasi-polynomial SAT solutions) would pose a serious threat. – Matt Groff Sep 23 '12 at 20:11
The problem of finding the password, given a password hash, can be phrased as an instance of SAT. Any SAT solver that is faster than trying all possible inputs would imply a faster method to crack passwords, given their password hash. SAT is only relevant if you know the password hash. If you're talking about online guessing attacks, SAT has no relevance, and a fast SAT algorithm wouldn't help you (you can't cast that problem as an instance of SAT). It's likely all moot, though, as the chances of finding a fast SAT solver for this kind of problem are thin to none. – D.W. Sep 23 '12 at 20:19

I think the best way to answer your question is to say: the premise is highly implausible, so the issue simply does not arise.

I might as well ask: if we suppose that we discover time travel, is there cause for alarm about password security? Sure, if we discover time travel, someone could travel back in time, appear poof just before I enter my password, look over my shoulder when I typed my password, and poof disappear before I notice.

Or, if my computer can time-travel on demand, I can set it up to iterate the following loop: pick a random password guess, try to see if it is correct, if it is correct print the password and halt; if it is incorrect travel back in time to the beginning of the loop and start over. If time-travel algorithm is possible, this is an O(1)-time algorithm to crack any password, given its password hash!

But of course these answers are silly, because for the foreseeable future there is no realistic likelihood of anyone discovering how to travel back in time. Similarly, for the foreseeable future there is no realistic prospect of someone discovering an algorithm to solve all SAT instances efficiently. Sure, if someone could find a SAT-solving algorithm that could solve every SAT instance in 15 seconds, then they could crack every password (given its password hash) in 15 seconds. But I don't think that's terribly likely to happen in my lifetime.

P.S. I see from clicking on your link that you would probably prefer a more technical answer. My suggestion is to read up on Hellman's time-space tradeoff and on rainbow tables; that will give you a better understanding of the state-of-the-art methods applicable to password cracking. You might also want to read up on why rainbow tables are not applicable to salted passwords; similar reasons are likely to apply to your methods.

-
Beyond my answer, it is also important to mention the difference between asymptotic complexity and practical efficiency. We might have an algorithm that runs in O(n^100) time; from a theoretical perspective, that is polynomial time, but in practice it is useless. Or, we might have an algorithm that runs in O(n^3) time; from a theoretical perspective, that is polynomial time, but if the constants hidden by the big-O notation are huge, the algorithm might be completely useless in practice. This is a somewhat different reason why quasi-polynomial time doesn't necessarily imply practical danger. – D.W. Sep 23 '12 at 20:03
If we suppose that there are only very small constants hidden by the asymptotic notation, and that we actually analyze this "implausible" scenario, could we come up with a more specific scenario where there could be some risk? – Matt Groff Sep 23 '12 at 20:17
`<tinfoil>` But the NSA might already be doing this! `</tinfoil>` – Polynomial Sep 23 '12 at 21:36
Let's hope that they, as well as other security organizations, are helping avert the problems! – Matt Groff Sep 23 '12 at 21:53
@MattGroff, OK, I provided more technical details about why I don't expect your method to pose a risk in practice. – D.W. Sep 23 '12 at 22:24

Let me only quote your two actual questions and put the SAT things to the side...

If we suppose that we have access to some form of generalized password hacking/cracking that can somehow find an \$n\$-bit password in time \$O(n^{\log n})\$, is there need for alarm?

If we assume that to be true for sake of a thought experiment, then yes, we are clearly in trouble, since any and all passwords in the world will be simply irrelevant. Compared to cracking a password hash, it is relatively easy to actually get your hands on said hash. It's not like everybody would instantly know everybody elses password, but it would be bad.

I am really wondering if we know some sort of threshhold (in terms of speed) where password hacking begins to get dangerous?

Do you mean a "moral" hacker (not cracker) should stop to hack at some point? The opposite is true, as far as I'm concerned. If people stop hacking on this stuff because they fear they get too close to a solution, then there will be other, less morally inclined crackers who will not stop. The "benign" hackers are the only ones who can point out potential dangers and at least try to get any kind of warning up front.

-

This one got a really high question vote.

Anyway, if true, than storing password hashes ~= storing plaintext passwords. Now consider what security demands would be in place for storing plaintext passwords.

In case it isn't blindingly obvious, use of completely different passwords for each site is now required, and this means using a password manager or writing passwords down. And that assumes the underlying crypto that protects SSL survives (it shouldn't).

-