Deprecation timeline for quantum-vulnerable cryptography

[John Mattsson]

Hi,

 

My understanding, based on [1], is that NIST (or the Secretary of Commerce, through the Director of NIST) within the next 28 days will release a first proposed timeline for the deprecation of quantum-vulnerable cryptography in standards. I think it is very good with more guidance on this topic, CNSA 2.0 only considers US national security systems.

 

I am looking forward to the anticipated revision of SP 800-57, but I assume the deprecation timeline might be a separate publication. In addition to the risk assessment of quantum attacks, hopefully based on something else than [2], I hope the deprecation timeline will take into consideration the use case (long-term confidentiality (50 years) of high-value targets is _very_ different from short-term authentication of low-value targets). And as explained in [3], the binding property of digital signatures for non-repudiation can be extended.

 

I would like to stress again that the current PQC standards are completely unusable for many constrained radio networks [4]. A requirement to deprecate ECC in these systems before the threat from quantum computers is imminent would significantly lower security by forcing them to switch to symmetric group keys and no perfect forward secrecy. I fully agree that other non-constrained systems should assume a conservative worst-case projection and mitigate accordingly.

 

If the deprecation timeline includes already deployed hardware, I hope the yearly timeline will consider the huge economical costs of replacing existing hardware.

In addition to a proposed timeline for the deprecation, it would be good with guidance on how store-now-decrypt-later attacks can be made harder to mount. If possible, communication channels should deploy fill signaling [3], continuously renegotiating of encryption keys using ephemeral key exchange, and Fully Encrypted Protocols (FEP) making it hard to differentiate between key exchange and data encryption.

 

When NIST revises 800-57, I would like to see:

 

- A timeline for category 1. As there is no consensus on when Moore's law will cease to apply, it might be hard to decide on an end date for category 1, in that case it would be good with a statement like "> 2060" or something like that.

 

- Clearer explanation of Figure 2. I have numerous times seen people claiming that use of 112-bit security for encrypting data (irrespectively of the data lifetime) is NIST approved until 2030. My understanding of 800-57 is that 112-bit security can only be used to protect data that does not need to be protected after 2030. Many readers of 800-57 seems to _only_ look at Table 1. It would be good if lifetime was clearly included in Table 1.

 

- Incorporate the "migration time" as in Mosca's XYZ theorem. Just like quantum computing experts are (according to me) way too optimistic about when a quantum computer can break RSA-2048, most people are way too optimistic on how long time migrating to new crypto algorithms takes.

 

Cheers,

John Preuß Mattsson

Expert Cryptographic Algorithms and Security Protocols, Ericsson

 

[1] https://www.whitehouse.gov/briefing-room/statements-releases/2022/05/04/national-security-memorandum-on-promoting-united-states-leadership-in-quantum-computing-while-mitigating-risks-to-vulnerable-cryptographic-systems/

 

[2] https://globalriskinstitute.org/publication/2023-quantum-threat-timeline-report/

 

[3] http://kth.diva-portal.org/smash/get/diva2:1902626/FULLTEXT01.pdf

 

[4] https://csrc.nist.gov/csrc/media/Events/2022/fourth-pqc-standardization-conference/documents/papers/constrained-radio-networks-pqc2022.pdf

[Stephan Mueller]

Am Mittwoch, 16. Oktober 2024, 20:02:03 MESZ schrieb 'John Mattsson' via pqc-
forum:

Hi 'John,

...

Perhaps you are looking for CNSA 2.0?

https://www.nsa.gov/Cybersecurity/Post-Quantum-Cybersecurity-Resources/

Ciao
Stephan

[D. J. Bernstein]

The requirement is to "release a proposed timeline for the deprecation
of quantum-vulnerable cryptography in standards, with the goal of moving
the maximum number of systems off quantum-vulnerable cryptography within
a decade of the publication of the initial set of standards".

