Subject: Re: [CFRG] NSA vs. hybrid

From: Marek Jankowski <[email-masked]>
Date: Thu, 2 Dec 2021 12:21:54 +0100

Joining Dan, I too believe that the vetting of PQC algorithms should
originate in a public process, and that NIST has not yet proven we should
rely on the finalists alone. I find it important that CFRG advise upon
hybridization both in KEMs and signatures, although I don't have a strong
opinion in the composite vs multi-certs debate.
In the same context, I worry that not having a FIPS standard for Ed25519,
the result of FIPS 186-5's publication being delayed, might cause a delay
in adoption of PQ+EC hybrid signatures. CFRG should address this issue and
take a proactive stance towards NIST by engaging in discussions regarding
the publication of FIPS 186-5 as well as PQC and hybrid standards later on.

Best regards,
Marek

On Thu, Nov 18, 2021 at 7:20 PM Dan Brown <[email-masked]> wrote:

> > D. J. Bernstein wrote (on Friday, November 12, 2021 4:28 AM)
> >  ...
> > I would like to see CFRG instead advising integration of ECC into all
> post-
> > quantum deployments for the foreseeable future. There's no reason that
> this
> > advice has to wait for NISTPQC standards.
> > ...
>
> I largely agree with the point above (as some might recall from my past
> CFRG
> messages).
>
> Hybrid cryptography in IETF ought to be encouraged by CFRG. At minimum,
> hybrid
> ought to be an option for sensitive applications (high-value data, needing
> long-term protection), where the cost seems worth the benefit.  As an
> exception, an IETF WG with low-value, short-term data and little budget
> for
> cryptography, might opt for a single non-hybrid PQC algorithm option.
>
> Real-time authentication (e.g., signature-based server authentication in
> TLS),
> might have less risk than other applications (e.g., TLS key exchange),
> because
> new attacks discovered in the future (e.g., relevant quantum computer)
> cannot
> retroactively break today's real-time authentication. Nonetheless, hybrid
> signatures may still be worth the cost?
>
> For certificate structuring, I don't know which is better: (1)
> certificates
> with hybrid-signatures, or (2) multiple certificates with a
> single-algorithm
> signatures (or (3)=(1)+(2)), but CFRG could contribute significantly to a
> recommendation on this issue (e.g. comments already made in this thread).
> Perhaps CFRG should defer this more protocol-specific detail to LAMPS?
>
> Organizationally, NIST and IETF could continue to have some interoperable
> cryptography options, while working independently on non-interoperable
> cryptography options (i.e., hybrid interoperability ;).
>
> Best regards,
>
> Dan
>
> PS. A simplistic cost-benefit approach to choosing hybrid cryptography:
> https://eprint.iacr.org/2021/608
> Better methods ought to be possible.   A discussion on this at
> https://groups.google.com/a/list.nist.gov/g/pqc-forum/c/OpFVbuMYk8c
>
>
> ----------------------------------------------------------------------
> 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.
> _______________________________________________
> CFRG mailing list
> [email-masked]
> https://www.irtf.org/mailman/listinfo/cfrg
>

---

From: "Blumenthal, Uri - 0553 - MITLL" <[email-masked]>
Date: Thu, 2 Dec 2021 12:55:06 +0000

NIST did not invent the finalists – some of them have more than two decades of research behind them. Situation looks comparable to that with RSA and ECC when those algorithms were brought into standards.

Thus, I do not support the Hybrid approach.

--

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: CFRG <[email-masked]> on behalf of Marek Jankowski <[email-masked]>
Date: Thursday, December 2, 2021 at 06:23
To: Dan Brown <[email-masked]>
Cc: CFRG <[email-masked]>, "D. J. Bernstein" <[email-masked]>
Subject: Re: [CFRG] NSA vs. hybrid

Joining Dan, I too believe that the vetting of PQC algorithms should originate in a public process, and that NIST has not yet proven we should rely on the finalists alone. I find it important that CFRG advise upon hybridization both in KEMs and signatures, although I don't have a strong opinion in the composite vs multi-certs debate.
In the same context, I worry that not having a FIPS standard for Ed25519, the result of FIPS 186-5's publication being delayed, might cause a delay in adoption of PQ+EC hybrid signatures. CFRG should address this issue and take a proactive stance towards NIST by engaging in discussions regarding the publication of FIPS 186-5 as well as PQC and hybrid standards later on.

