4 ms·

The problem is that you have no hints about what is correct or not because presumably a one way hash is being used, so even if you get the first 29 words right,

by phpnode 14y ago

The problem is that you have no hints about what is correct or not because presumably a one way hash is being used, so even if you get the first 29 words right, you don't know that. Assuming the cracker just uses a wordlist containing 200,000 terms and unsophisticated brute force, this thing could crack a 3 word password in a day and a 4 word password in 800 years[1]. It would certainly be an interesting project, but I honestly think this is a safe approach for now. [1] http://www.wolframalpha.com/input/?i=%28200000**4+%2F+63+billion%29+seconds http://www.wolframalpha.com/input/?i=%28200000**4+%2F+63+bil...

apawloski 14y ago
I know we've pretty much made our points by now, but my argument is that brute forcing at this level might be more feasible than what you suggest here (if we assume the sentence is correctly using a particular language). Say we choose one word from the 200,000 and it's a noun. Then we can make assumptions about the next word (eg it's likely a verb) and immediately the number of options for the next word collapses from 200,000 to a subset of some smaller cardinality. In fact we can use our knowledge of common English to restrict the next options down further -- to only verbs that make sense to this particular noun and that agree with the noun's plurality. So unlike current password brute forcing, where every character is independent of the others -- thus having exponential complexity -- brute forcing a sentence using current NLP methods could be much less expensive. Perhaps a hierarchical method exists that would scale at O(n log n). Anyway, this is just fun thinking. You're right that current password strategies are a long way away from making this type of cracking worthwhile.
- phpnode 14y ago
  I agree that you could potentially reduce the search space based on rules, but English especially is not well known for it's adherence to rules, see http://en.wikipedia.org/wiki/Buffalo_buffalo_Buffalo_buffalo_buffalo_buffalo_Buffalo_buffalo http://en.wikipedia.org/wiki/Buffalo_buffalo_Buffalo_buffalo... Conversations like this are why I come to hacker news.

by phpnode 14y ago

apawloski 14y ago

I know we've pretty much made our points by now, but my argument is that brute forcing at this level might be more feasible than what you suggest here (if we assume the sentence is correctly using a particular language). Say we choose one word from the 200,000 and it's a noun. Then we can make assumptions about the next word (eg it's likely a verb) and immediately the number of options for the next word collapses from 200,000 to a subset of some smaller cardinality. In fact we can use our knowledge of common English to restrict the next options down further -- to only verbs that make sense to this particular noun and that agree with the noun's plurality. So unlike current password brute forcing, where every character is independent of the others -- thus having exponential complexity -- brute forcing a sentence using current NLP methods could be much less expensive. Perhaps a hierarchical method exists that would scale at O(n log n). Anyway, this is just fun thinking. You're right that current password strategies are a long way away from making this type of cracking worthwhile.

phpnode 14y ago
I agree that you could potentially reduce the search space based on rules, but English especially is not well known for it's adherence to rules, see http://en.wikipedia.org/wiki/Buffalo_buffalo_Buffalo_buffalo_buffalo_buffalo_Buffalo_buffalo http://en.wikipedia.org/wiki/Buffalo_buffalo_Buffalo_buffalo... Conversations like this are why I come to hacker news.