Estimates favoring layered diverse PQC

[Dan Brown]

Dear PQC forum,

FYI, in

https://ia.cr/2021/608

is an elementary method to estimate risk of secret and future attacks on crypto, especially PQC.

The main conclusion is to use strongest-link layering of diverse crypto for sensitive data that needs long-term secrecy, with a quantifiable, if simplistic, justification.

For a concrete example, the paper picks some artificial input numbers. The resulting output estimates had the combination ECDH & McEliece & NTRU as minimizing net cost. Adding SIKE would reduce risk, but not enough to outweigh the usage costs.
​​​​​
Experts in this forum could provide input numbers more accurate than I used, with different results.

Best regards,

Dan Brown

----------------------------------------------------------------------
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.

[D. J. Bernstein]

Dan Brown writes:
> https://ia.cr/2021/608

This paper models every cryptosystem as being breakable with enough
thought---i.e., the model simultaneously denies every security
conjecture in the cryptographic literature. The paper's probability
estimates for systems being secretly broken when they aren't publicly
broken then boil down to guesses about relative time allocation between
the attacker and the defender.

For comparison, Section 3.2 of https://cr.yp.to/papers.html#competitions
proposes estimating p(M), the probability of a system being broken
within M months, by taking real data regarding attacks---e.g., MD5's
claim of 2^64 collision security was broken 12 years later. It then
proposes stratifying the analysis to see, e.g., correlations between
speed and brokenness. Unlike 2021/608, this model is compatible with the
idea that cryptographers aren't wrong 100% of the time (p(infinity) can
be below 100%), and is compatible with the idea that system design has
an influence on security.

In this more sophisticated model---and, as far as we know, in reality---
it's entirely possible that minimizing risks means taking one larger
system rather than a hybrid of multiple smaller systems. More generally,
different shapes of the stratified p function have different effects on
how to minimize the product of risks for any particular sum of costs.

I'm also skeptical of the independence assumption in 2021/608. If as a
community we keep splitting efforts---e.g., software efforts---across
several different systems then I'd expect threshold effects and other
nonlinear effects to make the risk of the combined system much higher
than the product of the risks of the individual systems. Section 3.3 of
https://cr.yp.to/papers.html#competitions notes the possibility of a
"critical mass" effect for cryptanalysis (and also notes nonlinear
theories in the opposite direction), while 2021/608 mentions only linear
effects.

I have much smaller concerns with the standard argument for ECC hybrids
as an adoption mechanism, making people feel comfortable that they
aren't losing security compared to their existing ECC deployments. The
ECC deployments are already there, and if there were zero ongoing ECC
work then the hybrids wouldn't trigger any concerns regarding splitting
community effort. My concerns are nonzero here because there actually
_is_ some ongoing ECC work, for example in formal verification; but I
don't see this taking much time away from the harder verification work
in post-quantum cryptography.

---Dan

[Dan Brown]

> From: D. J. Bernstein

>
> Dan Brown writes:
> > https://ia.cr/2021/608
>
> This paper models every cryptosystem as being breakable with enough
> thought---i.e., the model simultaneously denies every security conjecture in
> the cryptographic literature.

[DB] The paper models each conjecture declaring one cryptosystem "unbreakable"
as having nonzero probability of being wrong. (Sections 4.1 and 4.4 also say
that it possible for the conjectures to be right.)

I didn't, and wouldn't, equate a nonzero probability with a denial of a
conjecture.

A major point of the paper is that the probability of all the conjectures
simultaneously being wrong is lower than just one conjecture being wrong.

That all said, I agree the model suggest disappointingly high attack
probabilities, such as the artificial numbers in Table 2. Better input
numbers T (time spent trying but failing to find an attack) might fix this.
Perhaps more sophisticated models say even better things.

[D. J. Bernstein]

Page 10: "The probability of finding no practical attack in time T is: P
= e^(-AT)" where "independent public thought T is the total time spent
trying to break a given scheme"---the time spent looking for an attack
algorithm, not the CPU time spent running the algorithm!

