Hacker News new | past | comments | ask | show | jobs | submit login
A little game to demonstrate timing attacks. (bueno.org)
215 points by aristus on Oct 26, 2011 | hide | past | web | favorite | 68 comments



The same idea was used in a real-world attack. It used to be possible on the Tenex system in the early seventies to recover a password by laying out an attempted password across a page boundary, and observing whether the checker incurred a page fault.

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.

[ via http://www.win.tue.nl/~aeb/linux/hh/hh-4.html ]


Use bcrypt, with a caveat. Lookup the user record and get their password hash. Then check to ensure the supplied password matches the pre-existing hash. The speed of the computation will only vary based on the length of the supplied plaintext password and leaks no more information than has already been supplied.

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!


"The speed of the computation will only vary based on the length of the supplied plaintext password and leaks no more information than has already been supplied."

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)


Reading this discussion on bcrypt and timing attacks, I have a question. Aren't systems like these designed so that even someone who has access to the hashed password, the randomly created salt and the hashing algorithm cannot find the password? If timing attacks help in some way, doesn't this mean some small compromise for this goal? Bruteforce attacks can of course be done faster by someone who has access but this seems to be independent from timing issues.


Exactly. Someone hacks your server, downloads your entire database containing email addresses and bcrypt-hashed passwords. They can plow through these at full-speed on their own system and will be limited to calculating a handful of hashes per second due to the computational intensity of calculating the bcrypt hash. Compare this to MD5 where they can generate tens of millions (or more) hashes per second, salt or no salt.


While using bcrypt is a good idea, why not just (also?) add a short (~0.5 second?) delay before responding to 'bad username/password' reply? This has the advantage that you aren't burning CPU cycles.


There was a fantastic article a year or more ago on HN about a vulnerability in a standard library where some loop in a function returned as soon as it failed, which means that the more wrong your hash guess was, the quicker it executed, but the difference was only a few clock cycles.

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. :-)


Here's the HN submission for that article. http://news.ycombinator.com/item?id=2780248


Possibly the most damning sentence (for adding pauses rather than doing it right) in the whole thing is a quote to another research paper:

>... even though the Internet induces significant timing jitter, we can reliably distinguish remote timing differences as low as 20µs.


Okay, then instead, tack on a random amount of time.


Random is no different, it just takes more samples. An example:

Say I give you these results:

       *
     *     * 
                *   
  *        *
              *
No real pattern, yea? So sample some more:

       *
     *     *  *
        *       * * *
  *   *  * *
              *
Maybe nothing. So try more:

       *                *
     *     *  *
        *    ** *** *
  * * ** * *     *
        *      *
And more:

    *  * *    *    *
     *     *  *  *
    *   *   *********
  **********    *  *
   *   *  **  *   *
Zomg. You have a discernable behavior. Adding more randomness would just give you the same easily-visible results after adding, say, 2x as many points, at which point you have this (expanded a little):

    *  *  * *  * *    *
     **  *  ** * * * *
    *   * *** * **********
  ***************    *  *
   *   *  ** ** * *   *


Because if the 0.5 second delay is even marginally different than the amount of time it takes to actually run bcrypt, the attacker could tell the difference between valid/invalid usernames. Unless that 0.5 second delay comes from an extremely precise (and fresh) measurement of how long bcrypt takes to run, it's just as bad (if not worse) than doing nothing at all.


Why not just time the checking function and then round it off to 0.5 seconds? So, regardless of how long the actual checking took, the function would pad with a sleep() call to 0.5 seconds. This sounds like it would work for everything...


Why bother? Odds are that a call to sleep(500) vs. sleep(500 - bcrypt_time) is going to be subtly different depending on timer resolution for your platform and so on. An attacker might be able to bog down your system through other means such that the difference becomes statistically significant or such that bcrypt takes longer than 500ms, then you're not only worse off but you wasted the time it took to implement something that only sounded like it was going to be good enough.

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.


My earlier comment (which was for some reason downvoted) also solves this problem: you will always sleep for half a second, timer resolution is irrelevant, and if an attacker bogs down the system such that bcrypt takes longer than half a second, when the timer finished it would notice that bcrypt wasn't done and treat it as a failure.

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.


