Disclaimer
The views expressed on this website/weblog are mine alone and do not necessarily reflect the views of my employer.
Note to journalists and other readers: Unless you receive express written permission to the contrary from the author of the content of this blog/website, reproduction or quotation of any statements appearing on this blog/website is not authorized.
Wednesday, March 16, 2011
Forgotten Password and Birthday Attacks
I just stumbled over a piece of code that might be interesting for you as well. A web-app let's click you on a "forgotten password" link and will send a token to the (valid/known) email address you specified. When you return to the web-app and provide the token that was mailed to you, and the token was found by looking it up for ANY user, you are allowed to set a new password. So, theoretically (I didn't test it) this code is vulnerable to a birthday attack (random pair collision), the impact depends on the number of users and the length of the token.
For example, and I hope I get the math correct here, if the token is 8 bit long (8 bit of entropy, equally distributed) an attacker only needs to call the "forgotten password" functionality for 16 (birthday bound, 2^{n/2}) users and try 16 different tokens to have a probability of success close to 50%.
The solution is to look-up the user by email address or another unique identifier and verify if the token for this user matches or not.
Here is an example diagram for a 16 bit token (DNS TRXID) to compare brute force vs. birthday attack.
The birthday attack is so effective because the chance of a collision increases with each attempt. However, unless the web app allows more than one token per user, at some point you will have generated tokens for all users and the chance of a collision per attempt will be constant from then on. So a sufficiently long token (token space must be significantly larger than the number of users) with a one token per user limit would also be safe.
Solution: a.) Choose a token large enough to make brute-force attacks less interesting b.) Avoid the birthday attack by matching 1:1 instead of 1:n by also using the user-ID for the token look-up.
@cristian: Google does not find anything (except my blog entry) for "birthday attack forgotten password" Do you have any pointers?
3 comments:
The birthday attack is so effective because the chance of a collision increases with each attempt. However, unless the web app allows more than one token per user, at some point you will have generated tokens for all users and the chance of a collision per attempt will be constant from then on. So a sufficiently long token (token space must be significantly larger than the number of users) with a one token per user limit would also be safe.
Yeah, this kind of bug is pretty common in web applications.
what other kind of measures you suggest other than using >= 16 bit entropy and those you mention ?
I thought about some kind of HMAC where "secret" is known only to the application and bound someway to the particular user.
Solution:
a.) Choose a token large enough to make brute-force attacks less interesting
b.) Avoid the birthday attack by matching 1:1 instead of 1:n by also using the user-ID for the token look-up.
@cristian: Google does not find anything (except my blog entry) for "birthday attack forgotten password" Do you have any pointers?
Post a Comment