Request for feedback on Classic McEliece

[Moody, Dustin (Fed)]

All,

NIST is confident in the security of Classic McEliece and would be comfortable standardizing the submitted parameter sets (under a different claimed security strength in some cases). However, it is unclear whether Classic McEliece represents the best option for enough applications to justify standardizing it at this time. For genera lpurpose systems wishing to base their security on codes rather than lattices, BIKE or HQC may represent a more attractive option. 

NIST would like feedback on specific use cases for which Classic McEliece would be a good solution.

Thank you,

NIST PQC team

[Mike Hamburg]

Hi Dustin and team,

I propose that virtual private networks are a use case where Classic McEliece may be a good fit.  Of course not all VPN deployments are the same, but often the parties deploying a VPN are willing to pay a premium for more confidence in the security of their communications.  VPNs connect relatively infrequently, perhaps a few times per day.  They are often deployed in places where bandwidth is relatively cheap, such as offices or homes, so large public keys are affordable.  Furthermore, VPNs have relatively static client-server relationships, so the public keys can be cached depending on the desired forward secrecy window.

Regards,

— Mike

-- 
You received this message because you are subscribed to the Google Groups "pqc-forum" group.
To unsubscribe from this group and stop receiving emails from it, send an email to pqc-forum+...@list.nist.gov.
To view this discussion on the web visit https://groups.google.com/a/list.nist.gov/d/msgid/pqc-forum/SA1PR09MB86692928B933935B57535F57E5159%40SA1PR09MB8669.namprd09.prod.outlook.com.

[Blumenthal, Uri - 0553 - MITLL]

Respectfully disagree. I certainly can’t afford megabytes-worth of key exchange on my home VPN, and I’m sure my work would frown at the cost as well (especially scaling it up to all the employees, whose keys the work-server-appliance would need to cache). This could work only for pre-provisioned/cached scenarios, and once the cache gets invalidated for whatever reason, the cost becomes prohibitive. Bandwidth can never be this cheap, as laws of physics limit it. Also, even if bandwidth is free – factor in the latency caused by the need to download (and upload) public key of such size...

 

As I see it, the McEliece use case should fit all of the following:

• Pre-defined or static group of communicating entities – additions to the group must happen rarely; and
• Or the entities really don’t mind exchanging megabytes-worth of public keys – but I can’t think of any situation where it’s true;
• High tolerance to maintaining/caching large public keys for all the acceptable peers.

 

Might add “Can’t afford larger ciphertexts of Lattice-based KEMs”, but in this case all the peers must be pre-provisioned, with no possibility to re-key.

--

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

To view this discussion on the web visit https://groups.google.com/a/list.nist.gov/d/msgid/pqc-forum/2D692D2D-6763-4216-83CC-4360AEBA5DD9%40shiftleft.org.

[Mike Hamburg]

Hi Uri,

I understand your disagreement, but I will back up my suggestion with some calculations.  Let’s suppose you’re working remotely, connecting to an office VPN 100 times per month (~4-5x per workday, more than the typical once in the morning and maybe once after lunch), with mceliece8192128 (the largest instance, with a 1.36 MB public key) sent by the server to your laptop, which is on your home network.  Suppose that the server’s public key is never cached for some reason, that the 208-byte ciphertext is negligible for this analysis (anyway it’s smaller than Kyber), and that other components of a VPN key exchange are out of scope.  I would expect a VPN to use signing client certs (especially if the alternative is McEliece), but I will briefly touch on McEliece client certs later.

Suppose you have mediocre American internet: Comcast XFinity cable internet with 75 Mbps download speed and a 1.2 TB monthly data cap.  The price and availability of such internet depends on location, but in San Francisco that’s the cheapest tier at $25/mo.  With such a connection, downloading the key takes 1.36e6 * 8 bit / (75e6 bit / s) = 127ms at rated speeds, or maybe double that if the network is loaded.  Doing this 100 times per month uses 136 MB, which is 0.01% of your data cap. That latency isn’t great, but if you have to type your password or use two-factor authentication or even scan a finger, then it takes much longer than a quarter-second to log in.

Suppose the server is on Amazon EC2 in Northern California.  I’m choosing this because it’s easy to determine pricing; Amazon are not known to be especially cheap.  An on-premises server rack with business internet would likely have cheaper bandwidth, but it’s complicated to calculate because logins are likely to be bursty.  Anyway, outgoing data transfers from that zone cost $0.09 / GB, ignoring bulk discounts as you scale up.  At 136 MB / month, this is costing the company about 1.2¢ / month / user.  I’m not an accountant, but this seems plenty affordable to me.