One point to observe about the stated goal is that it doesn't say "all
systems"; it says "the maximum number of systems". Systems that can't
afford to upgrade could validly object to an "all systems" timeline but
can't object to a "maximum number of systems" timeline.

In other words, we don't want post-quantum crypto to wait for every last
straggler to be able to afford it. Future quantum computers mean that we
already have a security problem now. The systems that are doing the best
job of addressing this problem are the ones that are already upgrading
now, which is very much the opposite of waiting. A one-size-fits-all
timeline would be exacerbating the security problem.

A different point to observe about the stated goal is that ECC+PQ does a
better job than pure PQ of serving the goal, since it removes a common
reason for upgrade hesitation (namely: "this PQ system could easily be
less secure than what we have now so it's safer to delay the upgrade").
This is also why almost all PQ deployment so far is ECC+PQ.

I'm concerned that "deprecation of quantum-vulnerable cryptography" will
be taken out of the context of the stated goal. Concretely, I worry that
it will be misinterpreted as

(1) setting a timeline for _all_ systems and
(2) prohibiting not just ECC but also ECC+PQ.

#1 will create an incentive for a slower timeline than necessary. #2
will create unnecessary hesitation and unnecessary security risks.

---D. J. Bernstein

[John Mattsson]

Hi Dan,

 

I agree with everything you say. I think most people agree with the goal of “moving the maximum number of systems off quantum-vulnerable cryptography”.

 

Very important that no country, including the US, prohibits ECC+PQC in any way. I think ECC+PQC should be recommended for most use cases. NSA and GCHQ have argued against hybrid systems. That might make sense for their use cases. Cryptographic implementations for national security systems are developed by teams where money is not an issue, and the implementations are then thoroughly analyzed by experts at NSA and GCHQ. I wish this was the case in all industries and consumer products but that it unfortunately not the case. Almost all attacks on cryptography targets the implementation, not the mathematical problem. We will likely not see any practical theoretical attacks on any of the standardized PQC algorithms. What we will see for certain is a lot of practical attacks on PQC implementations including side-channel attacks. Many attacks today are performed by nation-state cyber actors with huge resources. ECC+PQC is a very cheap insurance that protects against many attacks. For the same reasons the Five Eyes recommend memory safe programming languages, they should recommend hybrid schemes.

 

I disagree with NIST’s plan to not recommend for/against hybrid schemes. I think NIST and other governments should recommend industry and consumer systems to use hybrid schemes where possible.

 

Cheers,

John

[bruno]

Hi john,  Dan, All 

Thanks John, for the heads-up about `depreciation timeline`.

After elaborating <> scenario based on risks and my understanding, I also do not see easily the rational to not recommend to move to ECC+PQC. So if there is please (ALL) let us know? we need to understand to drive the strategy.

I think I understand the challenges with PKI (Hybrid, Chameleon or composite) from security/complexity point of view i.e. (EUF-CMA, Non -Separability)/ Impact of the change.

But if the impact is `massive`  what is the rational to not implement the best of the controls and not recommend hybrid or composite?

I am writing it quickly but I failed on Level of Assurance approach to agree on PQC only. I landed on ECC+ PQC.  The rational looks to me like, we should do the best because the impact is High/ Very High. Means the cost of the impact is massive so we should do the best to mitigate it.

I also think the 'NSS' wording might be confusing for other parties not in US.  So if there is specific requirements for NSS and US may be they could be `quoted`/motivated/articulated.

'US' might be only in the NIST's scope but for instance us in AU we do follow so it would be awesome to get `guidance` with the timeline depreciation notes...

Regards

--
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/GVXPR07MB967812501493BB50945B0B8889472%40GVXPR07MB9678.eurprd07.prod.outlook.com.

[John Mattsson]

>is particularly difficult for products that aim to target both the NSS and enterprise spaces

 

It is also very difficult for products that aim to target both US and Europe. Most European governments say that hybrid is a must. With IETF, enterprise, European governments, and many industries going for hybrid, we will mainly do hybrid. We think hybrid is the right approach for most use cases. If you don’t like hybrid, you can see ECC as a non-security part of the implementation.

 

When we transition to PQC, we will also try to transition as much as possible to SHA-3/SHAKE/cSHAKE/KMAC. All ML-KEM and ML-DSA implementations implement SHA-3. SHA-3 is also much easier to protect against side-channel attacks. We think side-channel mitigation is important.

 

We will also transition to x25519, x448, Ed25519, and Ed448 as much as possible. Requiring public-key validation is not a robust design. There is a huge amount of impelentations that skip  public-key validation.

 

Cheers,

John

 

From: COSTA Graham <graham...@thalesgroup.com>
Date: Thursday, 17 October 2024 at 13:21
To: bruno <bruno.p...@gmail.com>, pqc-...@list.nist.gov <pqc-...@list.nist.gov>, John Mattsson <john.m...@ericsson.com>
Subject: RE: [pqc-forum] Re: Deprecation timeline for quantum-vulnerable cryptography

You don't often get email from graham...@thalesgroup.com. Learn why this is important

THALES GROUP LIMITED DISTRIBUTION to email recipients

 

The CNSA 2.0 stance on ‘only’ PQC with no exceptions is particularly difficult for products that aim to target both the NSS and enterprise spaces. While we can often address this for protocols through crypto-agility and cipher suites for key establishment, features like code-signing present a real challenge if we are explicitly told that we’re not allowed to use ECC+PQC.

To view this discussion on the web visit https://groups.google.com/a/list.nist.gov/d/msgid/pqc-forum/63318607-4aeb-4279-ab06-709306d85a9f%40gmail.com.

[B P]

Hi Uri,  I think when AES became standardised DES was already broken.  That s why i understand there was no need to have this safety hybrid period. May be this timeline depreciation is a good opportunity to explore further this topic (if in scope)?

 

Regards 

On Thu, 17 Oct 2024, 10:57 pm Blumenthal, Uri - 0553 - MITLL, <u...@ll.mit.edu> wrote:

When the industry was moving from becoming-vulnerable DES to AES - why wasn’t a “hybrid” spring proposed and insisted upon? Just super-encrypt (or pre-encrypt) with DES in addition to AES? 

—

Regards,

Uri

Secure Resilient Systems and Technologies

MIT Lincoln Laboratory

On Oct 17, 2024, at 06:50, bruno <bruno.p...@gmail.com> wrote:



Hi john, Dan, All Thanks John, for the heads-up about `depreciation timeline`. After elaborating <> scenario based on risks and my understanding, I also do not see easily the rational to not recommend to move to ECC+PQC. So if there is

ZjQcmQRYFpfptBannerStart

This Message Is From an External Sender

This message came from outside the Laboratory.

 

ZjQcmQRYFpfptBannerEnd

[Blumenthal, Uri - 0553 - MITLL]

[COSTA Graham]

THALES GROUP LIMITED DISTRIBUTION to email recipients

 

The CNSA 2.0 stance on ‘only’ PQC with no exceptions is particularly difficult for products that aim to target both the NSS and enterprise spaces. While we can often address this for protocols through crypto-agility and cipher suites for key establishment, features like code-signing present a real challenge if we are explicitly told that we’re not allowed to use ECC+PQC.

 

From: pqc-...@list.nist.gov <pqc-...@list.nist.gov> On Behalf Of bruno
Sent: Thursday, October 17, 2024 11:49 AM
To: pqc-...@list.nist.gov; John Mattsson <john.m...@ericsson.com>
Subject: Re: [pqc-forum] Re: Deprecation timeline for quantum-vulnerable cryptography

 

Hi john,  Dan, All 

To view this discussion on the web visit https://groups.google.com/a/list.nist.gov/d/msgid/pqc-forum/63318607-4aeb-4279-ab06-709306d85a9f%40gmail.com.

[Bas Westerbaan]

Also the practical security of symmetric cryptography is better understood. A better question is why hybrids weren't used when moving to ECC.

Best,

 Bas

To view this discussion on the web visit https://groups.google.com/a/list.nist.gov/d/msgid/pqc-forum/CAFCMCNR71tuXpttjOukcfpt-Z2-Zu0JrunWrvGiwcCGYoLG4hA%40mail.gmail.com.

[Blumenthal, Uri - 0553 - MITLL]

ZjQcmQRYFpfptBannerEnd

Also, the practical security of symmetric cryptography is better understood.

 

Agreed.

 

However, “better” does not mean “perfectly well”. Were there guarantees back then that AES won’t fall to a novel attack, e.g., side-channel?

 

A better question is why hybrids weren't used when moving to ECC.

 

And I’ve asked that one too, a while ago. With the same absence of a decent answer. 😉

 

Hi Uri,  I think when AES became standardised DES was already broken.  That s why i understand there was no need to have this safety hybrid period.

 

Oh no, not quite. Perhaps, I should’ve been more explicit/detailed – when DES showed weaknesses, Triple-DES was used in its place, and was widely believed to remain solid. But a hybrid solution that would involve it was not required.

 

May be this timeline depreciation is a good opportunity to explore further this topic (if in scope)?

 

Perhaps…?

 

 

Regards 

[Deirdre Connolly]

A theory: ECC was smaller than RSA/factoring, so going hybrid would have lost out on the primary advantage of ECC of far fewer bytes for the same level of security 

To view this discussion on the web visit https://groups.google.com/a/list.nist.gov/d/msgid/pqc-forum/CAMjbhoW_V-v9%2B4qMCLQBbN_xdaXR%2BYmpNO0yngieV_02Z53EGw%40mail.gmail.com.

[Brent Kimberley]

A better question is why hybrids weren't used when moving to ECC.

 

And I’ve asked that one too, a while ago. With the same absence of a decent answer. 😉

 

It's likely a case of mandate.  (Double envelope systems have trade-offs.  Those trade-offs require optimization or at the very least a best-effort radar chart.)

---

From: pqc-...@list.nist.gov on behalf of Blumenthal, Uri - 0553 - MITLL
Sent: Friday, October 18, 2024 9:20 AM
To: Bas Westerbaan; B P
Cc: pqc-...@list.nist.gov; John Mattsson
Subject: Re: [EXT] Re: [pqc-forum] Re: Deprecation timeline for quantum-vulnerable cryptography

To view this discussion on the web visit https://groups.google.com/a/list.nist.gov/d/msgid/pqc-forum/BN0P110MB141998CCE9247A1C864B76F09040A%40BN0P110MB1419.NAMP110.PROD.OUTLOOK.COM.
THIS MESSAGE IS FOR THE USE OF THE INTENDED RECIPIENT(S) ONLY AND MAY CONTAIN INFORMATION THAT IS PRIVILEGED, PROPRIETARY, CONFIDENTIAL, AND/OR EXEMPT FROM DISCLOSURE UNDER ANY RELEVANT PRIVACY LEGISLATION. No rights to any privilege have been waived. If you are not the intended recipient, you are hereby notified that any review, re-transmission, dissemination, distribution, copying, conversion to hard copy, taking of action in reliance on or other use of this communication is strictly prohibited. If you are not the intended recipient and have received this message in error, please notify me by return e-mail and delete or destroy all copies of this message.

[D. J. Bernstein]

> > A better question is why hybrids weren't used when moving to ECC.
> And I’ve asked that one too, a while ago. With the same absence of a
> decent answer.

"For the RSA->ECC upgrade there's (1) a stable ECC security picture and
(2) clear performance reasons to not have the ECC signatures accompanied
by RSA signatures. For the post-quantum upgrade, the story is reversed:
the post-quantum security picture isn't stable, and keeping ECC as a
security layer has low cost."

https://mailarchive.ietf.org/arch/msg/cfrg/IDX8_gnK94K2ZlCtkOpBrGyjpiM/

---D. J. Bernstein

[gard...@gmail.com]

As John has said, " Almost all attacks on cryptography targets the implementation, not the mathematical problem.", there is a very real risk that the hybrid logic will be targeted.

As someone who has spent a lot of time implementing software that leverages compliant cryptographic modules, and helping others do the same, I have seen a lot of misuse. I worry that pushing for hybrid approaches will exacerbate this problem and open new vectors for downgrade attacks. 

Cryptography is used because of a duty of care/due diligence around handling data. In the past, it was rational to recommend applying both a compliant (but unsafe) mechanism alongside a 'safe' but non-compliant mechanism to meet legal obligations for safe data handling.

However, today, as we transition to having certified mechanisms, there's little defense-in-depth benefit from combining a 'soon' known-to-be-useless mechanism with one that's simply feared due to newness. I haven't heard a compelling rationale for this approach, though it might be more justifiable when combining two post-quantum algorithms?  

For some systems, the need to transition to Post-Quantum Cryptography (PQC) is somewhat academic due to other layers of security. For instance, in the Authentication/Identity Provider space, a quantum adversary could forge an RSA/ECDSA JWT token in an attempt to bypass security controls, but the service can easily detect the forgery when introspecting it with the Identity Provider. (Note: This is not true for all IdPs; consult your vendors for specifics.)

While Passkeys are currently considered the 'best' authentication method, they would be more vulnerable during the transition because a forged Passkey attestation would be difficult to detect.  Pushing those devices to adopt some sort of hybrid/composite identity for attestation is one approach.  However, this would be more brittle than requiring a diverse set of individual keys that can be used situationally based on changing policy. 

Additionally, if we step away from security/complexity, hybrid approaches use more compute and network resources which has a higher economic and environmental cost. 

[Greg Maxwell]

Widespread use of ECC outside of specialized applications was also
massively delayed due to IPR concerns and other factors, so that once
there was widespread deployment ECC had achieved a higher level of
confidence. There is also the relative closeness of the factoring
problem and the DL problem that can be used to argue against the value
of hybridizing.

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

[Daniel Brown]

Hi Uri,

I find with this thread's answers "decent" and" satisfactory" about past lack of hybrids, especially AES+DES and RSA+ECC.  

I offer further answers.

 

1) Before 2013, the biggest problem was rarity of cryptographic protection.  Encryption is now much more common, so now is a good time to fix the remaining smaller problems (e.g., using hybrid to address risks of new attacks).

