Subject: Re: [CFRG] NSA vs. hybrid

From: Mike Ounsworth <[email-masked]>
Date: Mon, 6 Dec 2021 23:29:56 +0000

> Natanael <[email-masked]> Mon, 06 December 2021 17:09 UTC
> This is straying away from the main topic, but there is "quantum annoyance"
> as a step in between quantum resistant or quantum weak.

> In other words, systems where every session has to be broken individually
> even if you have a quantum computer, rather than just breaking one key once
> and then reading all sessions.

I haven't seen the term "quantum annoyance" before. I like it.

I think we have a bit of a "bike shedding" problem here that discussions like this one seem to inevitably gravitate back to TLS-like protocols; which IMO is the easier of the two problem spaces with "offline" or "asynchronous" protocols being a much harder problem to design and deploy PQ migrations for.
For example the following things don't have "sessions" where you can apply the concept of "quantum annoyance":
* S/MIME emails where you look up the recipient's encryption cert, and sign the message with your signing cert
* Code-signing infrastructures
* Documents signed by an eIDAS digital signature infrastructure

These are cases where the signing / encryption is done and the object sent into the ether to be verified / decrypted by some unknown client potentially years later. The PQ migrations concerns here are both security (longer data shelf-life means higher importance that algorithm(s) chosen at signing / encryption time don't turn out to be flawed hint hint hybrid), as well as interop (we really can't proceed pre-standards because of the multi-vendor nature of most of these environments, not to mention that the "unknown client" factor makes graceful migration mechanisms much more difficult to design).
It's fine that we want to solve PQ migration for TLS / IKE first, but let's not forget that we have this (IMO far more difficult) problem waiting for us around the corner.

---
Mike Ounsworth
Software Security Architect, Entrust

-----Original Message-----
From: CFRG <[email-masked]> On Behalf Of [email-masked]
Sent: December 6, 2021 11:43 AM
To: [email-masked]
Subject: [EXTERNAL] CFRG Digest, Vol 200, Issue 12

WARNING: This email originated outside of Entrust.
DO NOT CLICK links or attachments unless you trust the sender and know the content is safe.

______________________________________________________________________
Send CFRG mailing list submissions to
        [email-masked]

To subscribe or unsubscribe via the World Wide Web, visit
        https://urldefense.com/v3/__https://www.irtf.org/mailman/listinfo/cfrg__;!!FJ-Y8qCqXTj2!IH4lkvnSGWEpPmfUM7KgYGIRp3Qnzdib0uYXyNaP5j2NsST6Oghk2ZmcBVopdE1pe_tX$
or, via email, send a message with subject or body 'help' to
        [email-masked]

You can reach the person managing the list at
        [email-masked]

When replying, please edit your Subject line so it is more specific than "Re: Contents of CFRG digest..."

Today's Topics:

   1. Re: NSA vs. hybrid (Dan Brown)
   2. Re: NSA vs. hybrid (Natanael)
   3. Re: NSA vs. hybrid (Blumenthal, Uri - 0553 - MITLL)

----------------------------------------------------------------------

Message: 1
Date: Mon, 6 Dec 2021 15:19:27 +0000
From: Dan Brown <[email-masked]>
To: "Blumenthal, Uri - 0553 - MITLL" <[email-masked]>, Mike Ounsworth
        <Mike.Ounsworth=[email-masked]>, "[email-masked]"
        <[email-masked]>
Subject: Re: [CFRG] NSA vs. hybrid
Message-ID: <[email-masked]>
Content-Type: text/plain; charset="utf-8"