Best regards,
Marek

On Thu, Nov 18, 2021 at 7:20 PM Dan Brown <[email-masked]> wrote:

> I would like to see CFRG instead advising integration of ECC into all post-
> quantum deployments for the foreseeable future. There's no reason that this

I largely agree with the point above (as some might recall from my past CFRG 
messages).

Hybrid cryptography in IETF ought to be encouraged by CFRG. At minimum, hybrid 
ought to be an option for sensitive applications (high-value data, needing 
long-term protection), where the cost seems worth the benefit.  As an 
exception, an IETF WG with low-value, short-term data and little budget for 
cryptography, might opt for a single non-hybrid PQC algorithm option.

Real-time authentication (e.g., signature-based server authentication in TLS), 
might have less risk than other applications (e.g., TLS key exchange), because 
new attacks discovered in the future (e.g., relevant quantum computer) cannot 
retroactively break today's real-time authentication. Nonetheless, hybrid
signatures may still be worth the cost?

For certificate structuring, I don't know which is better: (1) certificates 
with hybrid-signatures, or (2) multiple certificates with a single-algorithm 
signatures (or (3)=(1)+(2)), but CFRG could contribute significantly to a 
recommendation on this issue (e.g. comments already made in this thread). 
Perhaps CFRG should defer this more protocol-specific detail to LAMPS?

Best regards,

Dan

----------------------------------------------------------------------
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.
_______________________________________________
CFRG mailing list
[email-masked]
https://www.irtf.org/mailman/listinfo/cfrg

---

From: Soatok Dreamseeker <[email-masked]>
Date: Thu, 2 Dec 2021 08:25:59 -0500

Hi Uri,

On Thu, Dec 2, 2021 at 7:55 AM Blumenthal, Uri - 0553 - MITLL <
[email-masked]> wrote:

> NIST did not invent the finalists – some of them have more than two
> decades of research behind them. Situation looks comparable to that with
> RSA and ECC when those algorithms were brought into standards.
>
>
>
> *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: *CFRG <[email-masked]> on behalf of Marek Jankowski <
> [email-masked]>
> *Date: *Thursday, December 2, 2021 at 06:23
> *To: *Dan Brown <[email-masked]>
> *Cc: *CFRG <[email-masked]>, "D. J. Bernstein" <[email-masked]>
> *Subject: *Re: [CFRG] NSA vs. hybrid
>
>
>

Thanks for sharing. Could you elaborate more on why you do not support the
Hybrid approach? You said "Thus, I do not support the Hybrid approach" but
did not establish a predicate for this conclusion.

Thank you,
Soatok

---

From: "Blumenthal, Uri - 0553 - MITLL" <[email-masked]>
Date: Thu, 2 Dec 2021 16:45:10 +0000

I'll use the NSA term "CRQC" - Cryptographically-Relevant Quantum Computer. I personally believe (based on my weak understanding of the incomplete scientific data - but understanding  that others have probably isn’t much better than mine) that CRQC will be built within the “relevant” (IMHO) time, aka - a matter of a decade or two. 

Basically, my reasoning against the Hybrid is that it is useless in the majority of cases. But it adds complexity to processing, and unnecessary ballast. 

Here are the possibilities and their relation to the usefulness of the Hybrid approach.

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. 

You can see from the above that Hybrid would be of benefit in only one case out of eight, one I personally consider among the least probable. 

Hope this explains my position?

Regards,
Uri 

> On Dec 2, 2021, at 08:27, Soatok Dreamseeker <[email-masked]> wrote:
> 
> 
> Hi Uri,
> 
>> On Thu, Dec 2, 2021 at 7:55 AM Blumenthal, Uri - 0553 - MITLL <[email-masked]> wrote:
> Thanks for sharing. Could you elaborate more on why you do not support the Hybrid approach? You said "Thus, I do not support the Hybrid approach" but did not establish a predicate for this conclusion.
> 
> Thank you,
> Soatok

---

From: Soatok Dreamseeker <[email-masked]>
Date: Thu, 2 Dec 2021 12:14:08 -0500

Hi Uri,

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

