Take the 2-minute tour ×
Information Security Stack Exchange is a question and answer site for Information security professionals. It's 100% free, no registration required.

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?

share|improve this question
    
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
add comment

1 Answer

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 2v precomputation, where v is the number of variables in the SAT instance. In contrast, Hellman's time-space tradeoff and rainbow tables require a 2n 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.

share|improve this answer
    
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
show 1 more comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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