3 ms·
Do you also sort in constant time at fixed array size, like djbsort claims it does? For the 1024 array their cycle count quartiles differ from the median at th
by SiempreViernes 8y ago
Do you also sort in constant time at fixed array size, like djbsort claims it does?
For the 1024 array their cycle count quartiles differ from the median at the 3 promille level, but I don't know if this counts as "constant" for timing attack purposes.
- Ono-Sendai 8y agoHmm, interesting question. Radix sorts, by their nature, execute the same code regardless of the contents of their elements. ( I think, I haven't thought about this before). However you will see some variation in execution time based on varying memory access patterns.
- exDM69 8y agoNo, it's not constant time. Depending on implementation details, you end up putting different elements in different buckets in different cache lines and that creates side channels. Radix sort will perform differently for an input that is 1,1,1,... and 1,2,3,...,n. I have not read up on how djbsort deals with this issue, but it's the problem it's trying to solve.
- Veedrac 8y agoIt's a sorting network, which means it only uses conditional swaps in a fixed pattern, which can be made constant time.