Purpose of constant_time_compare?

[Jonas H.]

Hello out there,

what is the point of `django.utils.crypto.constant_time_compare`? I
understand it takes O(n) time no matter what input it is feeded with,
but of what avail is it?

Can the time spent in *one single string comparison* really make such a
huge difference?

Confused,
Jonas

[Alex Gaynor]

--
You received this message because you are subscribed to the Google Groups "Django developers" group.
To post to this group, send email to django-d...@googlegroups.com.
To unsubscribe from this group, send email to django-develop...@googlegroups.com.
For more options, visit this group at http://groups.google.com/group/django-developers?hl=en.

In theory, yes.  These are a class of attacks known as timing attacks: http://en.wikipedia.org/wiki/Timing_attack.  That said I don't know of any actual real world attacks using these, but better safe than sorry.

Alex

--
"I disapprove of what you say, but I will defend to the death your right to say it." -- Evelyn Beatrice Hall (summarizing Voltaire)
"The people's good is the highest law." -- Cicero
"Code can always be simpler than you think, but never as simple as you want" -- Me

[Christophe Pettus]

On Dec 8, 2010, at 12:08 PM, Jonas H. wrote:
> Can the time spent in *one single string comparison* really make such a huge difference?

Yes.

http://codahale.com/a-lesson-in-timing-attacks/

--
-- Christophe Pettus
x...@thebuild.com

[Mike Malone]

Yea... in reality I'd bet my paycheck that the answer is no. Despite Coda's blog post, you can't use the jitter in HTTP requests to gain any insight into where a string match fails.

Even if you could do so with hundreds of requests, it's fairly obvious that an attack is taking place when you get that many bad requests for one account.

Mike

[sago]

Your paycheck is safe.

It is a hypothetical attack, yes. Only observed under very specific
conditions (with a comparator deliberately and parametrically slowed
down - see the actual TR for details). Best reported resolution for
this attack across a WAN has been microsecond resolution (still bloody
impressive, imho), LAN at hundreds of nanoseconds. Typical time for
individual character comparisons on commodity hardware is in the tens
of picosecond range.

But having said that, even hypothetical attacks are often a code-stink
of a badly reviewed implementation.

But it won't be fairly obvious you're getting attacked in that way,
unless you've specifically put in code or other tech to detect it.
Most web-frameworks (Django included) just let that sail right by
(rightly) assuming it isn't their job to worry.

Ian.

On Dec 9, 2:02 am, Mike Malone <mjmal...@gmail.com> wrote:
> Yea... in reality I'd bet my paycheck that the answer is no. Despite Coda's
> blog post, you can't use the jitter in HTTP requests to gain any insight
> into where a string match fails.
>
> Even if you could do so with hundreds of requests, it's fairly obvious that
> an attack is taking place when you get that many bad requests for one
> account.
>
> Mike
>
>
>
>
>
>
>
> On Wed, Dec 8, 2010 at 12:10 PM, Alex Gaynor <alex.gay...@gmail.com> wrote:
>
> > On Wed, Dec 8, 2010 at 3:08 PM, Jonas H. <jo...@lophus.org> wrote:
>
> >> Hello out there,
>
> >> what is the point of `django.utils.crypto.constant_time_compare`? I
> >> understand it takes O(n) time no matter what input it is feeded with, but of
> >> what avail is it?
>
> >> Can the time spent in *one single string comparison* really make such a
> >> huge difference?
>
> >> Confused,
> >> Jonas
>
> >> --
> >> You received this message because you are subscribed to the Google Groups
> >> "Django developers" group.
> >> To post to this group, send email to django-d...@googlegroups.com.
> >> To unsubscribe from this group, send email to

> >> django-develop...@googlegroups.com<django-developers%2Bunsubscr i...@googlegroups.com>
> >> .

> >> For more options, visit this group at
> >>http://groups.google.com/group/django-developers?hl=en.
>
> > In theory, yes.  These are a class of attacks known as timing attacks:
> >http://en.wikipedia.org/wiki/Timing_attack.  That said I don't know of any
> > actual real world attacks using these, but better safe than sorry.
>
> > Alex
>
> > --
> > "I disapprove of what you say, but I will defend to the death your right to
> > say it." -- Evelyn Beatrice Hall (summarizing Voltaire)
> > "The people's good is the highest law." -- Cicero
> > "Code can always be simpler than you think, but never as simple as you
> > want" -- Me
>
> >  --
> > You received this message because you are subscribed to the Google Groups
> > "Django developers" group.
> > To post to this group, send email to django-d...@googlegroups.com.
> > To unsubscribe from this group, send email to

