Suppose you have a secret list of n distinct integers. How would you sort this list in a way that is not vulnerable to timing attacks? I tried looking up "constant time sorting" and other related queries but that expectedly lead nowhere.

  • $\begingroup$ Why not randomize the list before sorting? This way, you spoil the data which the attacker needs to do a timing attack. $\endgroup$ – workoverflow Jul 10 '20 at 20:35
  • $\begingroup$ @workoverflow That still presents the same problem. The naive algorithm for shuffling a list is not constant time but you can use the Fisher-Yates shuffle which would always have n swaps for a list of length n. However, since you are indexing into the list with some value, that value can be inferred by cache timing attacks. This would allow an attacker to extract the pre-order and therefore get information about the content of the list. $\endgroup$ – Kai Arakawa Jul 11 '20 at 21:04
  • $\begingroup$ @workoverflow the implementation of such an attack is very difficult (two timing attacks simultaneously) and AFAIK it would be unexplored territory. However, it is still important to minimize attack surfaces. $\endgroup$ – Kai Arakawa Jul 11 '20 at 21:05

Yes, you can; you can use Batcher's Merge Exchange algorithm, paired with a constant time/access compare-and-swap routine (which reads two elements from locations A and B, and writes the larger element into location A and the smaller element into location B).

This takes $O(n (\log n)^2)$ time, which makes it not quite as fast as other sort algorithms; however if you want constant time/memory accesses, that's about the best we have.

The code on Wikipedia assumes that $n$ is a power of two; it is not hard to extend it to arbitrary $n$...

  • 7
    $\begingroup$ Note that there are sorting networks that have size $O(n\log n)$, it is practically far preferable to use these $O(n\log^2 n)$ constructions because they're much simpler, much more readily available and don't have a gigantic constant hidden behind their $O$-notation. $\endgroup$ – SEJPM Jul 9 '20 at 22:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.