See #39.

The reason this came about is because we're implementing algorithms for field arithmetic in one of our crates and the current practice (as seen in curve25519-dalek for example) of

1. If you call invert() it returns zero for a zero input, when it should actually fail.
2. If you call inverse square root, it will return a value and a Choice indicating whether it's correct or not; the caller could accidentally forget.

is error prone. Given this new Maybe abstraction

1. Inversion can now return a Maybe<T> and if the caller is sure that the inputs are never zero, they can unwrap() themselves to make it explicit.
2. (Inverse) square root can return a Maybe<T> and the caller can choose how to deal with it. If they want to deal with the case in constant time, they can.

The API in this PR is really simple and could probably be extended to support e.g. constant time mapping over the underlying value, but I want to avoid blocking this feature on the inevitable questions of how such APIs should behave. What's implemented in this PR should be sufficient for all of the users of subtle I know about, and we can extend it later without breaking backwards compatibility.

The only question is whether or not the name Maybe is good.

Currently, working with bls12_381 we have functions like Scalar::from_bytes() which returns a CtOption.

This is fine since it's "marking" the function as a const_time fn. The problem is that the type is really unflexible since you don't have any way to transform the CtOption to Result<T, Error> appart of doing something like:

if ct_opt.is_some() {
     return ct_opt.unwrap()
} else {
    return Err(....)
}

Is there any reason why ok_or() it's not implemented for CtOption? Or any workarround to that?

Fixes: #28

