Email address timing attacks
Today, I found an interesting article about password timing attacks. The basic point is that if you check a password one character at a time, the amount of time it takes to recieve a "bad password" response tells you how many characters you got right.
As an example, imagine a computer that takes 1 ms to check each character of a password (and does everything else instantaneous, and has no other threads), using this function to validate passwords:
def compare_strings(expected, actual):
for c1, c2 in zip(expected, actual):
if c1 != c2:
return False
return True
If the attacker guesses a completely wrong password, it will take 1 ms. Once they get one character right, it takes 2 ms. Two correct characters takes 3 ms, and so on.
What this means is that once the attacker detects the time increasing, they know that the current character is correct and can move to the next one. It's basically a real-life Hollywood hacker situation — where an attacker can watch as each character of the password is broken.
The huge security problem is that the difficulty of breaking a password increases linearly with its length, rather than exponentially like we want. With a 7 character password made of up all lowercase letters, it would only take a maximum of 208 guesses (26 * 7) to figure out the password if it was vulnerable to this attack, while a non-vulnerable system would need about 200 billion guesses (267).
The defense against this attack is actually pretty simple — just check the entire string, even after you know that that it's wrong:
def compare_strings(expected, actual):
valid = 0
for c1, c2 in zip(expected, actual):
# Note: The 'and' operator short-circuits, which we don't want
valid += c1 == c2
return valid == 0
The good news is that string comparisons aren't generally a large part of your processing time, so it takes thousands of measurements to determine if there's any difference. The bad news is that even with a thousand measurements for each character, 208,000 is a much smaller number than 200 billion.
The other good news is that people who know what they're doing are comparing hashes, not passwords, so we're only leaking information about the hash. It's still dangerous though, since the attacker can try passwords faster than they're supposed to (if I know the hash starts with "5", I can hash all of the passwords in my dictionary, and only try ones where the hash starts with "5" too).
Anyway, this got me thinking: What about user names? In any website where usability is important, user names are email addresses (or at least, email addresses can be used to log in). But, user names are even more vulnerable to an attack like this. Most people would consider it low priority, since all you could learn is that someone registered for a website using a particular email address, but it leaks private information, so it may be important in some cases.
The reason there's a timing problem is that it's wasteful to hash a password if I know that a user named doesn't exist, so most sites would skip hashing the password if they don't need to:
def login(username, password):
user = get_user_from_db(username)
if user is None:
return False
return check_password(user.password, password)
If your password hashing algorithm is any good, this login function will spend significantly more time attempting a login for a valid email address, so an attacker could determine email address validity with as little as two (fast) requests.
The method I've though of to handle this is meant to do two things:
- Make user name validity uncorrelated with time spent validating a login.
- Don't waste server time hashing a password if you already know the user doesn't exist.
The obvious solution is to guess how long hashing the password will take and do an asyncronous wait until that point before returning an invalid response, but that's would be pretty difficult to get right, and would depend on way too many variables (like how fast your computer is and the load).
The idea I had is.. If making all of the times the same is too hard, why not make them all different? My solution is to wait a random amount of time, based on the user name:
def login(username, password):
user = get_user_from_db(username)
valid = user is not None and check_password(user.password, password)
some_number = hash(username)
time.sleep(some_number)
return valid
Just design your hash function so a user name is hashed into a single number in a range significantly longer than the amount of time it takes to hash a password. The server doesn't have to work, since it's just sleeping (realistically, you want to do an asynchronous wait so the thread keeps working), and from an attacker's perspective, the amount of time it takes to check a login has nothing to do with if the user name is valid.
Example: Checking a password takes 10 ms, and your user interface guidelines say you must return a response within 500 ms. Set up your hash function to return a random number between 0 and 490 ms. If a response takes 100 ms, is the email address valid? At that point, it's a lot less work, and just about as accurate for an attacker to just guess.
The reason we generate a hash of the user name instead of just picking a random number is that with a random delay, you could take a large number of samples and do a regression test to determine if the difference between validating two different user names is statistically significant. With this method, the difference between any two user names' validation times is statistically significant, whether or not either of them is valid. A large number of samples would just tell you what the delay's range is.
There is the downside that at the very bottom and top of the range, the attacker gets valid information — if the response takes less than 10 ms, then it's definitely an invalid user. If it took more than 490 ms, it probably is a valid user (not certainly though, since there could be other delays).
I figure this system is better than nothing, but I'm definitely interested if anyone can think of something even better.
EDIT: Apparently most OpenID providers are vulnerable to timing attacks on their signatures. and apparently an older version of OpenSSL could actually leak certain private keys. So, this is very relevant if you're crazy enough to write your own security code.
