`Ord` and `PartialEq` of `SecretKey` are not constant time.

[Kixunil]

They are implemented using impl_array_newtype macro which just calls comparison methods from core which are not constant time. This seems to be a foot gun. Hash is also questionable - what if someone has a leaking hasher? Maybe we should sha256 it first?

[apoelstra]

Agreed on all counts. I'm not sure if we should push this upstream -- upstream we just treat secret keys as 32-byte blobs and if users want to compare them they're expected to do this themselves .... probably using the non-constant-time memcmp. cc @real-or-random do you think we should expose constant-time secret key comparison functions in libsecp?

Meanwhile we should definitely fix this here. We could sha2-then-compare, which would actually fix the problem for Ord and Eq without us needing to worry about the compiler or CPU screwing us :) though the perf hit (~200x I'd guess) is probably prohibitive.

For Hash you may be right that the best course of action for us is to just implement Hash by feeding a truncated sha2 into the untrusted hasher....still a big perf hit but probably fine as a default. Users who really know what they're doing will be able to work around this by e.g. converting to slices.

[Kixunil]

From my experience this shouldn't be optimized to non-const time:

fn eq(&self, other: &Self) -> bool {
    let accum = self.0.iter().zip(&other.0)
        .fold(0, |accum, (a, b)| accum | a ^ b);
    unsafe { core::ptr::read_volatile(&accum) == 0 }
}

Godbolts compiler explorer

Not sure how to safely impl Ord though.

We could also remove Hash impl with explanation.

[real-or-random]

cc @real-or-random do you think we should expose constant-time secret key comparison functions in libsecp?

Hm, I don't see an immediate use case for comparing secret keys but I guess bindings to higher-level languages is reasonable... We also added to pubkey comparison function. It wouldn't hurt to export a generic constant-time comparison function.

[real-or-random]

Meanwhile we should definitely fix this here. We could sha2-then-compare, which would actually fix the problem for Ord and Eq without us needing to worry about the compiler or CPU screwing us :) though the perf hit (~200x I'd guess) is probably prohibitive.

Nah this sounds expensive and also the resulting order would be pretty arbitrary.

I think it makes sense to look at other good crypto libraries and see how they implemented. This here is interesting https://stackoverflow.com/a/44691912 and matches what people usually do in C.

[RCasatta]

I think it makes sense to look at other good crypto libraries and see how they implemented. This here is interesting https://stackoverflow.com/a/44691912 and matches what people usually do in C.

If you take @Kixunil example in godbolt and remove the read_volatile (obtaining pretty the same as the StackOverflow answer) it gets optimized

[Kixunil]

@RCasatta it looks like the optimized code could still be constant time but I'm not knowledgeable enough about SIMD to be sure. If it was just me I'd rather keep read_volatile and risk wasted CPU time than risking non-const time. If anyone with SIMD expertise can confirm and explain why it's constant time, that'd be nice.

BTW in some future MSRV we could use an empty asm block instead of read_volatile.

[apoelstra]

It's a bit early, but it's possible that we could use a solution to Yao's Millionaire's Problem (computing leq in MPC) to compute leq in constant time, by appropriate replacement of crypto primitives by xors or something.

It also wouldn't be totally unreasonable to drop the Ord impl, whose uses seem pretty niche (and almost guaranteed to be leaky anyway, e.g. if you put a bunch of keys in a BTreeMap then you know the first one in the map will have a lower numeric value than average), nor would it be totally unreasonable to just implement a crazy and slow ordering like sha2-lexicographic. The idea being that users would only want this to derive Ord on larger structures where hopefully the secret keys aren't the primary ordering key.

[Kixunil]

almost guaranteed to be leaky anyway

Yeah, good point, silently making performance terrible doesn't sound appealing and not having the traits is a good opportunity to document the issue and teach newbies about the dangers.

users would only want this to derive Ord on larger structures where hopefully the secret keys aren't the primary ordering key.

We could also just always return equal. :) Manual impl seems better anyway. If anyone actually has this problem maybe this is motivation for adding customized derive to amplify-derive with skip attribute.

Also let's not forget - in case of sha256 or always-equal we would have to avoid Borrow.

[apoelstra]

It occurred to me to always return equal, but I think we're not allowed to do that if PartialEq is implemented differently? (And we do want to implement PartialEq properly, there are plenty of safe and legit usecases for determining whether keys are repeated.)

I don't understand what you mean about 'Borrow'.

[Kixunil]

Oh, yes, good point. Borrow requires that, if implemented (Partial)Eq, (Partial)Ord, and Hash return same values for borrowed and non-borrowed inputs.

[real-or-random]

@apoelstra Okay yeah, my first thought was that dropping Ord or Hash will likely hit some users. But if they really use secret keys as an index for a data structure or do something similar, it's probably good that we'll break their code...

[apoelstra]

Ah good catch @Kixunil -- I didn't know that about Borrow. I guess this forces our hands, semantically speaking, to implement ord/eq/hash based on the raw bytes (or not implement them at all).

[sanket1729]

I think we need atleast Partial(Eq). It is really handy to test misc things like key derivations.

(or not implement them at all).

I am okay if we drop Partial(Ord) requirements. If we really need we can expose it under a new feature or as a ComparableSecret type that allows users to opt-in into comparing if they really need it.

[Kixunil]

Based on the discussion my current preference is:

• Impl (Partial)Eq manually using the code in my comment with read_volatile
• Remove (Partial)Ord and Hash
• Explain both in realease notes and doc comments why those traits are intentionally unimplemented and explain that (Partial)Eq is protected.

[apoelstra]

Agreed, but I think we should also

• Add a OrdSecretKey type which does impl Ord and Hash, with a bunch of doc warnings that Ord at least is not constant-time, and Hash might not be

[Kixunil]

Couldn't users just use arrays?

[apoelstra]

Oh, derp, yes. We should doccomment that :)