A little game to demonstrate timing attacks.
carlos.bueno.org
carlos.bueno.org
The bug was that you could align the given password string so that it was at the end of a page boundary, and have the next page in the address space mapped to a non-existant page of a write-protected file. Normally, Tenex would create a page when you tried to access a non-existant page, but in this case it couldn't (since the file was write-protected).
So, you did a password-checking system call (e.g. the system call which tried to obtain owner access to another directory) set up in this way and you would get one of two failures: Incorrect Password meant that your prefix was wrong, Page Fault meant that your prefix was right but that you need more characters.
If the user record does not exist, you should still perform a check against a precomputed bcrypt hash that uses the same work factor as a real one, but throw away the results. This will incur the same performance penalty as a real check but won't leak information. This assumes that your login doesn't leak info already from saying "Sorry, that user does not exist" but instead says "Invalid username and/or password".
With regards to attempts to brute force a password, it's going to be slow with bcrypt and a sufficiently high work factor. However, you can improve this by implementing IP address banning. More than X failed attempts within Y minutes gets you a Z minute timeout period which you can easily implement in your database.
To prevent distributed attacks on a single account, if an account has more than M failed attempts within N minutes suspend the account and send the account owner an email with a reactivation link. The reactivation link must be designed to be immune to the above attacks as well. When clicked, the system should temporarily ignore the account suspension status from their IP address only, subject to normal failed attempt banning.
Password reset links should similarly not reveal whether or not an account exists, but send an email to the requested address anyways. For example, the email could read "A password reset was requested for your email address [foo@example.com] but an account with that email address does not exist in our system". IP-based banning should apply to the password reset email as well to prevent someone flooding everyone on the internet with emails from your system. If someone has to try more than 10 email addresses to find their own account, their IP address should get banned and they should be prompted to call or email customer service for assistance.
Corrections and/or other login tips appreciated!
Avoid the pain and burn the CPU cycles for all code paths. If you find that bcrypt takes up proportionally too much CPU, reduce the work factor by 1 until it's acceptable. Keep in mind that the vast majority of logins will be legitimate. For the small number that aren't and persist with failed attempts, let their IP get banned then you don't need to spend any CPU cycles dealing with them -- in this case, it would be fine to sleep an arbitrary amount of time and then display the banned notification.
It would be a bit of a hack compared to just using bcrypt every time, but it would save processing power, which may be useful in some contexts, like very energy-efficient devices, etc.
You seem to only be considering the case where the only logins you need to deal with are invalid logins. A busy and successful service will see the vast majority of logins being for legitimate, known users where the bcrypt check must consume CPU time. You have to design the system to be able to handle the workload from both good and bad logins without revealing information about a bad login to an attacker. Anything other than going through the same motions every time will leak information in ways you don't expect.
Also, there is no reason to implement an extensive backlog in the first place. It's far better for a system at 105% load to drop one in ten attempts than to have an infinitely growing queue.
And then you think so what? There's no way an attacker can use that because all requests are transmitted over the internet where latencies are way, way bigger than a few clock cycles, right?
Wrong. Using statistical analysis over a vast amount of requests you can find out which ones execute a few clock cycles faster than others, and then you're home free.
Lesson learned: I'm not smart enough for security. :-)
>... even though the Internet induces significant timing jitter, we can reliably distinguish remote timing differences as low as 20µs.
Say I give you these results:
*
* *
*
* *
*
*
* * *
* * * *
* * * *
*
* *
* * *
* ** *** *
* * ** * * *
* *
* * * * *
* * * *
* * *********
********** * *
* * ** * *
* * * * * * *
** * ** * * * *
* * *** * **********
*************** * *
* * ** ** * * *The devil's in the details.
General a way to compare the passwords (chunks of memory) would be memcmp or strcmp. The default versions of these functions break out of the checking loop on the first inequal byte.
Unless they're using a cryptographically safe memcmp (which should XOR the memory to 0 or similar), the speed of the computation will vary based on how many leading characters match between hash(supplied password) and hash(saved password).
If the hash function is known, the attacker could use a chosen set of plaintext that they know give a different leading value once hashed. One of these inputs will take slightly longer than the rest. The attacker now knows the first byte of the hash. They repeat the previous step as many times as computationally possible (it will get harder to find inputs such that hash(input) starts with a chosen substring as that substring increases in length).
Then finally, using the known start of the hash value, use a dictionary attack to reduce the number of searches to a minimal set (by dropping all entries from the dictionary that don't start with the precomputed hash substring)
If your backend fetches the user by username and then compares the password, a timing attack can be used to tell whether an account even exists by seeing if the 'compare returned password hashes' check is performed.
This is noticeable on sites (that I have developed at least) that use bcrypt which purposefully takes a moment to hash and then validate the password.
In order to not reveal the username exists (by returning the 'invalid login' error quickly), I have a bcrypt compare operation performed on a hard-coded 'Ignored Password' when no valid user exists, so that the 'compare password hashes' cost is always paid.
The time taken to hash or not is definitely noticeable, but unless you take steps to avoid it, even the string comparison of hashes can leak timing information.
Edit: As noted in an earlier comment, below. Whoops.
Also, this shouldn't even be a source of information if the password is salted and hashed to a fixed length before storing. I'd hope any secure system was at least doing this to start with anyway.
Our work analyzes the limits of attacks based on accurately measuring network response times and jitter over a local network and across the Internet. We present the design of filters to significantly reduce the effects of jitter, allowing an attacker to measure events with 15-100µs accuracy across the Internet, and as good as 100ns over a local network.
With the paper available at [1]. Nate Lawson and Tyler Nelson also did a Black Hat presentation on remote timing attacks ([2] and [3]). Bottom line is that if you're interested in using a timing attack, and you've got some effort to throw at the problem, remote ones are feasible.
[1] http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.65.9...
[2] http://rdist.root.org/2010/07/19/exploiting-remote-timing-at...
[3] http://www.youtube.com/watch?v=idjDiBtu93Y&feature=relat...
The quotation I provided conveys instead the idea that computing is not only about a particular tool of computers.
Do you have or know kids? I'd be glad to send you a copy to show to them.
If you've a copy to spare ...
Sorry if you find my forwardness offensive.
email addr in profile.about
It may be that the sample chapter wasn't representative of the rest of the book, but I found it a bit confusing. From an admittedly quick read, I got:
- commentary on jargon - a mention of red-black trees - reference to the Traveling Salesman Problem
What I found confusing is that if you have no grounding in CS, you wouldn't even catch the references - they don't seem to play a real part in the story.
If the traveling salesman were trying to find the shortest route to visit everyone, and had been trying for years and years and years on his own, and some days found one that was just a little bit shorter, and it was just enough hope to keep him going...the idea that figuring this out is difficult or impossible is at least well-explained.
I'm sure my algorithms teacher is upset by this, but I've completely forgotten how red-black trees work, and I didn't get a better understanding from that chapter.
I'm not trying to be an armchair critic, and I certainly like the story, but from this particular chapter I'm not completely clear on how it explains CS concepts.
There's a (very early) draft of a later chapter available: http://carlos.bueno.org/2011/01/tortoise.html
I do not actually explain red-black trees in the book, nor most of the things the Jargon say. There is a lot of ground to cover and I stuck to the stuff I understand best.
Being entertaining is a tough challenge as it is. Trying to be entertaining _and_ informative, and you're unlikely to accomplish both. That was my biggest challenge as an EFL teacher - I spent most of my time planning activities trying to be engaging and informative. Even then, I'd say only ~30% of the time did I really get the balance right in my lessons and that's in an active media where I can react to the class.
If its just meant to be a bit of fun with a topic then its a different thing. Perhaps its better described as a pop sci book for children. Like how Brief History of Time didn't go into detailed maths, but gave the reader a working mental model of complex phenomena in an interesting way. Perhaps Lorem Ipsum aims to give children that mental model of computation, without any expectation that they could reasonably apply it. Is that the sort of thing you're aiming at?
Edit: I just read through (http://carlos.bueno.org/2011/01/tortoise.html) extract you mentioned, and am a lot happier with it. You do have a really good way of personalising problems so that its about people all the time. I really like that, because that's something that is extremely important with children (and some adult learners). I remember I first groked multi-dimensional arrays from this MS-BASIC book I found in the school library, where it was explained by a large red jellybean jumping on this grid. I never understood the C-language book that dad gave me. That jumping jellybean was easy to understand.
I don't have any kids of my own. My cousin has young children, the oldest is just turning 7 in a few weeks. I think concepts like the sum of an infinite series might be a struggle for her at that age, but it would be very interesting to see what she and her brothers make of it. email is in my profile.
1st attempt - 1 second sleep
...
nth attempt - n^2 second sleep
Something of that nature.
[edit] - the sleep time INCLUDES the time required to process the login credentials
If HN did this, I could theoretically have a ton of bots attempt to log in to your account, thus pushing your login timer ever higher, and making your login attempt fairly frustrating and slow.
Ideally you want something like 3 seconds per password per IP starting the timer before you look up the password.
t1 = time();
/* Perform login credentials check, if okay return */
loginattempt = n;
sleep(n^2 - time() + t1);
In other words, the sleep time includes the time it took to process the login info.
can anyone not familiar with the matter actually understand the idea proposed on the 1st paragraph?
I think I'd render it like this (not the prose, the situation):
Jane is not too bright. She picks a password by pulling a page out of her one-word-on-a-page dictionary. Lauren writes her guess at the password on a pad. Then Jane compares the guess and the password one letter at a time. Jane rejects the password as soon as she meets a letter that doesn't match. It takes her about 2s to compare each letter. Lauren is allowed as many guesses as she likes.
I think that works as suitably unrealistic but understandable example of a timing attack? For bonus marks (advanced readers) you could calculate the expected time before Lauren cracks the password.
Turns out it's very straightforward to use statistical analysis to get rid of the noise and adding a little more doesn't do anything useful. The most reliable way to throw off the attacker is to make sure you do the same amount of computing in every case.
"It's stuff like this that makes building secure systems very hard."
Please do not use Markov chains to construct posts or refrain from commenting on things you do not actually understand.
I did not claim that I'm an expert in cryptography, but I will tell you that my graduate course in formal cryptography has taught me enough to explain something as basic as key strengthening.
So, mukyu, perhaps you'd like to fill us all in with your detailed explanation of the number theory behind the Blowfish key schedule.
Do that enough and you get your info.
It is not that it is impossible technically , it is that it is no longer possible to use the crack to good effect [ie "practically"].
Do you still disagree - I thought it was a truism that increasing attempts meant the crack could become impractical.
You only have to calculate the random average once, and you anyway need to collect lots of timing data.