[TLS] CRYSTALS Kyber and TLS

[Stephan Müller]

Hi,

Post-quantum computing cryptographic algorithms are designed and available for 
use. Considering that the Kyber algorithm is going to be mandated by US 
authorities in the future as a complete replacement for asymmetric key 
exchange and agreement, a proposal integrating Kyber into TLS is specified 
with [1].

This proposal, however, has one central shortcoming: only the TLS server 
contributes to the security strength of the shared secret generated by Kyber. 
This shortcoming can be solved with a slightly improved approach where the 
client and the server both independent of each other contribute to the 
security of the communication channel where the channel even retains its 
security when one side has insufficient entropy.

The entire analysis and the suggested proposal to address the outlined issue 
is provided with [2]. I would like to share this proposal to contribute to the 
discussion how Kyber can be applied to TLS.

[1] https://www.ietf.org/archive/id/draft-ietf-tls-hybrid-design-06.txt

[2] http://www.chronox.de/papers/TLS_and_Kyber_analysis.pdf

Ciao
Stephan


___
TLS mailing list
TLS@ietf.org
https://www.ietf.org/mailman/listinfo/tls

Re: [TLS] CRYSTALS Kyber and TLS

[Bas Westerbaan]

Hi Stephan,

>From your e-mail it's unclear which attack you worry about, but in the
attached document, you describe the problem unique to the implementation of
Kyber in TLS as:

If the random number generated
> for the encryption operation is weak, an attacker may sniff the pk sent
> over the wire and “guess” the random number to obtain the shared secret ss.


This is not unique to Kyber. If an attacker can successfully guess server
randomness, then they can guess the private key of the server's ephemeral
ECDH keypair (checking against the server keyshare), and compute the shared
secret as well.

Adding an extra ephemeral server KEM keypair to which the client
encapsulates doesn't change the situation: the attacker you describe can
still guess the KEM private key, and then decrypt the extra shared secret.

Best,

 Bas

On Mon, Jun 19, 2023 at 10:24 AM Stephan Müller  wrote:

> Hi,
>
> Post-quantum computing cryptographic algorithms are designed and available
> for
> use. Considering that the Kyber algorithm is going to be mandated by US
> authorities in the future as a complete replacement for asymmetric key
> exchange and agreement, a proposal integrating Kyber into TLS is specified
> with [1].
>
> This proposal, however, has one central shortcoming: only the TLS server
> contributes to the security strength of the shared secret generated by
> Kyber.
> This shortcoming can be solved with a slightly improved approach where the
> client and the server both independent of each other contribute to the
> security of the communication channel where the channel even retains its
> security when one side has insufficient entropy.
>
> The entire analysis and the suggested proposal to address the outlined
> issue
> is provided with [2]. I would like to share this proposal to contribute to
> the
> discussion how Kyber can be applied to TLS.
>
> [1] https://www.ietf.org/archive/id/draft-ietf-tls-hybrid-design-06.txt
>
> [2] http://www.chronox.de/papers/TLS_and_Kyber_analysis.pdf
>
> Ciao
> Stephan
>
>
> ___
> TLS mailing list
> TLS@ietf.org
> https://www.ietf.org/mailman/listinfo/tls
>
___
TLS mailing list
TLS@ietf.org
https://www.ietf.org/mailman/listinfo/tls

Re: [TLS] CRYSTALS Kyber and TLS

[Stephan Mueller]

Am Montag, 19. Juni 2023, 12:53:32 CEST schrieb Bas Westerbaan:

Hi Bas,

> Hi Stephan,
> 
> From your e-mail it's unclear which attack you worry about, but in the
> attached document, you describe the problem unique to the implementation of
> Kyber in TLS as:
> 
> If the random number generated
> 
> > for the encryption operation is weak, an attacker may sniff the pk sent
> > over the wire and “guess” the random number to obtain the shared secret
> > ss.
> 
> This is not unique to Kyber. If an attacker can successfully guess server
> randomness, then they can guess the private key of the server's ephemeral
> ECDH keypair (checking against the server keyshare), and compute the shared
> secret as well.

