Refactoring for constant time guarantees

[juliusl]

I wasn't sure how to title this in a more inquisitive way, but I was reviewing some of the implementation, and I was wondering if there are some places where some potential branching should/could be removed.

I have a couple of examples that I wanted to go through to see if these concerns are valid before putting anything through valgrind to do any type of deeper analysis.

Example 1

dryoc/src/blake2b/blake2b_soft.rs

Lines 86 to 88 in 49e01a6

	for i in 0..16 {
	tm[i] = load_u64_le(&block[(i * 8)..(i * 8 + 8)]);
	}

Since the for loop is used over a constant range, would it make more sense to unroll it to remove the compiler from the equation?

Example 2

https://github.com/brndnmtthws/dryoc/blob/49e01a6ca6991ede91da0f4151ab23ff82530f2b/src/classic/crypto_kdf.rs#L52C1-L65C6

pub fn crypto_kdf_derive_from_key(
    subkey: &mut [u8],
    subkey_id: u64,
    context: &Context,
    main_key: &Key,
) -> Result<(), Error> {
    if subkey.len() < CRYPTO_KDF_BLAKE2B_BYTES_MIN || subkey.len() > CRYPTO_KDF_BLAKE2B_BYTES_MAX {
        Err(dryoc_error!(format!(
            "invalid subkey length {}, should be at least {} and no more than {}",
            subkey.len(),
            CRYPTO_KDF_BLAKE2B_BYTES_MIN,
            CRYPTO_KDF_BLAKE2B_BYTES_MAX
        )))
    } else {

Should this be refactored to remove the if statement? This one is a bit trickier, but it would mean you use a trait with a constant generic to apply the subkey check and change the parameters to accept only sized arrays instead of a slice.

So something like:

trait Subkey<const LENGTH: usize>
    // Picking some random bounds
    const SUBKEY_LENGTH_MIN: () = assert!(LENGTH >= 32);
    const SUBKEY_LENGTH_MAX: () = assert!(LENGTH < 64);
}

impl<const L: usize> Subkey<L> for [u8; L] {}

const fn test_subkey_check<const L: usize, K: Subkey<{L}>>(_: &K) {
    let _ = K::SUBKEY_LENGTH_MAX;
    let _ = K::SUBKEY_LENGTH_MIN;
}

#[test]
const fn test_subkey() {
    let test_key: [u8; 2] = [0; 2];

    test_subkey_check(&test_key);
}

which would fail to compile with this,

error[E0080]: evaluation of `<[u8; 2] as Subkey<2>>::SUBKEY_LENGTH_MIN` failed
  --> test.rs:90:35
   |
90 |     const SUBKEY_LENGTH_MIN: () = assert!(LENGTH >= 32);
   |                                   ^^^^^^^^^^^^^^^^^^^^^ the evaluated program panicked at 'assertion failed: LENGTH >= 32', test.rs:90:35
   |
   = note: this error originates in the macro `assert` (in Nightly builds, run with -Z macro-backtrace for more info)

note: erroneous constant encountered
  --> test:98:13
   |
98 |     let _ = K::SUBKEY_LENGTH_MIN;
   |             ^^^^^^^^^^^^^^^^^^^^

note: the above error was encountered while instantiating `fn test_subkey_check::<2, [u8; 2]>`
   --> test:105:5
    |
105 |     test_subkey_check(&test_key);
    |     ^^^^^^^^^^^^^^^^^^^^^^^^^^^^

For more information about this error, try `rustc --explain E0080`.
error: could not compile `test` (lib test) due to 1 previous error

Let me know if I am off base at all, but for context I was looking at the KDF code and I was thinking about how someone might want to run the subkey generation several times, and so that got me thinking about side-channel attacks and finally reviewing the code to check for any branching code.

Just to re-iterate I haven't used any analysis tools yet so I'm not implying any issues currently exist, I'm mainly inquiring to explore and learn.

[brndnmtthws]

This is great, very thoughtful and I appreciate your attention to detail.

For example 1 above, I think you are quite right, unrolling the loop makes sense here. I think this particular example is benign, but it would be even more benign if it's unrolled.

Example 2 is a bit more tricky. Because the length checks in the branch will always be evaluated, it's not susceptible to any timing attacks because the timing only changes for invalid (and therefore irrelevant) keys. In other words, under normal circumstances, the number of instructions executed will always be the same which doesn't leak any information about the key itself other than the fact that it's valid.

The problem with your solution-which is very clever by the way–is twofold:

1. It's not quite compatible or equivalent to the libsodium implementation, and for this particular function it should stay as close as possible to being equivalent to the C implementation. In the case of libsodium, the key length is a separate function parameter, but in the Rust case we just use the length of the slice.
2. Changing the signature as it is would be a breaking change (which is not an impossible challenge, it just means doing a breaking version change).

It's worth taking a look at the libsodium implementation here for reference (which is quite well vetted):

https://github.com/jedisct1/libsodium/blob/1012bbc380c81bf7782a85d43c2c9ed7caf8c8b9/src/libsodium/crypto_kdf/blake2b/kdf_blake2b.c#L31-L52

You'll notice lines 43-47 contain the same code.

I'm not against trying to harden this up, it's not a bad idea to refactor if possible by skipping the check when we call the function here:

dryoc/src/kdf.rs

Lines 132 to 144 in 49e01a6

	pub fn derive_subkey<Subkey: NewByteArray<CRYPTO_KDF_KEYBYTES>>(
	&self,
	subkey_id: u64,
	) -> Result<Subkey, Error> {
	let mut subkey = Subkey::new_byte_array();
	crypto_kdf_derive_from_key(
	subkey.as_mut_array(),
	subkey_id,
	self.context.as_array(),
	self.main_key.as_array(),
	)?;
	Ok(subkey)
	}

And then moving the inner part of crypto_kdf_derive_from_key() such that we can skip the check when you call Kdf::derive_subkey() if that makes sense. The Kdf::derive_subkey() method already uses a fixed-length array for the subkey, so we don't need to check the length in that spot.

[juliusl]

Example 2 is a bit more tricky. Because the length checks in the branch will always be evaluated, it's not susceptible to any timing attacks because the timing only changes for invalid (and therefore irrelevant) keys.

That makes sense, so basically the only information you could derive (in that specific example) is that the length of the key is correct.

It's not quite compatible or equivalent to the libsodium implementation, and for this particular function it should stay as close as possible to being equivalent to the C implementation. In the case of libsodium, the key length is a separate function parameter, but in the Rust case we just use the length of the slice.

That makes a lot of sense, since I think libsodium probably has had an audit at this point, that's probably the safest approach.

Thanks for such a quick response! If there are any items you'd like help with in general, I don't mind picking any issues you tag as such. I really appreciate the goals of this crate so I'm happy to contribute in any way I can.