So if your system is heavily loaded, nobody will be able to login if bcrypt takes longer than half a second? If processing power is an issue, there are alternate solutions such as dynamically lowering the work factor (upon successful login, rehash the plaintext password they supplied using a decreased work factor) or offloading logins to a pool of servers.


Well, in this instance you wouldn't need any work factor, since it would always take half a second. And if a zero work factor hash is taking half a second to complete, something is very wrong... But granted, for almost all cases it would be best just to bcrypt in every circumstance.


A bcrypt work factor of 10 or 11 on a recent CPU will take about a tenth of a second to hash. Assuming little other workload, you can get about 10 valid logins/second before you'll hit a backlog. If your app is busy and the logins/second increases you'll eventually reach half a second per hash time. If you always return failure when the timer expires and bcrypt hasn't finished, you're doing a denial of service on your own users.

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.


You can limit it to only checking X hashes per second. The attacker can, under heavy load, figure out how many people are trying to log in, but that doesn't help them figure out any passwords.

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.


Just set a half-second timer, run bcrypt (or don't), and then respond when the timer goes off.


Login forms often try and hide whether you guessed a valid username or not by reporting invalid username and/or password.

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.


There's usually an easier way to check if a username exists - skip the login form and try the signup form. If you can't sign up with that name because its taken, then it exists :)


