I want to use randomized algorithms (quicksort, ect...) on a server, but secure pseudorandom generators use a lot of cpu time. But if I use a non-secure one, and the clients figure out the seed, they will be able to force a worst-case scenario. However, the users are never given the seed or output of the generator. The only way I think they can break this is by timing attacks. Will it help if I impose a delay on randomized algorithms e.g. they will be forced to run for 1 second, and if they finish earlier, just wait until 1 second passes? Also, I can reseed it with a cryptographically generated seed every now and then.
$\begingroup$
$\endgroup$
4
1 Answer
$\begingroup$
$\endgroup$
1
In fact, on a recent enough x86 CPU (I mean 2011 or later, so not exactly bleeding edge), there are AES opcodes that, as their name say, help implement the AES block cipher with hardwired dedicated operations. They are really fast. Thus, a PRNG that simply runs AES in CTR mode (encryption of successive values of a counter) will:
- be cryptographically secure; and:
- be blindingly fast, actually more so than most non-cryptographic PRNG.
We are talking here about several gigabytes per second. This should be adequate, and even negligible, for most purposes.
If your platform of choice does not have such an hardware implementation of AES, then there still are good cryptographic options, in particular the stream ciphers from the eSTREAM projects.
As an aside, there are several variants of Quicksort, and are not necessarily randomized. The randomized versions of Quicksort try to avoid the tricky cases where the performance degrades from the average O(n log n) to O(n2). Presumably, if there is an attacker, then the attacker will try to force the input to hit that kind of bad situation, as a denial-of-service attack. If you use a non-secure PRNG, then the attacker may indeed analyse the timing information to predict the PRNG output and thus defeat the countermeasure. Enforcing a delay might work only if the delay is such that the sorting is always below the threshold, which means that you made it so that your Quicksort is always slow. In other words, you defeat DoS by attackers by DoS-ing yourself harder. This is hardly a nice situation.
A fast, cryptographically secure PRNG will avoid such situations nicely, and if that PRNG is properly implemented, then its cost will be negligible with regards to the cost of sorting. Alternatively, you might consider other sorting algorithms that have guaranteed O(n log n) performance even in the worst case, in particular Mergesort and Heapsort (Mergesort is usually faster than Quicksort, but requires an extra RAM buffer; Heapsort is a bit slower but in run in guaranteed fixed RAM, contrary to Quicksort).
answered Jun 5, 2017 at 12:59
-
1$\begingroup$ Nowadays the popular choice for sorting is starting with quicksort and falling back to a O(n log(n)) worst-case algorithm when it detects too deep recursion. Introsort is an early example of this technique. $\endgroup$ Commented Jun 5, 2017 at 14:22
Collections.shuffle()will randomly sort 10M integers using a secure randomness source within a few seconds? I don't think that random generators will be susceptible to timing attacks as they don't have data-dependent timing variations. $\endgroup$