Regarding replaced match, proposed code produces the same assembly and does not use hint::unreachable_unchecked() which was stabilized only in Rust 1.27. (plus it's minus one line of unsafe code)

Integration tests using the haybale SMT solver and haybale-pitchfork crates for discovering constant-time violations.

The current test reports a violation originating from std::ops::BitXor being used for bitwise-XOR comparison.

The result may be a false-positive, so please disregard if it is.

If it is a valid result, one solution may be to write a new trait for constant-time bitwise-XOR (e.g. subtle::CtBitXor).

As stated in #73 and #74 the CtOption<T> API is a bit unflexible when you try to extract the value from the CtOption or you want to convert the CtOption<T> into an Option<T> or a Result<T>.

Therefore the conversion from CtOption<T> to Option<T> has been implemented to avoid having situations like:

if ct_opt.is_some() {
     return ct_opt.unwrap()
} else {
    return Err(....)
}

NOTE:

This impl is done to avoid ending up with unpractical, verbose and/or bad handled conversions from the CtOption<T> wraps to an Option<T> or Result<T, E>. This implementation doesn't intend to be constant-time nor try to protect the leakage of the T since the Option<T> will do it anyways.

Closes #73 Closes #74

I wasn't sure about adding an Unreleased section on the CHANGELOG.md or just leave it to you so you can handle this however you want. In any case, if you need I can add whatever.

It also seems that cargo fmt was applied on some places. Maybe it would be nice to add a rustfmt.toml file or something similar in the future.

EDIT

The code uploaded to solve #73 & #74 includes a feature that was added to the Rust language in Rust_1.41.0 via RFC2451.

Therefore, the minimum version needed in order to allow the tests pass for the MSRV testcase is the one mentioned avobe.

As suggested per @hdevalence, it might not be worth it to try to support a +4yo version of Rust, so the .travis.yml has been changed in order to update the version used to test the MSRV case to 1.41.0.

I am trying to implement check for <=, but as far as I can tell I can only check for equality with this crate. Is this something that could be added here?

Choice doesn't provide a const fn for constructing the Choice, since you must use From to construct it. It might be nice to provide a from_u8 const constructor for users that need it.

This error occurred when I try to complile blake2 on Termux on my Android device: I think there is nothing wrong with my device because I can compile other crates successfully, maybe this is a bug?

Building with latest rust nightlies are throwing this error.

error: legacy asm! syntax is no longer supported
   --> /usr/local/cargo/registry/src/github.com-1ecc6299db9ec823/subtle-2.2.2/src/lib.rs:150:14
    |
150 |     unsafe { asm!("" : "=r"(input) : "0"(input) ) }
    |              ----^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
    |              |
    |              help: replace with: `llvm_asm!

So I did the change. ¯_(ツ)_/¯

I remember watching many Chandler Carruth talks in my past life as a C++ developer. Chandler Carruth is a major contributor to llvm.

I found a choice moment from one of his talks (watch for about 1 min)

https://www.youtube.com/watch?v=nXaxk27zwlk&amp=&t=40m40s

"The two scariest tokens for the optimizer are asm volatile"

here's the black box function at current revision

/// This function is a best-effort attempt to prevent the compiler
/// from knowing anything about the value of the returned `u8`, other
/// than its type.
///
/// Uses inline asm when available, otherwise it's a no-op.
#[cfg(all(feature = "nightly", not(any(target_arch = "asmjs", target_arch = "wasm32"))))]
#[inline(always)]
fn black_box(mut input: u8) -> u8 {
    debug_assert!((input == 0u8) | (input == 1u8));

    // Move value through assembler, which is opaque to the compiler, even though we don't do anything.
    unsafe { asm!("" : "=r"(input) : "0"(input) ) }

    input
}

I suspect that the asm block should actually have the volatile token here for llvm to see.

Moreover, I think that this code comment:

    // Move value through assembler, which is opaque to the compiler, even though we don't do anything.

is not correct -- the compiler CAN pull out your inline assembly and start optimizing it, UNLESS you mark it volatile. This is based largely on my understanding of Chandler Carruth's talks, and informal discussions with my boss at my previous job who had earlier been a core developer of clang and a major contributor to llvm.

Note that, I am not an expert on compilers or llvm, and I'm not claiming to be one, but I wonder if you would be interested in a patch to make this like:

    unsafe { asm!("" : "=r"(input) : "0"(input) : : "volatile" ) }

or if you know a good reason not to do this, cause then I would learn something :)

I have been testing subtle using dudect, provided by dudect-bencher.

From what I can tell, there is a short-circuit in both black_box functions and the From<Choice> for bool trait implementation for Choice. This affects both stable and nightly, but in debug-mode only.

I have only tested ct_eq.

The asserts that seem to short-circuit are:

https://github.com/dalek-cryptography/subtle/blob/558316bd54507ab4bebdfdf55fa0dff74f7a4d3a/src/lib.rs#L79

https://github.com/dalek-cryptography/subtle/blob/558316bd54507ab4bebdfdf55fa0dff74f7a4d3a/src/lib.rs#L147

https://github.com/dalek-cryptography/subtle/blob/558316bd54507ab4bebdfdf55fa0dff74f7a4d3a/src/lib.rs#L163

Commit bf3888e changes the debug_assert OR to a strict evaluation.

Before applying commit bf3888e in #42, these were the t-tests that dudect-bencher reported

• nightly + debug:

running 1 bench
bench test_secure_cmp seeded with [0xc8437c3f, 0x1ebd6d87, 0x4143a2d8, 0xd9e40fe5]
bench test_secure_cmp ... : n == +0.334M, max t = +747.27294, max tau = +1.29251, (5/tau)^2 = 14

• nightly + release:

running 1 bench
bench test_secure_cmp seeded with [0xdd26324, 0xb0cd6929, 0x38345f3b, 0xe33981da]
bench test_secure_cmp ... : n == +0.861M, max t = -2.28511, max tau = -0.00246, (5/tau)^2 = 4121111

• stable + debug:

running 1 bench
bench test_secure_cmp seeded with [0x8de2c6f6, 0xef48ef86, 0x1331bfd1, 0x6318f891]
bench test_secure_cmp ... : n == +0.663M, max t = +955.01525, max tau = +1.17311, (5/tau)^2 = 18

• stable + release:

bench test_secure_cmp seeded with [0x88de063f, 0xa3944eaa, 0xa16ddc08, 0x4860f51b]
bench test_secure_cmp ... : n == +0.997M, max t = -1.68096, max tau = -0.00168, (5/tau)^2 = 8821035

After applying commit bf3888e:

• nightly + debug:

running 1 bench
bench test_secure_cmp seeded with [0xf66c77e4, 0xb6ad3111, 0x3fc3413b, 0x957ba0f4]
bench test_secure_cmp ... : n == +0.997M, max t = +1.55842, max tau = +0.00156, (5/tau)^2 = 10261010

• nightly + release:

running 1 bench
bench test_secure_cmp seeded with [0x1a77a729, 0x7de4a2f2, 0x55470f7a, 0xa4a18553]
bench test_secure_cmp ... : n == +0.247M, max t = -1.39785, max tau = -0.00281, (5/tau)^2 = 3155259

• stable + debug:

running 1 bench
bench test_secure_cmp seeded with [0x47063cc9, 0x66d3dc0e, 0x20ece803, 0xad3363ae]
bench test_secure_cmp ... : n == +0.994M, max t = +2.07018, max tau = +0.00208, (5/tau)^2 = 5796406

• stable + release:

running 1 bench
bench test_secure_cmp seeded with [0x8587213f, 0xfb937a4f, 0xaab1fee2, 0x88f71c10]
bench test_secure_cmp ... : n == +0.983M, max t = +2.50388, max tau = +0.00253, (5/tau)^2 = 3919187

The tests can be found here: https://github.com/brycx/orion-dudect/tree/subtle-short-circuit/ct-bencher.

Rust version 1.66 now comes with a stabilized version of a black_box function that emits an "empty" assembly directive. This patch replaces the older optimization barrier, which was based on a volatile read with the newly standardized function.

Announcement from Mara: https://hachyderm.io/@Mara/109518823276877083

Current implementation of black_box in rustc: https://github.com/rust-lang/rust/blob/a803f313fdf8f6eb2d674d7dfb3694a2b437ee1e/compiler/rustc_codegen_llvm/src/intrinsic.rs#L341-L375

Review suggestions:

• This patch bumps the MSRV to the most recent version (1.66), which might be undesirable. One workaround is to wait for merging this until cfg_version is stabilized, and then write a fallback black_box based for rustc before 1.66.

This is a feature request to support the trait ConditionallySelectable for types that are not Copy.

Motivation

I have large types (e.g. polynomials of high degree) that I'd like to be conditionally selectable.

My problem

struct C(A, B);

fn create_c(a: &[u8], b: &[u8]) -> CtOption<C> {
    let a: CtOption<A> = A::from_bytes(a);
    let b: CtOption<B> = B::from_bytes(b);
    // ???
}

Proposed solution

impl<T,U> CtOption<T> {
    pub fn merge<U>(self, other: CtOption<U>) -> CtOption<(T,U)> {
        CtOption {
            value: (self.value, other.value),
            is_some: self.is_some & other.is_some,
        }
    }
}

let c = a.merge(b).map(|(a, b)| C(a,b));

May I prepare a PR? Or do you have any better idea?

I am working on a project that has a policy to avoid BSD 2- and 3-clause licenses due to the complexity of satisfying the attribution clause:

Redistributions in binary form must reproduce the above copyright notice, this list of conditions and the following disclaimer in the documentation and/or other materials provided with the distribution.

Would you consider dual-licensing this project? Eg with MIT and/or Apache 2.0 licenses?

https://github.com/dalek-cryptography/subtle/blob/b4b070c3faf87cb8f324bd0ed0a5e5ec32d3a5b0/src/lib.rs#L223 remarks that u8 is neither Send nor Sync, however u8 has auto-trait implementations for both: https://doc.rust-lang.org/std/primitive.u8.html#impl-Sync