As I tried to outline in the end of section 1.3, the issue is not too much 
different from current DH-based or RSA-keywrapping-based TLS establishments. 
However, I would like to start a discussion whether this issue can now be 
addressed and fixed such that even if one side has insufficient entropy, the 
communication channel can still be cryptographically strong as stated in the 
first sentence in chapter 2.
> 
> Adding an extra ephemeral server KEM keypair to which the client
> encapsulates doesn't change the situation: the attacker you describe can
> still guess the KEM private key, and then decrypt the extra shared secret.

With the Kyber KEX, if you guess the servers entropy / random numbers, you can 
still not break the Kyber KEX shared secret as it in addition depends on the 
entropy / random number produced by the client, too.

The key of the issue is:

- Kyber adds entropy and thus security strength only with the Kyber 
encapsulation operation

- the Kyber KEX operation ensures that the client and server independently 
perform a Kyber KEM encapsulation

- the individual Kyber shared secrets derived from the indvidual Kyber KEM 
encapsulation/decapsulation are concatenated to derive a final shared secret 
that is returned to the caller for further use.

Thanks
Stephan



___
TLS mailing list
TLS@ietf.org
https://www.ietf.org/mailman/listinfo/tls

Re: [TLS] CRYSTALS Kyber and TLS

[Scott Fluhrer (sfluhrer)]

I do not believe that Müller is correct - we do not intend use the Kyber CPA 
public key encryption interface, but instead the Kyber CCA KEM interface.  And, 
with that interface, the server does contribute to the shared secret:

The shared secret that Kyber KEM (round 3) generates on success is:

KDF( G( m || H(pk)) || H(c) )

where:
- m is the hash of a value that the server selects
- pk is the public key selected by the client
- c is the server's keyshare
- H is SHA3-256, G is SHA3-512, KDF - SHAKE-256
Note that this formula includes a value (pk) that is selected solely by the 
client; hence we cannot say that this value contains only values selected by 
the server.
(reference: algorithms 8, 9 of the round 3 Kyber submission)

[Minor note: I believe that for the final FIPS version of Kyber, H(pk) will be 
replaced by pk - this does not change this argument]


Now, our proposal is not specific to Kyber; it could be used with other key 
exchange mechanisms that do not share this property.  That property could be 
introduced by using a stronger shared secret combiner (which, for example, may 
include key shares from both sides into the key derivation function) - that was 
suggested in Yokohoma and (I believe) is still under consideration by the 
working group.


Müller also goes on to suggest a two round key exchange - I do not believe that 
introducing such a change to the existing TLS protocol would be warranted.

> -Original Message-
> From: Stephan Müller 
> Sent: Monday, June 19, 2023 4:24 AM
> To: TLS List ; dsteb...@uwaterloo.ca; Scott Fluhrer (sfluhrer)
> ; shay.gue...@gmail.com
> Subject: CRYSTALS Kyber and TLS
> 
> Hi,
> 
> Post-quantum computing cryptographic algorithms are designed and
> available for use. Considering that the Kyber algorithm is going to be
> mandated by US authorities in the future as a complete replacement for
> asymmetric key exchange and agreement, a proposal integrating Kyber into
> TLS is specified with [1].
> 
> This proposal, however, has one central shortcoming: only the TLS server
> contributes to the security strength of the shared secret generated by Kyber.
> This shortcoming can be solved with a slightly improved approach where the
> client and the server both independent of each other contribute to the
> security of the communication channel where the channel even retains its
> security when one side has insufficient entropy.
> 
> The entire analysis and the suggested proposal to address the outlined issue
> is provided with [2]. I would like to share this proposal to contribute to the
> discussion how Kyber can be applied to TLS.
> 
> [1] https://www.ietf.org/archive/id/draft-ietf-tls-hybrid-design-06.txt
> 
> [2] http://www.chronox.de/papers/TLS_and_Kyber_analysis.pdf
> 
> Ciao
> Stephan
> 

___
TLS mailing list
TLS@ietf.org
https://www.ietf.org/mailman/listinfo/tls

Re: [TLS] CRYSTALS Kyber and TLS

[Stephan Mueller]

Am Montag, 19. Juni 2023, 15:56:57 CEST schrieb Scott Fluhrer (sfluhrer):

Hi Scott,

