Re: [CFRG] NSA vs. hybrid

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 <mjankowski309@gmail.com> 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 <uri@ll.mit.edu <mailto:uri@ll.mit.edu>> 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).
> 
> 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.
> 
> On Tue, Dec 7, 2021 at 3:01 AM Natanael <natanael.l@gmail.com <mailto:natanael.l@gmail.com>> 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 <natanael.l@gmail.com <mailto:natanael.l@gmail.com>> wrote:
> 
> 
> Den tis 7 dec. 2021 02:21Mike Ounsworth <Mike.Ounsworth=40entrust.com@dmarc.ietf.org <mailto:40entrust.com@dmarc.ietf.org>> skrev:
> 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.
> 
> 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. 
> _______________________________________________
> CFRG mailing list
> CFRG@irtf.org <mailto:CFRG@irtf.org>
> https://www.irtf.org/mailman/listinfo/cfrg <https://www.irtf.org/mailman/listinfo/cfrg>
> _______________________________________________
> CFRG mailing list
> CFRG@irtf.org
> https://www.irtf.org/mailman/listinfo/cfrg