Call for SUPERCOP contributions for round-2 NISTPQC

[D. J. Bernstein]

My understanding is that NIST is (1) starting benchmarks for round-2
submissions and (2) also requesting external benchmarks of round-2
submissions.

I'm planning another big SUPERCOP run in August, again with an emphasis
on collecting Haswell benchmarks. Anything sent to the eBATS mailing
list before the end of July will be included if it works and isn't
causing severe CPU-time problems.

https://bench.cr.yp.to/tips.html explains the general procedure for
developing software to add to SUPERCOP. Beware that there's often a
four-way split between

(A) round-1 software submitted to NIST,
(B) round-1 software in SUPERCOP,
(C) round-2 software submitted to NIST, and
(D) round-2 software in SUPERCOP.

A common situation is that the submission team prepared A and C, and I
modified A to obtain B. Maybe I'll similarly modify C to obtain D, but
there's no guarantee of this, also, even if this is done, there's no
guarantee that it will include all the optimizations that the submission
team is expecting. So I recommend that each team look at the differences
between A and B, prepare an analogous D, and check that the results from
a local SUPERCOP run are satisfactory.

---Dan

P.S. NIST has mentioned Haswell, Cortex-M4, and Artix-7 as optimization
targets. For implementors who are done with those, I'd suggest Cortex-A7
(as in https://eprint.iacr.org/2018/720) as a next optimization target.

[D. J. Bernstein]

Status update: All NIST PQC round-2 candidates are now represented in
SUPERCOP, and Haswell benchmarks are in progress. Caveats:

* Security is job #1. One aspect of security is avoiding timing
attacks, but some implementations still don't run in constant time.

* Haswell optimization is more comprehensive than it was but isn't
done yet: e.g., crypto_kem/ntruhps4096821 has only reference code.

* To increase the chance that results are available in time for the
workshop later this month, I'm skipping the gcc options for the
moment in favor of the clang options. This will produce minor
slowdowns for some code, and could produce larger slowdowns.

* Half of the candidates (BIKE, Frodo, GeMSS, LAC, LUOV, MQDSS,
NewHope, NTS-KEM, Picnic, qTESLA, Rainbow, SABER, SIKE) have only
round-1 code in SUPERCOP. More recent code could be faster, and
round-2 tweaks could affect performance in either direction: e.g.,
round-2 SIKE has a new smaller parameter set.

* For most of the candidates, cost in typical applications will be
dominated by size, not by CPU time. (SIKE is an exception.)

Regarding the last point, I've looked at various sources suggesting the
contrary, and found that these sources are unjustifiably relying on
benchmarks of reference code. It's important to be aware that reference
code properly designed for readability is often two or three orders of
magnitude slower than code properly designed for speed.

The following candidates have submitted fast round-2 code to SUPERCOP:
Classic McEliece, Dilithium, Falcon, Kyber, LEDA, NTRU, NTRU Prime,
SPHINCS+, ThreeBears. Picnic has also submitted round-2 code, but
SUPERCOP's checksums didn't match between the AVX implementation and the
other implementations, so I'll wait for a bug fix from the Picnic team
before benchmarking round-2 Picnic.

The candidates not named above are HQC, ROLLO, Round5, and RQC. Last
year I wrote the following about patented candidates:

* The primary goal of benchmarking is to predict the performance that
users will see. Patented cryptographic primitives generally have
far fewer users than unpatented cryptographic primitives, and are
correspondingly much less important as benchmarking targets.

* SUPERCOP doesn't have a policy against accepting code from patent
holders, but none of these teams have sent submissions to SUPERCOP.

* Any particular candidate is unlikely to be standardized, so a
statement releasing or partially releasing a patent in case of
standardization is unlikely to have any effect.

* For similar reasons, patented cryptographic primitives are less
important than unpatented cryptographic primitives as targets of
security analysis. This fact reduces the amount of security
analysis that the patented primitives receive, so security problems
in the patented primitives are more likely to persist without being
detected.

However, NIST told me last month that it "very much" wants to see
SUPERCOP cover all of the candidates, so I've now integrated the code
supplied as part of the round-2 NIST submission packages for HQC, ROLLO,
Round5, and RQC via the conversion scripts shown below. My understanding
is that this is legal, since all NIST submissions allow modification and
redistribution "for the purposes of the post-quantum algorithm public
review and evaluation process".

---Dan


# hqc-to-supercop.sh
( echo hqc-128-1 hqc1281
echo hqc-192-1 hqc1921
echo hqc-192-2 hqc1922
echo hqc-256-1 hqc2561
echo hqc-256-2 hqc2562
echo hqc-256-3 hqc2563
) | while read i j
do
( echo Reference_Implementation/$i crypto_kem/$j/ref
echo Optimized_Implementation/$i crypto_kem/$j/opt
) | while read source target
do
mkdir -p $target
touch $target/../nistpqc
touch $target/../nistpqc2

cp $source/src/*.* $target

# skip provided randombytes etc. in favor of SUPERCOP randombytes
( echo '#include <stdio.h>'
head -136 $source/lib/rng/rng.c
) > $target/rng.c
cp $source/lib/rng/rng.h $target
sed -i 's/randombytes/nist_randombytes/' $target/rng.h
sed -i 's/<stdio.h>/"randombytes.h"/' $target/rng.h

( echo '#include "crypto_hash_sha512.h"'
echo '#define sha512 crypto_hash_sha512'
) > $target/hash.h

sed -i 's/"api.h"/"crypto_kem.h"/' $target/kem.*

sed -i 's/#ifndef API_H//' $target/api.h
sed -i 's/#define API_H//' $target/api.h
sed -i 's/#endif//' $target/api.h

rm $target/main*
done
done

# rollo-to-supercop.sh
( echo ROLLO-I-128 rolloi128
echo ROLLO-I-192 rolloi192
echo ROLLO-I-256 rolloi256
echo ROLLO-II-128 rolloii128
echo ROLLO-II-192 rolloii192
echo ROLLO-II-256 rolloii256
echo ROLLO-III-128 rolloiii128
echo ROLLO-III-192 rolloiii192
echo ROLLO-III-256 rolloiii256
) | while read i j
do
( echo Reference_Implementation/$i crypto_kem/$j/ref
# skip Optimized_Implementation; it's the same code
) | while read source target
do
mkdir -p $target
touch $target/../nistpqc
touch $target/../nistpqc2

cp $source/src/*.* $target
cp $source/src/ffi/* $target

# skip provided randombytes etc. in favor of SUPERCOP randombytes
( echo '#include <stdio.h>'
head -136 $source/lib/rng/rng.c
) > $target/rng.c
cp $source/lib/rng/rng.h $target
sed -i 's/randombytes/nist_randombytes/' $target/rng.h
sed -i 's/<stdio.h>/"randombytes.h"/' $target/rng.h

sed -i 's_../parameters.h_parameters.h_' $target/ffi_vec.cpp $target/ffi.h

( echo '#include "crypto_hash_sha512.h"'
echo '#define sha512 crypto_hash_sha512'
) > $target/hash.h

sed -i 's/"api.h"/"crypto_kem.h"/' $target/kem.*

sed -i 's/#ifndef API_H//' $target/api.h
sed -i 's/#define API_H//' $target/api.h
sed -i 's/#endif//' $target/api.h

rm $target/main*
done
done

# round5-to-supercop.sh
( echo encrypt R5N1_1PKE_0d r5n11pke0d
echo encrypt R5N1_3PKE_0d r5n13pke0d
echo encrypt R5N1_3PKE_0smallCT r5n13pke0smallct
echo encrypt R5N1_5PKE_0d r5n15pke0d
echo encrypt R5ND_1PKE_0d r5nd1pke0d
echo encrypt R5ND_1PKE_5d r5nd1pke5d
echo encrypt R5ND_3PKE_0d r5nd3pke0d
echo encrypt R5ND_3PKE_5d r5nd3pke5d
echo encrypt R5ND_5PKE_0d r5nd5pke0d
echo encrypt R5ND_5PKE_5d r5nd5pke5d
echo kem R5N1_1KEM_0d r5n11kem0d
echo kem R5N1_3KEM_0d r5n13kem0d
echo kem R5N1_5KEM_0d r5n15kem0d
echo kem R5ND_0KEM_2iot r5nd0kem2iot
echo kem R5ND_1KEM_0d r5nd1kem0d
echo kem R5ND_1KEM_4longkey r5nd1kem4longkey
echo kem R5ND_1KEM_5d r5nd1kem5d
echo kem R5ND_3KEM_0d r5nd3kem0d
echo kem R5ND_3KEM_5d r5nd3kem5d
echo kem R5ND_5KEM_0d r5nd5kem0d
echo kem R5ND_5KEM_5d r5nd5kem5d
) | while read op i j
do
j2=`echo $i | tr '[A-Z]' '[a-z]' | tr -d _`
[ "$j" = "$j2" ] || echo "$j" "$j2"
( echo Reference_Implementation/$op/$i crypto_$op/$j/ref
echo Optimized_Implementation/$op/$i crypto_$op/$j/opt
echo Additional_Implementations/AVX2/$op/$i crypto_$op/$j/avx2
) | while read source target
do
mkdir -p $target
touch $target/../nistpqc
touch $target/../nistpqc2

cp $source/* $target

if [ "$op" = kem ]
then
( echo '#include "crypto_kem.h"'
cat $source/cpa_kem.c
) > $target/cpa_kem.c
fi

if [ "$op" = encrypt ]
then
( echo '#include "crypto_encrypt.h"'
cat $source/cca_encrypt.c
) > $target/cca_encrypt.c
fi

rm $target/PQCgenKAT*
rm $target/nist_rng.c
done
done

# rqc-to-supercop.sh
for i in rqc128 rqc192 rqc256
do
( echo Reference_Implementation/$i crypto_kem/$i/ref
# skip Optimized_Implementation; it's the same code
) | while read source target
do
mkdir -p $target
touch $target/../nistpqc
touch $target/../nistpqc2

cp $source/src/*.* $target
cp $source/src/ffi/* $target

# skip provided randombytes etc. in favor of SUPERCOP randombytes
( echo '#include <stdio.h>'
head -136 $source/lib/rng/rng.c
) > $target/rng.c
cp $source/lib/rng/rng.h $target
sed -i 's/randombytes/nist_randombytes/' $target/rng.h
sed -i 's/<stdio.h>/"randombytes.h"/' $target/rng.h

( echo '#include "crypto_hash_sha512.h"'
echo '#define sha512 crypto_hash_sha512'
) > $target/hash.h

sed -i 's/"api.h"/"crypto_kem.h"/' $target/kem.cpp

sed -i 's/#ifndef API_H//' $target/api.h
sed -i 's/#define API_H//' $target/api.h
sed -i 's/#endif//' $target/api.h

rm $target/main*
done
done

[Alperin-Sheriff, Jacob (Fed)]

Thank you, Dan.

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

[daniel.apon]

Thank you, Dan!


By the way, you mentioned:

"   * Security is job #1. One aspect of security is avoiding timing 
     attacks, but some implementations still don't run in constant time."

Would you be willing to post (here, on the pqc-forum) a list of the implementations that you've observed still do not run in constant time?


Thanks so much,
--Daniel

    To unsubscribe from this group and stop receiving emails from it, send an email to pqc-forum+unsubscribe@list.nist.gov.

[D. J. Bernstein]

Daniel Apon via pqc-forum writes:
> Would you be willing to post (here, on the pqc-forum) a list of the
> implementations that you've observed still do not run in constant time?

This question is backwards. The correct procedure is for proposers to
_first_ make crystal clear what security properties they're claiming,
guaranteeing that reviewers investing time and effort into analyzing
those properties won't be met with responses of "We didn't claim that"
(or "That was a typo", as we've seen with HILA5 and Frodo). The timeline
for the claims being made clear is also important: NIST's official
evaluation criteria ask about the "maturity" of security analysis, and
there's no reason that implementation security should be excluded here.

Suppose a reviewer investigates, e.g., the line

syndromePosToFlip = syndromePosToFlip >= P ? syndromePosToFlip - P : syndromePosToFlip;

in crypto_kem/ledakemlt10/portableopt/bf_decoding.c, or the similar
lines in ffi_vec_set_random_from_support_using_seedexpander() in
crypto_kem/rolloi128/ref/ffi_vec.cpp, or the similar lines in the
NTS-KEM software. The LEDA authors and ROLLO authors and NTS-KEM authors
will then respond, justifiably, "We never claimed that this code was
constant time." This is a serious disincentive to security review. Maybe
some review happens anyway but it's less likely.

State-of-the-art automated tools can make a list of code issues to
investigate, and aren't known to have false negatives for post-quantum
code, but rejection sampling is well known to create false positives, so
human effort is still required.

---Dan

[daniel.apon]

Fair enough.