Re: [CFRG] [EXTERNAL] Re: Streamlined NTRU Prime: sntrup761

[Mike Ounsworth <[e-mail]>]

Peter,

Thank you for the discussion; I learned something.

Going back to the top; the discussion was whether the SNTRU hybrid draft aligns with the combiner in draft-ounsworth-cfrg-kem-combiners, which we've established that it does not, and then whether it should -- or whether we should change the combiner in draft-ounsworth-cfrg-kem-combiners. I'm not sure how to interpret this discussion in terms of making progress on that question.

---
Mike Ounsworth

-----Original Message-----
From: Peter C <[e-mail]>
Sent: Friday, May 12, 2023 4:49 PM
To: Mike Ounsworth <[e-mail]>
Cc: [e-mail]
Subject: RE: [CFRG] [EXTERNAL] Re: Streamlined NTRU Prime: sntrup761

Mike,

> Thinking on this a bit more since I sent my last reply.
>
> Streamlined NTRU Prime is IND-CCA2 as per [1] section 7.1.
> X25519 may or may not be IND-CCA2 depending on the implementation
> consideration noted in the security considerations of RFC7748.

Sorry, I don't think I was clear enough.  The part of the RFC 7748 security considerations I meant was:

"Designers using these curves should be aware that for each public key, there are several publicly computable public keys that are equivalent to it, i.e., they produce the same shared secrets.  Thus using a public key as an identifier and knowledge of a shared secret as proof of ownership (without including the public keys in the key derivation) might lead to subtle vulnerabilities."

Clamping in X25519 means that for any private key a we have [a]Q = O when Q is a point of small order.  (This is the non-contributory issue you quoted.)  However, it also means that given any public key B we can easily compute a different public key B' = B + Q that gives

[a]B' = [a](B + Q) = [a]B + [a]Q = [a]B + O = [a]B;

i.e., the same shared secret.  (This is the equivalent public key issue quoted above.)

Equivalent public keys are the consequence of an intentional design choice, not an implementation issue.  Vanilla X25519 viewed as a KEM is not IND-CCA secure, even if you hash the shared secret (without including the ciphertext) and limit it to a single oracle call.  For IND-CCA security, you really need something much closer to DHKEM from RFC 9180.

> The combiner proposed in this draft:
> SHA2-512(K1||K2)
> Is IND-CCA2 if-and-only-if both of the underlying KEM primitives are.
> IE it propagates the weaker of the two properties.

I was only arguing that the specific sntrup761+x25519 hybrid construction is not IND-CCA secure.  I don't think it's necessarily true in general that an IND-CCA attack on one of the component KEMs always leads to an IND-CCA attack on the hybrid KEM.

> Whereas draft-ounsworth-cfrg-kem-combiners-03:
> KDF(counter || k_1 || ... || k_n || fixedInfo, outputBits) k_i =
> H(ss_i || ct_i) Is IND-CCA2 if either underlying KEM primitives are.
> IE it propagates the stronger of the two properties.

Again, I'd be cautious about claiming this in general.  There was a discussion of whether existing IND-CCA security proofs adequately covered this construction.  I'm not sure what the outcome of that was, but I suspect it depends on the specific assumptions you are making.  On the other hand, hashing the shared secrets with the ciphertexts does block IND-CCA attacks that rely on equivalent ciphertexts.

Peter

Peter Campbell
Industry Liaison and International Standards [e-mail]
Any email and files/attachments transmitted with it are confidential and are intended solely for the use of the individual or entity to whom they are addressed. If this message has been sent to you in error, you must not copy, distribute or disclose of the information it contains. Please notify Entrust immediately and delete the message from your system.