[TLS] Boring cryptography, and the opposite extreme

["D. J. Bernstein" <[e-mail]>]

David Adrian writes:
> Lattice cryptography is "boring" crypto at this point

I think it's useful to explain that this concept of boring crypto is
meant as a positive statement. The name comes from the "boring-crypto"
mailing list that I started in 2013, inspired by earlier boring-is-good
examples under other names, such as Ian Grigg's One True Cipher Suite.
Adam Langley introduced BoringSSL in 2014, with a disclaimer that "the
name is aspirational and not yet a promise". Here are more detailed
explanations of the concept:

    https://cr.yp.to/talks.html#2015.10.05
    https://speakerdeck.com/vixentael/dont-waste-time-on-learning-cryptography-better-use-it-properly

With this background in mind, I'm astonished by the claim that lattice
crypto qualifies as boring. Here's one of my slides from 2015:

    TLS is not boring crypto.
    New attacks! Disputes about security! Improved attacks!
    Proposed fixes! Even better attacks! Emergency upgrades!
    Different attacks! New protocol versions! Continual excitement;
    tons of research papers; more jobs for cryptographers.

A decade later, one can replace "TLS" with "lattice-based cryptography"
on the top line, and the rest of the slide fits perfectly.

Consider, e.g., FrodoKEM, which is supposed to be the safest lattice
KEM, an instantiation of https://eprint.iacr.org/2010/613. This 2010
paper estimated "about 2^150 operations" to break lattice dimension 256,
something that today sounds absurd because attacks have improved so
much. Everything else I'll say about FrodoKEM is more recent than that.

There was an official FrodoKEM software patch in 2020 to address the
security problem that

    https://ia.cr/2020/743

pointed out. This patch introduced a new security problem, as

    https://groups.google.com/a/list.nist.gov/g/pqc-forum/c/kSUKzDNc5ME/m/EMFYz9RNCAAJ.

pointed out, and then there was another official FrodoKEM software patch
to address that.

There was then an official patch to the FrodoKEM cryptosystem and
software in 2023 to address the security problem that

    https://cr.yp.to/papers.html#footloose

pointed out. This was accompanied by a documentation patch renaming the
previous version of FrodoKEM as "ephemeral FrodoKEM" to indicate that
you're not supposed to keep using it for many ciphertexts, never mind
the fact that it was previously portrayed as being safe for any number
of ciphertexts.

If you ask what exactly FrodoKEM's IND-CCA2 security level is claimed to
be, you'll find Table 2 of the official 2021 FrodoKEM documentation

    https://web.archive.org/web/20230224071445/https://frodokem.org/files/FrodoKEM-specification-20210604.pdf

claiming 2^141 pre-quantum IND-CCA2 security for Frodo-640. But, wait,
what about _post-quantum_ IND-CCA2 security, given that the actual
problem at hand is to protect against quantum attacks? You have to read
until page 32 to find out why the post-quantum IND-CCA2 numbers were
suppressed: namely, they're terrifyingly small. Here's how the official
documentation puts it: the underlying calculation "does not concretely
support the bit-security of the six FrodoKEM instantiations in this
document, which is why we omit the corresponding column from Table 2".

As one of the arguments that FrodoKEM is conservative, page 42 claims
that sieving algorithms with time exponents below 0.415b have "memory
complexities as large as time complexities". You can see from, e.g.,

    https://eprint.iacr.org/2015/522 and
    https://eprint.iacr.org/2015/1128

that this claim was already wrong when FrodoKEM was first submitted to
the NIST competition. How is it possible that, in 2025, I'm pointing out
that an official, non-retracted, FrodoKEM claim of being "conservative"
is pointing to a barrier that was already broken in 2015? Could this
maybe have something to do with lattice security being an extremely
complicated topic, and with security reviewers being overloaded?

Page 42 also claims that sieving algorithms below 0.415b have "much less
predictable memory access patterns" than sequential memory access. This
was true for a while---and is also the foundation of

    https://web.archive.org/web/20231219201240/https://csrc.nist.gov/csrc/media/Projects/post-quantum-cryptography/documents/faq/Kyber-512-FAQ.pdf

from 2023---but has been solidly debunked by two undisputed papers

    https://cic.iacr.org/p/1/3/6 (asymptotics) and
    https://eprint.iacr.org/2024/739 (concrete costs and demos)

showing that the memory-access exponents in these attacks can be
optimized to add very little on top of the costs of computation.

Let's review what we've seen. New attacks? Yes. Disputes about security?
Yes. Improved attacks? Yes. Proposed fixes? Yes. Even better attacks?
Yes. Emergency upgrades? Yes. Different attacks? Yes. New protocol
versions? Yes: the FrodoKEM security patch in 2023 wasn't interoperable.
Continual excitement? Yes. Tons of research papers? Yes. More jobs for
cryptographers? Regarding FrodoKEM in particular, maybe not, but for
lattice-based cryptography overall, certainly, as

    https://martinralbrecht.wordpress.com/2024/11/29/phd-position-in-lattice-based-cryptography/

illustrates. This is the opposite of boring cryptography.

---D. J. Bernstein