Current master (AVX2 and REF) broken on Linux and Mac

[mouse07410]

Fails to compile on Mac and Linux (CentOS 8 and Ubuntu 18.04.02):

$ cd ref-hrss701
$ make
gcc -O3 -fomit-frame-pointer -march=native -fPIC -fPIE -pie -Wall -Wextra -Wpedantic -DCRYPTO_NAMESPACE\(s\)=##s -o test/test_polymul cmov.c fips202.c kem.c owcpa.c pack3.c packq.c poly.c poly_lift.c poly_mod.c poly_r2_inv.c poly_rq_mul.c poly_s3_inv.c sample.c sample_iid.c randombytes.c test/test_polymul.c
<command-line>: error: '##' cannot appear at either end of a macro expansion
<command-line>: error: '##' cannot appear at either end of a macro expansion
<command-line>: error: '##' cannot appear at either end of a macro expansion
In file included from kem.c:1:
api.h:11:28: error: ‘CRYPTO_NAMESPACE’ declared as function returning a function
 #define crypto_kem_keypair CRYPTO_NAMESPACE(keypair)
                            ^~~~~~~~~~~~~~~~
api.h:12:5: note: in expansion of macro ‘crypto_kem_keypair’
 int crypto_kem_keypair(unsigned char *pk, unsigned char *sk);
     ^~~~~~~~~~~~~~~~~~
api.h:12:1: warning: parameter names (without types) in function declaration
 int crypto_kem_keypair(unsigned char *pk, unsigned char *sk);
 ^~~
api.h:14:24: error: ‘CRYPTO_NAMESPACE’ declared as function returning a function
 #define crypto_kem_enc CRYPTO_NAMESPACE(enc)
                        ^~~~~~~~~~~~~~~~
api.h:15:5: note: in expansion of macro ‘crypto_kem_enc’
 int crypto_kem_enc(unsigned char *c, unsigned char *k, const unsigned char *pk);
     ^~~~~~~~~~~~~~
api.h:15:1: warning: parameter names (without types) in function declaration
 int crypto_kem_enc(unsigned char *c, unsigned char *k, const unsigned char *pk);
 ^~~
api.h:17:24: error: ‘CRYPTO_NAMESPACE’ declared as function returning a function
 #define crypto_kem_dec CRYPTO_NAMESPACE(dec)
                        ^~~~~~~~~~~~~~~~
api.h:18:5: note: in expansion of macro ‘crypto_kem_dec’
 int crypto_kem_dec(unsigned char *k, const unsigned char *c, const unsigned char *sk);
     ^~~~~~~~~~~~~~
api.h:18:1: warning: parameter names (without types) in function declaration
 int crypto_kem_dec(unsigned char *k, const unsigned char *c, const unsigned char *sk);
 ^~~
<command-line>: error: '##' cannot appear at either end of a macro expansion
<command-line>: error: '##' cannot appear at either end of a macro expansion
<command-line>: error: '##' cannot appear at either end of a macro expansion
<command-line>: error: '##' cannot appear at either end of a macro expansion
<command-line>: error: '##' cannot appear at either end of a macro expansion
<command-line>: error: '##' cannot appear at either end of a macro expansion
<command-line>: error: '##' cannot appear at either end of a macro expansion
<command-line>: error: '##' cannot appear at either end of a macro expansion
<command-line>: error: '##' cannot appear at either end of a macro expansion
<command-line>: error: '##' cannot appear at either end of a macro expansion
<command-line>: error: '##' cannot appear at either end of a macro expansion
<command-line>: error: '##' cannot appear at either end of a macro expansion
<command-line>: error: '##' cannot appear at either end of a macro expansion
make: *** [Makefile:45: test/test_polymul] Error 1

The above happens with all the compilers I have - current Apple Clang, Clang-10, GCC-10, and on both Mac and Linux platforms.

With avx2-hrss701 it's even merrier - missing source file verify.c:

$ cd avx2-hrss701/
$ make
make: *** No rule to make target `verify.c', needed by `test/test_polymul'.  Stop.

[mouse07410]

Also, the following is not critical, but requires fixing:

$ NTRU_NAMESPACE="fff" make test -C ref-hps2048677/
make: Entering directory '/home/ur20980/src/ntru/ref-hps2048677'
gcc -O3 -fomit-frame-pointer -march=native -fPIC -fPIE -pie -Wall -Wextra -Wpedantic -DCRYPTO_NAMESPACE\(s\)=\(s\) -o test/test_polymul cmov.c crypto_sort_int32.c fips202.c kem.c owcpa.c pack3.c packq.c poly.c poly_lift.c poly_mod.c poly_r2_inv.c poly_rq_mul.c poly_s3_inv.c sample.c sample_iid.c randombytes.c test/test_polymul.c
sample.c: In function ‘sample_fixed_type’:
sample.c:89:3: warning: implicit declaration of function ‘crypto_sort_int32’ [-Wimplicit-function-declaration]
   crypto_sort_int32(s,NTRU_N-1);
   ^~~~~~~~~~~~~~~~~
