Security Appetizer (Outline)

Note: the “testing” link is actually to my prep, which contains a more completed and commented example of this attack.

Note: this used to work with ==, but for 2024 I just wrote our own little string equality check to make the demo smaller. These notes still refer to ==; see the code! (Also, see the comment for my guess about why == doesn’t allow this naive demo attack. If I’m right, we could adapt my code so it worked with ==…)

I’m not including the name of the attack in the title, in case this gets expanded into notes someday. The name of the attack spoils the exercise! This demo is a small example, and isn’t meant to be fully “real”. However, the problem it shows can be leveraged into real attacks on real systems.

Checking Passwords

Suppose we need to check whether a password matches one we have in mind. A basic approach would be to write a function that uses string equality:

# Helper function that tests whether a user is authenticating correctly
def can_login(entered: str) -> bool:
    return entered == password

This seems to be a natural thing to do. We have the password in the system, in some safe place. The person trying to log in can’t see the real password value. If they don’t have it, they can always try to log in repeatedly and make guesses (unless the system limits the number of tries you get, as some do).

How do you think that string equality is implemented?

Suppose the real password is "computer", and the entered value is "commercial". How do you think that == is actually implemented on strings?

It’s probably something like a for or while loop that scans through the string character by character. Since whoever wrote the __eq__ function for strings probably wanted good performance, it probably returns false as soon as a mismatch is found. Something like:

if len(s1) != len(s2): return False
idx = 0
while idx < len(s1):
    if s1[idx] != s2[idx]: return False
    idx = idx + 1
return True

How could we attack this password?

We could always write a big for loop that tried every possible password combination. If we had passwords consisting of only 26 lowercase letters, there are 26^10 possible 10-character passwords (and more if we include digits, etc.). That’s 141 trillion tries needed. So probably this sort of “brute force” attack won’t be very useful.

But we can still make guesses and try them. The question is whether we can learn anything from our bad guesses.

What do we learn from a failed attack?

Run the password-checker function on some input. It fails. What did we learn?

We learned False, sure, but what else? We learn some timing information.

Can we exploit that?

Let’s see exactly how long it takes to run the password check on "computer" vs. "commercial". Now, how about "computer" vs. "Brown university"?

Both take a very small amount of time. We can’t really tell the difference, even though we know that the first comparison did more work. And, anyway, there are a lot of other factors involved in how long it takes to do the comparison, right? (E.g., automated memory management.) So maybe we can’t actually use the timing information…

Why should you learn a little probability and statistics?

Here’s one reason: if we try the experiment enough times, through random noise, we might see the signal more strongly!

Let’s try 1000 iterations.

How should we combine these? Average? Not super great.

What else might we use? Keep in mind that we’re trying to catch when the check is running quickly, regardless of noise.

Minimum! Yeah, let’s try that. And…wow, it’s much better.

Isn’t that just the first character of the password?

How could we leverage this attack into a full password crack? Recursion!