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