. . . . .

Here it's worse:

$ NTRU_NAMESPACE="fff" make
gcc -O3 -fomit-frame-pointer -march=native -fPIC -fPIE -pie -Wall -Wextra -Wpedantic -DCRYPTO_NAMESPACE\(s\)=fff##s -o test/test_polymul cmov.c crypto_sort_int32.c fips202.c kem.c owcpa.c pack3.c packq.c poly.c poly_lift.c poly_mod.c poly_r2_inv.c poly_rq_mul.c poly_s3_inv.c sample.c sample_iid.c randombytes.c test/test_polymul.c
sample.c: In function ‘fffsample_fixed_type’:
sample.c:89:3: warning: implicit declaration of function ‘crypto_sort_int32’ [-Wimplicit-function-declaration]
   crypto_sort_int32(s,NTRU_N-1);
   ^~~~~~~~~~~~~~~~~
/tmp/cc7PVOYV.o: In function `fffsample_fixed_type':
sample.c:(.text+0x4e3): undefined reference to `crypto_sort_int32'
collect2: error: ld returned 1 exit status
make: *** [Makefile:48: test/test_polymul] Error 1

[mouse07410]

OK, here's the complete fix of the current master: ntru-p1.diff.txt

It is short enough to post directly:

diff --git a/README.md b/README.md
index ec9446e..e2e53f3 100644
--- a/README.md
+++ b/README.md
@@ -3,3 +3,16 @@
 NTRU is a submission to the second round of [NIST's Post-Quantum Cryptography
 project](https://csrc.nist.gov/Projects/Post-Quantum-Cryptography/Round-2-Submissions).
 It is a merger of the first round NTRUEncrypt and NTRU-HRSS-KEM submissions. See [ntru.org](https://ntru.org) for more information.
+
+### Building from source
+
+1. You must set environment variable `NTRU_NAMESPACE` to some non-empty string,
+   or at least on Mac the code will not compile.
+   Example: 
+     `export NTRU_NAMESPACE="ntru"`
+
+2. On Mac you need to make sure executable `md5sum` is installed - it is not a part
+   of the system software. The simplest way to do that is via Macports, e.g.
+```
+$ sudo port install md5sha1sum
+```
diff --git a/avx2-hps2048677/Makefile b/avx2-hps2048677/Makefile
index 7d54eaf..1f17cce 100644
--- a/avx2-hps2048677/Makefile
+++ b/avx2-hps2048677/Makefile
@@ -15,7 +15,7 @@ SRC = fips202.c \
       poly_s3_inv.c \
       sample.c \
       sample_iid.c \
-      verify.c
+      cmov.c

 HDR = crypto_sort_int32.h \
       kem.h \
@@ -24,7 +24,7 @@ HDR = crypto_sort_int32.h \
       poly.h \
       poly_r2_inv.h \
       sample.h \
-      verify.h
+      cmov.h

 SRC_URAND = $(SRC) randombytes.c
 HDR_URAND = $(HDR) randombytes.h
diff --git a/avx2-hps4096821/Makefile b/avx2-hps4096821/Makefile
index 814f3c0..6af570c 100644
--- a/avx2-hps4096821/Makefile
+++ b/avx2-hps4096821/Makefile
@@ -15,7 +15,7 @@ SRC = fips202.c \
       poly_s3_inv.c \
       sample.c \
       sample_iid.c \
-      verify.c
+      cmov.c

 HDR = crypto_sort_int32.h \
       kem.h \
@@ -24,7 +24,7 @@ HDR = crypto_sort_int32.h \
       poly.h \
       poly_r2_inv.h \
       sample.h \
-      verify.h
+      cmov.h

 SRC_URAND = $(SRC) randombytes.c
 HDR_URAND = $(HDR) randombytes.h
diff --git a/avx2-hrss701/Makefile b/avx2-hrss701/Makefile
index ff7fdca..f5ce65c 100644
--- a/avx2-hrss701/Makefile
+++ b/avx2-hrss701/Makefile
@@ -12,7 +12,7 @@ SRC = fips202.c \
       poly_r2_inv.c \
       sample.c \
       sample_iid.c \
-      verify.c
+      cmov.c

 HDR = kem.h \
       owcpa.h \
@@ -20,7 +20,7 @@ HDR = kem.h \
       poly.h \
       poly_r2_inv.h \
       sample.h \
-      verify.h
+      cmov.h

 SRC_URAND = $(SRC) randombytes.c
 HDR_URAND = $(HDR) randombytes.h
diff --git a/avx2-hrss701/asmgen/poly_s3_to_rq.py b/avx2-hrss701/asmgen/poly_s3_to_rq.py
index fbede84..82cb483 100644
--- a/avx2-hrss701/asmgen/poly_s3_to_rq.py
+++ b/avx2-hrss701/asmgen/poly_s3_to_rq.py
@@ -4,7 +4,6 @@ from params import *
 from mod3 import mod3, mod3_masks
 from math import ceil

-
 if __name__ == '__main__':
     p(".data")
     p(".p2align 5")
@@ -246,7 +245,7 @@ if __name__ == '__main__':
         p("vmovdqa %ymm{}, {}(%rsp)".format(retval, i*32))

     p("mov %rsp, %rsi")  # use b as input for poly_Rq_mul_x_minus_1
-    p("call {}poly_Rq_mul_x_minus_1@plt".format(NAMESPACE))
+    p("call {}poly_Rq_mul_x_minus_1".format(NAMESPACE))

     p("mov %r8, %rsp")
     p("ret")
diff --git a/ref-common/sample.h b/ref-common/sample.h
index 8fdd024..0237dcf 100644
--- a/ref-common/sample.h
+++ b/ref-common/sample.h
@@ -3,6 +3,9 @@

 #include "params.h"
 #include "poly.h"
+#ifdef NTRU_HPS
+#include "crypto_sort_int32.h"
+#endif

 #define sample_fg CRYPTO_NAMESPACE(sample_fg)
 #define sample_rm CRYPTO_NAMESPACE(sample_rm)

Fully tested on Mac and Linux (Ubuntu) with test_compatibility.sh.

On my CentOS Linux , I had problems compiling for AVX2:

gcc -O3 -fomit-frame-pointer -march=native -fPIC -fPIE -pie -Wall -Wextra -Wpedantic -DCRYPTO_NAMESPACE\(s\)=ntru##s -o test/keypair cmov.c crypto_sort_int32.c fips202.c kem.c owcpa.c pack3.c packq.c poly.c poly_lift.c poly_r2_inv.c poly_s3_inv.c sample.c sample_iid.c randombytes.c square_1_509_patience.s square_3_509_patience.s square_6_509_patience.s square_15_509_shufbytes.s square_30_509_shufbytes.s square_63_509_shufbytes.s square_126_509_shufbytes.s square_252_509_shufbytes.s poly_rq_mul.s poly_r2_mul.s poly_rq_to_s3.s vec32_sample_iid.s poly_mod_3_Phi_n.s poly_mod_q_Phi_n.s test/keypair.c
In file included from /usr/lib/gcc/x86_64-redhat-linux/8/include/immintrin.h:43,
                 from crypto_sort_int32.c:5:
crypto_sort_int32.c: In function ‘minmax_vector’:
/usr/lib/gcc/x86_64-redhat-linux/8/include/avx2intrin.h:363:1: error: inlining failed in call to always_inline ‘_mm256_max_epi32’: target specific option mismatch
 _mm256_max_epi32 (__m256i __A, __m256i __B)
 ^~~~~~~~~~~~~~~~
crypto_sort_int32.c:12:21: note: called from here
 #define int32x8_max _mm256_max_epi32
                     ^
crypto_sort_int32.c:17:9: note: in expansion of macro ‘int32x8_max’
   (b) = int32x8_max((a),(b)); \
         ^~~~~~~~~~~
crypto_sort_int32.c:46:5: note: in expansion of macro ‘int32x8_MINMAX’
     int32x8_MINMAX(x0,y0);
     ^~~~~~~~~~~~~~
In file included from /usr/lib/gcc/x86_64-redhat-linux/8/include/immintrin.h:43,
                 from crypto_sort_int32.c:5:
/usr/lib/gcc/x86_64-redhat-linux/8/include/avx2intrin.h:405:1: error: inlining failed in call to always_inline ‘_mm256_min_epi32’: target specific option mismatch
 _mm256_min_epi32 (__m256i __A, __m256i __B)
 ^~~~~~~~~~~~~~~~
crypto_sort_int32.c:11:21: note: called from here
 #define int32x8_min _mm256_min_epi32
                     ^
crypto_sort_int32.c:16:15: note: in expansion of macro ‘int32x8_min’
   int32x8 c = int32x8_min((a),(b)); \
               ^~~~~~~~~~~
crypto_sort_int32.c:46:5: note: in expansion of macro ‘int32x8_MINMAX’
     int32x8_MINMAX(x0,y0);
     ^~~~~~~~~~~~~~

but that could be a result of how that VM was configured - this is what Botan reports about the hardware it sees:

$ botan cpuid
CPUID flags: sse2 ssse3 sse41 sse42 rdtsc aes_ni clmul

Ubuntu VM that runs on a different server, says

and that VM detects HW support for AVX2.

[jschanck]

Thanks, should all be fixed.

[mouse07410]

Thanks - fix is confirmed.

[mouse07410]

@jschanck perhaps you could help me with an advice: I'm trying to use AVX2-accelerated code as a library. How would you suggest to proceed with that?

You mentioned PQClean - but that code is not accelerated.

Thanks!

[jschanck]

The AVX2 code is in PQClean as of sometime last week.