microsoft / pqcrypto-lweke

FrodoKEM: Learning with Errors Key Encapsulation. FrodoKEM is a family of key-encapsulation mechanisms that are designed to be conservative yet practical post-quantum constructions whose security derives from cautious parameterizations of the well-studied learning with errors problem.

FrodoKEM: Learning with Errors Key Encapsulation

This C library implements FrodoKEM, an IND-CCA secure key encapsulation (KEM) protocol based on the well-studied Learning with Errors (LWE) problem [1,3], which in turn has close connections to conjectured-hard problems on generic, "algebraically unstructured" lattices. This package also includes Python reference implementations. FrodoKEM is conjectured to be secure against quantum computer attacks.

FrodoKEM consists of two main variants:

• A standard variant (simply called FrodoKEM) that does not impose any restriction on the reuse of key pairs (i.e., it is suitable for applications in which a large number of ciphertexts may be encrypted to a single public key), and
• An ephemeral variant (called eFrodoKEM) that is suitable for applications in which not many ciphertexts are encrypted to a single public-key.

In contrast to eFrodoKEM, standard FrodoKEM uses an enlarged seed for generating the seed for sampling the secret and error matrices, and includes an additional salt in one of the hashing computations in encapsulation and decapsulation. These countermeasures safeguard standard FrodoKEM against some multi-ciphertext attacks. Refer to [3] for more details on these two variants.

Concretely, this library includes the following KEM schemes using AES128 for the generation of the public matrix "A":

• FrodoKEM-640-AES and eFrodoKEM-640-AES: matching the post-quantum security of AES128.
• FrodoKEM-976-AES and eFrodoKEM-976-AES: matching the post-quantum security of AES192.
• FrodoKEM-1344-AES and eFrodoKEM-1344-AES: matching the post-quantum security of AES256.

And the following KEM schemes using SHAKE128 for the generation of the public matrix "A":

• FrodoKEM-640-SHAKE and eFrodoKEM-640-SHAKE: matching the post-quantum security of AES128.
• FrodoKEM-976-SHAKE and eFrodoKEM-976-SHAKE: matching the post-quantum security of AES192.
• FrodoKEM-1344-SHAKE and eFrodoKEM-1344-SHAKE: matching the post-quantum security of AES256.

The label "eFrodoKEM" corresponds to the ephemeral variants.

The library was developed by the FrodoKEM team and Microsoft Research for experimentation purposes.

Contents

• eFrodoKEM folder: C and Python3 implementations of eFrodoKEM.
• FrodoKEM folder: C and Python3 implementations of standard FrodoKEM.
• LICENSE: MIT license file.
• README.md: this readme file.

Supported Platforms

The FrodoKEM library is supported on a wide range of platforms including x64, x86, ARM, PowerPC and s390x processors running Windows, Linux or macOS, and supports both little-endian and big-endian formats. We have tested the library with Microsoft Visual Studio, GNU GCC, and clang.

License

This software is licensed under the MIT License; see the LICENSE file for details. The Python3 implementation is licensed under the Creative Commons Zero v1.0 Universal license. It includes some third party modules that are licensed differently. In particular:

• <FrodoKEM_variant>/src/aes/aes_c.c: public domain
• <FrodoKEM_variant>/src/aes/aes_ni.c: public domain
• <FrodoKEM_variant>/src/sha3/fips202.c: public domain
• <FrodoKEM_variant>/src/sha3/fips202x4.c: public domain
• <FrodoKEM_variant>/src/sha3/keccak4x: all files in this folder are public domain (CC0), excepting
• <FrodoKEM_variant>/src/sha3/keccak4x/brg_endian.h which is copyrighted by Brian Gladman and comes with a BSD 3-clause license.
• <FrodoKEM_variant>/tests/ds_benchmark.h: public domain
• <FrodoKEM_variant>/tests/PQCtestKAT_kem<#>.c: copyrighted by Lawrence E. Bassham
• <FrodoKEM_variant>/tests/PQCtestKAT_kem<#>_shake.c: copyrighted by Lawrence E. Bassham
• <FrodoKEM_variant>/tests/rng.c: copyrighted by Lawrence E. Bassham

