llvm dev - Apr 2020 - _ExtInt, LLVM integers and constant time

> On Apr 22, 2020, at 12:24 AM, Roman Lebedev via llvm-dev <llvm-dev at
lists.llvm.org> wrote:
> 
> On Wed, Apr 22, 2020 at 9:35 AM Adrien Guinet via llvm-dev
> <llvm-dev at lists.llvm.org <mailto:llvm-dev at
lists.llvm.org>> wrote:
>> 
>> Hello everyone,
>> 
>> After reading the nice blog post about _ExtInt, I was wondering whether
>> operations on i128/i256 and more generally on integer types in LLVM are
>> guaranteed to be constant time or not.
> I don't believe there's any such guarantee even for normal
8/16/32/64
> -bit integers.
Right. I would expect this to be implementation / target dependent.  The maximum
bit width of an integer may also be target specific.  For example, some targets
may not provide a 1024 bit integer divide lib call, and may not want to open
code it.

-Chris
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20200422/540156fe/attachment.html>

On 4/22/20 6:13 PM, Chris Lattner wrote:>> On Apr 22, 2020, at 12:24 AM,
Roman Lebedev via
llvm-dev <llvm-dev at lists.llvm.org>
>> wrote:
>> 
>> On Wed, Apr 22, 2020 at 9:35 AM Adrien Guinet via llvm-dev <llvm-dev
at lists.llvm.org
>> <mailto:llvm-dev at lists.llvm.org>> wrote:
>>> 
>>> Hello everyone,
>>> 
>>> After reading the nice blog post about _ExtInt, I was wondering
whether operations
>>> on i128/i256 and more generally on integer types in LLVM are
guaranteed to be
>>> constant time or not.
>> I don't believe there's any such guarantee even for normal
8/16/32/64 -bit integers.
> 
> Right. I would expect this to be implementation / target dependent.  The
maximum bit
> width of an integer may also be target specific.  For example, some targets
may not
> provide a 1024 bit integer divide lib call, and may not want to open code
it.
> 
Okay that makes sense!

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 ? .

The only use case I have in mind that would benefit from this is cryptographic
code, but
there might be others.

On Wed, Apr 22, 2020 at 7:35 PM Adrien Guinet <aguinet at quarkslab.com>
wrote:
>
> On 4/22/20 6:13 PM, Chris Lattner wrote:>> On Apr 22, 2020, at 12:24
AM, Roman Lebedev via
> llvm-dev <llvm-dev at lists.llvm.org>
> >> wrote:
> >>
> >> On Wed, Apr 22, 2020 at 9:35 AM Adrien Guinet via llvm-dev
<llvm-dev at lists.llvm.org
> >> <mailto:llvm-dev at lists.llvm.org>> wrote:
> >>>
> >>> Hello everyone,
> >>>
> >>> After reading the nice blog post about _ExtInt, I was
wondering whether operations
> >>> on i128/i256 and more generally on integer types in LLVM are
guaranteed to be
> >>> constant time or not.
> >> I don't believe there's any such guarantee even for normal
8/16/32/64 -bit integers.
> >
> > Right. I would expect this to be implementation / target dependent. 
The maximum bit
> > width of an integer may also be target specific.  For example, some
targets may not
> > provide a 1024 bit integer divide lib call, and may not want to open
code it.
> >
>
> Okay that makes sense!
>
> 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,
I don't think that will work. Normally, flags on instructions are
optimization hints
that can be freely dropped without affecting correctness. It's not going to
be
really possible to ensure that every single existing&future fold
respects optional correctness-affecting flag.. I suspect this will involve
the similar approach as with constrained floating-point intrinsic.
> and have the
> backends honor it (which already seems the case), or fail if not possible ?
.
I think so, yes.
> The only use case I have in mind that would benefit from this is
cryptographic code, but
> there might be others.
>From previous discussions on the subject of constant time, i think
Chandler (CC'd)
has/is involved with some C++ paper about this.

Roman

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[1] 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 
them.

David

[1] https://ieeexplore.ieee.org/document/8406587