> -----Original Message-----
> From: Blumenthal, Uri - 0553 - MITLL
> Sent: Saturday, December 4, 2021 8:45 PM ...
> My point is: we "should NOT have layered..." then, and we did not - as
> evidenced by pretty much all of the current IETF and proprietary (that
> I'm aware of) protocols.
> ...
> People who designed IPsec and TLS (presumably as smart and educated as
> we are) understood the concept of combining different algorithms as
> well as we do (it's hard not to, given its age).
> ...
> The common sense prevailed back then, and IMHO it would be better if
> it prevails now.

Not offering hybrid, say NTRU & ECC, in the past put us in this pickle now of the quantum computer attack risk.
Especially, all the forward secrecy obtained in the past from (EC)DHE is now in jeopardy (even for bug-free implementations).
Arguably, it was a smaller bug than others (using http not https, and non-forward-secure key exchange (RSA)).
Certainly, there are applications where the gains from hybrid are outweighed by the cost, but also applications where hybrid is worthwhile.
Hybrid ought to be option, or IETF WGs should use a cost-benefit analysis per application, the CFRG could help there.
(Generally, let's learn from our mistakes. Besides, aren't some users naturally inclined to expect the Internet to maximally secure their data? ;)

----------------------------------------------------------------------
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.
-------------- next part --------------
A non-text attachment was scrubbed...
Name: smime.p7s
Type: application/pkcs7-signature
Size: 6441 bytes
Desc: not available
URL: <https://urldefense.com/v3/__https://mailarchive.ietf.org/arch/browse/cfrg/attachments/20211206/e1994010/attachment.p7s__;!!FJ-Y8qCqXTj2!IH4lkvnSGWEpPmfUM7KgYGIRp3Qnzdib0uYXyNaP5j2NsST6Oghk2ZmcBVopdIqIQ03t$ >

------------------------------

Message: 2
Date: Mon, 6 Dec 2021 18:09:04 +0100
From: Natanael <[email-masked]>
To: "Blumenthal, Uri - 0553 - MITLL" <[email-masked]>
Cc: Phillip Hallam-Baker <[email-masked]>, IRTF CFRG
        <[email-masked]>
Subject: Re: [CFRG] NSA vs. hybrid
Message-ID:
        <CAAt2M180ADofCVAw9DZ_86aNnzUU80rcckCQ=[email-masked]>
Content-Type: text/plain; charset="utf-8"

Den m?n 6 dec. 2021 15:21Blumenthal, Uri - 0553 - MITLL <[email-masked]>
skrev:

> > The other point to consider is that the WebPKI only needs signatures
> > and
> there are other,
>
> > simpler ways to achieve PQC hardening.
>
>
>
> I?m not sure I follow.
>
> In my understanding, PQ hardening (especially for signatures) requires
> using PQ algorithms ? what other ways are there?
>
>
>
> > We could heavily modify Certificate Transparency for instance.
>
>
>
> How would that help??
>

This is straying away from the main topic, but there is "quantum annoyance"
as a step in between quantum resistant or quantum weak.

In other words, systems where every session has to be broken individually even if you have a quantum computer, rather than just breaking one key once and then reading all sessions.

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://urldefense.com/v3/__https://mailarchive.ietf.org/arch/browse/cfrg/attachments/20211206/cd5330e0/attachment.htm__;!!FJ-Y8qCqXTj2!IH4lkvnSGWEpPmfUM7KgYGIRp3Qnzdib0uYXyNaP5j2NsST6Oghk2ZmcBVopdEeLeeWL$ >

------------------------------

Message: 3
Date: Mon, 6 Dec 2021 17:42:18 +0000
From: "Blumenthal, Uri - 0553 - MITLL" <[email-masked]>
To: Natanael <[email-masked]>
Cc: Phillip Hallam-Baker <[email-masked]>, IRTF CFRG
        <[email-masked]>
Subject: Re: [CFRG] NSA vs. hybrid
Message-ID: <[email-masked]>
Content-Type: text/plain; charset="utf-8"

>>> The other point to consider is that the WebPKI only needs signatures
>>> and there are other, simpler ways to achieve PQC hardening.
>>
>> In my understanding, PQ hardening (especially for signatures)
>> requires using PQ algorithms ? what other ways are there?
>>
>>> We could heavily modify Certificate Transparency for instance.
>>?
>> How would that help??
>
> This is straying away from the main topic, but there is "quantum annoyance"
> as a step in between quantum resistant or quantum weak.?

Ah, "quantum annoyance". I did not think it's applicable to signatures.

> In other words, systems where every session has to be broken
> individually even if you have a quantum computer, rather than just
> breaking one key once and then reading all sessions.?

Yes. But as I said, while I have my personal opinion about this defense mechanism, it may work for key exchange, but IMHO not for signatures, unless in some point up the chain a "true" PQ signature is used - and even then, people with sensitive information to protect and worry about, cannot rely on this kind of "annoyance" defense.
-------------- next part --------------
A non-text attachment was scrubbed...
Name: smime.p7s
Type: application/pkcs7-signature
Size: 5249 bytes
Desc: not available
URL: <https://urldefense.com/v3/__https://mailarchive.ietf.org/arch/browse/cfrg/attachments/20211206/1bb177e3/attachment.p7s__;!!FJ-Y8qCqXTj2!IH4lkvnSGWEpPmfUM7KgYGIRp3Qnzdib0uYXyNaP5j2NsST6Oghk2ZmcBVopdJWpIAxF$ >

------------------------------

Subject: Digest Footer

_______________________________________________
CFRG mailing list
[email-masked]
https://urldefense.com/v3/__https://www.irtf.org/mailman/listinfo/cfrg__;!!FJ-Y8qCqXTj2!IH4lkvnSGWEpPmfUM7KgYGIRp3Qnzdib0uYXyNaP5j2NsST6Oghk2ZmcBVopdE1pe_tX$

------------------------------

End of CFRG Digest, Vol 200, Issue 12
*************************************
Any email and files/attachments transmitted with it are confidential and are intended solely for the use of the individual or entity to whom they are addressed. If this message has been sent to you in error, you must not copy, distribute or disclose of the information it contains. Please notify Entrust immediately and delete the message from your system.

---

From: "Blumenthal, Uri - 0553 - MITLL" <[email-masked]>
Date: Tue, 7 Dec 2021 00:27:21 +0000

CRQC (Crypto-Relevant Quantum Computer) is a threat in two ways:
1. Breaking your key exchange and decrypting your confidential information;
2. Forging your digital signature and/or authentication.

For sensitive data, problem (1) is relevant now - because, as you said, ciphertexts could be recorded now and broken/decrypted decade(s) later, when CRQC is available. Hybrid won't help here (and those who don't expect CRQC to arrive, can stay with ECC).

As to (2), it's unclear when we need to start worrying (though, probably, not now). Clearly, it's of no advantage to the adversary to forge my signature now on a TLS session established 10 years ago. It may well be a concern for legal documents - e.g., if somebody 10 years from now forges a signature on a mortgage - but I can't evaluate this risk, as I don't have enough understanding of the field. 

So, "quantum annoyance" is not an answer for me: for short-lived data, I don't care at all (for now) - and for long-lived (presumably important) data I can't rely on "well, they're busy cracking zillions of somebody else's data, and my data's turn may not even come".
--
Regards,
Uri
 
There are two ways to design a system. One is to make it so simple there are obviously no deficiencies.
The other is to make it so complex there are no obvious deficiencies.
                                                                                                                                     -  C. A. R. Hoare

---

From: "Martin Thomson" <[email-masked]>
Date: Tue, 07 Dec 2021 11:41:15 +1100

On Tue, Dec 7, 2021, at 11:27, Blumenthal, Uri - 0553 - MITLL wrote:
> For sensitive data, problem (1) is relevant now - because, as you said, 
> ciphertexts could be recorded now and broken/decrypted decade(s) later, 
> when CRQC is available. Hybrid won't help here (and those who don't 
> expect CRQC to arrive, can stay with ECC).