2) It was a mistake not to support hybrid PKC earlier (but not unreasonable due to the larger problems above). Suppose that a hybrid of NTRU+ECC+RSA, or rbrn McEliece+ECC+RSA, had been standardized earlier, say in the 2000s. The hybrids would have offered least a little bit of quantum-resistance.  Sure, the PQC parameters or implementations would have been inadequate, but as hybrids, they would be pre-quantum secure.  Fixing the PQC part might have manageable by increasing the parameters and patch implementation or algorithms.  (I.e. lower y in Mosca's x+y=z theorem.)  Usage of broken preliminary PQC might have inspired greater effort towards a more thorough PQC effort.  Note that NTRU was standardized in IEEE P1363 in the early 2000s.

Note: I tried to provide answers similar to (1) and (2) in reply to similar questions, in past CFRG threads:

https://mailarchive.ietf.org/arch/msg/cfrg/xLJzB7AZJqv23uu4rxTMER9tIp8/

3) Regarding AES vs DES, my simplistic view is that they both (a) already have some built-in hybridization of confusion and diffusion, and (b) extremely high performance demands, meaning hybrid adds less value, and has more cost. 

4) Don't forget RC4.   What if TLS had  proactively hybridized RC4+TDES? (Supposed that the performance was acceptable.)  Wouldn't that have saved TLS some ill effects of using RC4? As in (2) above, I'm arguing here that lack of hybrid was a mistake (but not unreasonable).

