djbsort

Operations on secrets often influence attacker-observable timing through the branch predictor, the cache state, etc. Timing attacks work backwards to those secrets.

The constant-time discipline protects against these attacks by eliminating data flow from secrets to variable-time instructions. This matters for sorting software because sorting is a subroutine in various deployed post-quantum cryptosystems, such as Classic McEliece and NTRU Prime.

djbsort is designed so that the time for sorting is independent of the contents of the array being sorted. Specifically, djbsort systematically avoids secret branch conditions and secret array indices, and it uses only simple arithmetic instructions that are believed to run in constant time with all common compilers on all supported CPUs.

The time for sorting still depends on the size of the array being sorted (although one can work around this by padding to a maximum size). This is not an issue in the cryptographic context: the array sizes are standard.

A side effect of this security feature is that there are no bad inputs causing djbsort to take excessive amounts of time. This property also holds for heapsort libraries, but quicksort libraries are typically vulnerable to bad inputs.


Version: This is version 2024.01.17 of the "Security" web page.