For some protocols, it’s possible that the client must also upload a McEliece key.  That seems unlikely, and more likely to be cacheable since client certs are not regenerated frequently.  Typically the dollar cost for uploads is similar to the cost for downloads (actually less on AWS), but the available bandwidth from homes is much lower — perhaps by a factor of 10, leading to a 1.2s - 2.5s increased login latency when the cache is invalid.  That’s getting pretty inconvenient, but it’s not outright unaffordable.

Suppose instead that the company caches the certs server-side.  If the company is Microsoft and has 221,000 employees, then this uses 300 GB of storage to cache one key for each employee.  Possibly you would need a few keys per employee (cell phone, older keys or whatever) so let’s say it takes 1 TB, and the cache must be replicated across several VPN gateways.  That’s a lot, but you’re only reaching this size at Microsoft’s scale.  Putting 1 TB SSD in each of 100 gateways costs what, $10k?  I’m pretty sure Microsoft can afford this as a 1-time capex — and again, I think the likely case is that you’re using signatures (I dunno, SPHINCS+?) for client certs, and use McEliece in the other direction.

As a comparison point, Zoom’s system requirements page recommends 600 kilobit / second incoming and outgoing bandwidth for “high quality” 1-on-1 video calling.  “High quality” is the lowest full-frame video option, with half the bitrate of 720p, and group calls use more bandwidth.  At that rate, a 1-hour video Zoom meeting would use 600 kbit * 3600 / 8 = 270 megabytes incoming data, which is about double the above budget for a month of McEliece key exchanges.  This is a recommendation for smooth video and not a real usage estimate, so the true value might only be a quarter of this, but even then a month of key exchanges costs the same bandwidth as a couple hours of meetings (downstream, and the meetings also require upstream bandwidth).  Remote work is bandwidth intensive: for example, my work laptop has downloaded about 40 GB and uploaded about 7 GB in the past month according to its network statistics.

This is not representative of every user or every company, and surely some will not be able to afford it.  The above calculation with cellular tethering — say Google Fi Flexible at $10 / GB — would be much more significant at $1.36 / user / mo with no caching.  But for companies using typical remote work tools, the VPN key exchanges will not be a large fraction of their bandwidth budget, and I think some will consider a cents-per-user-per-month cost to be affordable for the increased assurance.

Also this whole calculation is assuming no client-side caching at all.  A realistic deployment would have at least some caching.

Regards,

— Mike

[Brent Kimberley]

>>It appears that we might be building the case for a DPU or HSM capable of storing megabytes-worth of key exchange.

To view this discussion on the web visit https://groups.google.com/a/list.nist.gov/d/msgid/pqc-forum/BABFBE19-1410-4B00-B329-EE8BF2E9C305%40shiftleft.org.

THIS MESSAGE IS FOR THE USE OF THE INTENDED RECIPIENT(S) ONLY AND MAY CONTAIN INFORMATION THAT IS PRIVILEGED, PROPRIETARY, CONFIDENTIAL, AND/OR EXEMPT FROM DISCLOSURE UNDER ANY RELEVANT PRIVACY LEGISLATION. No rights to any privilege have been waived. If you are not the intended recipient, you are hereby notified that any review, re-transmission, dissemination, distribution, copying, conversion to hard copy, taking of action in reliance on or other use of this communication is strictly prohibited. If you are not the intended recipient and have received this message in error, please notify me by return e-mail and delete or destroy all copies of this message.

[Gustavo Souza Banegas]

Hi Mike, Hi Uri, 

Well, MulladVPN has added an experimental feature in July 2022 that allows users to use McEliece with WireGuard. See [1] for more details. 

This is bigger than a private network for sure, I don't think that they showed the results of the number of users and data, but it is still already a change towards something considered "too big". 

All the best,

Gustavo

[1] - https://mullvad.net/fr/blog/2022/7/11/experimental-post-quantum-safe-vpn-tunnels/

To view this discussion on the web visit https://groups.google.com/a/list.nist.gov/d/msgid/pqc-forum/YT1PR01MB41871B863C44BDA5CC897B92FA159%40YT1PR01MB4187.CANPRD01.PROD.OUTLOOK.COM.

--

Best Regards,

Gustavo Souza Banegas
http://www.cryptme.in/

[Simon Hoerder]

Hi,

Would ‘BSI compatibility’ be a valid use-case? As far as I understand, Germany’s BSI is sticking to their TR-02202-1 recommendation of Classic McEliece and FrodoKEM and does not intend to follow NISTs example of standardising CRYSTALS-Kyber. My understanding may be wrong though, would be good to hear from BSI itself. It would also be good to know whether BSI will adopt the round 4 version of Classic McEliece or whether they prefer to stay with older versions at the risk of international incompatibility. 

Another question that I can’t  answer is whether BSI TR-02102-1 will have any impact beyond German NSS.

Best,

