P521 FieldElement conversions can panic

[daxpedda]

Minimal test case:

let _ = PublicKey::<NistP521>::from_sec1_bytes(&[
    2, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
    0, 0, 0, 0, 0, 0, 0,
]);

... instead of returning an error it panics with:

Input bound for the result[65] is [0x0 ~> 0x1]

I believe this can be boiled down to:

FieldElement::from_uint_unchecked(U576::from_be_slice(&[
    0, 0, 0, 0, 0, 2, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
]));

... where FieldElement is in p521::arithmetic::field::FieldElement, but is actually not public.

[tarcieri]

Hmm, where did you get that key from?

The panic is certainly bad, yes, but it seems like the given coordinate is invalid? It's:

0x20000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000

...which exceeds the field modulus size:

0x1ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff

...in fact, it's p + 1

[tarcieri]

Aha, I see the problem: https://github.com/RustCrypto/elliptic-curves/blob/f19ccf0/p521/src/arithmetic/field.rs#L84-L87

That function checks that the input Uint is less than the modulus, returning a subtle::Choice.

As currently written, the Uint is then unilaterally decoded regardless of whether or not it exceeds the modulus. This means an invalid Uint that exceeds the modulus can be passed to u576_to_le_bytes, so invalid inputs are always decoded in a constant time-ish manner, with ones that exceed the modulus rejected via CtOption.

@MasterAwesome I guess we should just remove the debug_assert!s from u576_to_le_bytes and treated more as an invariant which needs to be asserted elsewhere, in this case by from_uint, but more generally by any caller of from_uint_unchecked, with the caveat that calling it with a value that exceeds the modulus can have undefined results.

Edit: went ahead and did that in #967

[daxpedda]

Hmm, where did you get that key from?

Apologies for the lack of context here!
There was no key like that, this was discovered in fuzzing tests making sure that deserialization of a wrapping type can't panic.

Thank you for the quick fix!