FrodoKEM

Standard FrodoKEM

This variant, referred to as simply FrodoKEM, includes countermeasures against some multi-ciphertext attacks and, thus, allows for key reuse (i.e., it is suitable for applications in which a large number of ciphertexts may be encrypted to a single public key).

Contents

• KAT folder: Known Answer Test (KAT) files for the KEM.
• src folder: C and header files. Public APIs can be found in api_frodo640.h, api_frodo976.h and api_frodo1344.h.
  • Optimized matrix operations: optimized implementation of the matrix operations.
  • Reference matrix operations: reference implementation of the matrix operations.
  • src/aes folder: AES implementation.
  • src/random folder: randombytes function using the system random number generator.
  • src/sha3 folder: SHA-3 / SHAKE128 / SHAKE256 implementation.
• tests folder: test files.
• VisualStudio folder: Visual Studio 2022 files for compilation in Windows.
• Makefile: Makefile for compilation using the GNU GCC or clang compilers on Unix-like operative systems.
• README.md: this readme file.
• python3 folder: a Python3 reference implementation

Complementary crypto functions

Random values are generated with /dev/urandom on Unix-like operative systems, and CNG's BCryptGenRandom function in Windows. Check the folder random for details.

The library includes standalone implementations of AES and SHAKE. The generation of the matrix "A" (see the specification document [1]) can be carried out with either AES128 or SHAKE128. By default AES128 is used.

There are two options for AES: the standalone implementation that is included in the software or OpenSSL's AES implementation. OpenSSL's AES implementation is used by default.

Implementation Options

The following implementation options are available:

• Reference portable implementation enabled by setting OPT_LEVEL=REFERENCE.
• Optimized portable implementation enabled by setting OPT_LEVEL=FAST_GENERIC.
• Optimized x64 implementation using AVX2 intrinsics and AES-NI instructions enabled by setting ARCH=x64 and OPT_LEVEL=FAST.

Follow the instructions in the sections "Instructions for Linux" or "Instructions for Windows" below to configure these different implementation options.

Instructions for Linux

Using AES128

By simply executing:

$ make

the library is compiled for x64 using gcc, and optimization level FAST, which uses AVX2 instrinsics. AES128 is used by default to generate the matrix "A". For AES, OpenSSL's AES implementation is used by default.

Testing and benchmarking results are obtained by running:

$ ./frodo640/test_KEM
$ ./frodo976/test_KEM
$ ./frodo1344/test_KEM

To run the implementations against the KATs, execute:

$ ./frodo640/PQCtestKAT_kem
$ ./frodo976/PQCtestKAT_kem
$ ./frodo1344/PQCtestKAT_kem

Using SHAKE128

By executing:

$ make GENERATION_A=SHAKE128

the library is compiled for x64 using gcc, and optimization level FAST, which uses AVX2 instrinsics. SHAKE128 is used to generate the matrix "A".

Testing and benchmarking results are obtained by running:

$ ./frodo640/test_KEM
$ ./frodo976/test_KEM
$ ./frodo1344/test_KEM

To run the implementations against the KATs, execute:

$ ./frodo640/PQCtestKAT_kem_shake
$ ./frodo976/PQCtestKAT_kem_shake
$ ./frodo1344/PQCtestKAT_kem_shake

Additional options

These are all the available options for compilation:

$ make CC=[gcc/clang] ARCH=[x64/x86/ARM/PPC/s390x] OPT_LEVEL=[REFERENCE/FAST_GENERIC/FAST] GENERATION_A=[AES128/SHAKE128] USE_OPENSSL=[TRUE/FALSE]

Note that the FAST option is only available for x64 with support for AVX2 and AES-NI instructions. The USE_OPENSSL flag specifies whether OpenSSL's AES implementation is used (=TRUE) or if the standalone AES implementation is used (=FALSE). Therefore, this flag only applies when GENERATION_A= AES128 (or if GENERATION_A is left blank).

If OpenSSL is being used and is installed in an alternate location, use the following make options:

OPENSSL_INCLUDE_DIR=/path/to/openssl/include
OPENSSL_LIB_DIR=/path/to/openssl/lib

The program tries its best at auto-correcting unsupported configurations. For example, since the FAST implementation is currently only available for x64 doing make ARCH=x86 OPT_LEVEL=FAST is actually processed using ARCH=x86 OPT_LEVEL=FAST_GENERIC.

Instructions for Windows

Building the library with Visual Studio:

Open the solution file frodoKEM.sln in Visual Studio, and choose either x64 or x86 from the platform menu. Make sure Fast_generic is selected in the configuration menu. Finally, select "Build Solution" from the "Build" menu.

Running the tests:

After building the solution file, there should be three executable files: test_KEM640.exe, test_KEM976.exe and test_KEM1344.exe, to run tests for the KEM.

Using the library:

After building the solution file, add the generated FrodoKEM-640.lib, FrodoKEM-976.lib and FrodoKEM-1344.lib library files to the set of References for a project, and add api_frodo640.h, api_frodo976.h and api_frodo1344.h to the list of header files of a project.

Python3 implementation

The python3 folder contains a Python3 implementation of FrodoKEM. This reference implementation is a line-by-line transcription of the pseudocode from the FrodoKEM specification and includes extensive comments. The file frodokem.py contains a Python3 class implementing all 6 variants of FrodoKEM. The file nist_kat.py contains a minimal Python port of the known answer test (KAT) code; it should generate the same output as the C version for the first test vector (except that the line seed = will differ).

It can be run as follows:

pip3 install bitstring cryptography
cd python3
python3 nist_kat.py

WARNING: This Python3 implementation of FrodoKEM is not designed to be fast or secure, and may leak secret information via timing or other side channels; it should not be used in production environments.