[TLS] I-D Action: draft-ietf-tls-ctls-03.txt

[internet-drafts]

A New Internet-Draft is available from the on-line Internet-Drafts directories.
This draft is a work item of the Transport Layer Security WG of the IETF.

Title   : Compact TLS 1.3
Authors : Eric Rescorla
  Richard Barnes
  Hannes Tschofenig
Filename: draft-ietf-tls-ctls-03.txt
Pages   : 17
Date: 2021-07-12

Abstract:
   This document specifies a "compact" version of TLS 1.3.  It is
   isomorphic to TLS 1.3 but saves space by trimming obsolete material,
   tighter encoding, and a template-based specialization technique. cTLS
   is not directly interoperable with TLS 1.3, but it should eventually
   be possible for a cTLS/TLS 1.3 server to exist and successfully
   interoperate.


The IETF datatracker status page for this draft is:
https://datatracker.ietf.org/doc/draft-ietf-tls-ctls/

There is also an htmlized version available at:
https://datatracker.ietf.org/doc/html/draft-ietf-tls-ctls-03

A diff from the previous version is available at:
https://www.ietf.org/rfcdiff?url2=draft-ietf-tls-ctls-03


Internet-Drafts are also available by anonymous FTP at:
ftp://ftp.ietf.org/internet-drafts/


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

Re: [TLS] Advancing draft-ietf-tls-hybrid-design

[Douglas Stebila]

Thanks Martin.  All makes sense, and I'll incorporate in a revision.  Though at 
this point changing the word "hybrid" to "composite" would be a rather big 
rewrite so I'll omit that unless there are very strong objections to the word 
hybrid.

Douglas