References

[1] Erdem Alkim, Joppe W. Bos, Léo Ducas, Karen Easterbrook, Brian LaMacchia, Patrick Longa, Ilya Mironov, Michael Naehrig, Valeria Nikolaenko, Chris Peikert, Ananth Raghunathan, and Douglas Stebila, "FrodoKEM: Learning With Errors Key Encapsulation". Submission to the NIST Post-Quantum Standardization project, 2021-2023. The round 3 specification of FrodoKEM is available here.

[2] Joppe W. Bos, Craig Costello, Léo Ducas, Ilya Mironov, Michael Naehrig, Valeria Nikolaenko, Ananth Raghunathan, and Douglas Stebila, "Frodo: Take off the ring! Practical, quantum-secure key exchange from LWE". ACM CCS 2016, 2016. The preprint version is available here.

[3] FrodoKEM team, "FrodoKEM: Learning With Errors Key Encapsulation - Preliminary Draft Standards". Submission to ISO/IEC JTC1/SC27/WG2, 2023. The preliminary draft is available here.

Contributing

This project has adopted the Microsoft Open Source Code of Conduct. For more information see the Code of Conduct FAQ or contact [email protected] with any additional questions or comments.

pqcrypto-lweke's Issues

Measure of level of security

Documentation says "FrodoKEM-640-AES: matching the post-quantum security of AES128".
Does the algorithm describe a measure of security level?
If I were to make changes to the code, is there a metric that I can verify against in order to state my algorithm to be secure?
Or is passing against the Known Answer Tests the only check?

Building on MSYS2

I am attempting to use this library in a cross platform (between GNU+Linux and Windows [not really worried about Mac]) cryptographic tool I am making (Using Mingw64 for the Windows portion)

Compilation completes successfully under Mingw64, however when the tests (.\test_KEM.exe) are run, it just sits maxing out a single CPU core for a very long time. (>10 minutes and still not complete)

To attempt to remedy this, I have tried various permutations of the build options, and see no change.

I have run this on a GNU+Linux machine (with opt_level set to reference) that has a Core 2 Duo and it takes roughly 30 seconds to complete the tests. Therefore it probably shouldn't take longer running on an i7-4770.

Any ideas for where this issue may be stemming from?
Thanks

Need clarification on working of Frodo.encode()

In words, the encode function interprets every B-bit substring (starting from the most significant bits) as a B-bit value (integers). These B-bit integers are encoded using ec() and are filled into a matrix row by row entry wise.

for example, if my bit string is
0b00110110 ...

the B-bit substrings are (B=2)
0b00 0b11 0b01 0b10 ...

intuitively this translates to integers 0, 3, 1, 2
but (algorithm 1) assumes little endian bit order for the substrings and translates to integers 0, 3, 2, 1

Am I right about the endianness of the substring?
Was there a specific reason the algorithm was designed this way? Is it because the parent bit string is assumed to be in little endian format too?

This repo is missing important files

There are important files that Microsoft projects should all have that are not present in this repository. A pull request has been opened to add the missing file(s). When the pr is merged this issue will be closed automatically.

Microsoft teams can learn more about this effort and share feedback within the open source guidance available internally.

Merge this pull request

Undefined behavior in FAST_GENERIC implementation

When clang's undefined behavior sanitizer is run on the FAST_GENERIC implementation, it identifies some signed integer overflows.

To reproduce, run the following on a Linux platform with clang-11 and valgrind installed, or enable the undefined behavior sanitizer in the GitHub Actions c.yml workflow in #22.

make CC=clang-11 OPT_LEVEL=FAST_GENERIC EXTRA_CFLAGS="-g3 -fno-omit-frame-pointer -fno-optimize-sibling-calls -fsanitize-address-use-after-scope -fsanitize=undefined"
frodo640/test_KEM

