4 ms·

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

• ahomescu1 12y ago
  Except if you know the PRNG state, but I imagine that's really hard to pull off.
  • gamegoblin 12y ago
    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.
    • gsnedders 12y ago
      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).