> I'll use the NSA term "CRQC" - Cryptographically-Relevant Quantum
> Computer. I personally believe (based on my weak understanding of the
> incomplete scientific data - but understanding  that others have probably
> isn’t much better than mine) that CRQC will be built within the “relevant”
> (IMHO) time, aka - a matter of a decade or two.
>
> Basically, my reasoning against the Hybrid is that it is useless in the
> majority of cases. But it adds complexity to processing, and unnecessary
> ballast.
>
> 6. CRQC doesn’t arrive, Classic hold against classic attacks,  PQ
> algorithms broken - *Hybrid helps*.
> You can see from the above that Hybrid would be of benefit in only one
> case out of eight, one I personally consider among the least probable.
>

Your setup of 8 possible outcomes is reasonable, but I don't believe your
conclusion follows soundly from this premise.

The core of my disagreement is: none of us are omniscient. (If we were,
most cryptography would be useless, and we wouldn't need intelligence
agencies.)

Even if we take the 8 situations you sketched in your email as a given, *we'll
never know which world we're in*. If an intelligence agency (or
significantly sophisticated computer crime syndicate) discovers a classical
exploit against one of the NIST finalists (say, as a result of a novel
mathematical breakthrough that permits accelerated attacks against
lattices), they're strongly incentivized to keep this a secret. (NOBUS
vulnerabilities, etc.)

I'm inclined to agree that, in 1/8 of the worlds, Hybrid helps, and in the
other 7/8 of the other worlds, it doesn't. However, while Hybrid may not
help in those cases, it isn't a clear detriment. This is because the
overwhelming majority of the code needed for hybrid signatures (or, indeed,
hybrid KEMs) are already implemented in cryptography libraries today, so
the hit to code size, attack surface, and complexity is tractable.

Without any mechanism to distinguish between the 8 possible worlds, we
cannot make a strong logical argument either way. We're forced to rely on
inductive reasoning. Naturally, what we end up with is a 12.5% probability
of a security improvement and a 87.5% chance of a zero-sum outcome.

My conclusion, following the premise you shared, is that Hybrid is a modest
insurance policy (against a circumstance we can't guarantee that we won't
fall into due to the perverse incentives of national politics), even if
it's one we're not extremely likely to need.

If you wanted to pose a stronger argument against Hybrid, I think
demonstrating a significant cost and/or downside to Hybrid over doing
nothing would be the best way to make your case.

Regards,
Soatok

---

From: "Blumenthal, Uri - 0553 - MITLL" <[email-masked]>
Date: Thu, 2 Dec 2021 17:27:11 +0000

Who’s to say that an Intel agency or a crime syndicate (oops, I meant “outfit” ;) hasn’t secretly developed a classic exploit against one or more of the currently used Classic asymmetric algorithms?

Regards,
Uri

> On Dec 2, 2021, at 12:15, Soatok Dreamseeker <[email-masked]> wrote:
> 
> 
> Hi Uri,
> 
>> On Thu, Dec 2, 2021 at 11:45 AM Blumenthal, Uri - 0553 - MITLL <[email-masked]> wrote:
> Your setup of 8 possible outcomes is reasonable, but I don't believe your conclusion follows soundly from this premise.
> 
> The core of my disagreement is: none of us are omniscient. (If we were, most cryptography would be useless, and we wouldn't need intelligence agencies.) 
> 
> Even if we take the 8 situations you sketched in your email as a given, we'll never know which world we're in. If an intelligence agency (or significantly sophisticated computer crime syndicate) discovers a classical exploit against one of the NIST finalists (say, as a result of a novel mathematical breakthrough that permits accelerated attacks against lattices), they're strongly incentivized to keep this a secret. (NOBUS vulnerabilities, etc.)
> 
> I'm inclined to agree that, in 1/8 of the worlds, Hybrid helps, and in the other 7/8 of the other worlds, it doesn't. However, while Hybrid may not help in those cases, it isn't a clear detriment. This is because the overwhelming majority of the code needed for hybrid signatures (or, indeed, hybrid KEMs) are already implemented in cryptography libraries today, so the hit to code size, attack surface, and complexity is tractable.
> 
> Without any mechanism to distinguish between the 8 possible worlds, we cannot make a strong logical argument either way. We're forced to rely on inductive reasoning. Naturally, what we end up with is a 12.5% probability of a security improvement and a 87.5% chance of a zero-sum outcome.
> 
> My conclusion, following the premise you shared, is that Hybrid is a modest insurance policy (against a circumstance we can't guarantee that we won't fall into due to the perverse incentives of national politics), even if it's one we're not extremely likely to need.
> 
> If you wanted to pose a stronger argument against Hybrid, I think demonstrating a significant cost and/or downside to Hybrid over doing nothing would be the best way to make your case.
> 
> Regards,
> Soatok

---

From: Natanael <[email-masked]>
Date: Thu, 2 Dec 2021 18:34:15 +0100

> Hope this explains my position?

I disagree with your risk analysis.

The main problem is that we can't predict which of these situations we will
end up in. Simple enumeration doesn't help.

The main issue is that #6 has already been seen today, multiple times, with
algorithms previously expected to hold. That alone should realistically end
the argument that we're ready to deploy exclusively PQ today. It's not a
safe bet to make ourselves dependent on it in advance.

#5 is the only plausible case where betting on hybrid would be considered a
real negative after the fact, and most would complain about performance
more than complexity. And I wouldn't bet on #7 happening (even if it does
you might pick the wrong candidate).

