microsoft/fourqlib

FourQlib is an efficient and portable cryptographic library that provides functions for computing elliptic curve based operations on the high-performance FourQ curve.

FourQlib v3.1 (C Edition)

FourQlib implements essential elliptic curve and cryptographic functions based on FourQ, a high-security, high-performance elliptic curve that targets the 128-bit security level [1]. At the high level, FourQlib consists of a set of implementations targeting different platforms with different levels of portability and performance. The cryptographic and elliptic curve API is common to all the implementations.

The library was developed by Microsoft Research and is available under the MIT License.

Contents

Version 3.1 includes the following implementations:

• FourQ_32bit: a portable implementation especially tailored for 32-bit platforms.
• FourQ_64bit_and_portable: a portable implementation for 32-bit and 64-bit platforms with optional optimizations for x64 and 64-bit ARMv8 platforms.
• FourQ_ARM: an optimized implementation for 32-bit ARMv6, ARMv7 and ARMv7-M (Cortex-M4) platforms.
• FourQ_ARM_side_channel: an optimized implementation for 32-bit ARMv6, ARMv7 and ARMv7-M (Cortex-M4), including strong countermeasures against a wide variety of side-channel attacks.
• FourQ_ARM_NEON: an optimized implementation for 32-bit ARM platforms with NEON support.

The elliptic curve and crypto API can be found in FourQ_api.h, which is available per implementation.

The FourQ-Magma folder includes easy-to-read scripts written in Magma.

Complementary cryptographic functions

Random values are generated with /dev/urandom in the case of Linux, and with the function BCryptGenRandom() in the case of Windows. Check the random folder for details.

The library includes an implementation of SHA-512 which is used by default by SchnorrQ signatures (see sha512).

Users can provide their own PRNG and hash implementations by replacing the functions in the random and sha512folders, and applying the corresponding changes to the settings in FourQ.h (in a given implementation). Refer to [2] for the security requirements for the cryptographic hash function.

What's new

In version 3.0

• New support for co-factor ECDH and SchnorrQ signatures.
• New implementations for 32-bit processors, 32-bit ARMv6 and ARMv7 processors, and 32-bit ARM Cortex-M4 microcontroller.
• New implementation for ARMv6/ARMv7/ARMv7-M with strong countermeasures against several side-channel attacks.
• New support for 64-bit ARMv8 processors.

In version 3.1

• New hash to curve functionality (only supported in the portable implementation FourQ_64bit_and_portable).

Main features

• Support for co-factor Elliptic Curve Diffie-Hellman (ECDH) key exchange [3], the SchnorrQ digital signature scheme [2], and hash to curve conversion.
• Support for 3 core elliptic curve operations: variable-base, fixed-base and double-scalar multiplications.
• Support for Windows using Microsoft Visual Studio and Linux using GNU GCC or clang.
• Includes a basic implementation using portable C to enable support on a wide range of platforms including x64, x86 and ARM, Windows and Linux.
• Includes optimized implementations for 64-bit ARMv8 and x64 platforms with optional, high-performance x64 assembly for Linux [1].
• Includes high-performance implementations for 32-bit ARM processors with NEON support [4], for 32-bit ARMv6 and ARMv7 processors, and for 32-bit ARM Cortex-M4 microcontrollers [5].
• Includes side-channel secure implementations for 32-bit ARMv6/ARMv7 and for ARMv7-M (Cortex-M4) microcontrollers [5].
• Includes testing and benchmarking code for field arithmetic, elliptic curve and cryptographic functions.
• All functions evaluating secret data have regular, constant-time execution, protecting against timing and cache attacks.
• Includes an option to disable the use of the fast endomorphisms.

Quick start

Building the library and executing the tests on Linux

One can quickly test a given implementation by executing from the corresponding folder and using a supported architecture:

$ make ARCH=[x64/x86/ARM/ARM64] 

GNU GCC is used by default. After compilation, run fp_tests, ecc_tests or crypto_tests.

Below are the architectures supported by each implementation:

• FourQ_32bit: x86 and ARM
• FourQ_64bit_and_portable: x64, x86, ARM and ARM64
• FourQ_ARM, FourQ_ARM_side_channel and FourQ_ARM_NEON: ARM

