elliptic-curve: `SecretKey::from_slice` time variability

[fjarri]

At the moment SecretKey::from_slice allows up to 4 most significant bytes to be missing. According to the PR description that introduced it, it's done to support some formats that strip leading zeros. I've got two questions about that:

• Why is it only 4? Does that mean that in about 1/2^(8*4) cases it will fail? This is not that small of a probability considering the wide usage of the crate. Could that be modified to automatically add leading zeros to any number of bytes smaller than the full representation?
• Given this behavior, should this method be explicitly marked as vartime?

[tarcieri]

@fjarri this was introduced to tolerate some unusual (and technically invalid) keys being generated by ssh-keygen: https://github.com/RustCrypto/elliptic-curves/issues/769

I'm open to alternative design considerations on this, but note that typical usages do not encounter this problem.

I would prefer not to rename from_slice to from_slice_vartime. There's always going to be some length-related branching around slices. To the extent it can introduce timing variability I'd say we should just document it.

[fjarri]

I don't think that there would be any timing variability if the slices were restricted to a specific length, but I agree, at least we should document it.

As for the limit, I think ssh-keygen can generate keys with more than 4 leading zero bytes, and in general, if we are padding the slice with zeros, there is no reason to have an arbitrary limit.

[tarcieri]

The reason I included a limit at all was to catch egregious misuses.

Do you think it should accept an empty slice as a valid input?

[fjarri]

Probably not. Empty slice is not a number, but a single byte is.

[tarcieri]

We can turn the limit down to 1-byte, but is that really an improvement?

[fjarri]

I think it is, albeit a small one. It makes the API logical, and avoids a small but probable possibility of failure.

[tarcieri]

It makes the API logical

I'm not sure what this means.

My counterpoint would be that someone passing a 1-byte slice as a SecretKey has almost certainly made a mistake.

[fjarri]

Having a 4 byte limit raises a question - why 4 specifically? There is no logical answer to that.

I can imagine someone passing 1 byte for testing purposes. I don't think it's a good idea in this case to try and "protect" the user, because it can just as likely cause frustration. I've encountered a prime generation library that only generated primes over 128 bits in size. Why? Because primes under 128 bits are insecure. If your application doesn't care about security, or you need a more digestible test, you're out of luck. I fully support fool-proof APIs, but only when the prohibited ways to use them are incorrect 100% of the time. Otherwise, leave it to the user to decide.

Anyway, that's my opinion. I opened this issue to understand the motivation behind that API and to make sure it wasn't an oversight. If it wasn't, feel free to close it.

[tarcieri]

It's a debatable point. I'm open to changing how it's implemented.

The choice of 4 is admittedly arbitrary. Perhaps we could find a better, more easily justifiable minimum threshold.

[tarcieri]

How about 192-bits as an absolute minimum size? That's 32-bits lower than the NIST recommended minimum of 224-bits.

For NIST P-224, when dealing with these malformed keys generated by ssh-keygen it would fail for 1:2^32 keys, or 1:4.3 billion. However, I think it represents a dangerously low threshold at which keys lack enough entropy to be secure (i.e. 96-bits equivalent symmetric security).

[tarcieri]

Here's another use case: https://github.com/rozbb/rust-hpke/pull/54#issuecomment-1817066355

I've opened #1412 with my earlier suggestion of a 192-bit/24-byte minimum key size, which provides the equivalent of 96-bit symmetric security.

[tarcieri]

I'm adding a note to the rustdoc that SecretKey::from_slice is variable-time with respect to the input in #1480, which suggests ensuring the input is padded to avoid that.

Otherwise, I'm going to call this working as intended. There are sufficient real-world use cases where we have to support something like this, and IMO the whole point of a from_slice-style API is to be able to handle variable-sized inputs.