I'm sorry, is that right?  Are you asserting that a hybrid key exchange can be broken later?  I was under the impression that if I paired ECC with a PQ algorithm (and didn't mess it up) I could get the best of the two, assuming that the KDF and AEAD and whatnot are also OK.

---

From: Andrey Jivsov <[email-masked]>
Date: Mon, 6 Dec 2021 16:44:03 -0800

Firmware singing for long-lived systems, like chips used in cars, falls
under #2, yet the reasoning about relevance and time to worry is the same
as for #1. System built today may be broken 30 years from now, without
possibility to update them.

Fortunately, there is XMSS to solve this problem for firmware signing, and
XMSS should not need a hybrid scheme.

However, I generally support a hybrid scheme for cases like #1, at least as
a "paranoid security" option.

On Mon, Dec 6, 2021 at 4:27 PM Blumenthal, Uri - 0553 - MITLL <
[email-masked]> wrote:

> when CRQC is available. Hybrid won't help here (and those who don't expect
> CRQC to arrive, can stay with ECC).
>
> As to (2), it's unclear when we need to start worrying (though, probably,
> not now). Clearly, it's of no advantage to the adversary to forge my
> signature now on a TLS session established 10 years ago. It may well be a
> concern for legal documents - e.g., if somebody 10 years from now forges a
> signature on a mortgage - but I can't evaluate this risk, as I don't have
> enough understanding of the field.
>
> So, "quantum annoyance" is not an answer for me: for short-lived data, I
> don't care at all (for now) - and for long-lived (presumably important)
> data I can't rely on "well, they're busy cracking zillions of somebody
> else's data, and my data's turn may not even come".
> --
> Regards,
> Uri
>
> https://www.irtf.org/mailman/listinfo/cfrg
>

---

From: "Blumenthal, Uri - 0553 - MITLL" <[email-masked]>
Date: Tue, 7 Dec 2021 00:52:50 +0000

> I'm sorry, is that right?  Are you asserting that a
> hybrid key exchange can be broken later? 

If our PQ algorithms do not hold - absolutely, Hybrid will be broken with CRQC. 

If our PQ algorithms hold - Hybrid holds too, but we don't need it then.

In the end - the fate of Key Exchange rides on whether PQ algorithms will hold.

---

From: Mike Ounsworth <[email-masked]>
Date: Tue, 7 Dec 2021 01:20:36 +0000

I don't think the " PQ algorithms do not hold" case is as absolute as you're claiming:

In cold storage encryption or any kind of public trust signature scenario (ie places where record-now-crack-later doesn't apply):
1) Implementation bugs in either traditional or PQC: hybrid makes these not-immediately-fatal and buys you time to patch and potentially re-protect existing data. (applies to both pre- and post-CRQC scenarios thanks to "quantum annoyance").

In all scenarios:
2) Hybrid (esp. with 3+ algs) allows you to combine multiple PQC algs, spreading out your risk.

---
Mike Ounsworth

-----Original Message-----
From: CFRG <[email-masked]> On Behalf Of Blumenthal, Uri - 0553 - MITLL
Sent: December 6, 2021 6:53 PM
To: Martin Thomson <[email-masked]>; [email-masked]
Subject: [EXTERNAL] Re: [CFRG] NSA vs. hybrid

> > For sensitive data, problem (1) is relevant now - because, as you
> > said, ciphertexts could be recorded now and broken/decrypted
> > decade(s) later, when CRQC is available. Hybrid won't help here (and
> > those who don't expect CRQC to arrive, can stay with ECC).
>
> I'm sorry, is that right?  Are you asserting that a hybrid key
> exchange can be broken later?

