fiat-crypto
fiat-crypto copied to clipboard
mit-plv
Document recommended ladder code?
I tried switching Go's curve25519 implementation to use fiat-crypto (golang.org/cl/314889), and some (5/16) of the test vectors are failing. The same ones with both the 32-bit and 64-bit routines:
Failing test vectors
--- FAIL: TestTestVectors (0.00s)
--- FAIL: TestTestVectors/Generic (0.00s)
curve25519_test.go:69: in = 668fb9f76ad971c81ac900071a1560bce2ca00cac7e67af99348913761434014
curve25519_test.go:70: base = db5f32b7f841e7a1a00968effded12735fc47a3eb13b579aacadeae80939a7dd
curve25519_test.go:71: got = 78202e24db99e237f2a14f9ec61b051814ec8fd23a5e8e68add48d66fd09fc12
curve25519_test.go:72: expect = 090d85e599ea8e2beeb61304d37be10ec5c905f9927d32f42a9a0afb3e0b4074
curve25519_test.go:69: in = 203161c3159a876a2beaec29d2427fb0c7c30d382cd013d27cc3d393db0daf6f
curve25519_test.go:70: base = 6ab95d1abe68c09b005c3db9042cc91ac849f7e94a2a4a9b893678970b7b95bf
curve25519_test.go:71: got = 2ec45ca394a3febc6d63b8995ae63b38c7ba909bafed2a039dd54973f2b5be73
curve25519_test.go:72: expect = 11edaedc95ff78f563a1c8f15591c071dea092b4d7ecaac8e0387b5a160c4e5d
curve25519_test.go:69: in = 13d65491fe75f203a008b4415abc60d532e695dbd2f1e803accb34b2b72c3d70
curve25519_test.go:70: base = 2e784e04ca0073336256a839255ed2f7d4796a64cdc37f1eb0e5c4c8d1d1e0f5
curve25519_test.go:71: got = 87ee46a4852cd8088ec646518cbadb6614e54365e5bfc11215fb39229c107224
curve25519_test.go:72: expect = 563e8c9adaa7d73101b0f2ead3cae1ea5d8fcd5cd36080bb8e6ec03d61450917
curve25519_test.go:69: in = 7dc76404831397d5884fdf6f97e1744c9eb118a31a7b23f8d79f48ce9cad154b
curve25519_test.go:70: base = 1acd292784f47919d455f887448358610bb9459670eb99dee46005f689ca5fb6
curve25519_test.go:71: got = c69c617cf53db5c00c1942a920745f2bce27aca666261feed0cbcfe3bb7e3a19
curve25519_test.go:72: expect = 00f43c022e94ea3819b036ae2b36b2a76136af628a751fe5d01e030d44258859
curve25519_test.go:69: in = 4e060ce10cebf095098716c86619eb9f7df66524698ba7988c3b9095d9f50134
curve25519_test.go:70: base = 57733f2d869690d0d2edaec9523daa2da95445f44f5783c1faec6c3a982818f3
curve25519_test.go:71: got = 73ce4a41689ff9d7b3238cfe80fd29db5acf2b68e676b2c55a099f338d012b1c
curve25519_test.go:72: expect = a61e74552cce75f5e972e424f2ccb09c83bc1b67014748f02c371a209ef2fb2c
It looks like BoringSSL uses a slightly different ladder that distinguishes loose from strict elements (https://boringssl.googlesource.com/boringssl/+/master/crypto/curve25519/curve25519.c#2006), but I at least couldn't immediately spot any meaningful differences. In particular, even scattering explicit calls to Carry everywhere didn't seem to help.
/cc @JasonGross @andres-erbsen @filosottile
I think BoringSSL masks out the high bit when converting from bytes, while we just assert this fact in our precondition comment. Is it possible that this is what's missing?
I don't think that's the issue. The Go code is doing the high/low bit fiddling already too: https://go-review.googlesource.com/c/crypto/+/314889/2/curve25519/curve25519_generic.go#75
The problem here ended up being that the high bit of the point had to be cleared too.
I think a document that just sketches out in pseudo-code how the field operations can be used to construct interesting high-level operations would be helpful, so that users know how to incorporate them. E.g., as far as I can tell, the Go code is good, but I haven't manually vetted that the field operation bounds are respected.
I'm not sure the ladder difference is the issue here. IIRC I added the strict/loose annotations in boringssl to make ed25519 code easier to review when porting it from signed to unsigned limbs, they really shouldn't change the behavior.
~~It struck my eye that some of the values in the failing test cases are greater than 2^255-19.~~ The test printout is probably just little-endian, in which case all the failing inputs reported are larger than 2^255-19.
Do I understand correctly that the code at golang.org/cl/314889 now works, and the change that made the test vectors pass was taking the base input mod 2^255 first, and this is what you are asking us to document? Would a comment like "Note: when implementing rfc7748, the highest bit of the base point must be masked first" at FromBytes be satisfactory?
Do I understand correctly that the code at golang.org/cl/314889 now works, and the change that made the test vectors pass was taking the base input mod 2^255 first,
Yes.
and this is what you are asking us to document?
Not quite. I'm asking for documentation that provides an example (or recommended) ladder structure that's known to respect the input/output bounds for the individual field operations.
I didn't realize RFC 7748 had a sample ladder in it already. I think what I would just recommend is documenting somewhere that that ladder is known to respect the input/output bounds of the individual field operations generated by fiat-crypto (i.e., no additional explicit Carry operations are necessary).
But mentioning the high-bit issue for the base point wouldn't hurt either. (Though I also notice now that actually the Go code has an explicit test for the high bit; but it only tests the default implementation, which on amd64 is the assembly version, not fiat-crypto. Testing on other CPUs causes the test to fail.)
The ladder does somewhat matter in that Fiat's code really has two different types of field element, the "loose" and "tight" ones. If you don't capture that in the type system, it's possible you'll pass a loose element into a function that expects a tight one.
But I think rather than treating that as a property of the ladder, it's easier to capture it in the type system and sprinkle in [whatever the Go name is for]fiat_25519_carry as needed.
Agreed that reflecting the bounds in the type system would be even better.