5) Clarification: Is the objection here is limited to hybrid (strongest-link combos)? Or, is it wider scope in scope, objecting to diversity, i.e. does the objection here also include a preference to use the "best" single algorithm, and ignore the rest?  If so, is standardized diversity (several NIST encryption modes, ChaCha, (DES, RC4, in bygone days), HMAC, GCM, SHA3, Ascon), a mistake (under this objection)?  I've seen other people's objections to optionality, and even to agility, but they seem to independent objections because they are not combined with objections to hybrid.

6) Breaks over the years (especially OCB2, FFDH, RC4, CBC, MD5, SHA-1, ...) have decreased my confidence in long-accepted algorithms, thereby increasing the value I see in hybrid. I tried quantify the general wisdom "security, not obscurity", writing https://eprint.iacr.org/2021/608 which has already been discussed on this list (the gist being its model is too pessimistic and unrealistic, etc.)  To the question at hand: maybe others like me had more confidence in the 2000s about the scrutiny of single algorithms, seeing hybrid as a less valuable addition, hence fewer proposals, etc.

7)  The quantum threat is long-known, but is not enough alone to support AES+DES or ECC+RSA (for past or future proposals).

Best regards,

Dan

[dustin...@nist.gov]

NIST will release a migration document soon in accordance with National Security Memo 10, which John referenced.  This initial document will outline key points for the migration from NIST’s point of view, but will not include firm dates for deprecation of quantum vulnerable algorithms (which will appear in a future revision of SP 800-131a). 