---

From: Natanael <[email-masked]>
Date: Tue, 7 Dec 2021 03:00:46 +0100

Den tis 7 dec. 2021 02:21Mike Ounsworth <Mike.Ounsworth=
[email-masked]> skrev:

> In cold storage encryption or any kind of public trust signature scenario
> (ie places where record-now-crack-later doesn't apply):
> 1) Implementation bugs in either traditional or PQC: hybrid makes these
> not-immediately-fatal and buys you time to patch and potentially re-protect
> existing data. (applies to both pre- and post-CRQC scenarios thanks to
> "quantum annoyance").
>
>
> In all scenarios:

And my own main argument, rephrased in the list condensed form;

Most people worry about non quantum adversaries, some worry about both
quantum and non quantum adversaries.

PQ algorithms can break in that 1) they get reduced to classical quantum
weak security, in which case hybrid won't help but where they still resist
classical adversaries.

And 2) they can also break to even classical adversaries, in which case
hybrid does help because it's much less likely that the more well
established algorithms simultaneously break to classical adversaries.

As mentioned before #2 has already been observed. I anticipate to see it
happen again. Just because we failed to prevent a quantum attacker it
doesn't mean all is lost, because most relevant adversaries for most people
are still only classical adversaries. In addition hybrid under #2 raises
the cost of performing the attacks.

As for previous questions from earlier messages on the topic, we did not
use hybrid between RSA and ECC because ECC took so long to deploy that by
the time it was ready for use it was fairly widely trusted already. In
addition, it's fairly meaningless to deploy hybrid between algorithms with
fundamentally equivalent hardness assumptions and shared attacks. Hybrid is
most useful when the risks are different in between the algorithms of
choice.

---

From: "Blumenthal, Uri - 0553 - MITLL" <[email-masked]>
Date: Tue, 7 Dec 2021 02:15:34 +0000

> In all scenarios:
> 2) Hybrid (esp. with 3+ algs) allows you to combine
> multiple PQC algs, spreading out your risk.

Repeating myself, yes it would spread out the risk, but IMHO it is not worth the cost. It has not been done before, and it isn't worth doing now.

Besides, if "combining" was done back in the early 2000, it wouldn't've helped now - because the threat today (CRQC) would break all of them. Now we're talking about some unknown attacks that we *hope* would compromise some algorithms, but not other... What makes one think that the next (after-Quantum) threat wouldn't threaten both our Classic and our PQ?

---

From: Loganaden Velvindron <[email-masked]>
Date: Wed, 8 Dec 2021 10:01:18 +0400

> I'm sorry, is that right?  Are you asserting that a hybrid key exchange can be broken later?  I was under the impression that if I paired ECC with a PQ algorithm (and didn't mess it up) I could get…
I agree with Martin. ECC implementations have gone through a good
amount of review. From an engineering point of view, it is safer to
pair with a PQ implementation to be on the safe side.

---

From: Richard Outerbridge <[email-masked]>
Date: Wed, 8 Dec 2021 01:59:41 -0500

> pair with a PQ implementation to be on the safe side.

As has been noted, so has NTRU gone through a good amount of review,
even more perhaps than Rinjdael by this point in the competition for AES.

Anyone see any serious objection to adoption (it’s already de facto)?
__outer

---

From: Mike Ounsworth <[email-masked]>
Date: Wed, 8 Dec 2021 23:42:43 +0000

> As has been noted, so has NTRU gone through a good amount of review, even more perhaps than Rinjdael by this point in the competition for AES.

I'm probably gonna embarrass myself, but here goes ... The argument that I've heard made is that there's a quantum leap (pun intended) between the complexity of the mathematics of RSA/ECC and NTRU. You can mostly wrap your brain around RSA if your highschool teaches modular arithmetic, and the attacks if you take 2nd year uni group theory. ECC also 2nd year group theory. Lattices, LWE, R-LWE, and especially module-LWE are this esoteric combination of rings, fields, and linear algebra that requires a very specific trajectory of graduate studies (likely over-simplified, apologies in advance).

