ROUND 3 OFFICIAL COMMENT: NTRU Prime

[D. J. Bernstein]

Two years ago an NTRU Prime update talk announced the new "factored"
NTRU Prime software, a wrapper around "modules with separate tests and
optimizations". I gave a talk today announcing, among other things,
computer verification for most of these modules that the existing "avx"
implementation produces the same output as the existing "ref"
implementation for _all_ possible inputs:

https://cr.yp.to/talks.html#2021.09.03

This is a big step towards full verification of the optimized NTRU Prime
software. Next steps are matching "avx" to "ref" for the other modules
(notably multiplication, where another tool has gotten through some
important parts of the code but not yet everything) and matching the C
code to the Sage reference code.

The "saferewrite" tool used for this verification has a broad range of
applicability beyond NTRU Prime. The first example in the talk is how
saferewrite catches both of the array-comparison problems that were
announced in the official Frodo software. However, to enable this
analysis, I had to define a Frodo array-comparison module and write
reference code for that module, so that saferewrite could compare the
official code to my reference code. This wasn't a big deal since this
particular module is so simple, but an analogous analysis for larger
components of Frodo (short of taking the entire KEM as a monolith!)
would require additional work to write reference code for those modules.
For NTRU Prime, this work is already done.

For each module, saferewrite compiles each implementation with clang -O1
and with gcc -O3, uses the angr symbolic-execution toolkit to convert
each binary into unrolled code in a much simpler language, and uses the
Z3 theorem prover (via angr's claripy) to verify equivalence or find a
counterexample. The automatic equivalence chains look like this
(although this pattern isn't optimal in general):

opt clang -O1 = ref clang -O1 = avx clang -O1
||
opt gcc -O3 = ref gcc -O3 = avx gcc -O3

There could be compiler bugs affecting outputs, but to evade detection
these bugs would have to have the same effect on every node in the
diagram simultaneously. (It would also be possible to hook a direct
Python-to-the-simpler-language conversion into the picture.) There could
be unrolling bugs, but saferewrite also runs the binaries on some random
inputs (plus all-0 and all-1 to make sure every bit is touched) and
checks that these match the unrolled code; also, angr has been heavily
exercised in a variety of reverse-engineering applications. There could
be bugs in saferewrite itself, but reviewing saferewrite is a much
smaller task than reviewing a ton of optimized post-quantum code.

The examples supplied in the saferewrite package include deliberately
buggy code to exercise saferewrite's tests, in particular producing 16
analyses printing "differentfrom" counterexamples (which I've checked by
hand), providing some evidence that saferewrite is working as desired.
Some of these bugs are also found by random tests, but some aren't. More
advanced fuzzing can do better than random tests but has no hope of
finding typical cryptographic overflow bugs.

Seeing C code working with two compilers doesn't mean that the same code
will work with further compilers, but if analyses are fast enough then
it's realistic to re-apply the analyses whenever the compiler changes. I
tried the saferewrite analysis of 107 implementations of 27 functions,
times 2 compilers, on a dual EPYC 7742; it finished in 8 minutes of
wall-clock time, using 20 cores on average, using under 200GB of RAM.

I'm filing this as an OFFICIAL COMMENT regarding NTRU Prime because it's
directly relevant to the official NISTPQC evaluation criteria, notably
the following:

The algorithms can be implemented securely and efficiently on a wide
variety of platforms, including constrained environments, such as smart
cards.

Various NISTPQC submissions have provided fast AVX2 software, fast M4
software, etc., but the primary evidence for "securely" is that the
software is constant-time. (I'll skip discussion of the broken masked
implementations.) The problem is that the same optimizations add massive
complexity to the software, and this complexity is a security threat:

* https://arxiv.org/abs/2107.04940 studied the vulnerabilities
announced between 2010 and 2020 in eight well-known cryptographic
libraries, and found 73 vulnerabilities in the cryptographic
computations, including 11 known to be exploitable ("severe"),
along with "evidence of a strong correlation between the complexity
of these libraries and their (in)security". (There were also
hundreds of further bugs, such as buffer overflows.)

* Post-quantum software is newer, more complicated, and much harder
to thoroughly review. Superficial reviews of post-quantum software
have caught one devastating bug after another; the only reasonable
prediction is that more serious reviews will find many more bugs.

Is it reasonable to say that an algorithm "can be implemented securely
and efficiently" if fast implementations are so complex that the experts
are getting them wrong? If the answer is pointing to an implementation
and saying "No bugs are known in this implementation", then why should
we think that the code is correct, rather than thinking that security
reviewers are overloaded and that this answer is pure selection bias?

There's stronger evidence for "securely and efficiently" when optimized
modules are verified to match much simpler reference implementations.
Covering more modules will further strengthen this evidence.

Another relevant NISTPQC evaluation criterion is the following:

Factors that might hinder or promote widespread adoption of an
algorithm or implementation will be considered in the evaluation
process, including, but not limited to, ...

The availability of modularized implementations, and the availability of
verification tools applicable to some of those modules, certainly help
promote widespread adoption of those implementations and the algorithm.

---Dan (speaking for myself)

[Wrenna Robson]

Thank you for this, Dan - really interesting. I am hopeful of having something to share in the next couple of months on my own verification and validation efforts with Classic McEliece using SAW/Cryptol, and certainly much of your thinking here seems to align with conclusions and thoughts I've reached.

(Increasingly I think a hybrid approach, using multiple toolchains that complement each other's weaknesses, with a clear analysis and synthesis of the truth-claims that each makes. is the way forward - though this mean, of course, you have more tools that you need to validate and verify...)

- Wrenna

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

[D. J. Bernstein]

Each round-3 submission team was given a 15-minute slot at the NIST
conference three months ago to present updates for, and field questions
from, an online audience of about 300 people, of course including NIST.

During the NTRU Prime talk, Dr. Apon posted the text quoted below to the
Slack channel for the conference, publicly accusing me of professional
misconduct. Specifically, he accused me of initiating private contact
with NIST so as to provide false information to NIST regarding the
timing of an upcoming announcement relevant to NIST's ongoing decisions.
However:

* The contact was requested by NIST.

* The false information that Dr. Apon attributes to me is a
fabrication by Dr. Apon.

Here's Dr. Apon's text:

9:38 PM
Daniel Apon @djb a quick, gentle question:

Regarding cyclotomic-based attacks: 13-14 months ago (just before the
end of the 2nd Round), you privately emailed NIST PQC to suggest that
you had a new attack paper (in the line) against cyclotomics that was
coming out in 2-3 months. Of course, we are very eager to hear any
progress along this line, even attacks that provide progress on this
line, even if they don't break a cryptosystem outright (but might
threaten cryptosystems in the future). However, no paper came out. We
invited you to give a public 3rd Round Seminar talk on this issue in the
Fall, and you ended up giving a talk at the Seminar Series in January 15
of this year. The talk presented a variety of algebraic and mathematical
background that was quite interesting, but didn't suggest a clear attack
vector. At the time, I suggested that you finish the paper and submit
the attack paper to this conference. We didn't receive such a
submission. Given this background of no attack progress against
cyclotomics since the beginning of the pandemic (after claiming at least
an epsilon of progress would be coming in "a month or months" well over
a year ago), how would you characterize your progress in making a single
epsilon of progress in attacking cyclotomic structures in lattice-based
cryptography?

I replied quickly on the Slack channel to the beginning of this---

please don't misrepresent the history. nist specifically asked to be
informed regarding ongoing projects, and i answered.

---but then, reading further in Dr. Apon's text, I found one outright
fabrication after another, and responded accordingly:

i'll post an apon fact check to pqc-forum in due time. in the
meantime, happy to answer honest questions.

I promptly contacted Dr. Apon:

I'm writing to request a retraction of the "question" that you issued
during my talk. I expect the retraction to include a clear and
specific acknowledgment that you fabricated the "coming out in 2-3
months" part, and that this part plays a critical role in your
"question". I'll give you 1 week before escalating.

I sent another message to Dr. Apon shortly after that:

Appendix: I also expect the retraction to include the same clear and
specific acknowledgment regarding your fabrication of the "month or
months" part, which plays the same role in your "question".

A week later I filed a complaint with NIST, reviewing the relevant facts
in detail and comparing them to Dr. Apon's accusation, and also raising
the obvious procedural points.

NIST replied a week after that, admitting that the timing of Dr. Apon's
"question" was "not proper", but did not address any of the gaps that I
had identified between the facts and what Dr. Apon wrote. I asked two
clarification questions, which were never answered.

A few weeks later I further escalated the complaint within NIST. NIST
replied after a week, again not addressing the factual dispute. Two
weeks later I asked what options were available within NIST for
resolving the factual dispute. There was no reply.

Naturally, I cc'ed Dr. Apon on the complaint and every subsequent
message. He has had three months to tell me how exactly he believes I'm
getting the facts wrong or missing something that justifies his
accusation. He has not taken this opportunity.

I am now posting the fact check as promised. See attached for a copy of
the complaint that I filed with NIST. This incident appears to be part
of a larger problem with continuing impact on NIST's evaluation of NTRU
Prime, so I'm filing this as an OFFICIAL COMMENT regarding NTRU Prime.

---Dan (speaking for myself)

[Moody, Dustin (Fed)]

Dan,

That there was an impolite exchange on a Slack thread does not mean the PQC standardization process is unfair or biased in any way. We all have individual perspectives, as researchers and scientists, and it is inevitable that some disagreements and misunderstandings will occur during this process. However, we work as a team to ensure that the final outcomes of this process are rigorous and fair.  We take our responsibilities very seriously, and we will continue to be fair and impartial as we evaluate the different algorithms. We make our decisions scientifically based upon the technical results we see published or presented. The community is welcome to provide feedback if they feel this is not the case.

Also, as a reminder, we would like to keep the pqc-forum primarily for technical discussions. We will follow up with you directly on other issues.

Dustin
The NIST PQC team

---

From: D. J. Bernstein
Sent: Wednesday, September 8, 2021 10:16 PM
To: pqc-forum
Cc: pqc-comments
Subject: ROUND 3 OFFICIAL COMMENT: NTRU Prime