> > django-develop...@googlegroups.com<django-developers%2Bunsubscr i...@googlegroups.com>
> > .

[Gabriel Hurley]

You wanna hand over your paycheck now, or later? :-)

I know someone with a functional white-hat timing attack script sitting on their laptop. They've been honing the statistical analysis to get the number of data points needed down to a less noticeable size, but the technique can already be successfully applied.

To your latter point, you can run a timing attack as slowly as you like, and a lot of sites have very poor monitoring for things like 404s. A month or more of patient low-level attacking to gain access to a prime target is well worth it.

The point being that we all ought to take timing attacks seriously. They're not nearly as unrealistic as people think.

All the best,

    - Gabriel

[Mike Malone]

This is quickly becoming off topic, but I'll bite ;D.

On Wed, Dec 8, 2010 at 10:52 PM, Gabriel Hurley <gab...@gmail.com> wrote:

You wanna hand over your paycheck now, or later? :-)

I know someone with a functional white-hat timing attack script sitting on their laptop. They've been honing the statistical analysis to get the number of data points needed down to a less noticeable size, but the technique can already be successfully applied.

Pics or it didn't happen.

If you can show me a viable timing attack, over the Internet, under reasonable real-world circumstances, and caused by something as negligible as a single string comparison I will give you my paycheck. And I will eat my laptop.

 

To your latter point, you can run a timing attack as slowly as you like, and a lot of sites have very poor monitoring for things like 404s. A month or more of patient low-level attacking to gain access to a prime target is well worth it.

The longer you draw out the attack the less consistent the results. Code changes, hardware changes, data set sizes change, passwords change, BGP routes change, peering agreements change, phases of the moon change, etc.

If you can tune your web app to the point where response time variance is small enough to notice a couple dozen CPU cycles of variance, and can maintain that sort of consistency over an extended period of time, either you're not doing anything interesting, you're running a Commodore 32, or you're my new hero.

 

The point being that we all ought to take timing attacks seriously. They're not nearly as unrealistic as people think.

Sure, broadly speaking they're an attack vector. In this particular scenario it's silly wankery by smart people who put up with the same sort of silly wankery from me sometimes. So whatever.

<3,

Mike

[Luke Plant]

On Thu, 2010-12-09 at 00:54 -0800, Mike Malone wrote:

> If you can show me a viable timing attack, over the Internet, under
> reasonable real-world circumstances, and caused by something as
> negligible as a single string comparison I will give you my paycheck.
> And I will eat my laptop.

We don't just have the internet to worry about - given the places Django
is used, we must consider datacentres and LANs, and even shared hosting.
Shared hosting is probably the only one close to being exploitable at
the moment for our usage. My quick, fairly crude tests with python
timeit suggest a single character can take 2ns to check. I've struggled
to find information on time resolution for local timing attacks, but I
don't think 2ns is far off being exploitable.

Luke

(For reference, I used a command line like:

python -m timeit -s 'x="x2345678901234567890";
y="12345678901234567890"' 'x == y'

and then moved the 'x' in the first one along. I tried some other
variations too. There are some 'end effects' which I tried to remove.).

--
"My capacity for happiness you could fit into a matchbox without
taking out the matches first." (Marvin the paranoid android)

Luke Plant || http://lukeplant.me.uk/

[Adam Baldwin]

Depending on the implementation, yes timing attacks can be exploited in
the field, not just in theory. Again much depends on a lot of variables
involved.

Nate Lawson and Taylor Nelson had a great talk at BlackHat that covered
piles of background and theory of timing attacks and successful
exploitation.
http://www.youtube.com/watch?v=ehxjAq59xEw&feature=related Part 3 is
where they get into exploitation.

Another talk Nate Lawson Google TechTalk: "When Crypto Attacks"

"incorrenctly comparing hash value" at 30:00 - again I haven't looked at
if the recommended counter measures in the contact_time_compare are what
is recommended out there.

http://timingattacks.org/nate-lawson-google-techtalk-when-crypto-attac

Even if it's not 100% valuable to this thread those couple resources
provide some great info for anybody wanting to understand timing attacks
and their exploitability in more depth.

-Adam Baldwin

[Anssi Porttikivi]

https://github.com/anymail/django-anymail/commit/c07998304b4a31df4c61deddcb03d3607a04691b

It happened for real.  

[Josh Smeaton]

I don't doubt that timing attacks can work in practise, but the link you've posted is not this. From the commit message:

> There have not been any reports of attempted exploit in the wild. (The vulnerability was discovered through code review.)