Endorsing the secret types proposal for rust

Talk “RFC: Secret types in Rust” by Diane Hosfelt & Daan Sprenkels at RustFest Global 2020 (slides)

Article “LLVM provides no side-channel resistance” by Daan Sprenkels

Rust RFC 2859 “added secret types rfc” by Diane Hosfelt

Article “A beginner’s guide to constant-time cryptography” by Tim McLean

rust crates …

Ensuring operations run in constant-time (i.e. runtime measurements cannot reveal the value of a variable) is a fundamental property for cryptographic software. Whereas often physical access to the computing device is needed for attacks (small threat), network access is sometimes sufficient (large threat). As a result, you really want every cryptographic algorithm to run in constant time.

You can easily write non-constant time for an operation in a programming language (e.g. conditional copy of an array based on a secret value). But you can also write constant time algorithms in a programming language and the compiler turns it into a non-constant time algorithm.

Even if your machine code is constant-time, you additionally have to consider that some instructions (e.g. division) run faster for certain inputs. But one might argue that this is a different level (more difficult to exploit) and most importantly, algorithms are often specified to avoid these instructions.

As such the gap between the programming language and the machine code in the compiler needs to be closed (at least in sections with cryptographic code).

We want constant-time operations for all values touching secret values (e.g. they are part of the private key in asymmetric cryptography, or contains the random numbers used to generate the private key).

Non-constant time code must usually runs at the worst of all possible runtimes and thus we should distinguish between normal code and secret code. “Constant-time operations everywhere!” won’t work.

Thus we should annotate secret values to yield other machine code. RFC 2859 proposes other types (similar to rust’s Wrapping type). I would prefer a secret keyword to annotate secret values. In combination with taint analysis, we could identify sections that need different generated code. The type approach is annoying because it requires a large API-level change in existing codebases with cryptographic code (I think I am not the only one).

The rust language just needs to ensure that macro expansion (and other language mechanisms in the rust frontend) does not generate non-constant time code.

The rust compiler relies on the LLVM toolchain. The rest needs to be done by LLVM. so this is really an LLVM issue and affects other programming languages as well (e.g. zig).

func ConstantTimeByteEq(x, y uint8) int

func ConstantTimeCompare(x, y []byte) int

func ConstantTimeCopy(v int, x, y []byte)

func ConstantTimeEq(x, y int32) int

func ConstantTimeLessOrEq(x, y int) int

func ConstantTimeSelect(v, x, y int) int

Crate secret-integers claims to provide constant-time operations for all integer types.

Crate timing-shield takes an equivalent approach like secret-integers. Here are some notes.

Crate secrecy only encapsulates secret values but does not provide constant-time operations.

We need equivalent constant time algorithms in the stdlib.

Not so much work is left in rust. There are plenty of crates providing constant time algorithms, but everyone is afraid that LLVM turns it into a non-const time equivalent. As such all non-compiler efforts are unreliable.

So we need to wait for LLVM improvements. I would love to see some progress there.