microsoft / pqcrypto-sidh

SIDH Library is a fast and portable software library that implements state-of-the-art supersingular isogeny cryptographic schemes. The chosen parameters aim to provide security against attackers running a large-scale quantum computer, and security against classical algorithms.

Warning

The SIDH and SIKE protocols were proven insecure after a series of attacks starting with [14]. Therefore, these protocols MUST NOT be used in production.

The SIDH library is only presented here for historical reasons, and because some functionality may be reusable in other cryptographic applications.

SIDH v3.5.1 (C Edition)

The SIDH library is an efficient supersingular isogeny-based cryptography library written in C language. Version v3.5.1 of the library includes the ephemeral Diffie-Hellman key exchange scheme "SIDH" [1,2], and the CCA-secure key encapsulation mechanism "SIKE" [3]. These schemes are conjectured to be secure against quantum computer attacks.

Concretely, the SIDH library includes the following KEM schemes:

• SIKEp434: matching the post-quantum security of AES128 (level 1).
• SIKEp503: matching the post-quantum security of SHA3-256 (level 2).
• SIKEp610: matching the post-quantum security of AES192 (level 3).
• SIKEp751: matching the post-quantum security of AES256 (level 5).

And the following ephemeral key exchange schemes:

• SIDHp434: matching the post-quantum security of AES128 (level 1).
• SIDHp503: matching the post-quantum security of SHA3-256 (level 2).
• SIDHp610: matching the post-quantum security of AES192 (level 3).
• SIDHp751: matching the post-quantum security of AES256 (level 5).

It also includes the following compressed KEM schemes:

• SIKEp434_compressed: matching the post-quantum security of AES128 (level 1).
• SIKEp503_compressed: matching the post-quantum security of SHA3-256 (level 2).
• SIKEp610_compressed: matching the post-quantum security of AES192 (level 3).
• SIKEp751_compressed: matching the post-quantum security of AES256 (level 5).

And the following compressed ephemeral key exchange schemes:

• SIDHp434_compressed: matching the post-quantum security of AES128 (level 1).
• SIDHp503_compressed: matching the post-quantum security of SHA3-256 (level 2).
• SIDHp610_compressed: matching the post-quantum security of AES192 (level 3).
• SIDHp751_compressed: matching the post-quantum security of AES256 (level 5).

The compressed schemes exhibit reduced public keys at the expense of longer computing times. Their implementation is based on [11,12], which in turn are based on and improves upon [9] and [10].

The library was developed by Microsoft Research for experimentation purposes.

Contents

• KAT folder: Known Answer Test (KAT) files for the KEM.
• src folder: C and header files. Public APIs can be found in P434_api.h, P503_api.h, P610_api.h and P751_api.h.
• Optimized x64 implementation for p434: optimized implementation of the field arithmetic over the prime p434 for x64 platforms.
• Optimized x64 implementation for p503: optimized implementation of the field arithmetic over the prime p503 for x64 platforms.
• Optimized x64 implementation for p610: optimized implementation of the field arithmetic over the prime p610 for x64 platforms.
• Optimized x64 implementation for p751: optimized implementation of the field arithmetic over the prime p751 for x64 platforms.
• Optimized ARMv8 implementation for p434: optimized implementation of the field arithmetic over the prime p434 for 64-bit ARMv8 platforms.
• Optimized ARMv8 implementation for p503: optimized implementation of the field arithmetic over the prime p503 for 64-bit ARMv8 platforms.
• Optimized ARMv8 implementation for p610: optimized implementation of the field arithmetic over the prime p610 for 64-bit ARMv8 platforms.
• Optimized ARMv8 implementation for p751: optimized implementation of the field arithmetic over the prime p751 for 64-bit ARMv8 platforms.
• Generic implementation for p434: implementation of the field arithmetic over the prime p434 in portable C.
• Generic implementation for p503: implementation of the field arithmetic over the prime p503 in portable C.
• Generic implementation for p610: implementation of the field arithmetic over the prime p610 in portable C.
• Generic implementation for p751: implementation of the field arithmetic over the prime p751 in portable C.
• compression folder: main C files of the compressed variants.
• random folder: randombytes function using the system random number generator.
• sha3 folder: SHAKE256 implementation.
• Test folder: test files.
• Visual Studio folder: Visual Studio 2022 files for compilation in Windows.
• Makefile: Makefile for compilation using the GNU GCC or clang compilers on Linux.
• License: MIT license file.
• Readme: this readme file.

Main Features

• Supports IND-CCA secure key encapsulation mechanism.
• Supports ephemeral Diffie-Hellman key exchange.
• Includes compressed variants that feature reduced public key sizes.
• Supports four security levels matching the post-quantum security of AES128, SHA3-256, AES192 and AES256.
• Protected against timing and cache-timing attacks through regular, constant-time implementation of all operations on secret key material.
• Support for Windows OS using Microsoft Visual Studio, Linux OS and Mac OS X using GNU GCC and clang.
• Provides basic implementation of the underlying arithmetic functions using portable C to enable support on a wide range of platforms including x64, x86, ARM and s390x.
• Provides optimized implementations of the underlying arithmetic functions for x64 platforms with optional, high-performance x64 assembly for Linux and Mac OS X.
• Provides an optimized implementation of the underlying arithmetic functions for 64-bit ARM platforms using assembly for Linux.
• Includes Known Answer Tests (KATs), and testing/benchmarking code.

New in Version 3.3

• Improved versions of the four parameter sets for compressed SIDH and compressed SIKE [11,12].
• Optimized implementations of the field arithmetic for 64-bit ARMv8 processors for Linux.
• General optimizations to the field arithmetic.
• Support for Mac OS X for the optimized x64 assembly implementations.
• Support for big endian platforms, specifically IBM s390x processors.

New in Version 3.4

• Memory optimizations for compressed SIDH and compressed SIKE.

New in Versions 3.5 and 3.5.1

