Summary: The "FrodoKEM" submission claims that various theorems support
the security of the submission. This claim is incorrect for at least two
of the stated theorems: these two theorems do not, in fact, support the
security of the submission.
The exact quote at issue is in Section 5.1:
5 Justification of security strength
The security of FrodoKEM is supported both by security reductions and
by analysis of the best known cryptanalytic attacks.
5.1 Security reductions
A summary of the reductions supporting the security of FrodoKEM is as
follows: ... Theorem 5.2 gives a non-tight, classical reduction
against quantum adversaries in the quantum random oracle model. ...
Theorem 5.8 gives a non-tight classical reduction against classical
or quantum adversaries (in the standard model).
Qualitatively, the message of the two theorems is that the following two
attack avenues are ruled out against FrodoKEM:
(1) generic-hash quantum chosen-ciphertext attacks that don't break
IND-CPA security of the underlying PKE;
(2) attacks against the relevant LWE parameters that don't break
various worst-case lattice problems.
In fact, the theorems do _not_ rule out these attack avenues. A user of
FrodoKEM is not guaranteed security against attacks of these two types.
(Please note that I'm _not_ saying that attacks have been shown to exist
along these two lines.) For #1 this is because the stated theorem is too
loose to say anything regarding the KEMs that were actually submitted.
For #2 the theorem statement lacks the quantification necessary to even
see how loose the proof is; I'm skeptical of the idea that a tight
enough theorem is possible, and in any case the claim of applicability
of the stated theorem is incorrect.
Terminology: It's important to be aware of a conflict between two
different definitions of "KEM". For concrete literature such as
http://shoup.net/iso/std6.pdf
a KEM has a concrete size, a concrete security level, etc. This is the
definition that matters for standards, implementations, users, and this
message. Most encryption submissions specify more than one KEM, but,
ultimately, whichever particular KEM the user ends up using is the KEM
whose security and performance matter for that user.
Old-fashioned asymptotic definitions instead use the word "KEM" to refer
to a particular type of infinite _family_ of KEMs. Specifically, key
generation in a "KEM" takes a nonnegative-integer security parameter as
input---so one can't even talk about, e.g., the performance of commonly
used KEMs built from Curve25519, or the security of ntruhrss701. This
definition is also not compatible with statements such as
FrodoKEM’s communication size is sufficiently small that it is still
compatible with many existing deployments
in the FrodoKEM submission: the supporting details provided for this
statement are specific to the KEMs actually contained in the submission.
Details regarding the FrodoKEM security claims: The submission contains
two KEMs, FrodoKEM-640 and FrodoKEM-976 (plus a further division between
AES and SHAKE, not relevant here). Table 1 lists the following failure
probabilities for these two KEMs:
* 1/2^148.8 for FrodoKEM-640;
* 1/2^199.6 for FrodoKEM-976.
"Theorem 5.2 (IND-CPA PKE => IND-CCA KEM in quantum ROM)" refers to the
failure probability as "delta" and states that various types of attacks
succeed with probability at most
9*q_RO*sqrt(q_RO^2*delta+q_RO*sqrt(Adv_PKE^{ind-cpa}(B)+1/|M|)).
The "q_RO" term is the number of hash queries carried out inside the
attack. Let's focus specifically on an attack carrying out 2^50 hash
queries. What the theorem states is that such an attack succeeds with
probability at most
9*2^50*sqrt(2^100*delta+2^50*sqrt(Adv_PKE^{ind-cpa}(B)+1/|M|)).
In particular, for the delta = 1/2^148.8 claimed for FrodoKEM-640, the
theorem states that the attack succeeds with probability at most
457731076.16... + More
where "More" is a nonnegative term reflecting the addition of
Adv_PKE^{ind-cpa}(B)+1/|M| inside the square root. Similarly, for the
delta = 1/2^199.6 claimed for FrodoKEM-976, the theorem states that the
attack succeeds with probability at most
10.338... + More.
Both of these statements are superseded by the content-free observation
that an attack succeeds with probability <=1. (Even stronger, <=1/2 for
security definitions that define success as |Pr-1/2| without doubling.
Both 1/2 and 1 are adequate for my main point in this message.)
As noted above, this theorem is cited in a list of "reductions
supporting the security of FrodoKEM". In fact, the theorem does not
support the security of FrodoKEM. For all submitted FrodoKEM parameters,
the theorem becomes content-free before 2^50 hash queries.
The submission notes that the theorem is "non-tight" (and that this was
ignored in parameter selection), but this does not correct the error in
the "supporting the security of FrodoKEM" claim. There's a big
difference between
* quantitatively weak but still saying something about security and
* quantitatively so weak as to say _nothing_ about security.
One could change parameters to build KEMs for which the theorem _would_
say something, depending on Adv_PKE^{ind-cpa}(B) and |M|. However, those
KEMs would be slower and larger than what the submission proposes. Other
statements in the submission such as
FrodoKEM’s communication size is sufficiently small that it is still
compatible with many existing deployments
would have to be modified accordingly. A hypothetical submission S that
glues together
* S-640: small enough but theorem does not apply
* S-976: small enough but theorem does not apply
* S-MuchBigger: theorem applies but not small enough
cannot make the exaggerated claim that S is small enough and backed by a
theorem; the submission has to be clear about
* the inapplicability of the theorem to S-640 and S-976, and
* the inapplicability of the smallness claims to S-MuchBigger.
More to the point, if S-MuchBigger is omitted and the submission has
* S-640: small enough but theorem does not apply
* S-976: small enough but theorem does not apply
then the not-small-enough disclaimer regarding S-MuchBigger becomes
unnecessary but the theorem becomes irrelevant to what was actually
submitted.
The FrodoKEM submission also claims that the tightness gap "seems to be
an artifact of the proof technique" since there is "no known attack that
takes advantage of the tightness gap". There is no citation to previous
work giving examples of the nightmare scenario that tightness gaps are
exploitable, such as the following:
https://www.youtube.com/watch?v=l56ORg5xXkk
There is also a puzzling inconsistency between how FrodoKEM treats two
specific gaps between known attacks and theorems:
* For the _tightness_ gap discussed above, FrodoKEM chooses
parameters where the theorems are inapplicable, and points to the
lack of known attacks as justification.
* For the gap in _error width_, FrodoKEM insists on choosing
parameters that are claimed to make some theorems applicable, and
seems to portray these large parameters as an advantage, even when
this is not required for protection against known attacks.
In any case, whether or not attacks are known, the simple fact is that
the stated theorem is content-free for all submitted parameters and
therefore does not support the security of the submission.
Another theorem, Theorem 5.8, is also claimed to support the security of
FrodoKEM. However, the theorem uses words such as "negligible" and
"poly" without stating quantitative details, and therefore says nothing
about FrodoKEM-640, FrodoKEM-976, or any other specific KEM.
Previous work
https://eprint.iacr.org/2016/360.pdf by Chatterjee,
Koblitz, Menezes, and Sarkar filled in many quantitative details of an
older theorem (also cited in the FrodoKEM submission) of a similar type,
relating an LWE-type problem to a lattice-type problem. The conclusion
was that, for typical system parameters, the unstated monomial factor
was 2^504, presumably making the theorem useless.
(The reason I'm saying "presumably" is that the unstated _constant_
factor wasn't analyzed, and could conceivably be far enough below 1 to
outweigh the monomial factor. However, experience suggests that the
constant factor is also above 1.)
Of course it's possible that a new theorem is quantitatively better, but
this needs to be stated and proven. The statement presented as "Theorem
5.8" is missing the quantification required for applicability to any
particular KEM, so it does not support the security of the FrodoKEM
submission.
Elsewhere in the FrodoKEM submission there is an admission that the
"known worst-case reduction does not yield any meaningful 'end-to-end'
security guarantee for our concrete parameters based on the conjecture
[sic] hardness of a worst-case problem". However, the "Justification of
security strength" section incorrectly includes Theorem 5.8 in its list
of "reductions supporting the security of FrodoKEM".
Formally, similar problems also exist in at least
* Theorem 5.1 ("about"),
* Theorem 5.2 ("about"),
* Theorem 5.3 ("approximately"), and
* Theorem 5.4 ("about").
One might guess that the quoted words are alluding specifically to
polynomial slowdowns, and that these slowdowns aren't big problems, but
a security audit requires these polynomials to be quantified.
---Dan