_ExtInt, LLVM integers and constant time

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.

For instance, for now, the x86 & aarch64 backend generate constant time
code for additions on i256 integers (see https://godbolt.org/z/xMfkqz &
https://godbolt.org/z/jbkSpe), but is there some guarantee that this
will always be the case? For instance one could add an early exit if the
carry is zero at some point.

One use case is cryptography code on elliptic curves, where you need
this constant-time property to avoid side channel leakages. Such
constant-time property would be nice and allow to directly use this
extension, for which LLVM generates very efficient code (at least on
x86/aarch64).

Thanks everyone!

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.

For instance, for now, the x86 & aarch64 backend generate constant time
code for additions on i256 integers (see https://godbolt.org/z/xMfkqz &
https://godbolt.org/z/jbkSpe), but is there some guarantee that this
will always be the case? For instance one could add an early exit if the
carry is zero at some point.

One use case is cryptography code on elliptic curves, where you need
this constant-time property to avoid side channel leakages. Such
constant-time property would be nice and allow to directly use this
extension, for which LLVM generates very efficient code (at least on
x86/aarch64).

Thanks everyone!

--
Adrien.

Roman

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

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@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 4/22/20 6:13 PM, Chris Lattner wrote:>> On Apr 22, 2020, at 12:24 AM, Roman Lebedev via
llvm-dev <llvm-dev@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

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

Hi all,

I am late to the discussion, but this is one of the topics I’m researching, but have not been able to secure funding. It seems nobody from the LLVM team interested in the idea.

Anyway, I’m going to explain what have in my mind.

This is a very common problem in the cryptography community. Basically, cryptography people have said, “we are in the fight with compilers”. There are two fundamentally different approaches to this problem. The 1) shallow, or a 2) deep theoretical approach.

In the first one [1], you can basically test and implement different primitives in constant-time fashion and use them when the user annotate some part of his/her program as constant time. When you see that annotation, you will disable any optimization for that scenario and only use the tested ISA instruction in each platform. There are some tools for testing whether your code is constant time or not like Dudect and some other tools [2,3]. This is not a guaranteed approach, but in this approach, we are trying our best. This only works because the number of required primitives is not that much. To have idea about this, look at this Constant-time Toolkit https://github.com/pornin/CTTK (Thomas Pornin, NCC Group).

In the second approach, the more fundamental one, your approach is to have a theoretical concept of what is constant-time and what is not, then only use permitted of optimizations for that part of the program. There is some theoretical papers compiler team at Berkeley and French Institute for Research in Computer Science and Automation. Integrating those concepts to LLVM would be a huge (but extremely fun and interesting) undertaking.

This is a very interesting topic, and I had an internship offer to work on this as a researcher, which they rescinded because of Coronavirus. Webassembly guys would be interested in this research [6]. If anyone wants to work on it, shoot me an email. I am really interested in collaboration.

BTW, hardware people are doing something similar too [7].

  1. https://www.cl.cam.ac.uk/~rja14/Papers/whatyouc.pdf

  2. https://eprint.iacr.org/2016/1123.pdf

  3. https://www.usenix.org/system/files/conference/usenixsecurity16/sec16_paper_almeida.pdf

  4. https://cseweb.ucsd.edu/~dstefan/pubs/cauligi:2017:fact.pdf

  5. https://hal.archives-ouvertes.fr/hal-01959560/document

  6. https://dl.acm.org/doi/pdf/10.1145/3290390

  7. https://www.usenix.org/system/files/sec19-gleissenthall.pdf

  8. https://dl.acm.org/doi/pdf/10.1145/3371075