The subsequent calculations start from guesses of the ratio of the
attacker T and the defender T, and draw conclusions regarding the
probability that a scheme unbroken by the defender _within that T_ is
also unbroken by the attacker _within that T_.

These calculations assume A>0. Major steps are false for A=0. Equation
(19) says <= and is correct for A=0, but it's supposedly justifying
equation (6), which instead says = and is very wrong for A=0. Equation
(6) is then used for the main calculations.

So, putting together

* the assumption A>0 that's critical for the paper's calculations and
* the P = e^(-AT) statement on page 10,

we see that, according to the paper's model, for every "given scheme",
the probability of finding no attack against that scheme converges
exponentially to 0 as the attack-finding time T increases. The speed of
convergence depends on the positive parameter A.

As I said, this models every cryptosystem as being breakable with enough

thought---i.e., the model simultaneously denies every security
conjecture in the cryptographic literature.

In case someone misunderstands T as CPU time (which is not what the
paper says, although the T notation could easily confuse people):

* It's of course true that a mindless brute-force search will find
every key eventually, with failure chance e^(-AT) for some tiny A.
Let's not nitpick about key recognizability, equivalent keys, and
so on, and let's ignore the fact that more sophisticated attacks
tend to have sharper success curves.

* Attackers have vastly more CPU time than defenders do. A reasonable
guess for the ratio of the attacker T and the defender T would be
2^20 (which is much higher than what the paper says---not a
surprise since CPU time isn't what the paper is talking about).

* This tells us that a key unbroken by the defender's brute-force
search has _at least_ one chance in a million of being unbroken by
the attacker's brute-force search.

* Changing "at least" to "exactly" (which is also very wrong in
general, and _is_ a flaw in this paper as admitted in Section 4.4,
and is not the main issue I'm raising!) would say that the
attacker's CPU time has chance 99.9999% of breaking this key.

* If one then conflates "key" with "scheme" (which is not what this
paper does) then one concludes that the hybrids recommended in the
paper have >99.999% chance of being broken (which is also not what
this paper says) within the attacker's CPU time.

Starting from this pile of errors one could then recommend achieving a
90% chance of security (which _is_ what this paper concludes for its
recommended hybrid) by piling up millions of independent keys---which
would still allow brute-force searches if the keys can be recognized
independently, and would be a massive waste of resources if they can't.
Existing literature pays much closer attention to attacks and does a
much better job of choosing cryptosystems.

> The paper models each conjecture declaring one cryptosystem "unbreakable"
> as having nonzero probability of being wrong.

If "nonzero" is understood to mean specifically 100%: yes. If it's
understood to allow something smaller: no, this is contradicted by what
the paper says.

What the paper's P = e^(-AT) formula says, when combined with the A>0
assumption that's required for the paper's calculations, is that every
cryptosystem is breakable with enough thought, and that there's constant
chance of finding the break independently for each moment of thinking.

Saying that P is positive for some particular T is saying that the
cryptosystem _isn't broken by this amount of thought_, which is entirely
consistent with saying that it's _breakable with enough thought_.

> I didn't, and wouldn't, equate a nonzero probability with a denial of a
> conjecture.

I agree, but I don't see how this contradicts what I'm saying. This
paper's model implies that the probability of breakability of every
"given scheme" is 100%, not merely "nonzero".

---Dan

[Dan Brown]

Hi Dan,

Your model makes sense too. I recommend others here on the PQC forum to
consider it carefully.

I'm still comparing our models. The unknown parameter A of each scheme in my
model, has the property the expected amount of time before an attack is M=1/A
(in your notation, adjusting units).

Your proposal for one function p() common to all schemes based on observed M
values (ages of attacks), is therefore similar to estimating a prior
distribution on the values of A (as proposed by a random cryptographer). My
model uses no such prior distribution on A, and has no way to allow for
account for a predisposition that A=0, as claimed by conjectures.

This prior distribution buys your model more statistical power. Your model
makes a very reasonable, but extra, assumption. Basically, it is that there
is a pool of cryptographers, of varying (unknown) skills that propose schemes.
A random cryptographer proposing a scheme, leads to a distribution p() on M
(and thus on A). Your model would need to infer p() from the observed data,
smoothing out a histogram of M values, and perhaps projecting to lengthier
time periods (beyond much of the observed data).

Your model has a potentially very effective test-of-time using conditional
probabilities, but its effectiveness depends very much on the function p(). If
p() flattens out in the regions of interest (5-20 years), then the conditional
probabilities are very low -- so, it would be great if you have already
observed this flattening. If p() keeps getting steadily closer to 1, then the
conditional probabilities might remain high.

By comparison, my model treats each scheme as unique. This makes it
under-powered. To make an estimate for a single scheme, it completely ignores
other schemes, and does not attempt to learn from any trends or patterns or
lessons from other schemes, including the ages at which breakable schemes were
seen to be broken. This is partly because I wanted to apply these estimates
to independent schemes, e.g. SIKE and McEliece, and to focus on unbroken
schemes, and felt that unrelated schemes and broken schemes should have little
bearing on, especially McEliece, which pre-dates many of the newer broken
schemes. This uniqueness necessarily contributes to weak inferences, with
wide gaps in the ranges, and therefore high upper bounds on attack
probabilities (the lower bounds are A=0, it would not be prudent to infer
these with such little data). The high upper bounds on attack probabilities
are what leads to a gain from layering diverse cryptography. So, I would
expect your model to favor layering less often than mine.

Best regards,

Dan

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

[D. J. Bernstein]

Table 2 in 2021/608 estimates that there's a

* 94% chance of SIKE being broken,
* 75% chance of NTRU being broken,
* 50% chance of ECDH being broken, and
* 29% chance of McEliece being broken.

These estimates come from the 2021/608 model of 100% _breakability_ of
every cryptosystem after enough thought, plus guesses about the attacker
thought vs. the defender thought for each system.

An independence assumption then multiplies these chances and says "only"
11% chance of an NTRU+ECDH+McEliece hybrid being broken, which of course
sounds much better than 75% or 29%. There's no consideration of the
possibility that using the same cost to scale up a single system could
result in lower attack probabilities.

Earlier discussions here comparing frodokem1344 to, e.g., a
sikep751+kyber1024 hybrid, or to an easy-to-imagine scaled-up kyber2048
rather than a hybrid, were making real efforts to explore the solution
space and to look at what's actually known about costs. Quantitative
risk assessment was missing at that point, but there was subsequent work
in that direction; 2021/608 is a step backwards in the analysis.

Dan Brown writes:
> Your proposal for one function p() common to all schemes based on observed M
> values (ages of attacks)

Section 3.2 of https://cr.yp.to/papers.html#competitions starts with a
p() function common to all schemes, but then considers a refined model
where faster schemes and slower schemes have different functions
(modeling various "reasons for faster proposals to be more likely to be
broken than slower proposals"), and then mentions further stratification
by "the year when a proposal was made".

Obviously this is only the start. For example, it would be useful to
build metrics for how complicated state-of-the-art security analyses
are---e.g., anyone working on pre-quantum discrete logs would agree that
discrete logs for F_{2^n}^* already had a complicated attack surface
before they were smashed; surely we can quantify this somehow---and then
to analyze how well this predicts the probability of a break.

These stratifications are all compatible with saying that cryptographers
aren't wrong 100% of the time, and they're compatible with the idea that
a larger proposal is safer than a similar-cost hybrid of smaller
proposals. So the "all schemes" comment isn't a correct summary of the
modeling difference, and also doesn't correctly pinpoint the source of
the difference in ranges of conclusions regarding hybrids.

> is therefore similar to estimating a prior
> distribution on the values of A (as proposed by a random cryptographer).

I don't see the similarity. The p function carries real information, and
different possibilities for p give different conclusions regarding
hybrids, whereas A has no effect on the 2021/608 conclusions.

I'm assuming here, as in the 2021/608 calculations, that A>0. Allowing
A=0 would change the picture in 2021/608, would say that cryptographers
aren't necessarily 100% wrong in their security conjectures, and would
also remove the justification for the main conclusions in 2021/608.

> Your model would need to infer p() from the observed data,

Right. That's how science works: we look at the facts and try to figure
out what's going on.

It's already known that a real quantum computer would break both 256-bit
ECDH and 2048-bit RSA, for example, so we stratify the risk analysis to
distinguish those from post-quantum proposals. We _don't_ assume that
256-bit ECDH and 2048-bit RSA have independent chances of surviving. I
also don't believe that ECDH+RSA is safer than larger ECDH.

Why doesn't 2021/608 claim that adding RSA-2048 into the recommended
ECDH+McEliece+NTRU hybrid would cheaply chop risks in half? Presumably
the rationale for omitting RSA from the analysis is that 2021/608
requires "diverse" cryptosystems and that the quantum threat to both RSA
and ECDH makes them not "diverse"---so 2021/608 _is_ making inferences
from the observed data, beyond the guesses regarding attacker "thought"
vs. defender "thought". The shared quantum risk is then squeezed into
one bit of information, saying that RSA and ECDH aren't "diverse".

There's a multi-decade history of code attacks being adapted to lattice
attacks. Clearly there's some shared risk. This means that code-based
crypto and lattice-based crypto aren't "diverse" for 2021/608, right?
But then why are NTRU and McEliece listed as "diverse" systems?

Any improvement to the 1/2 in Kuperberg's 2^(O(n^(1/2))) hidden-shift
cost would also mean subexponential lattice attacks. Clearly there's a
shared risk between CSIDH and lattice systems. Does this mean that CSIDH
and lattice systems aren't "diverse" for 2021/608? If not, why not?

---Dan

[Dan Brown]

Dear Dan and PQC forum,

More thoughts about the age/thought-based estimates that feed into the cost
benefit analysis of layering diverse crypto. I hope that this email will help
make things clearer, this time.

First, on quantification, I notice that the methods can be re-expressed in
terms of well-established methods such as survival functions. Second, on
philosophy of what breakable means, and how conjectures are worded, I try to
clarify the distinction between existence of attack algorithms, and real-world
attackers being able to find attack algorithms.

Needless to say, some of these thoughts would not have occurred to me without
Dan Bernstein's criticisms. (E.g. I would have moved on to other more, or
less, important topics.)

1. Quantification and survival functions

Bernstein's initial model, with a single function p(), seems quite similar
1-S(), where S is a survival function
https://en.wikipedia.org/wiki/Survival_function so it seems a sensible
approach, for which there may already exist working tools.

In particular, the Kaplan-Meier estimator
https://en.wikipedia.org/wiki/Kaplan%E2%80%93Meier_estimator would infer,
based on the observation of attacks on schemes, likely suggest that p(M) < 1
for large M, just as Dan predicated. More interestingly, the KM estimator
says that p(M) becomes constant for M larger than the oldest observation. I
think that this is an artefact of the KM estimator. Anyway, with
KM-estimator, the conditional probability estimate for the breakability of the
oldest scheme works out to 0. So, maybe a more cautious estimate than the KM
estimator would be suitable for this application.

The model that I considered in 2021/608 can also be seen in terms of survival
function. It restricts the survival function to be an exponential survival
function (aka Poisson distribution) but allows for a different survival
function S for each cryptographic scheme. This is a one-parameter model. To
infer the parameter, we use one value of input data (the public thought T).
It is possible S(t)=1 for all t, but as a precaution the estimates never infer
this.


2. Philosophy of what counts as breakable, and crypto conjecture wording

In Bernstein's model, "breakable" means p(infinity) = 1, i.e. p(M)->1 as M->
infinity. In particular, breakable includes the case that p(M)<1 for all M,
but p(M) -> 1 (or p(infeasible-M)=1). This grants an attacker an ability to
find an attack that public attackers would never find in practice. For
example, suppose that p(100000) = 0.000001, yet p(10^10^10^10)=1. For now,
let's call this a prescient attacker. In other words, if an attack algorithm
exists, the prescient attacker will find it. As motivation for my choice of
word "prescient", suppose the attacker uses a time machine, travels to a point
when the public finds an attack, and then returns to the present.

Aiming for resistance a prescient attacker is a great precaution. Calling the
existence of a prescient attack "breakable" might be excessive, but of course,
authors are fairly free to define jargon arbitrarily.

In the 2021/608 model, the attackers considered are more limited than the
prescient attacker. All attackers are subject to the same p() that applies to
the defenders. Attacker and defenders are humans, with limited resources.
So, this model ignores the prescient attacker, and does not even attempt to
resist the prescient attacker. In other words, it drops Bernstein's
precaution about resisting a prescient attacker. Actually, the 2021/608
model is more drastic: it assumes that a prescient attacker exists. In other
words, it presumes that any cryptographic scheme is vulnerable to a prescient
attacker. This presumption could itself be considered a precaution, as way of
underestimating the security of the cryptography being studied. Perhaps it is
too harsh an estimate.

Dropping the precaution of demanding resistance to a prescient attacker is
arguably compensated by other precautions in the 2021/608 model. First, the
time input to p() is not calendar time, but rather amount of thought: one can
scale up the attacker's thought t. If we are worried about strong attackers,
though not prescient, boost t to high number. (Here were are of course not
worried about time travelers, but work done in parallel by multiple people, by
extra effort, expertise, etc.) Second, the survival function S()=1-p() is
assumed to be exponential S(t)=e^(-At), allowing p()->1 as t->infinity,
meaning it admits the possibility of a prescient attacker (as mentioned in the
previous paragraph).

Just to nitpick on wordings, the assumed function p() = 1 - e^(-At) never hits
"100%" exactly in "enough" time, unless "enough" time includes time t =
infinity, or "100%=99.6%".

Regarding the 2021/608 model impacting security conjectures, Bernstein made a
good point, though I don't agree with Bernstein's wording (see previous
paragraph "100%" and "enough").

The crypto conjectures are often formulated:

There exists no feasible algorithm to break scheme X.

A weakened version of this conjecture would be:

Nobody on earth will find a feasible algorithm to break scheme X.

Ok, "nobody on earth" is not the perfect wording, but I hope you can see what
I am aiming for. In other words, the first conjecture says the prescient
attacker does not exist, the second conjecture does not care whether the
prescient attacker exists.

The first form is cleaner and bolder, and more in line with computer science
practice. But in practice, the two conjectures have about the same real-world
impact, so the wording does not matter. However, this notion of a prescient
attacker does manage the split the hairline between these two wordings.

A cryptographer's main supporting evidence for either conjecture might be that
cryptographers have spent much time attacking X, and they feel every possible
algorithm likely to attack X will be infeasibly slow.

With such evidence, the second nobody on earth conjecture already seems
reasonably well supported, since people-on-earth tried and failed.

The stronger non-existence form of the conjecture needs a little more support,
I think.

Certainly, cryptographers could not have run all possible attack algorithms.
Nor could they have predicted the runtimes of all possible attack algorithms.
Indeed, I vaguely have an recollection that some algorithms have runtimes (or
halting status) that are difficult to predict other than by running the
algorithms. There could well be better evidence for the non-existence
conjectures, but what is it?

The famous NP>P conjecture is likely often stated the non-existence form too
(there exists no P algorithm that solves NP-complete, etc.). So, the crypto
conjectures have good company. But NP>P arguably has other types of
supporting evidence. Consider the huge generality of NP and P, and startling
implications of P=NP, the domino effects. I think typical crypto conjectures
have no comparable sweeping and startling impacts if proven wrong.

Anyway, at the splitting hairs level of detail, I agree that the 2021/608
model says that most crypto conjectures ought to be more cautious and used the
weakened nobody-on-earth form. At practical level, I wouldn't agree that the
2021/608 model says that "every cryptographer is wrong 100% of the time".

Best regards,

Dan