[prev in list] [next in list] [prev in thread] [next in thread]
List: cfrg
Subject: Re: [CFRG] [EXT] Re: Google's (current) Threat model for Post-Quantum Cryptography
From: John Mattsson <john.mattsson=40ericsson.com () dmarc ! ietf ! org>
Date: 2024-03-16 10:28:05
Message-ID: GVXPR07MB9678B3B3A960B2F779BC3EB7892F2 () GVXPR07MB9678 ! eurprd07 ! prod ! outlook ! com
[Download RAW message or body]
Hi,
Uri Blumenthal wrote:
> As I already said, people who consider probability of appearance of a
> working CRQC as very low, should not waste their time on PQ crypto
Daniel Bernstein wrote:
> but I don't want post-quantum deployment to be slowed
> down by auditors who think quantum computers will take longer.
I think the probability of a working CRQC in the next 15 years is very
low, but definitly not low enough to not take action. I think many
systems need to migrate to PQC asap. The hardware we are designing
today might still be deployed in 2050.
I think a driving force for many companies will be compliance, where
governments demand quantum-resistance algorithms. CNSA 2.0 already
requires quantum-resistant software/firmware signing to be implemented.
Daniel Bernstein wrote:
> The phrase "security proof" needs to be treated with extreme caution.
> failures of "provably secure" cryptosystems. One common failure
> mode is not actually writing down complete proofs. Another common
> failure mode---for example, the source of the MQDSS failure and
> the FrodoKEM failure---is ignoring quantitative gaps in theorem
> statements.
I agree, but I think an even bigger problem is the gap between
proofs and end users. Even if the proofs are complete and correct
they are typically quite hard for end users to understand. End
users here might be a developer or person in a SDO standardizing
a protocol or API using the cryptographic algorithm. I think
we need more user friendly cryptography, either by making the
cryptographic algorithms more fail safe, or by very clearly
stating the limitations of algorithms. Authors are often very
happy to describe all the good properties of their algorithms
but less happy to describe all the limitations.
Cheers,
John Preuß Mattsson
From: CFRG <cfrg-bounces@irtf.org> on behalf of D. J. Bernstein <djb@cr.yp.to>
Date: Saturday, 16 March 2024 at 19:09
To: cfrg@irtf.org <cfrg@irtf.org>
Subject: Re: [CFRG] [EXT] Re: Google's (current) Threat model for Post-Quantum \
Cryptography [Some people who received this message don't often get email from \
djb@cr.yp.to. Learn why this is important at \
https://aka.ms/LearnAboutSenderIdentification ]
Blumenthal, Uri - 0553 - MITLL writes:
> Lattice-based cryptographic algorithms have been under consideration
> and scrutiny since around 1996,
They've also been continually losing security since then. RC4 was
published in 1994 and has been losing security through a series of 83
papers. Factoring has been studied for much longer and has lost so much
security that an author writing a textbook on applied cryptography can
reasonably decide to skip RSA.
As I wrote before: "The question isn't simply whether a cryptographic
problem has had public security review. The question is how well it
_survived_ that review."
More broadly, cryptography varies between (1) systems smashed so quickly
that nobody continues studying them, (2) systems that hold up just fine
against attack, and (3) intermediate systems that seem kind of okay but
keep losing security. The intermediate systems are the best for
academics writing papers but not the best for the users. See Section 3.8
of https://eur02.safelinks.protection.outlook.com/?url=https%3A%2F%2Fcr.yp.to%2Fpapers \
.html%23competitions&data=05%7C02%7Cjohn.mattsson%40ericsson.com%7C7549b14470a7460493f \
808dc4598b774%7C92e84cebfbfd47abbe52080c6b87953f%7C0%7C0%7C638461769444328565%7CUnknow \
n%7CTWFpbGZsb3d8eyJWIjoiMC4wLjAwMDAiLCJQIjoiV2luMzIiLCJBTiI6Ik1haWwiLCJXVCI6Mn0%3D%7C0 \
%7C%7C%7C&sdata=WIwaacZsGe2iIJCBZ%2F%2BizxEObB8OeQE8wZVEXoB%2BGfc%3D&reserved=0<https://cr.yp.to/papers.html#competitions>.
> at which point lattice problems were
> considered well-studied. Some were broken, some remain strong.
The broken examples are a reason to disregard the "well-studied" claims.
As for "remain strong", what does this mean, and which lattice proposals
from 1996 are supposed to qualify?
The 1996 version of the NTRU paper presented, e.g., a cryptosystem with
104-byte public keys that was claimed to provide 2^80 security but
that's actually much easier to break. The paper allowed other parameter
choices, and NTRU has been able to survive every advance in attacks by
changing parameters, but the unbroken parameters provide much lower
security levels against attacks today than against 1996-vintage attacks.
How is this "remain strong"?
> Some of
> those unbroken ones come with security proofs (e.g., Oded Regev, 2005).
The phrase "security proof" needs to be treated with extreme caution.
Qualitatively, what Regev's proof says is that if you're given any
algorithm to break LWE then you can use that algorithm a polynomial
number of times to break some lattice problems. But the polynomial is
very large (as pointed out in \
https://eur02.safelinks.protection.outlook.com/?url=https%3A%2F%2Feprint.iacr.org%2F20 \
16%2F360&data=05%7C02%7Cjohn.mattsson%40ericsson.com%7C7549b14470a7460493f808dc4598b77 \
4%7C92e84cebfbfd47abbe52080c6b87953f%7C0%7C0%7C638461769444336902%7CUnknown%7CTWFpbGZs \
b3d8eyJWIjoiMC4wLjAwMDAiLCJQIjoiV2luMzIiLCJBTiI6Ik1haWwiLCJXVCI6Mn0%3D%7C0%7C%7C%7C&sd \
ata=aX1zh9hx3Q9HgRG3SVbCjdPsMBSqI9UnC2xAXGHBA%2Fc%3D&reserved=0)<https://eprint.iacr.org/2016/360>, \
and there are further gaps between LWE and cryptosystem security, and nobody
has a proof that those lattice problems are hard to break.
Quantitatively, https://eur02.safelinks.protection.outlook.com/?url=https%3A%2F%2Fepri \
nt.iacr.org%2F2023%2F947&data=05%7C02%7Cjohn.mattsson%40ericsson.com%7C7549b14470a7460 \
493f808dc4598b774%7C92e84cebfbfd47abbe52080c6b87953f%7C0%7C0%7C638461769444342293%7CUn \
known%7CTWFpbGZsb3d8eyJWIjoiMC4wLjAwMDAiLCJQIjoiV2luMzIiLCJBTiI6Ik1haWwiLCJXVCI6Mn0%3D \
%7C0%7C%7C%7C&sdata=xd5W8fwxEXMjOzki%2FRrDzZNI98MkDDr%2B97RMeN2BJ38%3D&reserved=0<https://eprint.iacr.org/2023/947> \
presents the first specific cryptosystem for which Regev's proof (plus proof \
improvements in that paper) actually _seems_ to say something meaningful. The
cryptosystem uses lattices of dimension 79510 and has a proof that if
QROM IND-CCA2 security is below 2^128 then those lattice problems can be
broken more quickly than a model of the cost of attacks known today.
The reason I'm saying "seems" is that lattice problems could be easier
to break than that model. But the more obvious issue is that pretty much
all lattice proposals are using dimensions far below 79510.
A nap.edu committee assessing the quantum threat in 2017 was given an
unfounded---and unfortunately still not withdrawn---claim that lattice
dimensions of "a few thousand" were enough for proofs. I commented in
2019 that "I'd love to see a complete proof handling 10000". I commented
in 2021 that "Existing analysis suggests that it's hopeless to write
down a complete proof applicable to dimensions appearing in NISTPQC
(<=1344)". The source of the original claim responded in
https://eur02.safelinks.protection.outlook.com/?url=https%3A%2F%2Fgroups.google.com \
%2Fa%2Flist.nist.gov%2Fg%2Fpqc-forum%2Fc%2FYx0wZuZP6ag%2Fm%2F3LKBnrbgBwAJ&data=05%7C02 \
%7Cjohn.mattsson%40ericsson.com%7C7549b14470a7460493f808dc4598b774%7C92e84cebfbfd47abb \
e52080c6b87953f%7C0%7C0%7C638461769444346269%7CUnknown%7CTWFpbGZsb3d8eyJWIjoiMC4wLjAwM \
DAiLCJQIjoiV2luMzIiLCJBTiI6Ik1haWwiLCJXVCI6Mn0%3D%7C0%7C%7C%7C&sdata=kig1ozoYqTjGrfeDB \
BbrVsnhxaoGG8BMyBsq0SOVhD8%3D&reserved=0<https://groups.google.com/a/list.nist.gov/g/pqc-forum/c/Yx0wZuZP6ag/m/3LKBnrbgBwAJ>
that this "clearly" wasn't hopeless given a 2018 thesis claiming a proof
for dimension 1460. This response doesn't hold up to examination: the
thesis actually concludes something much weaker than IND-CCA2 security,
and starts from an assumption of the form "lattice attacks cost >= X"
where the particular value of X is so high that the assumption is simply
false. The X calculation came from mixing up exact lattice problems with
(much easier) approximate lattice problems.
https://eur02.safelinks.protection.outlook.com/?url=https%3A%2F%2Feprint.iacr.org%2F20 \
19%2F1336&data=05%7C02%7Cjohn.mattsson%40ericsson.com%7C7549b14470a7460493f808dc4598b7 \
74%7C92e84cebfbfd47abbe52080c6b87953f%7C0%7C0%7C638461769444350854%7CUnknown%7CTWFpbGZ \
sb3d8eyJWIjoiMC4wLjAwMDAiLCJQIjoiV2luMzIiLCJBTiI6Ik1haWwiLCJXVCI6Mn0%3D%7C0%7C%7C%7C&s \
data=4M96woBxepKMbx1emvfjGDX3UPdpY2zYUeRJlkBiPaI%3D&reserved=0<https://eprint.iacr.org/2019/1336> \
surveys many examples of failures of "provably secure" cryptosystems. One common \
failure mode is not actually writing down complete proofs. Another common failure \
mode---for example, the source of the MQDSS failure and the FrodoKEM failure---is \
ignoring quantitative gaps in theorem statements. Procedurally, it's clear how to
protect against these failures:
* require claims of provability to be backed by complete proofs;
* carefully check those proofs;
* calculate what the proofs say about proposed parameter sets;
* reject claims of provability for unproven parameter sets.
https://eur02.safelinks.protection.outlook.com/?url=https%3A%2F%2Feprint.iacr.org%2F20 \
10%2F613&data=05%7C02%7Cjohn.mattsson%40ericsson.com%7C7549b14470a7460493f808dc4598b77 \
4%7C92e84cebfbfd47abbe52080c6b87953f%7C0%7C0%7C638461769444355372%7CUnknown%7CTWFpbGZs \
b3d8eyJWIjoiMC4wLjAwMDAiLCJQIjoiV2luMzIiLCJBTiI6Ik1haWwiLCJXVCI6Mn0%3D%7C0%7C%7C%7C&sd \
ata=1RKlgiE1z584Uq4xGK6I9LW9ERu6%2FddDWuGH9j2K%2BN0%3D&reserved=0<https://eprint.iacr.org/2010/613> \
claimed that Regev had shown that LWE was "provably as hard as certain lattice \
problems". The reaction should have been "No, Regev's theorem allows a polynomial \
loss of hardness; also, we don't know how big the polynomial is". Logically, the \
burden has to be on the people claiming provable security to present complete
proofs that directly apply to the proposed parameters.
> Because âEUR" repeating myself again âEUR" if CRQC does not arrive, all the PQ
> stuff is just an extra risk and expenditure
No, this is conflating current risk assessment with retroactive future
assessment of today's risks.
Would it make sense to argue against buying N years of fire insurance by
saying "If in N years we look back and see that there wasn't a fire then
the money will have been wasted"? No. It _can_ make sense to say that
the probability of a fire is too low to justify the expense of fire
insurance; but that's a statement about a-priori probabilities, not
about a-posteriori probabilities that appear after future observations.
> but if it does âEUR" then
> only PQ could save the day because no Classic part of the hybrid would
> survive. I.e., if Kyber is broken âEUR" then with CRQC your data is dead
> regardless of how good your RSA is.
Part of this is correct. If we stick to RSA or ECC then obviously we're
in trouble if the future attacker has a quantum computer. If we pick
Kyber or a hybrid then obviously we're in trouble if the future attacker
has a quantum computer and a break of Kyber.
But, just as obviously, if we pick non-hybrid Kyber then we're in
trouble if the current or future attacker merely has a break of Kyber.
For comparison, a hybrid will stop the current attacker, and will stop
the future attacker if that attacker _doesn't_ have a quantum computer.
The argument that Kyber is as safe as a hybrid relies on ignoring the
value of stopping current attacks and ignoring the possibility of future
attackers without quantum computers. I expect future attackers to have
quantum computers, but I don't want post-quantum deployment to be slowed
down by auditors who think quantum computers will take longer.
As an analogy, imagine the following argument being raised in 2019: "If
SIKE is broken then your data is revealed to a future quantum computer
no matter how good your ECC is. Use pure SIKE, not CECPQ2b." This would
have given user data away to fast attacks published in 2022---whereas
CECPQ2b was retaining the security level of ECC.
> So, if Kyber is too big a risk for you, but CRQC is a concern âEUR" pick a
> PQ KEM that you trust, as hybrid wonâEUR(tm)t help you.
I agree with part of this: looking ahead to quantum computers, we should
never use hybrids as an excuse for cutting corners on the choice of
post-quantum system. \
https://eur02.safelinks.protection.outlook.com/?url=https%3A%2F%2Fcr.yp.to%2Ftalks.htm \
l%232024.01.11&data=05%7C02%7Cjohn.mattsson%40ericsson.com%7C7549b14470a7460493f808dc4 \
598b774%7C92e84cebfbfd47abbe52080c6b87953f%7C0%7C0%7C638461769444359420%7CUnknown%7CTW \
FpbGZsb3d8eyJWIjoiMC4wLjAwMDAiLCJQIjoiV2luMzIiLCJBTiI6Ik1haWwiLCJXVCI6Mn0%3D%7C0%7C%7C \
%7C&sdata=FB1mbfWymNQ0DeEQno8nJg0MABLkdWhE81UD6Icf8Gc%3D&reserved=0<https://cr.yp.to/talks.html#2024.01.11> \
has a slide with title "Always wear your seatbelt" (use hybrids) followed by a slide
with title "Also: try not to crash the car".
The part of Google's blog post saying "if most deployments are in a
hybrid fashion, being able to break the PQC algorithm by itself would
not help until a quantum computer is available, giving the public
several years", in context, sounds to me like it isn't just advertising
seatbelts, but also incorrectly suggesting that car crashes are okay
given that most people are wearing seatbelts.
---D. J. Bernstein
[Attachment #3 (text/html)]
<html xmlns:o="urn:schemas-microsoft-com:office:office" \
xmlns:w="urn:schemas-microsoft-com:office:word" \
xmlns:m="http://schemas.microsoft.com/office/2004/12/omml" \
xmlns="http://www.w3.org/TR/REC-html40"> <head>
<meta http-equiv="Content-Type" content="text/html; charset=iso-8859-1">
<meta name="Generator" content="Microsoft Word 15 (filtered medium)">
<style><!--
/* Font Definitions */
@font-face
{font-family:"Cambria Math";
panose-1:2 4 5 3 5 4 6 3 2 4;}
@font-face
{font-family:Aptos;
panose-1:2 11 0 4 2 2 2 2 2 4;}
/* Style Definitions */
p.MsoNormal, li.MsoNormal, div.MsoNormal
{margin:0cm;
font-size:12.0pt;
font-family:"Aptos",sans-serif;}
a:link, span.MsoHyperlink
{mso-style-priority:99;
color:blue;
text-decoration:underline;}
span.EmailStyle19
{mso-style-type:personal-reply;
font-family:"Aptos",sans-serif;
color:windowtext;}
.MsoChpDefault
{mso-style-type:export-only;
font-size:10.0pt;
mso-ligatures:none;}
@page WordSection1
{size:612.0pt 792.0pt;
margin:72.0pt 72.0pt 72.0pt 72.0pt;}
div.WordSection1
{page:WordSection1;}
--></style>
</head>
<body lang="en-SE" link="blue" vlink="purple" style="word-wrap:break-word">
<div class="WordSection1">
<p class="MsoNormal"><span \
style="font-size:11.0pt;mso-fareast-language:EN-US">Hi,<o:p></o:p></span></p> <p \
class="MsoNormal"><span \
style="font-size:11.0pt;mso-fareast-language:EN-US"><o:p> </o:p></span></p> <p \
class="MsoNormal"><span style="font-size:11.0pt;mso-fareast-language:EN-US">Uri \
Blumenthal wrote:<o:p></o:p></span></p> <p class="MsoNormal"><span \
style="font-size:11.0pt;mso-fareast-language:EN-US">>As I already said, people who \
consider probability of appearance of a<o:p></o:p></span></p> <p \
class="MsoNormal"><span \
style="font-size:11.0pt;mso-fareast-language:EN-US">>working CRQC as very low, \
should not waste their time on PQ crypto<o:p></o:p></span></p> <p \
class="MsoNormal"><span \
style="font-size:11.0pt;mso-fareast-language:EN-US"><o:p> </o:p></span></p> <p \
class="MsoNormal"><span style="font-size:11.0pt;mso-fareast-language:EN-US">Daniel \
Bernstein wrote:<o:p></o:p></span></p> <p class="MsoNormal"><span \
style="font-size:11.0pt;mso-fareast-language:EN-US">>but I don't want post-quantum \
deployment to be slowed<o:p></o:p></span></p> <p class="MsoNormal"><span \
style="font-size:11.0pt;mso-fareast-language:EN-US">>down by auditors who think \
quantum computers will take longer.<o:p></o:p></span></p> <p class="MsoNormal"><span \
style="font-size:11.0pt;mso-fareast-language:EN-US"><o:p> </o:p></span></p> <p \
class="MsoNormal"><span style="font-size:11.0pt;mso-fareast-language:EN-US">I think \
the probability of a working CRQC in the next 15 years is very<o:p></o:p></span></p> \
<p class="MsoNormal"><span style="font-size:11.0pt;mso-fareast-language:EN-US">low, \
but definitly not low enough to not take action. I think many<o:p></o:p></span></p> \
<p class="MsoNormal"><span \
style="font-size:11.0pt;mso-fareast-language:EN-US">systems need to migrate to PQC \
asap. The hardware we are designing<o:p></o:p></span></p> <p class="MsoNormal"><span \
style="font-size:11.0pt;mso-fareast-language:EN-US">today might still be deployed in \
2050.<o:p></o:p></span></p> <p class="MsoNormal"><span \
style="font-size:11.0pt;mso-fareast-language:EN-US"><o:p> </o:p></span></p> <p \
class="MsoNormal"><span style="font-size:11.0pt;mso-fareast-language:EN-US">I think a \
driving force for many companies will be compliance, where<o:p></o:p></span></p> <p \
class="MsoNormal"><span \
style="font-size:11.0pt;mso-fareast-language:EN-US">governments demand \
quantum-resistance algorithms. CNSA 2.0 already<o:p></o:p></span></p> <p \
class="MsoNormal"><span style="font-size:11.0pt;mso-fareast-language:EN-US">requires \
quantum-resistant software/firmware signing to be implemented.<o:p></o:p></span></p> \
<p class="MsoNormal"><span \
style="font-size:11.0pt;mso-fareast-language:EN-US"><o:p> </o:p></span></p> <p \
class="MsoNormal"><span style="font-size:11.0pt;mso-fareast-language:EN-US">Daniel \
Bernstein wrote:<o:p></o:p></span></p> <p class="MsoNormal"><span \
style="font-size:11.0pt;mso-fareast-language:EN-US">>The phrase "security \
proof" needs to be treated with extreme caution.<o:p></o:p></span></p> <p \
class="MsoNormal"><span \
style="font-size:11.0pt;mso-fareast-language:EN-US"><o:p> </o:p></span></p> <p \
class="MsoNormal"><span \
style="font-size:11.0pt;mso-fareast-language:EN-US">>failures of "provably \
secure" cryptosystems. One common failure<o:p></o:p></span></p> <p \
class="MsoNormal"><span style="font-size:11.0pt;mso-fareast-language:EN-US">>mode \
is not actually writing down complete proofs. Another common<o:p></o:p></span></p> <p \
class="MsoNormal"><span \
style="font-size:11.0pt;mso-fareast-language:EN-US">>failure mode---for example, \
the source of the MQDSS failure and<o:p></o:p></span></p> <p class="MsoNormal"><span \
style="font-size:11.0pt;mso-fareast-language:EN-US">>the FrodoKEM failure---is \
ignoring quantitative gaps in theorem<o:p></o:p></span></p> <p \
class="MsoNormal"><span \
style="font-size:11.0pt;mso-fareast-language:EN-US">>statements.<o:p></o:p></span></p>
<p class="MsoNormal"><span \
style="font-size:11.0pt;mso-fareast-language:EN-US"><o:p> </o:p></span></p> <p \
class="MsoNormal"><span style="font-size:11.0pt;mso-fareast-language:EN-US">I agree, \
but I think an even bigger problem is the gap between<o:p></o:p></span></p> <p \
class="MsoNormal"><span style="font-size:11.0pt;mso-fareast-language:EN-US">proofs \
and end users. Even if the proofs are complete and correct<o:p></o:p></span></p> <p \
class="MsoNormal"><span style="font-size:11.0pt;mso-fareast-language:EN-US">they are \
typically quite hard for end users to understand. End<o:p></o:p></span></p> <p \
class="MsoNormal"><span style="font-size:11.0pt;mso-fareast-language:EN-US">users \
here might be a developer or person in a SDO standardizing<o:p></o:p></span></p> <p \
class="MsoNormal"><span style="font-size:11.0pt;mso-fareast-language:EN-US">a \
protocol or API using the cryptographic algorithm. I think<o:p></o:p></span></p> <p \
class="MsoNormal"><span style="font-size:11.0pt;mso-fareast-language:EN-US">we need \
more user friendly cryptography, either by making the<o:p></o:p></span></p> <p \
class="MsoNormal"><span \
style="font-size:11.0pt;mso-fareast-language:EN-US">cryptographic algorithms more \
fail safe, or by very clearly<o:p></o:p></span></p> <p class="MsoNormal"><span \
style="font-size:11.0pt;mso-fareast-language:EN-US">stating the limitations of \
algorithms. Authors are often very<o:p></o:p></span></p> <p class="MsoNormal"><span \
style="font-size:11.0pt;mso-fareast-language:EN-US">happy to describe all the good \
properties of their algorithms<o:p></o:p></span></p> <p class="MsoNormal"><span \
style="font-size:11.0pt;mso-fareast-language:EN-US">but less happy to describe all \
the limitations.<o:p></o:p></span></p> <p class="MsoNormal"><span \
style="font-size:11.0pt;mso-fareast-language:EN-US"><o:p> </o:p></span></p> <p \
class="MsoNormal"><span \
style="font-size:11.0pt;mso-fareast-language:EN-US">Cheers,<o:p></o:p></span></p> <p \
class="MsoNormal"><span style="font-size:11.0pt;mso-fareast-language:EN-US">John \
Preuß Mattsson<o:p></o:p></span></p> <p class="MsoNormal"><span \
style="font-size:11.0pt;mso-fareast-language:EN-US"><o:p> </o:p></span></p> <div \
id="mail-editor-reference-message-container"> <div>
<div style="border:none;border-top:solid #B5C4DF 1.0pt;padding:3.0pt 0cm 0cm 0cm">
<p class="MsoNormal" style="margin-bottom:12.0pt"><b><span style="color:black">From:
</span></b><span style="color:black">CFRG <cfrg-bounces@irtf.org> on behalf of \
D. J. Bernstein <djb@cr.yp.to><br> <b>Date: </b>Saturday, 16 March 2024 at \
19:09<br> <b>To: </b>cfrg@irtf.org <cfrg@irtf.org><br>
<b>Subject: </b>Re: [CFRG] [EXT] Re: Google's (current) Threat model for Post-Quantum \
Cryptography<o:p></o:p></span></p> </div>
<div>
<p class="MsoNormal" style="margin-bottom:12.0pt"><span \
style="font-size:11.0pt">[Some people who received this message don't often get email \
from djb@cr.yp.to. Learn why this is important at <a \
href="https://aka.ms/LearnAboutSenderIdentification">https://aka.ms/LearnAboutSenderIdentification</a> \
]<br> <br>
Blumenthal, Uri - 0553 - MITLL writes:<br>
> Lattice-based cryptographic algorithms have been under consideration<br>
> and scrutiny since around 1996,<br>
<br>
They've also been continually losing security since then. RC4 was<br>
published in 1994 and has been losing security through a series of 83<br>
papers. Factoring has been studied for much longer and has lost so much<br>
security that an author writing a textbook on applied cryptography can<br>
reasonably decide to skip RSA.<br>
<br>
As I wrote before: "The question isn't simply whether a cryptographic<br>
problem has had public security review. The question is how well it<br>
_survived_ that review."<br>
<br>
More broadly, cryptography varies between (1) systems smashed so quickly<br>
that nobody continues studying them, (2) systems that hold up just fine<br>
against attack, and (3) intermediate systems that seem kind of okay but<br>
keep losing security. The intermediate systems are the best for<br>
academics writing papers but not the best for the users. See Section 3.8<br>
of <a href="https://cr.yp.to/papers.html#competitions">https://eur02.safelinks.protect \
ion.outlook.com/?url=https%3A%2F%2Fcr.yp.to%2Fpapers.html%23competitions&data=05%7 \
C02%7Cjohn.mattsson%40ericsson.com%7C7549b14470a7460493f808dc4598b774%7C92e84cebfbfd47 \
abbe52080c6b87953f%7C0%7C0%7C638461769444328565%7CUnknown%7CTWFpbGZsb3d8eyJWIjoiMC4wLj \
AwMDAiLCJQIjoiV2luMzIiLCJBTiI6Ik1haWwiLCJXVCI6Mn0%3D%7C0%7C%7C%7C&sdata=WIwaacZsGe2iIJCBZ%2F%2BizxEObB8OeQE8wZVEXoB%2BGfc%3D&reserved=0</a>.<br>
<br>
> at which point lattice problems were<br>
> considered well-studied. Some were broken, some remain strong.<br>
<br>
The broken examples are a reason to disregard the "well-studied" \
claims.<br> As for "remain strong", what does this mean, and which lattice \
proposals<br> from 1996 are supposed to qualify?<br>
<br>
The 1996 version of the NTRU paper presented, e.g., a cryptosystem with<br>
104-byte public keys that was claimed to provide 2^80 security but<br>
that's actually much easier to break. The paper allowed other parameter<br>
choices, and NTRU has been able to survive every advance in attacks by<br>
changing parameters, but the unbroken parameters provide much lower<br>
security levels against attacks today than against 1996-vintage attacks.<br>
How is this "remain strong"?<br>
<br>
> Some of<br>
> those unbroken ones come with security proofs (e.g., Oded Regev, 2005).<br>
<br>
The phrase "security proof" needs to be treated with extreme caution.<br>
<br>
Qualitatively, what Regev's proof says is that if you're given any<br>
algorithm to break LWE then you can use that algorithm a polynomial<br>
number of times to break some lattice problems. But the polynomial is<br>
very large (as pointed out in <a \
href="https://eprint.iacr.org/2016/360">https://eur02.safelinks.protection.outlook.com \
/?url=https%3A%2F%2Feprint.iacr.org%2F2016%2F360&data=05%7C02%7Cjohn.mattsson%40er \
icsson.com%7C7549b14470a7460493f808dc4598b774%7C92e84cebfbfd47abbe52080c6b87953f%7C0%7 \
C0%7C638461769444336902%7CUnknown%7CTWFpbGZsb3d8eyJWIjoiMC4wLjAwMDAiLCJQIjoiV2luMzIiLC \
JBTiI6Ik1haWwiLCJXVCI6Mn0%3D%7C0%7C%7C%7C&sdata=aX1zh9hx3Q9HgRG3SVbCjdPsMBSqI9UnC2xAXGHBA%2Fc%3D&reserved=0)</a>,
and<br>
there are further gaps between LWE and cryptosystem security, and nobody<br>
has a proof that those lattice problems are hard to break.<br>
<br>
Quantitatively, <a href="https://eprint.iacr.org/2023/947">https://eur02.safelinks.pro \
tection.outlook.com/?url=https%3A%2F%2Feprint.iacr.org%2F2023%2F947&data=05%7C02%7 \
Cjohn.mattsson%40ericsson.com%7C7549b14470a7460493f808dc4598b774%7C92e84cebfbfd47abbe5 \
2080c6b87953f%7C0%7C0%7C638461769444342293%7CUnknown%7CTWFpbGZsb3d8eyJWIjoiMC4wLjAwMDA \
iLCJQIjoiV2luMzIiLCJBTiI6Ik1haWwiLCJXVCI6Mn0%3D%7C0%7C%7C%7C&sdata=xd5W8fwxEXMjOzki%2FRrDzZNI98MkDDr%2B97RMeN2BJ38%3D&reserved=0</a>
presents the first<br>
specific cryptosystem for which Regev's proof (plus proof improvements<br>
in that paper) actually _seems_ to say something meaningful. The<br>
cryptosystem uses lattices of dimension 79510 and has a proof that if<br>
QROM IND-CCA2 security is below 2^128 then those lattice problems can be<br>
broken more quickly than a model of the cost of attacks known today.<br>
<br>
The reason I'm saying "seems" is that lattice problems could be easier<br>
to break than that model. But the more obvious issue is that pretty much<br>
all lattice proposals are using dimensions far below 79510.<br>
<br>
A nap.edu committee assessing the quantum threat in 2017 was given an<br>
unfounded---and unfortunately still not withdrawn---claim that lattice<br>
dimensions of "a few thousand" were enough for proofs. I commented in<br>
2019 that "I'd love to see a complete proof handling 10000". I \
commented<br> in 2021 that "Existing analysis suggests that it's hopeless to \
write<br> down a complete proof applicable to dimensions appearing in NISTPQC<br>
(<=1344)". The source of the original claim responded in<br>
<br>
<a href="https://groups.google.com/a/list.nist.gov/g/pqc-forum/c/Yx0wZuZP6ag/m/3LKBnrbgBwAJ">
https://eur02.safelinks.protection.outlook.com/?url=https%3A%2F%2Fgroups.google.com%2 \
Fa%2Flist.nist.gov%2Fg%2Fpqc-forum%2Fc%2FYx0wZuZP6ag%2Fm%2F3LKBnrbgBwAJ&data=05%7C \
02%7Cjohn.mattsson%40ericsson.com%7C7549b14470a7460493f808dc4598b774%7C92e84cebfbfd47a \
bbe52080c6b87953f%7C0%7C0%7C638461769444346269%7CUnknown%7CTWFpbGZsb3d8eyJWIjoiMC4wLjA \
wMDAiLCJQIjoiV2luMzIiLCJBTiI6Ik1haWwiLCJXVCI6Mn0%3D%7C0%7C%7C%7C&sdata=kig1ozoYqTjGrfeDBBbrVsnhxaoGG8BMyBsq0SOVhD8%3D&reserved=0</a><br>
<br>
that this "clearly" wasn't hopeless given a 2018 thesis claiming a \
proof<br> for dimension 1460. This response doesn't hold up to examination: the<br>
thesis actually concludes something much weaker than IND-CCA2 security,<br>
and starts from an assumption of the form "lattice attacks cost >= \
X"<br> where the particular value of X is so high that the assumption is \
simply<br> false. The X calculation came from mixing up exact lattice problems \
with<br> (much easier) approximate lattice problems.<br>
<br>
<a href="https://eprint.iacr.org/2019/1336">https://eur02.safelinks.protection.outlook \
.com/?url=https%3A%2F%2Feprint.iacr.org%2F2019%2F1336&data=05%7C02%7Cjohn.mattsson \
%40ericsson.com%7C7549b14470a7460493f808dc4598b774%7C92e84cebfbfd47abbe52080c6b87953f% \
7C0%7C0%7C638461769444350854%7CUnknown%7CTWFpbGZsb3d8eyJWIjoiMC4wLjAwMDAiLCJQIjoiV2luM \
zIiLCJBTiI6Ik1haWwiLCJXVCI6Mn0%3D%7C0%7C%7C%7C&sdata=4M96woBxepKMbx1emvfjGDX3UPdpY2zYUeRJlkBiPaI%3D&reserved=0</a>
surveys many examples of failures of<br>
"provably secure" cryptosystems. One common failure mode is not \
actually<br> writing down complete proofs. Another common failure mode---for \
example,<br> the source of the MQDSS failure and the FrodoKEM failure---is \
ignoring<br> quantitative gaps in theorem statements. Procedurally, it's clear how \
to<br> protect against these failures:<br>
<br>
* require claims of provability to be backed by complete proofs;<br>
* carefully check those proofs;<br>
* calculate what the proofs say about proposed parameter sets;<br>
* reject claims of provability for unproven parameter sets.<br>
<br>
<a href="https://eprint.iacr.org/2010/613">https://eur02.safelinks.protection.outlook. \
com/?url=https%3A%2F%2Feprint.iacr.org%2F2010%2F613&data=05%7C02%7Cjohn.mattsson%4 \
0ericsson.com%7C7549b14470a7460493f808dc4598b774%7C92e84cebfbfd47abbe52080c6b87953f%7C \
0%7C0%7C638461769444355372%7CUnknown%7CTWFpbGZsb3d8eyJWIjoiMC4wLjAwMDAiLCJQIjoiV2luMzI \
iLCJBTiI6Ik1haWwiLCJXVCI6Mn0%3D%7C0%7C%7C%7C&sdata=1RKlgiE1z584Uq4xGK6I9LW9ERu6%2FddDWuGH9j2K%2BN0%3D&reserved=0</a>
claimed that Regev had shown that LWE<br>
was "provably as hard as certain lattice problems". The reaction should<br>
have been "No, Regev's theorem allows a polynomial loss of hardness;<br>
also, we don't know how big the polynomial is". Logically, the burden<br>
has to be on the people claiming provable security to present complete<br>
proofs that directly apply to the proposed parameters.<br>
<br>
> Because âEUR" repeating myself again âEUR" if CRQC does not arrive, \
all the PQ<br> > stuff is just an extra risk and expenditure<br>
<br>
No, this is conflating current risk assessment with retroactive future<br>
assessment of today's risks.<br>
<br>
Would it make sense to argue against buying N years of fire insurance by<br>
saying "If in N years we look back and see that there wasn't a fire then<br>
the money will have been wasted"? No. It _can_ make sense to say that<br>
the probability of a fire is too low to justify the expense of fire<br>
insurance; but that's a statement about a-priori probabilities, not<br>
about a-posteriori probabilities that appear after future observations.<br>
<br>
> but if it does âEUR" then<br>
> only PQ could save the day because no Classic part of the hybrid would<br>
> survive. I.e., if Kyber is broken âEUR" then with CRQC your data is \
dead<br> > regardless of how good your RSA is.<br>
<br>
Part of this is correct. If we stick to RSA or ECC then obviously we're<br>
in trouble if the future attacker has a quantum computer. If we pick<br>
Kyber or a hybrid then obviously we're in trouble if the future attacker<br>
has a quantum computer and a break of Kyber.<br>
<br>
But, just as obviously, if we pick non-hybrid Kyber then we're in<br>
trouble if the current or future attacker merely has a break of Kyber.<br>
For comparison, a hybrid will stop the current attacker, and will stop<br>
the future attacker if that attacker _doesn't_ have a quantum computer.<br>
<br>
The argument that Kyber is as safe as a hybrid relies on ignoring the<br>
value of stopping current attacks and ignoring the possibility of future<br>
attackers without quantum computers. I expect future attackers to have<br>
quantum computers, but I don't want post-quantum deployment to be slowed<br>
down by auditors who think quantum computers will take longer.<br>
<br>
As an analogy, imagine the following argument being raised in 2019: "If<br>
SIKE is broken then your data is revealed to a future quantum computer<br>
no matter how good your ECC is. Use pure SIKE, not CECPQ2b." This would<br>
have given user data away to fast attacks published in 2022---whereas<br>
CECPQ2b was retaining the security level of ECC.<br>
<br>
> So, if Kyber is too big a risk for you, but CRQC is a concern âEUR" pick \
a<br> > PQ KEM that you trust, as hybrid wonâEUR(tm)t help you.<br>
<br>
I agree with part of this: looking ahead to quantum computers, we should<br>
never use hybrids as an excuse for cutting corners on the choice of<br>
post-quantum system. <a \
href="https://cr.yp.to/talks.html#2024.01.11">https://eur02.safelinks.protection.outlo \
ok.com/?url=https%3A%2F%2Fcr.yp.to%2Ftalks.html%232024.01.11&data=05%7C02%7Cjohn.m \
attsson%40ericsson.com%7C7549b14470a7460493f808dc4598b774%7C92e84cebfbfd47abbe52080c6b \
87953f%7C0%7C0%7C638461769444359420%7CUnknown%7CTWFpbGZsb3d8eyJWIjoiMC4wLjAwMDAiLCJQIj \
oiV2luMzIiLCJBTiI6Ik1haWwiLCJXVCI6Mn0%3D%7C0%7C%7C%7C&sdata=FB1mbfWymNQ0DeEQno8nJg0MABLkdWhE81UD6Icf8Gc%3D&reserved=0</a>
has a slide<br>
with title "Always wear your seatbelt" (use hybrids) followed by a \
slide<br> with title "Also: try not to crash the car".<br>
<br>
The part of Google's blog post saying "if most deployments are in a<br>
hybrid fashion, being able to break the PQC algorithm by itself would<br>
not help until a quantum computer is available, giving the public<br>
several years", in context, sounds to me like it isn't just advertising<br>
seatbelts, but also incorrectly suggesting that car crashes are okay<br>
given that most people are wearing seatbelts.<br>
<br>
---D. J. Bernstein<o:p></o:p></span></p>
</div>
</div>
</div>
</div>
</body>
</html>
_______________________________________________
CFRG mailing list
CFRG@irtf.org
https://mailman.irtf.org/mailman/listinfo/cfrg
--===============7574937306813454342==--
[prev in list] [next in list] [prev in thread] [next in thread]
Configure |
About |
News |
Add a list |
Sponsored by KoreLogic