Practically speaking we're dealing with weighing the more likely outcomes
that the specific PQ of choice holds (that's a narrowed version of 1/3,
also 5/7) vs a continuation of #6, that it fails while classic algorithms
remain working. #8 and #4 (should be both breaks?) are IMHO less likely, I
expect to see some kind of surviving asymmetric algorithms in both cases.

#2 still protects against adversaries without quantum computing
capabilities.

Hybrid is a hedged bet, and it's a long term bet - data encrypted now can
still be relevant in two decades before we even know if a CRQC is plausible
at all, but we also don't know which algorithms will survive. Hybrid has a
chance of surviving everything but the nightmare scenario, and is the only
choice that can substantially reduce unknown risks.

Going single algorithm is not just a bet on CRQC vs none, but additionally
a bet on that specific algorithm.

---

From: "Blumenthal, Uri - 0553 - MITLL" <[email-masked]>
Date: Thu, 2 Dec 2021 17:40:05 +0000

Following your logic, why haven’t we been using Hybrid approach for the last two decades? Are we that confident in infallibility of RSA or ECDH(E)?

Regards,
Uri

> On Dec 2, 2021, at 12:35, Natanael <[email-masked]> wrote:
> 
> 
> 
> 
> Den tors 2 dec. 2021 17:45Blumenthal, Uri - 0553 - MITLL <[email-masked]> skrev:
> The main problem is that we can't predict which of these situations we will end up in. Simple enumeration doesn't help. 
> 
> The main issue is that #6 has already been seen today, multiple times, with algorithms previously expected to hold. That alone should realistically end the argument that we're ready to deploy exclusively PQ today. It's not a safe bet to make ourselves dependent on it in advance.
> 
> #5 is the only plausible case where betting on hybrid would be considered a real negative after the fact, and most would complain about performance more than complexity. And I wouldn't bet on #7 happening (even if it does you might pick the wrong candidate). 
> 
> Practically speaking we're dealing with weighing the more likely outcomes that the specific PQ of choice holds (that's a narrowed version of 1/3, also 5/7) vs a continuation of #6, that it fails while classic algorithms remain working. #8 and #4 (should be both breaks?) are IMHO less likely, I expect to see some kind of surviving asymmetric algorithms in both cases. 
> 
> #2 still protects against adversaries without quantum computing capabilities. 
> 
> Hybrid is a hedged bet, and it's a long term bet - data encrypted now can still be relevant in two decades before we even know if a CRQC is plausible at all, but we also don't know which algorithms will survive. Hybrid has a chance of surviving everything but the nightmare scenario, and is the only choice that can substantially reduce unknown risks.
> 
> Going single algorithm is not just a bet on CRQC vs none, but additionally a bet on that specific algorithm.

---

From: Björn Haase <[email-masked]>
Date: Thu, 2 Dec 2021 18:59:28 +0100

Dear Uri,

The point is IMO, what is the reason after all for any PQ algorithm?

Its all about extremely sensitive applications which 1.) could not even tolerate the extremely low risk that a quantum attack on classical crypto becomes practical and 2.) are willing to tolerate the large penilties.

For such a high security application one MUST really take all available mitigation strategies for even the tiniest identified risk IMHO. For instance I'd put that as a must for our country's embassy communication.

And as there is evidence that there IS a risk with any newly implemented crypto primitive, such a high security application needs everything for being on the safe side.

Putting it the other way round. Any actual application that does not need to bother about the risk coming with the newer PQ algorithms could stick with classical crypto, IMHO, and help saving our planet's resources by consuming less energy.

Yours,

Björn

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