Simon
(speaking for myself only)

On 30 Nov 2022, at 13:30, 'Moody, Dustin (Fed)' via pqc-forum <pqc-...@list.nist.gov> wrote:



--

[Sofi Celi]

Dear, all,

Thank you, Dustin, for starting this discussion.

I agree with Mike. The post-quantum Wireguard paper by Hülsing et al. (https://eprint.iacr.org/2020/379.pdf) gives good insight: Classic McEliece with its small ciphertext size can be used for operations in which the transmission of public key material is not constantly needed (static long-term keys, where keys are not rotated so often or somehow they are cached). So VPNs seem like a good candidate.

There is also research on using it in OpenVPN: https://essay.utwente.nl/70677/1/2016-08-09%20MSc%20Thesis%20Simon%20de%20Vries%20final%20color.pdf

Thank you,

To view this discussion on the web visit https://groups.google.com/a/list.nist.gov/d/msgid/pqc-forum/A91BCBAC-7FB8-46EB-82D4-3BE420066C9B%40hoerder.net.

--

Sofía Celi
@claucece
Cryptographic research and implementation at many places, but specially at Brave

Reach me out at: cher...@riseup.net
74BE 6517 031D 11CC D233  3FCA 44DF 95B9 E3BC 4369

[Bruno Couillard]

Dustin, NIST team,

Thank you for asking the question and allowing the community to participate in this process.

Crypto4A currently uses Classic McEliece in all of its HSMs for three important use cases:

1.            To secure the transfer of sensitive items (keys, secrets and other information) between HSMs in “clustered scenario”;

2.            To secure the transfer of sensitive information from Crypto4A to its fielded HSMs; and

3.            To secure the long term archiving of users' sensitive material.

In all of the above use cases, we use a hybrid approach (ECDH P-384 and McEliece) that offers both FIPS compliance as well as PQC readiness.

 

We determined a long time ago that the conservative and strong security claims of Classic McEliece would confer our HSM a strong claim of being Quantum Safe by design.

For the same reasons that have driven us to adopt Classic McEliece for its more conservative security properties, we believe that Classic McEliece will find use in other systems where the importance of said systems, or their inherent unsuitableness to support future updates (think of satellite systems and Industrial IoT for instance) are paramount. For those use cases, it is possible to envision a conservative PQC KEM such as Classic McEliece.

 

We also consider that use-cases such as long term archiving of “petabytes” of data for many decades would also benefit from using a very conservative KEM algorithm such as Classic McEliece.

Without a proper standardisation and ensuing validation process that would come from a proper NIST standardization process, Classic McEliece might not ever be considered by the masses as being a “legitimate” PQC algorithm. It is our belief that for those uses-cases where highly sensitive information is being protected for many decades, or systems that wouldn’t be easy to upgrade once launched/deployed, Classic McEliece is a very strong candidate PQC KEM, and users will find ways to accommodate the large public key sizes in the interest of security.

We hope that the above sample use-cases and reasoning might favour the standardisation of Classic McEliece in the next round.

Sincerely,

 

Team Crypto4A

--

[Stephan Ehlen]

Dear Simon,

dear all,

thank you for pointing out our (BSI's) recommendations.

Indeed, BSI recommends FrodoKEM-976 and FrodoKEM-1344

as well as Level 3 and 5 parameters for Classic McEliece in TR-02102-1

(see https://www.bsi.bund.de/EN/Themen/Unternehmen-und-Organisationen/Standards-und-Zertifizierung/Technische-Richtlinien/TR-nach-Thema-sortiert/tr02102/tr02102_node.html).

Even though FrodoKEM is no longer in the NIST process, we intend to keep this recommendation.

We will evaluate draft standards of NIST's selection when they are published and (in principle)

we are open to adding further algorithms to our technical guidelines after conclusion of our evaluation.

Best,

Stephan

Dr. Stephan Ehlen
____________________________________
Referat KM 21 -  Vorgaben an und Entwicklung von Kryptoverfahren
Bundesamt für Sicherheit in der Informationstechnik

Godesberger Allee 185-189
53175 Bonn
E-Mail:          stepha...@bsi.bund.de
Internet:       www.bsi.bund.de

#DeutschlandDigitalSicherBSI

Alle Informationen zum Umgang mit Ihren personenbezogenen
Daten finden Sie unter bsi.bund.de/datenschutz.

[Wrenna Robson]

Hi Stephen,

Is there an intention to create a standardised form of FrodoKEM? If so, under whose auspices? If not, what is to be considered the definitive version against which those who wish to follow this recommendation must compare implementations?

Best,

Wrenna

To view this discussion on the web visit https://groups.google.com/a/list.nist.gov/d/msgid/pqc-forum/fb6430c2-ce28-4f36-8481-be7b387ab283n%40list.nist.gov.

[Stephan Ehlen]

Hi Wrenna,

at BSI, we support international standardization of FrodoKEM and Classic McEliece.

For instance, there are now some standardization efforts at ISO for PQC and

we hope that our two conservative recommendations will be part of these efforts.

Best,

Stephan

Dr. Stephan Ehlen
____________________________________
Referat KM 21 -  Vorgaben an und Entwicklung von Kryptoverfahren
Bundesamt für Sicherheit in der Informationstechnik

Godesberger Allee 185-189
53175 Bonn

E-Mail:          stephan.ehlen@bsi.bund.de

Internet:       www.bsi.bund.de

#DeutschlandDigitalSicherBSI

Alle Informationen zum Umgang mit Ihren personenbezogenen
Daten finden Sie unter bsi.bund.de/datenschutz.

[John Mattsson]

Dear Stephan Ehlen,

 

If BSI wants to use FrodoKEM and Classic McEliece and NIST do not publish them, I think BSI should approach IRTF CFRG and publish the algorithms there, alternatively publish them as BSI documents. As Ericsson wrote in our comments on FIPS 186-5 we think it is grat that NIST is specifying ECDSA in FIPS 186-5 instead of relying on references behind paywalls. We do not think that cryptographic algorithm specifications behind paywalls are acceptable. Open access is very important for security specifications as history has showed over and over again that lack of analysis often lead to serious weaknesses.

 

Best Regards,

John Preuß Mattsson

To view this discussion on the web visit https://groups.google.com/a/list.nist.gov/d/msgid/pqc-forum/09daede0-fc41-493c-99a8-cfd91188a6a4n%40list.nist.gov.

[Simon Hoerder]

Dear Stephan, dear John, dear all,

Thank you for the information, Stephan. I fully agree with John that paywalled standards such as produced by ISO are undesirable. Putting a standard behind a paywall will not just increase security risks but also hinder adoption. IETF standards, NIST FIPS and SP800 standards and BSI’s own AIS standards are successful because of they are available to be scrutinized and implemented by everyone. Everyone can decide whether to trust them, everyone can deploy them once they do trust.

Best regards,

Simon

(speaking only for myself)

On 13 Dec 2022, at 20:01, John Mattsson <john.m...@ericsson.com> wrote:



[Tobias Fehenberger]

Dear NIST team, PQC community,

applications with a high bandwidth can benefit from the security of Classic McEliece. This includes high-speed optical networks where terabits of data are transmitted every second.

Since these systems are usually equipped with specialized and often low-clocked processors, the costly key generation can be avoided by reusing the public key for an appropriate number of ciphertexts as recommended by the Classic McEliece team. Furthermore, the fast encapsulation and decapsulation enables possible key update rates even below one second, which might be of interest for very high data rates.

Our real-world use-case are
1)    Encrypted layer 1 optical transport solutions (OTNsec) with 10-400 Gbit/s including BSI approval

Possible future use cases are
2)    MACsec using a FIPS-approved (hybrid) key agreement scheme where the Classic McEliece public key is associated to an ethernet port and can be used for multiple secure associations. This results in a very efficient post-quantum-secure key establishment.

The trade-off to be made is between (quantum) perfect forward secrecy and reusing the KEM key pair.

ADVA / Adva Network Security

[Iluminada Baturone]

Dear NIST team, PQC community,

 

In my research group we have been working on protecting the biometric templates associated with people identities by using post-quantum cryptography.

We have found Classic McEliece offers advantages for distributed biometric systems, in terms of  storage and communication overheads, with a reduction of more than 90.5% compared to other post-quantum solutions (particularly Kyber and Saber).

Concerning execution times, the facial authentication system that we have implemented allows real-time execution in clients (with Android App for smartphones) and servers (with Phyton code). This is explained in our paper (which is available open access):

"Post-Quantum Biometric Authentication Based on Homomorphic Encryption and Classic McEliece"

https://doi.org/10.3390/app13020757

Regards,

Iluminada.

--------

University of Seville (Spain)

[D. J. Bernstein]

'Moody, Dustin (Fed)' via pqc-forum writes:
> NIST would like feedback on specific use cases for which Classic
> McEliece would be a good solution.

I've just posted a paper "Predicting performance for post-quantum
encrypted-file systems": https://cr.yp.to/papers.html#pppqefs

The abstract is as follows: "Public-key cryptography is widely deployed
for encrypting stored files. This paper uses microbenchmarks and
purchase costs to predict the performance of various post-quantum KEMs
in this application, in particular concluding that Classic McEliece is
(1) the most efficient option and (2) easily affordable."

The paper's investigation of purchase costs for equipment and energy
concludes that, with current technology, each dollar pays for roughly

* 2^51 CPU cycles, or
* reading 2^51 bytes from a local hard drive, or
* sending 2^40 bytes through the Internet, or
* storing 2^38 bytes for a year.

These numbers are then combined with cryptographic microbenchmarks and
models of how encrypted-file systems are used. The numbers can also be
used to predict costs of applications beyond file encryption.

---D. J. Bernstein (speaking for myself)

[Anjan Roy]

Dear DJB and all,

Wow this is quite amazing. Thanks for sharing.

Regards,

Anjan 

--
You received this message because you are subscribed to the Google Groups "pqc-forum" group.
To unsubscribe from this group and stop receiving emails from it, send an email to pqc-forum+...@list.nist.gov.

To view this discussion on the web visit https://groups.google.com/a/list.nist.gov/d/msgid/pqc-forum/20231206145517.2024675.qmail%40cr.yp.to.

[Kampanakis, Panos]

Hi Dan,

Interesting analysis. I would rephrase the argument to "(1) the most efficient option especially for small file encryption and (2) easily affordable".

Indeed, for use-cases where the public key is re-used, someone could benefit from McEliece's small size ciphertext. There was a similar argument about using multivariate schemes in X.509 SCTs since the signatures were pretty small and the public key is pre-distributed. Btw, the same rationale could be an argument against SLH-DSA being used to sign small-size files or software/firmware.

The paper mentions this in page 10, but I think the analysis holds more ground for files > 10-30KB when comparing against ML-KEM or BIKE. The idea is that if your space and communication cost is dominated by the file size then the benefit you get from McEliece's ciphertext size is lower. For example, comparing the cost of encrypting a 30KB file with McEliece vs BIKEIII means that your file space and communication cost per file will be ~10x vs 11x for McEliece or BIKEII respectively, where x is the space and communication cost for a BIKEIII ciphertext. For 300KB files, it would have been ~300x vs 301x. So as the files grow the difference does not matter.

I would be interested to see the comparison if you assumed some file size distribution for S, E and D and calculated the total costs for those. For example, you could assume some arbitrary distribution where 30% of the files are ~30KB, 40% are ~100KB, 20% are 500KB and the rest are 10MB. Or you could use a distribution of E and D from [27] and for S from [16] in order to analyze the cost of McEliece vs ML-KEM vs BIKE. My intuition is that for real-world filesystems these KEMs won't make material impact.

A side comment about the arguments the paper brings up regarding Frodo or McEliece and TLS: Although this has been discussed before, I want to repeat it. We don't need any cost analysis for TLS. There have been many research and experimental publications which have pointed out the differences in performance between the KEMs. Arguing that going from 32-64B on the wire today to 10-20KB or 1MB is straightforward is unrealistic. No one in their right mind would deploy either Frodo or McEliece in TLS at scale when there is a good 1-3KB KEM primitive. Sure, we could use semi-static public keys and cache 1MB public keys at the ISP close to the user, we could use DNS to cache them, we could pre-distribute them etc. But these are not straightforward. If we quantify the cost of bytes on the wire, we ought quantify the cost of redesigning the Internet like that or the cost of potential outages or failures when deploying 1MB public keys.

In spite of all the criticisms of NIST, ML-KEM and BIKE/HQC offer good size/performance balance as general-use KEM candidates. There were only a few others that had similar properties from that perspective, but personally I think NIST overall made good choices in that respect.

And one correction: The paper references the HTTP Archive and says that each page is ~2MB but each page is not pulled over 1 TLS connection. The HTTP Archive shows ~2MB per page for all resources pulled and it also mentions 10-11 connections per page. That means that each connection carries about ~200KB. That is from the HTTP Archive. Depending on the application, the data per connection could vary of course.

Rgs,
Panos

-----Original Message-----
From: pqc-...@list.nist.gov <pqc-...@list.nist.gov> On Behalf Of D. J. Bernstein
Sent: Wednesday, December 6, 2023 9:55 AM
To: pqc-forum <pqc-...@list.nist.gov>

[Daniel Apon]

The reader should note that the paper https://cr.yp.to/papers/pppqefs-20231206.pdf ..very oddly.. cites [22] https://groups.google.com/a/list.nist.gov/g/pqc-forum/c/7aenKgDWV2k/m/1SJkfLT9DQAJ in a manner that appears to omit the context of [22] that that discussion was regarding " post-quantum TLS key exchange" whereas the discussion in https://cr.yp.to/papers/pppqefs-20231206.pdf is about the entirely separate use-case of encrypted-file systems.

I comment that perhaps there are some use-cases where Classic McEliece could be a viable option. (It's not TLS.)

To view this discussion on the web visit https://groups.google.com/a/list.nist.gov/d/msgid/pqc-forum/CANhqc%2BNkcWFtApBsxNb1dr2-kSRwoDWpjqG%2Bd7FaLHLc8VZKng%40mail.gmail.com.

[Daniel Apon]

Quoting https://eprint.iacr.org/2023/1873.pdf, Footnote 4: "A reader may wonder if Classic McEliece [3] has been also integrated into TLS. We have not found such a work, and we suspect that this is because TLS does not support public keys larger than 2 16 − 1 bytes [87], but the smallest public key size for Classic McEliece is 4× this limit"

I'm down for TLS 1.4; let's go.

[Peter Schwabe]

Daniel Apon <dapon....@gmail.com> wrote:

Dear all,

> The reader should note that the paper
> https://cr.yp.to/papers/pppqefs-20231206.pdf ..very oddly.. cites [22]
> https://groups.google.com/a/list.nist.gov/g/pqc-forum/c/7aenKgDWV2k/m/1SJkfLT9DQAJ
> in a manner that appears to omit the context of [22] that that discussion
> was regarding " post-quantum TLS key exchange" whereas the discussion in
> https://cr.yp.to/papers/pppqefs-20231206.pdf is about the entirely separate
> use-case of encrypted-file systems.
>
> I comment that perhaps there are some use-cases where Classic McEliece
> could be a viable option. (It's not TLS.)

That depends a bit on the definition of TLS. I agree that Classic
McEliece is not a drop-in replacement for ECDHE in TLS as it is today.
However, when considering KEMTLS-PDK [1], Classic McEliece is the most
efficient option for the static KEMs. For application in mobile apps,
see, e.g., https://eprint.iacr.org/2023/734 (in particular Section 5.4
and Table 4).

Cheers,

Peter

[1] https://eprint.iacr.org/2021/779

> > https://groups.google.com/a/list.nist.gov/d/msgid/pqc-forum/CANhqc%2BNkcWFtApBsxNb1dr2-kSRwoDWpjqG%2Bd7FaLHLc8VZKng%40mail.gmail.com
> > <https://groups.google.com/a/list.nist.gov/d/msgid/pqc-forum/CANhqc%2BNkcWFtApBsxNb1dr2-kSRwoDWpjqG%2Bd7FaLHLc8VZKng%40mail.gmail.com?utm_medium=email&utm_source=footer>
> > .

> >
>
> --
> You received this message because you are subscribed to the Google Groups "pqc-forum" group.
> To unsubscribe from this group and stop receiving emails from it, send an email to pqc-forum+...@list.nist.gov.

> To view this discussion on the web visit https://groups.google.com/a/list.nist.gov/d/msgid/pqc-forum/CAPxHsS%2B7KtChCMCNSqWCLePHbdYVmcy%3DZuYZKH1gbwFAcWA%2B5A%40mail.gmail.com.

[Daniel Apon]

Good point! TLS standardization is something outside of my wheelhouse (is it easy to change? is it hard?). Do you know whether IETF is considering changes to accommodate variants of "TLS as it is today"? (Well, I suppose "seriously considering" - whatever that might mean)

[Daniel Apon]

(Clearly the PDK scenario makes McEliece very attractive)

[Thom Wiggers]

Hi Daniel,

In the TLS working group at the IETF, we are currently pushing a discussion on the subject of KEM authentication for TLS (i.e. KEMTLS); but since we’re only covering the KEM authentication it’s now called AuthKEM.

We have two drafts:

1. https://datatracker.ietf.org/doc/draft-celi-wiggers-tls-authkem/

Which discusses integrating KEM public keys in certificates. Classic McEliece doesn’t realistically work for this use case, even though certificate sizes might permit this.

2. https://datatracker.ietf.org/doc/draft-wiggers-tls-authkem-psk/

This spin-off from AuthKEM is the “what if we use a KEM ciphertext in the existing pre-shared key mechanism” proposal that is essentially KEMTLS-PDK. 

You may note that these two drafts are still “individual submissions”, and not adopted by the TLS working group: we’re still very much discussing the merits. I’d like to invite all who think these mechanisms could help solve their problems to bring their comments and point of view to the IETF TLS mailing list (or reach out to me).

As Panos rightly noted, pre-distributing keys like required for AuthKEM-PSK, in particular with keys the size of Classic McEliece, is a highly niche solution. If you were using ML-KEM, the PSK mechanism could potentially be used for 'resumptions’ (without relying on symmetric keys) by simply caching the server’s certificate key. For Classic McEliece, you would likely need to distribute keys out of band, which makes the whole PKI and all related considerations (e.g. how do you do key rotation?) much more complicated — and as soon as you need to transmit a McEliece public key somewhat regularly you lose a lot of the gains from its small ciphertext. Finally, storing such large public keys on endpoint devices has costs.

Cheers,

Thom

By the way, if anyone is interested, I have a lot of pages with updated-as-of-last-spring benchmarks for post-quantum TLS, OPTLS, KEMTLS and KEMTLS-PDK in my PhD thesis. This includes unilateral and mutual authentication, and security levels I, III and V. Find it through https://thomwiggers.nl/publication/thesis/

To view this discussion on the web visit https://groups.google.com/a/list.nist.gov/d/msgid/pqc-forum/CAPxHsSL%2Bb87MBPkQOSvR%2BN%2BdeCYq%3DUNgTmWYBjZCHfj-J2htug%40mail.gmail.com.

[D. J. Bernstein]

'Kampanakis, Panos' via pqc-forum writes:
> if your space and communication cost is dominated by the file size
> then the benefit you get from McEliece's ciphertext size is lower.

Lower as a percentage of total costs, sure. See Section 6 ("Costs in
context"): "A different way to build confidence in the affordability of
post-quantum encrypted-file systems is to compare the costs of
post-quantum cryptography to other file-system costs" etc.

As an analogy, if Internet traffic is dominated by videos and other
large downloads, then there's negligible savings in Internet traffic
from, say, choosing Kyber-768 instead of Kyber-1024.

> We don't need any cost analysis for TLS.

Section 6.2 ("Other applications") quotes NIST claiming that "Frodo is
clearly not an immediate drop-in general-purpose scheme". NIST pointed
to frodokem640's 20KB of network traffic (assuming a new key for every
ciphertext) and 2 million cycles on the server.

That's roughly 0.02 microdollars of network traffic and roughly 0.001
microdollars of CPU time. A user starting a _million_ TLS sessions would
spend roughly $0.02 on frodokem640 (or roughly $0.05 for frodokem1344;
of course, a frodokem1344 ciphertext needs to be split across two TLS
records). Is there evidence somewhere that users are starting enough TLS
sessions to turn these costs into a problem?

The paper says "It would be interesting to collect data on the number of
TLS sessions initiated in a day by an average user's browser, the number
of different TLS servers contacted, etc."

> And one correction: The paper references the HTTP Archive and says
> that each page is ~2MB but each page is not pulled over 1 TLS
> connection. The HTTP Archive shows ~2MB per page for all resources
> pulled and it also mentions 10-11 connections per page. That means
> that each connection carries about ~200KB. That is from the HTTP
> Archive.

The paper already says this: "A web page can collect data from multiple
servers, but the number of TCP connections per web page has dropped to
10 (see again [18]), so the number of TLS sessions involved is at most
10. In other words, the 20000 bytes for FrodoKEM cannot add more than
10% to overall web-page traffic, and if a user is retrieving at least 10
web pages per TLS session then 20000 bytes cannot add more than 1%."

The case of frodokem640's 20KB adding "10% to overall web-page traffic"
is the case you're talking about: 1 TLS session per connection, 2MB per
web page, 10 connections per web page.

The HTTP Archive is based on crawl data, so of course it has no idea how
many web pages (or, more to the point, how many bytes of data) are being
retrieved by a browser through an average TLS session. Has anyone seen a
browser plugin (or local HTTPS proxy) that tallies the number of TLS
sessions, the number of bytes retrieved, etc.?

---D. J. Bernstein

[D. J. Bernstein]

Daniel Apon writes:
> The reader should note that the paper
> https://cr.yp.to/papers/pppqefs-20231206.pdf ..very oddly.. cites [22]
> https://groups.google.com/a/list.nist.gov/g/pqc-forum/c/7aenKgDWV2k/m/1SJkfLT9DQAJ
> in a manner that appears to omit the context of [22] that that discussion
> was regarding " post-quantum TLS key exchange" whereas the discussion in
> https://cr.yp.to/papers/pppqefs-20231206.pdf is about the entirely separate
> use-case of encrypted-file systems.

No.

Section 6 of the paper is "Costs in context": "This section compares the
costs of post-quantum encrypted-file systems to other file-system costs
and to costs of other applications of post-quantum cryptography."

Section 6.2 is "Other applications". Within that, there's a paragraph
about "FrodoKEM in TLS key exchange", in particular quoting [22]. The
TLS context is clear and explicit.

---D. J. Bernstein

[Thom Wiggers]

Hi Dan,

Op 7 dec 2023, om 14:56 heeft D. J. Bernstein <d...@cr.yp.to> het volgende geschreven:

Has anyone seen a
browser plugin (or local HTTPS proxy) that tallies the number of TLS
sessions, the number of bytes retrieved, etc.?

It’s not really a plugin or a ready-made solution, but one way to potentially approach collecting this data, is to specify SSLKEYLOGFILE=/some/file in the environment before starting Chrome or Firefox.  This will make them dump the master secret for TLS sessions in the file. [1] You could then use Wireshark or tshark to record and dissect TLS traffic, including its contents.

Naturally, obtaining a representative sample of web traffic / users and carefully and ethically setting up the experiment for recording users are the truly hard problems here, and you are probably better suited with a different solution, such as a browser extension (or scripting against the Browser’s developer tools?), that only records the relevant metrics — but perhaps this is helpful if you want to get some rough idea quickly.

Cheers,

Thom

[1]: https://datatracker.ietf.org/doc/draft-thomson-tls-keylogfile/ 

[John Mattsson]

Hi,

 

I think NIST should standardize Classic McEliece. Classic McEliece is seen as a conservative KEM alternative and in some use cases it has the best performance due to the small ciphertexts. There is definitly interest in Classic McEliece and I think it would be good to have a publicly available standard. If NIST standardizes Classic McEliece, I would like to see also security category 1-3 parameters and not just security category 5 as in the internet draft and the ISO specification.

 

I think the decision to standardize Classic McEliece is independent of the decision to standardize BIKE and HQC. BIKE and HQC are general purpose replacement for ML-KEM, Classic McEliece is not. I think NIST should standardize BIKE or HQC so that we have a general purpose replacement if any vulnerability is found in ML-KEM. (But note that I don't have any doubts about ML-KEM security. I recently suggested that NIST should standardize an Keccak based AEAD so that we have a NIST approved replacement if AES is broken).

 

Cheers,

John Preuß Mattsson

 

--

You received this message because you are subscribed to the Google Groups "pqc-forum" group.
To unsubscribe from this group and stop receiving emails from it, send an email to pqc-forum+...@list.nist.gov.

To view this discussion on the web visit https://groups.google.com/a/list.nist.gov/d/msgid/pqc-forum/837DF7AD-0066-482C-BDFF-CF8537A2BBFE%40thomwiggers.nl.

[D. J. Bernstein]

At first glance, the new encryption mechanism for Facebook Messenger
sounds like it's having each device upload a public key that's used
repeatedly. See, e.g., page 23 of

https://engineering.fb.com/wp-content/uploads/2023/12/TheLabyrinthEncryptedMessageStorageProtocol_12-6-2023.pdf

computing "epochEntropyEncrypted".

Right now this is using X25519, but I'm wondering whether this is
another example of an application where Classic McEliece is (1) easily
affordable and (2) the most efficient choice among post-quantum KEMs.
Has anyone found documentation on how short the epochs are, or, more to
the point, the overall volume of encapsulations etc.?

---D. J. Bernstein

[Daniel Apon]

Thanks Thom!

[Matthew Campagna]

NIST PQC Team,

I appreciate the conversation about use cases for McEliece. From a
top-level perspective, we don’t see any use cases for systems that
require forward secrecy to prefer McEliece over BIKE or ML-KEM. For
systems that don’t require forward secrecy, the only use cases we see
are ones in which there is a requirement that both the ciphertext and
the data to be encrypted are relatively small. Not too many use cases
come to mind, offline key escrow where storage or transmission is at a
premium.

Standardizing McEliece will likely cause undesirably complexity with
downstream specifications that use it. It may also encourage
developers to forgo providing forward secrecy at the prospects of
bandwidth benefits. We see this as a rollback in cryptographic
engineering practices.

Too many algorithm specifications adopted in different use-cases
usually does not help interoperability and code complexity. Use-cases
that absolutely need McEliece (we don't think they are many) could
still adopt the algorithm like TLS did for X25519 without it being a
NIST algorithm.

Regards,
Matt Campagna & Panos Kampanakis

On Wed, Nov 30, 2022 at 4:30 AM 'Moody, Dustin (Fed)' via pqc-forum

<pqc-...@list.nist.gov> wrote:
>
> All,
>
> NIST is confident in the security of Classic McEliece and would be comfortable standardizing the submitted parameter sets (under a different claimed security strength in some cases). However, it is unclear whether Classic McEliece represents the best option for enough applications to justify standardizing it at this time. For genera lpurpose systems wishing to base their security on codes rather than lattices, BIKE or HQC may represent a more attractive option.
>

> NIST would like feedback on specific use cases for which Classic McEliece would be a good solution.
>

> Thank you,
>
> NIST PQC team
>

> --
> You received this message because you are subscribed to the Google Groups "pqc-forum" group.
> To unsubscribe from this group and stop receiving emails from it, send an email to pqc-forum+...@list.nist.gov.

> To view this discussion on the web visit https://groups.google.com/a/list.nist.gov/d/msgid/pqc-forum/SA1PR09MB86692928B933935B57535F57E5159%40SA1PR09MB8669.namprd09.prod.outlook.com.