NIST acknowledges the significant challenges involved in migrating the wide range of systems currently relying on public key cryptography. We understand that this transition will require considerable efforts across diverse applications and infrastructures, each with its own set of requirements and constraints.

This message marks the beginning of a broader conversation that we intend to have with industry partners, standards organizations, and relevant agencies. We aim to collaborate closely on the development of a clear approach and realistic timeline for migrating to post-quantum cryptography (PQC). Our objective is to ensure that this process is as smooth and coordinated as possible, balancing the urgency of adopting PQC with the need to minimize disruption across critical systems.

We appreciate your feedback on this topic.

Dustin Moody

NIST PQC

[Tony Arcieri]

A hybrid construction is something you want to deploy when there are threats in your threat model which are covered by one construction and not the other, and vice versa.

This isn't the case for DES and AES: there aren't threats where we would prefer DES to AES. They are both symmetric constructions with similar pitfalls, and with larger key and block sizes AES is always preferable.

Deirdre noted that a hybrid RSA+ECC construction adds little over RSA alone because it still has all the disadvantages of RSA, which outweighs ECC's benefits. Both constructions are based on the same core problem, namely factoring and (EC)DLP respectively as different concrete examples of the hidden subgroup problem, and the big worry is finding a solution to one problem (such as the quantum threat of Shor's algorithm) breaks both systems.