> I do not believe that Müller is correct - we do not intend use the Kyber CPA
> public key encryption interface, but instead the Kyber CCA KEM interface. 
> And, with that interface, the server does contribute to the shared secret:
> 
> The shared secret that Kyber KEM (round 3) generates on success is:
> 
> KDF( G( m || H(pk)) || H(c) )
> 
> where:
>   - m is the hash of a value that the server selects
>   - pk is the public key selected by the client
>   - c is the server's keyshare
>   - H is SHA3-256, G is SHA3-512, KDF - SHAKE-256
> Note that this formula includes a value (pk) that is selected solely by the
> client; hence we cannot say that this value contains only values selected
> by the server. (reference: algorithms 8, 9 of the round 3 Kyber submission)

My concern is that the security strength cannot depend on the pk, because the 
PK is sent in clear over the wire. Thus it cannot contain entropy. Thus, 
entropy only comes from the message m in your listing which is a random number 
that is generated by the server. Further, c depends on m and thus does not add 
any entropy either.

Ciao
Stephan


___
TLS mailing list
TLS@ietf.org
https://www.ietf.org/mailman/listinfo/tls

[TLS] FW: New Version Notification for draft-rsalz-tls-tls12-frozen-01.txt

[Salz, Rich]

We'd like time on the agenda to present and ask for adoption. This is the 
document I agreed to write at IETF 117 and am I pleased to say that Nimrom 
Aviram is a co-author.

On 6/19/23, 10:55 AM, "internet-dra...@ietf.org 
" mailto:internet-dra...@ietf.org>> wrote:




A new version of I-D, draft-rsalz-tls-tls12-frozen-01.txt
has been successfully submitted by Rich Salz and posted to the
IETF repository.


Name: draft-rsalz-tls-tls12-frozen
Revision: 01
Title: TLS 1.2 is Frozen
Document date: 2023-06-19
Group: Individual Submission
Pages: 8
URL: https://www.ietf.org/archive/id/draft-rsalz-tls-tls12-frozen-01.txt 
Status: https://datatracker.ietf.org/doc/draft-rsalz-tls-tls12-frozen 
Html: https://www.ietf.org/archive/id/draft-rsalz-tls-tls12-frozen-01.html 
Htmlized: https://datatracker.ietf.org/doc/html/draft-rsalz-tls-tls12-frozen 
Diff: https://author-tools.ietf.org/iddiff?url2=draft-rsalz-tls-tls12-frozen-01 


Abstract:
TLS 1.2 is in widespread use and can be configured such that it
provides good security properties. TLS 1.3 is also in widespread use
and fixes some known deficiencies with TLS 1.2, such as removing
error-prone cryptographic primitives and encrypting more of the
traffic so that it is not readable by outsiders.


Both versions have several extension points, so items like new
cryptographic algorithms, new supported groups (formerly "named
curves"), etc., can be added without defining a new protocol. This
document specifies that TLS 1.2 is frozen: no new algorithms or
extensions will be approved.


Further, TLS 1.3 use is widespread, and new protocols should require
and assume its existence.


___
TLS mailing list
TLS@ietf.org
https://www.ietf.org/mailman/listinfo/tls

Re: [TLS] CRYSTALS Kyber and TLS

[Thom Wiggers]

Hi all,

The attack that is described by Stephan is something that we considered
while we were initially designing KEMTLS (in the papers, we also covered
the ephemeral key exchange). I'll quickly write what we were thinking of
and why we did not choose to do anything similar to what Stephan proposes.

I will be correcting for the misunderstanding in the document put forward
by Stephan, which suggests that Kyber is an asymmetric encryption scheme.
Encapsulation and Decapsulation should not be confused with encryption and
decryption, which are not part of the public API of Kyber and will not be
part of the NIST standard as far as I'm aware.

I believe we can summarize the argument as follows: in the straightforward
replacement of ECDH by a KEM, the client generates a keypair and the server
(through the encapsulate operation) computes a shared secret and a
ciphertext. If either the secret key or the shared secret are made public,
for example, due to an implementation flaw of either keygen or
encapsulation, then the ephemeral handshake key is no longer secret.

Bas correctly points out that this is not different from ECDH, where
compromise of one of the two exponents leads to shared secret computation,
but that in itself shouldn't necessarily be a reason not to investigate if
we can do better.

But, in my view, the proposed defense and the argument put forward assumes
that the flaw that affects encapsulation does not affect the key generation
(or vice versa); in particular, in the scenario of the broken server-side
random number generator it seems far-fetched that the busted random number
generator or implementation flaw affecting encapsulation won't *also*
affect the keygen (or in other scenarios such as side-channel
vulnerabilities, decapsulate) operation of the server. This, in my view,
makes the additional security offered by the additional key exchange very
marginal.

The reason why we were investigating this issue was a bit different: having
two KEM key exchanges gives the server more control to ensure that there
will be at least one freshly-generated KEM keypair in the mix. This could
improve the forward secrecy for handshakes (modeled via secret key
exposure) in which the client just re-uses the ephemeral keypair every
single time. But we also saw this as not significant enough to suffer the
additional, significant transmission requirement of another full Kyber key
exchange. Hopefully, we now have enough experience with evaluating
implementations of TLS to find and fix these sorts of key-reuse flaws more
easily, earlier, and in automated ways [1]. And again, this is the same
situation with ECDH today.

Cheers,

Thom Wiggers
PQShield

[1] see e.g. https://github.com/tls-attacker/TLS-Scanner. Relying on
implementers not to make mistakes is a dangerous game, but I do believe
that it needs to factor into the cost/benefit analysis.

PS: for marketing reasons I oppose comparisons between the post-quantum KEM
schemes (which are primitives that easily can be used in fully ephemeral
ways) and RSA key wrapping (which pretty much exclusively refers to the
much-derided non-forward-secure RSA transport in TLS-old). ;-)

