Short-circuit in debug mode resulting in non-constant-time execution

[brycx]

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:

subtle/src/lib.rs

Line 79 in 558316b

debug_assert!(source.0 == 0u8 || source.0 == 1u8);

subtle/src/lib.rs

Line 147 in 558316b

debug_assert!(input == 0u8 || input == 1u8);

subtle/src/lib.rs

Line 163 in 558316b

debug_assert!(input == 0u8 || input == 1u8);

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.

[isislovecruft]

Hi @brycx! Thanks for finding this and for the detailed write up. It seems you are correct that Rust's logical OR and AND operators short-circuit the evaluation at runtime (unless they are part of a const evaluation, which is actually a bug/not-yet-implemented feature). We don't guarantee anything in debug mode since there's are likely other debug runtime checks being performed which invalidate constant-timedness.

Thanks so much for the patch!

[brycx]

Hi @isislovecruft! I'm glad I could contribute to this great crate.

We don't guarantee anything in debug mode since there's are likely other debug runtime checks being performed which invalidate constant-timedness.

This comes as a surprise to me. Even though it's a very reasonable limitation, I haven't found any explicit mentions of this (either that debug should be avoided, or that only release is supported) in the README or the docs, which has made me assume otherwise.

Personally, I think that it should be mentioned in the README and docs, that you only support release mode for security reasons and users should avoid debug, due to the reason you mentioned above. I also think this should be added to the RustSec advisory database, because if other people have assumed constant-time execution in debug mode, like myself, then they should be made aware of this. It would hopefully also increase the number of people who would read the additions to the aforementioned security limitations.

What do you think?

[hdevalence]

Hi @brycx, thanks for digging into this, this is great work. If you wanted, it would be great if you wrote up something on the methodology and results somewhere (like a blog or something).

With regard to the debug-mode issue, it's true that it's not mentioned in the docs, and that's probably a documentation bug. It would be good to make that explicit, adding something like "Note that this crate includes additional debug assertions in debug builds; only release builds should be used in production", but I don't consider it a security issue, because debug mode is for debugging, not for running in production with secret data.

For example, the curve25519-dalek code is also non-constant-time in debug mode by design, because it inserts debug assertions that check pre-and-post conditions on the field arithmetic. (This is also why debug mode is 300x slower than release mode).

[brycx]

If you wanted, it would be great if you wrote up something on the methodology and results somewhere (like a blog or something).

Certainly, I can scribble something down once I've wrapped up the rest of my testing.

"Note that this crate includes additional debug assertions in debug builds; only release builds should be used in production"

I think explicitly mentioning the constant-time execution would be good, to make it clear why it should be avoided. Perhaps "Note that this crate includes additional debug assertions in debug builds, which can cause the code not to run in constant-time. Only release builds should be used in production."?

but I don't consider it a security issue, because debug mode is for debugging, not for running in production with secret data.

That makes sense.

For example, the curve25519-dalek code is also non-constant-time in debug mode by design

Should this also have a doc mention about debug builds in that case?

[isislovecruft]

Merged in for 1.0.1 and 2.0.1