# Known password length, brute force character in place?

We all know that brute forcing is a very slow process and trying all unnecessary possibilities is dumb. By knowing the password length, we can skip trying possibilities of other password lengths and saves us huge amounts of time. Still this change is insignificant for very long passwords. So I was wondering if we can brute force every character in place. It would be like cracking a combination for a mechanical lock. We try every character in place until it "clicks" into place, then we move on to the next character, and so on.

-
Not for properly digested passwords. – Stephen Touset Oct 11 '12 at 23:56
Have you ever seen a login screen that said "you only got one letter wrong, keep trying!"? – QuasarDonkey Oct 12 '12 at 0:23
JtR factors in trigraph frequencies when brute-forcing, i.e. it would try "bac" before "abc", since the first is a more common combination in English. That's not so dumb, but it's still brute force. – QuasarDonkey Oct 12 '12 at 0:27

If you have a password verification mechanism which lets you know, in any way, whether a given letter is correct or not, independently of the others, then you have an awfully weak, stupidly designed password verification mechanism. That's what happens when you let Hollywood scenarists deal with reality.

This board game is an illustration of how bad it is: if a letter "clicks into place", as you put it, then your password can be beaten by an 8 years old kid from the early 70s (and without any computer at all). I strongly hope that login screen security has increased a bit beyond the Disco kid security level.

-
+1 for the board game :-). It's interesting to note that some padding oracle attacks retrieve the plaintext message one byte at a time. Tom Ptacek calls this "Hollywood style" cracking. – David Wachtfogel Oct 12 '12 at 3:31

You could if the password verification is done very badly. Namely if the password verifier does all of the following:

1. The password verifier stores the passwords in the clear (and not hashed as they should be)
2. The password verifier compares the guess and the password directly (and not a hash of the guess and the password)
3. The password verifier behaves differently depending on which character the password check fails on
4. The password verifier doesn't limit the number of bad attempts

The first condition is the most important. If the implementer of a password verifier stores clear passwords, it's unlikely that they've gone to the trouble to implement a secure password comparison algorithm.

It's sad to say, but there are a surprisingly large number of Internet sites that store passwords in the clear. PlainTextOffenders.com is a (Tumblr) blog dedicated to "outing" such sites and contains many hundreds of such sites.

If a service stores passwords in the clear then it is likely that it is susceptible to a form of side channel attack called a "timing attack". If the password verifier checks one character at a time and returns a password failure message when it encounters the first non-matching character then you can guess one character at a time (starting from the first) and based on the timing of the failure message identify each character. Due to the inherent noisiness of Internet communication timing you would need to try each possibility more than once, but it still would be substantially faster than a simple brute force attack.

-
I call this "you can compare plain-text timing over internet" bullshit. Are you aware that byte-to-byte comparison of plain text hardly even takes 0.00000000001 second? How you propose to compare it with 0.001s delay even on LAN, with real WAN delays around 0.1-0.5s with huge (compared to comparison time) fluctuation between those? – Oleg V. Volkov Oct 12 '12 at 13:51
That's why I wrote you would need to try each multiple times - to cancel out the noise. This has been done succesfully by many reseachers - for example, please see rdist.root.org/2010/07/19/exploiting-remote-timing-attacks. – David Wachtfogel Oct 13 '12 at 19:13
@OlegV.Volkov Besides Nate Lawson's work I linked to in my previous comment, there's also this paper, cs.rice.edu/~dwallach/pub/crosby-timing2009.pdf, which states that time differences as small as 20 microseconds can be detected over the Internet. – David Wachtfogel Oct 13 '12 at 21:22
No matter how much you try you simply can't "average" delay that is 10+ orders larger than what you want to measure. First paper talks about HMAC, not plain text and 20ms, just as I've already said is billions time more than it takes to compare two plain-text strings. – Oleg V. Volkov Oct 13 '12 at 22:54
@OlegV.Volkov That quote is taken out of context. Their analysis was done on a customer application but is based on simulated real world applications. I know for a fact that this attack is possible in the real world because I've actually done it on a test system. – David Wachtfogel Oct 14 '12 at 13:03