Endorsing the secret types proposal for rust

✍️ Written on 2022-05-05 in 932 words. Part of cs IT-security software-development rustlang

Motivation

I recently watched Diane & Daan’s video at RustFest Global introducing secret types for constant time operations in rust. I think it is a good idea, has some challenges, but want to support this idea in this blogpost.

Resources

Why

  • 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).

This is at the heart of many cryptographic software authors. This concerns also our packages classic-mceliece-rust, rusty-saber, and ntrust-native. We wrote constant-time algorithms, but is the generated machine code really constant time? We would have to study the machine code for all hardware platforms to make a definite statement. An effort exceeding available resources.

How

  • 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).

Best efforts, so far

Crate subtle was inspired by Go’s crypto/subtle and provides few constant time (only in release mode!) operations. The Go implementation supports the following operations:

  • 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

So the Go implementation implements operations (BTW, ConstantTimeCopy is the conditional copy I mentioned in the Why-section) on int/int32 or byte arrays in constant time. On the other hand, the rust implementation provides a Choice type which wraps only a u8. It then implements and/or/swap/eq/….

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

Conclusion

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

Apparently there is a large gap between the written source code trying to provide constant-time guarantees and the machine code generated. I would love to see some improvements in this direction, because otherwise we need to continue writing assembly to maintain security properties.