Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Using Ordered Markov Chains and User Information to Speed Up Password Cracking

fsecurify.com

Post reply on HN
Print view View original

51–60 of 64 posts

Re: Using Ordered Markov Chains and User Information to Speed Up Password Cracking

#51

Post by ma2rten »

gwern wrote: post #48
ma2rten wrote: post #47

Earlier quoted context omitted.

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…

> 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-…

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.

Re: Using Ordered Markov Chains and User Information to Speed Up Password Cracking

#52

Post by Buge »

__ddd__ wrote: post #46
Buge wrote: post #43

Earlier quoted context omitted.

They can court order you to produce all relevant documents. They don't have to know that the document exists to order you to do it. You could lie to the court that the document doesn't exist, but I wouldn't recommend that.

Well if you're willing to compromise on security by trusting a password manager / encrypted volume (plus user opsec) to store your passwords, there are other compromises one can make to facilitate easier memorization. Security by obscurity is a worthless feature when designing a cryptographic system, but it is an invaluable tool for your own personal opsec. Reuse some passwords for services with a lesser threat model…

Like you point out, my everyday desktop is already not very secure. I use most of my high value accounts fairly frequently. So most of my accounts would be compromised regardless of what password scheme I use. Installing an open source password manager doesn't lower my security by much.

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.

Re: Using Ordered Markov Chains and User Information to Speed Up Password Cracking

#53

Post by robin_reala »

Buge wrote: post #40
__ddd__ wrote: post #36

Earlier quoted context omitted.

Random pass phrases written in uv marker on the underside of your desk, in a notebook (bonus: you can burn it once memorized) scrambled and/or hidden among decoy passphrases. Make the phrase long enough (high enough entropy) that you have enough time to memorize it and use it before it should be rotated. Whether you like this implementation or not, the solution is to choose better passwords.

If your house burns down, you lose your 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.

Specifically that’s true for US law. Under UK law memorised passwords can be demanded with prison sentences for failing to produce them. It also doesn’t count at the Us border.

Re: Using Ordered Markov Chains and User Information to Speed Up Password Cracking

#54

Post by Etheryte »

gravypod wrote: post #38

Can we make a characteristic scoring metric to help order password cracking attempts? Is there a standard distribution of characters in passwords that can be analyzed?

Every password guessing optimization is about finding logically linked character distributions in passwords.

Re: Using Ordered Markov Chains and User Information to Speed Up Password Cracking

#55

Post by amelius »

Buge wrote: post #39
tmalsburg2 wrote: post #25

Earlier quoted context omitted.

Correct me if I'm wrong but if you install a malicious application, aren't you screwed anyway, password in clipboard or not?

On desktop yes. But on mobile, where every app is sandboxed to some degree, not necessarily. Keepass2Android prevents clipboard attacks by installing a keyboard that autotypes your password, never letting it get to the clipboard.

Interesting approach. But keyboards are quite personal (some people choose their keyboard), and there's quite a lot of technology in keyboards (gestures to text, learning dictionaries, et cetera), so I'm wondering about the quality and user-friendliness of the approach.

Re: Using Ordered Markov Chains and User Information to Speed Up Password Cracking

#56

Post by gravypod »

Etheryte wrote: post #54
gravypod wrote: post #38

Can we make a characteristic scoring metric to help order password cracking attempts? Is there a standard distribution of characters in passwords that can be analyzed?

Every password guessing optimization is about finding logically linked character distributions in passwords.

I still think wordlists are the easiest generic way of brute forcing passwords en-masse since most people still don't use password generators or aren't as uniuque as they think they are.

Sorting wordlists by some kind of metric should improve performance.

Re: Using Ordered Markov Chains and User Information to Speed Up Password Cracking

#57

Post by landryraccoon »

Buge wrote: post #52
__ddd__ wrote: post #46

Earlier quoted context omitted.

Well if you're willing to compromise on security by trusting a password manager / encrypted volume (plus user opsec) to store your passwords, there are other compromises one can make to facilitate easier memorization. Security by obscurity is a worthless feature when designing a cryptographic system, but it is an invaluable tool for your own personal opsec. Reuse some passwords for services with a lesser threat model…

Like you point out, my everyday desktop is already not very secure. I use most of my high value accounts fairly frequently. So most of my accounts would be compromised regardless of what password scheme I use. Installing an open source password manager doesn't lower my security by much. Previously I tried to memorize passwords. I ended up forgetting a lot. It was frustrating trying to remember what my password was, o…

See, for your video game accounts imo writing down your password is just a no brainer. Unless you're protecting your account from family members or roommates, nobody is going to steal a piece of paper. And what government agency cares about your video game passwords? If they want to get into your blizzard account they'll just ask blizzard for access.

Re: Using Ordered Markov Chains and User Information to Speed Up Password Cracking

#58

Post by [deleted] »

Buge wrote: post #52
__ddd__ wrote: post #46

Earlier quoted context omitted.

Well if you're willing to compromise on security by trusting a password manager / encrypted volume (plus user opsec) to store your passwords, there are other compromises one can make to facilitate easier memorization. Security by obscurity is a worthless feature when designing a cryptographic system, but it is an invaluable tool for your own personal opsec. Reuse some passwords for services with a lesser threat model…

Like you point out, my everyday desktop is already not very secure. I use most of my high value accounts fairly frequently. So most of my accounts would be compromised regardless of what password scheme I use. Installing an open source password manager doesn't lower my security by much. Previously I tried to memorize passwords. I ended up forgetting a lot. It was frustrating trying to remember what my password was, o…

[deleted]

Re: Using Ordered Markov Chains and User Information to Speed Up Password Cracking

#59

Post by gwern »

ma2rten wrote: post #51
gwern wrote: post #48

Earlier quoted context omitted.

> 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-…

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 sequence…

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

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

Re: Using Ordered Markov Chains and User Information to Speed Up Password Cracking

#60

Post by x1798DE »

amelius wrote: post #55
Buge wrote: post #39

Earlier quoted context omitted.

On desktop yes. But on mobile, where every app is sandboxed to some degree, not necessarily. Keepass2Android prevents clipboard attacks by installing a keyboard that autotypes your password, never letting it get to the clipboard.

Interesting approach. But keyboards are quite personal (some people choose their keyboard), and there's quite a lot of technology in keyboards (gestures to text, learning dictionaries, et cetera), so I'm wondering about the quality and user-friendliness of the approach.

You only use the keyboard to enter the password, not in general. When you open the database and select an entry, it offers to switch to the password keyboard for you, then when you are done you switch back.
Post reply on HN