hybrid mode and the issues it raises

[Vadim Lyubashevsky]

Dear all,

At the industry panel of the 2nd NIST PQC conference, there seemed to have been a consensus agreement that a hybrid mode (in which a post-quantum scheme is combined with an EC scheme so that the resulting scheme is at least as classically secure as the EC one) should be the default option for the foreseeable future.  And I don't think anyone disagreed and it seemed like NIST actually wanted the community to go ahead and agree on a combiner for the hybrid.  If we seriously start considering hybrid modes (and I think we should), then I think that this is a game-changer for the standardization process in at least three ways (they are kind of obvious, but haven't been discussed at the conference):

1. Reasoning for the definitions of the NIST security levels.  NIST security level 5, for example, is defined as being at least as hard as AES, quantumly and classically.  This, as I understand it, means to be 128-bit secure quantumly and 256-bit secure classically.  All submissions have some gap between their quantum and classical securities, but it's never as large as that of AES.  Lattice schemes, for example, have security gaps of just a dozen or so bits.  So to claim level 5, schemes set parameters to be 256-bit secure classically.  But someone clever/sneaky could have done the following: constructed a scheme that was only 128-bit quantum secure and then used it in hybrid mode with a 512-bit EC scheme (ECDH or ECDSA).  At the cost of 64 bytes in the public key and output, which is much less that what one would need to add to achieve 256-bit classical security with just the post-quantum scheme, one gets level 5.  As an example, if I look at our CRYSTALS-Dilithium signature scheme, this trick gets us from Level 2 to Level 5 virtually for free (size-wise). 

I don't think anyone did this (or did they?) possibly because this is against the spirit of what we're trying to do, which is to create a secure standalone scheme. But if the hybrid mode is the default option and its purpose is exactly to provide classical security, then why should we care about the classical security of our post-quantum algorithms?  I would suggest that for the third round, a better way to measure the submissions is to only concentrate on the quantum hardness and to ask for, e.g. 96, 128, 160, 192 bits of quantum security.  The only reason I see for also asking for classical hardness of the submissions is if we don't have faith in the classical hardness of EC primitives ... but I don't know what the feelings of people are there. 

2. Early standardization of "safe" primitives.  There was also some discussion about standardizing a scheme that's not too efficient, but in which we have a lot of confidence.  If we talk about KEMs, then if someone asked me what's the KEM that I trust most, without hesitation I'd pick the pure-LWE "Frodo" (and I will not argue much if someone says McEliece).  Personally, I have more faith in the classical security of that scheme than in RSA.  So clearly, I should vote that we should standardize that one first, right? But ... if we're allowing for hybrids, then at half the size of one Frodo key exchange, I can do e.g. Kyber+NTRUPrime+Rollo+SIKE (the latter makes things slower, so leave it out if you wish)+some other code-based scheme.  This hybrid is smaller than Frodo and I now have more confidence in the security of (at least) one of the primitives comprising it than in the security of just Frodo.  I think it was Scott Fluhrer who remarked that he thinks McEliece and  SPHINCS+  will be standardized, but will never be used (because of their inefficiency).  So if we consider hybrids, is there still a reason to standardize a KEM that is much less efficient than a combination of more compact KEMs based on different assumptions (this is not a rhetorical question)?  Why not standardize efficient KEMs which we will only use in hybrid mode for a while, and then perhaps remove some as time progresses if we're confident in the security of the remaining ones.  Of course we should also have some efficient stand-alone schemes in which we are confident for situations where the device is not powerful enough to run the whole hybrid and has to rely on just one scheme.  With SPHINCS+ (and Picnic), the situation is different since they are based on the security of symmetric primitives -- so arguably no combination of mathematical assumptions is going to give us more confidence in the security of the resulting signature.  

3. (Not) standardizing untested submissions.  Some of the entrants remaining in the second round are based on rather new assumptions - e.g. the compact code-based schemes or the multivariate LUOV signature.  It seems unlikely to me that any of these could get standardized as stand-alone schemes if the process were to end in the next few years.  But maybe it still makes sense to use them in hybrid mode with other schemes that are more tested.  Adding them may provide added security as in the example above.

I would be very curious to hear NISTs and the community's opinions about these (or maybe other) effects of including a hybrid mode on the standardization process. 

Thanks (if you read this far :) ),

Vadim

[Perlner, Ray (Fed)]

Hi Vadim,

 

Regarding your consideration 1: I don’t believe we would rate a hybrid of a category 2 postquantum scheme and a 256-bit classically secure scheme as meeting category 5 postquantum security. First of all, it does not protect nearly as well as a category 5 scheme against a scenario where quantum computers advance to the point where they can just barely do Shor’s algorithm on cryptographically interesting targets, but classical computers advance to the point where they can realistically do  2^128 AES operations. Moreover, even ignoring the entirely plausible possibility that quantum operations may turn out to always be significantly more expensive than the equivalent classical operations, category 5 places a higher requirement on quantum security than category 2, not just classical. This is due to the parallelism issue which is noted in our call for proposals:

 

“It is worth noting that the security categories based on these reference primitives provide substantially more quantum security than a naïve analysis might suggest. For example, categories 1, 3 and 5 are defined in terms of block ciphers, which can be broken using Grover’s algorithm, with a quadratic quantum speedup. But Grover’s algorithm requires a long-running serial computation, which is difficult to implement in practice. In a realistic attack, one has to run many smaller instances of the algorithm in parallel, which makes the quantum speedup less dramatic.”

 

Rather, I would see the value of hybridizing a postquantum scheme with ECC as protection in the scenario where quantum computers completely fizzle, but there is a major advance in the cryptanalysis of the postquantum scheme. This would not be reflected in the security strength categories as it’s very difficult to numerically capture the risk of unknown cryptanalytic advances even in a coarse grained scale like our 5 security strength categories.

 

This brings us to your consideration 2: I see combinations like the one described in your consideration 2 as providing value in much the same way, for the case where quantum computers don’t completely fizzle. These combinations would only require one of the component algorithms to be FIPS Approved in order to be permissible under FIPS, (and it should already be possible to get FIPS approval for such a combination if it also includes something NIST has already approved like ECDH.)  So nothing NIST is planning to do should prevent the use of these diverse hybrid cryptosystems. Nonetheless, it would be interesting to hear community feedback about whether NIST should do something more than the minimum we’ve promised (at least one standard each for a postquantum PKE/KEM and a postquantum signature) to actively encourage the use of more diverse hybrid modes.

--
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/CAE158z_E7UZEacORoJZJrZLvZ8Jsip%2B731eW%2Be%2BvgerTykzk%3Dg%40mail.gmail.com.

[Chen, Lily (Fed)]

I agree with Ray. The hybrid shall target on a clear security goal. I like to clarify a few things about hybrid mode.

 

1. FIPS 140 validation only validates NIST “approved” primitives, that is, those specified in FIPS or SP, not a protocol or a combination.
2. The current key derivation as in SP 800-56A and SP 800-56B can accommodate additional “shared secrets”, for example, in one-step key derivation in the input field of “SuppPrivInfo” H(Z, ...|| ....|SuppPriveInfo), where Z = g^xy in Diffie-Hellman situation. We are looking at options to  explicitly define Z = Z_1||Z_2 (or more shared secrets or more methods to combine them), where Z_1 is the output of the “approved” while Z_2 is from some other schemes to accommodate hybrid mode. Currently, in 56A we have specification of a combination of ephemeral DH and static DH where Z = Z_1||Z_2.

 

People from CMVP testing Labs and also from vendors often approached us to ask different variations. I am sure that hybrid mode will introduce more interesting variations. But for interoperability and simplicity, we probably have to limit the options to hybridizing different schemes. 

 

Lily

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

[D. J. Bernstein]

Focusing on one part of Vadim's interesting message, namely the part
about whether it makes sense to standardize "big" systems.

Vadim Lyubashevsky writes:
> This hybrid is smaller than Frodo and I now have more confidence in
> the security of (at least) one of the primitives comprising it than in
> the security of just Frodo.

This is an important type of argument to consider. If Vadim's hybrid of
four small submissions is (1) more efficient than Frodo and (2) less
risky than Frodo, then why should users consider Frodo?

The Frodo team could try to respond to Vadim's argument here by

(1) explaining why an important application needs very small code,
(2) showing that Frodo fits within this limit, and
(3) saying that Vadim's hybrid surely doesn't fit within this limit.

More abstractly, this response is trying to

* choose an efficiency metric where Vadim's hybrid is worse than
Frodo (code size is an obvious choice of metric where everyone will
expect hybrids to do badly), and

* choose an application where this inefficiency is a problem for
Vadim's hybrid (I'd be interested in seeing real-world data points
regarding actual application limits on code size).

On the other hand, Vadim didn't have to take a hybrid for his argument.
What happens if frodokem1344 is worse than a simple kyber2048 parameter
set in size and cycles and risk level? Surely hybrids will do badly in
code size, but we're no longer talking about a hybrid. I see

https://github.com/mupq/pqm4/blob/master/benchmarks.md

reporting kyber1024 fitting under 6KB of code, smaller than the smallest
reported frodokem640 implementation. I don't think these implementations
are optimized for size, and I wouldn't be surprised if Frodo can be
squeezed into slightly less code than Kyber, but it'll be hard to find
applications where this small difference matters.

