pq-crystals/dilithium

Dilithium

This repository contains the official reference implementation of the Dilithium signature scheme, and an optimized implementation for x86 CPUs supporting the AVX2 instruction set. Dilithium is a finalist in the NIST PQC standardization project.

Build instructions

The implementations contain several test and benchmarking programs and a Makefile to facilitate compilation.

Prerequisites

Some of the test programs require OpenSSL. If the OpenSSL header files and/or shared libraries do not lie in one of the standard locations on your system, it is necessary to specify their location via compiler and linker flags in the environment variables CFLAGS, NISTFLAGS, and LDFLAGS.

For example, on macOS you can install OpenSSL via Homebrew by running

brew install openssl

Then, run

export CFLAGS="-I/usr/local/opt/[email protected]/include"
export NISTFLAGS="-I/usr/local/opt/[email protected]/include"
export LDFLAGS="-L/usr/local/opt/[email protected]/lib"

before compilation to add the OpenSSL header and library locations to the respective search paths.

Test programs

To compile the test programs on Linux or macOS, go to the ref/ or avx2/ directory and run

make

This produces the executables

test/test_dilithium$ALG
test/test_vectors$ALG
PQCgenKAT_sign$ALG

where $ALG ranges over the parameter sets 2, 3, 5, 2aes, 3aes, and 5aes.

• test_dilithium$ALG tests 10000 times to generate keys, sign a random message of 59 bytes and verify the produced signature. Also, the program will try to verify wrong signatures where a single random byte of a valid signature was randomly distorted. The program will abort with an error message and return -1 if there was an error. Otherwise it will output the key and signature sizes and return 0.
• test_vectors$ALG performs further tests of internal functions and prints deterministically generated test vectors for several intermediate values that occur in the Dilithium algorithms. Namely, a 48 byte seed, the matrix A corresponding to the first 32 bytes of seed, a short secret vector s corresponding to the first 32 bytes of seed and nonce 0, a masking vector y corresponding to the seed and nonce 0, the high bits w1 and the low bits w0 of the vector w = Ay, the power-of-two rounding t1 of w and the corresponding low part t0, and the challenge c for the seed and w1. This program is meant to help to ensure compatibility of independent implementations.
• PQCgenKAT_sign$ALG is the Known Answer Test (KAT) generation program provided by NIST. It computes the official KATs and writes them to the files PQCsignKAT_$(CRYPTO_ALGNAME).{req,rsp}.

Benchmarking programs

For benchmarking the implementations, we provide speed test programs for x86 CPUs that use the Time Step Counter (TSC) or the actual cycle counter provided by the Performance Measurement Counters (PMC) to measure performance. To compile the programs run

make speed

This produces the executables

test/test_speed$ALG

for all parameter sets $ALG as above. The programs report the median and average cycle counts of 10000 executions of various internal functions and the API functions for key generation, signing and verification. By default the Time Step Counter is used. If instead you want to obtain the actual cycle counts from the Performance Measurement Counters export CFLAGS="-DUSE_RDPMC" before compilation.

Please note that the reference implementation in ref/ is not optimized for any platform, and, since it prioritises clean code, is significantly slower than a trivially optimized but still platform-independent implementation. Hence benchmarking the reference code does not provide representative results.

Our Dilithium implementations are contained in the SUPERCOP benchmarking framework. See here for current cycle counts on an Intel KabyLake CPU.

Randomized signing

By default our code implements Dilithium's deterministic signing mode. To change this to the randomized signing mode, define the DILITHIUM_RANDOMIZED_SIGNING preprocessor macro at compilation by either uncommenting the line

//#define DILITHIUM_RANDOMIZED_SIGNING

in config.h, or adding -DDILITHIUM_RANDOMIZED_SIGNING to the compiler flags in the environment variable CFLAGS.

Shared libraries

All implementations can be compiled into shared libraries by running

make shared

For example in the directory ref/ of the reference implementation, this produces the libraries

libpqcrystals_dilithium$ALG_ref.so

for all parameter sets $ALG, and the required symmetric crypto libraries

libpqcrystals_aes256ctr_ref.so
libpqcrystals_fips202_ref.so

All global symbols in the libraries lie in the namespaces pqcrystals_dilithium$ALG_ref, libpqcrystals_aes256ctr_ref and libpqcrystals_fips202_ref. Hence it is possible to link a program against all libraries simultaneously and obtain access to all implementations for all parameter sets. The corresponding API header file is ref/api.h, which contains prototypes for all API functions and preprocessor defines for the key and signature lengths.

CMake

Also available is a portable cmake based build system that permits building the reference implementation.

By calling

mkdir build && cd build && cmake .. && cmake --build . && ctest

the Dilithium reference implementation gets built and tested.

dilithium's Issues

Building without -mnative

For machine-instruction-optimized code, better control is desirable over which CPU feature flags are set during compilation: For example when moving executables to other machines, the use of -mnative during build is risky (as executables can then crash "surprisingly") and should be avoided in favour of setting specific (and documented/"known") CPU feature flags like -mavx2. This then also gives a more exact definition of which CPU feature sets are required for optimized code to run and can be specifically tested for, e.g., in CI or cloud environments with different CPU feature sets.

Therefore, could you please remove this flag as a default setting when building and replace it by specific feature sets required (and as documented in the downstream integration .YML files)?

Split out shared code to 'common' folder

This would make building common code cleaner (and pave the way for further code sharing, e.g., with Kyber). If necessary, softlinks to this code could still exist in ref and avx2 for generating NIST code drops (if required). First candidate: fips202.c.

Is it AVX2 or AVX512 instruction set in the avx2 folder?

Hello,

I have compiled the code in the avx2 folder, and encountered this error while calling
int crypto_sign_verify(const uint8_t *sig, size_t siglen, const uint8_t *m, size_t mlen, const uint8_t *pk)

from cgo (golang):

SIGILL: illegal instruction PC=0xd0f392 m=7 sigcode=2 signal arrived during cgo execution instruction bytes: 0x62 0xf1 0x7f 0x28 0x7f 0x7 0x62 0xf1 0x7f 0x28 0x7f 0x47 0x1 0x62 0xf1 0x7f

