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

Question

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?

Answer 1

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.

Looking at the complexity of the method in your link, I see your method requires a 2^v precomputation, where v is the number of variables in the SAT instance. In contrast, Hellman's time-space tradeoff and rainbow tables require a 2ⁿ precomputation, where n is the number of bits of the password (the number of bits input to the hash function). In the password setting, n is going to be much smaller than v, so rainbow tables and Hellman's time-space tradeoff look like they will perform better than your method. In other words, it doesn't look likely to me that your method -- even if it is valid -- will beat the state-of-the-art at password cracking or will have much relevance to password cracking in practice. Of course, you could always try it in a little experiment, and compare your method to existing password crackers; that would be the true test. But at the moment, I see no reason to expect advances in SAT solving that would be relevant to password cracking.

Answer 2

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.

Answer 3

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

Answer 4

Yes, quasi-polynomial time cracking or passwords would probably lead to greatly increased number of security intrusions. Password cracking by brute force is already done, when hackers are desperate enough to wait for an exponential-time algorithm. If hackers could crack passwords in quasi-polynomial time, they would crack even more passwords. Of course, they need to have access to the password dictionary so that they are not shut-down by the number of password attempts. The number of password attempts allowed is typically a constant, so even quasi-polynomial cracking would run into blocks unless the hackers had the dictionary.

Forgive me, are there not standard reductions from SAT to de-encryption applications? It seems like a reduction which should exist in the literature. Since encryption itself is reduced to SAT via NP-completeness, the cracking algorithms also use the same reduction. Please consult your CS theory textbook for poly-time reductions being used to prove NP-completeness. A poly-time reduction can certainly be used to transform a psuedo-poly time SAT algorithm into a password cracking algorithm for encrypted passwords, since poly time is faster than pseudo-poly time.