(Of course the Frodo team can also try to argue that the assessment of
risk levels is wrong---that a feasible attack against kyber2048 or
against a hybrid of smaller systems is more likely than a feasible
attack against frodokem1344. This type of question is important to
analyze, but I won't dive into the details here; my main goal in this
message is to highlight other assumptions implicit in Vadim's argument.)

Vadim puts Classic McEliece into the same bucket as Frodo---but we don't
need to consider code size to see that the switch from Frodo to McEliece
breaks Vadim's efficiency argument (never mind the risk argument):

* It's not true that his hybrid is more efficient than McEliece.
* It's not true that kyber2048 would be more efficient than McEliece.
* It's not even true that kyber512 is more efficient than
mceliece6960119.

Here are the numbers:

* kyber512: 736 bytes of ciphertext.
* mceliece6960119: 226 bytes of ciphertext (3x more efficient).

Obviously the difference between what I'm saying here and what Vadim is
saying is that I'm measuring ciphertext size while Vadim is measuring
key size. Does someone have an argument that key size is more important
than ciphertext size for applications?

Google's post-quantum experiments sent one key per ciphertext---but
applications that care about the crypto communication cost obviously
won't be designed that way. David McGrew's 2015 talk

https://csrc.nist.gov/csrc/media/events/workshop-on-cybersecurity-in-a-post-quantum-world/documents/presentations/session4-mcgrew-david.pdf

gives examples of how to use standard networking techniques to
drastically reduce the costs of communicating large keys. I would expect
the real communication costs to scale as ciphertext size plus a _very
small fraction_ of key size, with this fraction decreasing as the
network grows (see below). If the fraction is 1/2^12 then kyber512
(which struggles to claim category 1: it's pre-quantum Core-SVP 2^111)
has higher communication costs than mceliece6960119 (category 5).

(There's also a fairly straightforward argument that something like
kyber2048 would still have higher risks than mceliece6960119; but,
again, my goal in this message is to highlight other issues.)

> I think it was Scott Fluhrer who remarked that he thinks McEliece and 
> SPHINCS+  will be standardized, but will never be used (because of
> their inefficiency).

I think we should leave it to Scott to put his actual position into
writing if he wants to do so. More to the point, NIST should disregard
claims (from whatever source) that aren't justified. I don't see an
argument stated or cited for the claim that "inefficiency" will stop
"McEliece and SPHINCS+" from being used. I have trouble seeing how such
an argument could be made even if it were narrowed to just McEliece:

* There have already been some deployed applications using McEliece,
so any broad impossibility argument is clearly wrong.

* One could try arguing that the key size is a showstopper for _some_
applications. However, this doesn't stop McEliece from being the
top encryption choice for applications that prioritize risk
reduction, and for applications that prioritize small ciphertexts.

* One could try arguing that applications will always prioritize key
size over both (1) risk reduction and (2) ciphertext size, and will
thus avoid McEliece unless and until all of the smaller-key schemes
are broken. But how would an argument of this type explain all the
people using, e.g., 256-bit curves rather than smaller curves? Why
would hyping the key size make sense for applications where most of
the cryptographic bandwidth is being used by ciphertexts?

It's also important to think about which performance-related arguments
will be obsolete in five or ten years---and which arguments are using
old cost models that are already obsolete today!

Sandvine reported in October 2018 that video has increased to 58% of
downstream Internet traffic, while general web traffic is only 17%:

https://www.sandvine.com/hubfs/downloads/phenomena/2018-phenomena-report.pdf

Meanwhile the median web page has reached almost 2MB, and the average is
larger:

https://httparchive.org/reports/state-of-the-web#bytesTotal

A web page can involve multiple public keys, but a key is often reused
for many pages. If the average number of keys retrieved per page is,
say, 0.1, and we add 1MB to upgrade _every_ key for _every_ page to
Classic McEliece, then the total increase in Internet traffic is around
0.8%. For comparison,

https://www.ktm2day.com/2018/12/24/cisco-predicts-tremendous-internet-traffic-growth-over-the-next-5-years/

predicts more than 20% traffic growth per year in every region of the
world. It also predicts further dominance of video traffic; this will
drive the 0.8% figure even lower. Furthermore, it's clearly feasible to
retrieve almost all keys from nearby caches, as in McGrew's talk, and
then the actual increase in communication cost will be even smaller.

The numbers show an explosion in the amount of data that the users of
any given ISP are downloading in any given period of (say) 10 minutes.
This is what's driving increases in the ISP's bandwidth. Meanwhile,
there _isn't_ a corresponding explosion in the number of sites that the
ISP's users are communicating with during the same 10-minute period---
and this number of sites is fundamentally what matters for the number of
public keys that need to be communicated to this ISP. Two notes
regarding details:

* I'm setting a goal here of erasing public keys within 10 minutes
for forward secrecy. For comparison, Langley aimed for "once a day"
in https://www.imperialviolet.org/2013/06/27/botchingpfs.html and
explained that TLS implementations would often keep keys for "many
months". If a 1-day key lifetime is acceptable then local caching
will be even more effective, and key size will matter even less. I
think that aiming for the scale of minutes is better.

* Instead of having the ISP download a 10-minute key from each site,
one can have each user upload a 10-minute key for all sites to use.
See McGrew's talk. This can be more efficient than downloads, but
I'll stick to the download case for simplicity.

The number of _ciphertexts_ communicated by the ISP is a different
story. For each site, each user needs a new ciphertext communicated end
to end to set up a session key. Thousands of users of this ISP who talk
to Google during this 10-minute period can happily download the same
10-minute Google public key through an ISP cache, but each user has to
send Google a separate ciphertext under that key. The cryptographic data
communicated between Google and the ISP is then

* one key plus
* thousands of ciphertexts.

Plugging McEliece into this straightforward network architecture
produces _less_ cryptographic traffic than any proposed lattice-based
solution. Surely people who claim to care about network traffic should
support McEliece for this reason. McEliece isn't big---it's small!

---Dan

[Vadim Lyubashevsky]

Hi Ray,

First of all, it does not protect nearly as well as a category 5 scheme against a scenario where quantum computers advance to the point where they can just barely do Shor’s algorithm on cryptographically interesting targets, but classical computers advance to the point where they can realistically do  2^128 AES operations. 

Thanks for the clarification.  While I still think that quantum security is the main thing that we should be caring about in a world where quantum computers can be scaled enough that Shor's algorithm is implementable, I see your point about 128-bit hard quantum + 256-bit classically-hard ECC not being of the same complexity as AES-256 in certain scenarios.   

 

This brings us to your consideration 2: I see combinations like the one described in your consideration 2 as providing value in much the same way, for the case where quantum computers don’t completely fizzle. These combinations would only require one of the component algorithms to be FIPS Approved in order to be permissible under FIPS, (and it should already be possible to get FIPS approval for such a combination if it also includes something NIST has already approved like ECDH.)  So nothing NIST is planning to do should prevent the use of these diverse hybrid cryptosystems.

Sure, after NIST creates a standard, one should be able to use it in a hybrid with whatever else she wishes.  My comment was more in reference to some requests for NIST to speed-up the standardization of certain schemes that are deemed more secure (but may be less efficient).  My point is that this is unnecessary because taking a hybrid of three future efficient round 3 KEMs should be more secure than any one scheme that NIST chooses to standardize early.  So no rushing is necessary if the goal is security.

If one still wants to see McEliece standardized, it should only be because they are happy with the ciphertext/public key trade-off (I have no opinion as to Dan's argument -- the people deploying these schemes should weigh in regarding it); and not due to a sense of higher security.  

One other case for Frodo that I see is that with respect to *quantum* cryptanalysis, lattice schemes have almost certainly received the most attention so far.  But still, I believe that hybrids of several post-quantum schemes provide/will provide the most security because the communities that work on lattices/codes/isogenies are almost entirely disjoint -- so this is the only way to have the entire post-quantum community meaningfully looking at the hardness of the scheme.

At the end of the NIST process (hopefully ending no sooner than 2024), we will want to gain enough confidence in one "small" scheme because this will be important for low-cost devices.  But until then, if one wants quantum security and doesn't care too much about the cost, I would simply advocate the hybrid approach.

Best regards,

Vadim

 

Nonetheless, it would be interesting to hear community feedback about whether NIST should do something more than the minimum we’ve promised (at least one standard each for a postquantum PKE/KEM and a postquantum signature) to actively encourage the use of more diverse hybrid modes.

 

From: Vadim Lyubashevsky <vadim....@gmail.com>
Sent: Wednesday, August 28, 2019 1:59 PM
To: pqc-forum <pqc-...@list.nist.gov>
Subject: [pqc-forum] hybrid mode and the issues it raises

 

Dear all,

 

At the industry panel of the 2nd NIST PQC conference, there seemed to have been a consensus agreement that a hybrid mode (in which a post-quantum scheme is combined with an EC scheme so that the resulting scheme is at least as classically secure as the EC one) should be the default option for the foreseeable future.  And I don't think anyone disagreed and it seemed like NIST actually wanted the community to go ahead and agree on a combiner for the hybrid.  If we seriously start considering hybrid modes (and I think we should), then I think that this is a game-changer for the standardization process in at least three ways (they are kind of obvious, but haven't been discussed at the conference):

 

1. Reasoning for the definitions of the NIST security levels.  NIST security level 5, for example, is defined as being at least as hard as AES, quantumly and classically.  This, as I understand it, means to be 128-bit secure quantumly and 256-bit secure classically.  All submissions have some gap between their quantum and classical securities, but it's never as large as that of AES.  Lattice schemes, for example, have security gaps of just a dozen or so bits.  So to claim level 5, schemes set parameters to be 256-bit secure classically.  But someone clever/sneaky could have done the following: constructed a scheme that was only 128-bit quantum secure and then used it in hybrid mode with a 512-bit EC scheme (ECDH or ECDSA).  At the cost of 64 bytes in the public key and output, which is much less that what one would need to add to achieve 256-bit classical security with just the post-quantum scheme, one gets level 5.  As an example, if I look at our CRYSTALS-Dilithium signature scheme, this trick gets us from Level 2 to Level 5 virtually for free (size-wise). 

 

I don't think anyone did this (or did they?) possibly because this is against the spirit of what we're trying to do, which is to create a secure standalone scheme. But if the hybrid mode is the default option and its purpose is exactly to provide classical security, then why should we care about the classical security of our post-quantum algorithms?  I would suggest that for the third round, a better way to measure the submissions is to only concentrate on the quantum hardness and to ask for, e.g. 96, 128, 160, 192 bits of quantum security.  The only reason I see for also asking for classical hardness of the submissions is if we don't have faith in the classical hardness of EC primitives ... but I don't know what the feelings of people are there. 

 

2. Early standardization of "safe" primitives.  There was also some discussion about standardizing a scheme that's not too efficient, but in which we have a lot of confidence.  If we talk about KEMs, then if someone asked me what's the KEM that I trust most, without hesitation I'd pick the pure-LWE "Frodo" (and I will not argue much if someone says McEliece).  Personally, I have more faith in the classical security of that scheme than in RSA.  So clearly, I should vote that we should standardize that one first, right? But ... if we're allowing for hybrids, then at half the size of one Frodo key exchange, I can do e.g. Kyber+NTRUPrime+Rollo+SIKE (the latter makes things slower, so leave it out if you wish)+some other code-based scheme.  This hybrid is smaller than Frodo and I now have more confidence in the security of (at least) one of the primitives comprising it than in the security of just Frodo.  I think it was Scott Fluhrer who remarked that he thinks McEliece and  SPHINCS+  will be standardized, but will never be used (because of their inefficiency).  So if we consider hybrids, is there still a reason to standardize a KEM that is much less efficient than a combination of more compact KEMs based on different assumptions (this is not a rhetorical question)?  Why not standardize efficient KEMs which we will only use in hybrid mode for a while, and then perhaps remove some as time progresses if we're confident in the security of the remaining ones.  Of course we should also have some efficient stand-alone schemes in which we are confident for situations where the device is not powerful enough to run the whole hybrid and has to rely on just one scheme.  With SPHINCS+ (and Picnic), the situation is different since they are based on the security of symmetric primitives -- so arguably no combination of mathematical assumptions is going to give us more confidence in the security of the resulting signature.  

 

3. (Not) standardizing untested submissions.  Some of the entrants remaining in the second round are based on rather new assumptions - e.g. the compact code-based schemes or the multivariate LUOV signature.  It seems unlikely to me that any of these could get standardized as stand-alone schemes if the process were to end in the next few years.  But maybe it still makes sense to use them in hybrid mode with other schemes that are more tested.  Adding them may provide added security as in the example above.

 

I would be very curious to hear NISTs and the community's opinions about these (or maybe other) effects of including a hybrid mode on the standardization process. 

 

Thanks (if you read this far :) ),

 

Vadim

--
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/CAE158z_E7UZEacORoJZJrZLvZ8Jsip%2B731eW%2Be%2BvgerTykzk%3Dg%40mail.gmail.com.

--
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/BL0PR0901MB4164D13CAD005E73BA372A859CA30%40BL0PR0901MB4164.namprd09.prod.outlook.com.

[D. J. Bernstein]

Vadim Lyubashevsky writes:
> taking a hybrid of three future efficient round 3 KEMs should be more
> secure than any one scheme that NIST chooses to standardize early

Consider an application integrating mceliece6960119. Can you please name
specific parameter choices for three KEMs that you consider "efficient",
and spell out the details of why you think a hybrid of those three KEMs
with those parameter choices would be better than mceliece6960119?

Being concrete is an important step towards falsification. I expect that
followup analyses will show that your specific proposal simultaneously
increases costs _and_ risks for cryptographic users.

Right now someone who considers doing the work for a serious cost
comparison to a hybrid has to guess what exactly you have in mind, and
then has to worry that you'll respond "No, I meant a lower-cost hybrid
than what you're comparing to". Same for a serious risk comparison.

---Dan

[Vadim Lyubashevsky]

Hi Dan, all,

On Thu, Sep 5, 2019 at 9:22 PM D. J. Bernstein <d...@cr.yp.to> wrote:

Vadim Lyubashevsky writes:
> taking a hybrid of three future efficient round 3 KEMs should be more
> secure than any one scheme that NIST chooses to standardize early

Consider an application integrating mceliece6960119. Can you please name
specific parameter choices for three KEMs that you consider "efficient",
and spell out the details of why you think a hybrid of those three KEMs
with those parameter choices would be better than mceliece6960119?

Being concrete is an important step towards falsification. I expect that
followup analyses will show that your specific proposal simultaneously
increases costs _and_ risks for cryptographic users.

Sorry for the delayed response.   Anyone can look at the parameters for McEliece/Kyber/Frodo/SIKE/etc. and figure out whether they are happy with the public key/ciphertext /run-time trade-offs.  These numbers speak for themselves and I have nothing to add to the discussion between practitioners who will be potentially putting these schemes into use.   So if someone wants to use McEliece because they deem it optimal for their application, then fine.  But there are also many scenarios where using McEliece is not optimal, yet it feels to me that some people would still lean towards using it because of the often-perpetuated narrative that McEliece is the gold standard for post-quantum security.  The only point that I wanted to make is that I personally disagree with this, and especially so if one considers hybrids.

Sure, McEliece is as old as RSA, but its study has almost exclusively been confined to academia (and a niche area of academia, at that).  There is no precise way to measure how well something has been studied in academia, but citation count is probably the least crude metric that exists.  So here are RSA and some papers introducing various PQ schemes: 

1977. “A Method for Obtaining Digital Signatures and Public-Key Cryptosystems.” RSA – 23600 citations (4100 since 2015)
1978. McEliece . "A Public-Key Cryptosystem Based On Algebraic Coding Theory" – 1920 citations (666 since 2015)
1998. NTRU “NTRU: A Ring-Based Public Key Cryptosystem” – 1610 citations (624 since 2015)
2005. LWE “On lattices, learning with errors, random linear codes, and cryptography” – 2243 citations (1380 since 2015)
2010. Ring-LWE. “On ideal lattices and learning with errors over rings” – 1245 citations (876 since 2015)

Of course you may argue that the LWE paper didn’t have any concrete parameters, and so there wasn’t any possible cryptanalysis to speak of.  And it’s true, lattice cryptography (except for NTRU), developed from the “top-down”, meaning that people wanted to understand the general problem and the cryptosystems came as particular instantiations.  This method has many advantages, with the biggest, in my view, being that it attracts people from outside cryptography to work on cryptographically relevant problems.  There have indeed been some valuable and fundamental lattice algorithms / techniques developed by non-cryptography people.  Examples include the original sieving algorithm (Ajtai, Kumar, Sivakumar) which is now a core component for setting concrete parameters, the BKW algorithm (Blum, Kalai, Wasserman), and the Arora-Ge algorithm (Arora, Ge) which precludes certain parameter sets in symmetric-based LWE crypto.    

I think that keeping the cryptographic algorithms as general and natural as possible, and not just restricting to the parameters that optimize a cryptosystem, is an extremely valuable feature.  This is why, if we try to predict which scheme will receive the most scrutiny (even if indirect) if standardized, I would say LWE is the number one choice, Ring-LWE is next, Ring-LWR follows (rounding instead of adding errors is quite unnatural, and probably only cryptanalysts will be looking at that feature), then NTRU (Ring-LWE/LWR schemes can be used for advanced primitives, like FHE, whereas NTRU cannot since it is insecure in that parameter range; and a segment of the AI community is now starting to look at FHE) and McEliece.

And if we consider SIKE (which hasn’t been studied as extensively yet, but with the entire ECC research community seemingly working on it, in 5 - 10 years, it could become considered to be pretty well-studied), I would contend that a hybrid of Ring-LWE and SIKE should give people as much confidence as anything else in the near future.  

  

Best,

Vadim

[D. J. Bernstein]

Vadim, thanks for elaborating upon your security argument. Can you
please name a specific hybrid, including specific parameters,

* that you would recommend in place of mceliece6960119 and
* that you believe is supported by this security argument?

Again, I predict that the result of this will be followup analyses
showing that this hybrid increases costs _and_ risks.

Users deploy specific cryptosystems. The problem right now is a lack of
clarity: the reader can't figure out _which_ specific cryptosystems are
included in this security argument. If someone picks a specific hybrid
and then does the work for a serious analysis of costs and risks of that
hybrid, will you respond "No, I didn't mean _that_ hybrid"?

Surely you aren't arguing for the security of a NewHope-like system
using x^128+1. Where exactly is this excluded in the argument? What's
the boundary between the systems that are included and the systems that
are excluded? If you can't point to a specific cryptosystem and tell the
users "_This_ cryptosystem is supported by this security argument", then
what exactly _are_ you recommending?

---Dan

[Vadim Lyubashevsky]

On Tue, Oct 1, 2019 at 11:18 AM D. J. Bernstein <d...@cr.yp.to> wrote:

Vadim, thanks for elaborating upon your security argument. Can you
please name a specific hybrid, including specific parameters,

   * that you would recommend in place of mceliece6960119 and
   * that you believe is supported by this security argument?

Sure, let's take SIKEp751 + Kyber1024  (since, as I understand it, you say that the version of McEliece that you're proposing is ~ 256-bits hard).  