Op ma 19 jun 2023 om 16:01 schreef Stephan Mueller :

> Am Montag, 19. Juni 2023, 15:56:57 CEST schrieb Scott Fluhrer (sfluhrer):
>
> Hi Scott,
>
> > I do not believe that Müller is correct - we do not intend use the Kyber
> CPA
> > public key encryption interface, but instead the Kyber CCA KEM
> interface.
> > And, with that interface, the server does contribute to the shared
> secret:
> >
> > The shared secret that Kyber KEM (round 3) generates on success is:
> >
> > KDF( G( m || H(pk)) || H(c) )
> >
> > where:
> >   - m is the hash of a value that the server selects
> >   - pk is the public key selected by the client
> >   - c is the server's keyshare
> >   - H is SHA3-256, G is SHA3-512, KDF - SHAKE-256
> > Note that this formula includes a value (pk) that is selected solely by
> the
> > client; hence we cannot say that this value contains only values selected
> > by the server. (reference: algorithms 8, 9 of the round 3 Kyber
> submission)
>
> My concern is that the security strength cannot depend on the pk, because
> the
> PK is sent in clear over the wire. Thus it cannot contain entropy. Thus,
> entropy only comes from the message m in your listing which is a random
> number
> that is generated by the server. Further, c depends on m and thus does not
> add
> any entropy either.
>
> Ciao
> Stephan
>
>
> ___
> TLS mailing list
> TLS@ietf.org
> https://www.ietf.org/mailman/listinfo/tls
>
___
TLS mailing list
TLS@ietf.org
https://www.ietf.org/mailman/listinfo/tls

Re: [TLS] CRYSTALS Kyber and TLS

[Bas Westerbaan]

I do have to add to Thom's remarks that KEMTLS (a.k.a. AuthKEM) offers an
advantage here. If the private key of the leaf cert is not compromised (for
instance when it was generated elsewhere), then the attacker Stephan
describes cannot learn the shared secret.


On Mon, Jun 19, 2023 at 5:02 PM Thom Wiggers  wrote:

> Hi all,
>
> The attack that is described by Stephan is something that we considered
> while we were initially designing KEMTLS (in the papers, we also covered
> the ephemeral key exchange). I'll quickly write what we were thinking of
> and why we did not choose to do anything similar to what Stephan proposes.
>
> I will be correcting for the misunderstanding in the document put forward
> by Stephan, which suggests that Kyber is an asymmetric encryption scheme.
> Encapsulation and Decapsulation should not be confused with encryption and
> decryption, which are not part of the public API of Kyber and will not be
> part of the NIST standard as far as I'm aware.
>
> I believe we can summarize the argument as follows: in the straightforward
> replacement of ECDH by a KEM, the client generates a keypair and the server
> (through the encapsulate operation) computes a shared secret and a
> ciphertext. If either the secret key or the shared secret are made public,
> for example, due to an implementation flaw of either keygen or
> encapsulation, then the ephemeral handshake key is no longer secret.
>
> Bas correctly points out that this is not different from ECDH, where
> compromise of one of the two exponents leads to shared secret computation,
> but that in itself shouldn't necessarily be a reason not to investigate if
> we can do better.
>
> But, in my view, the proposed defense and the argument put forward assumes
> that the flaw that affects encapsulation does not affect the key generation
> (or vice versa); in particular, in the scenario of the broken server-side
> random number generator it seems far-fetched that the busted random number
> generator or implementation flaw affecting encapsulation won't *also*
> affect the keygen (or in other scenarios such as side-channel
> vulnerabilities, decapsulate) operation of the server. This, in my view,
> makes the additional security offered by the additional key exchange very
> marginal.
>
> The reason why we were investigating this issue was a bit different:
> having two KEM key exchanges gives the server more control to ensure that
> there will be at least one freshly-generated KEM keypair in the mix. This
> could improve the forward secrecy for handshakes (modeled via secret key
> exposure) in which the client just re-uses the ephemeral keypair every
> single time. But we also saw this as not significant enough to suffer the
> additional, significant transmission requirement of another full Kyber key
> exchange. Hopefully, we now have enough experience with evaluating
> implementations of TLS to find and fix these sorts of key-reuse flaws more
> easily, earlier, and in automated ways [1]. And again, this is the same
> situation with ECDH today.
>
> Cheers,
>
> Thom Wiggers
> PQShield
>
> [1] see e.g. https://github.com/tls-attacker/TLS-Scanner. Relying on
> implementers not to make mistakes is a dangerous game, but I do believe
> that it needs to factor into the cost/benefit analysis.
>
> PS: for marketing reasons I oppose comparisons between the post-quantum
> KEM schemes (which are primitives that easily can be used in fully
> ephemeral ways) and RSA key wrapping (which pretty much exclusively refers
> to the much-derided non-forward-secure RSA transport in TLS-old). ;-)
>
> Op ma 19 jun 2023 om 16:01 schreef Stephan Mueller :
>
>> Am Montag, 19. Juni 2023, 15:56:57 CEST schrieb Scott Fluhrer (sfluhrer):
>>
>> Hi Scott,
>>
>> > I do not believe that Müller is correct - we do not intend use the
>> Kyber CPA
>> > public key encryption interface, but instead the Kyber CCA KEM
>> interface.
>> > And, with that interface, the server does contribute to the shared
>> secret:
>> >
>> > The shared secret that Kyber KEM (round 3) generates on success is:
>> >
>> > KDF( G( m || H(pk)) || H(c) )
>> >
>> > where:
>> >   - m is the hash of a value that the server selects
>> >   - pk is the public key selected by the client
>> >   - c is the server's keyshare
>> >   - H is SHA3-256, G is SHA3-512, KDF - SHAKE-256
>> > Note that this formula includes a value (pk) that is selected solely by
>> the
>> > client; hence we cannot say that this value contains only values
>> selected
>> > by the server. (reference: algorithms 8, 9 of the round 3 Kyber
>> submission)
>>
>> My concern is that the security strength cannot depend on the pk, because
>> the
>> PK is sent in clear over the wire. Thus it cannot contain entropy. Thus,
>> entropy only comes from the message m in your listing which is a random
>> number
>> that is generated by the server. Further, c depends on m and thus does
>> not add
>> any entropy either.
>>
>> Ciao
>> Stephan
>>
>>
>> _

Re: [TLS] CRYSTALS Kyber and TLS

[Thom Wiggers]

Hi,
Op ma 19 jun 2023 om 17:41 schreef Bas Westerbaan :

> I do have to add to Thom's remarks that KEMTLS (a.k.a. AuthKEM) offers an
> advantage here. If the private key of the leaf cert is not compromised (for
> instance when it was generated elsewhere), then the attacker Stephan
> describes cannot learn the shared secret.
>

Thanks Bas for the clarification, I was indeed only referring to the
ephemeral key exchange. I will add that sooner rather than later I will be
sending an email to the list suggesting some big editorial changes that
hopefully will make it easier to figure out what exactly AuthKEM has to
offer, and ask for some preliminary support; I also see pushing towards a
call for adoption in the future :)