Hence, signup forms tend to have CAPTCHAS more often than login forms. Also, it's easier to insert an artificial per-signup-form submission delay under the guise of "setting up your account". An artificial delay upon login might be annoying, but during signup it's not as painful (seeing as it's a one-time thing).


I would have optimized your last paragraph - "Why don't you hash the given password, and then check for the user, and then their password hash?" and then realized I was in error.

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.


Since bcrypt uses a random salt, the approach that I think you are suggesting (hash the input pass, check the user, and then strcmp the hashed pass in the database with the hashed pass from user input) would not work. Try bcrypting the same string repeatedly and you'll see that the same string produces different output each time.


Maybe I'm missing something here, but if the password is being checked on a remote system, then the variance in network transfer time is going to far, far (by many orders of magnitude) outstrip the difference in time a CPU takes to compare a few characters in a string.

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.


Surprisingly, with sufficient samples you can filter out the jitter that comes with transit time, and still execute a timing attack. From the abstract:

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...


If controlling for network jitter was impossible ntpd would be useless outside of the local LAN or rs232 cable.


That's my thought too. If you're susceptible to this kind of attack the problem is the lack of basic salting + hashing to create a fixed length password.


Off-topic, and not really a complaint, but the moment I saw "Lauren Ipsum" in the beginning I got the sense that I was looking at an incomplete website. It kind of caught me off guard.


Clever and confusing are not necessarily mutual exclusive.


The About page reminds me of a Dijkstra quotation: "Computing is no more about computers than astronomy is about telescopes."


I've always preferred "Computing is no more about computers than thermodynamics is about engines."


I like both. I think yours conveys a sense that computing is not driven by the particular application of computers.

The quotation I provided conveys instead the idea that computing is not only about a particular tool of computers.


This is from the computer-science-as-childrens-story-book (http://www.laurenipsum.org/) which has me intrigued. Though I'm still not sold on the idea, personally.


What about it gives you pause? The goal isn't to teach programming per se, but to have fun with some of the really interesting ideas and habits of mind that go along with programming. And to sneak in a lot of bad jokes.

Do you have or know kids? I'd be glad to send you a copy to show to them.


I think in theory, it's fantastic - the basic tenets of computer science are really fascinating, even abstracted away. I may look like an adult, but it's just a disguise.

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.


No, you're right. The first chapter is allegory. Lauren is literally attacked by the Jargon. You're not supposed to understand all those words. They are Jargon. :) Not much learning happens in chapter 0 but it sets up the rest of the story.

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.


I considered it in terms of teaching computer science, especially given (http://carlos.bueno.org/2011/09/ipsum.html) and (http://carlos.bueno.org/2010/07/corrupting-the-youth.html). In that frame of mind, chapter 0 exert seemed like it mentioned computer science concepts, but they weren't really explored as such. I interpreted your goal as edutainment, a noble goal, but one that fails so often it triggers a certain amount of skepticism.

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.


I have and know kids and am currently not at all convinced. We all read quite a lot (of children's literature). Certainly the eldest of my close group, she's 11, would be most interested in getting a pre-publication copy. She and her younger sister have not had any exposure to programming AFAIK.

If you've a copy to spare ...

Sorry if you find my forwardness offensive.

email addr in profile.about


I'm looking forward to the time when we have the A Young Lady's Illustrated Primer capability


That's exactly what this reminded me of. Very cool.


So glad I contributed to this kickstarter project last week :) Looking forward to the whole book


Which is why I like the method of increasing the login processing time per invalid login. It seems to be the easiest way to prevent most attacks.

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


Doesn't this open up the opportunity to basically DOS someone from logging in to their own account?

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.


Yes, it is.


so you can simply have a maximum delay, of say 10 minutes.


10 minutes +1ms vs 10minutes +2ms can still leak information.

Ideally you want something like 3 seconds per password per IP starting the timer before you look up the password.


If you had to wait 10 minutes to login to a website every time, you'd very quickly stop bothering to log in.


You'd rule out all the legitimate users and only be left with people trying to break in. That strategy would only work on a honey-pot site.


This only prevents brute-force password guessing, it doesn't solve the problem of the timing attack. Especially on passwords, which don't change very often. A patient attacker would try only a few attempts at a time, get timing info, then wait out the cooling period until the penalty is back down to 1 second of sleep, then repeat. Each time they gain more information which can all be put together to complete the attack.


With the 1 second sleep (for the first attempt) I was thinking of something along the lines of this:

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.


Hmmm... Linux takes a lot of time to prompt for a password again once an incorrect one has been entered. I'm guessing this may be the reason.


even knowing what a timing attack is, that text left me with a wtf look.

can anyone not familiar with the matter actually understand the idea proposed on the 1st paragraph?


Switching the name of the eponymous hero mid paragraph doesn't exactly help. From the previous links to book excerpts here I've got to say I find this writing style is pretty opaque.

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.


Just add some random sleep time, a few milliseconds here and there.


While this seems like a reasonable solution at first, it doesn't fix the vulnerability. It should be obvious when you consider that the attacker already deals with natural variation in network speeds and server load.

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."


How about starting a timer before doing the calculation and return the result always after XXX milliseconds? Sounds easier to implement than ensuring that calculations always need the same amount of time.


A random delay has an average. If you do enough attempts you can figure out what that average is. Then you do many trials and change if the average of those trials was above or below the random average.

Do that enough and you get your info.


That's going to vastly increase the number of attempts required though, which may be sufficient to make it practically impossible, no?


Increase number of attempts? Yes. Practically impossible? Not in the slightest.


What I was thinking was that if the brute-force took 2 weeks (say) and the randomisation added just a single order of increase it could be sufficient to make the crack no longer worthwhile (eg passwords are changed monthly) - ie impossible in a timely manner which achieves the aims of the cracker.

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.


It's a timing attack remember, not an ordinary brute force. The randomization adds almost no extra time.

You only have to calculate the random average once, and you anyway need to collect lots of timing data.


Incorrect. Salt and hash your password strings so they're all the same length.


Also incorrect. Use bcrypt with a sufficient work function to prevent key strengthening attacks.


"key strengthening attacks"

Please do not use Markov chains to construct posts or refrain from commenting on things you do not actually understand.


Key strengthening or key stretching is used to add a work function to key generation in order to prevent brute force attacks on the key. The attack itself is probably best referred to as a brute force attack, which I poorly worded.

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.


Moral of the story: use bcrypt with a high difficulty.




Registration is open for Startup School 2019. Classes start July 22nd.

Guidelines | FAQ | Support | API | Security | Lists | Bookmarklet | Legal | Apply to YC | Contact

Search: