4 ms·

Markov chains can do amazing things in password cracking: https://arstechnica.com/security/2013/05/how-crackers-make-minced-meat-out-of-your-passwords/ https://

by gwern 10y ago

Markov chains can do amazing things in password cracking: https://arstechnica.com/security/2013/05/how-crackers-make-minced-meat-out-of-your-passwords/ https://arstechnica.com/security/2013/05/how-crackers-make-m... But an RNN isn't necessarily going to help as much as you think. An RNN has two problems compared to a Markov chain: 1. Markov chains memorize strings very very easily, accurately, and scalably; it's easy to memorize phrases, words, suffixes, and prefixes from the existing corpuses of billions of passwords. That's all a Markov chain does, memorize & count. On the other hand, an RNN will struggle to do so because there's no 'place' for it to put all of that, everything has to be encoded into the fixed set of neural net weights, otherwise, it just doesn't know about it; and the more you ask it to learn, the more the competing demands fight each other. RNNs augmented with external memories might help fix this but are still cutting edge research. 2. Markov chains are also very fast, far faster than an RNN. Multiple orders of magnitude difference are possible, unless you use a RNN so small as to be irrelevant (since then it can't memorize anything). For cracking hashes, a small gain in plausibility of guesses is not worth being able to make hundreds or thousands times fewer guesses (unless perhaps the hash are something proper like bcrypt/scrypt where it takes seconds to check, in which case the guessing phase takes up a much smaller fraction of runtime and better guesses may be worthwhile).

matrix2596 10y ago
Nice explanation. Thanks Its more from a theoretical point of view. I want to try similar (conditioned on user info) to https://github.com/thoppe/5baa61e4c9b93f3f0682250b6cf8331b7ee68fd8 https://github.com/thoppe/5baa61e4c9b93f3f0682250b6cf8331b7e...
ma2rten 10y ago
Actually RNNs/LSTMs are surprisingly good at memorizing in addition to generalization. Have a look at the famous blog post "The Unreasonable Effectiveness of Recurrent Neural Networks" [1] for instance and notice how many words it's able to generate from characters. However, your second point is valid. [1] http://karpathy.github.io/2015/05/21/rnn-effectiveness/ http://karpathy.github.io/2015/05/21/rnn-effectiveness/
- gwern 10y ago
  That's not 'surprisingly' good, that's effective only on a small corpus. You can see for yourself that if you try to feed it multiple corpuses with many vocabulary words or proper names, which a Markov chain wouldn't break a sweat on memorizing them all, the RNN has limited memorization ability and what tends to happen is that the less common ones get overwritten in favor of the general grammar of English and the vocabulary of the largest corpus: https://www.gwern.net/RNN%20metadata https://www.gwern.net/RNN%20metadata
  - ma2rten 10y ago
    If I understand you correctly you are comparing Markov Chains on words to a RNN over characters. That's not fair. This paper shows a large LSTM outperform n-gram models: "In this paper we have shown that RNN LMs can be trained on large amounts of data, and outperform competing models including carefully tuned N-grams. [...] Unlike previous work, we do not require to interpolate both the RNN LM and the N-gram, and the gains of doing so are rather marginal." https://arxiv.org/abs/1602.02410 https://arxiv.org/abs/1602.02410
    - gwern 10y ago
      > If I understand you correctly you are comparing Markov Chains on words to a RNN over characters. That's not fair. No. Words have nothing to do with it. (An RNN over words would be useless for password guessing.) Anyway, your link doesn't demonstrate what you think it demonstrates. It's not on a password corpus but a much smaller natural language one, there is no attempt to equate runtime or model size, and the log-likelihood is an irrelevant measure of performance to passwords/s.
      - ma2rten 10y ago
        If words have nothing to do with it then I am not sure how your link shows that Markov Chains are better at memorizing, because a Markov Chain over characters would do a much worse job at generating coherent text. But I actually acknowledged your second point, so I never said that RNNs are useful for password guessing, unless maybe you have a very expensive hash function. However, they are good at memorizing sequences and log-likelihood is not an irrelevant measure of performance on passwords. It measures ability of the model to generalize to unseen data. In this case that means generating realistic passwords that are not in the training data. That is important because otherwise you might as well just use a dictionary attack.

by gwern 10y ago

matrix2596 10y ago

Nice explanation. Thanks Its more from a theoretical point of view. I want to try similar (conditioned on user info) to https://github.com/thoppe/5baa61e4c9b93f3f0682250b6cf8331b7ee68fd8 https://github.com/thoppe/5baa61e4c9b93f3f0682250b6cf8331b7e...

ma2rten 10y ago

Actually RNNs/LSTMs are surprisingly good at memorizing in addition to generalization. Have a look at the famous blog post "The Unreasonable Effectiveness of Recurrent Neural Networks" [1] for instance and notice how many words it's able to generate from characters. However, your second point is valid. [1] http://karpathy.github.io/2015/05/21/rnn-effectiveness/ http://karpathy.github.io/2015/05/21/rnn-effectiveness/

gwern 10y ago
That's not 'surprisingly' good, that's effective only on a small corpus. You can see for yourself that if you try to feed it multiple corpuses with many vocabulary words or proper names, which a Markov chain wouldn't break a sweat on memorizing them all, the RNN has limited memorization ability and what tends to happen is that the less common ones get overwritten in favor of the general grammar of English and the vocabulary of the largest corpus: https://www.gwern.net/RNN%20metadata https://www.gwern.net/RNN%20metadata
- ma2rten 10y ago
  If I understand you correctly you are comparing Markov Chains on words to a RNN over characters. That's not fair. This paper shows a large LSTM outperform n-gram models: "In this paper we have shown that RNN LMs can be trained on large amounts of data, and outperform competing models including carefully tuned N-grams. [...] Unlike previous work, we do not require to interpolate both the RNN LM and the N-gram, and the gains of doing so are rather marginal." https://arxiv.org/abs/1602.02410 https://arxiv.org/abs/1602.02410
  - gwern 10y ago
    > If I understand you correctly you are comparing Markov Chains on words to a RNN over characters. That's not fair. No. Words have nothing to do with it. (An RNN over words would be useless for password guessing.) Anyway, your link doesn't demonstrate what you think it demonstrates. It's not on a password corpus but a much smaller natural language one, there is no attempt to equate runtime or model size, and the log-likelihood is an irrelevant measure of performance to passwords/s.
    - ma2rten 10y ago
      If words have nothing to do with it then I am not sure how your link shows that Markov Chains are better at memorizing, because a Markov Chain over characters would do a much worse job at generating coherent text. But I actually acknowledged your second point, so I never said that RNNs are useful for password guessing, unless maybe you have a very expensive hash function. However, they are good at memorizing sequences and log-likelihood is not an irrelevant measure of performance on passwords. It measures ability of the model to generalize to unseen data. In this case that means generating realistic passwords that are not in the training data. That is important because otherwise you might as well just use a dictionary attack.