The case for a hybrid ECC+Lattice system is two different threats: hypothetical large quantum computers for ECC, and hypothetical lattice attacks for ML-KEM/ML-DSA. While you can argue the latter may not happen, if they do happen they aren't going to break ECC. Such a hybrid is robust in ways DES+AES or RSA+ECC are not.

To view this discussion on the web visit https://groups.google.com/a/list.nist.gov/d/msgid/pqc-forum/DA44C92C-0666-40FA-8704-711B15784FC2%40ll.mit.edu.

--

Tony Arcieri

[John Mattsson]

Deidre Connolly wrote:

> A theory: ECC was smaller than RSA/factoring, so going hybrid would have lost out on the primary advantage of ECC of far

>fewer bytes for the same level of security 

100%

 

Tony Arcieri wrote:

>Deirdre noted that a hybrid RSA+ECC construction adds little over RSA alone because it still has all the disadvantages of RSA,

>which outweighs ECC's benefits. Both constructions are based on the same core problem, namely factoring and (EC)DLP

>respectively as different concrete examples of the hidden subgroup problem, and the big worry is finding a solution to one

>problem (such as the quantum threat of Shor's algorithm) breaks both systems.

> 

>The case for a hybrid ECC+Lattice system is two different threats: hypothetical large quantum computers for ECC, and

>hypothetical lattice attacks for ML-KEM/ML-DSA. While you can argue the latter may not happen, if they do happen they aren't

>going to break ECC. Such a hybrid is robust in ways DES+AES or RSA+ECC are not.

 

My view is that the main reason to use hybrid schemes are not theoretical attacks but implementation bugs and weaknesses. I have seen deployments of threshold cryptography with RSA+ECC where the hybrid construction saved the day as one of algorithms had a faulty implementation. A hybrid scheme with X25519 or Ed25519 does not cost much and is an excellent defense-in-depth insurance. I think defense-in-depth should be a guiding principle for cybersecurity.

 

Cheers,

John

 

From: Tony Arcieri <bas...@gmail.com>
Date: Friday, 18 October 2024 at 16:07
To: Blumenthal, Uri - 0553 - MITLL <u...@ll.mit.edu>
Cc: bruno <bruno.p...@gmail.com>, pqc-...@list.nist.gov <pqc-...@list.nist.gov>, John Mattsson <john.m...@ericsson.com>
Subject: Re: [EXT] Re: [pqc-forum] Re: Deprecation timeline for quantum-vulnerable cryptography

[John Preuß Mattsson]

Deidre Connolly wrote:

> A theory: ECC was smaller than RSA/factoring, so going hybrid would have lost out on the primary advantage of ECC of far

>fewer bytes for the same level of security 

100%

 

Tony Arcieri wrote:

>Deirdre noted that a hybrid RSA+ECC construction adds little over RSA alone because it still has all the disadvantages of RSA,

>which outweighs ECC's benefits. Both constructions are based on the same core problem, namely factoring and (EC)DLP

>respectively as different concrete examples of the hidden subgroup problem, and the big worry is finding a solution to one

>problem (such as the quantum threat of Shor's algorithm) breaks both systems.

> 

>The case for a hybrid ECC+Lattice system is two different threats: hypothetical large quantum computers for ECC, and

>hypothetical lattice attacks for ML-KEM/ML-DSA. While you can argue the latter may not happen, if they do happen they aren't

>going to break ECC. Such a hybrid is robust in ways DES+AES or RSA+ECC are not.

 

My view is that the main reason to use hybrid schemes are not theoretical attacks but implementation bugs and weaknesses. I have seen deployments of threshold cryptography with RSA+ECC where the hybrid construction saved the day as one of algorithms had a faulty implementation. A hybrid scheme with X25519 or Ed25519 does not cost much and is an excellent defense-in-depth insurance. I think defense-in-depth should be a guiding principle for cybersecurity.

 

Cheers,

John

[Tim Hollebeek]

As someone who was involved in that transition, there are several rather obvious answers. One is that the threat to both was Moore’s Law, and doubling up on the same threat with both a new and an old defense makes less sense than when the threats to each algorithm are different. A second is that the performance ratios between algorithms were less different, which means feasibilities analyses often to very different answers (what is or is not feasible for various use cases and systems is a complicated space that still needs to be more fully explored). There were actually several clever ideas for how to make the DES to AES transition less painful that unfortunately we couldn’t take advantage of because of limitations of the capabilities of secure elements. That is one theme that looks like it is going to repeat itself, as the cryptographic capabilities of secure hardware are not where they need to be yet.

 

The idea that hybrid/composite shouldn’t be used for this transition because there are previous transitions where it wasn’t used is a great way to prevent anything new from ever happening, but beyond that, I’m not sure how much utility the observation has. New technology should be judged on it’s merits, not confronted with a “did we use it in the past?” strawman, which it will always inevitably fail.

 

-Tim

 

From: pqc-...@list.nist.gov <pqc-...@list.nist.gov> On Behalf Of Blumenthal, Uri - 0553 - MITLL
Sent: Thursday, October 17, 2024 7:58 AM
To: bruno <bruno.p...@gmail.com>
Cc: pqc-...@list.nist.gov; John Mattsson <john.m...@ericsson.com>
Subject: Re: [EXT] Re: [pqc-forum] Re: Deprecation timeline for quantum-vulnerable cryptography

 

When the industry was moving from becoming-vulnerable DES to AES - why wasn’t a “hybrid” spring proposed and insisted upon? Just super-encrypt (or pre-encrypt) with DES in addition to AES? 

To view this discussion on the web visit https://groups.google.com/a/list.nist.gov/d/msgid/pqc-forum/DA44C92C-0666-40FA-8704-711B15784FC2%40ll.mit.edu.

[John Gray]

I agree.  I've been wondering if PQ / PQ hybrid constructions will make sense in the future.   As long as the underlying hardness problems are quite different combining them as a hybrid makes a lot of sense. If you just need to protect against implementation bugs, then you also have a valid argument for combining algorithms that may use similar harness problems.  

Interesting to read that an RSA+ECC hybrid saved the day due to implementation bugs. Do you have a reference for that John?

Cheers,

John Gray

To view this discussion on the web visit https://groups.google.com/a/list.nist.gov/d/msgid/pqc-forum/610aa6da-99c6-4f9b-ab6d-0ca7e3d150e2n%40list.nist.gov.

[Daniel Apon]

"My view is that the main reason to use hybrid schemes are not theoretical attacks but implementation bugs and weaknesses."

Just make sure the extended set of code you've introduced, doing your KEX/KEM combining, doesn't have its own implementation bugs and weaknesses!

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

[Bas Westerbaan]

On Tue, Oct 22, 2024 at 3:03 PM Daniel Apon <dapon....@gmail.com> wrote:

"My view is that the main reason to use hybrid schemes are not theoretical attacks but implementation bugs and weaknesses."

Just make sure the extended set of code you've introduced, doing your KEX/KEM combining, doesn't have its own implementation bugs and weaknesses!

Combining KEMs is much easier to get right, then implementing a KEM itself. (I am quite concerned though with some of the more complex proposals for hybrid certificates.)

 

To view this discussion on the web visit https://groups.google.com/a/list.nist.gov/d/msgid/pqc-forum/CAPxHsS%2BHq9GcBWPiHGgj-p01zSw%2BK-8K7oqm2mrpwpkukHewPw%40mail.gmail.com.

[bruno]

Hi all,

may be we should change the topic (not deprecation timeline) to share ideas on hybrid?

Below my mindset

- For KEM (in openssh or tls with browsers as example) hybrid has been used without explicitly composite keys structure. the outcome turn to be similar with an `hybrid` share.  The cost of implementing the control is low so the outcome was a given.
- For digital signature and PKI, this is more complex and deploying trust is hard.  When we talk about hybrid we have (if not doing errors) 3 options: hybrid with a x509 extension, hybrid with Chameleon, Composite. Only Composite provides a strong dual protection bounded to one CA. I came to the point that Composite allows minimal/no change in protocols. IMHO it is more secure, easier than the other `hybrid`. i have also thought on chameleon or hybrid (with extension) that require changes in protocols and are quiet complex with security element to be discussed (critical extension that can be ignored or base certificate type -(from my internal notes). “In hybrid the critical extension should be the PQC and in Chameleon the base should be the non PQC)”. May be you have other references that i missed but i found [1] interesting about the security topic.

That said currently my preference is composite.  I think this is brillant if i am understanding correctly the impact.

- in the future, we could still use ML-DSA + PQC2 when we have another non lattice PQC2 scheme.  We should be agile and implementing now hybrid is in my opinion an advantage for the future. By doing so, means we are able to manage multiple root of trust and shift when need. I think all will be rotating faster and faster so we should prepare to transition more easily that we can today..

All what i am reading add real value to me. I think this looks like a risk appetite discussion to balance security/complexity (cost, delay, risks). risk appetite often change and we are adapting :)

[1] https://eprint.iacr.org/2017/460.pdf

regards