17

Since I was a teenager (that's 20 years ago) and till now-days you see movies with professionals stealing a super-computer and use it to crack a password or a home security system using brute-force (I assume). However they always demonstrate by showing them trying to crack a pin or a password that consists of many digits/characters and the super-computer cracks the fields one by one

enter image description here

The green digits on the left have been cracked, the ones on the right yet to come. The super-computer tries to figure out the first digit then the second and so on, you see the numbers keeps fluctuating till it's get locked on the right digit.

Does such attack even exist?

marked as duplicate by Xander, schroeder, TildalWave, D.W., SilverlightFox Sep 10 '14 at 16:35

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • 7
    Yes, in Hollywood :) – BadSkillz Sep 10 '14 at 9:51
  • 4
    Padding oracle... – KristoferA Sep 10 '14 at 9:51
  • Timing attack? – sq33G Sep 10 '14 at 11:15
  • @sq33G - Timing attacks are very unlikely, because you would measure time differences comparing the hash and not the password itself. Have a look at this question. – martinstoeckli Sep 10 '14 at 12:54
  • The only way I could think of this happening is if the attacker is very unlucky and always tries the actual character last. (So after a while the first 9 is fixed because 0-8 have been eliminated). Of course you would then typically see an incredible speedup as each number will be found n times faster than its predecessor. -- In theory you could see this in a movie but only in situations where the time between found numbers is not indicated. – Dennis Jaheruddin Sep 10 '14 at 13:00
29

What you see in the movies is a plot device to ratchet up tension, every time a character is determined it gives the audience a kick. Reality is a bit different.

Brute-force attacks do exist, however it's all or nothing - you either get the whole passcode right or wrong. There's no way to know whether you have guessed a correct character. Passcodes are typically hashed, where changing a single digit will return a completely different cryptographic result. You could get all but a single character right and you wouldn't have any indication you came close.

