Focusing here on comparing the following two responses to multi-target
attacks:
* Response #1: include a key prefix in the hash used in the CCA2
conversion, a long enough prefix that prefixes of user keys don't
collide.
* Response #2: "aim for a very high single-target security level, and
then rely on the fact that T-target attacks gain at most a factor
T".
My impression is that neither of these will be part of decisions at the
end of round 1---
*
https://groups.google.com/a/list.nist.gov/d/msg/pqc-forum/WxRmVPhAENw/I5yhtr9dAgAJ
indicates that NIST is treating CCA2 conversion choices as "minor
changes (tweaks)" for the beginning of round 2.
* NIST also doesn't seem concerned with the exact security levels in
round 1: "We’re not going to kick out a scheme just because they
set their parameters wrong".
---but surely these issues will have to receive more attention as the
post-quantum standardization project progresses. It will be useful for
the community to resolve disputes regarding the relative merits of the
two responses before round-2 tweaks are due. Also, the principles here
have an impact beyond multi-target attacks.
Mike Hamburg writes, regarding Response #2:
> overdesigning this way is unappealing
Response #2 is tremendously appealing for security evaluation, auditing,
and actually solving the security problem (see below), so I presume that
what you're claiming here is a performance problem. Let's look at the
performance numbers.
Say the best single-target attack is a search for one solution in a
space of size 2^k. There are other attack shapes, but this one maximizes
the performance gap that you're alluding to.
Here's the standard list of how big k needs to be for four single-target
security levels:
* Security 2^64 pre-quantum: k=64.
* Security 2^128 pre-quantum: k=128.
* Security 2^64 post-quantum: k=128.
* Security 2^128 post-quantum: k=256.
(Of course this list measures security with naive operation counts.
Depth limits and various quantum overheads mean that, e.g., k=256
actually has a much higher post-quantum security level.)
Now let's use Response #2 to protect against 2^64-target attacks, saying
that a 2^64-target attack implies a 1-target attack with probability
1/2^64. Here's what this does to k:
* Security 2^64 pre-quantum: k=128. This is 2x larger.
* Security 2^128 pre-quantum: k=192. This is 1.5x larger.
* Security 2^64 post-quantum: k=192. This is 1.5x larger.
* Security 2^128 post-quantum: k=320. This is 1.25x larger.
Sure, 2x sounds significant, but that's for an archaic 2^64 pre-quantum
security level. The gap rapidly shrinks as the target security level
increases. Do you really claim that 1.25x is "overdesigning"?
For typical lattice systems the key size scales as something like
k log k, so the 1.25x in search space turns into 1.30x in key size. This
doesn't noticeably change the picture. The gap can be even smaller when
the best attacks have worse probability dropoffs than Grover, but the
simple analysis already shows that the gap is small.
[ regarding Response #1: ]
> Each feature like this adds complexity and may hurt performance, while
> possibly improving security.
There's a metric missing from this list, namely the complexity of a
comprehensive _review_ of security. One way to see the importance of
this metric is as follows.
Is NIST going to end up standardizing---and are users going to end up
deploying---a post-quantum system that turns out to be devastatingly
insecure, allowing feasible attacks? Quite possibly, yes. My assessment
is that the most likely way for this to happen is as follows:
* as a direct result of design decisions, security review of the
standard will be much more complicated than necessary;
* as a result, the limited human resources available for security
review will run out of time to seriously review everything;
* as a result, serious vulnerabilities will be missed simply because
nobody ever looked at the vulnerable part of the standard.
As an analogy, consider the destruction of OCB2 this year, 14 years
after Rogaway's Asiacrypt 2004 security "proof" and 9 years after ISO
standardization. The Inoue--Minematsu OCB2 attack is simple and fast,
but this doesn't mean it was easy to find: OCB2 is only one of many
cryptographic standards, and it has many interacting components that
needed attack analysis.
Compared to serious security review for OCB2, serious security review
for a typical post-quantum system is another big step up in difficulty,
further increasing the risk of security disasters. The difficulty varies
from one system to another, motivating design changes.
Here are some of the things that happen when we identify the simplicity
of security review as an important goal, and systematically pursue this
goal in designing a KEM for CCA2 security.
We eliminate decryption failures in the underlying PKE. This takes away
a huge, painful, error-prone part of the review process. (My tally,
before eprint 2018/1089 and eprint 2018/1172, said that 25% of the
unscathed encryption submissions eliminate decryption failures.)
What about Dent's hash---plaintext confirmation? Try a security review
with this hash, vs. a security review with an earlier FO variant, and
you'll immediately see how the hash simplifies review:
* The PKE allows the attacker to modify ciphertexts to produce new
ciphertexts that are often valid. This is the starting point for
chosen-ciphertext attacks, and we've seen again and again that
analyzing the consequences is complicated.
* Plaintext confirmation makes it very easy to see that the only way
for an attacker to produce a new valid ciphertext is to already
know the plaintext. The hash also gives a tight ROM proof of
IND-CCA2 from OW-CPA. Security review of OW-CPA is simpler than
security review of IND-CPA.
Of course, evaluators have to check the proof, have to think about
whether there can be better non-ROM attacks, have to think about how an
attacker could use the extra information provided by the hash, etc., but
all of this is much simpler than than having to think through
consequences of valid modified ciphertexts for the underlying PKE.
What about implicit rejection? Implicit rejection makes it very easy to
see that an attacker modifying ciphertexts will obtain random-looking
session keys, whether the modified ciphertexts are valid or not, whether
there's plaintext confirmation or not. This also gives a tight ROM proof
of IND-CCA2 from OW-CPA, even simpler than Dent's proof.
Understanding whether it's best to do plaintext confirmation, or
implicit rejection, or both, requires a closer look at the details. My
current assessment---given the analysis in the tightkem paper, plus the
extra argument that I mentioned regarding side channels---is that
* plaintext confirmation by itself is good,
* implicit rejection by itself is better, and
* doing both implicit rejection and plaintext confirmation is best,
but it's possible that the ranking of these three options will change
with more research.
> The ideal case would be to prove a theorem that says:
> Hardness of underlying problem
> -> Multi-target CPA security of KEM
> -> Multi-target CCA security of KEM+FO
> at least in the [Q]ROM, with as little tightness loss as possible.
It's not at all clear that a tight QROM proof exists. We don't know how
to generate such a proof from Response #1. More to the point, we don't
even know how to use Response #1 to guarantee that multi-target attacks
against the final KEM are tightly equivalent to single-target attacks.
More importantly, even if we did have a proof, there would be a much
bigger problem for security reviewers. Cryptographic systems are full of
constructions that haven't been reviewed for multi-target security. When
review does happen, the reviewers produce one attack after another. See,
e.g.,
https://blog.cr.yp.to/20151120-batchattacks.html
https://eprint.iacr.org/2016/360
for various examples of multi-target attacks against NIST cryptographic
standards---attacks faster than all known single-target attacks. The
result of further review isn't going to be confidence in multi-target
security; it will be a continuing list of further multi-target attacks.
A KEM is one tiny piece of an end-user cryptographic system. Response #1
is looking at this tiny piece, and adding a complication that stops some
multi-target attacks against that piece ("stops" meaning that they are
no more effective than single-target attacks). Maybe at some point we'll
have a proof that this stops all possible multi-target attacks against
this tiny piece. But what about the rest of the system, with tons of
other multi-target weaknesses and potential multi-target weaknesses?
As an example, the New Hope submission claims that it is "rather
uncomfortable to have the security of all connections rely on a single
instance of a lattice problem" since the multiple targets might be
broken by a "massive precomputation". It claims that one can "avoid"
this "pitfall" by having each user generate a separate parameter "a".
But the new ideal-lattice attack algorithm from
https://nitaj.users.lmno.cnrs.fr/Caen2018/Alice_Pellet_MaryCaen2018.pdf
speeds up attacks against _every_ target after a single massive lattice
precomputation. The attack focuses on Ideal-SVP, but the supposed
hardness of Ideal-SVP is the main justification for the claimed hardness
of Ring-LWE. I'd guess that the precomputation is quantitatively larger
than a typical attack, but the New Hope argument isn't quantitative. I'm
not saying that the attack precisely disproves the New Hope multi-target
claim; I'm simply saying that the claim isn't proven and could be wrong.
If a multi-target lattice attack is faster than a single-target lattice
attack, then what exactly is gained by the extra hashing in Response #1?
More broadly, when people combine KEMs with many other components to
produce complete end-user cryptographic systems, there will surely be
many different multi-target weaknesses. What's the strategy to remove
all these weaknesses, and how is a security evaluator supposed to gain
confidence in this approach?
Response #2, unlike Response #1, is a complete solution to the problem:
assume that there will be multi-target attacks, and choose the security
level to protect against the maximum possible effect of those attacks.
This eliminates the hard problem of evaluating multi-target security.
The security evaluator can safely focus on single-target attacks.
I understand how Response #1 can feel like progress. I've even advocated
an analogous complication---but that was in a situation where
* it was easy to see how the complication eliminated multi-target
attacks against a complete end-user cryptographic system;
* this turned into a simple, easily reviewable, proof of multi-target
security for the complete system; and
* the target security level was only 2^128 pre-quantum.
This KEM hash is a very different story. It is, at best, addressing a
much smaller part of a system that has many other multi-target
weaknesses. I doubt that anyone has ever constructed a similar system
with a proof of multi-target security, even if a proof is possible for
this small piece. Furthermore, we're talking about post-quantum KEMs
aiming for a much higher security level, so the performance impact of
Response #2 is relatively small.
> NTRU Prime’s evaluation technique is already less conservative than
> other systems’ — they would call its parameter set class II or III
> instead of V. Just saying that you can divide that by T=2^64 and
> still be OK is unconvincing
Let me see if I understand, quantitatively, what you're claiming here.
You're starting from 2^155 pre-quantum security for Streamlined NTRU
Prime 4591^761, dividing by 2^64 for a 2^64-target attack, and saying
that 2^91 is not OK? Or you're doing something similar starting from
2^140 post-quantum security?
The starting points 2^155 and 2^140 are wild underestimates of the cost
of known single-target attacks. Checking the literature shows, as stated
in my undisputed summary from February, that each of these numbers comes
from
* taking a _small piece_ of an attack,
* dividing this piece into _expensive operations_,
* _asymptotically_ counting the number of these operations, and
* replacing o(1) in the asymptotics with 0.
Note that replacing o(1) with 0 can produce _overestimates_; there's no
guarantee that the o(1) is positive. The reason we think that the
overall effect of the above four steps is a wild underestimate is that
some people have done much more work for much more serious estimates of
attack costs, consistently finding much higher attack costs than the
underestimates indicate (although there are still many unresolved
questions about the details).
This also means that someone doing a security review has to check the
serious estimates (and worry about the unresolved questions). The wild
underestimates are certainly much simpler _formulas_, but this doesn't
mean that they simplify _security evaluation_.
Of course underestimating security levels has the general effect of
increasing security parameters. This could protect users against future
attack speedups. You call this "conservative", suggesting that it's a
good approach. I have two questions and a comment:
* How do you think this approach is different from "overdesigning",
which a moment ago you called "unappealing"? What's the principle
for deciding what's "overdesigning" and what's "conservative"?
* If you think that using a wild underestimate is good, do you think
that using an even wilder underestimate is better? What's the
principle for deciding when to stop?
* There's a different approach, which I'll call the "accurate
conservative" approach, that (1) clearly produces better results
and (2) doesn't use these underestimates.
The accurate conservative approach is as follows:
* Accurately evaluate the costs of the attacks.
* On the basis of this evaluation, choose the highest-security
parameters that users can afford.
The accurate conservative approach, by definition, is maximizing the
users' security against the best attacks considered.
For comparison, you seem to be advocating what I'll call the "inaccurate
conservative" approach, which replaces the accurate evaluations with
something less accurate---in particular, simplified formulas that turn
out to be underestimates. This replacement generally _damages_ security,
as explained in Appendix B.1.2 of
https://cr.yp.to/papers.html#nonuniform
(cited in the NTRU Prime submission under "Warning: underestimates are
dangerous"), and it can't improve security.
The previous paragraph is talking about the damage done to security
against _current_ attacks. The best bet we have is that this will also
damage security against _future_ attacks. Of course it's possible that
advances in attacks will magically turn out to be better correlated with
the current underestimates than with accurate evaluations of today's
attack costs---but what's the argument for betting on this possibility?
"I have an argument: underestimate U of the security level is smaller
than accurate estimate A, and future attacks will also be faster than
A!" ---To see that this argument is nonsense, consider a more radical
underestimate such as A/3. (If A/3 isn't below U, replace it with some
even smaller function of A.) The argument claims that replacing A with U
is an improvement, and that replacing U with A/3 is an improvement---but
A/3 gives exactly the same parameter choices as A, so the argument has
directly contradicted itself.
There are cases where the literature looks more closely at the details
of attacks and makes well-informed assessments of risks of various types
of speedups. Superficially, this might sound like recommending
underestimates---but there's an essential difference in methodology.
Saying "we want a smaller estimate because smaller is good", or "we want
a simpler formula because simpler is good", is very different from
saying "we see a risk of the following type of attack improvement and we
want to accurately evaluate the impact". Often the conclusion is that
the impact is so devastating that proper risk management requires
avoiding some types of cryptosystems. Consider, e.g., the statement
It is anticipated that these techniques can be used to produce
collisions for MD5 and perhaps also for RIPEMD
in
https://link.springer.com/content/pdf/10.1007%2F3-540-60865-6_44.pdf
twenty years ago.
There are also cases where we can't reasonably evaluate security against
some types of attacks since they're beyond the attack model that the
community normally considers. Timing attacks were like this twenty years
ago, with very high risks that people claiming timing-attack security
were disastrously wrong:
Table lookups: This instruction is not susceptible to a timing attack
...
--- Daemen and Rijmen, Resistance against implementation attacks: a
comparative study of the AES proposals, 1999
https://web.archive.org/web/20000816072451/http://csrc.nist.gov:80/encryption/aes/round1/conf2/papers/daemen.pdf
Table lookup: not vulnerable to timing attacks.
--- NIST, Report on the development of the Advanced Encryption
Standard (AES), 2001
Multi-target attacks are like this today. They're a fun research topic,
and maybe in twenty years we'll know how to stop multi-target attacks;
but most components of today's post-quantum cryptosystems were designed
by people who weren't even thinking about, let alone trying to stop,
multi-target attacks. Response #2 recognizes this, gives us confidence
that we're protected, and doesn't cost much in the context of
high-security post-quantum cryptography.
---Dan