k256 Point deserialization+serialization round trips incorrectly

[randombit]

TBH I'm not sure if this is a bug in k256 or a Rust miscompilation bug.

We've found that in certain cases k256 compressed point serialization and deserialization do not round trip correctly. In particular the sign of y will for certain rare points, be flipped.

This is using k256 0.10.2, rustc 1.58.1

use k256::elliptic_curve::group::GroupEncoding;
use k256::elliptic_curve::sec1::FromEncodedPoint;

pub fn deserialize(bytes: &[u8]) -> Option<k256::ProjectivePoint> {
    match k256::EncodedPoint::from_bytes(bytes) {
        Ok(ept) => {
            let apt = k256::AffinePoint::from_encoded_point(&ept);

            if bool::from(apt.is_some()) {
                Some(k256::ProjectivePoint::from(apt.unwrap()))
            } else {
                None
            }
        }
        Err(_) => None,
    }
}

pub fn serialize(pt: k256::ProjectivePoint) -> Vec<u8> {
    pt.to_affine().to_bytes().to_vec()
}

fn main() {
    let bits =
        hex::decode("024b395881d9965c4621459ad2ec12716fa7f669b6108ad3b8b82b91644fb44808").unwrap();

    let pt = deserialize(&bits).unwrap();

    let pt_bytes = serialize(pt);

    assert_eq!(bits, pt_bytes);
}

In release mode (only), this fails:

$ cargo run --release
   Compiling k256-bug v0.1.0 (/home/jack/sw/k256-bug)
    Finished release [optimized] target(s) in 0.58s
     Running `target/release/k256-bug`
thread 'main' panicked at 'assertion failed: `(left == right)`
  left: `[2, 75, 57, 88, 129, 217, 150, 92, 70, 33, 69, 154, 210, 236, 18, 113, 111, 167, 246, 105, 182, 16, 138, 211, 184, 184, 43, 145, 100, 79, 180, 72, 8]`,
 right: `[3, 75, 57, 88, 129, 217, 150, 92, 70, 33, 69, 154, 210, 236, 18, 113, 111, 167, 246, 105, 182, 16, 138, 211, 184, 184, 43, 145, 100, 79, 180, 72, 8]`', src/main.rs:31:5

So far we have not been able to reproduce this in either debug mode or with coverage guided fuzzing enabled.

[randombit]

Fails in the same way with Rust 1.59.0 and also currently nightly (1.61.0-nightly (e95b10ba4 2022-03-13))

[randombit]

Maybe a hint, enabling debug assertions seems to paper over the issue

[profile.release.package.k256]
debug-assertions = true

[randombit]

debug-assertions being enabled or not seems to be the critical thing. Even

[profile.release.package.k256]
opt-level = 0
debug-assertions = false

produces the incorrect result.

[tarcieri]

One thing that jumps to mind is the base field implementation. There's some gating on debug_assertions occurring here:

https://github.com/RustCrypto/elliptic-curves/blob/f60fc7f/k256/src/arithmetic/field.rs#L17-L32

cc @fjarri

[fjarri]

Wow, that's weird. FieldElementImpl is not supposed to modify any behavior, it just maintains the magnitude counter and checks that it doesn't overflow.

[tarcieri]

Yeah, I don't see anything that might be an immediate culprit. However, it's the only thing in k256 gated on debug_assertions.

[fjarri]

Right, so actually my assertion about FieldElementImpl was not entirely correct, and I think it is the reason for the bug. FieldElementImpl::is_odd() is

    pub fn is_odd(&self) -> Choice {
        self.normalize().value.is_odd()
    }

While the respective non-debug method does not perform normalization. So in AffinePoint::decompress(), after let beta = alpha.sqrt(); beta can be un-normalized (with magnitude 1). If this is the case, beta.is_odd() will return different values in release and debug. I wonder what are the odds of this happening (and how lucky @randombit was to be able to catch it), seems like a serious issue.

I'll make a PR.

[randombit]

@fjarri This was causing a test running a threshold ECDSA signature scheme (which internally uses k256 for point arithmetic) to fail once every ~5000 runs or so. Very roughly it seems to be a problem for 1 in a million points.

If it is useful, other points we found that trigger this are

• 02e77d7b458fb3a2df7d201806e8e1dbce8c1138303156c43398ac62891c43e3cc
• 02f973e12be0ea160cc82c16563753749b5e6590d22a0b9ab16cd48b9bd951b167

[fjarri]

Interesting, if the probability to hit the un-normalized region was uniform, it would be ~1/2^(256-32) chance, but evidently it happens much more often than that.

[randombit]

Thank you for the very fast patch!

[tarcieri]

@randombit can you confirm v0.10.3 fixes the issue? (see #532)

[randombit]

@tarcieri Everything looks good in my tests so far. Our CI system is jammed up ATM so I won't be able to confirm for certain until tomorrow.