I am also fine if you put in the level 5 version of NTRU/NTRU(L)prime instead of Kyber.  I think that a pure Ring-LWE scheme (without the NTRU trapdoor) is bound to get more attention in the future than NTRU due to FHE applications, but for the purpose of just putting something up against McEliece, I am fine with those two as well. 

Or just take Frodo (level 5) straight up, in case SIKEp751 is too slow in some applications.

I know I also said that one could add a structured code-based scheme, but I don't know which one of those has the momentum for some consensus in that area.  So I am fine with just the above proposals for now. 

Again, I predict that the result of this will be followup analyses
showing that this hybrid increases costs _and_ risks.

Fine, but please note again: I am not saying that McEliece will be worse in *every* scenario -- I am merely saying that in the cases where very large public keys and/or slow key generation are a problem, there are other options which are clearly better in terms of costs.

Best,

Vadim

[D. J. Bernstein]

Vadim Lyubashevsky writes:
> Sure, let's take SIKEp751 + Kyber1024

Thanks. To make sure I have this straight: Your starting hybrid question
was whether there is "a reason to standardize a KEM that is much less

efficient than a combination of more compact KEMs based on different

assumptions". To be specific, you're now claiming that

* sikep751+kyber1024 would be more efficient (rather than less
efficient) than mceliece6960119, and that

* sikep751+kyber1024 would reduce risks (rather than increase risks)
compared to mceliece6960119, for the reasons explained in your
previous message.

Did I get that right? If there's a followup paper analyzing the costs
and risks of sikep751+kyber1024 vs. mceliece6960119, you won't say that
this paper is addressing the wrong question?

---Dan

[Vadim Lyubashevsky]

On Wed, Oct 2, 2019 at 9:32 AM D. J. Bernstein <d...@cr.yp.to> wrote:

Vadim Lyubashevsky writes:
> Sure, let's take SIKEp751 + Kyber1024

Thanks. To make sure I have this straight: Your starting hybrid question
was whether there is "a reason to standardize a KEM that is much less
efficient than a combination of more compact KEMs based on different
assumptions". To be specific, you're now claiming that

   * sikep751+kyber1024 would be more efficient (rather than less
     efficient) than mceliece6960119, and that

I am not making such a blanket statement.  If some scenario would really benefit from a short ciphertext and doesn't care about a very large public key, then McEliece is better.  I again emphasize that I am not arguing either for or against standardizing McEliece --  my only point is that if McEliece, or any other scheme, is to be used in some scenario, it should be only on the merits of its efficiency.  Because when you start considering risk, there exist other (combinations of) schemes which have received (or will soon receive) even more vetting.   

   * sikep751+kyber1024 would reduce risks (rather than increase risks)
     compared to mceliece6960119, for the reasons explained in your
     previous message.

Right.  More precisely, I am guessing that by the time PQ standards will be set, the (combined) foundations of these two schemes will have been vetted at least as much as McEliece, and due to the practical usefulness of lattices in other applications (isogeny crypto, too, is now finding applications other than encryption), the gap between them and McEliece will grow even wider.  

 

Did I get that right? If there's a followup paper analyzing the costs
and risks of sikep751+kyber1024 vs. mceliece6960119, you won't say that
this paper is addressing the wrong question?

If there is a follow-up paper that breaks SIKE or kyber, I promise not to say that it's addressing the wrong question. 

Best,

Vadim

 

---Dan

--
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/20191002073238.28361.qmail%40cr.yp.to.

[Gregory Maxwell]

On Thursday, August 29, 2019 at 11:00:26 PM UTC, D. J. Bernstein wrote:

A web page can involve multiple public keys, but a key is often reused
for many pages. If the average number of keys retrieved per page is,
say, 0.1, and we add 1MB to upgrade _every_ key for _every_ page to
Classic McEliece, then the total increase in Internet traffic is around
0.8%. For comparison,

[...]

The number of _ciphertexts_ communicated by the ISP is a different
story. For each site, each user needs a new ciphertext communicated end
to end to set up a session key. Thousands of users of this ISP who talk
to Google during this 10-minute period can happily download the same
10-minute Google public key through an ISP cache, but each user has to
send Google a separate ciphertext under that key. The cryptographic data
communicated between Google and the ISP is then

   * one key plus
   * thousands of ciphertexts.

I am having a difficult time following this argument, which appears to assume that public keys (and the concomitant secret keys, with temporary reduction of PFS) can be cached but that symmetric session keying material cannot be cached.   If session keying is cached, then all asymmetric schemes are asymptotically equivalently performant under the assumption that new relationships are infrequent.

This argument also assumes that there is ISP level caching of provider public keys (e.g. as part of DNS records, or similar) -- but that kind of public caching is not particularly compatible with users keeping their communications metadata private.

In general, the assumption of a model where users communicate with a small number of very large providers (like google, cloudflare, etc) makes a fairly strong assumption of a rather centralized internet. I agree that this sort of communication pattern is currently common, I don't think it follows that its a good idea to adopt cryptosystems that will create strong financial advantages for that sort of centralization, especially since the introduction of choke points is itself toxic to user security--  what is the point of practically unbreakable cryptography when as a side effect traffic is economically forced through a small number of parties which can be compromised via non-cryptographic means?

I believe that for forward secure ephemeral keying the only important communication cost for optimization is the one pubkey + one ciphertext cost.  If pubkeys can be frequently reused, then session keys can be reused, making the entire asymmetric cost largely irrelevant.  Even in cases where the pubkey cost can be reasonably divided by a small number, the worst case cost-- which often drives provisioning-- is still 1pubkey/1ciphertext making it a worthwhile objective.

For non forward-secure applications, like stored message encryption optimizing for cyphertext size makes a lot more sense. But applications like email encryption are wildly different optimization targets, in general with tolerable amounts of computation and communication being an order of magnitude higher than applications like connection encryption (as demonstrated by people happily using 4096 bit RSA with PGP with little complaint about space or time, other than perhaps key generation).

[D. J. Bernstein]

Gregory Maxwell writes:
> I am having a difficult time following this argument

Happy to spell it out in more detail. Here's Google's link to your local
ISP, and your local ISP's link to you:

Google ------------------------------------------------- ISP ---- you

You're one of, say, 1000 users of this ISP talking to Google over the
next minute. Here's a space-time visualization of the network links:

Google ------------------------------------------------- ISP ---- 000
Google ------------------------------------------------- ISP ---- 001
...
Google ------------------------------------------------- ISP ---- 999

Here's Google's public key being sent to all of these users, with simple
caching at the ISP:

Google -PK-PK-PK-PK-PK-PK-PK-PK-PK-PK-PK-PK-PK-PK-PK-PK- ISP -PK- 000
Google ------------------------------------------------- ISP -PK- 001
...
Google ------------------------------------------------- ISP -PK- 999

Here are the same users sending their ciphertexts back to Google:

Google -CT-CT-CT-CT-CT-CT-CT-CT-CT-CT-CT-CT-CT-CT-CT-CT- ISP -CT- 000
Google -CT-CT-CT-CT-CT-CT-CT-CT-CT-CT-CT-CT-CT-CT-CT-CT- ISP -CT- 001
...
Google -CT-CT-CT-CT-CT-CT-CT-CT-CT-CT-CT-CT-CT-CT-CT-CT- ISP -CT- 999