So real password cracking might be a bit boring from a movie point of view, where you need to show progression to maintain audience interest. What they could do is show a progression bar for the calculation of all possible permutations of a hash, but it wouldn't have a predictable end time - you could get lucky and hit it right away, or get it towards the end of your brute force range. Not necessarily good for a movie but a good director could pull it off.

  • 1
    Maybe the movie takes place in a USA where the export of cryptography way more restricted and it is illegal to hash the keycode AND the implementation happens to be vulnerable to Timing-Attacks. That way you can find out the the keycode character by character if I am not mistaken. Though, I am most likely mistaken :p – Darsstar Sep 10 '14 at 10:12
  • 16
    The only caveat to this answer is that it assumes the system has been implemented properly. If, for some reason, the system somehow leaked information that confirmed each character individually (possibly through timing) then it might be possible. – Chris Murray Sep 10 '14 at 10:12
  • 7
    There have been systems that have been broken by timing attack because at some spot they used something like "candidate_password == true_password" and the speed of comparison sightly depended on how quickly a mismatch was found. No serious system should have such situations now (as plaintext passwords wouldn't be even stored), but there definitely will be some old systems still running that are vulnerable to a similar attack. Anyway, that wouldn't look like in the movies since each such attack would be tailored to a particular system, not just attaching a "bruteforcerizer" to a random system. – Peteris Sep 10 '14 at 11:03
  • 1
    > however it's all or nothing - you either get the whole passcode right or wrong Generally true, but there are some implementations that, unfortunately, validate parts of a passcode at a time. Most well-known is WPS, which validates each half of an 8-character passcode independently (and makes it trivial to brute-force). – Bob Sep 10 '14 at 12:07
  • 1
    Another good example of leaks resulting in a gradually reducing keyspace (essentially similar to the movie) is seen in WEP. The mechanism has a flaw that produces "Weak IVs" occasionally, and these events result in leaking a little information about the key each time. By combining information from these weak IVs with brute force once the keyspace is small enough, WEP is trivial to crack. In general, with a properly configured system, it is indeed all or nothing. Like Lawnmower Man. Except no 3D nonsense. – user24313 Sep 10 '14 at 12:24
16

Blind SQL Injection is one such example. Assume you have the possibility of SQL injection but you're limited in what you can inject. Something in lines of:

SELECT id FROM users WHERE username = <foo>;

You can inject into foo but you can get no other output than the page returning 404 (if there's no such user) or something else (if there's a result). You can't get any output from this query other than the status of the page ("works / doesn't work").

In this situation you could try to guess some data about the user (like his hashed password or his credit card number) in this way:

SELECT id FROM users WHERE username = "kos" AND secret = "mellon";
SELECT id FROM users WHERE username = "kos" AND secret = "rosebud";

Once you get a page that loads, you know that you have guessed the password correctly.

Now for the fun part: To guess in a resonable time, you can switch to binary lexicographical search:

SELECT id FROM users WHERE username = "kos" AND secret >= "a" AND secret <= "z" -- 1
SELECT id FROM users WHERE username = "kos" AND secret >= "a" AND secret <= "n" -- 0
SELECT id FROM users WHERE username = "kos" AND secret >= "o" AND secret <= "u" -- 0
SELECT id FROM users WHERE username = "kos" AND secret >= "v" AND secret <= "x" -- 1
SELECT id FROM users WHERE username = "kos" AND secret >= "w" AND secret <= "x" -- 1
SELECT id FROM users WHERE username = "kos" AND secret >= "x" AND secret <= "x" -- 1

You have the first letter! Continue:

SELECT id FROM users WHERE username = "kos" AND secret >= "xa" AND secret <= "xz" -- 1
SELECT id FROM users WHERE username = "kos" AND secret >= "xa" AND secret <= "xn" -- 1
SELECT id FROM users WHERE username = "kos" AND secret >= "xa" AND secret <= "xg" -- 0
SELECT id FROM users WHERE username = "kos" AND secret >= "xh" AND secret <= "xk" -- 1
SELECT id FROM users WHERE username = "kos" AND secret >= "xj" AND secret <= "xk" -- 1
SELECT id FROM users WHERE username = "kos" AND secret >= "xk" AND secret <= "xk" -- 1

... and so on, until you know all the letters.

8

Windows LM hashes had this mechanism where the password was divided into 7 character strings and hashed separately. In that case the password is revealed in 2 halves. But LM hashes ended with Windows XP.

Extending the same mechanism, just to theorize, if each character of the password were hashed separately and the final hash were a concatenation of the individual hashes, then there could be scenario close to the one you see in movies where the password is revealed character by character. But this is too far from practicality.

  • I believe the googleword for these is NTLM. It's a rather interesting saga of bad design, worth looking up for people who enjoy that sort of thing. – dig Apr 3 '18 at 5:22
6

Yes it is possible if you use for example timing attacks. If the password is not hashed and compared with a vulnerable string compare, you can measure if you put in the correct characters one by one. In most languages the string compare stops when a difference is found, or the strings have different lengths. This is normally a good thing, because it results in much better speed. If you want to do that without the possibility of a timing attack, you normally compare until the end of the strings, and only set a boolean if you encounter a difference, which you return at the end. Additionally you have to be careful with optimizations of your program, so it doesn't get changed to the shortcut version.

There is also an padding oracle attack, where you can guess each byte of the key by comparing different responses of the server, like "Invalid key" and "Invalid message".

  • Assuming that the password is hashed with an appropriate algorithm, you could only measure time differences comparing the hash, not the password, so you get no useful information. – martinstoeckli Sep 10 '14 at 12:52
  • 2
    That's why I wrote "If the password is not hashed [..]" – Juri Robl Sep 10 '14 at 12:54
  • Ahh yes, i just ignored that part, you are right then. – martinstoeckli Sep 10 '14 at 12:55
  • 1
    +1 for mentioning the padding oracle attack – James_pic Sep 10 '14 at 12:56
2

You can use this method in SQL injections using UNION query. The method consists of bruteforcing char by char the server and make it sleep if the character is correct. So when the server is long to answer, you know that the character is correct. The method you're talking about made me think of that.

  • You are talking about time based blind SQL injections. It is used to enumerate the database character by character. Not for cracking the password – user1720897 Sep 10 '14 at 11:15
1

In the past, and with primitive password systems, there have been cases where something like that could have worked.

Imagine a system where you enter a password, and some code checks that password character by character until it finds that all characters match, and it returns with success. Or it returns rejecting the password as soon as the first character fails. You could then try a timing attack: If you guess the first character right, then two characters would be checked, which takes a tiny tiny bit longer than checking only the first character. A clever system will always check all the characters, so rejecting any invalid password always takes exactly the same time.

There was a variant, where an attacker stored a password just before the end of valid memory. So the first character was in valid memory, but there would be a crash if the password checker tried to read the second character. So the attacker just tries 256 possibilities for the first character until they get a crash. Then they move the password one position away from the end of memory and wait for a crash when the second correct character is checked, and so on.

I sincerely hope that nobody uses that kind of password check anymore.

If I remember correctly, DVDs use a scheme where things are protected by some 40 bit key, but this can be changed into cracking one 25 bit key first, and then one 16 bit key (or 24 and 17). 25 bit keys are obviously a lot easier to crack with brute force than 40 bit keys.

  • Not security related, but the Node.js HTTP server used to validate requests this way (up until very recently). If someone made a PUT request, they could also make a PET request since the second character E was valid for GET as well. – Brad Sep 10 '14 at 14:03

Not the answer you're looking for? Browse other questions tagged or ask your own question.