Hi,
I'm having a new look at sntrup761, I have rebased the branch based on
Simon's work, and pushed as branch "sntrup761" in the Nettle repository.
And I've reread https://ntruprime.cr.yp.to/nist/ntruprime-20201007.pdf
(is that still the main spec?).
I've also added valgrind-based tests for side-channels. It appears key
generation may have leaks (when I mark the output from the randomness
generator as secret). Maybe this is just rejection of certain samples,
which should not be a problem (for this sampling strategy, it's expected
to leak the number of tries needed). Encapsulation appears to not
have branches or memory accesses depending on the randomness input.
Decapsulation appears to have no branches or memory accesses depending
on the secret key, which is the most important property.
I don't yet quite understand the implementation. Some issues:
* Not entirely sure where the sorting comes from (I saw no mention of it
in the spec). I imagine it's part of generating random values of the
appropriate types.
* The encode/decode step appear to follow the spec closely, but to me
it's a bit weird to use the M arrays filled with constant values.
* Coding style is a bit odd, e.g., with long long type for values that
always appear to always be small constant, short lowercase names like
"p" used for preprocessor constants.
I think it should be doable to get into good shape.
Regards,
/Niels
--
Niels Möller. PGP key CB4962D070D77D7FCB8BA36271D8F1FF368C6677.
Internet email is subject to wholesale government surveillance.
Hi,
I've received a bug report pointing out that misuse of the public key
input to ed25519_sha512_sign (and ed448_shake256_sign) is dangerous: If
you sign the same message twice using the same private key, but the
public key inputs differ, that can be exploited to recover the private
key from the two signatures, similar to a classic DSA nonce reuse.
If we compare to how others are dealing with this, a similar issue was
considered a bug in a Rust library (see
https://rustsec.org/advisories/RUSTSEC-2022-0093.html). On the other
end, we have the Golang standard library that represents an ed25519 private
key as 64 bytes where the first half are the private key according to
RFC 8032, and the second half are the private key. This is motivated by
performance, see https://pkg.go.dev/crypto/ed25519.
Some options:
1. Document clearer that the public key argument *must* be the value
produced by ed25519_sha512_public_key (e.g., immediately before the
signing operation, or computed at key generation time and stored
securely bundled with the private key).
Pro: Small change, flexible.
Cons: Leaves the possibility for applications to shoot themselves in
the feet in this way.
2. Make ed25519_sha512_sign check that the signature is valid,
essentially, adding an
assert (ed25519_sha512_verify (...))
before returning.
Pro: Could catch a range of potential bugs and attacks.
Cons: Much worse signing performance. Also, avoiding the particular
attack reported now depends on the verify operation enforcing
canonical representation of the public key.
3. Drop the public key input argument, recompute it for each signing
operation.
Pro: Simpler interface, closer to RFC 8032.
Cons: Much worse signing performance (but probably not as bad as
option (2)). And one would have to think about backwards
compatibility.
Note that both (2) and (3) can be implemented as simple wrappers around
the current signing function, for applications that are prepared to
accept the performance penalty.
Opinions? I'm leaning towards (1).
Regards,
/Niels
PS. The reason this is an issue at all is that the public key is hashed
together with the message in step 4 of the signing operation (see RFC
8032 5.1.6), but not in step 2. I imagine including the public key was
considered to bring some subtle advantage in security; but maybe this
should have been weighted differently against the additional api
complexity in making an additional public key input highly desirable for
performance.
--
Niels Möller. PGP key CB4962D070D77D7FCB8BA36271D8F1FF368C6677.
Internet email is subject to wholesale government surveillance.