I took this note during Steven Galbraith's keynote at PQCrypto2016:
"There are only a dozen people in the world (2 in the room) who are experts in all the branches of math and algorithm theory that go into lattice problems, so that poses a big problem in predicting the number of bits of security that these things offer."
(talk recording: https://youtu.be/xpBEgT9xyk8?t=520)

I am most certainly not one of those experts qualified to have an opinion, and I know the situation has improved since 2016, but either way I think NTRU, ECC, and Rijndael are not directly comparable in terms of how "hours of public effort" translate to "confidence".

---
Mike Ounsworth

-----Original Message-----
From: CFRG <[email-masked]> On Behalf Of Richard Outerbridge
Sent: December 8, 2021 1:00 AM
To: Loganaden Velvindron <[email-masked]>
Cc: CFRG <[email-masked]>
Subject: [EXTERNAL] Re: [CFRG] NSA vs. hybrid

> pair with a PQ implementation to be on the safe side.

As has been noted, so has NTRU gone through a good amount of review, even more perhaps than Rinjdael by this point in the competition for AES.

_______________________________________________
CFRG mailing list
[email-masked]
https://urldefense.com/v3/__https://www.irtf.org/mailman/listinfo/cfrg__;!!FJ-Y8qCqXTj2!PeBU3jsCIWp69Veg93PAEmFOTFBs-OzdmMra1UcsT_2I2G-F5pobk90n5uJcMiGF8sSx$
Any email and files/attachments transmitted with it are confidential and are intended solely for the use of the individual or entity to whom they are addressed. If this message has been sent to you in error, you must not copy, distribute or disclose of the information it contains. Please notify Entrust immediately and delete the message from your system.

---

From: "Blumenthal, Uri - 0553 - MITLL" <[email-masked]>
Date: Thu, 9 Dec 2021 01:36:16 +0000

On 12/8/21, 18:44, "CFRG on behalf of Mike Ounsworth" <[email-masked] on behalf of Mike.Ounsworth=[email-masked]> wrote:

> I'm probably gonna embarrass myself, but here goes ... The argument
> that I've heard made is that there's a quantum leap (pun intended)
> between the complexity of the mathematics of RSA/ECC and NTRU.

Strongly disagree.

> You can mostly wrap your brain around RSA if your high school teaches modular arithmetic,
> and the attacks if you take 2nd year uni group theory. ECC also 2nd year group theory.

Yes, it's fairly trivial to understand the basic attacks. If you go through more complicated stuff, like the work of Don Coppersmith - you'll find that the above would probably be insufficient. It's somewhat similar with lattices - see below.

> Lattices, LWE, R-LWE, and especially module-LWE are this esoteric combination of rings,
> fields, and linear algebra that requires a very specific trajectory of graduate studies
> (likely over-simplified, apologies in advance).

IMHO, in general - not true. It's fairly simple on basic level - e.g., LWE, but some attacks are quite subtle.

> "There are only a dozen people in the world (2 in the room) who are
> experts in all the branches of math and algorithm theory that go into
> lattice problems, so that poses a big problem in predicting the number
> of bits of security that these things offer."

He's a co-author of SIKE, one of the PQC finalists, right? And he published a lot on ECC, Hyperelliptic curves, Isogenies, etc.

I don't know what level of expertise Dr. Galbraith meant, but I've heard scientists discussing the strength of the lattice-based problems, and articulating their position pretty reasonably.

And, sorry, it's hard to watch talks. Publications (especially peer-reviewed ones ;), are much better to rely upon. Probably, https://www.math.auckland.ac.nz/~sgal018/PQCrypto.pdf would be easier for people to discuss. Starting with slide 2.

> I am most certainly not one of those experts qualified to have an opinion,
> and I know the situation has improved since 2016,

I'm sure I'm not one of the 12 experts that Dr. Galbraith considered qualified to have
an opinion (on the subject). ;-). 
On the other hand, I'm equally sure his criteria is overly exclusionary.

> .  .  .  but either way I think
> NTRU, ECC, and Rijndael are not directly comparable in terms
> of how "hours of public effort" translate to "confidence".

Do you _fully_ understand the design of AES/Rijndael? And _all_ of the (published) attacks against it? Maybe, you find comfortable determining the strength of EC Supersingular Isogenies-based algorithms? ;-)

---

From: Christopher Peikert <[email-masked]>
Date: Thu, 9 Dec 2021 09:46:41 -0500

On Wed, Dec 8, 2021 at 6:43 PM Mike Ounsworth <Mike.Ounsworth=
[email-masked]> wrote:

> I'm probably gonna embarrass myself, but here goes ... The argument that
> I've heard made is that there's a quantum leap (pun intended) between the
> complexity of the mathematics of RSA/ECC and NTRU. You can mostly wrap your
> brain around RSA if your highschool teaches modular arithmetic, and the
> attacks if you take 2nd year uni group theory. ECC also 2nd year group
> theory. Lattices, LWE, R-LWE, and especially module-LWE are this esoteric
> combination of rings, fields, and linear algebra that requires a very
> specific trajectory of graduate studies (likely over-simplified, apologies
> in advance).
>

It's unfortunate that people have this impression, because it's not true at
all.

