4 ms·
Securely random pivot selection would also avoid the DoS.
by CodesInChaos 7y ago
Securely random pivot selection would also avoid the DoS.
- GuB-42 7y agoSure, but secure RNGs are not cheap. That's another trade-off to consider.
- chkas 7y agoI think it should be enough to initialize the PRNG with a secure random value before sorting. Am I wrong?
- nwallin 7y agoIt kinda is. Use your operating system to get 128 random bits, use that as a key to AES, use AES-NI instructions to generate boat loads of more bits. These instructions can generate random bits faster than RAM can store them. Honestly, most of us mortals can operate on the assumption that thread local mt19937 PRNGs seeded with 19,937 OS provided secure bits is safe enough for secure quicksort pivot selection DOS protection, even if we can't generate crypto keys or nonces from it.