I have searched (found here: https://bugs.kde.org/show_bug.cgi?id=426330 ) for the instruction bytes and they seem to correspond to an AVX512 instruction, I can't pinpoint which instruction more exactly.

This is the lscpu info for the machine that has this error (it has avx2 support):
`
lscpu
Architecture: x86_64
CPU op-mode(s): 32-bit, 64-bit
Byte Order: Little Endian
Address sizes: 48 bits physical, 48 bits virtual
CPU(s): 2
On-line CPU(s) list: 0,1
Thread(s) per core: 2
Core(s) per socket: 1
Socket(s): 1
NUMA node(s): 1
Vendor ID: AuthenticAMD
CPU family: 23
Model: 1
Model name: AMD EPYC 7571
Stepping: 2
CPU MHz: 2199.782
BogoMIPS: 4399.56
Hypervisor vendor: KVM
Flags: fpu vme de pse tsc msr pae mce cx8 apic sep mtrr pge mca cmov pat pse36 clflush mmx fxsr sse sse2 ht syscall nx mmxext fxsr_opt pdpe1gb rdt
scp lm constant_tsc rep_good nopl nonstop_tsc cpuid extd_apicid tsc_known_freq pni pclmulqdq ssse3 fma cx16 sse4_1 sse4_2 movbe popcnt aes
xsave avx f16c rdrand hypervisor lahf_lm cmp_legacy cr8_legacy abm sse4a misalignsse 3dnowprefetch topoext vmmcall fsgsbase bmi1 avx2 smep
bmi2 rdseed adx smap clflushopt sha_ni xsaveopt xsavec xgetbv1 clzero xsaveerptr arat npt nrip_save

`

I have tested on a different machine that has an intel processor and it works.
`
Architecture: x86_64
CPU op-mode(s): 32-bit, 64-bit
Address sizes: 39 bits physical, 48 bits virtual
Byte Order: Little Endian
CPU(s): 8
On-line CPU(s) list: 0-7
Vendor ID: GenuineIntel
Model name: Intel(R) Core(TM) i7-8650U CPU @ 1.90GHz
CPU family: 6
Model: 142
Thread(s) per core: 2
Core(s) per socket: 4
Socket(s): 1
Stepping: 10
CPU max MHz: 4200,0000
CPU min MHz: 400,0000
BogoMIPS: 4199.88
Flags: fpu vme de pse tsc msr pae mce cx8 apic sep mtrr pge mc
a cmov pat pse36 clflush dts acpi mmx fxsr sse sse2 ss
ht tm pbe syscall nx pdpe1gb rdtscp lm constant_tsc art
arch_perfmon pebs bts rep_good nopl xtopology nonstop_
tsc cpuid aperfmperf pni pclmulqdq dtes64 monitor ds_cp
l vmx smx est tm2 ssse3 sdbg fma cx16 xtpr pdcm pcid ss
e4_1 sse4_2 x2apic movbe popcnt tsc_deadline_timer aes
xsave avx f16c rdrand lahf_lm abm 3dnowprefetch cpuid_f
ault epb invpcid_single pti ssbd ibrs ibpb stibp tpr_sh
adow vnmi flexpriority ept vpid ept_ad fsgsbase tsc_adj
ust sgx bmi1 avx2 smep bmi2 erms invpcid mpx rdseed adx
smap clflushopt intel_pt xsaveopt xsavec xgetbv1 xsave
s dtherm ida arat pln pts hwp hwp_notify hwp_act_window
hwp_epp md_clear flush_l1d arch_capabilities
Virtualization features:
Virtualization: VT-x

`

My problem is that the avx2 is supported for both machines but the one with the error doesn't support AVX512 I think.

What flag must I look for in order to decide if to use the code in the avx2 folder or the one in the ref one?

Make tests easy to trigger

A single .sh script (or Makefile target) to run all tests and get a single OK/NOK decision would make cross-platform CI easier.

wrong seed length

In polyvec.{c,h}, polyvecl_uniform_gamma1 has seed[SEEDBYTES] as parameter. According to the documentation, it should be seed[CRHBYTES].

Possibly wrong macro TRBYTES in crypto_sign_verify standard branch

CRHBYTES macro should be used instead of TRBYTES
in:

dilithium/ref/sign.c

Line 255 in e29d6ef

shake256(mu, TRBYTES, pk, CRYPTO_PUBLICKEYBYTES);

and:

dilithium/ref/sign.c

Line 257 in e29d6ef

shake256_absorb(&state, mu, TRBYTES);

Incrementing the nonce used to generate the y vector has not been updated after Round3

Probable timing leakage detected in dilithium implementation in liboqs library

Hi,
I am a graduate student at George Mason University. One of my courses required me to test open source implementations for any security vulnerabilities. In order to test for timing attacks, I and my teammate used a tool "dudect" on the liboqs library . After testing, we found out that Dilithium may have timing leakage. Below attached is the dudect folder containing the test files for all the tested algorithms in liboqs including dilithium. Also attached is our paper which gives a detailed description of dudect and reports the results we have obtained from it. Click here to view the paper published by dudect authors.

Attachments
dudect.zip
ISA_681_Final_Report.pdf

What is the newest version?

I am currently trying to implement dilithium, and as far as I can tell there are differences between this version here and the version for round 3.

Which one is the newest version?

Documentation of Reduce32 Function

Can you please explain the special reduction Reduce32 used in Dilithium and the reason for using it

Sampling procedure does not match with documentation

In the most recent documentation, page 20, paragraph "Sampling the vectors y", it is defined that gamma1-1 is subtracted from the uniform bits. The reference implementation, however, subtracts the uniform bits from gamma1.

Portable build system

Add CMake build system to

• create Makefiles for different platforms, incl. Win (nmake, VisualStudio) and Ninja (high-speed build)
• permit building static and shared libraries
• permit building cleanly separated namespaces for generic (non-optimized) and optimized variants
• incorporate testing in a platform-independent form (resolving issue #16)

Big-Endian missing conversions

When using Dilithium on Big-Endian systems, the following functions perform a type cast from uint16_t to uint8_t. This type cast leads to wrong data and thus to wrong calculations:

polyvec_matrix_expand

polyvecl_uniform_eta

polyvecl_uniform_gamma1

polyveck_uniform_eta

For a fix, please see [1] for a working solution. [2] Shows the success of this change.

[1] smuellerDD/leancrypto@f24f8f4

[2] https://build.opensuse.org/project/show/home:smuellerDD

Latest Apple Clang Seems to Break the Reference Implementation

I updated Apple Clang and Reference Dilithium no longer works. When I run ./test/test_dilithium I get a segmentation fault which with lldb shows the error as

* thread #1, queue = 'com.apple.main-thread', stop reason = EXC_BAD_ACCESS (code=EXC_I386_GPFLT)
    frame #0: 0x00007fff73a952be libdyld.dylib`stack_not_16_byte_aligned_error
libdyld.dylib`stack_not_16_byte_aligned_error:

It seems like the library produced is not 16 byte aligned (recall that MacOS stacks are 16 byte aligned). It seems like the new version of Clang enables -fstack-check by default, so this leads leads to a segmentation fault.

As expected, disabling stack check with -fno-stack-check (temporarily) resolves the issue and gives is the previous (working) behavior.

With some trial and error it seems like the -fomit-frame-pointer optimization is causing the issue (if we remove it, the stack seems to be 16 byte aligned, and if we add it, it is not 16 byte aligned.)

Here is my terminal dump.

➜  dil /usr/bin/cc -v
Apple clang version 11.0.3 (clang-1103.0.32.29)
Target: x86_64-apple-darwin19.3.0
Thread model: posix
InstalledDir: /Applications/Xcode.app/Contents/Developer/Toolchains/XcodeDefault.xctoolchain/usr/bin
➜  dil git clone https://github.com/pq-crystals/dilithium.git
Cloning into 'dilithium'...
remote: Enumerating objects: 96, done.
remote: Counting objects: 100% (96/96), done.
remote: Compressing objects: 100% (67/67), done.
remote: Total 681 (delta 47), reused 44 (delta 27), pack-reused 585
Receiving objects: 100% (681/681), 261.69 KiB | 3.40 MiB/s, done.
Resolving deltas: 100% (432/432), done.
➜  dil cd dilithium 
➜  dilithium git:(master) ls
AUTHORS.md LICENSE    README.md  SHA256SUMS avx2       ref
➜  dilithium git:(master) cd ref 
➜  ref git:(master) ls
Makefile         api.h            ntt.c            params.h         polyvec.h        reduce.c         rounding.c       symmetric.h
PQCgenKAT_sign.c config.h         ntt.h            poly.c           precomp.gp       reduce.h         rounding.h       test
aes256ctr.c      fips202.c        packing.c        poly.h           randombytes.c    rng.c            sign.c
aes256ctr.h      fips202.h        packing.h        polyvec.c        randombytes.h    rng.h            sign.h
➜  ref git:(master) make
cc -march=native -mtune=native -O3 -fomit-frame-pointer PQCgenKAT_sign.c rng.c sign.c polyvec.c poly.c packing.c ntt.c reduce.c rounding.c fips202.c -o PQCgenKAT_sign -lcrypto
cc -march=native -mtune=native -O3 -fomit-frame-pointer test/test_vectors.c rng.c sign.c polyvec.c poly.c packing.c ntt.c reduce.c rounding.c fips202.c -o test/test_vectors -lcrypto
cc -Wall -Wextra -Wpedantic -Wmissing-prototypes -Wredundant-decls -march=native -mtune=native -O3 -fomit-frame-pointer test/test_dilithium.c randombytes.c test/cpucycles.c test/speed.c \
	  sign.c polyvec.c poly.c packing.c ntt.c reduce.c rounding.c fips202.c -o test/test_dilithium
In file included from test/test_dilithium.c:3:
test/cpucycles.h:86:3: warning: extension used [-Wlanguage-extension-token]
  asm volatile("rdtsc; shlq $32,%%rdx; orq %%rdx,%%rax"
  ^
test/cpucycles.h:95:3: warning: extension used [-Wlanguage-extension-token]
  asm volatile("rdtsc; shlq $32,%%rdx; orq %%rdx,%%rax"
  ^
2 warnings generated.
In file included from test/cpucycles.c:1:
test/cpucycles.h:86:3: warning: extension used [-Wlanguage-extension-token]
  asm volatile("rdtsc; shlq $32,%%rdx; orq %%rdx,%%rax"
  ^
test/cpucycles.h:95:3: warning: extension used [-Wlanguage-extension-token]
  asm volatile("rdtsc; shlq $32,%%rdx; orq %%rdx,%%rax"
  ^
test/cpucycles.c:9:5: warning: extension used [-Wlanguage-extension-token]
    asm volatile("");
    ^
3 warnings generated.
In file included from poly.c:2:
./test/cpucycles.h:86:3: warning: extension used [-Wlanguage-extension-token]
  asm volatile("rdtsc; shlq $32,%%rdx; orq %%rdx,%%rax"
  ^
./test/cpucycles.h:95:3: warning: extension used [-Wlanguage-extension-token]
  asm volatile("rdtsc; shlq $32,%%rdx; orq %%rdx,%%rax"
  ^
2 warnings generated.
In file included from fips202.c:9:
./test/cpucycles.h:86:3: warning: extension used [-Wlanguage-extension-token]
  asm volatile("rdtsc; shlq $32,%%rdx; orq %%rdx,%%rax"
  ^
./test/cpucycles.h:95:3: warning: extension used [-Wlanguage-extension-token]
  asm volatile("rdtsc; shlq $32,%%rdx; orq %%rdx,%%rax"
  ^
2 warnings generated.
➜  ref git:(master) ✗ ./test/test_dilithium 
[1]    31373 segmentation fault  ./test/test_dilithium
➜  ref git:(master) ✗ lldb ./test/test_lithium
(lldb) target create "./test/test_dilithium"
rCurrent executable set to '/tmp/dil/dilithium/ref/test/test_dilithium' (x86_64).
(lldb) r
Process 31390 launched: '/tmp/dil/dilithium/ref/test/test_dilithium' (x86_64)
Process 31390 stopped
* thread #1, queue = 'com.apple.main-thread', stop reason = EXC_BAD_ACCESS (code=EXC_I386_GPFLT)
    frame #0: 0x00007fff73a952be libdyld.dylib`stack_not_16_byte_aligned_error
libdyld.dylib`stack_not_16_byte_aligned_error:
->  0x7fff73a952be <+0>: movdqa %xmm0, (%rsp)
    0x7fff73a952c3 <+5>: int3   
    0x7fff73a952c4 <+6>: nop    
    0x7fff73a952c5 <+7>: nop    
Target 0: (test_dilithium) stopped.
(lldb) ^D
➜  ref git:(master) ✗ vi Makefile 
➜  ref git:(master) ✗ gd Makefile | bat
───────┬───────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────
       │ STDIN
───────┼───────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────
   1   │ diff --git a/ref/Makefile b/ref/Makefile
   2   │ index 4d0830b..98b5844 100644
   3   │ --- a/ref/Makefile
   4   │ +++ b/ref/Makefile
   5   │ @@ -1,6 +1,6 @@
   6   │  CC ?= /usr/bin/cc
   7   │  CFLAGS += -Wall -Wextra -Wpedantic -Wmissing-prototypes -Wredundant-decls \
   8   │ -   -march=native -mtune=native -O3 -fomit-frame-pointer
   9   │ +   -march=native -mtune=native -O3 -fomit-frame-pointer -fno-stack-check
  10   │  NISTFLAGS += -march=native -mtune=native -O3 -fomit-frame-pointer
  11   │  SOURCES = sign.c polyvec.c poly.c packing.c ntt.c reduce.c rounding.c
  12   │  HEADERS = config.h api.h params.h sign.h polyvec.h poly.h packing.h ntt.h \
───────┴───────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────
➜  ref git:(master) ✗ make clean
rm -f *~ test/*~
rm -f PQCgenKAT_sign
rm -f PQCgenKAT_sign-AES
rm -f test/test_vectors
rm -f test/test_vectors-AES
rm -f test/test_dilithium
rm -f test/test_dilithium-AES
rm -f test/test_mul
➜  ref git:(master) ✗ make
cc -march=native -mtune=native -O3 -fomit-frame-pointer PQCgenKAT_sign.c rng.c sign.c polyvec.c poly.c packing.c ntt.c reduce.c rounding.c fips202.c -o PQCgenKAT_sign -lcrypto
cc -march=native -mtune=native -O3 -fomit-frame-pointer test/test_vectors.c rng.c sign.c polyvec.c poly.c packing.c ntt.c reduce.c rounding.c fips202.c -o test/test_vectors -lcrypto
cc -Wall -Wextra -Wpedantic -Wmissing-prototypes -Wredundant-decls -march=native -mtune=native -O3 -fomit-frame-pointer -fno-stack-check test/test_dilithium.c randombytes.c test/cpucycles.c test/speed.c \
	  sign.c polyvec.c poly.c packing.c ntt.c reduce.c rounding.c fips202.c -o test/test_dilithium
In file included from test/test_dilithium.c:3:
test/cpucycles.h:86:3: warning: extension used [-Wlanguage-extension-token]
  asm volatile("rdtsc; shlq $32,%%rdx; orq %%rdx,%%rax"
  ^
test/cpucycles.h:95:3: warning: extension used [-Wlanguage-extension-token]
  asm volatile("rdtsc; shlq $32,%%rdx; orq %%rdx,%%rax"
  ^
2 warnings generated.
In file included from test/cpucycles.c:1:
test/cpucycles.h:86:3: warning: extension used [-Wlanguage-extension-token]
  asm volatile("rdtsc; shlq $32,%%rdx; orq %%rdx,%%rax"
  ^
test/cpucycles.h:95:3: warning: extension used [-Wlanguage-extension-token]
  asm volatile("rdtsc; shlq $32,%%rdx; orq %%rdx,%%rax"
  ^
test/cpucycles.c:9:5: warning: extension used [-Wlanguage-extension-token]
    asm volatile("");
    ^
3 warnings generated.
In file included from poly.c:2:
./test/cpucycles.h:86:3: warning: extension used [-Wlanguage-extension-token]
  asm volatile("rdtsc; shlq $32,%%rdx; orq %%rdx,%%rax"
  ^
./test/cpucycles.h:95:3: warning: extension used [-Wlanguage-extension-token]
  asm volatile("rdtsc; shlq $32,%%rdx; orq %%rdx,%%rax"
  ^
2 warnings generated.
In file included from fips202.c:9:
./test/cpucycles.h:86:3: warning: extension used [-Wlanguage-extension-token]
  asm volatile("rdtsc; shlq $32,%%rdx; orq %%rdx,%%rax"
  ^
./test/cpucycles.h:95:3: warning: extension used [-Wlanguage-extension-token]
  asm volatile("rdtsc; shlq $32,%%rdx; orq %%rdx,%%rax"
  ^
2 warnings generated.
➜  ref git:(master) ✗ ./test/test_dilithium 
keygen:
median: 310568 ticks @ 2.6 GHz (0.1194 msecs)
average: 317223 ticks @ 2.6 GHz (0.122 msecs)

sign: 
median: 1046230 ticks @ 2.6 GHz (0.4024 msecs)
average: 1351139 ticks @ 2.6 GHz (0.5197 msecs)

verify: 
median: 344312 ticks @ 2.6 GHz (0.1324 msecs)
average: 350637 ticks @ 2.6 GHz (0.1349 msecs)

➜  ref git:(master) ✗ vi Makefile 
➜  ref git:(master) ✗ gd Makefile| bat
───────┬───────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────
       │ STDIN
───────┼───────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────
   1   │ diff --git a/ref/Makefile b/ref/Makefile
   2   │ index 4d0830b..e8a13ee 100644
   3   │ --- a/ref/Makefile
   4   │ +++ b/ref/Makefile
   5   │ @@ -1,6 +1,6 @@
   6   │  CC ?= /usr/bin/cc
   7   │  CFLAGS += -Wall -Wextra -Wpedantic -Wmissing-prototypes -Wredundant-decls \
   8   │ -   -march=native -mtune=native -O3 -fomit-frame-pointer
   9   │ +   -march=native -mtune=native -O3
  10   │  NISTFLAGS += -march=native -mtune=native -O3 -fomit-frame-pointer
  11   │  SOURCES = sign.c polyvec.c poly.c packing.c ntt.c reduce.c rounding.c
  12   │  HEADERS = config.h api.h params.h sign.h polyvec.h poly.h packing.h ntt.h \
───────┴───────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────
➜  ref git:(master) ✗ make clean
rm -f *~ test/*~
rm -f PQCgenKAT_sign
rm -f PQCgenKAT_sign-AES
rm -f test/test_vectors
rm -f test/test_vectors-AES
rm -f test/test_dilithium
rm -f test/test_dilithium-AES
rm -f test/test_mul
➜  ref git:(master) ✗ make
cc -march=native -mtune=native -O3 -fomit-frame-pointer PQCgenKAT_sign.c rng.c sign.c polyvec.c poly.c packing.c ntt.c reduce.c rounding.c fips202.c -o PQCgenKAT_sign -lcrypto
cc -march=native -mtune=native -O3 -fomit-frame-pointer test/test_vectors.c rng.c sign.c polyvec.c poly.c packing.c ntt.c reduce.c rounding.c fips202.c -o test/test_vectors -lcrypto
cc -Wall -Wextra -Wpedantic -Wmissing-prototypes -Wredundant-decls -march=native -mtune=native -O3 test/test_dilithium.c randombytes.c test/cpucycles.c test/speed.c \
	  sign.c polyvec.c poly.c packing.c ntt.c reduce.c rounding.c fips202.c -o test/test_dilithium
In file included from test/test_dilithium.c:3:
test/cpucycles.h:86:3: warning: extension used [-Wlanguage-extension-token]
  asm volatile("rdtsc; shlq $32,%%rdx; orq %%rdx,%%rax"
  ^
test/cpucycles.h:95:3: warning: extension used [-Wlanguage-extension-token]
  asm volatile("rdtsc; shlq $32,%%rdx; orq %%rdx,%%rax"
  ^
2 warnings generated.
In file included from test/cpucycles.c:1:
test/cpucycles.h:86:3: warning: extension used [-Wlanguage-extension-token]
  asm volatile("rdtsc; shlq $32,%%rdx; orq %%rdx,%%rax"
  ^
test/cpucycles.h:95:3: warning: extension used [-Wlanguage-extension-token]
  asm volatile("rdtsc; shlq $32,%%rdx; orq %%rdx,%%rax"
  ^
test/cpucycles.c:9:5: warning: extension used [-Wlanguage-extension-token]
    asm volatile("");
    ^
3 warnings generated.
In file included from poly.c:2:
./test/cpucycles.h:86:3: warning: extension used [-Wlanguage-extension-token]
  asm volatile("rdtsc; shlq $32,%%rdx; orq %%rdx,%%rax"
  ^
./test/cpucycles.h:95:3: warning: extension used [-Wlanguage-extension-token]
  asm volatile("rdtsc; shlq $32,%%rdx; orq %%rdx,%%rax"
  ^
2 warnings generated.
In file included from fips202.c:9:
./test/cpucycles.h:86:3: warning: extension used [-Wlanguage-extension-token]
  asm volatile("rdtsc; shlq $32,%%rdx; orq %%rdx,%%rax"
  ^
./test/cpucycles.h:95:3: warning: extension used [-Wlanguage-extension-token]
  asm volatile("rdtsc; shlq $32,%%rdx; orq %%rdx,%%rax"
  ^
2 warnings generated.
➜  ref git:(master) ✗ ./test/test_dilithium 
keygen:
median: 319763 ticks @ 2.6 GHz (0.123 msecs)
average: 327254 ticks @ 2.6 GHz (0.1259 msecs)

sign: 
median: 1096245 ticks @ 2.6 GHz (0.4216 msecs)
average: 1402955 ticks @ 2.6 GHz (0.5396 msecs)

verify: 
median: 357075 ticks @ 2.6 GHz (0.1373 msecs)
average: 363690 ticks @ 2.6 GHz (0.1399 msecs)

➜  ref git:(master) ✗  

Is it possible to change the modulus q in the implementation?

My question is if it is possible to change the modulus q in the implementation. I have been looking at the code to see the dependencies on q, and it seems that many parameters depend on q. But I can never be sure that I am seeing all dependencies. Some dependencies are semi-hidden. For example, gamma2 is defined as (q-1)/88 in Dilitihium2 implementation, which only makes sense with the current choice of q (since q-1 is divisible by 11 in the current form but if we change q, this will no longer be the case. How would gamma2 be defined in that case?)

Is there a prescription for changing the modulus?

Thanks.

make shared fails in avx2

Result of make shared in avx2 folder:

/usr/bin/ld: keccak4x/KeccakP-1600-times4-SIMD256.o: relocation R_X86_64_PC32 against symbol `pqcrystals_fips202x4_avx2_KeccakP1600times4_AddLanesAll' can not be used when making a shared object; recompile with -fPIC
/usr/bin/ld: final link failed: Bad value
collect2: error: ld returned 1 exit status
Makefile:70: recipe for target 'libpqcrystals_fips202x4_avx2.so' failed

Objections to a PR adding -fPIC in avx2/Makefile? Problem doesn't occur in cmake build.

Update README to reflect that dilithium is chosen of winner instead of linking to finalist webpage.

https://www.nist.gov/news-events/news/2022/07/nist-announces-first-four-quantum-resistant-cryptographic-algorithms

Size of c in packing.h

Hello,

In packing.h L21 & L36, the size of uint8_t c should be CTILDEBYTES?
Since CTILDEBYTES has different values in each security level (32, 48, 64), while c[SEEDBYTES] is a fixed 32 bytes array.

Thank you.

AVX2 test_speed Segmentation fault on macOS

test_speed3 and ./test_speed4 seg faul, while ./test_speed2, ./test_speed3aes, and ./test_speed4aes run with no problem!

$ ./test_speed3
Segmentation fault: 11

$ lldb ./test_speed3
Process 96578 stopped
* thread #1, queue = 'com.apple.main-thread', stop reason = EXC_BAD_ACCESS (code=EXC_I386_GPFLT)
    frame #0: 0x00000001000177d0 test_speed3`pqcrystals_dilithium3_avx2_poly_uniform_4x + 64
test_speed3`pqcrystals_dilithium3_avx2_poly_uniform_4x:
->  0x1000177d0 <+64>: vmovaps (%r8), %ymm0
    0x1000177d5 <+69>: vmovaps %ymm0, 0x340(%rsp)
    0x1000177de <+78>: vmovaps %ymm0, 0x6a0(%rsp)
    0x1000177e7 <+87>: vmovaps %ymm0, 0xa00(%rsp)
Target 0: (test_speed3) stopped.
(lldb) bt
* thread #1, queue = 'com.apple.main-thread', stop reason = EXC_BAD_ACCESS (code=EXC_I386_GPFLT)
  * frame #0: 0x00000001000177d0 test_speed3`pqcrystals_dilithium3_avx2_poly_uniform_4x + 64
    frame #1: 0x0000000100001abf test_speed3`main + 159
    frame #2: 0x00007fff6a74ccc9 libdyld.dylib`start + 1
(lldb) register read
General Purpose Registers:
       rax = 0x0000000000000000
       rbx = 0x00007ffeefbf2d60
       rcx = 0x431bec0dfde600d1
       rdx = 0x00007ffeefbf3560
       rdi = 0x00007ffeefbf2d60
       rsi = 0x00007ffeefbf3160
       rbp = 0x00007ffeefbea850
       rsp = 0x00007ffeefbe9740
        r8 = 0x00007ffeefbf7d70
        r9 = 0x0000000000000000
       r10 = 0x00007ffeefbff148
       r11 = 0x00007fff6a942da0  libsystem_platform.dylib`_platform_bzero$VARIANT$Haswell
       r12 = 0x00007ffeefbf3560
       r13 = 0x00007ffeefbf7960
       r14 = 0x00007ffeefbf3560
       r15 = 0x00007ffeefbf3160
       rip = 0x00000001000177d0  test_speed3`pqcrystals_dilithium3_avx2_poly_uniform_4x + 64
    rflags = 0x0000000000010202
        cs = 0x000000000000002b
        fs = 0x0000000000000000
        gs = 0x0000000000000000

Is this is an unaligned access issue?

macOS 10.15.5
Apple clang version 11.0.3 (clang-1103.0.32.59)

Failed to Generate Shared Library as per README

I am trying to generate a shared library following README.MD. It provides instruction as

Shared libraries

All implementations can be compiled into shared libraries by running

make shared
However, when I run make shared, I get the following output:~/softwares/pqc/dilithium/build$ make shared
make: *** No rule to make target 'shared'.  Stop.


Just a note earlier I successfully compiled and tested the code as per instruction in README.MD
mkdir build && cd build && cmake .. && cmake --build . && ctest

Your thought, pointers will be appreciated.

Documentation of bitpacking

(Deleted) :-)

Deadcode in poly_uniform

Hello,

This line cannot be reached: https://github.com/pq-crystals/dilithium/blob/master/ref/poly.c#L360 as STREAM128_BLOCKBYTES is multiple of 3.
The for loop does not run as well.

Calculation of genA matrix XOF(p,i,j)

Hello,
Matrix should be calculated with Calculation of genA matrix XOF(p,i,j) not Calculation of genA matrix XOF(p,j,i)

dilithium/ref/poly.c:868 maybe not correct?

now is
r->coeffs[2*i+0] &= 0xFFFFF;
maybe
r->coeffs[2*i+1] &= 0xFFFFF;
not sure, pls check, thx!

Key size defines in api.h

Hello.
First of all thank you for this job.

According to the below,
https://groups.google.com/a/list.nist.gov/g/pqc-forum/c/xOGBFJNIbEc/m/D_TgPNg6AAAJ

defines in api.h seems to be updated like the below.

8 #define pqcrystals_dilithium2_SECRETKEYBYTES 2528 → 2560
35 #define pqcrystals_dilithium3_SECRETKEYBYTES 4000 → 4032
36 #define pqcrystals_dilithium3_BYTES 3293 → 3309
62 #define pqcrystals_dilithium5_SECRETKEYBYTES 4864 → 4896
63 #define pqcrystals_dilithium5_BYTES 4595 → 4627

Am I correct?

Update README to reflect that dilithium is chosen as winner instead of linking to finalist

https://www.nist.gov/news-events/news/2022/07/nist-announces-first-four-quantum-resistant-cryptographic-algorithms

Size-optimised build

The current code+build structure generates some (object) code duplication as the same code gets compiled multiple times with different defines for different name spaces. This is not ideal for size-constrained environments (smart cards, HSMs) that have to provide all parameter options within one library. This also might be an issue for high-load servers having to serve clients with different parameter sets.

Just looking at the size of different .so libraries generated by make shared it seems there might be potential for saving ~54kB per algorithm combination in ref and ~60kB in avx2 (x64, -O3 compiled).

Looking at one library (build by cmake) containing all combinations (ref+avx2, dil2+3+4, plain+90s), the size differs (again, x64, -O3) between 714416 bytes and 347112 bytes supporting only the "dilithium3" parameter set (still including ref+avx2 & plain+90s), i.e., more than 50%.
This difference of course would change by doing even more code sharing (see also #21 ) and completely factoring out non-Dilithium core code (e.g., Keccak).

Misleading / unnecessary masks in unpacking code

There are three unnecessary masks in the polyt0_unpack and polyz_unpack functions. These all occur when the last coefficient of a block of coefficients is being unpacked. There is no overflow on this last coefficient, so masking the leading bits has no effect.

This is misleading in the polyz_unpack function, where a copy-paste error seems to have slipped in. At first glance this appears to be a bug in the implementation, until it becomes apparent that masking is not needed for this coefficient.

Clean C version?

I wanted to give Dilithium a try in an embedded environment. The github code is for Linux, with GCC directives and inline assembly code. The first try to compile it with a standard C99 compiler (and also under Windows with MS Visual Studio 2017) resulted in 535 compiler errors.

Is there a standard C version of Dilithium? Or Python, Java, Julia…, which I can easily turn to standard C?

ccccccunjvjvclrfckngvvlhjjfeiicfkclrgruenrlb

Bad semaphor value in sign.c

A small issue within crypto_sign_open is causing Dilithium to not compile on windows x86. It is a warning treated as an error. The issue is within the function crypto_sign_open in sign.c.

int crypto_sign_open(uint8_t *m,
                     size_t *mlen,
                     const uint8_t *sm,
                     size_t smlen,
                     const uint8_t *pk)
{
  size_t i;

  if(smlen < CRYPTO_BYTES)
    goto badsig;

  *mlen = smlen - CRYPTO_BYTES;
  if(crypto_sign_verify(sm, CRYPTO_BYTES, sm + CRYPTO_BYTES, *mlen, pk))
    goto badsig;
  else {
    /* All good, copy msg, return 0 */
    for(i = 0; i < *mlen; ++i)
      m[i] = sm[CRYPTO_BYTES + i];
    return 0;
  }

badsig:
  /* Signature verification failed */
  *mlen = -1;
  for(i = 0; i < smlen; ++i)
    m[i] = 0;

  return -1;
}

The issue is that *mlen = -1; is attempting to assign -1 to an unsigned integer, giving the warning:
warning C4245: '=': conversion from 'int' to 'std::size_t'

Would setting *mlen = 0; be sufficient?

I'm curious as to why *mlen = -1; is even set upon failure? It is not consistent with other verification functions in this file, i.e., it is not set to -1 in the event that crypto_sign_verify fails verification. Is this to distinguish between failure modes? Either way, the fact that the crypto_sign_open returns -1 should be enough of an indication of failure.

Thank you

license clarification

Hi Author,

Kindly confirm which one among the below two licenses are applicable.

Public Domain (License text - Public domain code is not subject to any license. )
Creative Commons Zero v1.0 Universal (https://creativecommons.org/publicdomain/zero/1.0/)

Compiler warnings with GCC 11 / -Wall

Compiling with GCC 11 leads to a ton of compiler warnings, e.g.:

aes256ctr.c:557:64: warning: argument 3 of type ‘const uint8_t *’ {aka ‘const unsigned char *’} declared as a pointer [-Warray-parameter=]
  557 | void aes256ctr_prf(uint8_t *out, size_t outlen, const uint8_t *key, const uint8_t *nonce)
      |                                                 ~~~~~~~~~~~~~~~^~~
In file included from aes256ctr.c:27:
aes256ctr.h:19:34: note: previously declared as an array ‘const uint8_t[32]’ {aka ‘const unsigned char[32]’}
   19 |                    const uint8_t key[32],
      |                    ~~~~~~~~~~~~~~^~~~~~~

AVX2 code fails in gcc 8/9 on several platforms

As already reported by email to @gregorseiler : When leaving away -mnative (but setting setting the required -mxyz options), the AVX2 code fails to pass self- and KAT tests under some circumstances (initial example was gcc 8 under Centos-8).

This is a blocker to resolving issue #30. In addition, this code now also seems to trigger downstream problems with Alpine and OSX (see comments and results of an investigation into the issues here).

This might be a compiler bug - but certainly warrants investigation and either a fix or workaround.

To reproduce, see/use this Makefile and use this docker image containing gcc-8:

docker run -v `pwd`:/root/dilithium -it openquantumsafe/ci-centos-8-amd64 bash

and execute in that container this minimal build-and-test cd /root/dilithium/avx2 && make clean && make && cd .. && ./runtests.sh .

What is the purpose of the `reduce` function when performing matrix-vector multiplication?

Hello,

I am currently reading into Dilithium and during that, a question regarding the matrix-vector multiplication came up:
I noticed that the matrix-vector multiplication w = Az is implemented like so:

1. Call polyvec_matrix_pointwise_montgomery(&w1, mat, &z);, where mat and z are already in NTT representation. This function performs coefficient wise multiplication and addition of the resulting polynomials without any reduction
2. A call to polyveck_reduce(&w1); follows
3. w1 is transformed back into coefficient representation: polyveck_invntt_tomont(&w1);

According to the comment, the reduce function reduces the coefficient to to representatives in [-6283009,6283007]. I am wondering: What is the purpose of this and how is this number chosen? If there is a paragraph in the paper which explains this, could you point me to it? Any help is very much appreciated!

Thank you very much

Cross-platform CI

As (intended) downstream consumers (e.g., OQS) run (and test) cross-platform, this should already be done here, too. If no comments to the contrary appear, I'll work on a PR to add CI capabilities for

• Ubuntu
• Debian
• Centos 7
• Centos 8
• Alpine
• OSX
• Windows

using CircleCI.

Dilithium3 and Dilithium4 seem to fail on the 21st KAT vector

Dilithium3 and Dilithium4 seem to fail (most of the time) on the following message. This message is the 21st KAT vector provided with Dilithium.

message.txt

ASAN failures for AVX2 DilithiumXAES code

When compiling the AVX2 code with -fsanitize=address,undefined, the ./test/test_dilithiumXaes executables crash with the following message (gcc 10.1.0):

=================================================================
==291152==ERROR: AddressSanitizer: unknown-crash on address 0x7ffefe704448 at pc 0x55c0811dc9fb bp 0x7ffefe704030 sp 0x7ffefe704020
READ of size 32 at 0x7ffefe704448 thread T0
    #0 0x55c0811dc9fa in pqcrystals_dilithium4aes_avx2_rej_uniform_avx (/home/thom/git/phd/dilithium/avx2/test/test_dilithium4aes+0x4c9fa)
    #1 0x55c0811ce34d in pqcrystals_dilithium4aes_avx2_poly_uniform_preinit (/home/thom/git/phd/dilithium/avx2/test/test_dilithium4aes+0x3e34d)
    #2 0x55c0811cc0ba in pqcrystals_dilithium4aes_avx2_expand_mat (/home/thom/git/phd/dilithium/avx2/test/test_dilithium4aes+0x3c0ba)
    #3 0x55c0811c51a8 in pqcrystals_dilithium4aes_avx2_keypair (/home/thom/git/phd/dilithium/avx2/test/test_dilithium4aes+0x351a8)
    #4 0x55c0811c35ee in main (/home/thom/git/phd/dilithium/avx2/test/test_dilithium4aes+0x335ee)
    #5 0x7fda72063001 in __libc_start_main (/usr/lib/libc.so.6+0x27001)
    #6 0x55c0811c3f8d in _start (/home/thom/git/phd/dilithium/avx2/test/test_dilithium4aes+0x33f8d)

Address 0x7ffefe704448 is located in stack of thread T0 at offset 776 in frame
    #0 0x55c0811ce25f in pqcrystals_dilithium4aes_avx2_poly_uniform_preinit (/home/thom/git/phd/dilithium/avx2/test/test_dilithium4aes+0x3e25f)

  This frame has 1 object(s):
    [32, 800) 'buf' (line 378) <== Memory access at offset 776 partially overflows this variable
HINT: this may be a false positive if your program uses some custom stack unwind mechanism, swapcontext or vfork
      (longjmp and C++ exceptions *are* supported)
SUMMARY: AddressSanitizer: unknown-crash (/home/thom/git/phd/dilithium/avx2/test/test_dilithium4aes+0x4c9fa) in pqcrystals_dilithium4aes_avx2_rej_uniform_avx
Shadow bytes around the buggy address:
  0x10005fcd8830: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x10005fcd8840: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x10005fcd8850: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x10005fcd8860: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x10005fcd8870: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
=>0x10005fcd8880: 00 00 00 00 00 00 00 00 00[00]00 00 f3 f3 f3 f3
  0x10005fcd8890: f3 f3 f3 f3 f3 f3 f3 f3 f3 f3 f3 f3 00 00 00 00
  0x10005fcd88a0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x10005fcd88b0: 00 00 00 00 f1 f1 f1 f1 00 00 00 f2 f2 f2 00 00
  0x10005fcd88c0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x10005fcd88d0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
Shadow byte legend (one shadow byte represents 8 application bytes):
  Addressable:           00
  Partially addressable: 01 02 03 04 05 06 07 
  Heap left redzone:       fa
  Freed heap region:       fd
  Stack left redzone:      f1
  Stack mid redzone:       f2
  Stack right redzone:     f3
  Stack after return:      f5
  Stack use after scope:   f8
  Global redzone:          f9
  Global init order:       f6
  Poisoned by user:        f7
  Container overflow:      fc
  Array cookie:            ac
  Intra object redzone:    bb
  ASan internal:           fe
  Left alloca redzone:     ca
  Right alloca redzone:    cb
  Shadow gap:              cc
==291152==ABORTING

Interestingly, the PQCgenKAT executables run fine.

Make PQCgenKAT_sign in RPi4

On the ARM processor using a 32 bit operating system, the long long type in rng.h, rng.c and PQCgenKAT_sign.c causes a segmentation fault when calling randombytes(seedbuf, SEEDBYTES) for generating the keypair. Changing the type to int appears to fix this although I am unsure if this is stable or optimal for the processor.

Error while usimg shared library usr/bin/ld: cannot find -llibpqcrystals_dilithium2_ref

Hi,
I want to use dilithium library in my application. I trying to compile my program by linking the shared library with the following command
sudo gcc -o dilithium dilithium.c -L/home/lucy/dilithium/ref/lib -llibpqcrystals_dilithium2_ref -I /home/lucy/dilithium/ref/include
but it shows the error usr/bin/ld : cannot find -llibpqcrystals_dilithium2_ref. I am struck here.
I am new learner . Can someone guide me how to use the library in my application?

Off-by-one error in documentation for reduce32

The documentation for reduce32 states that the output is in the range [-6283009, 6283007]. The range is actually [-6283009, 6283008], as evaluating reduce32 at 2^{31} - 2^{22} - 1 will illustrate.

I have a branch which fixes both this issue and #55 since they're quite minor.

Can we use the NTT functionality of Crystals-Dilithium for LWE encryption?

Hi,
We are trying to implement LWE encryption using the structure of Crystals-Dilithium :
-- Our vectors and the data types are same as that of the Crystals-Dilithium Library
--- Q , invQ and all constants are same.
-- We are using Shake to compute A , s1 and s2

The only problem occurs during decryption:
We have public key : bt= As1+s2
Encryption : u= Ar ; c= bt r + bit.q/2

Decryption: c-s1u= bt r + bit.q/2 - s1 Ar = As1r + s2r + bit.q/2 - s1Ar

NTT multiplication 👍
public key : ntt(s1), polypointwise(bt,a, S1) , polyvec_add(bt, s2) , reduce (bt)
u= ntt(r) , polypointwise(u, A, r)
c: polypointwise(c1,bt, r), reduce(c1), polyvec_add( c1. bit.q/2) polyreduce(c) invntt_to_mont(c)

Decryption: d1= polypointwise(s, u) , reduce(d1) , invntt(d1)
d= poly_sub(c, d1)

We suspect that reduce() is causing the non cancellation of the bigger terms during decryption and we are not getting the final value as : s2r + bit.q/2.

How do you suggest we tackle this issue?

"ExpandMask" vs. rej_gamma1m1()

Hello,

On page 16 of the 2nd round Dilithium specification, the function ExpandMask() is described under paragraph "Sampling the vectors y." I think that this is meant to correspond to functions poly_uniform_gamma1m1() and rej_gamma1m1() in the reference implementation file poly.c.

If you look at code after poly.c:500, you will observe that the "high 20 bits" quantity t1 is not used on line 506 if ctr == len after line 504. Based on testing this happens quite frequently (due to rejection sampling being integrated into the same loop), but the specification description ignores the possibility, stating "On the resulting sequence of 20 bit integers rejection sampling is performed".

    pos += 5;

    if(t0 <= 2*GAMMA1 - 2)
      a[ctr++] = Q + GAMMA1 - 1 - t0;

	//	XXX mjos: is the code ignoring a valid t1 altogether?
	if (ctr >= len && t1 <= 2*GAMMA1 - 2)
		fprintf(stderr, "rej_gamma1m1()  t1 ignored\n");

    if(t1 <= 2*GAMMA1 - 2 && ctr < len)
      a[ctr++] = Q + GAMMA1 - 1 - t1;

This has no security implications that I can think of; just makes meeting the test vectors with an independent implementation more difficult.

Luckily this affects operation extremely rarely with current parameters.

Cheers,

• markku

ps. Perhaps add comments to the effect "this is ExpandMask" to the functions in question.

Setting mode=3 causes hang

If I set MODE to 3 in params.h test_dilithium doesn't seem to complete in both the ref and avx implementations.