Understanding NTRU or (even easier) R-LWE encryption requires just basic
polynomial arithmetic. They can be taught in about an hour to early
undergraduates, or even talented high schoolers (I've handled both).

Understanding ECC seems at least as difficult: one needs the curve equation
and its solutions, the group operation (how points are "added"), the
repeated-doubling algorithm, and Diffie-Hellman-style agreement. This isn't
super-advanced stuff, but it probably takes a couple of hours to convey a
thorough understanding to someone who already knows modular arithmetic.

Comprehending the best *attacks* is an entirely different matter, but
that's true for all of RSA, ECC, and lattices. How many people are experts
in the Number Field Sieve factoring algorithm -- the best attack on RSA?
This is not undergrad-level stuff, by any means. Nor are the best attacks
on lattices, though many experts have been working on them for decades.

No matter the area, the best attacks turn out to be a lot more complicated
than the cryptosystems themselves. But you don't need to understand the
attacks to understand how the schemes work, nor why they appear to be
secure.

Sincerely yours in cryptography,
Chris

---

From: Mike Ounsworth <[email-masked]>
Date: Thu, 9 Dec 2021 16:38:37 +0000

Thanks for the correction Chris!

In that case, I’ve probably been over-weighting that comment from Steven Galbraith in how I think about when lattice cryptosystems will have had “enough review”.

---
Mike Ounsworth

From: Christopher Peikert <christopher.peikert=[email-masked]>
Sent: December 9, 2021 8:47 AM
To: Mike Ounsworth <[email-masked]>
Cc: Richard Outerbridge <[email-masked]>; Loganaden Velvindron <[email-masked]>; CFRG <[email-masked]>
Subject: Re: [CFRG] [EXTERNAL] Re: NSA vs. hybrid

It's unfortunate that people have this impression, because it's not true at all.

Understanding NTRU or (even easier) R-LWE encryption requires just basic polynomial arithmetic. They can be taught in about an hour to early undergraduates, or even talented high schoolers (I've handled both).

Understanding ECC seems at least as difficult: one needs the curve equation and its solutions, the group operation (how points are "added"), the repeated-doubling algorithm, and Diffie-Hellman-style agreement. This isn't super-advanced stuff, but it probably takes a couple of hours to convey a thorough understanding to someone who already knows modular arithmetic.

Comprehending the best *attacks* is an entirely different matter, but that's true for all of RSA, ECC, and lattices. How many people are experts in the Number Field Sieve factoring algorithm -- the best attack on RSA? This is not undergrad-level stuff, by any means. Nor are the best attacks on lattices, though many experts have been working on them for decades.

No matter the area, the best attacks turn out to be a lot more complicated than the cryptosystems themselves. But you don't need to understand the attacks to understand how the schemes work, nor why they appear to be secure.

---

From: Marek Jankowski <[email-masked]>
Date: Thu, 16 Dec 2021 16:47:22 +0100

I would like to share my opinion regarding the thesis presented bellow, as
I think it neglects a major issue which must be taken into account.

On Thu, Dec 2, 2021 at 5:45 PM Blumenthal, Uri - 0553 - MITLL <
[email-masked]> wrote:

> 1.  CRQC arrived, Classic hold against classic attacks,  PQ algorithms
> hold - Hybrid is useless.
> 2. CRQC arrived, Classic hold against classic attacks, PQ algorithms fail
> - Hybrid is useless.
> 3. CRQC arrived, Classic broken against classic attacks,  PQ algorithms
> hold - Hybrid is useless.
> 4. CRQC arrived, Classic hold against classic attacks,  PQ algorithms
> broken - Hybrid useless.
> 5. CRQC doesn’t arrive, Classic hold against classic attacks,  PQ
> algorithms hold - Hybrid is useless.
> 6. CRQC doesn’t arrive, Classic hold against classic attacks,  PQ
> algorithms broken - *Hybrid helps*.
> 7. CRQC doesn’t arrive, Classic broken against classic attacks,  PQ
> algorithms hold - Hybrid is useless.
> 8. CRQC doesn’t arrive, Classic broken against classic attacks,  PQ
> algorithms broken - Hybrid is useless.
>

The most relevant period to consider is between the emerging of PQC
standards and the arrival of CRQC.
According to most estimations, this period will be the next 10-20 years
(see Michele Mosca's post here
https://open-ecosystem.org/articles/whats-your-risk-quantum-computers).
The above analysis considers only two cases: CRQC will arrive "in the near
future" and CRQC will never arrive. This approach neglects the importance
of safe and trusted cryptography in this interim period (which is also the
migration period).

In this period, those are the possibilities for hybrid usefulness:
1. Classic holds (against classic attacks), PQ holds - Hybrid isn't useful.
2. Classic holds, PQ breaks - Hybrid helps.
3. Classic breaks, PQ holds - Hybrid isn't useful.
4. Classic breaks, PQ breaks - Hybrid isn't useful.

Those possibilities aren't equally likely. Specifically, a classical attack
against current classical ciphers seems highly improbable. This means that
3 and 4 are unlikely and shouldn't be meaningfully taken into account.
In this case, 2 is not an unreasonable outcome, which leaves hybridization
in an important position.

> established algorithms simultaneously break to classical adversaries.

I think that this is a valid point as well. Even if 2 happens in a world
with CRQC, it leaves us open to quantum adversaries only. Not the best
scenario, but better than being vulnerable to every cyber-criminal out
there.

Regards,
Marek

---

From: Mike Hamburg <[email-masked]>
Date: Thu, 16 Dec 2021 09:01:58 -0800

Hi all,

Here are my two cents on this issue.

Hybrid cryptosystems would give a modest reduction in the risk of mathematical breakthrough, and on its own I’m not sure whether that’s worth the increased risk of implementation errors.

However, PQ systems will take a while to be implemented and validated on HSMs, and it will take a while to have well-tested defenses against side channel and fault attacks.  So if someone needs these features today, they will have trouble migrating to a postquantum system.  But they might be able to migrate to a hybrid system with the classical part running in the HSM or in a side-channel-protected way, if this can be done in a way that’s at least as secure as the classical system.

I don’t know if that’s a controlling consideration, but we should at least consider it.

Regards,
— Mike

> On Dec 16, 2021, at 7:47 AM, Marek Jankowski <[email-masked]> wrote:
> 
> I would like to share my opinion regarding the thesis presented bellow, as I think it neglects a major issue which must be taken into account.
> 
> On Thu, Dec 2, 2021 at 5:45 PM Blumenthal, Uri - 0553 - MITLL <[email-masked] <mailto:[email-masked]>> wrote:
> 1.  CRQC arrived, Classic hold against classic attacks,  PQ algorithms hold - Hybrid is useless. 
> 2. CRQC arrived, Classic hold against classic attacks, PQ algorithms fail - Hybrid is useless. 
> 3. CRQC arrived, Classic broken against classic attacks,  PQ algorithms hold - Hybrid is useless. 
> 4. CRQC arrived, Classic hold against classic attacks,  PQ algorithms broken - Hybrid useless. 
> 5. CRQC doesn’t arrive, Classic hold against classic attacks,  PQ algorithms hold - Hybrid is useless. 
> 6. CRQC doesn’t arrive, Classic hold against classic attacks,  PQ algorithms broken - Hybrid helps. 
> 7. CRQC doesn’t arrive, Classic broken against classic attacks,  PQ algorithms hold - Hybrid is useless. 
> 8. CRQC doesn’t arrive, Classic broken against classic attacks,  PQ algorithms broken - Hybrid is useless. 
> 
> The most relevant period to consider is between the emerging of PQC standards and the arrival of CRQC.
> According to most estimations, this period will be the next 10-20 years (see Michele Mosca's post here https://open-ecosystem.org/articles/whats-your-risk-quantum-computers <https://open-ecosystem.org/articles/whats-your-risk-quantum-computers>).
> The above analysis considers only two cases: CRQC will arrive "in the near future" and CRQC will never arrive. This approach neglects the importance of safe and trusted cryptography in this interim period (which is also the migration period).
> 
> Those possibilities aren't equally likely. Specifically, a classical attack against current classical ciphers seems highly improbable. This means that 3 and 4 are unlikely and shouldn't be meaningfully taken into account.
> In this case, 2 is not an unreasonable outcome, which leaves hybridization in an important position.
> 
> On Tue, Dec 7, 2021 at 3:01 AM Natanael <[email-masked] <mailto:[email-masked]>> wrote:
> PQ algorithms can break in that 1) they get reduced to classical quantum weak security, in which case hybrid won't help but where they still  resist classical adversaries.
> 
> And 2) they can also break to even classical adversaries, in which case hybrid does help because it's much less likely that the more well established algorithms simultaneously break to classical adversaries. 
> 
> I think that this is a valid point as well. Even if 2 happens in a world with CRQC, it leaves us open to quantum adversaries only. Not the best scenario, but better than being vulnerable to every cyber-criminal out there.
> 
> Regards,
> Marek
> 
> 
> 
> On Tue, Dec 7, 2021 at 3:01 AM Natanael <[email-masked] <mailto:[email-masked]>> wrote:
> 
> 
> Den tis 7 dec. 2021 02:21Mike Ounsworth <Mike.Ounsworth=[email-masked] <mailto:[email-masked]>> skrev:
> Most people worry about non quantum adversaries, some worry about both quantum and non quantum adversaries. 
> 
> PQ algorithms can break in that 1) they get reduced to classical quantum weak security, in which case hybrid won't help but where they still resist classical adversaries.
> 
> And 2) they can also break to even classical adversaries, in which case hybrid does help because it's much less likely that the more well established algorithms simultaneously break to classical adversaries. 
> 
> As mentioned before #2 has already been observed. I anticipate to see it happen again. Just because we failed to prevent a quantum attacker it doesn't mean all is lost, because most relevant adversaries for most people are still only classical adversaries. In addition hybrid under #2 raises the cost of performing the attacks. 
> 
> As for previous questions from earlier messages on the topic, we did not use hybrid between RSA and ECC because ECC took so long to deploy that by the time it was ready for use it was fairly widely trusted already. In addition, it's fairly meaningless to deploy hybrid between algorithms with fundamentally equivalent hardness assumptions and shared attacks. Hybrid is most useful when the risks are different in between the algorithms of choice. 
> [email-masked] <mailto:[email-masked]>
> https://www.irtf.org/mailman/listinfo/cfrg <https://www.irtf.org/mailman/listinfo/cfrg>