Relevant parts of the output:

src/frodo_macrify.c:178:34: runtime error: signed integer overflow: 65535 * 33392 cannot be represented in type 'int'
SUMMARY: UndefinedBehaviorSanitizer: undefined-behavior src/frodo_macrify.c:178:34 in 
src/frodo_macrify.c:179:34: runtime error: signed integer overflow: 65535 * 39246 cannot be represented in type 'int'
SUMMARY: UndefinedBehaviorSanitizer: undefined-behavior src/frodo_macrify.c:179:34 in 
src/frodo_macrify.c:180:34: runtime error: signed integer overflow: 65535 * 58836 cannot be represented in type 'int'
SUMMARY: UndefinedBehaviorSanitizer: undefined-behavior src/frodo_macrify.c:180:34 in 
src/frodo_macrify.c:181:34: runtime error: signed integer overflow: 65534 * 54684 cannot be represented in type 'int'
SUMMARY: UndefinedBehaviorSanitizer: undefined-behavior src/frodo_macrify.c:181:34 in 

Unclear why PARAMS_NBAR has be a multiple of 8

Hi,
I did not understand the purpose of PARAMS_NBAR in the reference code, and why should it be a multiple of 8.
Also, Regev'05 did not use PARAMS_NBAR parameter in their LWE proposal.

Can you help me understand it?

round() makes a mistake

Hi,

When I used the python implementation to run an experiment, I found an error in decode method when E''' = 2^(D-B-1). It should make a decryption failure, but that didn't happen! Like this,

round(51200*16/65536)=12 #51200*16/65536=12.5

I found that the reason is round() returns a mistake answer sometimes because the peoperty of float number .
So, why not replace
round(a)
with
math.floor(a+0.5)

Use of /dev/random in random.c and quantum computing attacks

If we conjecture that frodokem's secure key encapsulation protocol is actually secure against quantum computer attacks, the reliance upon /dev/random is still in question, is it not? Perhaps this project could also examine the implementation of quantum effects as a source of randomness, including radioactive decay, rather than relying solely upon the Linux kernel for entropy generation. How to package this in a trustless way (not relying on a 3rd party source for the quantum effects) with every personal computer is another question entirely :)

Example of this would be: https://www.fourmilab.ch/hotbits/

Python implementation is not constant time

The __ctverify does not run in constant time as Python ignores the second argument to and if the first is False.

Easily verified with

def __ctverify(a,b):
    r = True
    for i in range(len(a)):
        r = r and (a[i] == b[i])
    return r

a = [0]*1000000
b = list(a)
b[0] = 1

import time

start = time.time()
__ctverify(a,b)
print (time.time() - start)

start = time.time()
__ctverify(a,a)
print (time.time() - start)

Unclear indexing in s

PQCrypto-LWEKE/src/frodo_macrify_reference.c

Line 59 in d5bbd04

sum += A[i*PARAMS_N + j] * s[k*PARAMS_N + j];

It seems like you are indexing s as if it is in column major order. Is this really correct?

return value of randombytes() not checked

For example during key generation:

PQCrypto-LWEKE/src/kem.c

Line 35 in 4210d53

randombytes(randomness, CRYPTO_BYTES + CRYPTO_BYTES + BYTES_SEED_A);

randombytes() can fail on Windows, which will go unnoticed and will lead to an insecure (possibly completely deterministic) key!

Additionally: the code in randombytes.c is not very well written for other reasons. On Linux, the code will simply deadlock if \dev\urandom is not available. And if you ever compile without either WINDOWS or NIX, then it defaults to returning passed instead of failed. But that last point doesn't actually matter, since the return value is not checked anyway...

enable PQCrypto-LWEKE on s390x

The PQCrypto-LWEKE library has been tested on s390x architecture with a configuration very similar to PPC. On initial exploration, it looks like the PPC configurations can work efficiently on s390x. The goal is to try out the Power PC configuration on s390x, build and test and make the changes needed to enable it.