[CFRG] Re: RG Last Call on draft-irtf-cfrg-hybrid-kems-12 and draft-irtf-cfrg-concrete-hybrid-kems-04

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

Soatok Dreamseeker writes:
> I was referring to your SafeCurves website.
> https://safecurves.cr.yp.to/complete.html still says P-256 doesn't satisfy
> completeness,

Neither of the criteria defined on the page is met by any known formulas
for NIST P-256.

First criterion: "SafeCurves requires curves to support simple, fast,
_complete_, constant-time single-coordinate single-scalar multiplication.
This includes the SafeCurves ladder requirement but goes further by
requiring completeness."

The word "ladder" links to the ladder page, which provides underlying
definitions: "'Fast' means that implementations of scalar multiplication
for the same curve cannot be much faster, and 'simple' means that
reasonably fast implementations of scalar multiplication for the same
curve cannot be much more concise. At this time there are no examples
close enough to the edge to warrant quantification of 'much'."

Second criterion: "SafeCurves also requires curves to support simple,
fast, _complete_, constant-time multi-scalar multiplication."

More broadly, the SafeCurves introduction explains the point of the
SafeCurves criteria: "Most of these attacks would have been ruled out by
better choices of curves that allow _simple_ implementations to be
_secure_ implementations. This is the primary motivation for SafeCurves.
The SafeCurves criteria are designed to ensure ECC security, not just
ECDLP security."

As an analogy, C++ has an unsafe "s[i] = c" and a safe (aside from
threading issues etc.) "s.at(i) = c". The safe version is endlessly
advertised; it's only _slightly_ less concise; and the slowdown usually
doesn't matter. But, hmmm, somehow I keep seeing new C++ code that's
using "s[i] = c" (not just in the occasional hot spots), and security
problems resulting from this.

> and https://safecurves.cr.yp.to/ind.html claims it doesn't
> satisfy indistinguishability.

The criterion defined on that page is not met by any known formulas for
NIST P-256.

> Maybe consider updating these pages to incorporate research that's as
> fresh as 11-12 years old.

Maybe learn to read. The completeness page has always explained why the
line of research that you're referring to isn't relevant: "Subsequent
research has introduced other complete scalar-multiplication formulas.
However, many of these formulas are considerably slower and more
complicated than standard incomplete scalar-multiplication formulas,
creating major conflicts between simplicity, efficiency, and security."

Probably some alert people reading this message are thinking: wait a
minute, how can the SafeCurves web pages from 2013---

    https://web.archive.org/web/20131019003140/http://safecurves.cr.yp.to/complete.html

---be talking about other complete formulas if those formulas were
introduced in a 2015 paper? Was this time travel?

Answer: After introducing complete addition formulas for Edwards curves
in 2007, Lange and I started looking more broadly at completeness, and
by 2009 we had presented complete addition laws for all elliptic curves
over finite fields:

    https://web.archive.org/web/20130816082425/http://cr.yp.to/talks/2009.07.17/slides.pdf

But the Edwards formulas were simple and fast while the formulas we gave
for, e.g., NIST P-256 weren't---and this matters for figuring out which
formulas have a realistic chance of taking over the software ecosystem,
addressing the real-world problems caused by incomplete formulas.

Similarly, the newer paper https://eprint.iacr.org/2015/1060 managed to
attract a few implementations (e.g., https://eprint.iacr.org/2019/1166)
but never had a real chance of becoming dominant, because it still
flunks the "simple" and "fast" criteria.

The same type of tension is evident for more issues than completeness,
and played an explicit and central role in the SafeCurves pages that we
posted in 2013. See the 2024 paper for much more about all this (for
completeness, for indistinguishability, and in general), along with a
review of how newer vulnerability announcements tracked the SafeCurves
predictions of what would happen, in particular with various security
failures in NIST P-256 software, such as CVE-2023-6135.

Of course, having this all spelled out doesn't stop some people from
skipping the SafeCurves introduction, skipping the definitions of the
criteria, missing the words "simple" and "fast", generally missing the
whole point of the SafeCurves security analysis, and, as a result of
this spectacular failure of reading comprehension, falsely accusing us
of missing something. (If readers can miss such basic words as "fast" in
a security analysis, do we seriously believe it's safe to assume that
readers will see and understand the importance of, say, "C2PRI"?)

Apparently some people even think that P-256 is now safe (at least from
a completeness perspective). I guess these people also think that, since
C++ _allows_ "s.at(i) = c", that's what everybody is using. Sorry, no,
the simpler "s[i] = c" option naturally attracts usage.

---D. J. Bernstein


===== NOTICES =====

IETF BCP 78, "Rights Contributors Provide to the IETF Trust", Section 5
(normative), "Rights in Contributions", provides a modification right
"unless explicitly disallowed in the notices contained in a Contribution
(in the form specified by the Legend Instructions)".

The official language from IETF's "Legend Instructions" for the
situation that "the Contributor does not wish to allow modifications nor
to allow publication as an RFC" is as follows: "This document may not be
modified, and derivative works of it may not be created, and it may not
be published except as an Internet-Draft."
<https://trustee.ietf.org/wp-content/uploads/Corrected-TLP-5.0-legal-provsions.pdf>

The same language is used in, e.g., RFC 5831. The same language hereby
applies to this document. This is not disclaiming or limiting the
applicability of IETF policies; it is strictly following IETF policies.

IESG claims that the "explicitly disallowed" provision in BCP 78 is
limited to the examples in Section 3 in BCP 78. That is incorrect. BCP
78 states that Section 5, "Rights in Contributions", is normative, while
Section 3, "Exposition of Why These Procedures Are the Way They Are", is
informative. The opt-out provision in the normative text is clear, and
cannot be limited by an informative section. BCP 78 does not give IESG
any authority to issue changes or purported clarifications of the rules.

Rationale for exercising the BCP 78 opt-out provision: I'm fine with
redistribution of copies of this document. The issue is instead with
modification, such as (1) IESG's May 2025 posting of an IESG-mangled
version of an appeal that I had filed and (2) IETF management selling
IETF mailing-list text to AI companies. This goes far beyond what
copyright law allows as fair use (such as giving quotes for purposes of
commentary). When I complained about the mangled document, the IETF
Executive Director responded not by apologizing but instead by asserting
that IETF management had the power to do whatever it wanted.