For example, to compile the optimized x64 implementation using assembly with GNU GCC, using the efficient endomorphisms on a machine with AVX2 support (e.g, Intel's Haswell or Skylake), execute:

$ cd FourQ_64bit_and_portable
$ make ARCH=x64

Additional compilation options are available. Refer to the README files in a given implementation folder for complete details.

NOTE: the above instructions apply to all the "processor-class" implementations. For instructions on how to compile on an ARM Cortex-M (ARMv7-M) microcontroller, refer to the README files in FourQ_ARM_side_channel or FourQ_ARM.

Building the library and executing the tests on Windows

FourQ_32bit and FourQ_64bit_and_portable include Visual Studio solutions for compilation on Windows. Refer to the corresponding README files for instructions.

License

FourQlib is licensed under the MIT License; see License for details.

Files stm32f4_wrapper.c and stm32f4_wrapper.h in the FourQ_ARM and FourQ_ARM_side_channel folders are by Joost Rijneveld and are released under the CC0 1.0 Universal license.

Files in the folder FourQ_ARM_side_channel/libopencm3 and FourQ_ARM/libopencm3 are from the libopencm3 project and are under the GNU LGPL v3.0 license.

The SHA-512 implementation is by D.J. Bernstein and is released to the public domain.

References

[1] Craig Costello and Patrick Longa, "FourQ: four-dimensional decompositions on a Q-curve over the Mersenne prime". Advances in Cryptology - ASIACRYPT 2015, 2015. The extended version is available here.

[2] Craig Costello and Patrick Longa. "SchnorrQ: Schnorr signatures on FourQ". MSR Technical Report, 2016. Available here.

[3] Watson Ladd, Patrick Longa and Richard Barnes, "Curve4Q". Internet-Draft, draft-ladd-cfrg-4q-01, 2017. Available here.

[4] Patrick Longa, "FourQNEON: faster elliptic curve scalar multiplications on ARM processors". Selected Areas in Cryptography (SAC 2016), 2016. Preprint available here.

[5] Zhe Liu, Patrick Longa, Geovandro Pereira, Oscar Reparaz and Hwajeong Seo, "FourQ on embedded devices with strong countermeasures against side-channel attacks". Preprint 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.

fourqlib's Issues

article suggesting speed-up using avx512 IFMA

The recently launched gen3 Ice Lake Server chips added the avx512 IFMA instructions.
An article on medium, "Even faster Edwards curves with IFMA", suggests that FourQ might benefit from the same speed-up.
see https://medium.com/@hdevalence/even-faster-edwards-curves-with-ifma-8b1e576a00e9

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

Why is Last Byte of FourQ Signature always 00?

Does this have something to do with the curve chosen?
By the way, 4D decomposition optimization is pretty awesome.

Thanks in advance.

Make Github Release of Version 3.0.0

This library doesn't appear to be maintained. Perhaps it's effectively feature complete. In any case, a github release with a semantic version number would make this library more usable by the OSS community.

Failed to run on Tencent Cloud, Tencent customer service said that there is a problem with the warehouse you provided

I want to know if you have encountered similar problems and how to solve them. Tencent customer service said that there is a problem with the library provided by Microsoft.

`fp_test`s do not pass with `gcc 11.4.1`

Am I missing something here? Below are the versions of gcc and clang. Then, the output of running

[ec2-user@ip-172-31-28-24 FourQ_64bit_and_portable]$ gcc --version
gcc (GCC) 11.4.1 20230605 (Red Hat 11.4.1-2)
Copyright (C) 2021 Free Software Foundation, Inc.
This is free software; see the source for copying conditions.  There is NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.

[ec2-user@ip-172-31-28-24 FourQ_64bit_and_portable]$ clang --version
clang version 15.0.7 (Amazon Linux 15.0.7-3.amzn2023.0.1)
Target: x86_64-amazon-linux-gnu
Thread model: posix
InstalledDir: /usr/bin

This seems to be related to the version of gcc (see above for the problematic version) when coupled with the optimization level -O2 or -O3 do it but lower levels do not. (I am able to get the tests below to pass with gcc 7.3.1 but I did not investigate what is the oldest version of gcc which fails.

[ec2-user@ip-172-31-28-24 ~]$ git clone https://github.com/microsoft/FourQlib.git
Cloning into 'FourQlib'...
remote: Enumerating objects: 405, done.
remote: Counting objects: 100% (49/49), done.
remote: Compressing objects: 100% (45/45), done.
remote: Total 405 (delta 11), reused 19 (delta 4), pack-reused 356
Receiving objects: 100% (405/405), 1.27 MiB | 18.50 MiB/s, done.
Resolving deltas: 100% (216/216), done.
[ec2-user@ip-172-31-28-24 ~]$ cd FourQlib/FourQ_64bit_and_portable/
[ec2-user@ip-172-31-28-24 FourQ_64bit_and_portable]$ make ARCH=x64 CC=gcc
gcc -c -O3      -fwrapv -fomit-frame-pointer -march=native -mavx2 -D _AMD64_ -D __LINUX__ -D _AVX_ -D _AVX2_ -D _ASM_  -D USE_ENDO   tests/crypto_tests.c
gcc -c -O3      -fwrapv -fomit-frame-pointer -march=native -mavx2 -D _AMD64_ -D __LINUX__ -D _AVX_ -D _AVX2_ -D _ASM_  -D USE_ENDO   eccp2.c
gcc -c -O3      -fwrapv -fomit-frame-pointer -march=native -mavx2 -D _AMD64_ -D __LINUX__ -D _AVX_ -D _AVX2_ -D _ASM_  -D USE_ENDO   eccp2_no_endo.c
gcc -c -O3      -fwrapv -fomit-frame-pointer -march=native -mavx2 -D _AMD64_ -D __LINUX__ -D _AVX_ -D _AVX2_ -D _ASM_  -D USE_ENDO   eccp2_core.c
gcc -c -O3      -fwrapv -fomit-frame-pointer -march=native -mavx2 -D _AMD64_ -D __LINUX__ -D _AVX_ -D _AVX2_ -D _ASM_  -D USE_ENDO   -S -o AMD64/consts.s AMD64/consts.c
sed '/.globl/d' -i AMD64/consts.s
gcc -c -O3      -fwrapv -fomit-frame-pointer -march=native -mavx2 -D _AMD64_ -D __LINUX__ -D _AVX_ -D _AVX2_ -D _ASM_  -D USE_ENDO   -o fp2_1271_AVX2.o AMD64/fp2_1271_AVX2.S
gcc -c -O3      -fwrapv -fomit-frame-pointer -march=native -mavx2 -D _AMD64_ -D __LINUX__ -D _AVX_ -D _AVX2_ -D _ASM_  -D USE_ENDO   crypto_util.c
crypto_util.c: In function ‘decode’:
crypto_util.c:114:9: warning: ‘fp2neg1271’ accessing 32 bytes in a region of size 16 [-Wstringop-overflow=]
  114 |         fp2neg1271(P->x);
      |         ^~~~~~~~~~~~~~~~
crypto_util.c:114:9: note: referencing argument 1 of type ‘digit_t (*)[2]’ {aka ‘long unsigned int (*)[2]’}
In file included from crypto_util.c:9:
FourQ_internal.h:287:6: note: in a call to function ‘fp2neg1271’
  287 | void fp2neg1271(f2elm_t a);
      |      ^~~~~~~~~~
gcc -c -O3      -fwrapv -fomit-frame-pointer -march=native -mavx2 -D _AMD64_ -D __LINUX__ -D _AVX_ -D _AVX2_ -D _ASM_  -D USE_ENDO   schnorrq.c
gcc -c -O3      -fwrapv -fomit-frame-pointer -march=native -mavx2 -D _AMD64_ -D __LINUX__ -D _AVX_ -D _AVX2_ -D _ASM_  -D USE_ENDO   hash_to_curve.c
gcc -c -O3      -fwrapv -fomit-frame-pointer -march=native -mavx2 -D _AMD64_ -D __LINUX__ -D _AVX_ -D _AVX2_ -D _ASM_  -D USE_ENDO   kex.c
gcc -c -O3      -fwrapv -fomit-frame-pointer -march=native -mavx2 -D _AMD64_ -D __LINUX__ -D _AVX_ -D _AVX2_ -D _ASM_  -D USE_ENDO   ../sha512/sha512.c
gcc -c -O3      -fwrapv -fomit-frame-pointer -march=native -mavx2 -D _AMD64_ -D __LINUX__ -D _AVX_ -D _AVX2_ -D _ASM_  -D USE_ENDO   ../random/random.c
gcc -c -O3      -fwrapv -fomit-frame-pointer -march=native -mavx2 -D _AMD64_ -D __LINUX__ -D _AVX_ -D _AVX2_ -D _ASM_  -D USE_ENDO   tests/test_extras.c
gcc -o crypto_test crypto_tests.o eccp2.o eccp2_no_endo.o eccp2_core.o fp2_1271_AVX2.o crypto_util.o schnorrq.o hash_to_curve.o kex.o sha512.o random.o  test_extras.o  
gcc -c -O3      -fwrapv -fomit-frame-pointer -march=native -mavx2 -D _AMD64_ -D __LINUX__ -D _AVX_ -D _AVX2_ -D _ASM_  -D USE_ENDO   tests/ecc_tests.c
gcc -o ecc_test ecc_tests.o eccp2.o eccp2_no_endo.o eccp2_core.o fp2_1271_AVX2.o crypto_util.o schnorrq.o hash_to_curve.o kex.o sha512.o random.o  test_extras.o  
gcc -c -O3      -fwrapv -fomit-frame-pointer -march=native -mavx2 -D _AMD64_ -D __LINUX__ -D _AVX_ -D _AVX2_ -D _ASM_  -D USE_ENDO   tests/fp_tests.c
gcc -o fp_test fp_tests.o eccp2.o eccp2_no_endo.o eccp2_core.o fp2_1271_AVX2.o crypto_util.o schnorrq.o hash_to_curve.o kex.o sha512.o random.o  test_extras.o  
[ec2-user@ip-172-31-28-24 FourQ_64bit_and_portable]$ ./fp_test 

--------------------------------------------------------------------------------------------------------

Testing quadratic extension field arithmetic over GF((2^127-1)^2): 

  GF(p^2) multiplication tests .................................................................... PASSED
  GF(p^2) squaring tests........................................................................... PASSED
  GF(p^2) inversion tests... FAILED
[ec2-user@ip-172-31-28-24 FourQ_64bit_and_portable]$ make clean
rm -rf libFourQ.so crypto_test ecc_test fp_test *.o AMD64/consts.s
[ec2-user@ip-172-31-28-24 FourQ_64bit_and_portable]$ make ARCH=x64 CC=clang
clang -c -O3      -fwrapv -fomit-frame-pointer -march=native -mavx2 -D _AMD64_ -D __LINUX__ -D _AVX_ -D _AVX2_ -D _ASM_  -D USE_ENDO   tests/crypto_tests.c
clang -c -O3      -fwrapv -fomit-frame-pointer -march=native -mavx2 -D _AMD64_ -D __LINUX__ -D _AVX_ -D _AVX2_ -D _ASM_  -D USE_ENDO   eccp2.c
clang -c -O3      -fwrapv -fomit-frame-pointer -march=native -mavx2 -D _AMD64_ -D __LINUX__ -D _AVX_ -D _AVX2_ -D _ASM_  -D USE_ENDO   eccp2_no_endo.c
clang -c -O3      -fwrapv -fomit-frame-pointer -march=native -mavx2 -D _AMD64_ -D __LINUX__ -D _AVX_ -D _AVX2_ -D _ASM_  -D USE_ENDO   eccp2_core.c
clang -c -O3      -fwrapv -fomit-frame-pointer -march=native -mavx2 -D _AMD64_ -D __LINUX__ -D _AVX_ -D _AVX2_ -D _ASM_  -D USE_ENDO   -S -o AMD64/consts.s AMD64/consts.c
sed '/.globl/d' -i AMD64/consts.s
clang -c -O3      -fwrapv -fomit-frame-pointer -march=native -mavx2 -D _AMD64_ -D __LINUX__ -D _AVX_ -D _AVX2_ -D _ASM_  -D USE_ENDO   -o fp2_1271_AVX2.o AMD64/fp2_1271_AVX2.S
clang -c -O3      -fwrapv -fomit-frame-pointer -march=native -mavx2 -D _AMD64_ -D __LINUX__ -D _AVX_ -D _AVX2_ -D _ASM_  -D USE_ENDO   crypto_util.c
clang -c -O3      -fwrapv -fomit-frame-pointer -march=native -mavx2 -D _AMD64_ -D __LINUX__ -D _AVX_ -D _AVX2_ -D _ASM_  -D USE_ENDO   schnorrq.c
clang -c -O3      -fwrapv -fomit-frame-pointer -march=native -mavx2 -D _AMD64_ -D __LINUX__ -D _AVX_ -D _AVX2_ -D _ASM_  -D USE_ENDO   hash_to_curve.c
clang -c -O3      -fwrapv -fomit-frame-pointer -march=native -mavx2 -D _AMD64_ -D __LINUX__ -D _AVX_ -D _AVX2_ -D _ASM_  -D USE_ENDO   kex.c
clang -c -O3      -fwrapv -fomit-frame-pointer -march=native -mavx2 -D _AMD64_ -D __LINUX__ -D _AVX_ -D _AVX2_ -D _ASM_  -D USE_ENDO   ../sha512/sha512.c
clang -c -O3      -fwrapv -fomit-frame-pointer -march=native -mavx2 -D _AMD64_ -D __LINUX__ -D _AVX_ -D _AVX2_ -D _ASM_  -D USE_ENDO   ../random/random.c
clang -c -O3      -fwrapv -fomit-frame-pointer -march=native -mavx2 -D _AMD64_ -D __LINUX__ -D _AVX_ -D _AVX2_ -D _ASM_  -D USE_ENDO   tests/test_extras.c
clang -o crypto_test crypto_tests.o eccp2.o eccp2_no_endo.o eccp2_core.o fp2_1271_AVX2.o crypto_util.o schnorrq.o hash_to_curve.o kex.o sha512.o random.o  test_extras.o  
clang -c -O3      -fwrapv -fomit-frame-pointer -march=native -mavx2 -D _AMD64_ -D __LINUX__ -D _AVX_ -D _AVX2_ -D _ASM_  -D USE_ENDO   tests/ecc_tests.c
clang -o ecc_test ecc_tests.o eccp2.o eccp2_no_endo.o eccp2_core.o fp2_1271_AVX2.o crypto_util.o schnorrq.o hash_to_curve.o kex.o sha512.o random.o  test_extras.o  
clang -c -O3      -fwrapv -fomit-frame-pointer -march=native -mavx2 -D _AMD64_ -D __LINUX__ -D _AVX_ -D _AVX2_ -D _ASM_  -D USE_ENDO   tests/fp_tests.c
clang -o fp_test fp_tests.o eccp2.o eccp2_no_endo.o eccp2_core.o fp2_1271_AVX2.o crypto_util.o schnorrq.o hash_to_curve.o kex.o sha512.o random.o  test_extras.o  
[ec2-user@ip-172-31-28-24 FourQ_64bit_and_portable]$ ./fp_test 

--------------------------------------------------------------------------------------------------------

Testing quadratic extension field arithmetic over GF((2^127-1)^2): 

  GF(p^2) multiplication tests .................................................................... PASSED
  GF(p^2) squaring tests........................................................................... PASSED
  GF(p^2) inversion tests.......................................................................... PASSED
  Modular addition tests .......................................................................... PASSED
  Montgomery multiplication and conversion tests .................................................. PASSED
  Montgomery inversion tests....................................................................... PASSED

--------------------------------------------------------------------------------------------------------

Benchmarking quadratic extension field arithmetic over GF((2^127-1)^2): 

  GF(p^2) addition runs in ...............        7 cycles
  GF(p^2) subtraction runs in ............        7 cycles
  GF(p^2) squaring runs in ...............       20 cycles
  GF(p^2) multiplication runs in .........       29 cycles
  GF(p^2) inversion runs in ..............     2026 cycles
  Addition modulo the order runs in ......       19 cycles
  Subtraction modulo the order runs in ...       18 cycles
  Montgomery multiply mod order runs in ..      152 cycles
  Montgomery inversion mod order runs in .    50298 cycles
[ec2-user@ip-172-31-28-24 FourQ_64bit_and_portable]$ 

Any plans for Mac OS support?

This only supports Linux and Windows, are there any plans for MacOS support?

make error？

error：ld: symbol(s) not found for architecture x86_64

PamdeMacBook-Air:~ pam$ uname -a
Darwin PamdeMacBook-Air.local 21.2.0 Darwin Kernel Version 21.2.0: Sun Nov 28 20:28:54 PST 2021; root:xnu-8019.61.5~1/RELEASE_X86_64 x86_64

PamdeMacBook-Air:~ pam$ clang -v
Apple clang version 13.0.0 (clang-1300.0.29.30)
Target: x86_64-apple-darwin21.2.0
Thread model: posix
InstalledDir: /Library/Developer/CommandLineTools/usr/bin