Cheers,

Thom
PQShield


>
> On Mon, Jun 19, 2023 at 5:02 PM Thom Wiggers  wrote:
>
>> Hi all,
>>
>> The attack that is described by Stephan is something that we considered
>> while we were initially designing KEMTLS (in the papers, we also covered
>> the ephemeral key exchange). I'll quickly write what we were thinking of
>> and why we did not choose to do anything similar to what Stephan proposes.
>>
>> I will be correcting for the misunderstanding in the document put forward
>> by Stephan, which suggests that Kyber is an asymmetric encryption scheme.
>> Encapsulation and Decapsulation should not be confused with encryption and
>> decryption, which are not part of the public API of Kyber and will not be
>> part of the NIST standard as far as I'm aware.
>>
>> I believe we can summarize the argument as follows: in the
>> straightforward replacement of ECDH by a KEM, the client generates a
>> keypair and the server (through the encapsulate operation) computes a
>> shared secret and a ciphertext. If either the secret key or the shared
>> secret are made public, for example, due to an implementation flaw of
>> either keygen or encapsulation, then the ephemeral handshake key is no
>> longer secret.
>>
>> Bas correctly points out that this is not different from ECDH, where
>> compromise of one of the two exponents leads to shared secret computation,
>> but that in itself shouldn't necessarily be a reason not to investigate if
>> we can do better.
>>
>> But, in my view, the proposed defense and the argument put forward
>> assumes that the flaw that affects encapsulation does not affect the key
>> generation (or vice versa); in particular, in the scenario of the broken
>> server-side random number generator it seems far-fetched that the busted
>> random number generator or implementation flaw affecting encapsulation
>> won't *also* affect the keygen (or in other scenarios such as
>> side-channel vulnerabilities, decapsulate) operation of the server. This,
>> in my view, makes the additional security offered by the additional key
>> exchange very marginal.
>>
>> The reason why we were investigating this issue was a bit different:
>> having two KEM key exchanges gives the server more control to ensure that
>> there will be at least one freshly-generated KEM keypair in the mix. This
>> could improve the forward secrecy for handshakes (modeled via secret key
>> exposure) in which the client just re-uses the ephemeral keypair every
>> single time. But we also saw this as not significant enough to suffer the
>> additional, significant transmission requirement of another full Kyber key
>> exchange. Hopefully, we now have enough experience with evaluating
>> implementations of TLS to find and fix these sorts of key-reuse flaws more
>> easily, earlier, and in automated ways [1]. And again, this is the same
>> situation with ECDH today.
>>
>> Cheers,
>>
>> Thom Wiggers
>> PQShield
>>
>> [1] see e.g. https://github.com/tls-attacker/TLS-Scanner. Relying on
>> implementers not to make mistakes is a dangerous game, but I do believe
>> that it needs to factor into the cost/benefit analysis.
>>
>> PS: for marketing reasons I oppose comparisons between the post-quantum
>> KEM schemes (which are primitives that easily can be used in fully
>> ephemeral ways) and RSA key wrapping (which pretty much exclusively refers
>> to the much-derided non-forward-secure RSA transport in TLS-old). ;-)
>>
>> Op ma 19 jun 2023 om 16:01 schreef Stephan Mueller :
>>
>>> Am Montag, 19. Juni 2023, 15:56:57 CEST schrieb Scott Fluhrer (sfluhrer):
>>>
>>> Hi Scott,
>>>
>>> > I do not believe that Müller is correct - we do not intend use the
>>> Kyber CPA
>>> > public key encryption interface, but instead the Kyber CCA KEM
>>> interface.
>>> > And, with that interface, the server does contribute to the shared
>>> secret:
>>> >
>>> > The shared secret that Kyber KEM (round 3) generates on success is:
>>> >
>>> > KDF( G( m || H(pk)) || H(c) )
>>> >
>>> > where:
>>> >   - m is the hash of a value that the server selects
>>> >   - pk is the public key selected by the client
>>> >   - c is the server's keyshare
>>> >   - H is SHA3-256, G is SHA3-512, KDF - SHAKE-256
>>> > Note that this formula includes a value (pk) that is selecte

