Rustc copying cryptographic keys onto the stack instead of using them via pointer

[tczajka]

@bascule

RNGs which don't have cryptographic requirements can go much faster.

That is true, but performance isn't the only criterion for the quality of RNGs.

In fact, speed is rarely that important in that context since random number generation is not usually the bottleneck of whatever randomized algorithm or Monte Carlo simulation you're running. Crypto RNGs can generate bits pretty fast.

But what you do often care about is the statistical quality of the random numbers, i.e. (algorithmic) indistinguishability from true randomness. Which is precisely the definition of what a cryptographically strong RNG is.

[HeroicKatora]

It tooks a while for me to realize just how cursed the problem is. The intrinsic's signature is of course already unfortunate:

pub unsafe fn _mm_aesdec_si128(a: __m128i, round_key: __m128i) -> __m128i

This of course makes it impossible to heed the caution against turning cryptographic material into Rust values.

I tend to agree with calling this a 'bug' of sorts in the standard library's way to provide these functions, even though the library itself is pretty innocent in only following Intel's own header files for C. A language which .. comes with the same problem. It's tragic that it makes the intrinsic dubious in its most pressing use case.

[newpavlov]

@HeroicKatora

I tend to agree with calling this a 'bug' of sorts in the standard library's way to provide these functions

I disagree. The intrinsic definition is fine, according to ABI all its inputs and outputs will be passed in registers. You can see it clearly in the LLVM IR in the @comex's comment above. The problem is with optimization passes used by LLVM.

@comex

This is really something that should be reported to LLVM

Unnecessary stack usage

[HeroicKatora]

@newpavlov

I disagree. The intrinsic definition is fine, according to ABI all its inputs and outputs will be passed in registers. You can see it clearly in the LLVM IR in the @comex's comment above. The problem is with optimization passes used by LLVM.

I don't quite follow. The original definition is certainly not fine. It may be that the ABI itself is permissible (both extern "C" in core #[inline] "rust" assign registers here, that's hopefully right) but that is only a necessary and not a sufficient condition. Further it already leaks the values out of the registers as in initially containing allocas.

The value semantics of Rust don't allow denoting places which are allocated in registers, as places need addresses. As soon as execution gets into the intrinsic implementation, the argument may be moved onto the stack as none of the semantics require the value passed in the arguments to stay in registers. This level of guarantee is only good enough if there's a reasonable way to enforce the optimization or check whether it has take place .. and to quote:

And it's not like there's a good way to produce that more-straightforward IR from Rust.

The full unoptimized IR for the exposed intrinsic is as follows: godbolt

use std::arch::x86_64::*;

pub unsafe fn foo(x: __m256i, bbox: __m256i) -> __m256i {
    _mm256_cmpgt_epi32(x, bbox)
}

define internal void @core::core_arch::x86::avx2::_mm256_cmpgt_epi32(ptr sret(<4 x i64>) align 32 %_0, ptr align 32 %a, ptr align 32 %b) unnamed_addr {
start:
  %0 = alloca <8 x i32>, align 32
  %_5 = alloca <8 x i32>, align 32
  %_4 = alloca <8 x i32>, align 32
  %1 = load <4 x i64>, ptr %a, align 32
  store <4 x i64> %1, ptr %_4, align 32
  %2 = load <4 x i64>, ptr %b, align 32
  store <4 x i64> %2, ptr %_5, align 32
  %3 = load <8 x i32>, ptr %_4, align 32
  %4 = load <8 x i32>, ptr %_5, align 32
  %5 = icmp sgt <8 x i32> %3, %4
  %6 = sext <8 x i1> %5 to <8 x i32>
  store <8 x i32> %6, ptr %0, align 32
  %_3 = load <8 x i32>, ptr %0, align 32
  store <8 x i32> %_3, ptr %_0, align 32
  ret void
}

