Re: [TLS] [Pqc] Post-Quantum TLS instantiations and synthetic benchmarks
Hi Martin, As Sofía correctly saw, this is just plain TLS with the "straightforward" DH->KEM and Sig->PQ-Sig substitutions. I, of course, do have another 50 pages on how KEMTLS performs and compare it to these results, but I will save those for another day ;-) Cheers, Thom PQShield Op di 27 jun 2023 om 05:19 schreef Sofia Celi : > Hi Martin, > > I’m not the author of the note but, as far as I understand, it is not at > all about KEMTLS. The experiments use NIST submitted PQC KEM algorithms for > the key exchange and NIST submitted Signature algorithms for > authentication. Not sure if I would call this a “simpler integration” (as > digital signatures are as complex as KEMs) but, as far as I know, that is > not KEMTLS ;) > > Thanks, > > Sent from the phone > > > > On 27 Jun 2023, at 00:56, Martin Thomson wrote: > > > > Hi Thom, > > > > I infer - though it is not explicit - that this experiment is based on > the assumption that KEM-TLS is used, rather than a simpler integration. > Can you comment on what you see as the relative impact of that difference? > > > >> On Mon, Jun 26, 2023, at 21:48, Thom Wiggers wrote: > >> Hi TLS-wg and PQUIP-rg, > >> > >> Recently, I have computed the sizes and measured the performance of > >> post-quantum TLS (both PQ key exchange and post-quantum > >> authentication). In these experiments, I have examined combinations of > >> Kyber, Dilithium, Falcon, SPHINCS+-(sf), HQC, and XMSS. The experiments > >> include measuring their performance over two network settings, one > >> high-bandwidth, low-latency and one low-bandwidth, high-latency > >> connection. > >> > >> I have examined the instances at NIST PQC security levels I, III and V, > >> and for both unilaterally authenticated and mutually authenticated TLS. > >> > >> The report on these experiments (which is basically an excerpt of my > >> PhD thesis manuscript) can be found in the attached document. It's a > >> fairly dense document, so refer to the reading suggestions to easily > >> find what you are looking for. > >> > >> It can be found at > https://wggrs.nl/post/tls-measurements/handout-tls.pdf. > >> > >> I hope this document can be useful to: > >> > >> * get a feeling for how we can combine (signature) algorithms to fit > >> their differing roles in the handshake > >> * to see how this affects the handshake sizes, and > >> * have some indication of how the performance of these combinations of > >> algorithms is in a TLS stack on a network. > >> * Additionally, I believe my results are useful to compare the cost of > >> different NIST security levels. > >> > >> The experiments do not include SCTs or OSCP staples, but I think that > >> their effect can mostly be extrapolated from the reported results. Also > >> note that I am simulating the network environment, so the effect of the > >> initial congestion window is much less gradual than observed in > >> practice. > >> > >> As I write in the document, I want to examine the NIST on-ramp > >> candidates' suitability for use in TLS as soon as the list of > >> algorithms is formally out; for my PhD thesis they unfortunately came > >> into the picture too late. > >> > >> Cheers, > >> > >> Thom Wiggers > >> PQShield > >> > >> ___ > >> 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 > ___ TLS mailing list TLS@ietf.org https://www.ietf.org/mailman/listinfo/tls
Re: [TLS] [Pqc] Post-Quantum TLS instantiations and synthetic benchmarks
Thanks! These results are pretty much in line with expectations. It looks like you don't model packet loss and the effect of that. One concern I have is that increases in the number of packets will significantly increase exposure to loss. 1-(1-p)^n tends to increase quite a bit as n increases. p of 0.02 is a lot more common than people like to think, for which a full 10 packet CWND would need retransmissions almost 19% of the time. Also, RSA is probably OK here, even with the wildly asymmetric CPU costs, but the size comparisons would look better with P-256. Your claim that KDDD is faster than errr (errr) might not look as favourable for (though the client cost should increase, I'm not sure if would be slower). On Tue, Jun 27, 2023, at 17:49, Thom Wiggers wrote: > Hi Martin, > > As Sofía correctly saw, this is just plain TLS with the > "straightforward" DH->KEM and Sig->PQ-Sig substitutions. > > I, of course, do have another 50 pages on how KEMTLS performs and > compare it to these results, but I will save those for another day ;-) > > Cheers, > > Thom > PQShield > > Op di 27 jun 2023 om 05:19 schreef Sofia Celi : >> Hi Martin, >> >> I’m not the author of the note but, as far as I understand, it is not at all >> about KEMTLS. The experiments use NIST submitted PQC KEM algorithms for the >> key exchange and NIST submitted Signature algorithms for authentication. Not >> sure if I would call this a “simpler integration” (as digital signatures are >> as complex as KEMs) but, as far as I know, that is not KEMTLS ;) >> >> Thanks, >> >> Sent from the phone >> >> >> > On 27 Jun 2023, at 00:56, Martin Thomson wrote: >> > >> > Hi Thom, >> > >> > I infer - though it is not explicit - that this experiment is based on the >> > assumption that KEM-TLS is used, rather than a simpler integration. Can >> > you comment on what you see as the relative impact of that difference? >> > >> >> On Mon, Jun 26, 2023, at 21:48, Thom Wiggers wrote: >> >> Hi TLS-wg and PQUIP-rg, >> >> >> >> Recently, I have computed the sizes and measured the performance of >> >> post-quantum TLS (both PQ key exchange and post-quantum >> >> authentication). In these experiments, I have examined combinations of >> >> Kyber, Dilithium, Falcon, SPHINCS+-(sf), HQC, and XMSS. The experiments >> >> include measuring their performance over two network settings, one >> >> high-bandwidth, low-latency and one low-bandwidth, high-latency >> >> connection. >> >> >> >> I have examined the instances at NIST PQC security levels I, III and V, >> >> and for both unilaterally authenticated and mutually authenticated TLS. >> >> >> >> The report on these experiments (which is basically an excerpt of my >> >> PhD thesis manuscript) can be found in the attached document. It's a >> >> fairly dense document, so refer to the reading suggestions to easily >> >> find what you are looking for. >> >> >> >> It can be found at https://wggrs.nl/post/tls-measurements/handout-tls.pdf. >> >> >> >> I hope this document can be useful to: >> >> >> >> * get a feeling for how we can combine (signature) algorithms to fit >> >> their differing roles in the handshake >> >> * to see how this affects the handshake sizes, and >> >> * have some indication of how the performance of these combinations of >> >> algorithms is in a TLS stack on a network. >> >> * Additionally, I believe my results are useful to compare the cost of >> >> different NIST security levels. >> >> >> >> The experiments do not include SCTs or OSCP staples, but I think that >> >> their effect can mostly be extrapolated from the reported results. Also >> >> note that I am simulating the network environment, so the effect of the >> >> initial congestion window is much less gradual than observed in >> >> practice. >> >> >> >> As I write in the document, I want to examine the NIST on-ramp >> >> candidates' suitability for use in TLS as soon as the list of >> >> algorithms is formally out; for my PhD thesis they unfortunately came >> >> into the picture too late. >> >> >> >> Cheers, >> >> >> >> Thom Wiggers >> >> PQShield >> >> >> >> ___ >> >> 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 ___ TLS mailing list TLS@ietf.org https://www.ietf.org/mailman/listinfo/tls
Re: [TLS] [Pqc] Post-Quantum TLS instantiations and synthetic benchmarks
Hi Martin, Op di 27 jun 2023 om 13:18 schreef Martin Thomson : > Thanks! These results are pretty much in line with expectations. > Indeed, I don't think there are any results that are surprising when you know all of the details of the algorithms. But I do hope that this set of experiments provides a quick point of reference to both those who are familiar with those details and to those less familiar. :-) It looks like you don't model packet loss and the effect of that. One > concern I have is that increases in the number of packets will > significantly increase exposure to loss. 1-(1-p)^n tends to increase quite > a bit as n increases. p of 0.02 is a lot more common than people like to > think, for which a full 10 packet CWND would need retransmissions almost > 19% of the time. > A long while ago (while writing the original KEMTLS paper) we tried to model packet loss, but the main problem that we ran into is the fact that it mainly just seemed to drive up the error bars in the handshakes. We also had to stop somewhere with the measurements---but I will consider including 2% packet loss in a next benchmark run.[1] > Also, RSA is probably OK here, even with the wildly asymmetric CPU costs, > but the size comparisons would look better with P-256. Your claim that > KDDD is faster than errr (errr) might not look as favourable for > (though the client cost should increase, I'm not sure if would be > slower). > We again had to stop somewhere, obviously (my PhD thesis has become a *very* chunky book). Just for fun: looking at the raw numbers from my laptop, P256 and Dilithium2 seem close: openssl speed ecdsap256 signverifysign/s verify/s 256 bits ecdsa (nistp256) 0.s 0.0001s 50927.6 16308.6 versus liboqs speed_sig Operation| Iterations | Total time (s) | Time (us): mean | pop. stdev | CPU cycles: mean | pop. stdev | --:| --:| ---:| --:| -:| --: Dilithium2 ||| || | keypair | 131926 | 3.000 | 22.740 | 2.257 | 59330 | 5773 sign | 49496 | 3.000 | 60.612 | 36.122 |158216 | 94312 verify | 133519 | 3.000 | 22.469 | 1.411 | 58624 | 3465 As the effect of the additional bandwidth used by KDDD doesn't really kick in with how the experiments are set up (compared to https://blog.cloudflare.com/sizing-up-post-quantum-signatures/ which sees a gradual increase per kilobyte), I think that within the experiment parameters, our claim seems not too unreasonable still. In a slightly more real-world setting, ECDSA probably has us beat. Of course, any computation time that is well under a millisecond is basically academic (aka negligible) anyway; and this is the case for both algorithms on my laptop (and the benchmark server) at least. Cheers, Thom PQShield [1] Off-topic semi-ranty bit: You are completely right that I have no idea about the prevalence of packet loss. I still think that it is very unfortunate that there seems to be no "standard" set of parameters for this style of network benchmarks. I imagine it would be much more helpful to compare results if people use the same set of experimental parameters, but this does not seem to be the case unfortunately. I would also have appreciated a set of "reference" parameters like "this is a data center-tier connection", "this is a home fibre connection in a western city", "this is LTE in a city", and "this is what a poor-quality rural 3G link looks like". But alas, these don't seem to exist either. If someone does have these numbers, I would very much appreciate it if they maybe put them up as an RFC in some networking RG somewhere :) On Tue, Jun 27, 2023, at 17:49, Thom Wiggers wrote: > > Hi Martin, > > > > As Sofía correctly saw, this is just plain TLS with the > > "straightforward" DH->KEM and Sig->PQ-Sig substitutions. > > > > I, of course, do have another 50 pages on how KEMTLS performs and > > compare it to these results, but I will save those for another day ;-) > > > > Cheers, > > > > Thom > > PQShield > > > > Op di 27 jun 2023 om 05:19 schreef Sofia Celi : > >> Hi Martin, > >> > >> I’m not the author of the note but, as far as I understand, it is not > at all about KEMTLS. The experiments use NIST submitted PQC KEM algorithms > for the key exchange and NIST submitted Signature algorithms for > authentication. Not sure if I would call this a “simpler integration” (as > digital signatures are as complex as KEMs) but, as far as I know, that is > not KEMTLS ;) > >> > >> Thanks, > >> > >> Sent from the phone > >> > >> > >> > On 27 Ju
Re: [TLS] [Pqc] Post-Quantum TLS instantiations and synthetic benchmarks
Thanks for preparing the excerpt; this will be helpful for many use cases. (For the WebPKI, as you already mention, we also need to consider SCTs and realistically crappy networks.) "this is LTE in a city", and "this is what a poor-quality rural 3G link > looks like". But alas, these don't seem to exist either. > Unfortunately, it will not be as simple as plugging in a single packet loss number and then dropping that fraction of packets. Because TCP interpets packet loss as congestion, it grinds down to a halt much earlier than at a loss of 2%. Instead, lossy links such as WiFi and cellular have their own retransmission protocols hidden from TCP. ___ TLS mailing list TLS@ietf.org https://www.ietf.org/mailman/listinfo/tls
Re: [TLS] [Pqc] Post-Quantum TLS instantiations and synthetic benchmarks
Hi Bas, Op di 27 jun 2023 om 14:44 schreef Bas Westerbaan : > Thanks for preparing the excerpt; this will be helpful for many use cases. > (For the WebPKI, as you already mention, we also need to consider SCTs and > realistically crappy networks.) > > "this is LTE in a city", and "this is what a poor-quality rural 3G link >> looks like". But alas, these don't seem to exist either. >> > > Unfortunately, it will not be as simple as plugging in a single packet > loss number and then dropping that fraction of packets. Because TCP > interpets packet loss as congestion, it grinds down to a halt much earlier > than at a loss of 2%. Instead, lossy links such as WiFi and cellular have > their own retransmission protocols hidden from TCP. > Yeah, I'm all too familiar with wireless retransmission (a previous laptop had a bad wifi chip that would drop up to 1/3rd of the packets leading to massive latency spikes). Still, I hope that someone has a good idea on how to best represent these facets of real-world networking in some way that is useful for experiments :) Cheers, Thom ___ TLS mailing list TLS@ietf.org https://www.ietf.org/mailman/listinfo/tls
Re: [TLS] [Pqc] Post-Quantum TLS instantiations and synthetic benchmarks
Imo, we have been measuring handshake time as an indication or performance, but time-to-last-byte or time-to-x%-byte should be used instead. There is nothing wrong with your study Thom. It is pretty detailed and useful. I just think that if these new algos get deployed, we would know if their impact would be noticeable by measuring different things that what we have been measuring so far. An 150KB (on average) web page over a lossy LTE connection will have pretty bad user experience regardless of adding 10-15KB of Dilithium certs or 1-2KB of Kyber keys/ciphertexts. From: Pqc On Behalf Of Thom Wiggers Sent: Tuesday, June 27, 2023 4:04 PM To: Bas Westerbaan Cc: Martin Thomson ; Sofía Celi ; tls@ietf.org; p...@ietf.org Subject: RE: [EXTERNAL][Pqc] [TLS] Post-Quantum TLS instantiations and synthetic benchmarks 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. Hi Bas, Op di 27 jun 2023 om 14:44 schreef Bas Westerbaan mailto:b...@cloudflare.com>>: Thanks for preparing the excerpt; this will be helpful for many use cases. (For the WebPKI, as you already mention, we also need to consider SCTs and realistically crappy networks.) "this is LTE in a city", and "this is what a poor-quality rural 3G link looks like". But alas, these don't seem to exist either. Unfortunately, it will not be as simple as plugging in a single packet loss number and then dropping that fraction of packets. Because TCP interpets packet loss as congestion, it grinds down to a halt much earlier than at a loss of 2%. Instead, lossy links such as WiFi and cellular have their own retransmission protocols hidden from TCP. Yeah, I'm all too familiar with wireless retransmission (a previous laptop had a bad wifi chip that would drop up to 1/3rd of the packets leading to massive latency spikes). Still, I hope that someone has a good idea on how to best represent these facets of real-world networking in some way that is useful for experiments :) Cheers, Thom ___ TLS mailing list TLS@ietf.org https://www.ietf.org/mailman/listinfo/tls