---

From: "Blumenthal, Uri - 0553 - MITLL" <[email-masked]>
Date: Thu, 16 Dec 2021 17:24:22 +0000

> Hybrid cryptosystems would give a modest reduction in the risk of mathematical
> breakthrough, and on its own I’m not sure whether that’s worth the increased
> risk of implementation errors.

I agree 100%.

> However, PQ systems will take a while to be implemented and validated on HSMs,
> and it will take a while to have well-tested defenses against side channel and
> fault attacks. 

Again, I concur. 

Though I doubt we're fully done with side channel attacks against symmetric and Classic, so I doubt we'll be done with side channel attacks against PQ. 

> So if someone needs these features today, they will have trouble migrating
> to a postquantum system.  But they might be able to migrate to a hybrid
> system with the classical part running in the HSM or in a
> side-channel-protected way, if this can be done in a way that’s at
> least as secure as the classical system.

You are saying - "those who now use HSM, can still use Classic part on HSM and add PQ part in software"? I don't think it would be acceptable: if you embrace PQ - the only real reason seems to be that you really don't want your _today's_ data to become exposed (much?) later, when CRQC arrives. In that case, your combination won't work: CRQC would break the Classic part regardless of HSM. And if one does not worry about data lifetime - then there's no reason to add PQ now.

