[llvm-dev] _ExtInt, LLVM integers and constant time
David Chisnall via llvm-dev
llvm-dev at lists.llvm.org
Thu Apr 30 00:56:56 PDT 2020
On 22/04/2020 17:35, Adrien Guinet via llvm-dev wrote:
> If we would like, at some point, to introduce such guarantees, that would imply adding a
> "constant time" flag to the arithmetic operations at the LLVM IR level, and have the
> backends honor it (which already seems the case), or fail if not possible ? .
I'm really nervous about any suggestion of a constant-time flag for LLVM
for two reasons:
1. LLVM does not have a notion of time in its abstract machine, so you
are introducing an entirely new concept but applying it in a single
place. The C abstract machine does not either. One of the most common
flaws in papers about constant-time extensions to C is the assumption
that they are preserving an invariant, not adding a new invariant.
2. Most ISAs do not make timing guarantees about individual
instructions, so even if we define and preserve the guarantee throughout
the optimisation pipeline, we can't guarantee it in the final binary.
We discussed some of this on our paper on preserving security invariants
through a compiler pipeline a few years ago.
In the second case, consider something as simple as an add. There have
been ARM implementations where a 32-bit integer add took one or two
cycles depending on the operand values. To guarantee constant-time
execution, you'd need to ensure that you toggled some bits in your
values to guarantee the slow path and then reassembled the result.
That's a big codegen effort, but is required only for one or two our of
hundreds of microarchitectural implementations of the AArch32 ISA.
More troubling for most people should be the fact that Intel
*explicitly* does not guarantee that CMOV is constant time. There are
possible microarchitectural implementations of this instruction that
handle it entirely in the scheduler so that the instruction commits as
soon as both the condition code and the used operand are available
(side-effect-free instructions that lead to the unused value can be
silently dropped). No one implements CMOV like this, but Intel is not
willing to commit to *never* implementing CMOV like this, so any code
that assumes that using select instead of branches is constant time is
not guaranteed to be.
The lack of any kind of notion of time in the LLVM abstract machine
makes plumbing this in very difficult. Informally, a constant-time
abstract machine has no data-dependent flow control and has no
operations that have operand-dependent timing. In most ISAs, this
eliminates data-dependent loads and stores, floating point instructions,
and integer division.
If you want to support constant-time execution, I'd recommend defining
markers for the start and end of constant-time blocks (e.g. crypto
kernels) and explicitly annotate input values that are not secret
dependent with metadata. Then ensure that this metadata (insecure
values and safe input values) is emitted in the resulting assembly. You
can then write a per-ISA (probably tuned per-microarchitecture)
validator that ensures that the output is constant time according to
your model. You can then work backwards to find places where LLVM does
transforms that are breaking your assumptions and work on patches to fix
More information about the llvm-dev