> On Jul 6, 2021, at 21:53, Martin Thomson  wrote:
> 
> I just took a look.  I didn't read the (large) appendices, though I 
> appreciate that they have value.
> 
> The draft is largely in good shape.  I have a few minor concerns.
> 
> I don't think that you want to reserve the hybrid_private_use(0x2F00..0x2FFF) 
> range of values.  There were specific reasons for an FFDHE range that I don't 
> think apply if we constrain this design to TLS 1.3 and higher (as we should). 
>  The same applies to the 0x02.. prefix you suggest for the use of hybrid 
> codepoints.
> 
> I find the emphasis on the NIST process a little strong for what is a 
> permanent artifact.  It is OK to note its existence as motivation for the 
> work, but I would avoid over-emphasis.  For example:
> 
> OLD:
>   Moreover, it is possible that even by the end of the NIST Post-
>   Quantum Cryptography Standardization Project, and for a period of
>   time thereafter, conservative users may not have full confidence in
>   some algorithms.
> NEW:
>   Moreover, it is possible that after next-generation algorithms are defined, 
> and for a period of
>   time thereafter, conservative users may not have full confidence in those 
> algorithms.
> 
> and 
> 
> OLD:
>   In the context of the NIST Post-Quantum Cryptography Standardization
>   Project, key exchange algorithms are formulated as key encapsulation
>   mechanisms (KEMs), which consist of three algorithms:
> NEW:
>   This document models key agreement as key encapsulation
>   mechanisms (KEMs), which consist of three algorithms:
> 
> Please avoid "defining" codepoints, even in examples:
> 
> OLD:
>   For example, a future document could specify that hybrid value 0x2000 
> corresponds to
>   secp256r1+ntruhrss701, and 0x2001 corresponds to x25519+ntruhrss701.
> NEW:
>   For example, a future document could specify that one codepoint corresponds 
> to
>   secp256r1+ntruhrss701, and another corresponds to x25519+ntruhrss701.
> 
> Finally, the use of the word "hybrid" is awkward.  Maybe "composite" is a 
> less-heavily overloaded term that accurately captures the intent; with an 
> antonym of "unitary" or "discrete".
> 
> When you talk about concatenation, it might pay to cite the relevant 
> appendix.  I would also note that the goal is that when the composed elements 
> are not fixed-length, a length prefix might be used to ensure that both 
> secrets contribute all of their entropy without being exposed to a weakness 
> in the other.  (You might say that the composition is injective.)
> 
> Section 4 includes questions to which I think answers can be given now:
> 
> *Larger public keys and/or ciphertexts.* => I think that the answer here has 
> to be "too bad".  Just note that TLS cannot handle a KEM that includes values 
> larger than 2^16 (minus a little bit).
> 
> *Duplication of key shares.* => Your existing text is sufficient to answer 
> this one.
> 
> *Resumption.* => There isn't much existing language on this point, but I 
> don't see it as needing anything special in this draft.  My view is that 
> fresh entropy of any kind is an improvement, but generally we will see better 
> than that because clients and servers will perform a fresh key exchange with 
> an algorithm that they consider sufficient at the time.  That might result in 
> a change in posture relative to the original session, but the result should 
> still be as good as min(original, current), which is always better than just 
> using the PSK.
> 
> *Failures.* => KEM failure is a problem, but I would do nothing more than 
> note the potential and have the handshake fail.  I see that the finalists 
> have low enough error rates that this doesn't seem likely to be an issue in 
> practice.  Clients can always try again if they hit this specific problem.  
> Ours already retries in a bunch of different failure cases.  Some text on 
> this point in the draft is probably sensible.
> 
> Nits:
> 
> OLD:
>   However, the
>   key_exchange values for each algorithm MUST be generated
>   independently.
> NEW:
>   However, 
>   key_exchange values for different algorithms MUST be generated
>   independently.
> 
> 
> 
> On Wed, Jul 7, 2021, at 11:19, Douglas Stebila wrote:
>> Dear TLS working group,
>> 
>> We wanted to see if there is any further feedback on our draft "Hybrid 
>> key exchange in TLS 1.3" 
>> (https://datatracker.ietf.org/doc/draft-ietf-tls-hybrid-design/) and 
>> what steps are required for it to advance further.  We have not 
>> received any new feedback from the working group since we posted our 
>> last non-trivial update in October 2020.
>> 
>> The draft as written does not actually specify any post-quantum 
>> algorithms nor give identifiers for specific algorithm c

Re: [TLS] Advancing draft-ietf-tls-hybrid-design

[Douglas Stebila]

On Jul 7, 2021, at 09:26, Salz, Rich  wrote:
> 
> PQ OID's came up in the LAMPS working group, which seems to want to defer to 
> NIST.  You should maybe cross-post your note there.

Hi Rich,

Unless I'm mistaken, OIDs are relevant to TLS in the context of signatures, but 
not key exchange; TLS defines its own algorithm identifiers for "groups" in key 
exchange independently of the OID system.  So when to define group identifiers 
for hybrid key exchange would be a TLS working group choice.

Douglas

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

[TLS] Comments on draft-celi-wiggers-tls-authkem-00.txt

[Eric Rescorla]

Hi folks,

I have just given draft-celi-wiggers-tls-authkem-00.txt a quick
read. I'm struggling a bit with the rationale, which I take to be
these paragraphs:

   In this proposal we use the DH-based KEMs from [I-D.irtf-cfrg-hpke].
   We believe KEMs are especially worth discussing in the context of the
   TLS protocol because NIST is in the process of standardizing post-
   quantum KEM algorithms to replace "classic" key exchange (based on
   elliptic curve or finite-field Diffie-Hellman [NISTPQC]).

   This proposal draws inspiration from [I-D.ietf-tls-semistatic-dh],
   which is in turn based on the OPTLS proposal for TLS 1.3 [KW16].
   However, these proposals require a non-interactive key exchange: they
   combine the client's public key with the server's long-term key.
   This imposes a requirement that the ephemeral and static keys use the
   same algorithm, which this proposal does not require.  Additionally,
   there are no post-quantum proposals for a non-interactive key
   exchange currently considered for standardization, while several KEMs
   are on the way.

I see why this motivates using a KEM for key establishment, but I'm
not sure it motivates this design, which seems like a fairly radical
change to TLS. As I understand the situation, in the post-quantum
world we're going to have:

- non-interactive KEMs (as you indicate above)
- some sort of signature system (otherwise we won't have certificates).

This certainly argues that we need a KEM for key establishment, but
not for authentication. Instead, why can't we use signatures for
authentication, as TLS does today? I.e., the certificates would have a
(potentially post-quantum) signing key in them and you then use the
KEM for key establishment and the signing key for authentication.
That would give us a design much closer to the present TLS 1.3
(effectively just defining a new group for the KEM).

What am I missing?

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

Re: [TLS] Comments on draft-celi-wiggers-tls-authkem-00.txt

[Douglas Stebila]

Hi Eric,

The main motivation is that, in some cases, post-quantum signatures are larger 
in terms of communication size compared to a post-quantum KEM, under the same 
cryptographic assumption.  

For example, the KEM Kyber (based on module LWE) at the 128-bit security level 
has 800-byte public keys and 768-byte ciphertexts.  The matching signature 
scheme Dilithium (also based on module LWE) has 1312-byte public keys and 
2420-byte signatures.  Doing KEM-based server authentication rather than 
signature-based server authentication would thus save 2164 bytes per handshake. 
 

We would still need digital signatures for a PKI (i.e., the root and 
intermediate CAs would sign certificates using PQ digital signature schemes), 
but the public key of the endpoint server can be a KEM public key, not a 
digital signature public key.

Douglas


> On Jul 12, 2021, at 20:30, Eric Rescorla  wrote:
> 
> Hi folks,
> 
> I have just given draft-celi-wiggers-tls-authkem-00.txt a quick
> read. I'm struggling a bit with the rationale, which I take to be
> these paragraphs:
> 
>In this proposal we use the DH-based KEMs from [I-D.irtf-cfrg-hpke].
>We believe KEMs are especially worth discussing in the context of the
>TLS protocol because NIST is in the process of standardizing post-
>quantum KEM algorithms to replace "classic" key exchange (based on
>elliptic curve or finite-field Diffie-Hellman [NISTPQC]).
> 
>This proposal draws inspiration from [I-D.ietf-tls-semistatic-dh],
>which is in turn based on the OPTLS proposal for TLS 1.3 [KW16].
>However, these proposals require a non-interactive key exchange: they
>combine the client's public key with the server's long-term key.
>This imposes a requirement that the ephemeral and static keys use the
>same algorithm, which this proposal does not require.  Additionally,
>there are no post-quantum proposals for a non-interactive key
>exchange currently considered for standardization, while several KEMs
>are on the way.
> 
> I see why this motivates using a KEM for key establishment, but I'm
> not sure it motivates this design, which seems like a fairly radical
> change to TLS. As I understand the situation, in the post-quantum
> world we're going to have:
> 
> - non-interactive KEMs (as you indicate above)
> - some sort of signature system (otherwise we won't have certificates).
> 
> This certainly argues that we need a KEM for key establishment, but
> not for authentication. Instead, why can't we use signatures for
> authentication, as TLS does today? I.e., the certificates would have a
> (potentially post-quantum) signing key in them and you then use the
> KEM for key establishment and the signing key for authentication.
> That would give us a design much closer to the present TLS 1.3
> (effectively just defining a new group for the KEM).
> 
> What am I missing?
> 
> -Ekr
> 
> 
> ___
> 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] Comments on draft-celi-wiggers-tls-authkem-00.txt

[Eric Rescorla]

On Mon, Jul 12, 2021 at 5:58 PM Douglas Stebila  wrote:

> Hi Eric,
>
> The main motivation is that, in some cases, post-quantum signatures are
> larger in terms of communication size compared to a post-quantum KEM, under
> the same cryptographic assumption.
>
> For example, the KEM Kyber (based on module LWE) at the 128-bit security
> level has 800-byte public keys and 768-byte ciphertexts.  The matching
> signature scheme Dilithium (also based on module LWE) has 1312-byte public
> keys and 2420-byte signatures.  Doing KEM-based server authentication
> rather than signature-based server authentication would thus save 2164
> bytes per handshake.
>

Doug,

Thanks for the explanation.

I agree that all things being equal it's good to save bytes, but in this
case, I think this is the wrong tradeoff.

In general, TLS handshake latency is dominated not by message size but by
the number of round trips you have to use to perform the handshake, which
is only loosely coupled to the number of bytes.

Specifically:
- If you are doing TLS over TCP, then the server can use IW10 as specified
in RFC 6928. This will allow the server's first flight to be about 14 KB,
which should be large enough.
- If you are doing QUIC, then the server is restricted to 3x the client's
initial message, which is potentially a problem with very large server
first flights, but the client can add extra bytes to its Initial messages
to increase the limit [0]

And of course, there are mechanisms for shrinking the handshake, such as
RFC 8879 certificate compression or draft=thomson-tls-sic.

So, while I'm not that enthusiastic about paying a few K, I think on
balance it's a better than doing this kind of major rearchitecture of TLS.

-Ekr

[0] Or the server can send a Retry packet, incurring a round trip, but this
only needs to be done the first time as long as the client's IP doesn't
change.



> > On Jul 12, 2021, at 20:30, Eric Rescorla  wrote:
> >
> > Hi folks,
> >
> > I have just given draft-celi-wiggers-tls-authkem-00.txt a quick
> > read. I'm struggling a bit with the rationale, which I take to be
> > these paragraphs:
> >
> >In this proposal we use the DH-based KEMs from [I-D.irtf-cfrg-hpke].
> >We believe KEMs are especially worth discussing in the context of the
> >TLS protocol because NIST is in the process of standardizing post-
> >quantum KEM algorithms to replace "classic" key exchange (based on
> >elliptic curve or finite-field Diffie-Hellman [NISTPQC]).
> >
> >This proposal draws inspiration from [I-D.ietf-tls-semistatic-dh],
> >which is in turn based on the OPTLS proposal for TLS 1.3 [KW16].
> >However, these proposals require a non-interactive key exchange: they
> >combine the client's public key with the server's long-term key.
> >This imposes a requirement that the ephemeral and static keys use the
> >same algorithm, which this proposal does not require.  Additionally,
> >there are no post-quantum proposals for a non-interactive key
> >exchange currently considered for standardization, while several KEMs
> >are on the way.
> >
> > I see why this motivates using a KEM for key establishment, but I'm
> > not sure it motivates this design, which seems like a fairly radical
> > change to TLS. As I understand the situation, in the post-quantum
> > world we're going to have:
> >
> > - non-interactive KEMs (as you indicate above)
> > - some sort of signature system (otherwise we won't have certificates).
> >
> > This certainly argues that we need a KEM for key establishment, but
> > not for authentication. Instead, why can't we use signatures for
> > authentication, as TLS does today? I.e., the certificates would have a
> > (potentially post-quantum) signing key in them and you then use the
> > KEM for key establishment and the signing key for authentication.
> > That would give us a design much closer to the present TLS 1.3
> > (effectively just defining a new group for the KEM).
> >
> > What am I missing?
> >
> > -Ekr
> >
> >
> > ___
> > 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] Comments on draft-celi-wiggers-tls-authkem-00.txt

[Blumenthal, Uri - 0553 - MITLL]

Let me emphasize the reasons Douglas brought up. Note that I need to use NIST 
Sec Level 5 algorithms. So, Kyber-1024 and Dilithium5 (other algorithms show 
even worse ratio between KEM and signature!). 

Communications costs:
- Difference in public key sizes: 1568 bytes of Kyber vs. 2592 bytes of 
Dilithium => 1024 extra bytes to carry over channel each way;
- Signature: extra 4595 bytes each way, because in addition to exchanging certs 
(aka "signed public keys", which is inevitable) you need to sign the exchange 
and communicate that signature across;
- Total: 5619 extra bytes each way. For peer-to-peer broadband connections, you 
can say "so what?". But my links are *very* austere.

Computation costs (ballpark, on a powerful CPU):
- KEM: keygen 15us, encap 18us, decap 14us (say, double encap and decap for 
PFS-providing exchange); 
- Signature: sign 113us, verify 55us;
- Comparison: 134us for signature-less KEM vs. 215us for TLS-like exchange => 
almost twice as long;
- Difference may be negligible for Intel Xeon, but for my much weaker hardware 
it matters.

So, for constrained environments with austere comm links, signature-less 
"authkem" is God-sent. 
Big servers that need to support many clients (so they care how much CPU cycles 
and comm bytes they spend on every connection) would appreciate these savings 
too.

@ekr,I hope this provides convincing explanation why "authkem" is needed. 

P.S. I know that Falcon has much more favorable sizes - but (a) it takes three 
times as long to sign, and (b) it uses FP calculations, which isn't great to 
implement in my environment. 
--
Regards,
Uri
 
There are two ways to design a system. One is to make is so simple there are 
obviously no deficiencies.
The other is to make it so complex there are no obvious deficiencies.

 -  C. A. R. Hoare
 

On 7/12/21, 20:59, "TLS on behalf of Douglas Stebila"  wrote:

Hi Eric,

The main motivation is that, in some cases, post-quantum signatures are 
larger in terms of communication size compared to a post-quantum KEM, under the 
same cryptographic assumption.  

For example, the KEM Kyber (based on module LWE) at the 128-bit security 
level has 800-byte public keys and 768-byte ciphertexts.  The matching 
signature scheme Dilithium (also based on module LWE) has 1312-byte public keys 
and 2420-byte signatures.  Doing KEM-based server authentication rather than 
signature-based server authentication would thus save 2164 bytes per handshake. 
 

We would still need digital signatures for a PKI (i.e., the root and 
intermediate CAs would sign certificates using PQ digital signature schemes), 
but the public key of the endpoint server can be a KEM public key, not a 
digital signature public key.

Douglas


> On Jul 12, 2021, at 20:30, Eric Rescorla  wrote:
> 
> Hi folks,
> 
> I have just given draft-celi-wiggers-tls-authkem-00.txt a quick
> read. I'm struggling a bit with the rationale, which I take to be
> these paragraphs:
> 
>In this proposal we use the DH-based KEMs from [I-D.irtf-cfrg-hpke].
>We believe KEMs are especially worth discussing in the context of the
>TLS protocol because NIST is in the process of standardizing post-
>quantum KEM algorithms to replace "classic" key exchange (based on
>elliptic curve or finite-field Diffie-Hellman [NISTPQC]).
> 
>This proposal draws inspiration from [I-D.ietf-tls-semistatic-dh],
>which is in turn based on the OPTLS proposal for TLS 1.3 [KW16].
>However, these proposals require a non-interactive key exchange: they
>combine the client's public key with the server's long-term key.
>This imposes a requirement that the ephemeral and static keys use the
>same algorithm, which this proposal does not require.  Additionally,
>there are no post-quantum proposals for a non-interactive key
>exchange currently considered for standardization, while several KEMs
>are on the way.
> 
> I see why this motivates using a KEM for key establishment, but I'm
> not sure it motivates this design, which seems like a fairly radical
> change to TLS. As I understand the situation, in the post-quantum
> world we're going to have:
> 
> - non-interactive KEMs (as you indicate above)
> - some sort of signature system (otherwise we won't have certificates).
> 
> This certainly argues that we need a KEM for key establishment, but
> not for authentication. Instead, why can't we use signatures for
> authentication, as TLS does today? I.e., the certificates would have a
> (potentially post-quantum) signing key in them and you then use the
> KEM for key establishment and the signing key for authentication.
> That would give us a design much closer to the prese

Re: [TLS] Comments on draft-celi-wiggers-tls-authkem-00.txt

[Kampanakis, Panos]

> So, while I'm not that enthusiastic about paying a few K, I think on balance 
> it's a better than doing this kind of major rearchitecture of TLS.

+1. KEMTLS is a great scheme but significantly changes the TLS state machine. 
It introduces implicit and explicit auth concepts which do not exist in TLS 1.3 
and would need further security proofs and study. Also, it may save ~1-2KB of 
data (Falcon, Dilithium assumed), but still uses PQ Sigs in the PKI which means 
we go to 10+ KB for the cert chain. So we alleviate 1-2KB, but still have to 
deal with 10+. Also note ia.cr/2019/1447 which makes 
the argument that the more the data the more the slowdown in lossy environments 
(which intuitively makes sense as the loss probability (1-(1-p)n) increases 
with more packets). Imo the draft-celi-wiggers-tls-authkem should be considered 
for future versions of TLS as the drastic changes do not justify the marginal 
benefit.

And a couple of comments regarding Ekr’s points:

> - If you are doing TLS over TCP, then the server can use IW10 as specified in 
> RFC 6928. This will allow the server's first flight to be about 14 KB, which 
> should be large enough.

That is not completely accurate. The smallest Dilithium parameters will fit in 
10MSS only when doing plain TLS (no SCTs, no OCSP staples) with up to 2 ICAs. 
Anything else will go beyond 14KB. Now if we talk web (include SCTs), then only 
1 ICA would fit with Dilithium-II.

Having said that, if we talk about the other lattice based NIST PQ Sig 
Finalist, Falcon-512, then there are more TLS cases (up to 3 ICAs) where the 
data would fit in an TCP initcwnd.  For Falcon-1024 that is not the case either.

> - If you are doing QUIC, then the server is restricted to 3x the client's 
> initial message, which is potentially a problem with very large server first 
> flights, but the client can add extra bytes to its Initial messages to 
> increase the limit [0]

Padding to the client initial message to 1200B would mean the QUIC 
amplification attack protection would kick in for any PQ KEM Round 3 Finalist 
and any PQ Sig Finalist, even Falcon-512 which is the smallest one. The 
smallest PQ Sig will still be >3x when used with X25519+the biggest PQ KEM 
Finalists. I am not sure what dummy key exchange data and how much of it 
someone could put in the client message in order to reach 2.5KB in the request 
in order for the response to fit in the 3x2.5 window necessary (assuming 2 
ICAs).

I think the best answer to the extra round-trip problems which are inevitable 
for PQ Sigs (as shown in ia.cr/2020/071 , 
dl.acm.org/doi/10.1145/3386367.3431305)
 is Martin’s 
draft-thomson-tls-sic
 which should be revived imo.

Cert compression will not help as these big certs mostly consist of big keys or 
sigs which are random sequences and thus do not benefit from compression.

Rgs,
Panos






From: TLS  On Behalf Of Eric Rescorla
Sent: Monday, July 12, 2021 9:10 PM
To: Douglas Stebila 
Cc:  
Subject: RE: [EXTERNAL] [TLS] Comments on draft-celi-wiggers-tls-authkem-00.txt


CAUTION: This email originated from outside of the organization. Do not click 
links or open attachments unless you can confirm the sender and know the 
content is safe.




On Mon, Jul 12, 2021 at 5:58 PM Douglas Stebila 
mailto:dsteb...@gmail.com>> wrote:
Hi Eric,

The main motivation is that, in some cases, post-quantum signatures are larger 
in terms of communication size compared to a post-quantum KEM, under the same 
cryptographic assumption.

For example, the KEM Kyber (based on module LWE) at the 128-bit security level 
has 800-byte public keys and 768-byte ciphertexts.  The matching signature 
scheme Dilithium (also based on module LWE) has 1312-byte public keys and 
2420-byte signatures.  Doing KEM-based server authentication rather than 
signature-based server authentication would thus save 2164 bytes per handshake.

Doug,

Thanks for the explanation.

I agree that all things being equal it's good to save bytes, but in this case, 
I think this is the wrong tradeoff.

In general, TLS handshake latency is dominated not by message size but by the 
number of round trips you have to use to perform the handshake, which is only 
loosely coupled to the number of bytes.

Specifically:
- If you are doing TLS over TCP, then the server can use IW10 as specified in 
RFC 6928. This will allow the server's first flight to be about 14 KB, which 
should be large enough.
- If you are doing QUIC, then the server is restricted to 3x 

Re: [TLS] Comments on draft-celi-wiggers-tls-authkem-00.txt

[Kampanakis, Panos]

Hi Uri,

If we are talking NIST Level 5 (and I am assuming you are discussing mTLS), 
have you calculated the total CertVerify+cert chain sizes there assuming 2 ICAs 
let's say? 

And would constrained devices or mediums that sweat about 5KB really be able to 
support PQ KEMs and Sigs at NIST Level 5?




-Original Message-
From: TLS  On Behalf Of Blumenthal, Uri - 0553 - MITLL
Sent: Monday, July 12, 2021 11:39 PM
To: Douglas Stebila ; Eric Rescorla 
Cc:  
Subject: RE: [EXTERNAL] [TLS] Comments on draft-celi-wiggers-tls-authkem-00.txt

CAUTION: This email originated from outside of the organization. Do not click 
links or open attachments unless you can confirm the sender and know the 
content is safe.



Let me emphasize the reasons Douglas brought up. Note that I need to use NIST 
Sec Level 5 algorithms. So, Kyber-1024 and Dilithium5 (other algorithms show 
even worse ratio between KEM and signature!).

Communications costs:
- Difference in public key sizes: 1568 bytes of Kyber vs. 2592 bytes of 
Dilithium => 1024 extra bytes to carry over channel each way;
- Signature: extra 4595 bytes each way, because in addition to exchanging certs 
(aka "signed public keys", which is inevitable) you need to sign the exchange 
and communicate that signature across;
- Total: 5619 extra bytes each way. For peer-to-peer broadband connections, you 
can say "so what?". But my links are *very* austere.

Computation costs (ballpark, on a powerful CPU):
- KEM: keygen 15us, encap 18us, decap 14us (say, double encap and decap for 
PFS-providing exchange);
- Signature: sign 113us, verify 55us;
- Comparison: 134us for signature-less KEM vs. 215us for TLS-like exchange => 
almost twice as long;
- Difference may be negligible for Intel Xeon, but for my much weaker hardware 
it matters.

So, for constrained environments with austere comm links, signature-less 
"authkem" is God-sent.
Big servers that need to support many clients (so they care how much CPU cycles 
and comm bytes they spend on every connection) would appreciate these savings 
too.

@ekr,I hope this provides convincing explanation why "authkem" is needed.

P.S. I know that Falcon has much more favorable sizes - but (a) it takes three 
times as long to sign, and (b) it uses FP calculations, which isn't great to 
implement in my environment.
--
Regards,
Uri

There are two ways to design a system. One is to make is so simple there are 
obviously no deficiencies.
The other is to make it so complex there are no obvious deficiencies.

 -  C. A. R. Hoare


On 7/12/21, 20:59, "TLS on behalf of Douglas Stebila"  wrote:

Hi Eric,

The main motivation is that, in some cases, post-quantum signatures are 
larger in terms of communication size compared to a post-quantum KEM, under the 
same cryptographic assumption.

For example, the KEM Kyber (based on module LWE) at the 128-bit security 
level has 800-byte public keys and 768-byte ciphertexts.  The matching 
signature scheme Dilithium (also based on module LWE) has 1312-byte public keys 
and 2420-byte signatures.  Doing KEM-based server authentication rather than 
signature-based server authentication would thus save 2164 bytes per handshake.

We would still need digital signatures for a PKI (i.e., the root and 
intermediate CAs would sign certificates using PQ digital signature schemes), 
but the public key of the endpoint server can be a KEM public key, not a 
digital signature public key.

Douglas


> On Jul 12, 2021, at 20:30, Eric Rescorla  wrote:
>
> Hi folks,
>
> I have just given draft-celi-wiggers-tls-authkem-00.txt a quick
> read. I'm struggling a bit with the rationale, which I take to be
> these paragraphs:
>
>In this proposal we use the DH-based KEMs from [I-D.irtf-cfrg-hpke].
>We believe KEMs are especially worth discussing in the context of the
>TLS protocol because NIST is in the process of standardizing post-
>quantum KEM algorithms to replace "classic" key exchange (based on
>elliptic curve or finite-field Diffie-Hellman [NISTPQC]).
>
>This proposal draws inspiration from [I-D.ietf-tls-semistatic-dh],
>which is in turn based on the OPTLS proposal for TLS 1.3 [KW16].
>However, these proposals require a non-interactive key exchange: they
>combine the client's public key with the server's long-term key.
>This imposes a requirement that the ephemeral and static keys use the
>same algorithm, which this proposal does not require.  Additionally,
>there are no post-quantum proposals for a non-interactive key
>exchange currently considered for standardization, while several KEMs
>are on the way.
>
> I see why this motivates using a KEM for key establishment, but I'm
> not sure it motivates this design, whic

Re: [TLS] Comments on draft-celi-wiggers-tls-authkem-00.txt

[Blumenthal, Uri - 0553 - MITLL]

> If we are talking NIST Level 5 (and I am assuming you are
> discussing mTLS), 

Yes. ;-)

> ...have you calculated the total CertVerify+cert chain sizes
> there assuming 2 ICAs let's say? 

More or less. ;-)

My use case has all the ICAs pre-loaded - the transmitted chain contains only 
one entity cert. I'm sacrificing flexibility for performance under constraints. 
Size is the real enemy here.


> And would constrained devices or mediums that sweat about 5KB
> really be able to support PQ KEMs and Sigs at NIST Level 5?

My tests showed that they *do* support PQ KEMs (NTRU and Kyber - haven't tried 
McEliece ;) and Sigs (Falcon and Dilithium - haven't tried Rainbow ;) at Level 
5. Caveat - they do only Sig *verification* (which suits me fine).

(I posted benchmarks from Intel Core i9, but they work acceptably well on the 
"smaller" chips.)

Also, sorry if I did not make it clear - it's not the *devices* themselves that 
sweat 5KB, it's their austere links.



-Original Message-
From: TLS  On Behalf Of Blumenthal, Uri - 0553 - MITLL
Sent: Monday, July 12, 2021 11:39 PM
To: Douglas Stebila ; Eric Rescorla 
Cc:  
Subject: RE: [EXTERNAL] [TLS] Comments on 
draft-celi-wiggers-tls-authkem-00.txt

CAUTION: This email originated from outside of the organization. Do not 
click links or open attachments unless you can confirm the sender and know the 
content is safe.



Let me emphasize the reasons Douglas brought up. Note that I need to use 
NIST Sec Level 5 algorithms. So, Kyber-1024 and Dilithium5 (other algorithms 
show even worse ratio between KEM and signature!).

Communications costs:
- Difference in public key sizes: 1568 bytes of Kyber vs. 2592 bytes of 
Dilithium => 1024 extra bytes to carry over channel each way;
- Signature: extra 4595 bytes each way, because in addition to exchanging 
certs (aka "signed public keys", which is inevitable) you need to sign the 
exchange and communicate that signature across;
- Total: 5619 extra bytes each way. For peer-to-peer broadband connections, 
you can say "so what?". But my links are *very* austere.

Computation costs (ballpark, on a powerful CPU):
- KEM: keygen 15us, encap 18us, decap 14us (say, double encap and decap for 
PFS-providing exchange);
- Signature: sign 113us, verify 55us;
- Comparison: 134us for signature-less KEM vs. 215us for TLS-like exchange 
=> almost twice as long;
- Difference may be negligible for Intel Xeon, but for my much weaker 
hardware it matters.

So, for constrained environments with austere comm links, signature-less 
"authkem" is God-sent.
Big servers that need to support many clients (so they care how much CPU 
cycles and comm bytes they spend on every connection) would appreciate these 
savings too.

@ekr,I hope this provides convincing explanation why "authkem" is needed.

P.S. I know that Falcon has much more favorable sizes - but (a) it takes 
three times as long to sign, and (b) it uses FP calculations, which isn't great 
to implement in my environment.
--
Regards,
Uri

There are two ways to design a system. One is to make is so simple there 
are obviously no deficiencies.
The other is to make it so complex there are no obvious deficiencies.

 -  C. A. R. Hoare


On 7/12/21, 20:59, "TLS on behalf of Douglas Stebila"  wrote:

Hi Eric,

The main motivation is that, in some cases, post-quantum signatures are 
larger in terms of communication size compared to a post-quantum KEM, under the 
same cryptographic assumption.

For example, the KEM Kyber (based on module LWE) at the 128-bit 
security level has 800-byte public keys and 768-byte ciphertexts.  The matching 
signature scheme Dilithium (also based on module LWE) has 1312-byte public keys 
and 2420-byte signatures.  Doing KEM-based server authentication rather than 
signature-based server authentication would thus save 2164 bytes per handshake.

We would still need digital signatures for a PKI (i.e., the root and 
intermediate CAs would sign certificates using PQ digital signature schemes), 
but the public key of the endpoint server can be a KEM public key, not a 
digital signature public key.

Douglas


> On Jul 12, 2021, at 20:30, Eric Rescorla  wrote:
>
> Hi folks,
>
> I have just given draft-celi-wiggers-tls-authkem-00.txt a quick
> read. I'm struggling a bit with the rationale, which I take to be
> these paragraphs:
>
>In this proposal we use the DH-based KEMs from 
[I-D.irtf-cfrg-hpke].
>We believe KEMs are especially worth discussing in the context of 
the
>TLS protocol because NIST is in the process of standardizing post-
>quantum KEM algorithms to replace "classic" key e