Meet undocumented scalar contract in current Karatsuba code about curve25519-dalek HOT 7 CLOSED

I put some commits here: https://github.com/chain/curve25519-dalek/tree/optimized_scalar that remove the masking of the high 3 bits, so that the unpacked scalar types (Scalar32 / Scalar64) treat the bytes of a Scalar as a 256-bit integer. I also added a fuzzer.

It seems like there's a problem with the Scalar64 code. The test vectors are in this test: https://github.com/chain/curve25519-dalek/commit/94ef56ad230ec680ba69907bab77ccaf40903660

from curve25519-dalek.

Aside from hating the clamping and masking and Ed25519 managing to use 3 different convoluted types of scalars (clamped partial hash, masked but unreduced, and reduced from hash)..

Maybe have a Scalar::clamp() method that clamps & (doesn't reduce! doesn't!) the scalar bytes (which would cover Ed25519/Curve25519), and a Scalar::mask() method that clears the top 3 bits and returns if they were non-zero (which covers Ed25519 signatures)?

The Scalar64 bug is very embarrassing, from_bytes_wide initializes words as [064; 16] instead of [0u64; 8]. 064 seems to just be parsed as 64 as well, no warnings about octal or possible mistyped constant?

from curve25519-dalek.

I don't think that clamping/masking really makes sense in the Ristretto case, where you have a genuine prime-order group, which should probably be the focus for curve25519-dalek. So I think the thing to do in curve25519-dalek is to treat a Scalar as a 256-bit integer representing an integer mod l and providing a Scalar::reduce() method that reduces the Scalar mod l (to produce the canonical representative).

Since the clamping, masking, etc. is not compatible with doing arithmetic (because it's not well-defined mod l), maybe it should be kept out of curve25519-dalek and left in protocol-specific ed25519-dalek, x25519-dalek crates?

from curve25519-dalek.

Since the clamping, masking, etc. is not compatible with doing arithmetic (because it's not well-defined mod l), maybe it should be kept out of curve25519-dalek and left in protocol-specific ed25519-dalek, x25519-dalek crates?

Yeah, the clamping and masking isn't the most elegant. As mentioned, it's breaking the (so far, implicit) contract on what exactly a scalar is, and it produces bias in the keys. So, I'm in full agreement that if a protocol is designed to do something that hideous it should stay in the protocol's implementation (and preferably in a manner which doesn't encourage anyone to repeat the behaviour!).

I reverted the revert of floodyberry's code in my optimzed_scalar_r1, which also includes:

• a fix for the typo,
• the fuzz tests that caught it,
• more unittests, and
• removes some code for operations which have no effect (i.e. masking a integer which cannot possibly exceed the mask size).

Probably we still need better documentation on scalar behaviour? Opinions, @hdevalence?

from curve25519-dalek.

I would like to rearrange some of the scalar behaviour and documentation to better align it with the Ristretto use-case, but that could be in a later issue during other refactoring...

from curve25519-dalek.

Okay, sounds good. I'll merge the working branch here so that we have @floodyberry's improvements, and the docs can happen when we move stuff around.

from curve25519-dalek.

Merged for 0.13.x.

from curve25519-dalek.