See how the PK transmission costs are shared by the users? Any serious
assessment of costs will give a PK byte lower weight than a CT byte.

> I believe that for forward secure ephemeral keying the only important
> communication cost for optimization is the one pubkey + one ciphertext
> cost. If pubkeys can be frequently reused, then session keys can be
> reused

You're looking at reuse of computations within one user's machine, but
that's not the main cost here. You have to look at which bytes are being
sent through which network links.

[ the argument above ]

> appears to assume that public keys (and the concomitant secret keys,
> with temporary reduction of PFS) can be cached

Yes, this is what "download the same 10-minute Google public key through
an ISP cache" means. (The ISP doesn't even need new caching software if
clients retrieve keys from DNS records.) As a side note, calling this a
"reduction" of "PFS" is backwards; see my previous comments comparing
this 10-minute goal to the 1-day goal in Adam Langley's blog post.

> but that symmetric session keying material cannot be cached

No, there's no such assumption in the argument. Each of the 1000 users
is using a normal hybrid of public-key crypto and symmetric crypto. Of
course symmetric crypto is applied to much more data than public-key
crypto is, and any serious assessment of costs will take this into
account, the same way that any serious assessment of costs will take
into account the difference in communication patterns between public
keys and ciphertexts.

> If session keying is cached, then all asymmetric schemes are
> asymptotically equivalently performant under the assumption that new
> relationships are infrequent.

Increases in data volume obviously tend to put even more weight on
symmetric crypto. I've written here before about "the difference between
looking at cryptographic costs in isolation and looking at them as part
of the total costs of the application", and I've put serious work into
quantifying examples.

There are nevertheless people trying to hype particular aspects of
public-key performance, maintaining a drumbeat of comments along the
lines of "A MEGABYTE? ARE YOU INSANE?" and apparently not even
understanding how the cost of larger keys can be outweighed by the
benefit of smaller ciphertexts. Understanding the right weights requires
analyzing network communication patterns---and saying that both weights
are zero "asymptotically" doesn't help with this quantification.

> This argument also assumes that there is ISP level caching of provider
> public keys (e.g. as part of DNS records, or similar) -- but that kind
> of public caching is not particularly compatible with users keeping
> their communications metadata private.

Do you have a basis for this incompatibility claim?

As far as I know, the best metadata protection we know how to achieve
comes from broadcast networks. An attacker can't tell which pieces (or
even how many pieces!) of locally stored data a node is accessing.

People building broadcast networks try to _publicly_ cache data on as
many nodes as possible, so that each node obtains data via a cheap link
from a nearby node. This is perfectly compatible with the metadata
protection described in the previous paragraph.

The extra cost of a broadcast, compared to the cost of sending data only
to the nodes that request it, depends on how many nodes would have been
requesting the data anyway. For example, a huge number of people want to
see Google's 10-minute key, the latest news story, etc., whereas very
few people want to see _your_ ciphertext.

The same basic cost issues are visible on a smaller scale in anonymity
systems that have less ambitious security goals. As the total usage
increases, it becomes more and more attractive to broadcast each node's
ephemeral public keys throughout the network.

> In general, the assumption of a model where users communicate with a
> small number of very large providers (like google, cloudflare, etc)
> makes a fairly strong assumption of a rather centralized internet. I
> agree that this sort of communication pattern is currently common, I
> don't think it follows that its a good idea to adopt cryptosystems that
> will create strong financial advantages for that sort of centralization,
> especially since the introduction of choke points is itself toxic to

> user security--what is the point of practically unbreakable

> cryptography when as a side effect traffic is economically forced
> through a small number of parties which can be compromised via
> non-cryptographic means?

Let me get this straight. You think that adopting McEliece with 1MB
public keys will create "strong financial advantages" for "choke points"
and "centralization" on the Internet, so users are suddenly "forced" to
use central services such as Google and Wikipedia? Wow. I didn't realize
that the tail had so much power to wag the dog. How much money is this
cryptographic "strong financial advantage" supposed to be?

Meanwhile, a few paragraphs earlier, you said that "all asymmetric

schemes are asymptotically equivalently performant under the assumption

that new relationships are infrequent"---which sounds to me like you're
acknowledging that Alice and Bob can rely on symmetric crypto for their
communication after just 1MB for key exchange. If Alice and Bob are
communicating, say, 30MB of data then why do they care about the 1MB? If
they're communicating under 30MB of data then why do they care about the
costs at all? How many (Alice,Bob) pairs do you think there are?

Cisco says that the Internet sends more than 1000000000000000000000
bytes of data each year---i.e., hundreds of thousands of megabytes per
user---and that this figure is rapidly growing. How many people do you
think you're communicating secretly with?

> the worst case cost-- which often drives provisioning-- is still
> 1pubkey/1ciphertext making it a worthwhile objective.

I agree that there are scenarios that look at worst-case costs:
real-time systems look at maximum processing times, for example, and
Internet services do their best to handle DDoS floods. However, I'm
unable to figure out how these scenarios justify looking at the total
bandwidth of 1 public key and 1 ciphertext.

For comparison, it's clear how the NewHope experiment sent (under normal
operation) 1 ephemeral public key and 1 ciphertext through each network
link. It's also clear that, as I wrote before, applications that care
about the crypto communication cost won't be designed this way.

---Dan

[Mike Hamburg]

Hi Dan,

I’m also having a hard time following your argument.  For what it’s worth, I think it is potentially worth standardizing “big” systems for use cases where online key exchange is rare (email, maybe).  But I don’t see the case for using them in TLS on the web.

As I understand it, you are suggesting a scenario where websites’ public keys (which I will take as 1MB McEliece class-5 public keys; the impacts will be less but still significant for the 260kB class-1 keys) will be cached for up to 10 minutes (the forward secrecy window) at each ISP.  When Alice visits that site, if she has visited it within that same window, then she will have a cached session key.  Otherwise, she will get the public key key from the ISP, where it will query a broadcast-fed cache.  Normally, Alice would miss cache if she were the first user on that ISP to visit that site recently, but let’s suppose that usually she is not and/or that the cache gets most of the public key on the internet.  So usually she hits the ISP cache, but either way, Alice never caches the public key locally.  She either uses a cached session key or fetches the public key.

When the cache hits, this will save all but the last link in latency, bandwidth, energy etc.  But the last link is the most expensive per bit in all these metrics, especially if Alice is on a cell phone.  I really don’t see the ISP cache saving more than, say, 80% of the cost (latency, bandwidth, energy, infrastructure, whatever) of the load vs only session resumption, especially if it doesn’t always hit, but if you have better numbers feel free to correct this.

So now, under an architecture that’s designed explicitly to mitigate the cost of large public keys — one that we probably wouldn’t bother rolling out if a “small” scheme were used — we should be comparing the size of 1 public key + 5 ciphertexts, right?  Because for every key exchange, the links that transport the public key use only 1/5th the energy or other costs of the ones that transport the ciphertext?  That’s obviously more favorable than 1+1, but McEliece still isn’t going to beat Kyber or even Frodo in that comparison.  In other words, the cost of the large public keys is not outweighed by savings of the smaller ciphertexts.

Certainly we could additionally consider extending the broadcast mechanism to the last hop too.  But at least in cell phones we’re now talking about significant modifications to the physical and MAC layers around large public keys, and possibly significantly increasing receive energy costs, in addition to transport- and application-layer workarounds.  Even if this is feasible, it will considerably hinder deployment.

Now let’s consider page load times.  It’s well and good that large public keys won’t much affect streaming video services like Netflix that use the bulk of the bandwidth, but they will affect webpages.  As of 2017, according to Akamai, the mean (not even median!) US internet speed was 18.7 megabit [1], which would mean that loading a new page costs 420ms *per handshake* just for the 1MB public key.  This is for the last hop, so the ISP cache won’t reduce it beyond that.  Currently sites use prefetch to mitigate per-site latency costs, but that only works well for things that are latency-limited, not bandwidth-limited.  If the page has any cross-domain data on it, this cost will increase further.  I’m not sure by how much, because a pretty good fraction of cross-domain data goes to the same, say, hundred ad servers, JS library hosts, CDNs and trackers, so most but not all will have a cached session key.  This is, of course, outside the first few pages of a web browsing session, which will each take several seconds to load.  A minor annoyance to be sure, but an annoyance nonetheless.

Also in 2017, a different Akamai study [2] found that a 100ms delay hurts conversion rates by 7%, and a 2-second delay increases bounce rates by 100%.  To the extent that this is linear, we’re talking about a 30% conversion rate drop and 20% bounce rate increase *per domain involved*.  This is the financial incentive to centralized hosting, and even centralized crypto where many domains share keypairs within a cloud host.  In other words, 1MB public keys might make the goals of network neutrality — that small sites can have nearly the same QoS as larger ones — infeasible, even if the rest of the network were neutral.

On the plus side, it will also be cost-prohibitive to add 30 cross-domain trackers to every page, and people will have better incentives not to check their phones 52 times a day.  Also, internet speeds have surely increased since 2017 and will increase more by the time we need this, which will reduce load times and cost.  Then again, the US is a developed nation, albeit one with mediocre internet speeds.  The numbers will surely be worse in, say, India, possibly even in 2030.

Overall, I agree that a 1:1 cost doesn’t capture what can be accomplished with careful network engineering, and that a 1MB public key isn’t outright insane.  But McEliece is still much more expensive in reasonable scenarios, and this expense will make building a network on top of it significantly more costly and less useful than with a “small” system.

Regards,

— Mike

[1] https://www.akamai.com/us/en/multimedia/documents/state-of-the-internet/q1-2017-state-of-the-internet-connectivity-report.pdf

[2] https://www.akamai.com/uk/en/about/news/press/2017-press/akamai-releases-spring-2017-state-of-online-retail-performance-report.jsp

--
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/20191005131216.13046.qmail%40cr.yp.to.

[D. J. Bernstein]

A naive textbook-level description of HTTPS makes it sound as if there's
always a key exchange on top of the cost of sending a cryptographically
protected web page from end to end. Furthermore, there's continual news
saying that a typical web page includes trackers from a variety of
servers. So it's easy to see how a cryptographer ends up imagining that
a web-page retrieval includes retrieving many short-term public keys.

However, for someone who takes a broader view of the communications
system, there are obvious steps that drastically reduce the cost of
communicating these public keys while still providing the desired
confidentiality (including forward secrecy), the desired integrity, and
even better availability:

