armfazh / rfc7748_precomputed

Updated! (Dec2-2019) This is a C-language software library that provides optimized implementations of the Diffie-Hellman functions known as X25519 and X448 (RFC-7748) for 64-bit architectures.

How to (pre-)compute a ladder

This is a C-language software library that provides optimized implementations of the Diffie-Hellman functions known as X25519 and X448 (RFC-7748) for 64-bit architectures.

This source code is part of the research work titled: "How to (pre-)compute a ladder" by the authors:

• Thomaz Oliveira, Computer Science Department, Cinvestav-IPN, Mexico.
• Julio López, University of Campinas, Brazil.
• Hüseyin Hisil, Yasar University, Turkey.
• Armando Faz-Hernández, University of Campinas, Brazil.
• Francisco Rodríguez-Henríquez, Computer Science Department, Cinvestav-IPN, Mexico.

---

Research Resources

A peer-reviewed paper was presented in the 24th Annual Conference on Selected Areas in Cryptography (SAC2017).

• Paper [DOI]
• Slides [PDF].
• Pre-print (IACR ePrint Archive) http://iacr.eprint.org/2017/264 [PDF]

To cite this work use:

@inproceedings{oliveira_sac2017,
    author    = {Thomaz Oliveira and Julio L\'opez and
                 H\"useyin H{\i}\c{s}{\i}l and Armando Faz-Hern\'andez and
                 Francisco Rodr\'iguez-Henr\'iquez},
    editor    = {Adams, Carlisle and Camenisch, Jan},
    title     = {How to (pre-)compute a ladder},
    booktitle = {Selected Areas in Cryptography – SAC 2017:
                 24th International Conference, Ottawa, Ontario,
                 Canada, August 16 - 18, 2017, Revised Selected Papers},
    year      = {2018},
    publisher = {Springer International Publishing},
    pages     = {172-191},
    doi       = {10.1007/978-3-319-72565-9_9},
}

---

Implementation Details

• Prime field arithmetic is optimized for the 4th and 6th generation of Intel Core processors (Haswell and Skylake micro-architectures).
• Efficient integer multiplication using MULX instruction.
• Integer additions accelerated with ADCX/ADOX instructions.
• Key generation uses a read-only table of 8 KB (25 KB) for X25519 (X448).
• It follows secure coding countermeasures.

---

Pre-requirements

This library is a standalone C-language code. However, for tests we use C++ code.

• C and C++ compilers.
• git
• cmake

Compilation

First, clone the repository and configure project using the CMake tool:

 $ git clone https://github.com/armfazh/rfc7748_precomputed
 $ cd rfc7748_precomputed
 $ mkdir build
 $ cd build

To specify an alternative C/C++ compiler set the following variables:

 $ CC=gcc CXX=g++ cmake ..

Also, to specify a custom install directory (install_dir) use:

 $ cmake -DCMAKE_INSTALL_PREFIX=install_dir ..

Finally, compile and install:

 $ make
 $ make install (optional)

---

Running Companion Programs

Once compilation was done, you can run some companion programs.

For running a sample program use:

 $ bin/sample_x25519
 $ bin/sample_x448

For running a performance benchmark (in clock cycles) use:

 $ make bench
 $ bin/bench

For running the Google benchmark tool use:

 $ make gbench
 $ bin/gbench --benchmark_repetitions=10 --benchmark_display_aggregates_only=true

For running the Google Test tool use:

 $ make tests
 $ bin/tests

Fuzzing Test

In the fuzz folder, there are several tests against gmp library and the HACL project. Read the compilation instructions at fuzz/README.md for more information.

---

Timings

Benchmark performance on 64-bit Intel architectures (table entries are clock cycles).

X25519	Haswell	Skylake
Key Generation	92,400	69,500
Shared Secret	145,800	108,700

X448	Haswell	Skylake
Key Generation	401,902	322,040
Shared Secret	670,747	528,470

Haswell is a Core i7-4770 processor.

Skylake is a Core i7-6700K processor.

---

License

BSD-3 Clause License (LICENSE)

---

Contact

To report some issues or comments of this project, please use the issues webpage [here].

---

rfc7748_precomputed's Issues

Problems with field arithmetic

I reviewed the field implementation in fp25519_x64 and either I'm missing something or both the add_EltFp25519_1w_x64 and sub_EltFp25519_1w_x64 have incomplete carry handling.

e.g. I can't see why this line would never carry, since RAX could hold any value, and this line is (possibly) adding 38 to it:

rfc7748_precomputed/src/fp25519_x64.c

Line 676 in cde6f49

"addq %%rcx, %%rax \n\t"

I think a similar logic also applies for:

rfc7748_precomputed/src/fp25519_x64.c

Line 725 in cde6f49

"subq %%rcx, %%rax \n\t"

I don't see any tests specifically for add_/sub_. They are covered e.g. by the "mul/sqr" test, but random inputs with 64-bit limbs are very unlikely to catch carry handling errors, especially since random_EltFp25519_1w_x64 is only generating 255-bit values, while add_/sub_ apparently support 256-bit values (?).

I only briefly checked fp448_x64 for comparison, but I believe add_EltFp448_1w_x64 and sub_EltFp448_1w_x64 also have similar errors, probably even less likely to be detected by random inputs.

Possible errors in arithmetic operations in GF(2^448 -2^224 -1).

Brief: It is possible that carry propagation is not performed properly in addition/suibtraction/reduction.
This issue was previously observed in #5 for GF(2^255 -19).

Help wanted:

• Include more tests for arithmetic operations.
• Proper carry handling for the worst case, i.e. numbers of 2^448 bits.

Change license to GPLv2+ or something more permissive

I'd like to use this in WireGuard, and by extension, in the Linux kernel. I've already imported it and gotten it ready for the kernel's environment, as well as reducing input points mod 2^255-19 and accounting for the various different CPU flags at runtime. However, right now it lives in this unhappy branch, which I can't yet merge to master, because this project appears to be LGPLv3+, whereas the kernel requires GPLv2.

Would you consider re-licensing this project to something compatible with GPLv2? This would include things like:

• GPLv2 itself.
• GPLv2+
• LGPLv2+
• GPLv2 and GPLv3
• LGPLv2 and LGPLv3
• BSD
• MIT
• Public domain
• Many other good candidates

Doing so will get this code some real world usage and deployment.