Re: [TLS] CRYSTALS Kyber and TLS

[Dennis Jackson]

If you have access to an uncompromised signing key, you can fix a 
compromised CSRNG generically without having to change the protocol. [1]


Best,
Dennis

[1] https://datatracker.ietf.org/doc/html/rfc8937

On 19/06/2023 16:41, Bas Westerbaan wrote:
I do have to add to Thom's remarks that KEMTLS (a.k.a. AuthKEM) offers 
an advantage here. If the private key of the leaf cert is not 
compromised (for instance when it was generated elsewhere), then the 
attacker Stephan describes cannot learn the shared secret.



On Mon, Jun 19, 2023 at 5:02 PM Thom Wiggers  wrote:

Hi all,

The attack that is described by Stephan is something that we
considered while we were initially designing KEMTLS (in the
papers, we also covered the ephemeral key exchange). I'll quickly
write what we were thinking of and why we did not choose to do
anything similar to what Stephan proposes.

I will be correcting for the misunderstanding in the document put
forward by Stephan, which suggests that Kyber is an asymmetric
encryption scheme. Encapsulation and Decapsulation should not be
confused with encryption and decryption, which are not part of the
public API of Kyber and will not be part of the NIST standard as
far as I'm aware.

I believe we can summarize the argument as follows: in the
straightforward replacement of ECDH by a KEM, the client generates
a keypair and the server (through the encapsulate operation)
computes a shared secret and a ciphertext. If either the secret
key or the shared secret are made public, for example, due to an
implementation flaw of either keygen or encapsulation, then the
ephemeral handshake key is no longer secret.

Bas correctly points out that this is not different from ECDH,
where compromise of one of the two exponents leads to shared
secret computation, but that in itself shouldn't necessarily be a
reason not to investigate if we can do better.

But, in my view, the proposed defense and the argument put forward
assumes that the flaw that affects encapsulation does not affect
the key generation (or vice versa); in particular, in the scenario
of the broken server-side random number generator it seems
far-fetched that the busted random number generator or
implementation flaw affecting encapsulation won't *also* affect
the keygen (or in other scenarios such as side-channel
vulnerabilities, decapsulate) operation of the server. This, in my
view, makes the additional security offered by the additional key
exchange very marginal.

The reason why we were investigating this issue was a bit
different: having two KEM key exchanges gives the server more
control to ensure that there will be at least one
freshly-generated KEM keypair in the mix. This could improve the
forward secrecy for handshakes (modeled via secret key exposure)
in which the client just re-uses the ephemeral keypair every
single time. But we also saw this as not significant enough to
suffer the additional, significant transmission requirement of
another full Kyber key exchange. Hopefully, we now have enough
experience with evaluating implementations of TLS to find and fix
these sorts of key-reuse flaws more easily, earlier, and in
automated ways [1]. And again, this is the same situation with
ECDH today.

Cheers,

Thom Wiggers
PQShield

[1] see e.g. https://github.com/tls-attacker/TLS-Scanner. Relying
on implementers not to make mistakes is a dangerous game, but I do
believe that it needs to factor into the cost/benefit analysis.

PS: for marketing reasons I oppose comparisons between the
post-quantum KEM schemes (which are primitives that easily can be
used in fully ephemeral ways) and RSA key wrapping (which pretty
much exclusively refers to the much-derided non-forward-secure RSA
transport in TLS-old). ;-)

Op ma 19 jun 2023 om 16:01 schreef Stephan Mueller
:

Am Montag, 19. Juni 2023, 15:56:57 CEST schrieb Scott Fluhrer
(sfluhrer):

Hi Scott,

> I do not believe that Müller is correct - we do not intend
use the Kyber CPA
> public key encryption interface, but instead the Kyber CCA
KEM interface.
> And, with that interface, the server does contribute to the
shared secret:
>
> The shared secret that Kyber KEM (round 3) generates on
success is:
>
> KDF( G( m || H(pk)) || H(c) )
>
> where:
>       - m is the hash of a value that the server selects
>       - pk is the public key selected by the client
>       - c is the server's keyshare
>       - H is SHA3-256, G is SHA3-512, KDF - SHAKE-256
> Note that this formula includes a value (pk) that is
selected solely by the
> client; hence we cannot say that this value contains only