

A little game to demonstrate timing attacks. - aristus
http://carlos.bueno.org/2011/10/timing.html

======
dym
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> ]

------
biot
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!

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

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

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

~~~
Groxx
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._

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

~~~
slashCJ
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 :)

~~~
humbledrone
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).

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

~~~
JimmyL
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...](http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.65.9811)

[2] [http://rdist.root.org/2010/07/19/exploiting-remote-timing-
at...](http://rdist.root.org/2010/07/19/exploiting-remote-timing-attacks/)

[3]
[http://www.youtube.com/watch?v=idjDiBtu93Y&feature=relat...](http://www.youtube.com/watch?v=idjDiBtu93Y&feature=related)

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

~~~
ToastOpt
Clever and confusing are not necessarily mutual exclusive.

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

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

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

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

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

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

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

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

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

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

~~~
ToastOpt
Yes, it is.

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

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

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

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

------
gcb
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?

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

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

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

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

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

