Library for elliptic curves cryptography
Copyright (C) 2017
This software is licensed under a dual BSD and GPL v2 license. See LICENSE file at the root folder of the project.
This software implements a library for elliptic curves based cryptography (ECC). The API supports signature algorithms specified in the ISO 14888-3:2018 standard, with the following specific curves and hash functions:
ECDSA comes in two variants: the classical non-deterministic one, and the deterministic ECDSA as described in RFC 6979. The deterministic version generates nonces using a HMAC-DRBG process, and is suitable for situations where there is no RNG or where entropy sources are considered weak (please note that any leak on these nonces bits can lead to devastating attacks exploiting the Hidden Number Problem). On the downside, the deterministic version of ECDSA is susceptible to fault attacks. Hence, one will have to carefully select the suitable version to use depending on the usage and attack context (i.e. which of side-channel attacks or fault attacks are easier to perform).
The library also supports EdDSA (Ed25519 and Ed448) as defined in RFC 8032 with all their variants (with context, pre-hashed). Since the core of the library supports short Weierstrass curves, and as EdDSA uses instead Twisted Edwards curves with dedicated formulas, we use isogenies as described in the lwig-curve-representations draft. Isogenies are transformations (homomorphisms that are almost isomorphisms) between curves models, allowing to implement operations on one model by operating with formulas on another model. Concretely, in our case we perform computations on the Weierstrass WEI25519 that is isogenic to Ed25519 (Twisted Edwards) and Curve25519 (Montgomery) curves. This, of course, induces overheads in computations while having the great benefit of keeping the library core mathematical foundations simple and keep the defense-in-depth (regarding software security and side-channels) focused on a rather limited part: see the discussions below on libecc efforts with regards to security.
Please note that as for deterministic ECDSA, EdDSA signatures are trivially susceptible to fault attacks without having a non-deterministic variant. Hence, when using EdDSA one will have to either ensure that the usage context naturally prevents such attacks, that the platform implements countermeasures (e.g. using secure MCUs, etc.) or that other means allow to detect/mitigate such attacks (e.g. on the compilation toolchain side).
Regarding the specific case of ECRDSA (the Russian standard), libecc implements by default the RFC 7091 and draft-deremin-rfc4491-bis versions to comply with the standard test vectors (provided in the form of X.509 certificates). This version of the algorithm differs from the ISO/IEC 14888-3 description and test vectors, the main difference coming from the way the hash of the message to be signed/verified is processed: in the RFCs, the little endian representation of the hash is taken as big number while in ISO/IEC the big endian representation is used. This seems (to be confirmed) to be a discrepancy of ISO/IEC 14888-3 algorithm description that must be fixed there. In order to allow users to still be able to reproduce the ISO/IEC behavior, we provide a compilation toggle that will force this mode
$ USE_ISO14888_3_ECRDSA=1 make
Advanced usages of this library also include the possible implementation of elliptic curve based Diffie--Hellman protocols as well as any algorithm on top of prime fields based elliptic curves (or prime fields, or rings of integers). Compared to other cryptographic libraries providing such features, the differentiating points are:
The main Makefile is in the root directory, and compiling is as simple as executing:
This will compile different elements in the build directory:
For known test vectors:
$ ./build/ecselftests vectors ======= Known test vectors test =================== [+] ECDSA-SHA224/secp224r1 selftests: known test vectors sig/verif ok [+] ECDSA-SHA256/secp256r1 selftests: known test vectors sig/verif ok [+] ECDSA-SHA512/secp256r1 selftests: known test vectors sig/verif ok ...
For sign/verify checks (with random key pairs and random data):
$ ./build/ec_self_tests rand ======= Random sig/verif test =================== [+] ECDSA-SHA224/FRP256V1 randtests: random import/export with sig(0)/verif(0) ok [+] ECDSA-SHA224/SECP224R1 randtests: random import/export with sig(0)/verif(0) ok ...
For performance measurements:
$ ./build/ec_self_tests perf ======= Performance test ===================== [+] ECDSA-SHA224/FRP256V1 perf: 462 sign/s and 243 verif/s [+] ECDSA-SHA224/SECP224R1 perf: 533 sign/s and 276 verif/s ...
Generate keys for ECKCDSA over the BRAINPOOLP512R1 curve, with the 'mykeypair' prefix:
$ ./build/ecutils genkeys BRAINPOOLP512R1 ECKCDSA mykeypair
This will create four files. Two binary '.bin' files corresponding to the private key (mykeypair_private_key.bin) and the public key (mykeypair_public_key.bin). Two header '.h' files are also created, corresponding to a C style header version of the keys so that these can be included and used in a C program using libecc. Note that both kind of keys (public and private) include leading metadata (type, algorithm, curve, etc) for possible sanity checks when they are used (e.g. to detect passing of an ECDSA private key to an ECKCDSA signature call, etc).
Once the key pair has been created, one can sign a raw binary file named 'myfile' and store the signature in 'sig.bin'. In the example below, we use SHA3_512 as the hash function for the signature. BRAINPOOLP512R1 and ECKCDSA are explicitly given (matching the type of key we generated during previous step). Note that the call would yield an error if invalid parameters were given (thanks to the metadata elements described above).
$ ./build/ecutils sign BRAINPOOLP512R1 ECKCDSA SHA3512 myfile mykeypairprivatekey.bin sig.binAfter this, a raw signature is created, mainly consisting of the ECKCDSA (r, s) big numbers concatenated (the length of this file should be 1024 bits = 2 x 512 bits). The signature can now be verified with the 'verify' command and the public key, the result being either OK or failed:
$ ./build/ecutils verify BRAINPOOLP512R1 ECKCDSA SHA3512 myfile mykeypairpublickey.bin sig.bin Signature check of myfile OK
The ec_utils tool can also be used to produce/verify structured binaries containing a header, raw binary and their signature (see the 'struct_sign' and 'struct_verify' commands for a help on this mode). The rationale behind these commands is to ease the production/verification of self-contained signed images (which can be useful when dealing with embedded firmware updates for instance).
Since it is possible to use libecc as a NN (positive Natural Numbers), Fp (Finite field over primes) or EC curve layer library, we provide some examples in the src/examples folder. Compiling these examples is as simple as:
$ cd src/examples $ make
NN layer examples:
Fp layer examples:
Curves layer examples:
WARNING: these examples are toy implementations not to be used in a production environment (for instance, the code has neither been designed to be efficient nor robust against side channel attacks). Their purpose is only to show basic usage of the libarith and libec libraries.
The public headers containing the functions to be used by higher level code are src/libarith.h, src/libec.h and src/libsig.h: they are respectively used for the NN and Fp arithmetic layers, the Elliptic Curves layer, and the signature layer.
libecc is provided with arithmetic random tests for the low level NN and Fp routines (addition, subtraction, logical operations, multiplication and Montgomery multiplication, ...).
These tests are located inside the src/arithmetic_tests/ folder. More specifically, the tests are split in two files:
libecc can be statically configured at compilation time: the user can tune what curves, hash functions and signature algorithms are embedded in 'libsign.a' and all the binaries using it.
The main entry point to configure/tune the library is src/lib_ecc_config.h. By default libecc embeds everything. In order to remove something, one has to comment the element to remove (i.e. comment the
WITH_XXXmacro). For instance, removing FRP256V1 is simply done by commenting the line:
/* Supported curves / / #define WITHCURVEFRP256V1 / / REMOVING FRP256V1 */ #define WITHCURVESECP192R1 #define WITHCURVESECP224R1 #define WITHCURVESECP256R1 #define WITHCURVESECP384R1 #define WITHCURVESECP521R1 #define WITHCURVEBRAINPOOLP224R1 #define WITHCURVEBRAINPOOLP256R1 #define WITHCURVEBRAINPOOLP384R1 #define WITHCURVEBRAINPOOLP512R1 #define WITHCURVEGOST256 #define WITHCURVEGOST512 ...
As another example, if one wants to build a custom project supporting only ECFSDA using SHA3-256 on BrainpoolP256R1, this can be done by keeping only the following elements in src/lib_ecc_config.h:
#define WITH_SIG_ECFSDSA #define WITH_HASH_SHA3_256 #define WITH_CURVE_BRAINPOOLP256R1
libecc supports 16, 32 and 64 bits word sizes. Though this word size is usually inferred during compilation and adapted depending on the detected platform (to fit the best performance), the user can force it in three ways:
WORDSIZEmacro in src/words/words.h.
WORDSIZEmacro in the Makefile
Please refer to the portability guide for details on this.
libecc infers the Natural Numbers maximum length from the curves parameters that have been statically defined in src/lib_ecc_config.h. Though this behaviour is perfectly fine and transparent for the user when dealing with the elliptic curves and signature layers, this can become a limitation when building code around the NN and Fp arithmetic layers. The user will be stuck with a hard coded maximum size of numbers depending on the curve that is used by libecc, which can be a nonsense if he is only interested in the big number basic algorithmic side (when the default curves are used, this maximum size is 521 bits, corresponding to SECP521 parameters).
libecc provides a way to overload the NN maximum size, with a strong limit depending on the word size (around 5300 bits for 64-bit words, around 2650 bits for 32-bit words, and around 1300 bits for 16-bit words). See the comments in src/nn/nn_config.h for more details about this. In order to manually increase the NN size, the user will have to define the macro
USER_NN_BIT_LEN, either directly in src/nn/nn_config.h, or more appropriately through overloading the Makefile
-DUSER_NN_BIT_LEN=(see the dedicated section for more on how to do this).
NOTE: objects and binaries compiled with different word sizes and/or user defined NN maximum bit lengths are not compatible, and could produce executables with dangerous runtime behaviour. In order to prevent possible honest mistakes, there is a safety net function catching such situations at compilation time in src/nn/nn_config.h: the
nn_check_libconsistencyroutine will throw an error. For instance, if 'libarith.a' has been compiled with
WORDSIZE=64, and one tries to compile the arithmetic tests with
WORDSIZE=32, here is the error the compiler should produce:
... arithmetic_tests.c:(.text+0x3af21) : undefined reference to « nn_consistency_check_maxbitlen521wordsize32 » ...
Though libecc has been designed to be compiled with a static embedding of all its features (i.e. no dynamic modules loading), its static code extensibility has been a matter of attention. The library can be: * Easily expanded by adding new curves, with zero coding effort. Note that only curves over prime fields are supported. * Expanded with new hash functions and new signature algorithms with some coding effort, but clean and well defined APIs should ease this task.
A companion python script scripts/expand_libecc.py will transparently add (and remove) new user defined curves in the source tree of the project. The '.h' headers defining the new curves will be created in a dedicated folder: src/curves/user_defined/.
The python script should have a self explanatory and complete help:
$ python scripts/expand_libecc.py -h This script is intented to statically expand the ECC library with user defined curves. ...
In order to add a curve, one can give explicit parameters (prime, order, ...) on the command line or provide a RFC3279 formatted ASN.1 file (DER or PEM) with the parameters. Sanity checks are performed by the script. The script is also able to generate test vectors for the new curve with the
Let's show how we can add the BRAINPOOLP320R1 supported by OpenSSL. We use the
ecparamoption of the
$ openssl ecparam -param_enc explicit -outform DER -name brainpoolP320r1 -out brainpoolP320r1.der
This creates a DER file 'brainpoolP320r1.der' embedding the parameters (beware of the
-param_enc explicitoption that is important here). Now, in order to add this new curve to libecc, we will execute:
$ python scripts/expand_libecc.py --name="mynewcurve" --ECfile=brainpoolP320r1.der --add-test-vectors=1 Test vectors generation asked: this can take some time! Please wait ... 1/56
This will create a new header file 'ec_params_user_defined_mynewcurve.h' in the src/curves/user_defined/ folder, and it will modify some libecc core files to transparently add this curve for the next compilation (modified files are src/curves/curves_list.h, src/tests/ec_self_tests_core.h, src/lib_ecc_config.h and src/lib_ecc_types.h).
The test vectors generation can take some time since all the possible triplets (curve, hash function, signature algorithm) are processed with the new curve.
After compiling the library, the new curve should show up in the self tests:
$ ./build/ecselftests ======= Known test vectors test ================= ... [+] ECDSASHA224USERDEFINEDMYNEWCURVE0 selftests: known test vectors sig/verif ok ... ======= Random sig/verif test =================== ... [+] ECDSA-SHA224/USERDEFINEDMYNEWCURVE randtests: random import/export with sig/verif ok ... ======= Performance test ======================== ... [+] ECDSA-SHA224/USERDEFINED_MYNEWCURVE perf: 269 sign/s and 141 verif/s ...
It should also appear in the
$ ./build/ecutils sign Bad args number for ./build/ecutils sign: arg1 = curve name: FRP256V1 USERDEFINEDMYNEWCURVE ... arg2 = signature algorithm type: ECDSA ... arg3 = hash algorithm type: SHA224 ... arg4 = input file to sign arg5 = input file containing the private key (in raw binary format) arg6 = output file containing the signature
It is possible to remove a user defined curve by using the python script and its name:
$ python scripts/expand_libecc.py --remove --name mynewcurve You asked to remove everything related to user defined mynewcurve curve. Enter y to confirm, n to cancel [y/n]. y Removing user defined curve mynewcurve ...
It is also possible to remove all the user defined curves at once:
$ python scripts/expand_libecc.py --remove-all
Finally, two companion shell scripts are provided along with the expanding python script in order to show its basic usage:
Obviously, adding new algorithms (hash or signature) will require adding new code.
We detail hereafter the necessary steps to add a new hash function. The main file listing all the hash functions is src/hash/hash_algs.h. The new hash algorithm should be added here in compliance with the API described in the
hash_mapping struct. This API includes:
hfunc_init: the hash function initialization routine.
hfunc_update: the hash function update routine.
hfunc_finalize: the hash function finalization routine.
hfunc_scattered: this function applies the hash function (i.e. compute the digest) on multiple messages (it takes as input an array of pointers to message chunks, and an array of sizes).
These libecc API functions are in fact redirections to the core routines of the hash algorithm, and the user is expected to add the specific implementation in '.c' and '.h' files inside the src/hash/ folder. See src/hash/sha224.c and src/hash/sha224.h for a practical example of how to do this with SHA-224.
Finally, the user is expected to update the libecc main configuration file src/lib_ecc_config.h with the
WITH_MY_NEW_HASHtoggle ('my_new_hash' being the new hash function).
In order to add a new elliptic curve based signature algorithm, here is the needed work: * The main file listing all the signature algorithms is src/sig/sig_algs_internal.h. The signature algorithm should be added in compliance with the API described in the
ec_sig_mapping struct. This API includes: * The signature type and a pretty print name. *
siglen: a function giving the length of the produced signature. *
init_pub_key: a routine producing a public key when given a corresponding private key. *
sign_finalize: the usual functions initializing a signature, updating it with input buffers, and finalizing it to produce an output signature. *
verify_finalize: the usual functions initializing a signature verification, updating it with input buffers, and finalizing it to produce a check status (i.e. signature OK or not OK).
These libecc APIs have to be plugged to the core signature functions, and the user is expected to handle this implementation with adding the specific '.c' and '.h' files inside the src/sig folder. See src/sig/ecdsa.c and src/sig/ecdsa.h for a practical example of how to do this with ECDSA.
Finally, the user is expected to update the libecc main configuration file src/lib_ecc_config.h with the
WITH_MY_NEW_SIGN_ALGtoggle ('my_new_sign_alg' being the new signature algorithm).
As already stated, libecc has not been designed with performance in mind, but with simplicity and portability as guiding principles; this implies several things when it comes to performance:
Nonetheless and despite all these elements, libecc is on par with some other general purpose and portable cryptographic libraries such as mbedTLS (see the performance figures given below).
We present hereafter the ECDSA performance comparison of libecc with mbedTLS and OpenSSL on various platforms representing different CPU flavours. Here are some information about the tested version when not stated otherwise:
For all the platforms in this subsection, the CPUs have been tested in 64-bit mode.
| libecc | Core i7-5500U @ 2.40GHz | Xeon E3-1535M v5 @ 2.90GHz | Power-7 | |-----------------|:----------------------------|:------------------------------|:--------------------------| | BP256R1 | 583 sign/s - 300 verif/s | 700 sign/s - 355 verif/s | 213 sign/s - 110 verif/s | | BP384R1 | 231 sign/s - 118 verif/s | 283 sign/s - 150 verif/s | 98 sign/s - 50 verif/s | | BP512R1 | 111 sign/s - 56 verif/s | 133 sign/s - 68 verif/s | 51 sign/s - 26 verif/s |
| mbedTLS | Core i7-5500U @ 2.40GHz | Xeon E3-1535M v5 @ 2.90GHz | Power-7 | |-----------------|:----------------------------|:------------------------------|:--------------------------| | BP256R1 | 426 sign/s - 106 verif/s | 552 sign/s - 141 verif/s | 178 sign/s - 45 verif/s | | BP384R1 | 239 sign/s - 56 verif/s | 322 sign/s - 77 verif/s | 44 sign/s - 23 verif/s | | BP512R1 | 101 sign/s - 26 verif/s | 155 sign/s - 34 verif/s | 38 sign/s - 12 verif/s |
| OpenSSL | Core i7-5500U @ 2.40GHz | Xeon E3-1535M v5 @ 2.90GHz | Power-7 | |-----------------|:----------------------------|:------------------------------|:--------------------------| | BP256R1 | 2463 sign/s - 1757 verif/s | 2873 sign/s - 2551 verif/s | 1879 sign/s - 1655 verif/s| | BP384R1 | 1091 sign/s - 966 verif/s | 1481 sign/s - 1265 verif/s | 792 sign/s - 704 verif/s| | BP512R1 | 727 sign/s - 643 verif/s | 1029 sign/s - 892 verif/s | 574 sign/s - 520 verif/s|
| libecc | Marvell A388 @ 1.6GHz | BCM2837 (aarch64) @ 1.2GHz | Atom D2700 @ 2.13GHz | |-----------------|:----------------------|----------------------------|:-----------------------| | BP256R1 | 64 sign/s - 33 verif/s| 43 sign/s - 22 verif/s | 68 sign/s - 35 verif/s | | BP384R1 | 24 sign/s - 12 verif/s| 17 sign/s - 9 verif/s | 25 sign/s - 13 verif/s | | BP512R1 | 11 sign/s - 5 verif/s | 8 sign/s - 4 verif/s | 12 sign/s - 6 verif/s |
| mbedTLS | Marvell A388 @ 1.6GHz | BCM2837 (aarch64) @ 1.2GHz | Atom D2700 @ 2.13GHz -| |-----------------|:----------------------|----------------------------|:------------------------| | BP256R1 | 33 sign/s - 8 verif/s | 14 sign/s - 4 verif/s | 87 sign/s - 22 verif/s| | BP384R1 | 20 sign/s - 4 verif/s | 8 sign/s - 2 verif/s | 50 sign/s - 11 verif/s| | BP512R1 | 10 sign/s - 2 verif/s | 4 sign/s - 1 verif/s | 23 sign/s - 5 verif/s |
| OpenSSL | Marvell A388 @ 1.6GHz | BCM2837 (aarch64) @ 1.2GHz | Atom D2700 @ 2.13GHz | |-----------------|:------------------------|----------------------------|:------------------------| | BP256R1 | 369 sign/s - 332 verif/s| 124 sign/s - 112 verif/s | 372 sign/s - 334 verif/s| | BP384R1 | 102 sign/s - 94 verif/s | 54 sign/s - 49 verif/s | 163 sign/s - 149 verif/s| | BP512R1 | 87 sign/s - 81 verif/s | 31 sign/s - 29 verif/s | 92 sign/s - 83 verif/s |
The library, when configured for a 256-bit curve (SECP256R1, FRP256), SHA-256 and ECDSA signature fits in around 30 Kilo Bytes of flash/EEPROM, and uses around 8 Kilo Bytes of RAM (stack) with variations depending on the chosen WORDSIZE (16, 32, 64), the compilation options (optimization for space
-O3) and the target (depending on the instructions encoding, produced binary code can be more or less compact). A 521-bit curve with SHA-256 hash function and ECDSA signature should fit in 38 Kilo Bytes of flash and around 16 Kilo Bytes of RAM (stack), with the same variations depending on the WORDSIZE and the compilation options.
Note: libecc does not use any heap allocation, and the only global variables used are the constant ones. The constant data should end up in the flash/EEPROM section with a read only access to them: no RAM memory should be consumed by these. The libecc read/write data are only made of local variables on the stack. Hence, RAM consumption (essentially made of arrays representing internal objects such as numbers, point on curves ...) should be reasonably constant across platforms. However, some platforms using the Harvard architecture (as opposed to Von Neumann's one) can have big limitations when accessing so called "program memory" as data. The 8-bit Atmel AVR MCU is such an example. Compilers and toolchains for such architectures usually copy read only data in RAM at run time, and/or provide non-standard ways to access read only data in flash/EEPROM program memory (through specific macros, pragmas, functions). The first case means that the RAM consumption will increase for libecc compared to the stack only usage (because of the runtime copy). The second case means that libecc code will have to be adapted to the platform if the user want to keep RAM usage at its lowest. In any case, tracking where
constqualified data reside will be important when the amount of RAM is a critical matter.
A full software stack containing a known test vector scenario has been compiled and tested on a Cortex-M0 (STM32F030R8T6 @ 48MHz with 64KB of flash and 8KB of RAM). It has also been compiled and tested on a Cortex-M3 (STM32F103C8T6 @ 72MHz with 64KB of flash and 20KB of RAM). The results of the flash/RAM occupancy are given in the table below, as well as the timings of the ECDSA signature and verification operations.
Note: The Cortex-M0 case is a bit special in the ARM family. Since this MCU lacks a 32-bit x 32-bit to 64-bit multiplication instruction, the multiplication is implemented using a builtin software function. This yields in poor performance with WORDSIZE=64 compared to WORDSIZE=32 (this might be explained by the calling cost to the builtin function).
| libecc | STM32F103C8T6 (Cortex-M3 @ 72MHz) | STM32F030R8T6 (Cortex-M0 @ 48MHz) | |-----------------|:----------------------------------|:----------------------------------| | Flash size | 32KB | 30KB | | RAM size | 8KB | 8KB | | Sign time | 950ms | 2146ms | | Verif time | 1850ms | 4182ms |
In order to compare the libecc performance on these embedded platforms, we give figures for mbedTLS on Cortex-M3 taken from a recent study by ARM. As we have previously discussed, only the figures without NIST curves specific optimizations are of interest for a fair comparison:
| mbedTLS | LPC1768 (Cortex-M3 @ 92MHz)1 | |-----------------|:------------------------------| | Flash size | ?? | | RAM size | 3KB2| | Sign time | 1893ms | | Verif time | 3788ms |
1 Beware of the MCU frequency difference when comparing with libecc test case.
2 This figure only includes heap usage (stack usage is unknown so this is only a rough lower limit for RAM usage).
When dealing with the portability of a program across various platforms, many issues are in fact hidden behind this property. This is due to the very complex nature of what a platform is, namely:
Regarding libecc, here are the main elements to be aware of when dealing with a "new" platform:
stdint.hheader, it is still possible to compile libecc by exporting LIBECC_NOSTDLIB=1: in this case, the code will try to guess and fit to native C types or throw an error so that the user can adapt src/words/types.h to its specific case.
Some other external dependencies could arise depending on the compilation chain and/or the platform. Such an example is the implementation of the gcc and clang stack protection option, usually expecting the user to provide stack canaries generation (with random values) and failover behavior.
Compiling for Cortex-M targets should be straightforward using the arm-gcc none-eabi (for bare metal) cross-compiler as well as the specific Cortex-M target platform SDK. In order to compile the core libsign.a static library, the only thing to do is to execute the makefile command by overloading
$ CC=arm-none-eabi-gcc CFLAGS="$(TARGET_OPTS) -W -Wextra -Wall -Wunreachable-code \ -pedantic -fno-builtin -std=c99 -Os \ -ffreestanding -fno-builtin -nostdlib -DWORDSIZE=64" \ make build/libsign.a
$(TARGET_OPTS)are the flags specific to the considered target:
-mcpu=cortex-m3 -mthumbfor Cortex-M3 for example. The word size flag should be adapted to
-DWORDSIZE=32for the specific case of Cortex-M0/M0+ as discussed in the performance section (because of the lacking of 32-bit to 64-bit native multiplication instruction). The library can then be used to be linked against a file containing the
maincalling function, and the linking part will depend on the target platform (in addition to the target CPU): one will use the linker scripts provided by the platform/board manufacturer to produce a firmware suitable for the target (ST for STM32, NXP for LPC, Atmel for SAM, ...).
If the external dependencies have been implemented by the user, it is also possible to build a self-tests binary by adding the GNU ld linker script specific to the target platform (
linker_script.ldin the example below):
$ CC=arm-none-eabi-gcc CFLAGS="$(TARGETOPTS) -W -Wextra -Wall -Wunreachable-code \ -pedantic -fno-builtin -std=c99 -Os \ -ffreestanding -fno-builtin -nostdlib -DWORDSIZE=64" \ LDFLAGS="-T linkerscript.ld" \ make build/libsign.a
NOTE1: By default, the linker scripts share the RAM between heap and stack. Since libecc only uses stack, it is convenient (sometimes necessary, specifically on devices with very constrained RAM, such as Cortex-M0 with 8KB) to adapt the stack base address so that no stack overflow errors occur. These errors can be tricky to detect since they generally produce hard faults silently at run time.
NOTE2: It is up to the user to link against the libc (if standard functions are necessary) or not, but this will obviously influence the program size in flash. As already stated, the libc footprint is not included in the figured that have been given in the performance section.
This section is dedicated to giving some more details on how to compile libecc when non-GNU compilers are used (i.e. C compilers that do not support gcc syntax), and/or when compiling with environments that do not provide a GNU make compilation style (this is generally the case for all-in-one IDEs such as Visual Studio or other BSP and SDK provided by proprietary integrated circuits founders and board manufacturers).
As we have already stated, libecc requires a C99 compiler. More specifically, libecc makes use of only four feature of the C99 standard (over the older C89/C90 standard), namely: * The
long long inttype. * Designated initializers for structures. * The usage of the
inlinekeyword. * The usage of variadic macros.
Hence, when compiling with a given compiler, one will have to check that the compiler is either fully C99 compliant, or that these four features are at least implemented as extensions. Such details are generally provided by the compiler documentation.
NOTE: if one wants to adapt libecc for compilers where some of the necessary C99 features are missing, here is a big picture of the necessary work: * The
long long intand structures initializers are used all over libecc code, so they are strong requirements, and would imply deep code modifications. * The
inlinekeyword can be removed in most cases, except in the context of header files where it is used to define
static inlinefunctions. These functions will have to be moved to '.c' files, and one will have to deal with minor adaptations. * The usage of variadic macros is marginal and can be removed with minimal efforts: these are only used to deal with debug helpers in src/utils.
libecc uses a GNU style Makefile to automate the compilation process. One can however use other compilation environments that are not GNU make compatible by implementing the following guidelines: * Make the compilation toolchain compile into '.o' objects all the necessary '.c' files in src/nn, src/fp, src/curve, src/sig, src/utils and src/hash. * Make the compilation toolchain link the necessary object files to generate the static libraries:
libarith.a: °°°°°°°°°°° src/fp/fprand.o src/fp/fpmul.o src/fp/fpmontgomery.o src/fp/fpmulredc1.o src/fp/fpadd.o src/fp/fp.o src/fp/fppow.o src/nn/nnmul.o src/nn/nnmulredc1.o src/nn/nnlogical.o src/nn/nn.o src/nn/nnmodinv.o src/nn/nnadd.o src/nn/nnrand.o src/nn/nndiv.o src/utils/printnn.o src/utils/printfp.o src/utils/printkeys.o src/utils/printcurves.o src/utils/utils.o
libec.a: °°°°°°°° src/fp/fprand.o src/fp/fpmul.o src/fp/fpmontgomery.o src/fp/fpmulredc1.o src/fp/fpadd.o src/fp/fp.o src/fp/fppow.o src/nn/nnmul.o src/nn/nnmulredc1.o src/nn/nnlogical.o src/nn/nn.o src/nn/nnmodinv.o src/nn/nnadd.o src/nn/nnrand.o src/nn/nndiv.o src/utils/printnn.o src/utils/printfp.o src/utils/printkeys.o src/utils/printcurves.o src/utils/utils.o src/curves/prjpt.o src/curves/curves.o src/curves/affpt.o src/curves/prjptmonty.o src/curves/ecshortw.o src/curves/ecparams.o
libsign.a: °°°°°°°°°° src/fp/fprand.o src/fp/fpmul.o src/fp/fpmontgomery.o src/fp/fpmulredc1.o src/fp/fpadd.o src/fp/fp.o src/fp/fppow.o src/nn/nnmul.o src/nn/nnmulredc1.o src/nn/nnlogical.o src/nn/nn.o src/nn/nnmodinv.o src/nn/nnadd.o src/nn/nnrand.o src/nn/nndiv.o src/utils/printnn.o src/utils/printfp.o src/utils/printkeys.o src/utils/printcurves.o src/utils/utils.o src/curves/prjpt.o src/curves/curves.o src/curves/affpt.o src/curves/prjptmonty.o src/curves/ecshortw.o src/curves/ecparams.o src/hash/sha384.o src/hash/sha3-512.o src/hash/sha512.o src/hash/sha3-256.o src/hash/sha3-224.o src/hash/sha3.o src/hash/sha256.o src/hash/sha3-384.o src/hash/sha224.o src/hash/hashalgs.o src/sig/ecsdsa.o src/sig/ecdsa.o src/sig/ecrdsa.o src/sig/ecosdsa.o src/sig/ecfsdsa.o src/sig/eckcdsa.o src/sig/ecgdsa.o src/sig/ecsdsacommon.o src/sig/sigalgs.o src/sig/ec_key.o
Compiling binaries (such as
ec_utils) is nothing more than compiling concerned '.c' files under src/tests and linking them with
Some important preprocessor flags are expected to be defined when compiling libecc: *
WORDSIZE=: this is a preprocessor flag defining libecc internal words size (16, 32, or 64). By default libecc will detect the best size depending on the platform, but if the platform is not recognized the user is expected to provide this flag. *
WITH_STDLIB: this flag is used for standard library usage inside libecc. Exporting the environment variable
LIBECC_NOSTDLIB=1will trigger the non usage of standard includes and libraries. Standard C library headers and files are used for two things in the project: * Defining standard types through the
stdint.hheader. Though using this header helps libecc to properly define basic types in src/words/types.h, it is not required to use it and some heuristics can be used to define these types without standard headers (see explanations on that in src/words/types.h) comments. * Defining standard library functions used by external dependencies as well as
ec_utils. Compiling without
WITH_STDLIBflag means that one has to provide these.
In any case, if the user forgot to provide important preprocessing flags whenever they are necessary, errors will be thrown during the compilation process. As explained in src/words/types.h, when
stdint.his not used (i.e.
WITH_STDLIBnot defined), heuristics are used to guess primitive types sizes. These heuristics can fail and the user will have to adapt the types definitions accordingly depending on the platform.
When compiling using compilers that are not compatible with the gcc syntax, but still using a GNU make compilation environment, it is possible to adpat the Makefile behavior. In addition to the
LIBECC_NOSTDLIB=1environment variable previously described, here is the list of the variables that tune the compilation process:
CC: as usual, this overloads the compiler to be used.
LDFLAGS: these flags can be overloaded by user defined ones. The user defined flags will completely shadow the default flags for both the static libraries (libarith.a, libec.a, libsign.a) and the produced binaries.
BIN_LDFLAGS: when one wants to specifically tune compilation and linking flags for the static libraries and the binaries, these flags can be used and they will shadow the
RANLIB: these flags override the ar and ranlib tools used to generate the static library archives.
As a simple example of when and how to use this environment variables overloading system, let's take the following case: one wants to compile libecc with an old version of gcc that does not support the
-fstack-protector-strongoption (this is the case for gcc < 4.9). Since this is the flag used by default in libecc Makefile, an error will be triggered. It is possible to overcome this issue by overloading the
CFLAGSwith the following:
$ CFLAGS="-W -Werror -Wextra -Wall -Wunreachable-code -pedantic -fno-builtin -std=c99 -DFORTIFYSOURCE=2 \ -fstack-protector-all -O3 -DWITH_STDLIB -fPIC" make
As we can see, we keep the other
CFLAGSfrom default compilation while replacing
-fstack-protector-strongwith the less efficient but more compatible
In addition to compilation flags, it is also possible to overload the library word sizes as well as debug modes through Makefile targets: *
make debugwill compile a debug version of the library and binaries, with debugging symbols. *
make 64will respectively compile the library with 16, 32 and 64 bits word sizes.
make debug64will compile the debug versions of these. *
make force_arch64will force 32-bit and 64-bit architectures compilation (
-m64flags under gcc). These targets allow cross-compilation for a 32-bit (respectively 64-bit) target under a 64-bit (respectively 32-bit) host: a typical example is compiling for i386 under x86_64.
NOTE: the targets that we have described here can be used in conjunction with overloading the
LDFLAGS. Hence, a:
CFLAGS="-fstack-protector-all" make debug16will indeed compile all the binaries for debug, with a word size of 16 bits and a
-fstack-protector-allstack protection option.
As an example to show how to adapt the compilation process to compilers that are not compatible with the GNU compilers syntax, we will detail how to proceed by exploring the SDCC (Small Device C Compiler) toolchain. Porting libecc to this compiler is interesting for many reasons:
-cflag to generate object files,
-oflag to define output file).
We suppose that the user has also provided the external dependencies for print, random and time functions (otherwise explicit errors will be thrown by #error directives).
We will show how overloading the Makefile flags can be of use in this case. Say that we want to compile libecc in order to embed it in a Game Boy ROM. The Game Boy console uses a proprietary version of the Z80 MCU supported by SDCC under the target name
Hence, a first attempt at compilation would be to: * Overload
CC=sdccto change the default compiler. * Overload
RANLIB=sdranlibto overload the archives handling binaries (they are specific to SDCC). * Overload
CFLAGS="-mbgz80 --std-sdcc99"to specify the target, and ask for the C99 compatibility mode. * Overload
LDFLAGS=" "with nothing since we do not want default gcc linking flags to break compilation.
This first attempt will trigger an error:
$ CC=sdcc AR=sdar RANLIB=sdranlib CFLAGS="-mgbz80 --std-sdcc99" LDFLAGS=" " make ... src/external_deps/../words/words.h:62:2: error: #error "Unrecognized platform. \ Please specify the word size of your target (with make 16, make 32, make 64)"
As we have explained, when the platform is not recognized one has to specify the word size. We will do it by overloading
WORDSIZE=16: the Z80 is an 8-bit CPU, so it seems reasonable to fit the word size to 16-bit (8-bit half words). The second attempt will go further but will fail at some point when trying to compile the final binaries:
$ CC=sdcc AR=sdar RANLIB=sdranlib CFLAGS="-mgbz80 --std-sdcc99 -DWORDSIZE=16" LDFLAGS=" " make ... at 1: error 119: don't know what to do with file 'src/tests/ecselftests_core.o'. file extension unsupported
However, one can notice that the static libraries and some object files have been compiled, which is a first step! Compiling a full binary is a bit technical due to the fact that SDCC does not know how to deal with '.o' object files and '.a' archives. However, we can find our way out of this by renaming the 'libsign.a' to 'libsign.lib', and adding missing objects in the library. Compiling the
ec_self_testsbinary needs external dependencies (src/external_deps/print.c, src/external_deps/rand.c and src/external_deps/time.c) as well as the two '.c' files src/tests/ec_self_tests_core.c and src/tests/ec_self_tests.c, the latter being the one containing the
mainfunction. So we will first add the necessary objects files in the existing library with
$ cp build/libsign.a build/libsign.lib $ sdar q build/libsign.lib src/externaldeps/print.o src/externaldeps/rand.o src/externaldeps/time.o src/tests/ecselftestscore.o
Then, we compile and link src/tests/ec_self_tests.c with the library:
$ sdcc -mgbz80 -DWORDSIZE=16 --std-sdcc99 src/tests/ecselftests.c build/libsign.lib
This should create a
ec_self_tests.ihx, which has an Intel HEX file format for firmware programming. From this file, it is usually straightforward to create a Game Boy ROM file that can be interpreted by an emulator (there are however some quirks related to the Game Boy platform hardware architecture, see the note below).
NOTE: the purpose of the section was to show how to adapt the compilation process to compilers non compatible with the GNU C one. Consequently, fully porting libecc to the Game Boy platform is left as a complementary work, and this is not a "so easy" task. Among other things, one will have to deal with the ROM size limitation of 32KB that can be solved using bank switching, which will involve some code and compilation tuning. Another issue would be the RAM size of 8KB and properly handling the stack pointer base as described in the previous sections.
Though some efforts have been made to have (most of) the core algorithms constant time, turning libecc into a library shielded against side channel attacks is still a work in progress.
Beyond pure algorithmic considerations, many aspects of a program can turn secret leakage resistance into a very complex problem, especially when writing portable C code. Among other things, we can list the following:
For a thorough discussion about cryptography and constant time challenges, one can check this page.
In order to avoid a range of attacks on the signature algorithm exploiting various side channel attacks and leading to the recovery of the secret key (see here for more details), blinding operations can be used.
Since such security countermeasures have a significant performance hit on the signature algorithm, we have decided to leave the activation of such countermeasures as a voluntary decision to the end user. The performance impact might be acceptable or not depending on the context where the signature is performed, and whether attackers exploiting side channels are indeed considered in the threat model of the specific use case. Of course, for security critical use cases we recommend the blinding usage despite its performance cost.
Compiling the library with blinding is as simple as using the
BLINDIG=1environment variable (or the
$ BLINDING=1 make
NOTE: if you are unsure about your current security context, use the
All in all, libecc has now the following approaches to limit SCA:
ADALWAYS=1switch), plus complete formulas (see here) to avoid leaking point at infinity (by avoiding exceptions). Constant time operations are (tentatively) used to limit leakage of different operations, even though this task is very complex to achieve (especially in pure C). See the discussion above.
BLINDING=1switch, see the discussion above.
All these countermeasures must, of course, be validated on the specific target where the library runs with leakage assessments. Because of the very nature of C code and CPU microarchitectural details, it is very complex without such a leakage assessment (that again depends on the target) to be sure that SCA protection is indeed efficient.
Efforts made to render libecc robust against FIA are a work in progress, and will require substantial additions. As for SCA robustness, many elements might depend on the low-level compilation process and are difficult to handle at high-level in pure C.
For now, we check if points are on the curve when entering and leaving the scalar multiplication algorithm. Efforts are also made to sanity check the signature and verification contexts whenever possible. Currently, no specific effort has been made to render conditional operations robust (e.g. using double if and limiting compilation optimization).
The source code is composed of eight main parts that consist of the core source code:
 Machine code: in src/words
Abstraction layer to handle word size depending on the target machine (the word size can also be forced during compilation). Some useful low level macros and functions are handled there.
 Natural Numbers layer: in src/nn
This part implements all the functions related to positive integers arithmetic (including modular arithmetic).
 Fp layer: in src/fp
Finite field of prime order (binary fields are intentionally not supported).
 Elliptic curves core: in src/curves
This layer implements all the primitives handling elliptic curves over prime fields, including point addition and doubling, affine and projective coordinates, ...
These are the definitions of some standard curves (SECP, Brainpool, FRP, ...).
 EC*DSA signature algorithms: in src/sig
This layer implements the main elliptic curves based signature algorithms (ECSDSA, ECKCDSA, ECFSDSA, ECGDSA, ECRDSA, ECOSDSA). It exposes a sign and verify API with the standard Init/Update/Final logic.
 Hash functions: in src/hash
Hash functions (SHA-2 and SHA-3 based algorithms for now).
Various useful libc functions (memcpy, memset, ...) as well as well as pretty printing functions for our NN, Fp and curves layers.
In addition to the core source code of the library, various resources are also present in the source tree. We describe them hereafter.
Some self tests are provided for the signature algorithms over all the curves and using all the hash functions , as well as tests targeting arithmetic operations over NN and Fp more specifically :
 Sig self tests: in src/tests
Functions to test that the compiled library is properly working with regard to the signature algorithms over the curves statically defined in the library. These tests consiste in known test vectors, random test vectors (i.e. random data sign/verify) as well as performance measurements.
 Arithmetic self tests: in src/arithmetic
Functions to test that the compiled arithmetic library is properly working in its basic operations (addition, subtraction, multiplication, ...).
Some examples to help the user interact with the NN, Fp and cruves layers are also provided:
 User examples: in src/examples
User examples for each of the NN, Fp and curves layers. These examples show what are headers to use, and how to interact with the abstract mathematical objects of each layer.
The configuration of the library  as well as an external dependencies abstraction layer are also provided:
 External dependencies: in src/external_deps
These files contain the functions that are considered as external dependencies, meaning that their implementation is platform dependent (this concerns debug output on a console or file, random generation, time measurement). If no C standard library is provided, the user must implement those functions.
 Configuration files: in src/lib_ecc_config.h
These are top C headers that are used for libecc configuration, i.e. activate given hash/curve/signature algorithms at compilation time through ifdefs.
Finally, various useful scripts are provided:
Tools to expand the libecc with new user defined curves.
Here is a big picture of the library architecture summarizing the links between the modules previously described:
+-------------------------+ |EC*DSA signature | |algorithms |