Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Algorithmic complexity attacks and libc qsort()

calmerthanyouare.org

Post reply on HN
Print view View original

51–55 of 55 posts

Re: Algorithmic complexity attacks and libc qsort()

#51

Post by gamegoblin »

ahomescu1 wrote: post #48
ccurtsinger wrote: post #43

There is no "killer input" for randomized quicksort. I'm surprised libc doesn't select pivots randomly already.

Except if you know the PRNG state, but I imagine that's really hard to pull off.

I wonder of it's possible to do some statistical attacks by sending sample input and measuring response time? That is, after getting the response times for a million sorts, perhaps you can make inferences into the current PRNG state?

I suspect fluctuations in latency would make this exceedingly difficult, but I am constantly amazed by the statistical attacks people pull off.

Re: Algorithmic complexity attacks and libc qsort()

#52

Post by mattchamb »

Jabbles wrote: post #14

In comparison, the Go standard sort function is not vulnerable to this, and references the same paper as this article: http://golang.org/src/pkg/sort/sort.go#L168

This is the same approach used the the .NET framework in Array.Sort: http://referencesource.microsoft.com/#mscorlib/system/collec...

You can see the fallback to heapsort here: http://referencesource.microsoft.com/#mscorlib/system/collec...

Re: Algorithmic complexity attacks and libc qsort()

#53

Post by userbinator »

simias wrote: post #8

I'm surprised the article does not point out more directly that it's usually pretty simple to mitigate this attack vector by switching to mergesort. The worst case is O(n log n) so there's no real "killer input". I think it's a good rule of thumb to say "if you need to sort large quantities of untrusted data you should probably use mergesort".

I think heapsort is a better replacement - in-place, guaranteed O(n log n) time (so also quite resistant to information leakage via timing disclosure, which could be important in higher security applications.)

Re: Algorithmic complexity attacks and libc qsort()

#54

Post by gsnedders »

gamegoblin wrote: post #51
ahomescu1 wrote: post #48

Earlier quoted context omitted.

Except if you know the PRNG state, but I imagine that's really hard to pull off.

I wonder of it's possible to do some statistical attacks by sending sample input and measuring response time? That is, after getting the response times for a million sorts, perhaps you can make inferences into the current PRNG state? I suspect fluctuations in latency would make this exceedingly difficult, but I am constantly amazed by the statistical attacks people pull off.

Considering the fact that timing attacks based on memcmp short circuiting were shown to be remotely practical a decade ago, latency isn't going to be an issue. The bigger question is whether you can get down your inputs to a small enough number to practically determine PRNG state (you probably can).

Re: Algorithmic complexity attacks and libc qsort()

#55

Post by Gracana »

valarauca1 wrote: post #25
Gracana wrote: post #18

Earlier quoted context omitted.

> Application level DDoS's leave the kernel/network/sockets layers exposed for exploitation. Since their tasks will take priority over user's applications. So what's the benefit of that, just that you can maximize the chaos you cause by attacking in two different ways?

One attack and obfuscate the other. Like if you server is at 90% cpu use, and the vast majority of it is server application. You won't consider anything strange happening. You can keep attacking the system with strange algorithm exploits or stop. Nobody will expect an attack in the system since well last time I check the box was at 90% CPU, and it was the server. I'd check again, but maybe we just have a lot of traff…

Ah okay, I wondered if it was that simple.
Post reply on HN