Am 02.12.21, 18:35 schrieb Natanael <[email-masked]>:

_______________________________________________ CFRG mailing list [email-masked] https://www.irtf.org/mailman/listinfo/cfrg

---

From: Natanael <[email-masked]>
Date: Thu, 2 Dec 2021 19:33:20 +0100

Hybrid *with what* in the past decades?

The backup algorithm has to plausibly be an actual improvement -
historically any lowered confidence in RSA only led to greater key lengths,
because that was the option that was understood. Performance issues ruled
out most hybrid options and there were no obvious secondary or substitute
algorithm (especially due to patent issues).

PQ algorithms simply haven't had enough cryptoanalysis in the past decades
for us to be confident in them, so the value proposition was missing. That
analysis is building up now, but I don't yet trust any one option enough to
rely on it.

Hybrid choices *today* gives both an additional motivation for the
algorithms to be analyzed further and gives more room for experimentation
with the PQ candidates, and does so with minimal risk. And most systems
where they can be deployed can tolerate the performance hit today.

Den tors 2 dec. 2021 18:40Blumenthal, Uri - 0553 - MITLL <[email-masked]>
skrev:

> Following your logic, why haven’t we been using Hybrid approach for the
> last two decades? Are we that confident in infallibility of RSA or ECDH(E)?
>
> Regards,
> Uri
>
>

---

From: "Blumenthal, Uri - 0553 - MITLL" <[email-masked]>
Date: Thu, 2 Dec 2021 21:22:36 +0000

I’ll constrain myself to Key Agreement algorithms (in some form – i.e., RSA is more of a Key Encapsulation, but…).

Given that the following algorithms have been around for at least 25 years: RSA, DH(E) (or El Gamal), ECDH(E), NTRU (published in 1996), I’d expect to see at least some combinations of the above. By 2010, only NTRU was still patented – and patents did not stop people from using RSA and ECC (though IETF – correctly – did not embrace them until their patents expired).

The backup algorithm has to plausibly be an actual improvement - historically any lowered confidence in RSA only led to greater key lengths, because that was the option that was understood. Performance issues ruled out most hybrid options and there were no obvious secondary or substitute algorithm (especially due to patent issues). 

Respectfully disagree. Performance was fairly comparable, so at worst it would’ve doubled the key exchange duration – probably the same effect as increasing RSA key size. As for obvious secondary or substitute – to me the most obvious choice would be an algorithm from “another” class: if your main algo relies on factoring – pick discrete log-based to back it up, or Lattice-based…

PQ algorithms simply haven't had enough cryptoanalysis in the past decades for us to be confident in them, so the value proposition was missing. 

I’m asking why the current Classic algorithms have not been paired using the same approach – as they have been around from 10 to 25 years longer than, e.g.,  NTRU. 

It’s all about extremely sensitive applications which 1.) could not even tolerate the extremely low risk that a quantum attack on classical crypto becomes practical and 2.) are willing to tolerate the large penalties.

Respectfully disagree on all of the above. (1) I do not consider CRQC to be “extremely low risk” – not for the data that must remain secure for a long time. (2) Some of my applications are pretty sensitive, but they are not able (nor willing) to tolerate large penalties.

For such a high security application one MUST really take all available mitigation strategies for even the tiniest identified risk IMHO. For instance, I'd put that as a must for our country's embassy communication.

Apparently, this is not how things are designed and deployed. I guess it boils down to how much the designers trust their algorithms – but I challenge you to point me at one instance where for security reasons the application uses a Hybrid approach (even symmetric crypto 😊).

Please define “new”. AES (symmetric, granted) is “newer” than NTRU .

First, it looks like Lattice-based crypto consumes much less energy than classical, so dropping 3-4 Kb RSA keys would be helpful to save energy. Second – who says that a 70-year-old algorithm is stronger than 25-years-old? Finally, risk is not an absolute static value – it’s the output of an evaluation. I “bother about the risk” very much – but not blindly grasping at whatever’s available (mean no offense or insult). 

And you still did not answer my question: if an “extremely sensitive” applications (in your opinion) cannot rely on one algorithm that’s “only” 20-25 years old – why didn’t people embrace this approach in 1990-ties (ECC + RSA), or 2005-ish (ECC + RSA or NTRU or such), etc. etc.?

Den tors 2 dec. 2021 18:40Blumenthal, Uri - 0553 - MITLL <[email-masked]> skrev:

Regards,

Uri