Using a Simple Big-O Analysis to Defeat Unhashed Password Checking Functions

[ryoh]

In preparation for the CTF series I want to work on I've been watching some videos of other people's processes.  I highly encourage everyone to watch this one and appreciate its subtleties. 

https://youtu.be/_m_LY7JO9MM

 

For those of you that didn't watch it (go back and watch it), the guy in the video has a vulnerable image from vulnhub.com called "pandora".  He runs a portscan on the image and finds that the admin left himself a backdoor on one of the ports.  after connecting to the port it prompts for a password. Mr. Hacker then tries all the common passwords (sex, secret, god, lol), and then wonders to himself: "Hmm... is this vulnerable to a timing attack".  The rest of the video is of him coding a short python script to exploit the port.  This was the first time I've ever heard of a timing attack, and I have knowledge of most vulnerabilities.  So at first I wondered if he was either (1 a genius, or (2 had prior knowledge and wanted to look cool.  Turn out though that this problem falls into an entire subclass of exploits of the genre "timing attack", and this one, in particular, is possible because of comparison functions running in O(n) time.

 

What is a timing attack?

Quote

In cryptography, a timing attack is a side channel attack in which the attacker attempts to compromise a cryptosystem by analyzing the time taken to execute cryptographic algorithms. Every logical operation in a computer takes time to execute, and the time can differ based on the input; with precise measurements of the time for each operation, an attacker can work backwards to the input.[1]

On wikipedia that certainly sounds complex, and I'm sure in some cases it can be fairly complex.  But for our purposes all you need to understand is that:

• Computers execute instructions to get things done
• Computers take time to execute those instructions
• Depending on how long it takes we can make assumptions

 

Meat and Potatoes of this simple magic trick

Every password comparison function at some point needs to compare the inputted string, to its saved value for the password.  Here's some psuedo code for how this works:

for letter1 in input_string:

     for letter2 in correct_stored_password:

          if letter1 != letter2: return False

return True

Notice that on the first letter that doesn't match, it goes ahead and returns False. No point in wasting time right?  This is actually the problem.  Don't be distracted by the for loop. this function does indeed run in O(n) time where 'n' is the length of the string.  One problem: 'n' doesn't equal the length of the string, it equals the number of letters in the string that are correct because otherwise the function immediately returns. And this is how the timing attack works. While checking the password, the computer will look at the first letter, and compares it to its stored value.  If it's incorrect it will display invalid password and return, but if the first letter is correct it must at least check one more letter before returning! Hence the closer your guess, the further the computer looks at you string, and the longer it should take.

Note: in the video the guy actually does the opposite: he immediately starts looking for a letter that is rejected faster: characteristic of an invalid letter.   He was not the first person to work on this image, and someone else had already posted their results first (you can no longer find a link).  In reality, when looking for timing attacks you perform take an average of all the compute times and find an outlier.  And outlier is more useful than just looking for what takes a longer or shorter amount of time because you don't know what the backdoor is written in, and you don't know how the code is optimized.  What's more, this is the only way to detect if the code is doing hashing behind the scenes. In other words, this dude cheated for views and made you watch 30 mins of him being shitty at python before trying to wow you with his magic trick. Now back to the post.

When Mr. Hacker decided that he would use a timing attack you could say he was using some lateral thinking.  Would an administrator lazy enough to write a backdoor instead of setting up ssh actually take the time to hash the function?  The answer here is no. A timing attack such as this one wouldn't have worked if the password was hashed before comparison because, in all the commonly secure hashing functions, slight changes in input have drastic effects on the output. Consider this image:

Even changing one letter completely changes the resulting hash.  So this makes a timing attack impossible.

 

Conclusion:

This attack should work everywhere a linear comparison function is used and is not offset by a confounding function like a hash.  This includes not just passwords prompts but also guessing games, finding cheat codes etc...

 

Edited July 29, 2018 by ryoh