Repr endianness vs RFC6979

[rvolgers]

I believe the current ecdsa code uses from_repr and to_repr when generating a k value in ways which are only fully compliant with RFC6979 if the internal representation is big endian. The docs for these functions claim that the endianness of the internal representation is not defined at the trait level.

I'm assuming current curves choose a big endian representation, but it would be better to use an API which provides defined endianness.

The reason I'm making an issue out of this is because it seems sloppy to use APIs with undefined endianness and since I'm working on DSA related code I'd like to understand the situation.

The code in question:

signatures/ecdsa/src/rfc6979.rs

Lines 31 to 42 in bfd60ba

	let mut x = secret_scalar.to_repr();
	let h1 = Scalar::<C>::from_digest(msg_digest).to_repr();
	let mut hmac_drbg = HmacDrbg::<D>::new(&x, &h1, additional_data);
	x.zeroize();
	loop {
	let mut tmp = FieldBytes::<C>::default();
	hmac_drbg.generate_into(&mut tmp);
	if let Some(k) = NonZeroScalar::from_repr(tmp) {
	return Zeroizing::new(k);
	}
	}

[tarcieri]

There is no practical reason to worry about ECDSA with endianness other than big endian. Doing as such would violate ECDSA specifications like ANSI X9.62. More generally I like to avoid introducing complexity where it need not exist, and ECDSA is already full of it.

ECDSA is a legacy algorithm and effectively an evolutionary dead end. It's a somewhat bizarre adaptation of DSA to elliptic curves which uses ECDLP to prevent reversal of an integer division operation.

Elliptic curves are capable of much more powerful group-based signature algorithms based on things like Schnorr signatures. The EdDSA family (i.e. Ed25519, Ed448) is a concrete example. There are many other Schnorr-based protocols being explored, like Taproot/MuSig, Schnorrkel, and FROST.

Many of those new signature formats are using little endian exclusively. To the extent that there's any need to worry about usage of little endian in future curves, it's happening in signature algorithms that aren't ECDSA.

[rvolgers]

There is no practical reason to worry about ECDSA with endianness other than big endian. Doing as such would violate ECDSA specifications like ANSI X9.62.

This almost sounds like you think I'm worried about people who want to use ECDSA in a little-endian way, but that wasn't my point at all.

My point is the internal Scalar representation does not have a defined endianness (at least according to its docs), so it should probably not be used directly for any algorithm which wants a defined endianness, whether little endian or big endian, modern or dead end.

I know this doesn't matter, I'm just trying to understand the APIs better and that includes poking at weird things and seeing if my understanding is correct.

[tarcieri]

That's a much more general concern than ECDSA. If you want to talk about external representations of scalars for elliptic curves, I'd suggest filing an issue against the elliptic-curve crate in https://github.com/rustcrypto/traits

That said, it's a somewhat valid concern, but it seems like for things like external representations of the scalar field most curves choose one encoding or the other, and to the extent the elliptic-curve doesn't prescribe a specific encoding or provide knobs around it, it's because generally it's an implementation detail left up to a particular curve implementation and I can't think of a case in the wild where there isn't a specific endianness always used by a particular curve.

[tarcieri]

Also note that long-term, we'll probably migrate to scalar field representations as managed by the ff crate

[rvolgers]

Thank you. The reason I use a specific, DSA-related example is because that is the code I have in front of me and am somewhat familiar with now.

I am more familiar with RSA and DSA in protocols such as SSH and PGP, and in that world everything at the crypto layer is just abstract bigints with a wire encoding defined on another layer, so it feels strange to me to not be able to get defined-endianness data. I guess modern EC curve specs like to control the representation side because of things like point compression and not all values being legal for some curves, and also because they tend to micro-optimize the various formulas for a representation, and also just because being overly generic and algorithm agility has gone out of style? If that's what you're used to I understand defined endianness not being a significant thing.

[tarcieri]

Yeah, that pretty much covers it. To the extent there's a choice about endianness of external representations of field elements with ECC, it's generally made at a curve-by-curve level. Older curves use big endian, and newer curves have generally moved to little endian.

I expect being able to specify the endianness of the external representations of scalar fields will eventually come up, but when it does, it will be as part of something like extracting a general purpose const generic bignum library as part of work like RustCrypto/elliptic-curves#218

[tarcieri]

The concerns in this issue are eliminated by the rfc6979 crate (originally added in #409)

It's implemented using types from the crypto-bigint crate, which allows a common integer type for either DSA or ECDSA private scalars.

It also provides endian-aware serialization methods, which always use big endian in the RFC6979 implementation:

https://github.com/RustCrypto/signatures/blob/090a85a/rfc6979/src/lib.rs#L49-L56