-r--r--r-- 10366 djbsort-20260127/doc/html/security.html raw
<html>
<head>
<meta http-equiv="content-type" content="text/html; charset=utf-8">
<meta name="viewport" content="width=device-width, initial-scale=1">
<style type="text/css">
html{overflow-y:scroll;background-color:#012345}
body{font-family:"Noto Sans","Droid Sans","DejaVu Sans","Arial",sans-serif;line-height:1.5}
tt,code{background-color:#f0f0f0;font-family:"Noto Sans Mono","Droid Sans Mono","DejaVu Sans Mono","Courier New",monospace,sans-serif;font-size:1em;}
pre{margin-left:3em}
p,ul,ol,blockquote,pre{font-size:1.0em;line-height:1.6}
li p{font-size:1.0em}
blockquote p{font-size:1.0em}
h1{font-size:1.5em}
h2{font-size:1.3em}
h3{font-size:1.0em}
h1 a{text-decoration:none}
table{border-collapse:collapse}
th,td{border:1px solid black}
table a{text-decoration:none}
table tr{font-size:1.0em;line-height:1.6em}
table tr{font-size:1.0em;line-height:1.5}
tbody tr:nth-child(2n+1){background-color:#f0ffff}
tbody tr:nth-child(2n+2){background-color:#fffff0}
#headline{display:block;margin:0;padding:0;color:#ffffff;background-color:#012345}
#headline .text{font-weight:bold;font-size:1.0em}
#headline input{display:none}
#nav ul{margin:0;padding:0}
#nav li{list-style-type:none;margin:0;padding:0}
.navtop{padding-bottom:0.5em;font-weight:bold;font-size:1.0em}
.navtop{background-color:#012345;color:#ffffff}
#nav .here{background-color:#012345;color:#ffffff}
#nav .away{background-color:#012345;color:#ffffff}
#nav .away a{text-decoration:none;display:block;color:#ffffff}
#nav .away a:hover,.away a:active{text-decoration:underline}
#hidemenu{visibility:hidden;display:none;overflow:hidden;position:fixed;top:0;left:0;height:100%;width:100%}
.main{padding:5px}
.main{background-color:#ffffff}
.pagetitle{font-size:1.4em;font-weight:bold}
@media only screen and (min-width:512px) {
.navtop{padding-top:5px}
#headline{top:0;margin:0;width:160px;height:100%;position:fixed;overflow:auto}
#headline .noselect{display:none}
#headline #nav{visibility:visible;display:block;width:auto;height:auto}
.main{margin-left:170px}
#headline #hidemenu{visibility:hidden}
}
@media not screen and (min-width:512px) {
#headline .noselect{-webkit-user-select:none;-ms-user-select:none;user-select:none;}
#headline #nav #navbot{visibility:hidden;position:fixed;top:0;left:-70%;z-index:2;transition:0.2s;margin:0;padding:0}
#headline input:checked ~ #nav #navbot{height:100%;position:fixed;top:0;left:0;visibility:visible;display:block;box-sizing:border-box;-moz-box-sizing:border-box;-webkit-box-sizing:border-box;vertical-align:center;font-size:1.0em;width:70%;overflow:auto}
#headline input:checked ~ #hidemenu{visibility:visible;display:block;background:black;opacity:0.3;z-index:1}
}
</style>
<title>
djbsort: Security</title>
</head>
<body>
<label id=headline>
<input type=checkbox />
<nav id=nav>
<div class=navtop>
<span class=noselect>≡</span>
djbsort</div>
<ul id=navbot>
<li class=away><a href=index.html>Intro</a>
</li><li class=away><a href=download.html>Download</a>
</li><li class=away><a href=install.html>Install</a>
</li><li class=away><a href=test.html>Test</a>
</li><li class=away><a href=api.html>API</a>
</li><li class=away><a href=speed.html>Speed</a>
</li><li class=here>Security
</li><li class=away><a href=verif.html>Verification</a>
</li><li class=away><a href=internals.html>Internals</a>
</li><li class=away><a href=license.html>License</a>
</li><li class=away><a href=refs.html>References</a>
</li><li class=away><a href=comparison.html>Comparison</a>
</li></ul></nav>
<div id=hidemenu></div>
</label>
<div class=main>
<div class=pagetitle>djbsort: Security</div>
<p>This page covers djbsort's protections against
<a href="#timing">timing attacks</a>,
<a href="#dos">denial-of-service attacks</a>,
<a href="#memory">buffer overflows</a>,
and
<a href="#bugs">output-ordering bugs</a>.</p>
<h2 id="timing">Protection against timing attacks</h2>
<p>Operations on secrets
often influence attacker-observable timing
through the branch predictor, the cache state, etc.
<a href="https://timing.attacks.cr.yp.to">Timing attacks</a>
work backwards to those secrets.</p>
<p>The
<a href="https://timing.attacks.cr.yp.to/programming.html">constant-time discipline</a>
protects against these attacks
by eliminating data flow from secrets to timings.
This matters for sorting software because
sorting is a subroutine in various deployed post-quantum cryptosystems,
such as
<a href="https://classic.mceliece.org">Classic McEliece</a>
and
<a href="https://ntruprime.cr.yp.to">NTRU Prime</a>.</p>
<p>Part of the constant-time discipline
is disabling dynamic frequency-selection mechanisms such as
<a href="https://blog.cr.yp.to/20230609-turboboost.html">Turbo Boost</a>:
those mechanisms expose power information via timing information,
and power consumption is influenced via secrets.
Another part of the constant-time discipline
is writing software that avoids data flow from secrets to timing variations in CPU instructions:
for example, avoiding secret branch conditions and secret array indices.
This constrains sorting software:
many sorting algorithms rely on data flow from array contents to branch conditions and array indices.</p>
<p>djbsort combines simple arithmetic instructions into comparators that sort 2 array elements,
and combines comparators into sorting networks to sort arrays of any size.
These arithmetic instructions are believed to run in constant time on all supported CPUs.
To protect against compilers converting these arithmetic instructions into variable-time instructions,
the djbsort <a href="test.html">test suite</a>
includes tests for various array sizes
that the compiled software avoids data flow from array contents
to branch conditions and array indices.
To reduce the chance of compilers introducing these problems in the first place,
djbsort uses <a href="https://cr.yp.to/papers.html#cryptoint">cryptoint</a> for arithmetic.</p>
<p>The time for sorting still depends on the <em>size</em> 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.</p>
<h2 id="dos">Protection against denial-of-service attacks</h2>
<p>A different security issue caused by timing variations
is that attackers influencing inputs can sometimes cause problematic consumption of CPU time.
This type of problem is well known in the context of
<a href="https://cr.yp.to/talks.html#2012.12.29">hash flooding</a>
but also applies to some sorting algorithms.</p>
<p>In particular,
many sorting libraries use quicksort.
Quicksort uses Θ(n log n) comparisons on average for random arrays of n integers (each having more than log<sub>2</sub>n bits),
but drastically slows down to Θ(n<sup>2</sup>) comparisons for many types of non-random arrays.
Libraries typically add features
to try to avoid slowdowns observed in tests
(sample features: checking whether an array consists of many repetitions of the same number;
taking the median of the first, middle, and last array elements as a pivot),
but these features do not protect against quadratic slowdowns produced by attacker-chosen inputs.
Some libraries guarantee that the slowdown will not be worse than an order of magnitude
(for example, "introspective sort" automatically falls back to heapsort when quicksort is progressing slowly),
but an order-of-magnitude slowdown can still be an attractive attack target.</p>
<p>There does not seem to have been serious investigation of
how much slowdown adversarial inputs can produce in current libraries.
A brief investigation shows that the <code>int32</code> array</p>
<pre><code>for (i = 0;i < n;++i)
buf[i] = 10000*(i/66)+((i%66)==0)-((i%66)==1);
</code></pre>
<p>makes vqsort slower;
the same pattern with 34 instead of 66 makes x86-simd-sort slower;
the same pattern with 514 makes the "far" library slower;
and a constant array makes vxsort much slower.
Most libraries select pivots deterministically,
so merely influencing array entries at the pivot positions would make those libraries much slower.
The vqsort library seeds its pivot-selection RNG with OS randomness generated once per thread,
but there does not seem to have been investigation of whether vqsort's RNG state can be reconstructed via timings,
which would then reduce to the deterministic case.</p>
<p>None of this is an issue for djbsort.
The sorting networks in djbsort always use Θ(n log<sup>2</sup>n) comparisons,
more precisely about (1/4)n log<sup>2</sup>n comparisons.
CPUs with AVX2 instructions carry out many comparisons per cycle,
making djbsort
<a href="speed.html">faster</a>
for typical array sizes on those CPUs than the <em>average</em> case
of the far, vqsort, vxsort, and x86-simd-sort libraries.
For larger array sizes, djbsort is only slightly slower,
and in any case adversarial array contents cannot cause djbsort to take more time.</p>
<h2 id="memory">Memory safety</h2>
<p>Sorting software, like other software,
could have bugs that read or write outside the specified array.
For example, the array</p>
<pre><code>for (i = 0;i < 1291;++i)
buf[i] = 100000*(4+3*(i/65536)+((i%15)==0)-((i%15)==1));
</code></pre>
<p>appears to reliably cause vxsort to
<a href="https://cr.yp.to/2026/20260118-vxsort.sh">crash under asan</a>.
In general, such bugs might crash the application,
leak sensitive data,
or allow an attacker to take control of the application.</p>
<p>For djbsort,
array indices are determined entirely by the array size,
and the tests include
tests under valgrind for many different array sizes.</p>
<h2 id="bugs">Protection against output-ordering bugs</h2>
<p>Non-buffer-overflow bugs in sorting algorithms
might produce outputs in the wrong order,
perhaps causing applications to misbehave in ways that affect security.
It is even conceivable that some inputs will be lost
(overwritten by other inputs) or corrupted (changed in value).</p>
<p>Beyond traditional tests in its
<a href="test.html">test suite</a>,
djbsort includes tools that, given n,
<a href="verif.html">verify</a>
that the compiled code sorts all size-n inputs correctly.
These tools have been run for many choices of n,
although this does not rule out the possibility
of bugs appearing for other choices of n.</p><hr><font size=1><b>Version:</b>
This is version 2026.01.24 of the "Security" web page.
</font>
</div>
</body>
</html>