Using Ordered Markov Chains and User Information to Speed Up Password Cracking
fsecurify.com
fsecurify.com
https://experts.illinois.edu/en/publications/personalized-pa...
I mean, I understand that computers managed by typical users will be a shitshow, but much of the problem in that situation is that they don't really care.
The encryption scheme on iOS is nice, but for how much of a game they talk about privacy Apple had the opportunity to do so much more for security around identity/auth and they did approximately nothing.
Whether you like this implementation or not, the solution is to choose better passwords.
If somemone (burglar / law enforcement / intelligence agencies) breaks in, they have your passwords.
If you are memorizing a lot of passwords (I have 500+ in my password database) you are surely going to forget rarely used ones.
If passwords are written down, they can be demanded from you by a warrant/court order. If they are memorized, they cannot.
If your passphrase is an innocuous phrase, like "red dogs like spicy food", how will they you know you have a password to demand? How do they know you have a piece of paper instead of having it memorized?
Previously I tried to memorize passwords. I ended up forgetting a lot. It was frustrating trying to remember what my password was, or even whether I had an account on the site or not. The user experience of being able to ctrl+f through all the accounts that I have in my database is very refreshing.
I have a quite high value video game account, and 6 people have specifically targeted me. They've attempted various things, such as trying to exploit password reuse, and utilizing previous website database breaches that I was in.
I don't see what benefit the paper would have. Whether it's paper or a password manager, if my computer is compromised they'll get my accounts with a keylogger.
I've never lost my wallet, but my brother lost his a couple months ago. I never really change my passwords except when I was switching from my old crap password to unique strong passwords in my database. The problem with losing my wallet would be that I would lost access to all my accounts if that was the only copy of the paper. It would be an availability problem.
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).
Its more from a theoretical point of view. I want to try similar (conditioned on user info) to https://github.com/thoppe/5baa61e4c9b93f3f0682250b6cf8331b7e...
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."
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.
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.
Over n-grams, it would not, as some of the responses to Karpathy's post noted, by posting Markov chain text which is of high quality. The char-RNN shows its greatest ability in matching syntax and recusive structures and in modeling the subtler aspects of English grammar, syntax, and semantics... which are all useless in password guessing. (For example, I could only tell the difference between the Markov chain and char-RNN C source, because the char-RNN understood the nesting of syntax, but not between the Shakespeare.)
> 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.
No, it measures a particular loss function proportional to the mean log probability. In password guessing, the loss function is zero-one: you care only about guessing a single exactly right password. You get zero points for generating a realistic password which is one character off. Being able to model the distribution of 'e's slightly better is irrelevant compared to being able to memorize common birthday suffixes and guess a few more passwords per second. Having a better log likelihood on a natural English language corpus is measuring the wrong thing on the wrong data.
> you might as well just use a dictionary attack.
Exactly. This is how the best password crackers work: mix-and-match memorized literals, prefixes, and suffixes extracted from dumps of billions of passwords. A Markov chain is a souped-up dictionary attack demonstrating 'The unreasonable effectiveness of big data'.
Sorting wordlists by some kind of metric should improve performance.