> I don’t know if that’s a controlling consideration, but we should

Consideration-wise, I'd say - not for me. If I have a "secure" box that performs crypto computations (you may call it "HSM" ;), then PQ would go there too. 

Makes sense?

On Dec 16, 2021, at 7:47 AM, Marek Jankowski <mailto:[email-masked]> wrote:

On Thu, Dec 2, 2021 at 5:45 PM Blumenthal, Uri - 0553 - MITLL <mailto:[email-masked]> wrote:

The most relevant period to consider is between the emerging of PQC standards and the arrival of CRQC.
According to most estimations, this period will be the next 10-20 years (see Michele Mosca's post here https://open-ecosystem.org/articles/whats-your-risk-quantum-computers).
The above analysis considers only two cases: CRQC will arrive "in the near future" and CRQC will never arrive. This approach neglects the importance of safe and trusted cryptography in this interim period (which is also the migration period).

On Tue, Dec 7, 2021 at 3:01 AM Natanael <mailto:[email-masked]> wrote:
PQ algorithms can break in that 1) they get reduced to classical quantum weak security, in which case hybrid won't help but where they still resist classical adversaries.

Regards,
Marek

On Tue, Dec 7, 2021 at 3:01 AM Natanael <mailto:[email-masked]> wrote:

Den tis 7 dec. 2021 02:21Mike Ounsworth <Mike.Ounsworth=mailto:[email-masked]> skrev:
I don't think the " PQ algorithms do not hold" case is as absolute as you're claiming:

In all scenarios:

mailto:[email-masked]
mailto:[email-masked]

---

From: Mike Hamburg <[email-masked]>
Date: Thu, 16 Dec 2021 11:01:00 -0800

> You are saying - "those who now use HSM, can still use Classic part on HSM and add PQ part in software"? I don't think it would be acceptable: if you embrace PQ - the only real reason seems to be t…

Yes, but this attack requires the attacker to hack you today to steal your non-HSM postquantum keys, and then also come back with a quantum computer in 10 or 20 years to break the classical components (if the HSM resists the attack).  Similarly with side-channels attacks, the attacker must mount the side-channel attack today on your PQC in order to attack you much later.

This is a much more difficult attack model than “slurp up everything on the internet today, and break inteteresting-seeming things later”.

> Consideration-wise, I'd say - not for me. If I have a "secure" box that performs crypto computations (you may call it "HSM" ;), then PQ would go there too. 

Sure, PQC should eventually go into the secure box, but that may take longer.  This might prevent people who take security very seriously, such that they need HSMs, from deploying PQC.

Cheers,
— Mike

---

From: Natanael <[email-masked]>
Date: Fri, 17 Dec 2021 21:34:15 +0100

Just saw somebody post this from French ANSSI:

https://www.ssi.gouv.fr/en/publication/anssi-views-on-the-post-quantum-cryptography-transition/

Quoting two parts;

> Acknowledging the immaturity of PQC is important: ANSSI will not endorse
any direct drop-in replacement of currently used algorithms in the
short/medium term. However, this immaturity should not serve as an argument
for postponing the first deployments.

And;

> Even though hybridation is a relatively simple construction, ANSSI
emphasizes that the role of hybridation in the cryptographic security is
crucial and will be mandatory for phases 1 and 2 presented in the sequel.
In addition, the implementation security of the hybridation technique
should be also taken in consideration.

> Given that most post-quantum algorithms involve message sizes much larger
than the current pre-quantum schemes, the extra performance cost of an
hybrid scheme remains low in comparison with the cost of the underlying
post-quantum scheme.
> ANSSI believes that this is a reasonable price to pay for guaranteeing an
additional pre-quantum security at least equivalent to the one provided by
current pre-quantum standardized algorithms.

TLDR they plan to require a hybrid approach until PQC alternatives are
sufficiently established (have enough cryptoanalysis to be trusted to be
sufficiently strong).

---

From: Björn Haase <[email-masked]>
Date: Fri, 17 Dec 2021 21:41:37 +0100

Regarding the assessment of the french ANSSI, this matches also the outcome of discussions that I recall from the german counterpart BSI during the last brainpool meetings regarding PQ crypto.

--
Diese Nachricht wurde von meinem Android Mobiltelefon mit WEB.DE Mail gesendet.