• New implementations of the quadratic extension field arithmetic for x64 processors on Linux [13].
• Countermeasure to protect the decapsulation step against the "Hertzbleed" vulnerability discovered in modern processors using frequency-scaling technology (see https://www.hertzbleed.com/).

Supported Platforms

SIDH v3.5.1 is supported on a wide range of platforms including x64, x86, ARM and s390x processors running Windows, Linux or Mac OS X. We have tested the library with Microsoft Visual Studio 2022, GNU GCC v5.4, and clang v3.8. See instructions below to choose an implementation option and compile on one of the supported platforms.

Implementation Options

The following implementation options are available:

• Portable implementations enabled by setting OPT_LEVEL=GENERIC.
• Optimized x64 assembly implementations for Linux\Mac OS X enabled by setting ARCH=x64 and OPT_LEVEL=FAST.
• Optimized ARMv8 assembly implementation for Linux\Mac OS X enabled by setting ARCH=ARM64 (or ARCH=M1 for Apple M1 SoC) 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\Mac OS X

By simply executing:

$ make

the library is compiled for x64 using clang, optimization level FAST, and using the special instructions MULX and ADX. Optimization level FAST enables the use of assembly, which in turn is a requirement to enable the optimizations using MULX/ADX.

Other options for x64:

$ make tests_pXXX ARCH=x64 CC=[gcc/clang] OPT_LEVEL=[FAST/GENERIC] USE_MULX=[TRUE/FALSE] USE_ADX=[TRUE/FALSE]

When OPT_LEVEL=FAST (i.e., assembly use enabled), the user is responsible for setting the flags MULX and ADX according to the targeted platform (for example, MULX/ADX are not supported on Sandy or Ivy Bridge, only MULX is supported on Haswell, and both MULX and ADX are supported on Broadwell, Skylake and Kaby Lake architectures). Note that USE_ADX can only be set to TRUE if USE_MULX=TRUE. The option USE_MULX=FALSE with USE_ADX=FALSE is only supported on p503 and p751. The use of tests_pXXX, for any value XXX in [434,503,610,751], allows to compile only one parameter set at a time.

Options for x86/ARM/M1/s390x:

$ make tests_pXXX ARCH=[x86/ARM/M1/s390x] CC=[gcc/clang]

Options for ARM64 or Apple M1:

$ make tests_pXXX ARCH=[ARM64/M1] CC=[gcc/clang] OPT_LEVEL=[FAST/GENERIC]

As in the x64 case, OPT_LEVEL=FAST enables the use of assembly optimizations on ARMv8 platforms.

Different tests and benchmarking results are obtained by running:

$ ./arith_tests-p434
$ ./arith_tests-p503
$ ./arith_tests-p610
$ ./arith_tests-p751
$ ./sike434/test_SIKE
$ ./sike503/test_SIKE
$ ./sike610/test_SIKE
$ ./sike751/test_SIKE
$ ./sidh434/test_SIDH
$ ./sidh503/test_SIDH
$ ./sidh610/test_SIDH
$ ./sidh751/test_SIDH
$ ./sike434_compressed/test_SIKE
$ ./sike503_compressed/test_SIKE
$ ./sike610_compressed/test_SIKE
$ ./sike751_compressed/test_SIKE
$ ./sidh434_compressed/test_SIDH
$ ./sidh503_compressed/test_SIDH
$ ./sidh610_compressed/test_SIDH
$ ./sidh751_compressed/test_SIDH

To run the KEM implementations against the KATs, execute:

$ ./sike434/PQCtestKAT_kem
$ ./sike503/PQCtestKAT_kem
$ ./sike610/PQCtestKAT_kem
$ ./sike751/PQCtestKAT_kem
$ ./sike434_compressed/PQCtestKAT_kem
$ ./sike503_compressed/PQCtestKAT_kem
$ ./sike610_compressed/PQCtestKAT_kem
$ ./sike751_compressed/PQCtestKAT_kem

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

Instructions for Windows

Building the library with Visual Studio:

Open the solution file SIDH.sln in Visual Studio, choose either x64 or Win32 from the platform menu and then choose either Fast or Generic from the configuration menu (as explained above, the option Fast is not currently available for x86). Finally, select "Build Solution" from the "Build" menu.

Running the tests:

After building the solution file, there should be the following executable files: arith_tests-P434.exe, arith_tests-P503.exe, arith_tests-P610.exe and arith_tests-P751.exe, to run tests for the underlying arithmetic, test-SIDHp[SET].exe to run tests for the key exchange, and test-SIKEp[SET].exe to run tests for the KEM, where SET = {434, 503, 610, 751, 434_compressed, 503_compressed, 610_compressed, 751_compressed}.

Using the library:

After building the solution file, add the generated P434.lib, P503.lib, P610.lib and P751.lib library files to the set of References for a project, and add P434_api.h, P503_api.h, P610_api.h, P751_api.h, P434_compressed_api.h, P503_compressed_api.h, P610_compressed_api.h and P751_compressed_api.h to the list of header files of a project.

License

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

The library includes some third party modules that are licensed differently. In particular:

• tests/aes/aes_c.c: public domain
• tests/rng/rng.c: copyrighted by Lawrence E. Bassham
• tests/PQCtestKAT_kem<#>.c: copyrighted by Lawrence E. Bassham
• src/sha3/fips202.c: public domain

Other contributors

• Basil Hess.
• Geovandro Pereira.
• Joost Renes.

References

[1] Craig Costello, Patrick Longa, and Michael Naehrig, "Efficient algorithms for supersingular isogeny Diffie-Hellman". Advances in Cryptology - CRYPTO 2016, LNCS 9814, pp. 572-601, 2016. The extended version is available here.

[2] David Jao and Luca DeFeo, "Towards quantum-resistant cryptosystems from supersingular elliptic curve isogenies". PQCrypto 2011, LNCS 7071, pp. 19-34, 2011. The extended version is available here.

[3] Reza Azarderakhsh, Matthew Campagna, Craig Costello, Luca De Feo, Basil Hess, Aaron Hutchinson, Amir Jalali, Koray Karabina, David Jao, Brian Koziel, Brian LaMacchia, Patrick Longa, Michael Naehrig, Geovandro Pereira, Joost Renes, Vladimir Soukharev, and David Urbanik, "Supersingular Isogeny Key Encapsulation (SIKE)", 2017.
The specifications document is available here.

[4] Craig Costello, and Huseyin Hisil, "A simple and compact algorithm for SIDH with arbitrary degree isogenies". Advances in Cryptology - ASIACRYPT 2017, LNCS 10625, pp. 303-329, 2017. The preprint version is available here.

[5] Armando Faz-Hernández, Julio López, Eduardo Ochoa-Jiménez, and Francisco Rodríguez-Henríquez, "A faster software implementation of the supersingular isogeny Diffie-Hellman key exchange protocol". IEEE Transactions on Computers, Vol. 67(11), 2018. The preprint version is available here.

[6] Gora Adj, Daniel Cervantes-Vázquez, Jesús-Javier Chi-Domínguez, Alfred Menezes and Francisco Rodríguez-Henríquez, "On the cost of computing isogenies between supersingular elliptic curves". SAC 2018, LCNS 11349, pp. 322-343, 2018. The preprint version is available here.

[7] Samuel Jaques and John M. Schanck, "Quantum cryptanalysis in the RAM model: Claw-finding attacks on SIKE". Advances in Cryptology - CRYPTO 2019, 2019. The preprint version is available here.

[8] Craig Costello, Patrick Longa, Michael Naehrig, Joost Renes and Fernando Virdia, "Improved classical cryptanalysis of the computational supersingular isogeny problem". PKC 2020, LCNS 12111, pp. 505-534, 2020. The preprint version is available here.

[9] Craig Costello, David Jao, Patrick Longa, Michael Naehrig, Joost Renes and David Urbanik, "Efficient compression of SIDH public keys". Advances in Cryptology - EUROCRYPT 2017, LNCS 10210, pp. 679-706, 2017. The preprint version is available here.

[10] Gustavo H.M. Zanon, Marcos A. Simplicio Jr, Geovandro C.C.F. Pereira, Javad Doliskani and Paulo S.L.M. Barreto, "Faster key compression for isogeny-based cryptosystems". IEEE Transactions on Computers, Vol. 68(5), 2019. The preprint version is available here.

[11] Michael Naehrig and Joost Renes, "Dual isogenies and their application to public-key compression for isogeny-based cryptography". Advances in Cryptology - ASIACRYPT 2019, LNCS 11922, pp. 243-272, 2019. The preprint version is available here.

[12] Geovandro C.C.F. Pereira, Javad Doliskani and David Jao, "x-only point addition formula and faster torsion basis generation in compressed SIKE". JCEN, Vol. 11, pp. 57-69, 2021. The preprint version is available here.

[13] Patrick Longa, "Efficient algorithms for large prime characteristic fields and their application to bilinear pairings and supersingular isogeny-based protocols", 2022. The preprint version is available here.

[14] Wouter Castryck and Thomas Decru, "An efficient key recovery attack on SIDH", 2022. The preprint version 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-sidh's Issues

AES-256?

Hello! Wondering if including AES-256 is in the security level roadmap?

Nathan Aw

Binance

Imprecise specification of `get_2_isog` and `get_4_isog`

In src/ec_isogeny.c the specification of get_2_isog states that

void get_2_isog(const point_proj_t P, f2elm_t A, f2elm_t C)
{ // Computes the corresponding 2-isogeny of a projective Montgomery point (X2:Z2) of order 2.
  // Input:  projective point of order two P = (X2:Z2).
  // Output: the 2-isogenous Montgomery curve with projective coefficients A/C.

The specification of the output is not correct. The parameters A and C should be renamed to A24plus and C24 and the output spec should read

  // Output: the 2-isogoneous Montgomery curve with projective coefficients A'/C' where A'+2C' = A24plus and 4C' = C24.

A similar phrasing should be used for the output spec of get_4_isog.
This would align with the specification document available on sike.org.

Non-Interactive Digital Signatures

In some cases it can be really annoying having to use 2 different algorithms for Encryption and Signatures. For example, I have to use GLYPH for signatures (which has 2KB public key sizes, which is okay compared to other PQC algorithms, but can still be inconvenient compared to traditional ECC or even SIDH/SIKE) and SIKE for encryption. Implementing both a good encryption scheme and a signature scheme that can use the same algorithm can be very useful, especially in decentralized systems like Tox and Bitcoin. This whitepaper discusses a possible implementation.

Support for Big Endian Platforms

The conversion between unsigned char* arrays and digit_t* arrays causes this issue. Not sure of a clean way to fix this without changing the function interfaces in several places.

Illegal instruction

PQCrypto-SIDH$ ./sidh751/test_SIDH

TESTING EPHEMERAL ISOGENY-BASED KEY EXCHANGE SYSTEM SIDHp751
--------------------------------------------------------------------------------------------------------

Illegal instruction (core dumped)
/PQCrypto-SIDH$

ASM does not compile on MacOS

MacOS 10.14.1 Mojave, Xcode-10.1. CPU is modern enough (see below).

$ botan cpuid
CPUID flags: sse2 ssse3 sse41 sse42 avx2 avx512f rdtsc bmi1 bmi2 adx aes_ni clmul rdrand rdseed
$ $ make SET=EXTENDED
clang -c -O3      -fwrapv -fomit-frame-pointer -march=native -D _AMD64_ -D __LINUX__ -D _FAST_ -D _MULX_ -D _ADX_  src/P503/P503.c -o objs503/P503.o
clang -c -O3      -fwrapv -fomit-frame-pointer -march=native -D _AMD64_ -D __LINUX__ -D _FAST_ -D _MULX_ -D _ADX_  src/P503/AMD64/fp_x64.c -o objs503/fp_x64.o
clang -c -O3      -fwrapv -fomit-frame-pointer -march=native -D _AMD64_ -D __LINUX__ -D _FAST_ -D _MULX_ -D _ADX_ src/P503/AMD64/fp_x64_asm.S -o objs503/fp_x64_asm.o
src/P503/AMD64/fp_x64_asm.S:86:3: error: invalid operand for instruction
  movq rcx, 0xFFFFFFFFFFFFFFFE
  ^
src/P503/AMD64/fp_x64_asm.S:88:3: error: invalid operand for instruction
  movq rcx, 0xFFFFFFFFFFFFFFFF
  ^
src/P503/AMD64/fp_x64_asm.S:91:3: error: invalid operand for instruction
  movq rcx, 0x57FFFFFFFFFFFFFF
  ^
src/P503/AMD64/fp_x64_asm.S:93:3: error: invalid operand for instruction
  movq rcx, 0x2610B7B44423CF41
  ^
src/P503/AMD64/fp_x64_asm.S:95:3: error: invalid operand for instruction
  movq rcx, 0x3737ED90F6FCFB5E
  ^
src/P503/AMD64/fp_x64_asm.S:97:3: error: invalid operand for instruction
  movq rcx, 0xC08B8D7BB4EF49A0
  ^
src/P503/AMD64/fp_x64_asm.S:99:3: error: invalid operand for instruction
  movq rcx, 0x0080CDEA83023C3C
  ^
src/P503/AMD64/fp_x64_asm.S:107:3: error: invalid operand for instruction
  movq rcx, 0x57FFFFFFFFFFFFFF
  ^
src/P503/AMD64/fp_x64_asm.S:120:3: error: invalid operand for instruction
  movq r8, 0x2610B7B44423CF41
  ^
src/P503/AMD64/fp_x64_asm.S:122:3: error: invalid operand for instruction
  movq r9, 0x3737ED90F6FCFB5E
  ^
src/P503/AMD64/fp_x64_asm.S:124:3: error: invalid operand for instruction
  movq r10, 0xC08B8D7BB4EF49A0
  ^
src/P503/AMD64/fp_x64_asm.S:126:3: error: invalid operand for instruction
  movq r11, 0x0080CDEA83023C3C
  ^
src/P503/AMD64/fp_x64_asm.S:180:3: error: invalid operand for instruction
  movq rcx, 0x57FFFFFFFFFFFFFF
  ^
src/P503/AMD64/fp_x64_asm.S:193:3: error: invalid operand for instruction
  movq r8, 0x2610B7B44423CF41
  ^
src/P503/AMD64/fp_x64_asm.S:195:3: error: invalid operand for instruction
  movq r9, 0x3737ED90F6FCFB5E
  ^
src/P503/AMD64/fp_x64_asm.S:197:3: error: invalid operand for instruction
  movq r10, 0xC08B8D7BB4EF49A0
  ^
src/P503/AMD64/fp_x64_asm.S:199:3: error: invalid operand for instruction
  movq r11, 0x0080CDEA83023C3C
  ^
make: *** [objs503/fp_x64_asm.o] Error 1

Merging #18 improves the situation.

Cry

Demo code in Python?

I have found that NTRUEncrypt has a pure python (no numpy) implementation (https://github.com/logannc/pyNTRUEncrypt), and ECC has it too (https://github.com/johndoe31415/joeecc) but there is none for SIDH, is it possible to write one to make understanding SIDH easier?

Square roots in FP2 I think gives wrong answer in certain special cases.

In sqrt_Fp2, I think there is a subtle error in the implementation of the square root that leads to wrong answers in the specific case where u = a + 0i, and a is not a quadratic residue modulo p.

The issue arises when calculating (a^2 + b^2)^((p+1)/4). When b = 0, this is a^((p+1)/2) = aa^((p-1)/2)) = aL(a), where L(a) is the Legendre symbol modulo p. This is then added to a on the next line. But when a is a quadratic non-residue, this then sets t_0 to zero, and subsequently therefore the whole square root is set to zero.

It might be that this doesn't occur in practice for some reason but if so I can't see why.

I've written up a more full exposition which contains a (very modest) fix:

squareroots1.pdf

I apologise if this actually isn't an issue and I've missed a mitigation for it.

Surgestion: Name change

Please Consider name change to Eliptic Curve Cartography, if the name wasnt allready passed over in favour of SIDH.... 1 biased opinion of course but there is no way one can get "tits or dicks" explaining that they are super into Supersingular Isogeny Diffie-Hellman key exchange/cryptography. i am aware this would effect many pre-existing git/subversoin/mercurial etc but this is the price of having a bad ass name
and will likely be the deciding factor for its eventual adoption.

reserved identifier violation

I would like to point out that identifiers like “__P503_INTERNAL_H__” and “__P751_API_H__” do eventually not fit to the expected naming convention of the C++ language standard.
Would you like to adjust your selection for unique names?

SIKE: question

The specification for SIKE (http://www.sike.org/files/SIDH-spec.pdf) says that values for cSHAKE256 customization bit strings are F=2, G=0 and H=1.

In this implementation, those values (called P,G,H) are encoded on 16 bits, which means that value of let say H customization byte-string will be {0x01, 0x00}.
See here: https://github.com/Microsoft/PQCrypto-SIDH/blob/e5b378378d0f316ed0f602189dfd7f16d3021148/src/sha3/fips202.c#L442

Any idea why it was done that way?

The problem with this is that value of cSHAKE digest depends on length of the byte string, so it maybe would be good to improve spec or change code (and then KATs)

Linking with ARM64 assembly code fails for larger APKs

First of all thanks a lot for this code :-)

I ran several tests with the ARM64 assembly code and the results are impressive on my Android 6P device. However, when I tried to use the assembly code in a larger project the linker complained about several relocation problems:

relocation truncated to fit: R_AARCH64_LD_PREL_LO19 against `.data'

I checked the code and the ARM64 documentation and the culprit are the simple ldr instructions. The offset between the instruction and the data (in the data section) cannot be bigger than 1MB according to the ARM64 doc. For larger programs this will be usually the case. I changed the assembly code and replaced the simple ldr instructions with this sequence:

// ldr x16, p751x2
adrp x16, p751x2
ldr  x16, [x16, #:lo12:p751x2]

After changing and adapting all the simple ldr instructions I ran the tests, everything works and no errors reported.

After adding the code to my larger project the linker was also happy, no complaints. First tests were also OK. I'm not a specialist in ARM assembler coding, thus a better solution may exist.

Attached the complete modified assembler file, compressed in a ZIP.

Werner

fp_arm64_asm.S.zip

Too many global variables, functions etc in SIDH source modules

In my fork of SIDH to add Cmake, C++ wrapper, Android, Java support I build a shared library which includes the SIDH modules. To support Android applications a shared library is a pre-requisite.

When combining all SIDH modules (P434, P503, P610, P751) into one shared library there are a lot of multiple definitions due to global variables and functions. To solve the problems I did some small refactoring of the sources:

• move some functions to a common/common_funcs.c file. The common functions do not
  depend on fields or parameters which are specific to a SIDH type

• define several fields/arrays/functions as static inside their sources files. Due to
  the sources' structure this was possible without affecting functionality. This also reduces
  the number of global definitions which is a 'good thing (tm)' :-) in general.

• add some #defines to map generic names to SIDH type specific names. This follows the
  technique already in use inside the Pnnn.c files. These #defines were put into the
  Pnnn_internal.h files and thus are accessible to the arithmetic tests.

No changes to the actual implementation of the math-functions.

If this is of interest to the SIDH dev team please have a look at the fork mentioned above, branch develop.

Consider integrating https://eprint.iacr.org/2017/1015

A Faster Software Implementation of the Supersingular Isogeny Diffie-Hellman Key Exchange Protocol

Armando Faz-Hernández and Julio López and Eduardo Ochoa-Jiménez and Francisco Rodríguez-Henríquez

Abstract: Since its introduction by Jao and De Feo in 2011, the supersingular isogeny Diffie-Hellman (SIDH) key exchange protocol has positioned itself as a promising candidate for post-quantum cryptography. One salient feature of the SIDH protocol is that it requires exceptionally short key sizes. However, the latency associated to SIDH is higher than the ones reported for other post-quantum cryptosystem proposals. Aiming to accelerate the SIDH runtime performance, we present in this work several algorithmic optimizations targeting both elliptic-curve and field arithmetic operations. We introduce in the context of the SIDH protocol a more efficient approach for calculating the elliptic curve operation P + [k]Q. Our strategy achieves a factor 1.4 speedup compared with the popular variable-three-point ladder algorithm regularly used in the SIDH shared secret phase. Moreover, profiting from pre-computation techniques our algorithm yields a factor 1.7 acceleration for the computation of this operation in the SIDH key generation phase. We also present an optimized evaluation of the point tripling formula, and discuss several algorithmic and implementation techniques that lead to faster field arithmetic computations. A software implementation of the above improvements on an Intel Skylake Core i7-6700 processor gives a factor 1.33 speedup against the state-of-the-art software implementation of the SIDH protocol reported by Costello-Longa-Naehrig in CRYPTO 2016.

(emphasis mine)

Which bits to ignore when the secret agreement is finished

Hello !
Computer science student here, I was fidgeting around with the library, and i saw that on the secret agreement method using p751, there is the following comment : Output: a shared secret SharedSecretB that consists of one element in GF(p751^2) encoded in 188 bytes.

Now, 751 * 2 = 1502, and 188 * 8 = 1504. That would mean that two bits are redundant, right ?

However, when running the following mock program :

#include <stdio.h>
#include "P751_api.h"

#define BTBP "%c%c%c%c%c%c%c%c"
#define BTB(byte)  \
  (byte & 0x80 ? '1' : '0'), \
  (byte & 0x40 ? '1' : '0'), \
  (byte & 0x20 ? '1' : '0'), \
  (byte & 0x10 ? '1' : '0'), \
  (byte & 0x08 ? '1' : '0'), \
  (byte & 0x04 ? '1' : '0'), \
  (byte & 0x02 ? '1' : '0'), \
  (byte & 0x01 ? '1' : '0') 

int main() {

	unsigned char APri[47];
	unsigned char APub[564];
	random_mod_order_A_SIDHp751(APri);
	EphemeralKeyGeneration_A_SIDHp751(APri, APub);
	
	unsigned char BPri[48];
	unsigned char BPub[564];
	random_mod_order_B_SIDHp751(BPri);
	EphemeralKeyGeneration_B_SIDHp751(BPri, BPub);

	unsigned char secretAgreementA[188];
	unsigned char secretAgreementB[188];

	EphemeralSecretAgreement_A_SIDHp751(APri, BPub, secretAgreementA);
	EphemeralSecretAgreement_B_SIDHp751(BPri, APub, secretAgreementB);

	printf(BTBP"\n", BTB(secretAgreementA[0]));
	printf(BTBP"\n", BTB(secretAgreementA[187]));

	return 0;
}

we see no particular pattern in either the first or last byte. My question is, where are the two missing bits ?

Thanks in advance,
MRandl

Porting to javascript version

I slightly changed SIDH.h and makefile to build the web version using emscripten.
My changes here:
https://github.com/procoru/PQCrypto-SIDH/commit/539c0f2d5e14682d3cf1a893e4753423e0ce592a

Demo here: http://sidh.getforge.io/

Makefile doesn't work for multithreaded builds

With the current Makefile, it's not possible to do a multithreaded build. This is the error I get:

patrick@titus:~/Projects/PQCrypto-SIDH$ make -j16
clang -c -O3      -std=gnu11 -march=native -D _AMD64_ -D __NIX__ -D _FAST_ -D _MULX_ -D _ADX_ src/P434/AMD64/fp_x64.c -o objs434/fp_x64.o
clang -c -O3      -std=gnu11 -march=native -D _AMD64_ -D __NIX__ -D _FAST_ -D _MULX_ -D _ADX_ src/P434/AMD64/fp_x64_asm.S -o objs434/fp_x64_asm.o
clang -c -O3      -std=gnu11 -march=native -D _AMD64_ -D __NIX__ -D _FAST_ -D _MULX_ -D _ADX_ src/P434/P434.c -o objs434/P434.o
clang -c -O3      -std=gnu11 -march=native -D _AMD64_ -D __NIX__ -D _FAST_ -D _MULX_ -D _ADX_ src/sha3/fips202.c -o objs/fips202.o
clang -c -O3      -std=gnu11 -march=native -D _AMD64_ -D __NIX__ -D _FAST_ -D _MULX_ -D _ADX_ src/random/random.c -o objs/random.o
clang -c -O3      -std=gnu11 -march=native -D _AMD64_ -D __NIX__ -D _FAST_ -D _MULX_ -D _ADX_ src/P503/AMD64/fp_x64.c -o objs503/fp_x64.o
clang -c -O3      -std=gnu11 -march=native -D _AMD64_ -D __NIX__ -D _FAST_ -D _MULX_ -D _ADX_ src/P503/AMD64/fp_x64_asm.S -o objs503/fp_x64_asm.o
clang -c -O3      -std=gnu11 -march=native -D _AMD64_ -D __NIX__ -D _FAST_ -D _MULX_ -D _ADX_ src/P503/P503.c -o objs503/P503.o
clang -c -O3      -std=gnu11 -march=native -D _AMD64_ -D __NIX__ -D _FAST_ -D _MULX_ -D _ADX_ src/P610/AMD64/fp_x64.c -o objs610/fp_x64.o
clang -c -O3      -std=gnu11 -march=native -D _AMD64_ -D __NIX__ -D _FAST_ -D _MULX_ -D _ADX_ src/P610/AMD64/fp_x64_asm.S -o objs610/fp_x64_asm.o
clang -c -O3      -std=gnu11 -march=native -D _AMD64_ -D __NIX__ -D _FAST_ -D _MULX_ -D _ADX_ src/P610/P610.c -o objs610/P610.o
clang -c -O3      -std=gnu11 -march=native -D _AMD64_ -D __NIX__ -D _FAST_ -D _MULX_ -D _ADX_ src/P751/AMD64/fp_x64.c -o objs751/fp_x64.o
clang -c -O3      -std=gnu11 -march=native -D _AMD64_ -D __NIX__ -D _FAST_ -D _MULX_ -D _ADX_ src/P751/AMD64/fp_x64_asm.S -o objs751/fp_x64_asm.o
clang -c -O3      -std=gnu11 -march=native -D _AMD64_ -D __NIX__ -D _FAST_ -D _MULX_ -D _ADX_ src/P751/P751.c -o objs751/P751.o
clang -c -O3      -std=gnu11 -march=native -D _AMD64_ -D __NIX__ -D _FAST_ -D _MULX_ -D _ADX_ src/P434/P434_compressed.c -o objs434comp/P434_compressed.o
clang -c -O3      -std=gnu11 -march=native -D _AMD64_ -D __NIX__ -D _FAST_ -D _MULX_ -D _ADX_ src/P503/P503_compressed.c -o objs503comp/P503_compressed.o
clang -c -O3      -std=gnu11 -march=native -D _AMD64_ -D __NIX__ -D _FAST_ -D _MULX_ -D _ADX_ src/P610/P610_compressed.c -o objs610comp/P610_compressed.o
clang -c -O3      -std=gnu11 -march=native -D _AMD64_ -D __NIX__ -D _FAST_ -D _MULX_ -D _ADX_ src/P751/P751_compressed.c -o objs751comp/P751_compressed.o
clang -c -O3      -std=gnu11 -march=native -D _AMD64_ -D __NIX__ -D _FAST_ -D _MULX_ -D _ADX_ tests/aes/aes.c -o objs/aes.o
clang -c -O3      -std=gnu11 -march=native -D _AMD64_ -D __NIX__ -D _FAST_ -D _MULX_ -D _ADX_ tests/aes/aes_c.c -o objs/aes_c.o
rm -rf lib503 sike503 sidh503
ar rcs lib503/libsidh_for_testing.a objs503/P503.o objs503/fp_x64.o objs503/fp_x64_asm.o objs/random.o objs/fips202.o objs/aes.o objs/aes_c.o
mkdir lib503 sike503 sidh503
ar rcs lib503/libsidh.a objs503/P503.o objs503/fp_x64.o objs503/fp_x64_asm.o objs/random.o objs/fips202.o
ranlib lib503/libsidh.a
ranlib lib503/libsidh_for_testing.a
rm -rf lib610 sike610 sidh610
ar rcs lib610/libsidh_for_testing.a objs610/P610.o objs610/fp_x64.o objs610/fp_x64_asm.o objs/random.o objs/fips202.o objs/aes.o objs/aes_c.o
mkdir lib610 sike610 sidh610
ar: lib610/libsidh_for_testing.a: No such file or directory
make: *** [Makefile:288: lib610_for_KATs] Error 1
make: *** Waiting for unfinished jobs....
ar rcs lib610/libsidh.a objs610/P610.o objs610/fp_x64.o objs610/fp_x64_asm.o objs/random.o objs/fips202.o
ranlib lib610/libsidh.a

ARM64 code for Apple iOS devices supporting ARM64

The Apple A7 - A10 processors are ARM64 compatible and run iOS. I know that the SIDH code was designed for Linux/Windows, however it should not be a big issue to make it ready for iOS based ARM64 systems ;-) . I did a quick check (no testing yet) about the iOS requirements for ARM64 assembler code and found one issue regarding usage of register x18:
https://developer.apple.com/library/content/documentation/Xcode/Conceptual/iPhoneOSABIReference/Articles/ARM64FunctionCallingConventions.html

Currently the ARM64 assembler code uses x18 which is reserved if the code runs on iOS. Maybe the code can use some other register? Maybe not a high priority issue yet :-) .

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

Different shared secret from encaps/decaps in SIKE-pX-Compressed

The compressed versions of SIKE seem to have a probability of disagreeing on the shared secret. See discussion in open-quantum-safe/liboqs#988 and the linked issue.

@jschanck wrote up the following reproducer in this repo's test harness:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "rng/rng.h"
#include "../src/P434/P434_compressed_api.h"

#define KAT_SUCCESS          0
#define KAT_CRYPTO_FAILURE  -4

int
main()
{
    unsigned char       seed[48] = {0x70, 0x4D, 0x49, 0xD5, 0xFF, 0x14, 0x5E, 0xF5, 0xB7, 0x90, 0x43, 0x93, 0x55, 0x38, 0xBC, 0xAC, 0x03, 0x71, 0x08, 0x17, 0x9E, 0x68, 0xBD, 0xDB, 0x47, 0x60, 0x06, 0x11, 0x9B, 0x7F, 0x3C, 0x68, 0x37, 0x29, 0xEB, 0x33, 0x97, 0x87, 0xBB, 0x93, 0x09, 0xA4, 0x48, 0x5C, 0xA4, 0xBA, 0x25, 0x38};
    unsigned char       ct[CRYPTO_CIPHERTEXTBYTES], ss[CRYPTO_BYTES], ss1[CRYPTO_BYTES];
    unsigned char       pk[CRYPTO_PUBLICKEYBYTES], sk[CRYPTO_SECRETKEYBYTES];
    int                 ret_val;

    randombytes_init(seed, NULL, 256);

    // Generate the public/private keypair
    if ( (ret_val = crypto_kem_keypair_SIKEp434_compressed(pk, sk)) != 0) {
        printf("crypto_kem_keypair returned <%d>\n", ret_val);
        return KAT_CRYPTO_FAILURE;
    }

    if ( (ret_val = crypto_kem_enc_SIKEp434_compressed(ct, ss, pk)) != 0) {
        printf("crypto_kem_enc returned <%d>\n", ret_val);
        return KAT_CRYPTO_FAILURE;
    }

    if ( (ret_val = crypto_kem_dec_SIKEp434_compressed(ss1, ct, sk)) != 0) {
        printf("crypto_kem_dec returned <%d>\n", ret_val);
        return KAT_CRYPTO_FAILURE;
    }

    if ( memcmp(ss, ss1, CRYPTO_BYTES) ) {
        printf("crypto_kem_dec returned bad 'ss' value\n");
        return KAT_CRYPTO_FAILURE;
    }

    return KAT_SUCCESS;
}

Undefined left shift by -1 in ord2w_dloghyb

It is possible for the following line to be executed with ord=1, in which case the left shift is undefined.

PQCrypto-SIDH/src/compression/dlog.c

Line 183 in 0b6f740

if (i_j >= (1 << (ord-2))) {

It would be OK to multiply through by 2 or 4 here, there's no risk of overflow.

Several compiler warnings

SIKE triggers many compiler warnings, especially on the most recent version of GCC. This is prohibitive to compiling with -Wall -Werror as is generally recommended. Some of these warnings suggest possibly invalid behaviour. The below logs are copied from this issue on downstream liboqs but I can reproduce them trivially by calling make on this repo.

The problem appears to lie in -Warray-parameter=2, which is included in -Wall. It appears by adding either to the makefile here.

At level 2 the warning also triggers for redeclarations involving any other inconsistency in array or pointer argument forms denoting array sizes. Pointers and arrays of unspecified bound are considered equivalent and do not
trigger a warning.

  void g (int*);
  void g (int[]);     // no warning
  void g (int[8]);    // warning (inconsistent array bound)

In file included from ../src/kem/sike/external/P503/P503.c:164:
../src/kem/sike/external/P503/../fpx.c:90:35: error: argument 1 of type ‘const digit_t[8]’ {aka ‘const long unsigned int[8]’} with mismatched bound [-Werror=array-parameter=]
   90 | __inline void fpcopy(const felm_t a, felm_t c)
      |                      ~~~~~~~~~~~~~^
In file included from ../src/kem/sike/external/P503/P503.c:10:
../src/kem/sike/external/P503/P503_internal.h:148:38: note: previously declared as ‘const digit_t *’ {aka ‘const long unsigned int *’}
  148 | static void fpcopy503(const digit_t *a, digit_t *c);
      |                       ~~~~~~~~~~~~~~~^

It also fails on -Warray-bounds.

In file included from ../src/kem/sike/external/P751/P751_compressed.c:435:
../src/kem/sike/external/P751/../compression/dlog.c: In function ‘Traverse_w_div_e_torus.constprop’:
../src/kem/sike/external/P751/../compression/dlog.c:166:13: error: array subscript 3 is above array bounds of ‘digit_t[3][2][12]’ {aka ‘long unsigned int[3][2][12]’} [-Werror=array-bounds]
  166 |         d = mod(ord2w_dlog(&H[W_2_1][0], logT, Texp), (1 << W_2_1));
      |             ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
../src/kem/sike/external/P751/../compression/dlog.c:141:13: note: while referencing ‘H’
  141 |     f2elm_t H[W_2_1] = {0}; // Size of H should be max of {W_2_1, W_2 - W_2_1}
      |             ^

And on -Wstringop-overflow. I don't even need to enable extra warnings for this one to show up here.

In function ‘CompleteMPoint’,
    inlined from ‘BuildOrdinary2nBasis_dual’ at ../src/kem/sike/external/P751/../compression/torsion_basis.c:440:5,
    inlined from ‘EphemeralKeyGeneration_B_extended’ at ../src/kem/sike/external/P751/../compression/sidh_compressed.c:630:5:
../src/kem/sike/external/P751/P751_compressed.c:400:21: error: ‘fp2mul751_mont’ accessing 192 bytes in a region of size 96 [-Werror=stringop-overflow=]
  400 | #define fp2mul_mont fp2mul751_mont
../src/kem/sike/external/P751/../ec_isogeny.c:434:9: note: in expansion of macro ‘fp2mul_mont’
  434 |         fp2mul_mont(P->X, P->Z, xz);       // xz = x*z;
      |         ^~~~~~~~~~~
../src/kem/sike/external/P751/../ec_isogeny.c: In function ‘EphemeralKeyGeneration_B_extended’:
../src/kem/sike/external/P751/P751_compressed.c:400:21: note: referencing argument 2 of type ‘const digit_t (*)[12]’ {aka ‘long unsigned int (*)[12]’}
  400 | #define fp2mul_mont fp2mul751_mont
../src/kem/sike/external/P751/../ec_isogeny.c:434:9: note: in expansion of macro ‘fp2mul_mont’
  434 |         fp2mul_mont(P->X, P->Z, xz);       // xz = x*z;
      |         ^~~~~~~~~~~
../src/kem/sike/external/P751/P751_compressed.c:400:21: note: in a call to function ‘fp2mul751_mont’
  400 | #define fp2mul_mont fp2mul751_mont
      |                     ^~~~~~~~~~~~~~
../src/kem/sike/external/P751/../fpx.c:320:13: note: in expansion of macro ‘fp2mul_mont’
  320 | static void fp2mul_mont(const f2elm_t a, const f2elm_t b, f2elm_t c)
      |             ^~~~~~~~~~~

Use Curve255719 for this Encryption

Hello, look like this Encryptions Algorithm use NIST curve. As I known, in 2013, Bernstein was discovered that the NSA had potentially implemented a backdoor into the P-256 curve based Dual_EC_DRBG algorithm. So I think Curve255719 is better to use on SIDH

Cannot compile/assemble some assembly modules as PIC

In my fork of SIDH to add Cmake, C++ wrapper, Android, Java support I build a shared library which includes the SIDH modules. To support Android applications a shared library is a pre-requisite.

When compiling/assemble fp_x64_asm.S clang reports a problem that it cannot generate position independent code (-fpic).

The offending lines in file fp_x64_asm.S look like this

    MUL128x256_SCHOOL [reg_p1], [rip+p434p1+24], r8, r9, r10, r11, r12, r13, rcx     

The culprit here is the reference to p434p1 which is a global variable in the C-sources. The same holds for p503p1, p610p1, and p751p1 variables in their respective assembler files. Tested using clang V9.0.1.

Because I'm not familiar with x86 assembler ;-) I could not fix this and thus reverted to the generic modules to build the shared library. These are definitely slower than the optimized assembler code.

I found some other smaller issues when building the shared library, however these could be easily solved - I show them in another issue.

Thanks for 4th Round Submission

Dear SIDH Team,

I am sure it must have been devastating to find that your work was broken, given the mountain of effort that must have gone into your submission. I am really sorry this happened to you.

The purpose of the issue is to thank you for your 4th round submission and postscript. I for one would not have seen the issue had you not made this submission.

My side research project is to monitor long term risks to crypto systems. Finding obscure maths definitely falls into this category. My hunch is that over time finding and applying obscure maths will be increasingly easy as LLM's and other forms of AI, combined with proof systems such as LEAN evolve. Yours is a good canary for this type of risk.

Again, sorry for the break - thanks for the publication.

Many thanks,
Philip

Tests use GNU C extensions and fail to compile

gcc -O3      -std=c11 -fsanitize=undefined,address -march=native -D _AMD64_ -D __NIX__ -D _FAST_ -D _MULX_ -D _ADX_ -L./lib434 tests/arith_tests-p434.c tests/test_extras.c -lsidh -lm -o arith_tests-p434
tests/test_extras.c: In function ‘cpucycles’:
tests/test_extras.c:37:5: error: ‘asm’ undeclared (first use in this function)
   37 |     asm volatile ("rdtsc\n\t" : "=a" (lo), "=d"(hi));
      |     ^~~
tests/test_extras.c:37:5: note: each undeclared identifier is reported only once for each function it appears in
tests/test_extras.c:37:8: error: expected ‘;’ before ‘volatile’
   37 |     asm volatile ("rdtsc\n\t" : "=a" (lo), "=d"(hi));
      |        ^~~~~~~~~
      |        ;

If you use -std=gnu11, these errors go away.

Bug in p434/fp_x64_asm.S prevents linking on MacOS

Problem:

$ make
ar rcs lib434/libsidh_for_testing.a objs434/P434.o objs434/fp_x64.o objs434/fp_x64_asm.o objs/random.o objs/fips202.o objs/aes.o objs/aes_c.o
ranlib lib434/libsidh_for_testing.a
ar rcs lib434comp/libsidh_for_testing.a objs434comp/P434_compressed.o objs434/fp_x64.o objs434/fp_x64_asm.o objs/random.o objs/fips202.o objs/aes.o objs/aes_c.o
ranlib lib434comp/libsidh_for_testing.a
clang -O3       -std=gnu11 -Wall -march=native -D _AMD64_ -D __NIX__ -D _FAST_ -D _MULX_ -D _ADX_ -Wno-missing-braces -L./lib434 tests/arith_tests-p434.c tests/test_extras.c -lsidh -lm -o arith_tests-p434 
Undefined symbols for architecture x86_64:
  "p434p1", referenced from:
      _fp2mul434_c0_asm in libsidh.a(fp_x64_asm.o)
      _fp2mul434_c1_asm in libsidh.a(fp_x64_asm.o)
     (maybe you meant: _p434p1)
ld: symbol(s) not found for architecture x86_64
clang: error: linker command failed with exit code 1 (use -v to see invocation)
make: *** [Makefile:302: tests_p434] Error 1
$ nm lib434/libsidh.a | grep p434p1
0000000000008800 S _p434p1
                 U _p434p1
                 U p434p1

Solution:

diff --git a/src/P434/AMD64/fp_x64_asm.S b/src/P434/AMD64/fp_x64_asm.S
index 86be311..843b0ba 100644
--- a/src/P434/AMD64/fp_x64_asm.S
+++ b/src/P434/AMD64/fp_x64_asm.S
@@ -376,22 +376,22 @@ fmt(mp_sub434_p2_asm):
     // [Z7, Z0:Z5] <- z = (z0 x p434p1 + z)/2^64
     mov    rdx, \Z6                // rdx <- z0
     //MULADD64x256 [rip+fmt(p434p1)+24], \Z1, \Z2, \Z3, \Z4, \Z5, \T0, \T1 
-    mulx   \Z6, \Z7, [rip+p434p1+24]
+    mulx   \Z6, \Z7, [rip+fmt(p434p1)+24]
     pop    \T0
     adox   \Z1, \Z7
     adox   \Z2, \Z6  
     mov    [rcx+8], \Z0  
-    mulx   \Z6, \Z7, [rip+p434p1+32]
+    mulx   \Z6, \Z7, [rip+fmt(p434p1)+32]
     mov    [rcx+16], \Z1 
     adcx   \Z2, \Z7
     adox   \Z3, \Z6   
     mov    [rcx+24], \Z2  
-    mulx   \Z2, \Z1, [rip+p434p1+40]
+    mulx   \Z2, \Z1, [rip+fmt(p434p1)+40]
     pop    \Z7
     adcx   \Z3, \Z1
     adox   \Z4, \Z2   
     mov    [rcx+32], \Z3   
-    mulx   \Z2, \Z1, [rip+p434p1+48] 
+    mulx   \Z2, \Z1, [rip+fmt(p434p1)+48] 
     pop    \Z6        
     adcx   \Z4, \Z1
     adox   \Z5, \Z2

Unused pre-loop init

Looks like line 662 from ec_isogeny.c isn't used; it is re-initialized on line 671 and therefore should be removed.

This was noted by the scan-build tool on the OQS project; see PR 1211.

when is scheme not secure

Given this cryptic note at the top of the repo

SECURITY NOTE: the scheme is NOT secure when using static keys.

Could you elaborate on what "static" means? Are static keys ever the default?

Wrong delay loop

Such delay loops:

PQCrypto-SIDH/src/random/random.c

Lines 22 to 25 in 873f8d1

	static __inline void delay(unsigned int count)
	{
	while (count--) {}
	}

may not work, because compiler can remove this. Example:
https://godbolt.org/z/9bd6xd

Use getrandom() in Linux instead of /dev/urandom

Using getrandom() instead of opening /dev/urandom is the preferred way to get random bytes in modern Linux systems.

Something like the following could be used in src/random/random.c:

/********************************************************************************************
* Hardware-based random number generation function
*
* It uses /dev/urandom in Linux and CNG's BCryptGenRandom function in Windows
*********************************************************************************************/ 

#include "random.h"
#include <stdlib.h>
#if defined(__WINDOWS__)
    #include <windows.h>
    #include <bcrypt.h>
#elif defined(__LINUX__)
    #include <unistd.h>
    #include <fcntl.h>
    #include <sys/random.h>
    #include <errno.h>
    static int lock = -1;
    static int getrandom_works = 1;
#endif

#define passed 0 
#define failed 1


static __inline void delay(unsigned int count)
{
    while (count--) {}
}


int randombytes(unsigned char* random_array, unsigned long long nbytes)
{ // Generation of "nbytes" of random values
    
#if defined(__WINDOWS__)   
    if (!BCRYPT_SUCCESS(BCryptGenRandom(NULL, random_array, (unsigned long)nbytes, BCRYPT_USE_SYSTEM_PREFERRED_RNG))) {
        return failed;
    }

#elif defined(__LINUX__)
    int r, n = (int)nbytes, count = 0;
    
    if (getrandom_works == 1) {
        errno = 0;
        while (n > 0) {
            r = getrandom(random_array+count, n, 0);
            if (r < 0) {
                if (errno == EINTR) {
                    /* retry getrandom() if it was interrupted by a signal */
                    continue;
                }
                getrandom_works = 0;
                break;
            }
            count += r;
            n -= r;
        }
        if (n == 0) {
            return passed;
        }
    }

    if (lock == -1) {
        do {
            lock = open("/dev/urandom", O_RDONLY);
            if (lock == -1) {
                delay(0xFFFFF);
            }
        } while (lock == -1);
    }

    while (n > 0) {
        do {
            r = read(lock, random_array+count, n);
            if (r == -1) {
                delay(0xFFFF);
            }
        } while (r == -1);
        count += r;
        n -= r;
    }
#endif

    return passed;
}

Library symbols can't be found

After attempting to link the 434 and 751 libraries/add API includes to a project, the linker complains that symbols can't be found.

I can see the symbol by running strings on the library, still investigating deeper.

target_include_directories(client
    PUBLIC
    ../deps/PQCrypto-SIDH/src
    ${CMAKE_BINARY_DIR}/proto)
    
target_link_libraries(client
    PUBLIC
    ${PROTOBUF_LIBRARIES}
    ${CMAKE_BINARY_DIR}/proto/libsockproto.a
    ${CMAKE_BINARY_DIR}/../deps/PQCrypto-SIDH/lib434/libsidh.a)

[ 52%] Linking CXX executable client
/usr/bin/ld: CMakeFiles/client.dir/client.cc.o: in function `sockpuppet::client::exchange_keys()':
/home/jonesy/git/sockpuppet/include/sockpuppet/client.h:150: undefined reference to `random_mod_order_A_SIDHp434(unsigned char*)'
/usr/bin/ld: /home/jonesy/git/sockpuppet/include/sockpuppet/client.h:152: undefined reference to `EphemeralKeyGeneration_A_SIDHp434(unsigned char const*, unsigned char*)'
/usr/bin/ld: /home/jonesy/git/sockpuppet/include/sockpuppet/client.h:159: undefined reference to `EphemeralSecretAgreement_A_SIDHp434(unsigned char const*, unsigned char const*, unsigned char*)'
collect2: error: ld returned 1 exit status
make[2]: *** [example/CMakeFiles/client.dir/build.make:106: example/client] Error 1
make[1]: *** [CMakeFiles/Makefile2:261: example/CMakeFiles/client.dir/all] Error 2

SIKE: Choice of Alice/Bob sequence

Hi! I've been reviewing and testing this Library and Test code for a project. It's been working quite well, Kudos to the writers.

I do have one question on the sequence of operations implemented in the sike.c file. In many papers on SIKE (including Fig2 of "A Note on Post-Quantum Authenticated Key Exchange from Supersingular Isogenies"), Alice does the KeyGen, Bob does the Encode, then Alice completes with Decode.

Yet in sike.c the crypto_kem_keypair() function does a Bob KeyGen, crypto_kem_enc() does Alice Encode, and crypto_kem_dec() Bob Decode. Was this done on purpose? Can they be reversed without consequence?

I know this might seem a nit, but there appears to be differences in the _A and _B versions of the underlying SIDH functions, and I wanted to get this clarfied.

Question about SECRETKEY_B_BYTES

These macros are defined in P610_internal.h

#define SECRETKEY_A_BYTES       ((OALICE_BITS + 7) / 8)
#define SECRETKEY_B_BYTES       ((OBOB_BITS - 1 + 7) / 8)
#define FP2_ENCODED_BYTES       2*((NBITS_FIELD + 7) / 8)

#ifdef COMPRESS
    #define MASK2_BOB               0x07
    #define MASK3_BOB               0xFF
    #define ORDER_A_ENCODED_BYTES   SECRETKEY_A_BYTES
    #define ORDER_B_ENCODED_BYTES   (SECRETKEY_B_BYTES + 1)

I wonder why SECRETKEY_A_BYTES = (OALICE_BITS + 7) / 8 but SECRETKEY_B_BYTES = (OBOB_BITS + 6) / 8. What's more, ORDER_B_ENCODED_BYTES is defined as SECRETKEY_B_BYTES + 1 in P610_internal.h but in other Pxxx_internal.h ORDER_B_ENCODED_BYTES is just SECRETKEY_B_BYTES. According to my understanding, SECRETKEY_B_BYTES should be defined as (OBOB_BITS + 7) / 8 so that the ORDER_B_ENCODED_BYTES in P610_internal.h does not need to be especially defined.

6vju