* When a user retrieves many pages from the same site, one can simply
reuse the same symmetric session for all of the pages, skipping all
of the costs of public-key crypto after the initial setup. (As I
wrote in my first message: "A web page can involve multiple public
keys, but a key is often reused for many pages.")

* When many users talk to the same site, one can simply reuse the
same IND-CCA2 short-term key for the server, and send it through
standard caching mechanisms such as ISP DNS caches so that the key
rarely has to be sent end-to-end.

All of this is spelled out in the research literature: see, e.g., how
short-term keys are distributed in the MinimaLT paper at ACM CCS 2013.
Not all of it has been fully integrated into current Internet standards
such as HTTPS, but we want to change those standards anyway to include
post-quantum cryptography; we can make other changes at the same time,
or deploy new protocols the same way that QUIC has been widely deployed.

(Of course it's also interesting to ask how future cryptography can be
squeezed into yesterday's protocols with minimal changes, but we'd be
doing a disservice to future cryptographic users if we said that for
historical reasons we can't even consider better protocols.)

With these two optimizations, the average communication cost of a
protected web page is the cost of sending a byte end-to-end times

* the average web-page size, plus

* k ciphertext sizes where k is the average number of key exchanges
used per page (accounting for the possibility of multiple public
keys per page but also for reuse of a key across many pages), plus

* k*u public-key sizes where u is the fraction of the end-to-end
key-transmission cost that _isn't_ eliminated by caching, plus

* any necessary certificates (which can also be massively cached and
which I won't discuss further).

To make this concrete, here are six examples of what this means for a
3MB web page (a common size today; see the httparchive.org link in my
first message) using mceliece6960119 for various pairs (k,u):

u k | page bytes ciphertext bytes public-key bytes
------- ------- + ---------- ---------------- ----------------
1/5 1 | 3000000 226 209464
1/5 0.1 | 3000000 23 20946
1/100 1 | 3000000 226 10473
1/100 0.1 | 3000000 23 1047
1/2000 1 | 3000000 226 524
1/2000 0.1 | 3000000 23 52

mceliece6960119 uses only 6.5% of the total cost in the first scenario;
uses only 0.7% of the total cost in the second scenario; costs less than
frodokem976 in the third, fourth, fifth, and sixth scenarios; and costs
less than kyber1024 in the fifth and sixth scenarios. The big picture is
as follows:

* Better caching reduces u, moving down through the list of scenarios
and reducing the relative importance of key size.

* Continued increases in page size reduce the relative importance of
both the key size and the ciphertext size.

* Retrieving more pages from the same site reduces k, also reducing
the relative importance of key size and ciphertext size.

* Continued increases in the dominance of video traffic (see the
Sandvine report that I cited before) reduce the relative importance
of the key size, the ciphertext size, and the page size.

Another interesting point of comparison is Google's conclusion that "it
would be practical to quickly deploy NewHope in TLS 1.2". This referred
to the original non-IND-CCA2 version of NewHope, requiring a separate
short-term key for each session:

u k | page bytes ciphertext bytes public-key bytes
------- ------- + ---------- ---------------- ----------------
any 1 | 3000000 2048 2048
any 0.1 | 3000000 205 205

The overhead beyond the page size is about 2.6x smaller than
mceliece6960119 in the third and fourth scenarios, but about 5.5x larger
than mceliece6960119 in the fifth and sixth scenarios.

There isn't justification for the claim that the supposed "inefficiency"
of McEliece will stop it from being used. There isn't even justification
for the claim that McEliece costs more than NewHope---that we won't end
up in, e.g., the fifth scenario during the lifetime of the standards
that NIST produces. There's merely some speculation that _current_
networks don't allow this scenario---speculation that's looking at the
wrong networks; see below.

Mike Hamburg writes:
> the last link is the most expensive per bit in all these metrics,
> especially if Alice is on a cell phone.

The problem with pointing to variations in network costs, and trying to
cherry-pick the most expensive current network to support your argument,
is that the systems engineer will instead pick the _best_ network to
download a pile of short-term keys in advance---so the variation goes
very much _against_ your argument!

An iPhone already waits for a Wi-Fi connection for OS upgrades, app
upgrades, etc. New short-term keys are easy to see as another type of
upgrade. The savings are particularly clear when these prefetches over
Wi-Fi are used in place of just-in-time fetches over a cellular network.

In case there are people confused about the forward-secrecy concept, let
me emphasize that short-term keys can be computed and distributed any
amount of time in advance. Forward secrecy is measured by how long the
user's ciphertexts remain decryptable after they're sent.

(Generating a batch of keys at once also allows speedups in some
systems, notably systems using inversion. This is of interest since
there has also been quite a bit of hype regarding key-generation time.)

> I really don’t see the ISP cache saving more than, say, 80% of the cost

I don't see any citations backing up this u=1/5 guess regarding current
cell networks. A reader who asks "What will u look like in 5 years?" or
who asks "Surely Wi-Fi is much cheaper---what's u for Wi-Fi?" or who
simply wants to see how you arrived at this guess is left with no basis
for doing so.

> we should be comparing the size of 1 public key + 5 ciphertexts, right?

This statement isn't justified. First, this statement doesn't include
the unjustified assumption of a cell network. Second, this statement
doesn't include the unjustified u=1/5 assumption regarding current cell
networks. Third, readers will naturally compare the tally to page sizes
to see how important the cryptographic costs are in context, and then
tallying k ciphertexts + 0.2*k public keys is different from tallying
5 ciphertexts + 1 public key---unless k=5, another unjustified
assumption that the statement doesn't include.

> In other words, the cost of the large public keys is not
> outweighed by savings of the smaller ciphertexts.

This statement is again missing the assumption of a cell network, and
the u=1/5 assumption regarding current cell networks.

> Now let’s consider page load times.

Sure! Switching from traffic to latency gives the system designer yet
another reason to fetch a pile of short-term keys in advance through a
fast network, so that the user sees _zero_ latency for all those keys.
Prefetching directly undermines the stories about 420ms delays "*per
handshake*", about a 100ms delay hurting "conversion rates by 7%", etc.

As for the grandiose followup claims about the tail wagging the dog
(cryptographic costs making cross-domain trackers "prohibitive", making
the "goals" of network neutrality "infeasible", etc.), it's certainly
tempting to comment on the details (e.g., these claims hype the
web-page-can-involve-multiple-public-keys effect while apparently
missing the key-is-often-reused-for-many-pages effect), but I have a
better idea: NIST should adopt the normal scientific rule of
falsifiability for all inputs to the PQC process.

Finally, you briefly claim that prefetching "only works well for things
that are latency-limited, not bandwidth-limited". Here's how prefetching
actually works from a performance perspective:

* A successful prefetch---even if it can't take advantage of a faster
network---has _zero_ traffic cost compared to a just-in-time fetch.
It's simply shifting the fetch to an earlier time, so that the user
doesn't see the latency.

* The system designer decides how much cost is acceptable for
unsuccessful prefetches---of course accounting for the effect of
moving prefetches to idle times on fast networks---and tunes the
prefetch strategy accordingly. (When your phone asks you to upgrade
all your apps overnight over a free Wi-Fi network, and you agree,
but it then turns out that you don't run some app before upgrading
it again, do you curse yourself for the waste of free bandwidth and
swear to do only just-in-time upgrades in the future?)

* The overall latency impact of this amount of prefetching depends on
fetch patterns (e.g., how often you visit each site) and needs to
be measured. Of course there's also a dependence on the
forward-secrecy interval; as far as I know, standard web-server
installations today still don't achieve Adam Langley's 1-day goal.

You're already out on a _very_ shaky limb in claiming that the McEliece
key size is a problem for total traffic---and then how do you get from
this to the idea that the system designer won't replace just-in-time
fetching of N keys with prefetching of 1.05N keys or even 1.5N keys? Do
you think that there's some sort of magical barrier at N keys?

---Dan

[Mike Hamburg]

Hi Dan,

Perhaps I wasn’t being clear about my spitball of u = 1/5. I admit that I was too lazy to look up actual cost (Joules or TCO $ per bit) for various different kinds of links. I was guessing that since a typical website is maybe 10-20 long-distance links away, and there is an economy of scale plus more efficient transmission technologies (fiber and ethernet instead of wifi, DSL and coax) for the later hops, the first two hops (wifi and DSL / cable / point-to-point wireless) will make up at least 20% of the cost. A cell link would be more — those towers are very expensive and power-hungry. Again, you’re welcome to dispute this, but the picture doesn’t change much if u = 1/10.

Also, u is larger for website that are already using CDNs, because the denominator is smaller.

And in 15 years, who knows what it’s going to be? If it’s SpaceX low-orbit satellites, u is going to go up rather than down.

On the contrary, I’m not sure how you’re getting u = 1/2000. How is loading from an ISP cache 2000x more cost-efficient or energy-efficient than loading from the general internet? How are you even hitting cache 99.95% of the time? Yes, you can use the same public key for multiple connections, but usually it’s easier to use it once and then use the exchanged symmetric key for multiple connections, and it has similar exposure risk. (This reduces k rather than u, which still helps the total bandwidth case but not the comparison with other systems like Frodo.)



As for downloading certs on wifi, are we still talking about 10-minute keys? Even if they’re pre-generated, just the top 100 sites on the internet would be 14.4 GB per device per day, just for the public keys. Right now, this would be a meaningful fraction of the device’s storage too, but let’s assume that this will be greatly improved by the time we’re rolling out McEliece. That’s still going to be a meaningful cost, and even then it’s not enough to make cache misses rare.

Sure, OK, your phone could learn from your usage patterns to better predict which certs to download, or adaptively use longer-term (less-forward-secure) certs for a first connection and then download a more recent one in the background, or you could have a mesh network where your router forwards keys to your neighbors, or … there are ways to mitigate the cost.

But when we’re talking about building a machine-learning system to control a link-cost-sensitive prefetch mechanism which will use keys broadcast from secure key-pregeneration servers via a CDN, all just to mitigate the cost of transporting the public keys … maybe it’s time to admit that having big keys will meaningfully increase the cost of the system.

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/20191006205141.13267.qmail%40cr.yp.to.

[Panos Kampanakis (pkampana)]

Hi Dan,

I think Mike's points are valid from an operations point of view. Speaking as a vendor, I would like to see McEliece standardized because of its security guarantees, but I consider it as one of the least favorable schemes to deploy for (D)TLS VPN or IKEv2 because of its public key size (and in spite of its good ct size and performance).

We live in an era where
- Public Key Pinning that allowed clients to pin (identity) public keys for websites was abandoned or not used by major vendors because of operational concerns. ISP caching resembles public key pinning with even more aggressive schedules.
- ISPs have been under long lasting pressure with profit margins and their equipment lifespans are long. Upgrading millions of edge devices to do caching is not trivial.
- DANE that allows for passing identity public keys over DNS has seen pretty low adoption for many years now. So passing public keys over DNS may be a good idea, but it is not getting the traction.
- IETF is currently standardizing cert compression to save <1KB per certificate in a 3-5KB cert chain. 1MB keys are magnitudes more.
- IETF has been strongly striving for ephemeral key per TLS connection and strongly opposed static/long-lived keys for any usecase. 10mins keys are not static, but they are not ephemeral either.

A couple additional Ops challenges with what you are proposing are
- With TLS 1.3 and ESNI, an ISP cache would not know what public key to serve to a client as everything is encrypted. Serving a public key based on destination address will not work because CDNs serve multiple destinations from the same location.
- Caching a chunk of all internet server public keys every x-mins at the ISP edge is not trivial from an operations point of view
- Broadcast 1MB messages all the way to the ISP edge every 10minutes? I would ask an ISP first.

Imposing great changes and redesigns in currently deployed protocols to accommodate McEliece needs careful consideration and proof that alternatives will not work. I am a big proponent of making drastic changes only if there is no other option. To revisit Mike's point, there are some good enough KEMs in the NIST submissions that would slow down a typical handshake by 5-10%. Google, Cloudflare and AWS have been testing in this space and we have been doing similar testing with signature algorithms.

Again, I am all for NIST standardizing McEliece, I just don't think that "live protocol" key exchange is its usecase, at least not until other good candidates are eliminated.

Rgs,
Panos



-----Original Message-----
From: D. J. Bernstein <d...@cr.yp.to>
Sent: Sunday, October 06, 2019 4:52 PM
To: pqc-...@list.nist.gov
Subject: Re: [pqc-forum] Re: Why standardize "big" systems?

* PGP Signed by an unknown key

--
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/20191006205141.13267.qmail%40cr.yp.to.

* Unknown Key
* 0x3B0E5459

[D. J. Bernstein]

Mike Hamburg writes:
> there is an economy of scale plus more efficient transmission
> technologies (fiber and ethernet instead of wifi, DSL and coax) for
> the later hops

ISPs have been building more and more fiber to customer premises to
replace the old copper wires. Verizon Fios Internet alone claims more
than 6 million U.S. customers:

https://www.verizon.com/about/sites/default/files/2018-Verizon-Annual-Report.pdf

This makes the "DSL and coax" story sound rather shortsighted. I also
see no evidence that Wi-Fi will be a bottleneck.

Fundamentally, the costs of communicating a byte are proportional to the
distance that the byte travels. This is

* why CDNs take data several million meters away from you and try
to make sure that it's cached within a million meters of you---
making the CDN another point of attack, but many people accept this
for the lower communication cost;

* why ISPs sometimes cache data much closer to you (and complain that
end-to-end encryption gets in the way of this---the issue here is
the distance of data transmission, not the public-key costs);

* why the "last mile" of Internet connectivity is also the least
important to transition to fiber---a byte traveling 1000000 meters
end to end over fiber, plus 1000 meters over copper that's c times
less efficient, is incurring total communication cost proportional
to 1000000+1000c;

* why the convenience of Wi-Fi for the last ten meters of Internet
delivery outweighs the inherent inefficiency of broadcasting data
in every direction through the air;

* why Intel reports moving 8 bytes as costing 11.20pJ "per 5 mm" (see
https://www.openfabrics.org/images/eventpresos/workshops2015/DevWorkshop/Tuesday/tuesday_10.pdf);

etc. Of course the standard "economy of scale" arguments say that the
last mile is also the most expensive mile to upgrade from copper to
fiber---but the transition is happening anyway, clearly driven by users
wanting more data than ISPs can squeeze out of the installed copper.

> SpaceX low-orbit satellites

Let's assume that SpaceX manages to deploy all 11943 satellites by 2027,
that each satellite works at the rated 23Gbps, and that each satellite
is magically being used full-time. That's still not enough capacity to
handle _today's_ Internet traffic. Furthermore, I'm not aware of any
numbers suggesting that SpaceX will be competitive in cost with
traditional ISPs even if we ignore SpaceX's obvious inefficiencies in
caching. The argument that SpaceX actually makes in, e.g.,

https://cdn.arstechnica.net/wp-content/uploads/2016/11/spacex-Legal-Narrative.pdf

is that "many parts of the United States and the world lack access to
reliable broadband connectivity".

I'm not arguing that SpaceX should be excluded from the list of target
networks for future cryptography. I think it's useful to consider how
cryptography can squeeze into narrow corners of various networks. But
it's wrong to demand that _all_ NISTPQC options be designed this way.

> On the contrary, I’m not sure how you’re getting u = 1/2000.

By "getting" do you mean "describing how this can happen" (which I've
done in considerable detail), or "claiming that this is the only
possibility" (which I've never done)?

I'm not arguing that NISTPQC should limit attention to a particular
deployment scenario. On the contrary, I'm _objecting to_ arguments that
NISTPQC should limit attention to a particular scenario.

In particular, there's an unjustified claim that McEliece uses more
bandwidth than (e.g.) NewHope---as part of an even more extreme claim
that the "inefficiency" of McEliece will stop it from being used. These
claims should never have been issued without explicit statements of the
underlying assumptions about u (and k).

> How is loading from an ISP cache 2000x more cost-efficient or
> energy-efficient than loading from the general internet?

You mean, how _can_ loading from an ISP cache be 2000x more efficient?
Answer: consider an ISP cache that's thousands of times closer than the
server.

> How are you even hitting cache 99.95% of the time?

You mean, how _can_ the cache-hit ratio be 99.95%? Answer: consider
thousands of users of the ISP who want the same ephemeral key because
they're accessing the same site during the same forward-secrecy period.

> Yes, you can use the same public key for multiple connections, but
> usually it’s easier to use it once and then use the exchanged
> symmetric key for multiple connections

Throughout this discussion I've been assuming normal use of symmetric
crypto by each user, including normal caching of symmetric keys to use
for many messages, which is what you're talking about here.

Looking beyond this single-user perspective shows that _there are many
users_. These users should not share symmetric keys. They _can_ and
_should_ share the work of retrieving public keys, producing the cost
reduction that I've been talking about for public keys---showing that
the "key size + ciphertext size" metric is oversimplified.

> As for downloading certs on wifi, are we still talking about 10-minute
> keys?

I described this as a variable from the outset ("period of (say) 10
minutes"). I also quoted Langley's "once a day" goal---where, evidently,
once-per-day prefetching would cost you just 1MB of storage per site.
For comparison, the app that I upgraded a moment ago was 140MB.

> the top 100 sites on the internet

Do you think there are 100 different sites that you frequently visit
from your smartphone? To me that sounds like a lot, but I haven't been
able to find measurements of typical smartphone behavior.

It's much easier to find numbers regarding the growth of device storage:
e.g., 16GB for the largest iPhone in 2007 vs. 512GB for the largest
iPhone today. Is it hard to imagine an iPhone with 16TB of storage in,
say, 2027, just a few years after NIST issues post-quantum standards?

> That’s still going to be a meaningful cost

If we ask ten different pqc-forum participants for the dividing line
between "meaningful" and non-"meaningful" costs then we'll get ten
different answers. If you think you have a solid objective argument then
why do you resort to unclear, judgmental terminology?

> Sure, OK, your phone could learn from your usage patterns to better
> predict which certs to download

Aha! Now I see one of the underlying problems in this discussion.

You seem to be thinking of caching, "link-cost-sensitive prefetch", etc.
as hypothetical tools that we _could_ theoretically build to reduce the
costs of transporting these 1MB McEliece keys. You complain about the
effort to build these tools. You seem to think that this effort is a
"cost" of using McEliece, and that this justifies making claims about
network traffic under implicit assumptions that these tools won't exist.

I'm instead seeing caching, prefetching, etc. as general-purpose tools
that are already built into the Internet infrastructure today, at every
level from CDNs down to your phone (which, yes, already pays attention
to the link costs). There's no reason that we shouldn't use the same
tools to transport public keys. This undermines the claims about network
traffic---and enables better solutions for future cryptographic users.

I have a suggestion for NIST: Why not ask NIST's Advanced Network
Technologies Division for help in evaluating the network-performance
aspects of NISTPQC? Explaining the cryptographic sizes and data flow to
them is surely much less effort than explaining to cryptographers how
the Internet works, while there are other aspects of NISTPQC that we
really need cryptographers to be focusing on.

---Dan

[Mike Hamburg]

This is nice for fabrics, but in practice our devices are not continuously connected by on-die wires.  For a realistic application, see eg:

https://www.mdpi.com/1996-1073/12/1/184

Note that a femto-cell has on the same order of magnitude power efficiency as wi-fi, and comparable range.  You will see that a typical (macro) cell network uses approximately 20x the power consumption of the wireline network, whereas femto-cells are around 1/5th the power consumption of the wireline network.  This accords with my previous claims that wifi + the last wireline hop will be at least 20% of the power consumption.

This is because of the economy of scale not only in signal amplification, but in power distribution, cooling, routing, etc.

I’ve tried to find better references for the core internet, but I’ve come up with nothing recent of particularly high quality.  However, the articles I’ve found seem to claim that the power consumption of routers and network interfaces are typically larger than those of the signal regenerators, though not necessarily by an order of magnitude; and that edge routers use more total power than core routers.  See eg:

http://netlab.cs.ucla.edu/wiki/files/e_energy10ccn.pdf

This article is old, but other articles I’ve found are in agreement with this.

etc. Of course the standard "economy of scale" arguments say that the
last mile is also the most expensive mile to upgrade from copper to
fiber---but the transition is happening anyway, clearly driven by users
wanting more data than ISPs can squeeze out of the installed copper.

SpaceX low-orbit satellites

Let's assume that SpaceX manages to deploy all 11943 satellites by 2027,
that each satellite works at the rated 23Gbps, and that each satellite
is magically being used full-time. That's still not enough capacity to
handle _today's_ Internet traffic. Furthermore, I'm not aware of any
numbers suggesting that SpaceX will be competitive in cost with
traditional ISPs even if we ignore SpaceX's obvious inefficiencies in
caching. The argument that SpaceX actually makes in, e.g.,

  https://cdn.arstechnica.net/wp-content/uploads/2016/11/spacex-Legal-Narrative.pdf

is that "many parts of the United States and the world lack access to
reliable broadband connectivity".

I'm not arguing that SpaceX should be excluded from the list of target
networks for future cryptography. I think it's useful to consider how
cryptography can squeeze into narrow corners of various networks. But
it's wrong to demand that _all_ NISTPQC options be designed this way.

I am not demanding that all NISTPQC options be suitable for TLS-like or other web-applicable use.  You will see that I disclaimed that explicitly.  However, to the extent that many customers would use this kind of network for their day-to-day internet activity, it makes sense to consider it in a protocol designed for the general internet.  The same is true for cell networks.

On the contrary, I’m not sure how you’re getting u = 1/2000.

By "getting" do you mean "describing how this can happen" (which I've
done in considerable detail), or "claiming that this is the only
possibility" (which I've never done)?

I'm not arguing that NISTPQC should limit attention to a particular
deployment scenario. On the contrary, I'm _objecting to_ arguments that
NISTPQC should limit attention to a particular scenario.

In particular, there's an unjustified claim that McEliece uses more
bandwidth than (e.g.) NewHope---as part of an even more extreme claim
that the "inefficiency" of McEliece will stop it from being used. These
claims should never have been issued without explicit statements of the
underlying assumptions about u (and k).

As I understand it, your argument for how this can happen assumes that one key will be used for many exchanges either by one user (which is unlikely as we agree below) or by many users.  But for many users, the key still needs to be distributed locally that many times, which, as I’ve argued, uses much more than 1/2000th the power of distributing the key over the internet.

How is loading from an ISP cache 2000x more cost-efficient or
energy-efficient than loading from the general internet?

You mean, how _can_ loading from an ISP cache be 2000x more efficient?
Answer: consider an ISP cache that's thousands of times closer than the
server.

As I have argued, it is highly unlikely to be thousands of times “closer" energy-wise, or even 10 times closer.  Even the wi-fi router would not be 2000x closer energy-wise.

How are you even hitting cache 99.95% of the time?

You mean, how _can_ the cache-hit ratio be 99.95%? Answer: consider
thousands of users of the ISP who want the same ephemeral key because
they're accessing the same site during the same forward-secrecy period.

How is it likely that you will hit cache 99.95% of the time in a realistic scenario capturing Web-like network usage over a long period of time (eg, days or weeks)?

If the cache is “thousands of times closer” to users (let’s pretend for a moment that this captures energy-efficiency), then it is within a mile or so of them, so it is serving at most, say, 10,000 users, or maybe a few tens of thousands in a dense city.  For general web browsing, you won’t even have that many users hitting the cache for a given website in a given forward-secrecy period.

Yes, you can use the same public key for multiple connections, but
usually it’s easier to use it once and then use the exchanged
symmetric key for multiple connections

Throughout this discussion I've been assuming normal use of symmetric
crypto by each user, including normal caching of symmetric keys to use
for many messages, which is what you're talking about here.

Looking beyond this single-user perspective shows that _there are many
users_. These users should not share symmetric keys. They _can_ and
_should_ share the work of retrieving public keys, producing the cost
reduction that I've been talking about for public keys---showing that
the "key size + ciphertext size" metric is oversimplified.

As for downloading certs on wifi, are we still talking about 10-minute
keys?

I described this as a variable from the outset ("period of (say) 10
minutes"). I also quoted Langley's "once a day" goal---where, evidently,
once-per-day prefetching would cost you just 1MB of storage per site.

For comparison, the app that I upgraded a moment ago was 140MB.

Ah.  So we could mitigate the cost of prefetching, but we would have to abandon a goal that you think is better for security:

“””

  * I'm setting a goal here of erasing public keys within 10 minutes
    for forward secrecy. For comparison, Langley aimed for "once a day"
    in https://www.imperialviolet.org/2013/06/27/botchingpfs.html and
    explained that TLS implementations would often keep keys for "many
    months". If a 1-day key lifetime is acceptable then local caching
    will be even more effective, and key size will matter even less. I
    think that aiming for the scale of minutes is better.

“””

Also, your apps don’t update every day.  140 MB is less than the keys required for 1 site for 24 hours, if they update every 10 minutes.

the top 100 sites on the internet

Do you think there are 100 different sites that you frequently visit
from your smartphone? To me that sounds like a lot, but I haven't been
able to find measurements of typical smartphone behavior.

No.  I spend quite a bit of time browsing news and articles on the web, which I find through search engines, aggregators, etc.  So while I don’t have 100+ sites that I regularly visit, my access pattern likely does not typically stay within a particular 100 sites either.

Furthermore, each site contains multiple subdomains that use different keys.  This is due to them being hosted in different places, eg at the website’s data center vs at a CDN.  You seem to think that this will go away, but I don’t see any justification for this assumption.

It's much easier to find numbers regarding the growth of device storage:
e.g., 16GB for the largest iPhone in 2007 vs. 512GB for the largest
iPhone today. Is it hard to imagine an iPhone with 16TB of storage in,
say, 2027, just a few years after NIST issues post-quantum standards?

Many sins can be covered by imagining that Moore’s law will continue for another decade.

That’s still going to be a meaningful cost

If we ask ten different pqc-forum participants for the dividing line
between "meaningful" and non-"meaningful" costs then we'll get ten
different answers. If you think you have a solid objective argument then
why do you resort to unclear, judgmental terminology?

OK, here’s my solid, objective argument.

Come 2030, a large enough fraction of Web users (say, 1/4) will have slow enough and/or expensive enough connections (say, 50 Mb cell connections) that, in the minds of website operators, the cost (in bandwidth and latency) of 1MB McEliece keys will outweigh the risk reduction, compared to any of the current Round-2 lattice KEM candidates that remain unbroken at that time, including Frodo.  This is true even accounting for improvement in caching and CDN technologies.

The other posters in this thread and I have presented ample evidence that this argument is true on today’s internet, and that in fact the cost outweighs the risk reduction by at least one and more likely multiple orders of magnitude.  I have also presented evidence that caching will reduce the cost by less than one order of magnitude.

Sure, OK, your phone could learn from your usage patterns to better
predict which certs to download

Aha! Now I see one of the underlying problems in this discussion.

You seem to be thinking of caching, "link-cost-sensitive prefetch", etc.
as hypothetical tools that we _could_ theoretically build to reduce the
costs of transporting these 1MB McEliece keys. You complain about the
effort to build these tools. You seem to think that this effort is a
"cost" of using McEliece, and that this justifies making claims about
network traffic under implicit assumptions that these tools won't exist.

I'm instead seeing caching, prefetching, etc. as general-purpose tools
that are already built into the Internet infrastructure today, at every
level from CDNs down to your phone (which, yes, already pays attention
to the link costs). There's no reason that we shouldn't use the same
tools to transport public keys. This undermines the claims about network
traffic---and enables better solutions for future cryptographic users.

Setting up a CDN is an additional burden on site operators, which larger websites take on to reduce their bandwidth bills but smaller ones do not.  For example, your own website distributes content directly from UIC, not via a CDN, and a similar statement is true of my website.  However, both these websites enjoy forward secrecy due to ECDH and, hopefully, a time-limited session cache.

Furthermore, CDNs come with an inherent privacy tradeoff, which will extend to future HTTPS analogues by, eg, preventing encrypted SNI as Panos pointed out.  While it is possible that ISPs could automatically cache public keys for some amount of time, this would still require effort on the server side and would again preclude the use of encrypted SNI.

If rolling out McEliece comes at a high cost in administrator effort or in privacy, in addition to significant bandwidth issues, then people will not choose to do it.

I have a suggestion for NIST: Why not ask NIST's Advanced Network
Technologies Division for help in evaluating the network-performance
aspects of NISTPQC? Explaining the cryptographic sizes and data flow to
them is surely much less effort than explaining to cryptographers how
the Internet works, while there are other aspects of NISTPQC that we
really need cryptographers to be focusing on.

I would certainly be interested in NIST’s opinion on this topic.

---Dan

— 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/20191009220710.32314.qmail%40cr.yp.to.

[D. J. Bernstein]

If we want to reduce post-quantum KEM traffic, we should

* use standard networking techniques to share the costs of sending
keys to many users (as in McGrew's talk), and

* account for how this sharing interacts with KEM sizes when we
select a KEM (not necessarily the same KEM for every connection).

I've been explaining how this can end up with "McEliece + heavy caching"
as the optimal solution (at each NISTPQC security level), especially for
popular sites such as Google.

I'm not saying that this scenario is guaranteed to happen. I'm objecting
to analyses that ignore this scenario. How can anyone claim that traffic
is a McEliece disadvantage, when there are scenarios where traffic is a
McEliece advantage? The operations-research answer is to

* quantify the probabilities of the scenarios and
* merge the probabilities of advantages and disadvantages into a
combined metric,

but the arguments here aren't trying to take this quantitative approach.
Instead there have been more extreme efforts to dismiss the scenarios
where traffic is a McEliece advantage. The rest of this message analyzes
various arguments for the specific claim that keys won't be downloaded
via ISP caches, such as DNS caches.

'Panos Kampanakis (pkampana)' via pqc-forum writes:
> We live in an era where

I agree with some of your statements about the situation in 2019, and I
disagree with others; see below. But let me begin by emphasizing a
broader structural problem with this type of argument.

The Internet changes over time. Look at TLS 1.3 versus TLS 1.2, for
example, or at the bandwidth trends that I've cited. I don't see how you
can argue that the scope of NISTPQC should be limited to tweaking the
crypto primitives deployed in a 2019-vintage protocol on the
2019-vintage Internet. Why should we think that we'll have the same
environment in 2024, or in 2029, or in 2034? If the most efficient way
to deploy post-quantum crypto in the future comes from a synergy between

* a change in the protocol (e.g., obtaining keys through DNS) and
* a feature of a post-quantum system (e.g., very small ciphertexts),

shouldn't NISTPQC _promote_ that possibility rather than ignoring it?

> - Public Key Pinning that allowed clients to pin (identity) public
> keys for websites was abandoned or not used by major vendors because
> of operational concerns. ISP caching resembles public key pinning with
> even more aggressive schedules.

Google proposed pinning as a security feature for sites to "defend
against certificate misissuance" by limiting the CAs "that can issue for
their domain". Google withdrew the proposal in

https://groups.google.com/a/chromium.org/forum/#!msg/blink-dev/he9tr7p3rZ8/eNMwKPmUBAAJ

explaining that pinning often fails in the real world---it is "hard to
build a pin-set that is guaranteed to work, due to the variance in both
user-agent trust stores and CA operations". In short, this was a
functionality limit first being promoted as a security feature, and then
being withdrawn because it turned out to be _too_ limited.

These quotes provide no support for your suggested analogy between
pinning and caching. The whole idea of _caching_ is to speed up the
normal case---not to prohibit changes of keys or limit the choices of
CAs. There's no limit on functionality; the worst case is falling back
to uncached data. The reasons that Google gave for withdrawing pinning
don't apply to caches. Furthermore, this thread has focused on the
bandwidth for _short-term_ keys, and those don't interact with the CAs.

> - ISPs have been under long lasting pressure with profit margins and
> their equipment lifespans are long.

Of course ISPs pay attention to costs---but what do you expect to happen
to an old device that can't handle the user's demands for data? See the
numbers that I cited before regarding the growth of Internet traffic.
How many of the current devices do you expect to be running in 2034?

I also don't understand how current ISP equipment is supposed to have a
problem with what I'm talking about. See below.

> Upgrading millions of edge devices to do caching is not trivial.

ISP-level caches such as DNS caches already exist. Do you claim that
further upgrades are required for the efficiency gains I've described?

This thread started with an unjustified claim that McEliece would "never
be used" because of its "inefficiency". What does "not trivial" mean? Is
it something expensive enough to support the "never be used" claim?

The lack of clarity makes errors unnecessarily difficult to identify and
correct. Let me again propose that NIST adopt the normal scientific rule

of falsifiability for all inputs to the PQC process.

> - DANE that allows for passing identity public keys over DNS has seen
> pretty low adoption for many years now. So passing public keys over
> DNS may be a good idea, but it is not getting the traction.

DANE's advertisement is a _security_ claim that DNS authorities are more
trustworthy than CAs. This is what "DNS-based Authentication of Named
Entities" is referring to. This claim is disputed---see, e.g.,

https://sockpuppet.org/blog/2015/01/15/against-dnssec/

under "Government-Controlled PKI"---and I don't see users rushing to
take action on the basis of this claim.

How does the lack of popularity of a disputed _security_ improvement
support any conclusions regarding current or future popularity of an
_efficiency_ improvement? I already cited a TLS replacement that
retrieves short-term keys through DNS.

> - IETF is currently standardizing cert compression to save <1KB per
> certificate in a 3-5KB cert chain. 1MB keys are magnitudes more.

I don't understand the logic here. How is the existence of one speedup
effort supposed to be an argument against a further speedup effort,
namely caching keys? If keys _are_ sufficiently cached, then why are you
highlighting the key size and ignoring the ciphertext size? One has to
look at the total costs, not just isolated fragments of the costs.

> - IETF has been strongly striving for ephemeral key per TLS connection
> and strongly opposed static/long-lived keys for any usecase.

Before this you seemed to be arguing that NISTPQC should limit attention
to what's currently standardized and deployed, except for swapping out
the crypto primitives. Here, however, you're arguing that NISTPQC should
_ignore_ the installed base of working software (from, e.g., Microsoft)
that does _not_ do what you're advocating, contrary to what a reader
might expect from the word "strongly".

Why should NISTPQC ignore current practice regarding one topic (the
speed of key erasure) but limit attention to current practice regarding
other topics? By bringing up this topic you seem to be acknowledging
that protocols can and sometimes do change---but then why should NISTPQC
ignore changes that can reverse performance comparisons, such as
retrieving short-term keys through DNS?

Regarding the merits of new keys: The actual security goal is for user
data to be encrypted under keys that will be erased soon, so that later
theft of Alice and/or Bob's devices won't allow retroactive decryption
of their ciphertexts. As far as I know, getting "soon" down to "1 day"
is still not acheived by standard configurations. See, e.g.,

https://jhalderm.com/pub/papers/forward-secrecy-imc16.pdf

and the Adam Langley blog post that I cited before.

What's the security benefit of reducing "soon" from 1 day to 1 hour? 10
minutes? 1 minute? 10 seconds? 1 second? 1 milliseconds? 1 microsecond?
Do you think the security benefit approaches infinity as this time
decreases towards 0? I've seen no literature arguing this, nor do I know
how such an argument could be made, starting from the actual security
motivation for erasing keys.

If Alice presses "send" and her phone is disconnected from the network
for a second, you think she wants the phone to give up on sending the
message? If the phone is retrying using the next second's key and the
key after that and so on for, say, 5 minutes, then what exactly is being
accomplished by discarding keys? The _user data_ is still on the phone a
minute later. Furthermore, once the message _does_ get through, are
Alice and Bob both deleting it in under a minute? And what about the two
minutes that Alice spent typing the message in the first place? Similar
comments apply when messaging is replaced with web browsing.

If we agree that erasing keys doesn't have security benefit approaching
infinity as the key-erasure time T decreases, then, mathematically, we
must agree that some nonzero T gets within 1% of the maximum possible
security benefit---and then I don't see how you can argue that NISTPQC
should be excluding scenarios where keys are cached for time T. The next
question is what T is, and I don't see literature studying this, beyond
the literature pointing to a bunch of reasons that _currently_ data is
decryptable more than a day later.

To summarize, I don't see the argument for NISTPQC to rule out the
scenario of 1-day key erasure (which, again, is more ambitious than what
we have today). I don't see the argument for NISTPQC to rule out the
scenario of 10-minute key erasure. There are many more possibilities.

As a side note, if a user is asking a sensible question such as

"Rogue government G arrested me and took my unlocked device. I erased
a message an hour before that. Can G still figure out the message
from the intercepted ciphertext?"

then I don't see how one can come up with a convincing answer based on
protocol concepts that don't mention time, such as

* "every TLS packet" or
* "every 100 TLS packets" or
* "every TLS connection" or
* "every 100 TLS connections" or
* "every TLS session" or
* "every 100 TLS sessions".

Sliding between these concepts _feels_ like selecting different time
scales, but of course the actual story is much more complicated---e.g.,
sometimes the spacing between packets in TLS connection #1 is longer
than an entire TLS session #2.

> A couple additional Ops challenges with what you are proposing are
> - With TLS 1.3 and ESNI, an ISP cache would not know what public key
> to serve to a client as everything is encrypted. Serving a public key
> based on destination address will not work because CDNs serve
> multiple destinations from the same location.

The client begins by using DNS to map the server name to the server
address. There are various protocols that use exactly the same channel
to also retrieve cryptographic data such as certificates, long-term
keys, and short-term keys. The server name is provided at the outset,
and nobody ever has to try to map an IP address to a key.

To the extent that DNS is encrypted (to the ISP, or to CDNs offering
substitute DNS caches and claiming to be less evil than the ISP), there
isn't any direct SNI-type exposure of names to random eavesdroppers. In
other words, these protocols never had the TLS problem that ESNI tries
to solve. To the extent that DNS _isn't_ encrypted, the names you're
looking up are exposed to random eavesdroppers anyway.

The TLS data flow makes this seem like an annoying conflict between
functionality (hosting multiple sites on one server) and security
(encrypting the site name). This is a fixable flaw in TLS.

> - Caching a chunk of all internet server public keys every x-mins at
> the ISP edge is not trivial from an operations point of view

What "chunk" are you referring to? What does "not trivial" mean?

As for "all internet server public keys": For the goal of minimizing
post-quantum KEM bandwidth, I would start with popular sites such as
Google. If the popular sites save bandwidth with McEliece then that's
enough to show that the "McEliece is big" narrative is oversimplified.

> - Broadcast 1MB messages all the way to the ISP edge every 10minutes?
> I would ask an ISP first.

That's 1748 bytes/second. Google sends _vastly_ more data than this to
ISP users, as do most of the other sites that add up to pretty much all
Internet usage today.

Concretely, Cisco reports Internet traffic above 30000 gigabytes per
second. Sandvine reports Google using 3.48% of Internet traffic in the
Americas, and more elsewhere. Multiply: above 1000 gigabytes per second,
half a billion times larger than the per-ISP number that you say we
should be asking the ISP about. Of course a full analysis has to look
more at ISP networks, but it's hard to see how your snap judgment here
could match reality for any of the sites that would want broadcasts.

To repeat part of my first message (see that message for the underlying
numbers): If the average number of keys retrieved per page is, say, 0.1,

and we add 1MB to upgrade _every_ key for _every_ page to Classic
McEliece, then the total increase in Internet traffic is around 0.8%.
For comparison,

https://www.ktm2day.com/2018/12/24/cisco-predicts-tremendous-internet-traffic-growth-over-the-next-5-y
+ears/

predicts more than 20% traffic growth per year in every region of the
world. It also predicts further dominance of video traffic; this will
drive the 0.8% figure even lower.

> Imposing great changes and redesigns

What does "great" mean here?

> in currently deployed protocols to accommodate McEliece

If you look at the ACM CCS 2013 paper that I mentioned retrieving keys
through DNS, you'll see that the paper _doesn't_ use McEliece. The point
is to reduce latency---the paper uses even fewer round trips than QUIC
(or "0RTT" TLS) on the first connection.

> there are some good enough KEMs in the NIST submissions that would
> slow down a typical handshake by 5-10%.

I thought Cloudflare was putting in the engineering effort to test SIKE
because their current evaluation is that---at least for slow connections
that they see often enough to care about---the lattice sizes are _not_
good enough for them to be satisfied.

Does this contradict your "good enough" claim? Does this contradict the
conclusions that you're trying to draw from the "good enough" claim? The
ambiguity of "good enough" makes analysis unnecessarily difficult.

---Dan

[David A. Cooper]

My opinion on this topic doesn't really matter. It's one thing to argue that a particular scheme could be more efficient if keys were distributed in a certain manner and were reused for a period of time. However, it doesn't matter what could be, if those who will actually be implementing these protocols will not accept it.

While the current installed base may reuse (EC)DH keys on the server side, it is not clear how that would translate to the use of the KEMs that are being considered as part of NISTPQC. For the KEMs, the most straightforward implementation under TLS 1.3 would be for the client to generate the key pair and for the server to respond with the ciphertext. The server wouldn't be generating any key pairs.

One could certainly imagine a version of TLS in which the proposed scheme would work. The proposal to store a server's public key in DNS and then use that key to establish the session keys sounds exactly like what is proposed with ESNI. In ESNI a key agreement is performed using a server key that is stored in the DNS and an ephemeral key that is generated by the client. The resulting shared secret is used to derive a session key, which is used to encrypt the server's name in the TLS handshake. That same shared secret could also be used to derive a pre-shared key, which could be used in TLS's pre-shared key mode to derive the session keys used to protect application traffic.

Note, however, that while the above idea is rather obvious, to the best of my knowledge it has never been discussed within the IETF TLS working group. The idea could be proposed, but my guess is that it would face strong opposition. Even if everyone on this mail list agreed that this proposal was secure, efficient, and easily implementable, would it really matter if those who actually make the decisions about what to implement insist that it is unacceptable to them? Why not present this idea within the appropriate IETF forum(s) to try to find out whether there is any chance of this idea being accepted by those who would have to be convinced to implement it?

I do not understand the suggestion about "an annoying conflict between functionality ... and security." ESNI is only considered to be useful if multiple sites are hosted on one server. If a server only hosts one site, then there is a one-to-one mapping between IP address and server name, and since the IP address is not encrypted, there isn't much benefit in encrypting the server name. What is this conflict and what if the flaw in TLS that is fixable?

On 10/28/19 5:47 PM, D. J. Bernstein wrote:

- IETF has been strongly striving for ephemeral key per TLS connection
and strongly opposed static/long-lived keys for any usecase.

Before this you seemed to be arguing that NISTPQC should limit attention
to what's currently standardized and deployed, except for swapping out
the crypto primitives. Here, however, you're arguing that NISTPQC should
_ignore_ the installed base of working software (from, e.g., Microsoft)
that does _not_ do what you're advocating, contrary to what a reader
might expect from the word "strongly".

...

A couple additional Ops challenges with what you are proposing are 
- With TLS 1.3 and ESNI, an ISP cache would not know what public key
to serve to a client as everything is encrypted. Serving a public key
based on destination address will not work because CDNs serve 
multiple destinations from the same location. 

...
The TLS data flow makes this seem like an annoying conflict between
functionality (hosting multiple sites on one server) and security
(encrypting the site name). This is a fixable flaw in TLS.

[Dan Brown]

A few small questions/points:

1. Could small-key NIST PQC algorithms expand their keys (where cost is low)
for some benefits, such as efficiency improvements? For example, hasn't
somebody already timed SIKE using 1MB of pre-computation? Long ago, Scott
Vanstone's team proposed "fat" ECC certificates that include a table (e.g.,
RSA-sized) of pre-computed multiples of an EC public key, thereby speeding up
the recipient's computations (I ask: at a risk of cache-timing side channels,
etc?) Such certificates were even added to SEC1 v2, though it never gained
much acceptance elsewhere (in particular, in IETF, though I do not recall
anybody trying to seriously persuade IETF on that issue, so I cannot argue
that IETF objected to big keys).

2. Although far too late to fit into NIST PQC procedure, I ask a far-out
question, if only for thoroughness: are there other old, big-key
cryptosystems, previously considered impractical only due to large key size (I
am thinking something like Merkle puzzles), that everybody was too busy to
reconsider and submit?

3. Personally, FWIW, both the big-key and small-key emails convinced me,
evidence at least I am learning new things.



----------------------------------------------------------------------
This transmission (including any attachments) may contain confidential information, privileged material (including material protected by the solicitor-client or other applicable privileges), or constitute non-public information. Any use of this information by anyone other than the intended recipient is prohibited. If you have received this transmission in error, please immediately reply to the sender and delete this information from your system. Use, dissemination, distribution, or reproduction of this transmission by unintended recipients is not authorized and may be unlawful.

[Christopher Wood]

On Tue, Oct 29, 2019 at 7:08 AM 'David A. Cooper' via pqc-forum
<pqc-...@list.nist.gov> wrote:
>
> My opinion on this topic doesn't really matter. It's one thing to argue that a particular scheme could be more efficient if keys were distributed in a certain manner and were reused for a period of time. However, it doesn't matter what could be, if those who will actually be implementing these protocols will not accept it.
>
> While the current installed base may reuse (EC)DH keys on the server side, it is not clear how that would translate to the use of the KEMs that are being considered as part of NISTPQC. For the KEMs, the most straightforward implementation under TLS 1.3 would be for the client to generate the key pair and for the server to respond with the ciphertext. The server wouldn't be generating any key pairs.
>
> One could certainly imagine a version of TLS in which the proposed scheme would work. The proposal to store a server's public key in DNS and then use that key to establish the session keys sounds exactly like what is proposed with ESNI. In ESNI a key agreement is performed using a server key that is stored in the DNS and an ephemeral key that is generated by the client. The resulting shared secret is used to derive a session key, which is used to encrypt the server's name in the TLS handshake. That same shared secret could also be used to derive a pre-shared key, which could be used in TLS's pre-shared key mode to derive the session keys used to protect application traffic.
>
> Note, however, that while the above idea is rather obvious, to the best of my knowledge it has never been discussed within the IETF TLS working group.

Speaking as a co-chair of the TLS WG, to my knowledge, this is correct.

> The idea could be proposed, but my guess is that it would face strong opposition.

Speaking as a TLS WG participant (no chair hat), I agree. That said,
as you suggest below, it certainly seems appropriate to bring this to
the WG. ESNI is (hopefully) nearing completion, so time is of the
essence. :-)

Best,
Chris

> Even if everyone on this mail list agreed that this proposal was secure, efficient, and easily implementable, would it really matter if those who actually make the decisions about what to implement insist that it is unacceptable to them? Why not present this idea within the appropriate IETF forum(s) to try to find out whether there is any chance of this idea being accepted by those who would have to be convinced to implement it?
>
> I do not understand the suggestion about "an annoying conflict between functionality ... and security." ESNI is only considered to be useful if multiple sites are hosted on one server. If a server only hosts one site, then there is a one-to-one mapping between IP address and server name, and since the IP address is not encrypted, there isn't much benefit in encrypting the server name. What is this conflict and what if the flaw in TLS that is fixable?
>
> On 10/28/19 5:47 PM, D. J. Bernstein wrote:
>
> - IETF has been strongly striving for ephemeral key per TLS connection
> and strongly opposed static/long-lived keys for any usecase.
>
> Before this you seemed to be arguing that NISTPQC should limit attention
> to what's currently standardized and deployed, except for swapping out
> the crypto primitives. Here, however, you're arguing that NISTPQC should
> _ignore_ the installed base of working software (from, e.g., Microsoft)
> that does _not_ do what you're advocating, contrary to what a reader
> might expect from the word "strongly".
>
> ...
>
> A couple additional Ops challenges with what you are proposing are
> - With TLS 1.3 and ESNI, an ISP cache would not know what public key
> to serve to a client as everything is encrypted. Serving a public key
> based on destination address will not work because CDNs serve
> multiple destinations from the same location.
>
> ...
> The TLS data flow makes this seem like an annoying conflict between
> functionality (hosting multiple sites on one server) and security
> (encrypting the site name). This is a fixable flaw in TLS.
>
>

> --
> 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/bfc4eff7-1bf6-e788-0cd7-b5db953eedbe%40nist.gov.