[Valgrind-developers] Proposed valgrind division patch

[D. J. B. <aut...@bo...>]

There have been many successful "timing attacks" that break
cryptographic software by working backwards from timings to secrets. One
common use of valgrind's memcheck tool in cryptography is to catch data
flow from secrets (marked with VALGRIND_MAKE_MEM_UNDEFINED) to branch
instructions and array indices. Some references: 

   https://neuromancer.sk/article/26
   https://www.usenix.org/system/files/sec24fall-prepub-760-fourne.pdf
   https://bench.cr.yp.to/tips.html#timecop

However, there are other variable-time instructions. Our new paper
"KyberSlash: Exploiting secret-dependent division timings in Kyber
implementations" includes demonstrations of secret-key recovery from the
reference software for the Kyber cryptosystem in two different
environments, exploiting the fact that compilers sometimes use
variable-time division instructions for divisions in that software:

   https://kyberslash.cr.yp.to/papers.html

The paper describes a patch to valgrind to optionally catch division
instructions on undefined data. The point of this message is to propose
this patch for inclusion in valgrind. The patch is attached.

The patch was written by Tee Kiah Chia. A few API tweaks and tests in
valgrind's test framework were added by D. J. Bernstein. The patch
applies cleanly to valgrind's current git repository. As per
valgrind/README, we have licensed the patch as follows:

   SPDX-License-Identifer: GPL-2.0-or-later

The patch is designed to be off by default. The user can start scanning
for divisions using --variable-latency-errors=yes on the command line,
VALGRIND_CLO_CHANGE("--variable-latency-errors=yes") from the program
under test, or, easiest to use, a new environment variable
VALGRIND_BESTEFFORT_VARIABLE_LATENCY_ERRORS=yes.

Internally, the patch is designed to allow easy future extensions to
catch timing variations in instructions other than divisions. The patch
catches square roots as an example. A natural long-term goal is to
synchronize the allowed instructions with lists from CPU designers:

   https://www.intel.com/content/www/us/en/developer/articles/technical/software-security-guidance/resources/data-operand-independent-timing-instructions.html
   https://developer.arm.com/documentation/ddi0595/2021-06/AArch64-Registers/DIT--Data-Independent-Timing

This would also naturally resolve inconsistency #8 (vector shifts)
documented in memcheck/mc_translate.c. Full synchronization will,
however, be a large project. Division is an immediate problem for many
cryptographic implementations (as shown by the scans reported in
the KyberSlash paper), so there is immediate value in a patch that looks
for divisions.

---D. J. Bernstein (on behalf of the KyberSlash paper authors)