Add text comparing DH and KEMs

[sfluhrer]

Florence D asked: There are several points in the draft where properties of, or restrictions on KEMs, are mentioned but it's not clear whether this applies to all KEMs, just to the next-generation KEMs, or just to the NIST Round 3 candidates. I think it's important to clarify this, drawing a distinction between post-quantum and classical KEMs (specifically FFDH and ECDH modelled as KEMs) as well as between general next-generation KEMs and the NIST Round 3 candidates.

We should address it; however it's not clear how - (EC)DH does not satisfy the CCA assumptions currently in the draft, and I can't immediately think how to address the CDH assumptions they do exhibit...

[sfluhrer]

Further text from Florence: As you say in section 2, IND-CPA and IND-CCA2 security of KEMs relies on the generated shared secret being indistinguishable from random, but this is not necessarily the case (e.g. for DH modelled as a KEM as described in this draft). Is it an assumption that the KEMs are indistinguishable from random? If so, this should be stated up front and discussed in the security considerations. If not, then some of the analysis should take this into account (e.g. the results from [BINDEL] referenced in the first paragraph of section 6 do not apply as expected when using this draft's description of DH as a KEM).

[dstebila]

Further text from Florence: As you say in section 2, IND-CPA and IND-CCA2 security of KEMs relies on the generated shared secret being indistinguishable from random, but this is not necessarily the case (e.g. for DH modelled as a KEM as described in this draft). Is it an assumption that the KEMs are indistinguishable from random? If so, this should be stated up front and discussed in the security considerations. If not, then some of the analysis should take this into account (e.g. the results from [BINDEL] referenced in the first paragraph of section 6 do not apply as expected when using this draft's description of DH as a KEM).

IND in both IND-CPA and IND-CCA is defined as the generated shared secret being indistinguishable from a key selected uniformly at random from the KEM's defined keyspace, which could be bitstrings of a certain length or which could be group elements.

[dstebila]

Florence D asked: There are several points in the draft where properties of, or restrictions on KEMs, are mentioned but it's not clear whether this applies to all KEMs, just to the next-generation KEMs, or just to the NIST Round 3 candidates. I think it's important to clarify this, drawing a distinction between post-quantum and classical KEMs (specifically FFDH and ECDH modelled as KEMs) as well as between general next-generation KEMs and the NIST Round 3 candidates.

We should address it; however it's not clear how - (EC)DH does not satisfy the CCA assumptions currently in the draft, and I can't immediately think how to address the CDH assumptions they do exhibit...

What does the TLS 1.3 standard state as the requirements on DH groups? I'm sure some language could be developed saying that DH groups are acceptable even though they aren't IND-CCA, but would need a bit of care to develop such language to take into account things like small subgroup attacks etc.

[sfluhrer]

Except that DH doesn't satisfy the CCA requirements, as it is distinguishable from random (even if the distribution of random values is chosen from group elements).

If we have ciphertext H that the DH private operation converts to the secret S, then the ciphertext 2H would convert into the secret 2S (using additive notation). That's distinguishable with two queries.

Kyber avoids this issue because if the adversary selects a ciphertext in a way other than the Kyber ciphertext generation process, the other side generates an error.

From: Douglas Stebila @.> Sent: Monday, August 15, 2022 2:44 PM To: dstebila/draft-ietf-tls-hybrid-design @.> Cc: Scott Fluhrer (sfluhrer) @.>; Author @.> Subject: Re: [dstebila/draft-ietf-tls-hybrid-design] Add text comparing DH and KEMs (Issue #11)

Further text from Florence: As you say in section 2, IND-CPA and IND-CCA2 security of KEMs relies on the generated shared secret being indistinguishable from random, but this is not necessarily the case (e.g. for DH modelled as a KEM as described in this draft). Is it an assumption that the KEMs are indistinguishable from random? If so, this should be stated up front and discussed in the security considerations. If not, then some of the analysis should take this into account (e.g. the results from [BINDEL] referenced in the first paragraph of section 6 do not apply as expected when using this draft's description of DH as a KEM).

IND in both IND-CPA and IND-CCA is defined as the generated shared secret being indistinguishable from a key selected uniformly at random from the KEM's defined keyspace, which could be bitstrings of a certain length or which could be group elements.

- Reply to this email directly, view it on GitHubhttps://github.com/dstebila/draft-ietf-tls-hybrid-design/issues/11#issuecomment-1215601243, or unsubscribehttps://github.com/notifications/unsubscribe-auth/AB5KPWQX5LNBF4RVKF5JOBTVZKFX7ANCNFSM56OKC4NA. You are receiving this because you authored the thread.Message ID: @.***>

[sfluhrer]

RFC 8446 doesn't mention any cryptographical assumptions it makes about DH - given that RFC 8446 was written for implementors and not cryptographers, that makes sense.

Now, of course, the security proofs of TLS do make assumptions about the security properties of DH - should we try to track those down? Or, are you using that logic to justify our draft being silent about the cryptographical reasoning...

From: Douglas Stebila @.> Sent: Monday, August 15, 2022 2:46 PM To: dstebila/draft-ietf-tls-hybrid-design @.> Cc: Scott Fluhrer (sfluhrer) @.>; Author @.> Subject: Re: [dstebila/draft-ietf-tls-hybrid-design] Add text comparing DH and KEMs (Issue #11)

Florence D asked: There are several points in the draft where properties of, or restrictions on KEMs, are mentioned but it's not clear whether this applies to all KEMs, just to the next-generation KEMs, or just to the NIST Round 3 candidates. I think it's important to clarify this, drawing a distinction between post-quantum and classical KEMs (specifically FFDH and ECDH modelled as KEMs) as well as between general next-generation KEMs and the NIST Round 3 candidates.

We should address it; however it's not clear how - (EC)DH does not satisfy the CCA assumptions currently in the draft, and I can't immediately think how to address the CDH assumptions they do exhibit...

What does the TLS 1.3 standard state as the requirements on DH groups? I'm sure some language could be developed saying that DH groups are acceptable even though they aren't IND-CCA, but would need a bit of care to develop such language to take into account things like small subgroup attacks etc.

- Reply to this email directly, view it on GitHubhttps://github.com/dstebila/draft-ietf-tls-hybrid-design/issues/11#issuecomment-1215602693, or unsubscribehttps://github.com/notifications/unsubscribe-auth/AB5KPWVXQXSIGXQIQPSYPTLVZKF55ANCNFSM56OKC4NA. You are receiving this because you authored the thread.Message ID: @.***>

[dstebila]

Except that DH doesn't satisfy the CCA requirements, as it is distinguishable from random (even if the distribution of random values is chosen from group elements). If we have ciphertext H that the DH private operation converts to the secret S, then the ciphertext 2H would convert into the secret 2S (using additive notation). That's distinguishable with two queries.

Yes, I understand DH doesn't satisfy the CCA requirements. Formally the proofs of TLS 1.3 rely on a property called PRF-ODH, which is that taking a DH shared secret and hashed by a PRF with an adversary-supplied label yields a bitstring that's indistinguishable from random.

Writing it out like that, it's clear that the arguments about hybrid combiners on two IND-CCA KEMs don't apply in this case. My quick intuition is that it shouldn't be hard to prove that the hybrid construction (including the relevant part of the TLS key schedule) is secure under either the PRF-ODH assumption on the DH component or the IND-CCA assumption on the KEM component.

RFC 8446 doesn't mention any cryptographical assumptions it makes about DH - given that RFC 8446 was written for implementors and not cryptographers, that makes sense.

Now, of course, the security proofs of TLS do make assumptions about the security properties of DH - should we try to track those down? Or, are you using that logic to justify our draft being silent about the cryptographical reasoning...

I had raised it because I was hoping we'd be able to borrow language from RFC 8446. I don't think our draft should be silent on cryptographic reasoning because the draft is written as a framework for hybrid with Kyber as one example, but in principle other KEMs could be used, so it feels like we ought to specify requirements other components should satisfy to be used in this framework.

[dstebila]

Except that DH doesn't satisfy the CCA requirements, as it is distinguishable from random (even if the distribution of random values is chosen from group elements). If we have ciphertext H that the DH private operation converts to the secret S, then the ciphertext 2H would convert into the secret 2S (using additive notation). That's distinguishable with two queries.

Yes, I understand DH doesn't satisfy the CCA requirements. Formally the proofs of TLS 1.3 rely on a property called PRF-ODH, which is that taking a DH shared secret and hashed by a PRF with an adversary-supplied label yields a bitstring that's indistinguishable from random.

Writing it out like that, it's clear that the arguments about hybrid combiners on two IND-CCA KEMs don't apply in this case. My quick intuition is that it shouldn't be hard to prove that the hybrid construction (including the relevant part of the TLS key schedule) is secure under either the PRF-ODH assumption on the DH component or the IND-CCA assumption on the KEM component.

I talked to some research colleagues and will continue to explore this, but don't have a theorem/proof on this exact scenario. But I – and no one I've talked to – expects anything unusual to happen this case, the expected security result should go through just fine.

RFC 8446 doesn't mention any cryptographical assumptions it makes about DH - given that RFC 8446 was written for implementors and not cryptographers, that makes sense. Now, of course, the security proofs of TLS do make assumptions about the security properties of DH - should we try to track those down? Or, are you using that logic to justify our draft being silent about the cryptographical reasoning...

I had raised it because I was hoping we'd be able to borrow language from RFC 8446. I don't think our draft should be silent on cryptographic reasoning because the draft is written as a framework for hybrid with Kyber as one example, but in principle other KEMs could be used, so it feels like we ought to specify requirements other components should satisfy to be used in this framework.

I added some text in PR #16.