Many stack moves, a type change from 4 × i64 to 8 × i32 and all those addresses involved which demonstrate a lack of enforcement of register use. The original function arguments are even defined as pointers to values and not as registers in that level of ABI. These are all obviously wrong for the sake of any semblence of leak-freedom. Imho the implementation of these intrinsics would need to utilize inline assembly itself to truly promise absence of stack spillage / a direct translation to the intrinsic. And even that will be wrong on the caller side where no value used in arguments can be certified to keep being allocated within a register without spillage.

None of this is to say that rustc or coreis at some kind of fault here. If anything, I think C is in the exact same predicament regarding actual guarantees around intrinsics; and its silent saving grace is the lack of wide-spread dereferencable attributes that ensure no improper optimizations involving 'deduplication' of a loop constant to the stack for 'efficiency' as here.

[comex]

I agree it would be nice if rustc generated IR that didn't use pointers for intrinsics like this.

But on the other hand, I'll reiterate that 'secret values will not be written to the stack' is fundamentally not a security property that LLVM tries to guarantee. The same is true for GCC and other highly optimizing backends. This is an extreme case because the codegen is not just insecure but also inefficient – but if it weren't inefficient, I wouldn't call this a bug in LLVM or rustc.

Also, direct stores to the stack are not the only way values can be leaked. If you look at the generated assembly, it doesn't just leave secret values on the stack, it also leaves parts of them in caller-saved xmm registers. Depending on the attack scenario, it may be possible to retrieve those registers directly, or they may be spilled to the stack by another operation (e.g. C variadic functions tend to dump xmm0-xmm7 to the stack). If on the other hand the function uses callee-saved xmm registers, then those will be restored once the function returns, but if the function calls something else first, the second function may save them to the stack. Even if the original function does not make any calls, it might do so after inlining or outlining. (The x86-64 Unix ABI doesn't actually make any xmm registers callee-saved, but the x86-64 Windows ABI does, and – if you happen to be writing similar code on ARM – the standard ARM ABI makes some vector registers callee-saved.)

Ideally LLVM would have an option to zero the stack and registers before returning, which would effectively mitigate most kinds of leakage, including the stack spills originally being discussed. This has been proposed before in the context of Rust, and (entirely separately) someone made a prototype patch to LLVM a few years ago, to implement this for C. But as far as I know there's nothing upstream. In lieu of that, if you want to reliably prevent key material from being leaked to the stack, you really should be using functions written entirely in assembly.

Though there is one more source of leakage: signal handlers, which can interrupt any code at any point and can store both caller-saved and callee-saved registers to the stack. There is no good way to prevent that, if you are a library running in some arbitrary program that might be using signal handlers. At best you could clean some region below the stack before returning, in the hope that it covers whatever a signal handler might have been using, if one happened to interrupt your function. But that won't work if the signal handler is using sigaltstack, or other OS-specific signal-like mechanisms that might save data somewhere other than the current stack. Of course, the fact that there may be leakage you can't control doesn't mean you shouldn't try to control what you can control, but… just saying.

[robinm]

If you write a function entirely in assembly to prevent your compiler to leak any data, couldn't the linker, especially when using LTO, rewrite your assembly and expose your secrets?

[scottmcm]

@robinm

couldn't the linker, especially when using LTO

Normal LTO pipelines work at a higher level than assembly, so in practice no. ASM is a horrible level for optimizers to work at, because the side effects are just so pervasive.

(That's why LTO and BOLT are two different things, and why BOLT is about layout, but doesn't really change instructions other than branches.)

[the8472]

@scottmcm

Normal LTO pipelines work at a higher level than assembly, so in practice no. ASM is a horrible level for optimizers to work at, because the side effects are just so pervasive.

Though things like wasm JITs could still screw things up since there you're handing off your already linked code to another level of optimizations.

[bascule]

@comex

I'll reiterate that 'secret values will not be written to the stack' is fundamentally not a security property that LLVM tries to guarantee.

I'm reminded of the secret types RFC although unfortunately it was only for the core integer types and not SIMD registers (and in that regard, a generic-based syntax like Secret<__m128i> might be nice for future extensibility).

Though now that I re-read it:

Out of scope: Memory zeroing (beyond implementing the drop trait) and register spilling