Replace C constant-time code with Rust code built in a separate stage

[briansmith]

Currently we have several functions that implement constant-time primitives. Let's replace the ones that are used by Rust code with new implementations that are written in Rust.

Currently we insist all the constant-time utilities are written in C in part because we don't want the Rust optimizer to "see" the implementation of these utilities. In particular, we don't want to rely on the Rust compiler generating code that maintains the constant-time properties we need. More specifically, we don't want the inter-module optimizations to have any opportunity to do weird stuff to the generated code. We rely on the assumption that rustc and the C compiler are unable to do inter-module optimizations across the two languages. That's a dubious assumption. Also, we assume that the C compiler compiles our constant-time idioms into constant-time code, which is also dubious.

Instead, let's replace the constant-time utilities used by Rust code with new Rust code. Let's compile that Rust code in a separate stage into .S files. Then, let's manually review the .S files for side channels. Then check the .S files into version control, and change build.rs to use the generated .S files. This way we achieve a good level of assurance that the code is actually constant-time.

Unfortunately that means that the constant time utilities will have to remain unsafe. We can mitigate that usability issue by creating non-unsafe #[inline(always)] wrappers around them, and then having the Rust code use those wrappers.

I suggest we first implement verify_slices_are_equal() this way and see how it goes, before we implement the other functions this way.

The .S files should be generated with minimal optimizations and with full debug info.

If somebody does the non-Windows stuff, I'll do the Windows-specific work.

/cc @Aaronepower. See also #625.

[briansmith]

Tim McLean‏ mentioned on Twitter that this has an added risk of FFI bugs. It would be bad if the .S files were generated for a different ABI than what the Rust code is compiled for. I'm not sure all platforms' linkers would recognize a mismatched ABI and stop the compilation. Ideally we'd find some way to do that ourselves, if it isn't done automatically.

Another limitation is that the Rust functions in that initial stage would be limited to having FFI-safe signatures. There would be no Result return types for example. We'd need to find some convention for this.

Maybe the idiom we'd use would be something like:

Stage 1 code:

#[no_mangle]
unsafe GFp_verify_slices_are_equal(a: &[u8], b: &[u8]) -> c_int {
    result_to_int(verify_slices_are_equal_inner(a, b))
}

#[inline(always)]
verify_slices_are_equal_inner(a: &[u8], b: &[u8]) -> Result<(), ()> {
    // No `unsafe` logic allowed in here.
}

// The inverse of `bssl::map_result()`.
#[inline(always)]
fn result_to_int(r: Result<(), ()>) -> c_int {
    match r {
        Ok(()) => 1,
        Err(()) => 0,
    }
}

Stage 2 code:

/// A non-`#[unsafe]` wrapper for the `#[unsafe]` function above.
#[inline(always)]
fn verify_slices_are_equal(a: &[u8], b: &[u8]) -> Result<(), ()> {
    bssl::map_result(GFp_verify_slices_are_equal(a, b))
}