1[](https://github.com/libecc/libecc/actions/workflows/libecc_compilation_tests.yml) 2[](https://github.com/libecc/libecc/actions/workflows/libecc_runtime_tests.yml) 3[](https://github.com/libecc/libecc/actions/workflows/libecc_crossarch_tests.yml) 4[](https://github.com/libecc/libecc/actions/workflows/libecc_python_tests.yml) 5[](https://github.com/libecc/libecc/actions/workflows/libecc_examples.yml) 6 7 8# libecc project 9 10## Copyright and license 11Copyright (C) 2017-2023 12 13This software is licensed under a dual BSD and GPL v2 license. 14See [LICENSE](LICENSE) file at the root folder of the project. 15 16## Authors 17 18 * Ryad BENADJILA (<mailto:ryadbenadjila@gmail.com>) 19 * Arnaud EBALARD (<mailto:arnaud.ebalard@ssi.gouv.fr>) 20 * Jean-Pierre FLORI (<mailto:jpflori@gmail.com>) 21 22## Contributors 23 * Nicolas VIVET (<mailto:nicolas.vivet@ssi.gouv.fr>) 24 * Karim KHALFALLAH (<mailto:karim.khalfallah@ssi.gouv.fr>) 25 * Niels SAMWEL (<mailto:nsamwel@google.com>) 26 27## Description 28This software implements a library for elliptic curves based 29cryptography (ECC). The API supports signature algorithms specified 30in the [ISO 14888-3:2018](https://www.iso.org/standard/76382.html) 31standard and some other signature algorithms as well as ECDH primitives, with the following specific curves and hash functions: 32 33 * **Signatures**: 34 * Core ISO 14888-3:2018 algorithms: ECDSA, ECKCDSA, ECGDSA, ECRDSA, EC{,O}SDSA, ECFSDSA, SM2. 35 * EdDSA (25519 and 448 as specified in [RFC 8032](https://datatracker.ietf.org/doc/html/rfc8032)). 36 * BIGN (as standardized in [STB 34.101.45-2013](https://github.com/bcrypto/bign)). We allow a more lax usage of 37 BIGN than in the standard as we allow any curve and any hash function. 38 * BIP0340, also known as the "Schnorr" Bitcoin proposal, as specified in [bip-0340](https://github.com/bitcoin/bips/blob/master/bip-0340.mediawiki). 39 We allow a more lax usage of BIP0340 than the standard as we allow any curve and any hash function (the standard mandates SECP256K1 with SHA-256). 40 41 * **ECDH**: 42 * ECC-CDH (Elliptic Curve Cryptography Cofactor Diffie-Hellman) as described in [section 5.7.1.2 of the NIST SP 800-56A Rev. 3](https://csrc.nist.gov/publications/detail/sp/800-56a/rev-3/final) standard. 43 * X25519 and X448 as specified in [RFC7748](https://datatracker.ietf.org/doc/html/rfc7748) (with some specificities, see the details below). 44 * **Curves**: SECP{192,224,256,384,521}R1, SECP{192,224,256}K1, BRAINPOOLP{192,224,256,320,384,512}{R1,T1}, 45 FRP256V1, GOST{256,512}, GOSTR3410-2001-CryptoPro{A,B,C,XchA,XchB,Test}-ParamSet, GOSTR3410-2012-{256,512}-ParamSet{A,B,C}, GOSTR3410-2012-256-ParamSetD, GOSTR3410-2012-512-ParamSetTest, SM2P256V1, SM2P{192,256}Test, WEI{25519,448}, BIGN{256,384,512}V1. The library can be easily expanded with 46 user defined curves using a standalone helper script. 47 * **Hash functions**: SHA-2 and SHA-3 hash functions (224, 256, 384, 512), SM3, RIPEMD-160, 48GOST 34.11-2012 as described in [RFC 6986](https://datatracker.ietf.org/doc/html/rfc6986) 49(also known as [Streebog](https://tc26.ru/en/events/research-projects-competition/streebog-competition.html)), 50SHAKE256 in its restricted version with 114 bytes output (mainly for Ed448), BELT-HASH (as standardized in 51[STB 34.101.31-2011](https://github.com/bcrypto/belt)), and BASH-{224,256,384,512} (as standardized in 52[STB 34.101.77-2020](http://apmi.bsu.by/assets/files/std/bash-spec24.pdf)). 53**HMAC** based on any of these hash functions is also included. 54 55ECDSA comes in two variants: the classical non-deterministic one, and the **deterministic** ECDSA 56as described in [RFC 6979](https://datatracker.ietf.org/doc/html/rfc6979). The deterministic version 57generates nonces using a HMAC-DRBG process, and is suitable for situations where there is 58no RNG or where entropy sources are considered weak (please note that any leak on these nonces 59bits can lead to devastating attacks exploiting the [Hidden Number Problem](https://eprint.iacr.org/2020/615.pdf)). 60On the downside, the deterministic version of ECDSA is susceptible to [fault attacks](https://eprint.iacr.org/2017/1014.pdf). 61Hence, one will have to **carefully select** the suitable version to use depending on the usage and 62attack context (i.e. which of side-channel attacks or fault attacks are easier to perform). 63The same applies to BIGN that comes in two flavours as standardized in [STB 34.101.45-2013](https://github.com/bcrypto/bign): 64non-deterministic and deterministic (following an iterative generation process using the BELT hash function and its underlying block cipher). 65 66The library also supports EdDSA (Ed25519 and Ed448) as defined in [RFC 8032](https://datatracker.ietf.org/doc/html/rfc8032) with 67all their variants (with context, pre-hashed). 68Since the core of the library supports short Weierstrass curves, and as 69EdDSA uses instead Twisted Edwards curves with dedicated formulas, we use 70**isogenies** as described in the [lwig-curve-representations](https://datatracker.ietf.org/doc/html/draft-ietf-lwig-curve-representations) 71draft. Isogenies are transformations (homomorphisms that are almost isomorphisms) between 72curves models, allowing to implement operations on one model by operating with 73formulas on another model. Concretely, in our case we perform computations on 74the Weierstrass WEI25519 that is isogenic to Ed25519 (Twisted Edwards) 75and Curve25519 (Montgomery) curves. This, of course, induces overheads in computations 76while having the great benefit of keeping the library core mathematical foundations simple 77and keep the defense-in-depth (regarding software security and side-channels) focused on 78a rather limited part: see the discussions below on libecc efforts with regards to security. 79 80Please note that as for deterministic ECDSA and BIGN, EdDSA signatures are trivially susceptible to 81[fault attacks](https://eprint.iacr.org/2017/1014.pdf) without having a non-deterministic 82variant. Hence, when using EdDSA one will have to either ensure that the usage context naturally prevents 83such attacks, that the platform implements countermeasures (e.g. using secure MCUs, etc.) or that 84other means allow to detect/mitigate such attacks (e.g. on the compilation toolchain side). 85 86Please refer to [this CFRG thread](https://mailarchive.ietf.org/arch/browse/cfrg/?gbt=1&index=5l3XCLHLCVfOmnkcv4mo2-pEV94) 87for more insight on why deterministic versus non-deterministic EC signature schemes is still an open debate 88and how the usage context and **attack model** is **crucial** when choosing to use one or the other. 89 90 91**Batch verification** is implemented for the signature algorithms that support it - the signature schemes 92that preserve some "reversible" projective point coordinate information in the signature value. 93This is the case for some "Schnorr" based schemes, namely ECFSDSA ("full Schnorr" from ISO14888-3), EdDSA and BIP0340. 94Batch verification allows (thanks to the Bos-Coster algorithm) to bring speedups between 2 to 6.5 times 95the regular verification for batches of at least 10 signatures, which is not negligible depending on the usage. 96Beware that for the specific case of BIP0340, results might depend on the underlying prime of the curve, since 97the batch verification makes heavy use of square root residues and the Tonelli-Shanks algorithm complexity 98is sensitive to the prime "form" (e.g. is equal to 1 modulo 4, etc.). Finally, beware that the speedup of 99batch verification comes at an increased memory cost: the Bos-Coster algorithm requires a scratchpad memory space 100that increases linearly with the number of signatures to be checked. 101 102 103Regarding the specific case of ECRDSA (the Russian standard), libecc implements by default the 104[RFC 7091](https://datatracker.ietf.org/doc/html/rfc7091) and [draft-deremin-rfc4491-bis](https://datatracker.ietf.org/doc/html/draft-deremin-rfc4491-bis) 105versions to comply with the standard test vectors (provided in the form of X.509 certificates). 106This version of the algorithm **differs** from the ISO/IEC 14888-3 description and test vectors, 107the main difference coming from the way the hash of the message to be signed/verified is processed: 108in the RFCs, the little endian representation of the hash is taken as big number while in ISO/IEC the big endian 109representation is used. This seems (to be confirmed) to be a discrepancy of ISO/IEC 14888-3 algorithm description 110that must be fixed there. In order to allow users to still be able to reproduce the ISO/IEC behavior, we provide 111a compilation toggle that will force this mode `USE_ISO14888_3_ECRDSA=1`: 112 113<pre> 114 $ USE_ISO14888_3_ECRDSA=1 make 115</pre> 116 117**ECDH (Elliptic Curve Diffie-Hellman)** variants are also implemented in the 118library. Classical ECDH over Weierstrass curves is implemented in the form 119of ECC-CDH (Elliptic Curve Cryptography Cofactor Diffie-Hellman) as described 120in [section 5.7.1.2 of the NIST SP 800-56A Rev. 3](https://csrc.nist.gov/publications/detail/sp/800-56a/rev-3/final) standard. Montgomery curves 121based algorithms (Curve25519 and Curve448) are included as specified in [RFC7748](https://datatracker.ietf.org/doc/html/rfc7748), 122although the implementation somehow diverges from the canonical ones as u coordinates on the curve 123quadratic twist are rejected (this is due to the underlying usage of isogenies to 124handle Montgomery curves). This divergence does not impact the ECDH use case though. 125 126 127Advanced usages of this library also include the possible implementation 128of elliptic curve based protocols as well as any algorithm 129on top of prime fields based elliptic curves (or prime fields, or rings 130of integers). Many examples are present in the [src/examples](src/examples) 131folder, notable ones being: 132 * Pollard-Rho, Miller-Rabin and square residues over finite fields. 133 * The RSA cryptosystem as defined in the PKCS#1 [RFC8017](https://datatracker.ietf.org/doc/html/rfc8017) 134standard. This implementation also comes with the integration of deprecated hash 135functions such as MD2, MD4, MD5, SHA-0, SHA-1, MDC-2, GOSTR34-11-94 and so on in order to be compliant with existing 136signatures (e.g. in X.509). These primitives are **not** included in the core 137library on purpose: they are **dangerous and broken** and must only be used for 138tests purposes. 139 * The DSA cryptosystem as defined in [FIPS 186-4](https://csrc.nist.gov/publications/detail/fips/186/4/final). 140 * The SDSA (Schnorr DSA) as defined in ISO14888-3 141 * The KCDSA (Korean DSA) as defined in ISO14888-3 142 * The GOSTR34-10-94 function as defined in [RFC4491](https://www.rfc-editor.org/rfc/rfc4491) 143 * The SSS (Shamir Secret Sharing) algorithm over a prime field of 256 bits. 144 145 146**NOTE**: for all the primitives (specifically relevant for signature primitives), a maximum 147allowed size for big numbers is **4096 bits** with word size **64 bits** (this will be less 148for word sizes 16 and 32 bits). This is due to an internal limitation of libecc 149on big numbers allocation documented [here](include/libecc/nn/nn_config.h). We can live with 150this limitation as the library is primarily intended to focus on ECC based algorithms. 151However, one should be aware that for example RSA with modulus > 4096 will fail (as well 152and DSA and other El-Gamal based algorithms): these primitives are only included as 153examples and should be used with care. 154 155**NOTE**: handling 4096 bits NN numbers must be explicitly configured at compilation 156time using the `-DUSER_NN_BIT_LEN=4096` toggle in the `CFLAGS` or `EXTRA_CFLAGS` as explained 157in [the dedicated section](https://github.com/ANSSI-FR/libecc#modifying-the-big-numbers-size). 158 159 160Compared to other cryptographic libraries providing such 161features, the differentiating points are: 162 163 * A focus on code readability and auditability. The code is pure C99, 164 with no dynamic allocation and includes pre/post-asserts in the code. 165 Hence, this library is a good candidate for embedded targets (it should be 166 easily portable accross various platforms). 167 * A clean layer separation for all needed mathematical abstractions and 168 operations. Strong typing (as "strong" as C99 allows, of course) of 169 mathematical objects has been used in each layer. 170 * The library has NOT been designed to break performance records, though 171 it does a decent job (see the [performance section discussion](#performance)). Similarly, 172 the library memory footprint (in terms of ROM and RAM usage) is not the 173 smallest achievable one (though some efforts have been made to limit it 174 and fit "common" platforms, see the [dedicated section](#constrained-devices)). 175 * libecc library core has **no external dependency** (not even the standard 176 libc library) to make it portable. See the 177 [section about portability](#compatibility-and-portability) for more information. 178 179## Building 180 181### Building the static libraries and the signature self tests 182 183The main [Makefile](Makefile) is in the root directory, and compiling is as simple as 184executing: 185 186<pre> 187 $ make 188</pre> 189 190By default, compilation is quiet. **Verbose compilation** (i.e. showing all the compilation 191executed commands) can be achieved using the `VERBOSE=1` toggle: 192 193<pre> 194 $ VERBOSE=1 make 195</pre> 196 197This will compile different elements in the [build](build/) directory: 198 199 * Three **archive** static libraries, each one containing (based on) the previous ones: 200 * **libarith.a**: this library contains the Natural Numbers (NN) and Finite field over primes 201 (Fp) arithmetic layers. 202 * **libec.a**: this library is based on libarith.a and contains the EC curves implementation 203 (points abstraction, point addition/doubling formulas and scalar multiplication). 204 * **libsign.a**: this library is based on libec.a and contains all our ISO 14888-3 signature 205 algorithms over some statically defined curves and hash functions. 206 * Two binaries based on the libsign.a static library: 207 * **ec\_self\_tests**: the self tests for signature/verification algorithm of ISO 14888-3 208 with known and random test vectors, as well as performance tests. Launching the self tests without 209 an argument will execute the three tests (known and fixed test vectors, random sign/verify 210 checks, and performance measurements). One can also launch each test separately. 211 212 For known test vectors: 213<pre> 214 $ ./build/ec_self_tests vectors 215 ======= Known test vectors test =================== 216 [+] ECDSA-SHA224/secp224r1 selftests: known test vectors sig/verif ok 217 [+] ECDSA-SHA256/secp256r1 selftests: known test vectors sig/verif ok 218 [+] ECDSA-SHA512/secp256r1 selftests: known test vectors sig/verif ok 219 ... 220</pre> 221 222 For sign/verify checks (with random key pairs and random data): 223 224<pre> 225 $ ./build/ec_self_tests rand 226 ======= Random sig/verif test =================== 227 [+] ECDSA-SHA224/FRP256V1 randtests: random import/export with sig(0)/verif(0) ok 228 [+] ECDSA-SHA224/SECP224R1 randtests: random import/export with sig(0)/verif(0) ok 229 ... 230</pre> 231 232 For performance measurements: 233 234<pre> 235 $ ./build/ec_self_tests perf 236 ======= Performance test ===================== 237 [+] ECDSA-SHA224/FRP256V1 perf: 462 sign/s and 243 verif/s 238 [+] ECDSA-SHA224/SECP224R1 perf: 533 sign/s and 276 verif/s 239 ... 240</pre> 241 242**NOTE**: it is possible to parallelize self tests (known and random) using the 243[OpenMP](https://en.wikipedia.org/wiki/OpenMP) framework (usually packaged with 244most distros) by using the `OPENMP_SELF_TESTS=1` compilation toggle. This requires 245the `WITH_STDLIB` option (as it obviously uses the standard library). Performance 246tests are not parallelized due to possible shared ressources exhaustion between CPUs and cores 247(e.g. caches, Branch Prediction Units, etc.). 248 249- **ec\_utils**: a tool for signing and verifying user defined files, with a user 250provided signature algorithm/curve/hash function triplet. The tool can also be 251used to generate signature keys. 252 253 Generate keys for ECKCDSA over the BRAINPOOLP512R1 curve, with 254the 'mykeypair' prefix: 255<pre> 256 $ ./build/ec_utils gen_keys BRAINPOOLP512R1 ECKCDSA mykeypair 257</pre> 258 259 This will create four files. Two 260binary '.bin' files corresponding to the private key (mykeypair\_private\_key.bin) 261and the public key (mykeypair\_public\_key.bin). Two header '.h' files are also 262created, corresponding to a C style header version of the keys so that these can 263be included and used in a C program using libecc. Note that both kind of keys 264(public and private) include leading metadata (type, algorithm, curve, etc) for 265possible sanity checks when they are used (e.g. to detect passing of an ECDSA 266private key to an ECKCDSA signature call, etc). 267 268 Once the key pair has been created, 269one can sign a raw binary file named 'myfile' and store the signature in 270'sig.bin'. In the example below, we use SHA3\_512 as the hash function for 271the signature. BRAINPOOLP512R1 and ECKCDSA are explicitly given (matching the 272type of key we generated during previous step). Note that the call would yield 273an error if invalid parameters were given (thanks to the metadata elements 274described above). 275<pre> 276 $ ./build/ec_utils sign BRAINPOOLP512R1 ECKCDSA SHA3_512 myfile mykeypair_private_key.bin sig.bin 277</pre> 278 After this, a raw signature is created, mainly consisting of the ECKCDSA (r, s) big 279numbers concatenated (the length of this file should be 1024 bits = 2 x 512 bits). The signature can now be verified with 280the 'verify' command and the public key, the result being either **OK** or **failed**: 281<pre> 282 $ ./build/ec_utils verify BRAINPOOLP512R1 ECKCDSA SHA3_512 myfile mykeypair_public_key.bin sig.bin 283 Signature check of myfile OK 284</pre> 285 286 The ec\_utils tool can also be used to produce/verify **structured binaries** 287containing a header, raw binary and their signature (see the 'struct\_sign' and 'struct\_verify' commands for a help on 288this mode). The rationale behind these commands is to ease the production/verification of self-contained signed images 289(which can be useful when dealing with embedded firmware updates for instance). 290 291### Building the user examples 292 293Since it is possible to use libecc as a NN (**positive** Natural Numbers), Fp (Finite field over primes) or EC curve layer library, 294we provide some examples in the [src/examples](src/examples) folder. Compiling these examples is as simple as: 295<pre> 296 $ cd src/examples 297 $ make 298</pre> 299 300* NN layer examples: 301 * [src/examples/basic/nn_miller_rabin.c](src/examples/basic/nn_miller_rabin.c): this example implements the 302 [Miller-Rabin](https://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test) composition (or probabilistic primality) test as 303 described in the [Handbook of Applied Cryptography (4.29)](http://cacr.uwaterloo.ca/hac/about/chap4.pdf). 304 * [src/examples/basic/nn_pollard_rho.c](src/examples/nn_pollard_rho.c): this example is a straightforward 305 implementation of the [Pollard's Rho](https://en.wikipedia.org/wiki/Pollard%27s_rho_algorithm) integer factorization 306 algorithm as specified in the [Handbook of Applied Cryptography (3.9)](http://cacr.uwaterloo.ca/hac/about/chap3.pdf). 307 308* Fp layer examples: 309 * [src/examples/basic/fp_square_residue.c](src/examples/basic/fp_square_residue.c): this is an implementation of 310 the [Tonelli-Shanks](https://en.wikipedia.org/wiki/Tonelli%E2%80%93Shanks_algorithm) algorithm for finding quadratic residues 311 over a prime field Fp. Given a prime field element x, the algorithm finds y so that y<sup>2</sup> = x (or informs that there 312 is no solution if this is the case). 313 314* Curves layer examples: 315 * [src/examples/basic/curve_basic_examples.c](src/examples/basic/curve_basic_examples.c): this example shows basic 316 features of libec for playing with elliptic curves group arithmetic, namely loading defined named curves, generating random points on 317 these curves, checking point addition and doubling formulas as well as scalar multiplication (both Montgomery and non Montgomery based). 318 319 * [src/examples/basic/curve_ecdh.c](src/examples/basic/curve_ecdh.c): the purpose of this code is to provide a toy example of 320 how to implement an [Elliptic Curve Diffie-Hellman](https://en.wikipedia.org/wiki/Elliptic_curve_Diffie%E2%80%93Hellman) protocol between two 321 entities 'Alice' and 'Bob' in order to produce a shared secret over a public channel. 322 323**WARNING**: these examples are **toy implementations** not to be used in a production environment (for instance, the code 324has neither been designed to be efficient nor robust against side channel attacks). Their purpose is only to show basic usage of the 325libarith and libec libraries. 326 327The **public headers** containing the functions to be used by higher level code are [include/libecc/libarith.h](include/libecc/libarith.h), 328[include/libecc/libec.h](include/libecc/libec.h) and [include/libecc/libsig.h](include/libecc/libsig.h): they are respectively used for the NN and Fp arithmetic layers, 329the Elliptic Curves layer, and the signature layer. 330 331More advanced examples are present in the examples folder: 332 333* Obsolete hash algorithms as an expansion to libecc core algorithms, in [src/examples/hash](src/examples/hash) (MD2, MD4, MD5, MDC2, SHA-0, 334SHA-1, and TDES for supporting MDC2). Please **be careful** when using them, it is advised to use them as toy primitives in **non-production code** 335(e.g. for checking old protocols and cipher suites). 336 337* Pre-ECC Signature schemes (based on Fp finite fields discrete logarithm) in [src/examples/sig](src/examples/sig) (RSA, DSA, SDSA, KCDSA, 338GOSTR34-10-94). Beware that for these signatures, you will have to expand the NN size to bigger values than the default (e.g. supporting RSA 4096 339will need a size of at least 4096 bits for NN, see how to expand the size in the documentation [here](include/libecc/nn/nn_config.h)). Although some 340efforts have been made when developing these signature algorithms, using them in production code should be decided with care (e.g. regarding 341side-channel attack and so on). 342 343* SSS (Shamir Secret Sharing) in [src/examples/sss](src/examples/sss). 344 345 346### Building the NN and Fp arithmetic tests 347 348libecc is provided with arithmetic random tests for the low level NN and Fp routines (addition, subtraction, logical 349operations, multiplication and Montgomery multiplication, ...). 350 351These tests are located inside the [src/arithmetic_tests/](src/arithmetic_tests/) folder. More specifically, the tests 352are split in two files: 353 354* [src/arithmetic_tests/arithmetic_tests.c](src/arithmetic_tests/arithmetic_tests.c): a '.c' file to be compiled and linked with libecc 355static library and performing a set of tests given on the standard input or in a file. The tests have a specific ASCII 356format with expected input/output as big numbers, and crafted **opcodes** defining the operation type (addition over 357NN, over Fp, ...). 358* [src/arithmetic_tests/arithmetic_tests_generator.py](src/arithmetic_tests/arithmetic_tests_generator.py): a python 359script that generates a set of arithmetic tests. 360 361### Building with the meson build system 362 363In parallel to the `Makefile` build system, a migration to the newer and more user friendly `meson` build is a 364**work in progress**. Compiling with `meson` can be simply achieved with: 365 366<pre> 367 $ meson setup builddir && cd builddir && meson dist 368</pre> 369 370Please note that you will need `meson`, `ninja` and `dunamai` (that can be installed from the Python `pip` installer). 371 372Most of libecc compilation options have been migrated, please check the output of the `meson configure` command to get 373a complete list of these (in the 'Project options' category). For instance, compiling libecc with a word size of 32 and 374a debug mode can be triggered with: 375 376<pre> 377 $ meson setup -Dwith_wordsize=32 -Dwith_debug=true builddir && cd builddir && meson dist 378</pre> 379 380## Configuring the libecc library 381 382### Basic configuration 383 384libecc can be statically configured at compilation time: the user can tune what curves, hash functions and signature 385algorithms are embedded in 'libsign.a' and all the binaries using it. 386 387The main entry point to configure/tune the library is [include/libecc/lib_ecc_config.h](include/libecc/lib_ecc_config.h). By default libecc 388embeds everything. In order to remove something, one has to **comment** the element to remove (i.e. comment the 389`WITH_XXX` macro). For instance, removing 390FRP256V1 is simply done by commenting the line: 391<pre> 392 /* Supported curves */ 393 /* #define WITH_CURVE_FRP256V1 */ /* REMOVING FRP256V1 */ 394 #define WITH_CURVE_SECP192R1 395 #define WITH_CURVE_SECP224R1 396 #define WITH_CURVE_SECP256R1 397 #define WITH_CURVE_SECP384R1 398 #define WITH_CURVE_SECP521R1 399 #define WITH_CURVE_BRAINPOOLP224R1 400 #define WITH_CURVE_BRAINPOOLP256R1 401 #define WITH_CURVE_BRAINPOOLP384R1 402 #define WITH_CURVE_BRAINPOOLP512R1 403 #define WITH_CURVE_GOST256 404 #define WITH_CURVE_GOST512 405 ... 406</pre> 407 408As another example, if one wants to build a custom project supporting only 409ECFSDA using SHA3-256 on BrainpoolP256R1, this can be done by keeping only the 410following elements in 411[include/libecc/lib_ecc_config.h](include/libecc/lib_ecc_config.h): 412 413<pre> 414 #define WITH_SIG_ECFSDSA 415 #define WITH_HASH_SHA3_256 416 #define WITH_CURVE_BRAINPOOLP256R1 417</pre> 418 419### Advanced configuration 420 421#### Modifying the word size 422 423libecc supports 16, 32 and 64 bits word sizes. Though this word size is usually inferred during compilation 424and adapted depending on the detected platform (to fit the best performance), the user can force it in three ways: 425 426* Overloading the `WORDSIZE` macro in [include/libecc/words/words.h](include/libecc/words/words.h). 427* Overloading the `WORDSIZE` macro in the Makefile `CFLAGS`. 428* Use specific Makefile targets. 429 430Please refer to the [portability guide](#libecc-portability-guide) for details on this. 431 432#### Modifying the big numbers size 433 434libecc infers the Natural Numbers maximum length from the **curves** parameters that have been statically 435defined in [include/libecc/lib_ecc_config.h](include/libecc/lib_ecc_config.h). Though this behaviour is perfectly fine and transparent 436for the user when dealing with the elliptic curves and signature layers, this can become a limitation when building 437code around the NN and Fp arithmetic layers. The user will be stuck with a hard coded maximum size of numbers depending 438on the curve that is used by libecc, which can be a nonsense if he is only interested in the big number basic 439algorithmic side (when the default curves are used, this maximum size is 521 bits, corresponding to SECP521 440parameters). 441 442libecc provides a way to **overload the NN maximum size**, with a strong limit depending on the word size (around 4435300 bits for 64-bit words, around 2650 bits for 32-bit words, and around 1300 bits for 16-bit words). See 444the comments in [include/libecc/nn/nn_config.h](include/libecc/nn/nn_config.h) for more details about this. In order to manually increase 445the NN size, the user will have to define the macro `USER_NN_BIT_LEN`, either directly in 446[include/libecc/nn/nn_config.h](include/libecc/nn/nn_config.h), or more appropriately through overloading the Makefile `CFLAGS` 447with `-DUSER_NN_BIT_LEN=` (see [the dedicated section](#overloading-makefile-variables) for more on how to do this). 448 449**NOTE**: objects and binaries compiled with different word sizes and/or user defined NN maximum bit lengths **are not compatible**, 450and could produce executables with dangerous runtime behaviour. In order to prevent possible honest mistakes, there is 451a safety net function catching such situations **at compilation time** in [include/libecc/nn/nn_config.h](include/libecc/nn/nn_config.h): the 452`nn_check_libconsistency` routine will throw an error. For instance, if 'libarith.a' has been compiled with 453`WORDSIZE=64`, and one tries to compile the arithmetic tests with `WORDSIZE=32`, here is the error the compiler 454should produce: 455 456<pre> 457... 458arithmetic_tests.c:(.text+0x3af21) : undefined reference to « nn_consistency_check_maxbitlen521wordsize32 » 459... 460</pre> 461 462#### Small RAM footprint devices (small stack usage) 463 464In order to squeeze the stack usage on very constrained devices, a `SMALLSTACK` toggle can be activated. Beware that this toggle 465removes some countermeasures (Itoh et al. masking) in order to fit in 8KB of RAM stack usage. Also beware that this is incompatible 466with EdDSA and X25519 as these specific functions need more than this amount of stack because of the isogenies usage (you should get 467a compilation error when trying to activate them with `SMALLSTACK=1`). 468 469<pre> 470$ SMALLSTACK=1 make 471</pre> 472 473 474## Expanding the libecc library 475 476Though libecc has been designed to be compiled with a static embedding of all its features (i.e. no dynamic modules 477loading), its **static code extensibility** has been a matter of attention. The library can be: 478* Easily expanded by **adding new curves**, with **zero coding effort**. Note that **only curves over prime fields are 479supported**. 480* Expanded with new hash functions and new signature algorithms with some coding effort, but clean and well defined 481APIs should ease this task. 482 483### Adding user defined curves 484 485A companion python script [scripts/expand_libecc.py](scripts/expand_libecc.py) will transparently add (and remove) new 486user defined curves in the source tree of the project. The '.h' headers defining the new curves 487will be created in a dedicated folder: [include/libecc/curves/user_defined/](include/libecc/curves/user_defined/). 488 489The python script should have a self explanatory and complete help: 490<pre> 491 $ python scripts/expand_libecc.py -h 492 This script is intented to *statically* expand the ECC library with user defined curves. 493 ... 494</pre> 495 496In order to add a curve, one can give explicit parameters (prime, order, ...) on the command line or 497provide a [RFC3279](https://www.ietf.org/rfc/rfc3279.txt) formatted ASN.1 file (DER or PEM) with the 498parameters. Sanity checks are performed by the script. The script is also able to generate 499**test vectors** for the new curve with the `--add-test-vectors` toggle. 500 501Let's show how we can add the BRAINPOOLP320R1 supported by OpenSSL. We use the `ecparam` option of 502the `openssl` command line: 503 504<pre> 505 $ openssl ecparam -param_enc explicit -outform DER -name brainpoolP320r1 -out brainpoolP320r1.der 506</pre> 507 508This creates a DER file 'brainpoolP320r1.der' embedding the parameters (beware of the `-param_enc explicit` 509option that is important here). Now, in order to add this new curve to libecc, we will execute: 510<pre> 511 $ python scripts/expand_libecc.py --name="mynewcurve" --ECfile=brainpoolP320r1.der --add-test-vectors=1 512 Test vectors generation asked: this can take some time! Please wait ... 513 1/56 514</pre> 515 516This will create a new header file 'ec_params_user_defined_mynewcurve.h' in the [include/libecc/curves/user_defined/](include/libecc/curves/user_defined/) 517folder, and it will modify some libecc core files to transparently add this curve for the next compilation (modified files 518are [include/libecc/curves/curves_list.h](include/libecc/curves/curves_list.h), [src/tests/ec_self_tests_core.h](src/tests/ec_self_tests_core.h), 519[include/libecc/lib_ecc_config.h](include/libecc/lib_ecc_config.h) and [include/libecc/lib_ecc_types.h](include/libecc/lib_ecc_types.h)). 520 521The test vectors generation can take some time since all the possible triplets (curve, hash function, signature algorithm) are 522processed with the new curve. 523 524After compiling the library, the new curve should show up in the self tests: 525<pre> 526 $ ./build/ec_self_tests 527 ======= Known test vectors test ================= 528 ... 529 [+] ECDSA_SHA224_USER_DEFINED_MYNEWCURVE_0 selftests: known test vectors sig/verif ok 530 ... 531 ======= Random sig/verif test =================== 532 ... 533 [+] ECDSA-SHA224/USER_DEFINED_MYNEWCURVE randtests: random import/export with sig/verif ok 534 ... 535 ======= Performance test ======================== 536 ... 537 [+] ECDSA-SHA224/USER_DEFINED_MYNEWCURVE perf: 269 sign/s and 141 verif/s 538 ... 539</pre> 540 541It should also appear in the `ec_utils` help: 542<pre> 543 $ ./build/ec_utils sign 544 Bad args number for ./build/ec_utils sign: 545 arg1 = curve name: FRP256V1 USER_DEFINED_MYNEWCURVE ... 546 arg2 = signature algorithm type: ECDSA ... 547 arg3 = hash algorithm type: SHA224 ... 548 arg4 = input file to sign 549 arg5 = input file containing the private key (in raw binary format) 550 arg6 = output file containing the signature 551 <arg7 (optional) = ancillary data to be used> 552</pre> 553 554It is possible to remove a user defined curve by using the python script and its name: 555<pre> 556 $ python scripts/expand_libecc.py --remove --name mynewcurve 557 You asked to remove everything related to user defined mynewcurve curve. Enter y to confirm, n to cancel [y/n]. y 558 Removing user defined curve mynewcurve ... 559</pre> 560 561It is also possible to remove **all** the user defined curves at once: 562<pre> 563 $ python scripts/expand_libecc.py --remove-all 564</pre> 565 566Finally, two companion shell scripts are provided along with the expanding python script in order to show its basic usage: 567 568* [scripts/gen_curves_tests.sh](scripts/gen_curves_tests.sh): this script generates the default libecc curves 569with explicit parameters given on the command line. Of course, since these curves are already embedded in 570libecc, there is no real use of generating them - the script is only here to serve as a showcase for expanding 571the library with explicit parameters. 572* [scripts/gen_openssl_curves_tests.sh](scripts/gen_openssl_curves_tests.sh): this script enumerates all OpenSSL 573named curves, generates a DER file with their parameters, and adds them to libecc. 574 575### Adding new hash and signature algorithms 576 577Obviously, adding new algorithms (hash or signature) will require adding new code. 578 579#### Adding new hash functions 580We detail hereafter the necessary steps to add a new hash function. The main file listing all the hash functions is [include/libecc/hash/hash_algs.h](include/libecc/hash/hash_algs.h). The new hash 581algorithm should be added here in compliance with the API described in the `hash_mapping struct`. This API includes: 582 583 * The digest and block sizes and a pretty print name for the algorithm. 584 * `hfunc_init`: the hash function initialization routine. 585 * `hfunc_update`: the hash function update routine. 586 * `hfunc_finalize`: the hash function finalization routine. 587 * `hfunc_scattered`: this function applies the hash function (i.e. compute the digest) on multiple messages 588 (it takes as input an array of pointers to message chunks, and an array of sizes). 589 590These libecc API functions are in fact redirections to the core routines of the hash algorithm, and 591the user is expected to add the specific implementation in '.c' and '.h' files inside the [src/hash/](src/hash/) 592folder. See [src/hash/sha224.c](src/hash/sha224.c) and [include/libecc/hash/sha224.h](include/libecc/hash/sha224.h) for a practical 593example of how to do this with SHA-224. 594 595Finally, the user is expected to update the libecc main configuration file [include/libecc/lib_ecc_config.h](include/libecc/lib_ecc_config.h) 596with the `WITH_MY_NEW_HASH` toggle ('my_new_hash' being the new hash function). 597 598#### Adding new signature algorithms 599In order to add a new elliptic curve based signature algorithm, here is the needed work: 600* The main file listing all the signature algorithms is [include/libecc/sig/sig_algs_internal.h](include/libecc/sig/sig_algs_internal.h). 601The signature algorithm should be added in compliance with the API described in the `ec_sig_mapping struct`. This 602API includes: 603 * The signature type and a pretty print name. 604 * `siglen`: a function giving the length of the produced signature. 605 * `init_pub_key`: a routine producing a public key when given a corresponding private key. 606 * `sign_init`, `sign_update` and `sign_finalize`: the usual functions initializing a signature, updating it with 607 input buffers, and finalizing it to produce an output signature. 608 * `verify_init`, `verify_update` and `verify_finalize`: the usual functions initializing a signature verification, updating 609 it with input buffers, and finalizing it to produce a check status (i.e. signature OK or not OK). 610 611These libecc APIs have to be plugged to the core signature functions, and the user is expected to handle this implementation 612with adding the specific '.c' files inside the [src/sig](src/sig) folder and the specific '.h' files inside the [include/libecc/sig](include/libecc/sig) folder. See [src/sig/ecdsa.c](src/sig/ecdsa.c) and [include/libecc/sig/ecdsa.h](include/libecc/sig/ecdsa.h) for a practical example of how to do this with ECDSA. 613 614Finally, the user is expected to update the libecc main configuration file [include/libecc/lib_ecc_config.h](include/libecc/lib_ecc_config.h) 615with the `WITH_MY_NEW_SIGN_ALG` toggle ('my_new_sign_alg' being the new signature algorithm). 616 617## <a name="performance"></a> Performance 618 619As already stated, libecc has not been designed with performance in mind, but 620with **simplicity** and **portability** as guiding principles; this implies 621several things when it comes to performance: 622 623* libecc does not intend to compete with libraries developed with platform specific accelerations, such as the use of **assembly** 624routines or the adaptation to CPUs quirks at execution time (e.g. a CPU with very slow shift instructions). [OpenSSL](https://www.openssl.org/) 625is an example of such libraries with good and homogeneous performance in mind on most heterogeneous platforms (with the lack of 626portability on very small embedded platforms though). 627* Some algorithmic tricks on specific prime curves are not implemented: the same algorithms are used for all the curves. 628This means for instance that curves using pseudo-Mersenne primes (such as NIST's SECP curves) won't be faster than 629curves using generic random primes (such as Brainpool curves), though pseudo-Mersenne primes can benefit from a 630dedicated reduction algorithm, yielding **orders of magnitude faster field arithmetic** (around five to ten times faster). See 631[here](https://tls.mbed.org/kb/cryptography/elliptic-curve-performance-nist-vs-brainpool) for further discussions on this. 632Consequently, we will only focus on performance comparison with other libraries using the Brainpool curves. 633* We use a very straightforward elliptic curve arithmetic implementation, without using literature generic algorithmic optimizations 634such as [windowing](https://en.wikipedia.org/wiki/Elliptic_curve_point_multiplication#Windowed_method) or 635[fixed-base comb](https://link.springer.com/chapter/10.1007/3-540-45537-X_21) precomputations. 636 637Nonetheless and despite all these elements, **libecc is on par with some other general purpose and portable cryptographic 638libraries** such as [mbedTLS](https://tls.mbed.org) (see the performance figures given below). 639 640We present hereafter the ECDSA performance comparison of libecc with mbedTLS and OpenSSL on various platforms representing 641different CPU flavours. Here are some information about the tested version when not stated otherwise: 642 643* mbedTLS: stable version 2.4.2, the figures have been gathered with the builtin benchmark. 644* OpenSSL: debian packaged version 1.1.0e. Since OpenSSL builtin ECDSA benchmark does not handle Brainpool curves, 645a basic C code using "named curves" have been compiled against the installed dynamic library. 646 647### Performance oriented platforms 648 649* **Core i7-5500U** (Broadwell family) is a typical x86 mid-range current laptop CPU. 650* **Xeon E3-1535M** (Skylake family) is a typical x86 high-end CPU. 651* **Power-7** is a typical server CPU of the previous generation (2010) with 652a PowerPC architecture. 653 654For all the platforms in this subsection, the CPUs have been tested in 64-bit mode. 655 656 657| **libecc** | Core i7-5500U @ 2.40GHz | Xeon E3-1535M v5 @ 2.90GHz | Power-7 | 658|-----------------|:----------------------------|:------------------------------|:--------------------------| 659| BP256R1 | 583 sign/s - 300 verif/s | 700 sign/s - 355 verif/s | 213 sign/s - 110 verif/s | 660| BP384R1 | 231 sign/s - 118 verif/s | 283 sign/s - 150 verif/s | 98 sign/s - 50 verif/s | 661| BP512R1 | 111 sign/s - 56 verif/s | 133 sign/s - 68 verif/s | 51 sign/s - 26 verif/s | 662 663| **mbedTLS** | Core i7-5500U @ 2.40GHz | Xeon E3-1535M v5 @ 2.90GHz | Power-7 | 664|-----------------|:----------------------------|:------------------------------|:--------------------------| 665| BP256R1 | 426 sign/s - 106 verif/s | 552 sign/s - 141 verif/s | 178 sign/s - 45 verif/s | 666| BP384R1 | 239 sign/s - 56 verif/s | 322 sign/s - 77 verif/s | 44 sign/s - 23 verif/s | 667| BP512R1 | 101 sign/s - 26 verif/s | 155 sign/s - 34 verif/s | 38 sign/s - 12 verif/s | 668 669| **OpenSSL** | Core i7-5500U @ 2.40GHz | Xeon E3-1535M v5 @ 2.90GHz | Power-7 | 670|-----------------|:----------------------------|:------------------------------|:--------------------------| 671| BP256R1 | 2463 sign/s - 1757 verif/s | 2873 sign/s - 2551 verif/s | 1879 sign/s - 1655 verif/s| 672| BP384R1 | 1091 sign/s - 966 verif/s | 1481 sign/s - 1265 verif/s | 792 sign/s - 704 verif/s| 673| BP512R1 | 727 sign/s - 643 verif/s | 1029 sign/s - 892 verif/s | 574 sign/s - 520 verif/s| 674 675### Embedded platforms with moderate constraints 676* **Marvel Armada A388** is a good representative of moderately constrained embedded devices, such as 677IAD (Internet Access Devices), NAS (Network Attached Storage), STB (Set Top Boxes) and smartphones. 678This SoC is built around a Cortex-A9 ARMv7-A 32-bit architecture. 679* **BCM2837** is a Broadcom SoC built around the recent 64-bit ARMv8-A architecture, with a 680Cortex-A53 core. This SoC can be found in the Raspberry Pi 3, and also represents what can 681be found in recent Smartphones. 682* **Atom D2700** is a small x86 CPU typically embedded in NAS devices. Though its "embedded" 683coloration, it uses a 64-bit mode that we have tested here. 684 685| **libecc** | Marvell A388 @ 1.6GHz | BCM2837 (aarch64) @ 1.2GHz | Atom D2700 @ 2.13GHz | 686|-----------------|:----------------------|----------------------------|:-----------------------| 687| BP256R1 | 64 sign/s - 33 verif/s| 43 sign/s - 22 verif/s | 68 sign/s - 35 verif/s | 688| BP384R1 | 24 sign/s - 12 verif/s| 17 sign/s - 9 verif/s | 25 sign/s - 13 verif/s | 689| BP512R1 | 11 sign/s - 5 verif/s | 8 sign/s - 4 verif/s | 12 sign/s - 6 verif/s | 690 691| **mbedTLS** | Marvell A388 @ 1.6GHz | BCM2837 (aarch64) @ 1.2GHz | Atom D2700 @ 2.13GHz -| 692|-----------------|:----------------------|----------------------------|:------------------------| 693| BP256R1 | 33 sign/s - 8 verif/s | 14 sign/s - 4 verif/s | 87 sign/s - 22 verif/s| 694| BP384R1 | 20 sign/s - 4 verif/s | 8 sign/s - 2 verif/s | 50 sign/s - 11 verif/s| 695| BP512R1 | 10 sign/s - 2 verif/s | 4 sign/s - 1 verif/s | 23 sign/s - 5 verif/s | 696 697| **OpenSSL** | Marvell A388 @ 1.6GHz | BCM2837 (aarch64) @ 1.2GHz | Atom D2700 @ 2.13GHz | 698|-----------------|:------------------------|----------------------------|:------------------------| 699| BP256R1 | 369 sign/s - 332 verif/s| 124 sign/s - 112 verif/s | 372 sign/s - 334 verif/s| 700| BP384R1 | 102 sign/s - 94 verif/s | 54 sign/s - 49 verif/s | 163 sign/s - 149 verif/s| 701| BP512R1 | 87 sign/s - 81 verif/s | 31 sign/s - 29 verif/s | 92 sign/s - 83 verif/s | 702 703 704### <a name="constrained-devices"></a> Very constrained embedded devices 705The library, when configured for a 256-bit curve (SECP256R1, FRP256), SHA-256 and ECDSA signature fits in around 706**30 Kilo Bytes of flash/EEPROM**, and uses around **8 Kilo Bytes of RAM** (stack) with variations depending on the 707chosen WORDSIZE (16, 32, 64), the compilation options (optimization for space `-Os` or speed `-O3`) and the 708target (depending on the instructions encoding, produced binary code can be more or less compact). 709A 521-bit curve with SHA-256 hash function and ECDSA signature should fit in 38 Kilo Bytes of flash and around 71016 Kilo Bytes of RAM (stack), with the same variations depending on the WORDSIZE and the compilation options. 711 712**Note**: libecc does not use any heap allocation, and the only global variables used are the **constant ones**. The 713constant data should end up in the flash/EEPROM section with a read only access to them: no RAM memory should 714be consumed by these. The libecc read/write data are only made of local variables on the stack. Hence, RAM 715consumption (essentially made of arrays representing internal objects such as numbers, point on curves ...) 716should be reasonably constant across platforms. **However**, some platforms using the 717**[Harvard architecture](https://en.wikipedia.org/wiki/Harvard_architecture)** (as opposed to Von Neumann's one) 718can have big limitations when accessing so called "program memory" as data. The 8-bit 719[Atmel AVR](http://www.atmel.com/products/microcontrollers/avr/) MCU 720is such an example. Compilers and toolchains for such architectures usually copy read only data in RAM at run time, 721and/or provide [non-standard ways](http://www.atmel.com/webdoc/avrlibcreferencemanual/pgmspace_1pgmspace_strings.html) 722to access read only data in flash/EEPROM program memory (through specific macros, pragmas, functions). The 723first case means that the RAM consumption will increase for libecc compared to the stack only usage (because of 724the runtime copy). The second case means that libecc code will have to be **adapted** to the platform if the user 725want to keep RAM usage at its lowest. In any case, tracking where `const` qualified data reside will be important 726when the amount of RAM is a critical matter. 727 728A full software stack containing a known test vector scenario has been compiled and tested on a **Cortex-M0** 729([STM32F030R8T6](http://www.st.com/en/microcontrollers/stm32f030r8.html) @ 48MHz with 64KB of flash and 8KB of RAM). 730It has also been compiled and tested on a **Cortex-M3** ([STM32F103C8T6](http://www.st.com/en/microcontrollers/stm32f103c8.html) 731@ 72MHz with 64KB of flash and 20KB of RAM). The results of the flash/RAM occupancy are given in the table below, 732as well as the timings of the ECDSA signature and verification operations. 733 734**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 735multiplication instruction, the multiplication is implemented using a builtin software function. This yields 736in poor performance with WORDSIZE=64 compared to WORDSIZE=32 (this might be explained by the calling cost to 737the builtin function). 738 739 740| **libecc** | STM32F103C8T6 (Cortex-M3 @ 72MHz) | STM32F030R8T6 (Cortex-M0 @ 48MHz) | 741|-----------------|:----------------------------------|:----------------------------------| 742| Flash size | 32KB | 30KB | 743| RAM size | 8KB | 8KB | 744| Sign time | 950ms | 2146ms | 745| Verif time | 1850ms | 4182ms | 746 747In order to compare the libecc performance on these embedded platforms, we give figures for mbedTLS on 748Cortex-M3 taken from a [recent study by ARM](http://csrc.nist.gov/groups/ST/lwc-workshop2015/presentations/session7-vincent.pdf). 749As we have previously discussed, only the figures without NIST curves specific optimizations are of interest 750for a fair comparison: 751 752| **mbedTLS** | LPC1768 (Cortex-M3 @ 92MHz)<sup>1</sup> | 753|-----------------|:------------------------------| 754| Flash size | ?? | 755| RAM size | 3KB<sup>2</sup>| 756| Sign time | 1893ms | 757| Verif time | 3788ms | 758 759<sup>1</sup> Beware of the MCU frequency difference when comparing with libecc test case. 760 761<sup>2</sup> This figure only includes heap usage (stack usage is unknown so this is only a 762rough lower limit for RAM usage). 763 764 765## <a name="compatibility-and-portability"></a> Compatibility and Portability 766 767### libecc compatibility 768 769When dealing with the **portability** of a program across various platforms, many issues are 770in fact hidden behind this property. This is due to the very complex nature of what a 771**platform** is, namely: 772 773* A **core CPU** architecture (x86, ARM, MIPS, PowerPC, ...). 774* A target **OS** (Linux, Windows, Mac OS, ...) or more low level firmware (including a **bare-metal** 775programming model or exotic real-time OS for microcontrollers for instance). 776* A proper compilation **(cross-)toolchain** producing binaries for the platform. This toolchain will usually 777include a compiler and a linker, both with possibly specific flags and limitations. 778 779Regarding libecc, here are the main elements to be aware of when dealing with a "new" platform: 780 781* libecc is in pure C-99 (no assembly), so it should compile on **any platform** with a decent C-99 782compatible compiler. The code is **endian neutral**, meaning that libecc should work on little endian 783and big endian platforms. 784* The Makefile has been tested with clang and gcc under Linux, as well as gcc cross-compilation variants 785such as **mingw** for Windows or gcc **Mac OS** version. In order to adapt the makefile behaviour when the 786compiler is not gcc/clang compatible, the user can modify the CFLAGS as well as the LDFLAGS by exporting them. 787* The library supports 16-bit/32-bit/64-bit word sizes, which should ensure compatibility with most of the platforms 788for 8-bit MCUs to 64-bit CPUs. If the toolchain does not have a [`stdint.h`](http://pubs.opengroup.org/onlinepubs/009695399/basedefs/stdint.h.html) 789header, it is still possible to compile libecc by exporting LIBECC_NOSTDLIB=1: in this case, the code will try to 790guess and fit to native C types or throw an error so that the user can adapt [src/words/types.h](src/words/types.h) to its specific case. 791* The library core is platform independent. However, when the platform is not recognized (i.e. everything aside UNIX/Windows/Mac OS), 792an error is thrown at compilation time asking the user to provide implementations for **external dependencies** 793in [src/external_deps/](src/external_deps), namely: 794 * The printing helper in [src/external_deps/print.c](src/external_deps/print.c). This helper serves output debugging purposes. 795 * The timing helper in [src/external_deps/time.c](src/external_deps/time.c). This helper is used to measure performances of the 796 library in the performance self tests. 797 * The random helper in [src/external_deps/rand.c](src/external_deps/rand.c). This helper is used in the core library for the signature 798 schemes. One should notice that a **good random source** is **crucial** for the security of Elliptic Curve based signature schemes, 799 so great care must be taken when implementing this. 800 801Some other external dependencies could arise depending on the compilation chain and/or the platform. Such an example is the 802implementation of the gcc and clang stack protection option, usually expecting the user to provide stack canaries generation 803(with random values) and failover behavior. 804 805 806### <a name="compiling-libecc-for-arm-cortex-m-with-GNU-gcc-arm"></a> Compiling libecc for ARM Cortex-M with GNU gcc-arm 807 808Compiling for Cortex-M targets should be straightforward using the arm-gcc none-eabi (for bare metal) cross-compiler as 809well 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 810the makefile command by overloading `CROSS_COMPILE`, `CC` and the `CFLAGS`: 811<pre> 812 $ CROSS_COMPILE=arm-none-eabi- CC=gcc CFLAGS="$(TARGET_OPTS) -W -Wextra -Wall -Wunreachable-code \ 813 -pedantic -fno-builtin -std=c99 -Os \ 814 -ffreestanding -fno-builtin -nostdlib -DWORDSIZE=64" \ 815 make build/libsign.a 816</pre> 817 818where `$(TARGET_OPTS)` are the flags specific to the considered target: `-mcpu=cortex-m3 -mthumb` for Cortex-M3 for example. The word size 819flag should be adapted to `-DWORDSIZE=32` for the specific case of Cortex-M0/M0+ as discussed in the [performance section](#performance) 820(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 821containing the `main` calling function, and the linking part will depend on the 822target platform (in addition to the target CPU): one will use the **linker scripts** provided by the platform/board manufacturer to produce 823a firmware suitable for the target (ST for STM32, NXP for LPC, Atmel for SAM, ...). 824 825If the external dependencies have been implemented by the user, it is also possible to build a self-tests binary by adding the 826GNU ld linker script specific to the target platform (`linker_script.ld` in the example below): 827<pre> 828 $ CROSS_COMPILE=arm-none-eabi- CFLAGS="$(TARGET_OPTS) -W -Wextra -Wall -Wunreachable-code \ 829 -pedantic -fno-builtin -std=c99 -Os \ 830 -ffreestanding -fno-builtin -nostdlib -DWORDSIZE=64" \ 831 LDFLAGS="-T linker_script.ld" \ 832 make build/libsign.a 833</pre> 834 835**NOTE1**: By default, the linker scripts share the RAM between heap and stack. Since libecc only uses stack, it is convenient 836(sometimes necessary, specifically on devices with very constrained RAM, such as Cortex-M0 with 8KB) to adapt the **stack base address** 837so that no stack overflow errors occur. These errors can be tricky to detect since they generally produce hard faults silently at 838run time. Also, a `SMALLSTACK=1` compilation toggle allows to limit stack consumption further: you can use it carefully if your device 839does not have enough stack for the regular compilation options (use with care as some side channels countermeasures are deactivated, and this 840mode is not compatible with the EdDSA signature and X25519 ECDH algorithm). 841 842**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 843program size in flash. As already stated, the libc footprint is not included in the figured that have been given in 844the [performance section](#performance). 845 846**NOTE3**: libecc has also been successfully tested with other non-GNU compilation SDK and toolchains such as [Keil MDK](http://www.keil.com/) 847configured to use the [ARM compiler](http://www2.keil.com/mdk5/compiler/5/). 848 849### <a name="libecc-portability-guide"></a> libecc portability guide 850 851This section is dedicated to giving some more details on how to compile libecc when non-GNU compilers 852are used (i.e. C compilers that do not support gcc syntax), and/or when compiling with environments that 853do not provide a **GNU make** compilation style (this is generally the case for all-in-one IDEs such as 854Visual Studio or other BSP and SDK provided by proprietary integrated circuits founders and board manufacturers). 855 856#### 1 - Compilers and C99 standard compliance 857 858As we have already stated, libecc requires a C99 compiler. More specifically, libecc makes use of 859only four feature of the C99 standard (over the older C89/C90 standard), namely: 860* The `long long int` type. 861* Designated initializers for structures. 862* The usage of the `inline` keyword. 863* The usage of variadic macros. 864 865Hence, when compiling with a given compiler, one will have to check that the compiler is 866**either fully C99 compliant**, or that these four features are at least **implemented as extensions**. 867Such details are generally provided by the compiler documentation. 868 869**NOTE**: if one wants to adapt libecc for compilers where some of the necessary C99 features are missing, here is a 870big picture of the necessary work: 871* The `long long int` and structures initializers are used all over libecc code, so they are 872**strong requirements**, and would imply deep code modifications. 873* The `inline` keyword can be removed in most cases, except in the context of header files where it is used 874to define `static inline` functions. These functions will have to be moved to '.c' files, and one will have to 875deal with minor adaptations. 876* The usage of variadic macros is marginal and can be removed with minimal efforts: these are only used 877to deal with debug helpers in [src/utils](src/utils). 878 879#### 2 - Compiling with environments without GNU make 880 881libecc uses a GNU style [Makefile](Makefile) to automate the compilation process. One can however use other 882compilation environments that are not GNU make compatible by implementing the following guidelines: 883* Make the compilation toolchain compile into **'.o' objects** all the necessary '.c' files in [src/nn](src/nn), 884[src/fp](src/fp), [src/curve](src/curve), [src/sig](src/sig), [src/utils](src/utils) and [src/hash](src/hash). 885* Make the compilation toolchain **link** the necessary object files to generate the static libraries: 886<pre> 887 libarith.a: 888 °°°°°°°°°°° 889 src/fp/fp_rand.o src/fp/fp_mul.o src/fp/fp_montgomery.o src/fp/fp_mul_redc1.o src/fp/fp_add.o src/fp/fp.o 890 src/fp/fp_pow.o src/nn/nn_mul.o src/nn/nn_mul_redc1.o src/nn/nn_logical.o src/nn/nn.o src/nn/nn_modinv.o 891 src/nn/nn_add.o src/nn/nn_rand.o src/nn/nn_div.o src/utils/print_nn.o src/utils/print_fp.o src/utils/print_keys.o 892 src/utils/print_curves.o src/utils/utils.o 893</pre> 894<pre> 895 libec.a: 896 °°°°°°°° 897 src/fp/fp_rand.o src/fp/fp_mul.o src/fp/fp_montgomery.o src/fp/fp_mul_redc1.o src/fp/fp_add.o src/fp/fp.o src/fp/fp_pow.o 898 src/nn/nn_mul.o src/nn/nn_mul_redc1.o src/nn/nn_logical.o src/nn/nn.o src/nn/nn_modinv.o src/nn/nn_add.o src/nn/nn_rand.o 899 src/nn/nn_div.o src/utils/print_nn.o src/utils/print_fp.o src/utils/print_keys.o src/utils/print_curves.o src/utils/utils.o 900 src/curves/prj_pt.o src/curves/curves.o src/curves/aff_pt.o src/curves/prj_pt_monty.o src/curves/ec_shortw.o src/curves/ec_params.o 901</pre> 902<pre> 903 libsign.a: 904 °°°°°°°°°° 905 src/fp/fp_rand.o src/fp/fp_mul.o src/fp/fp_montgomery.o src/fp/fp_mul_redc1.o src/fp/fp_add.o src/fp/fp.o src/fp/fp_pow.o 906 src/nn/nn_mul.o src/nn/nn_mul_redc1.o src/nn/nn_logical.o src/nn/nn.o src/nn/nn_modinv.o src/nn/nn_add.o src/nn/nn_rand.o 907 src/nn/nn_div.o src/utils/print_nn.o src/utils/print_fp.o src/utils/print_keys.o src/utils/print_curves.o src/utils/utils.o 908 src/curves/prj_pt.o src/curves/curves.o src/curves/aff_pt.o src/curves/prj_pt_monty.o src/curves/ec_shortw.o src/curves/ec_params.o 909 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 910 src/hash/sha3-384.o src/hash/sha224.o src/hash/hash_algs.o src/sig/ecsdsa.o src/sig/ecdsa.o src/sig/ecrdsa.o src/sig/ecosdsa.o 911 src/sig/ecfsdsa.o src/sig/eckcdsa.o src/sig/ecgdsa.o src/sig/ecsdsa_common.o src/sig/sig_algs.o src/sig/ec_key.o 912</pre> 913 914Compiling binaries (such as `ec_self_tests` and `ec_utils`) is nothing more than compiling concerned '.c' files under [src/tests](src/tests) 915and linking them with `libsign.a`. 916 917#### 3 - Dealing with the standard library and stdint 918 919Some important **preprocessor flags** are expected to be defined when compiling libecc: 920* `WORDSIZE=`: this is a preprocessor flag defining libecc internal words size (16, 32, or 64). By default libecc will 921detect the best size depending on the platform, but if the platform is not recognized the user is expected to 922provide this flag. 923* `WITH_STDLIB`: this flag is used for standard library usage inside libecc. Exporting the environment variable 924`LIBECC_NOSTDLIB=1` will trigger the **non usage** of standard includes and libraries. Standard C library headers and files 925are used for two things in the project: 926 * Defining standard types through the `stdint.h` header. 927Though using this header helps libecc to properly define basic types in [include/libecc/words/types.h](include/libecc/words/types.h), it is not 928required to use it and some heuristics can be used to define these types without standard headers (see explanations on that 929in [include/libecc/words/types.h](include/libecc/words/types.h)) comments. 930 * Defining standard library functions used by external dependencies as well as `ec_utils`. Compiling without `WITH_STDLIB` 931flag means that one has to provide these. 932 933In any case, if the user forgot to provide important preprocessing flags whenever they are necessary, **errors will be thrown** during 934the compilation process. As explained in [include/libecc/words/types.h](include/libecc/words/types.h), when `stdint.h` is not used (i.e. `WITH_STDLIB` 935not defined), heuristics are used to guess primitive types sizes. These heuristics can fail and the user will have to adapt the types 936definitions accordingly depending on the platform. 937 938#### <a name="overloading-makefile-variables"></a> 4 - Overloading Makefile variables 939 940When compiling using compilers that are not compatible with the gcc syntax, but still using a GNU make 941compilation environment, it is possible to **adpat the Makefile behavior**. In addition to the `LIBECC_NOSTDLIB=1` 942environment variable previously described, here is the list of the variables that tune the compilation process: 943 944* `CC`: as usual, this overloads the compiler to be used. 945* `CFLAGS` and `LDFLAGS`: these flags can be overloaded by user defined ones. The user defined flags will completely 946shadow the default flags for both the static libraries (libarith.a, libec.a, libsign.a) and the produced binaries. 947* `LIB_CFLAGS`, `BIN_CFLAGS`, `BIN_LDFLAGS`: when one wants to specifically tune compilation and linking flags for 948the static libraries and the binaries, these flags can be used and they will shadow the `CFLAGS` and `LDFLAGS`. 949* `AR` and `RANLIB`: these flags override the ar and ranlib tools used to generate the static library archives. 950 951As a simple example of when and how to use this environment variables overloading system, let's take the following case: 952one wants to compile libecc with an old version of gcc that does not support the `-fstack-protector-strong` option 953(this is the case for [gcc < 4.9](https://lwn.net/Articles/584225/)). Since this is the flag used by default in 954libecc Makefile, an error will be triggered. It is possible to overcome this issue by overloading the `CFLAGS` with 955the following: 956<pre> 957 $ CFLAGS="-W -Werror -Wextra -Wall -Wunreachable-code -pedantic -fno-builtin -std=c99 -D_FORTIFY_SOURCE=2 \ 958 -fstack-protector-all -O3 -DWITH_STDLIB -fPIC" make 959</pre> 960 961As we can see, we keep the other `CFLAGS` from default compilation while replacing `-fstack-protector-strong` with 962the **less efficient but more compatible** `-fstack-protector-all`. 963 964In addition to compilation flags, it is also possible to overload the library **word sizes** as well as **debug** 965modes through Makefile targets: 966* `make debug` will compile a debug version of the library and binaries, with debugging symbols. 967Setting the environment variable `VERBOSE_INNER_VALUES=1` will print out more values. 968* `make 16`, `make 32` and `make 64` will respectively compile the library with 16, 32 and 64 bits word sizes. `make debug16`, 969`make debug32` and `make debug64` will compile the debug versions of these. 970* `make force_arch32` and `make force_arch64` will force 32-bit and 64-bit architectures compilation (`-m32` and `-m64` 971flags under gcc). These targets allow cross-compilation for a 32-bit (respectively 64-bit) target under a 64-bit (respectively 97232-bit) host: a typical example is compiling for i386 under x86\_64. 973 974**NOTE**: the targets that we have described here can be used in conjunction with overloading the `CFLAGS` and `LDFLAGS`. Hence, 975a: `CFLAGS="-fstack-protector-all" make debug16` 976will indeed compile all the binaries for debug, with a word size of 16 bits and a `-fstack-protector-all` stack protection option. 977 978 979#### 5 - A concrete example with SDCC 980 981As an example to show how to adapt the compilation process to compilers that are not compatible with the 982GNU compilers syntax, we will detail how to proceed by exploring the [SDCC](http://sdcc.sourceforge.net/) 983(Small Device C Compiler) toolchain. Porting libecc to this compiler is interesting for many reasons: 984 985* The SDCC compiler uses some specific syntax, though it shares some similarities with 986other compilers (`-c` flag to generate object files, `-o` flag to define output file). 987* This compiler is "almost" C99 compliant: depending on the target, it has some C99 features 988[partially implemented](http://sdcc.sourceforge.net/mediawiki/index.php/Standard_compliance). 989* The compiler has "exotic" targets such as the Zilog Z80 MCU. 990 991We suppose that the user has also provided the **external dependencies** for print, random and time 992functions (otherwise explicit errors will be thrown by #error directives). 993 994We will show how overloading the Makefile flags can be of use in this case. Say that we want 995to compile libecc in order to embed it in a Game Boy ROM. The Game Boy console uses a proprietary 996version of the Z80 MCU supported by SDCC under the target name `gbz80`. 997 998Hence, a first attempt at compilation would be to: 999* Overload `CC=sdcc` to change the default compiler. 1000* Overload `AR=sdar` and `RANLIB=sdranlib` to overload the archives handling binaries (they are specific 1001to SDCC). 1002* Overload `CFLAGS="-mbgz80 --std-sdcc99"` to specify the target, and ask for the C99 compatibility mode. 1003* Overload `LDFLAGS=" "` with nothing since we do not want default gcc linking flags to break compilation. 1004 1005This first attempt will trigger an error: 1006<pre> 1007 $ CC=sdcc AR=sdar RANLIB=sdranlib CFLAGS="-mgbz80 --std-sdcc99" LDFLAGS=" " make 1008 ... 1009 src/external_deps/../words/words.h:62:2: error: #error "Unrecognized platform. \ 1010 Please specify the word size of your target (with make 16, make 32, make 64)" 1011</pre> 1012 1013As we have explained, when the platform is not recognized one has to specify the word size. We will 1014do it by overloading `WORDSIZE=16`: the Z80 is an 8-bit CPU, so it seems reasonable to fit the word 1015size to 16-bit (8-bit half words). The second attempt will go further but will fail at some point when 1016trying to compile the final binaries: 1017<pre> 1018 $ CC=sdcc AR=sdar RANLIB=sdranlib CFLAGS="-mgbz80 --std-sdcc99 -DWORDSIZE=16" LDFLAGS=" " make 1019 ... 1020 at 1: error 119: don't know what to do with file 'src/tests/ec_self_tests_core.o'. file extension unsupported 1021</pre> 1022 1023However, one can notice that the static libraries and some object files have been compiled, which is a 1024first step! Compiling a full binary is a bit technical due to the fact that SDCC does not know how 1025to deal with '.o' object files and '.a' archives. However, we can find our way out of this by renaming 1026the 'libsign.a' to 'libsign.lib', and adding missing objects in the library. Compiling the `ec_self_tests` 1027binary needs external dependencies ([src/external_deps/print.c](src/external_deps/print.c), 1028[src/external_deps/rand.c](src/external_deps/rand.c) and [src/external_deps/time.c](src/external_deps/time.c)) 1029as well as the two '.c' files [src/tests/ec_self_tests_core.c](src/tests/ec_self_tests_core.c) and 1030[src/tests/ec_self_tests.c](src/tests/ec_self_tests.c), the latter being the one containing the `main` 1031function. So we will first add the necessary objects files in the existing library with `sdar`: 1032<pre> 1033 $ cp build/libsign.a build/libsign.lib 1034 $ sdar q build/libsign.lib src/external_deps/print.o src/external_deps/rand.o src/external_deps/time.o src/tests/ec_self_tests_core.o 1035</pre> 1036 1037Then, we compile and link [src/tests/ec_self_tests.c](src/tests/ec_self_tests.c) with the library: 1038<pre> 1039 $ sdcc -mgbz80 -DWORDSIZE=16 --std-sdcc99 src/tests/ec_self_tests.c build/libsign.lib 1040</pre> 1041 1042This should create a `ec_self_tests.ihx`, which has an [Intel HEX](https://fr.wikipedia.org/wiki/HEX_(Intel)) 1043file format for firmware programming. From this file, it is usually straightforward to create a Game Boy ROM file 1044that can be interpreted by an [emulator](http://m.peponas.free.fr/gngb/) (there are however some quirks related 1045to the Game Boy platform hardware architecture, see the note below). 1046 1047**NOTE**: the purpose of the section was to show how to adapt the compilation process to compilers non 1048compatible with the GNU C one. Consequently, fully porting libecc to the Game Boy platform is left as 1049a complementary work, and this is not a "so easy" task. Among other things, one will have to deal with 1050the ROM size limitation of 32KB that can be solved using [bank switching](http://gbdev.gg8.se/wiki/articles/Memory_Bank_Controllers), 1051which will involve some code and compilation tuning. Another issue would be the RAM size of 8KB and 1052properly handling the stack pointer base as described in the [previous sections](#compiling-libecc-for-arm-cortex-m-with-GNU-gcc-arm). 1053 1054## libecc, side channel attacks and constant time 1055 1056### Constant time 1057 1058Though **some efforts** have been made to have (most of) the core algorithms 1059constant time, turning libecc into a library shielded against side channel attacks 1060is still a **work in progress**. 1061 1062Beyond pure algorithmic considerations, many aspects of a program can turn 1063secret leakage resistance into a very complex problem, especially when writing 1064portable C code. Among other things, we can list the following: 1065 1066* Low level issues can arise when dealing with heterogeneous platforms (some 1067instructions might not be constant time) and compilers optimizations 1068(a C code that seems constant time is in fact compiled to a non constant time assembly). 1069* Any shared hardware resource can become a leakage source (the caches, the 1070branch prediction unit, ...). When dealing with a portable source code 1071meant to run on most platforms, it is not an easy task to think of all these 1072leakage sources. 1073 1074For a thorough discussion about cryptography and constant time challenges, 1075one can check [this page](https://bearssl.org/constanttime.html). 1076 1077### Signature algorithm blinding 1078 1079In order to avoid a range of attacks on the signature algorithm exploiting various 1080side channel attacks and leading to the recovery of the secret key 1081(see [here](https://www.nccgroup.trust/globalassets/our-research/us/whitepapers/2018/rohnp-return-of-the-hidden-number-problem.pdf) 1082for more details), **blinding** operations can be used. 1083 1084Since such security countermeasures have a **significant performance hit** on the signature algorithm, we have 1085decided to leave the activation of such countermeasures as a **voluntary decision** to the end user. 1086The performance impact might be acceptable or not depending on the context where the signature is performed, and whether attackers exploiting side channels 1087are indeed considered in the threat model of the specific use case. 1088Of course, for **security critical use cases we recommend the blinding usage 1089despite its performance cost**. 1090 1091Compiling the library with blinding is as simple as using the ``BLINDIG=1`` environment variable (or the ``-DUSE_SIG_BLINDING`` C flag): 1092 1093<pre> 1094 $ BLINDING=1 make 1095</pre> 1096 1097**NOTE**: if you are **unsure** about your current security context, use the ``BLINDING=1`` by default! 1098 1099 1100### Overview of SCA (Side Channel Attacks) countermeasures 1101 1102All in all, libecc has now the following approaches to limit SCA: 1103 1104* SPA (Simple Power Analysis) is thwarted using Montgomery Ladder (or Double and Add Always optionally using the ``ADALWAYS=1`` switch), plus complete formulas 1105(see [here](https://joostrenes.nl/publications/complete.pdf)) to avoid leaking point at infinity (by avoiding exceptions). Constant time 1106operations are (tentatively) used to limit leakage of different operations, 1107even though this task is very complex to achieve (especially in pure C). See 1108the discussion above. 1109* DDPA (Data DPA) is thwarted using blinding of the point (projective 1110coordinates) and of the scalar (with adding a random multiple of the 1111curve order with maximum entropy). Because of its major impact on 1112performance, blinding must be specifically turned on by the used using the 1113``BLINDING=1`` switch, see the discussion above. 1114* ADPA (Address-bit DPA) is limited using Itoh et al. Double and Add Always 1115masked variant. See the article "A Practical Countermeasure against 1116Address-Bit Differential Power Analysis" by Itoh, Izu and Takenaka for more information. 1117 1118All these countermeasures must, of course, be validated on the specific target 1119where the library runs with leakage assessments. Because of the very nature of 1120C code and CPU microarchitectural details, it is very complex without such a leakage 1121assessment (that again depends on the target) to be sure that SCA protection 1122is indeed efficient. 1123 1124### libecc against FIA (Fault Injection Attacks) 1125 1126Efforts made to render libecc robust against FIA are a **work in progress**, and 1127will require **substantial additions**. As for SCA robustness, many elements 1128might depend on the low-level compilation process and are difficult to handle 1129at high-level in pure C. 1130 1131For now, we check if points are on the curve when entering and leaving the 1132scalar multiplication algorithm, as well as when importing external public points. 1133Efforts are also made to sanity check the signature and verification contexts whenever possible, 1134as well as all the intermediate contexts (natural numbers, fields, hash functions, etc.). 1135 1136Currently, no specific effort has been made to render conditional operations robust 1137(e.g. using double if and limiting compilation optimization). 1138 1139 1140## Software architecture 1141 1142The public header of the libecc API are in the [include/libecc/](include/libecc/) 1143folder. Then, the source code is composed of eight main parts that consist of the 1144**core source code**: 1145 1146 * [1] Machine code: in [src/words](src/words/) 1147 1148 >Abstraction layer to handle word size depending 1149 >on the target machine (the word size can also be forced during 1150 >compilation). Some useful low level macros and functions are 1151 >handled there. 1152 1153 * [2] Natural Numbers layer: in [src/nn](src/nn/) 1154 1155 >This part implements all the functions 1156 >related to positive integers arithmetic (including modular 1157 >arithmetic). 1158 1159 * [3] Fp layer: in [src/fp](src/fp/) 1160 1161 >Finite field of prime order (binary fields are 1162 >intentionally not supported). 1163 1164 * [4] Elliptic curves core: in [src/curves](src/curves/) 1165 1166 >This layer implements all the primitives 1167 >handling elliptic curves over prime fields, including point 1168 >addition and doubling, affine and projective coordinates, ... 1169 1170 * [5] Curves definitions: in [include/libecc/curves/known](include/libecc/curves/known) and 1171 [include/libecc/curves/user_defined](include/libecc/curves/user_defined) 1172 1173 >These are the definitions of some standard curves (SECP, Brainpool, 1174 >FRP, ...). 1175 1176 * [6] EC\*DSA signature algorithms: in [src/sig](src/sig/) 1177 1178 >This layer implements the main 1179 >elliptic curves based signature algorithms (ECSDSA, ECKCDSA, 1180 >ECFSDSA, ECGDSA, ECRDSA, ECOSDSA). It exposes a sign and 1181 >verify API with the standard Init/Update/Final logic. 1182 1183 * [7] Hash functions: in [src/hash](src/hash/) 1184 1185 >Hash functions (SHA-2 and SHA-3 based algorithms 1186 >for now). 1187 1188 * [8] Utils: in [src/utils](src/utils/) 1189 1190 >Various useful libc functions (memcpy, memset, ...) as well as 1191 >well as pretty printing functions for our NN, Fp and curves layers. 1192 1193In addition to the core source code of the library, various resources 1194are also present in the source tree. We describe them hereafter. 1195 1196Some self tests are provided for the signature algorithms over all the curves 1197and using all the hash functions [9], as well as tests targeting arithmetic 1198operations over NN and Fp more specifically [10]: 1199 1200 * [9] Sig self tests: in [src/tests](src/tests/) 1201 1202 >Functions to test that the compiled library is 1203 >properly working with regard to the signature algorithms over 1204 >the curves statically defined in the library. 1205 >These tests consiste in known test vectors, random test 1206 >vectors (i.e. random data sign/verify) as well as performance measurements. 1207 1208 * [10] Arithmetic self tests: in [src/arithmetic](src/arithmetic_tests/) 1209 1210 >Functions to test that the compiled arithmetic library is 1211 >properly working in its basic operations (addition, subtraction, 1212 >multiplication, ...). 1213 1214Some examples to help the user interact with the NN, Fp and cruves layers 1215are also provided: 1216 1217 * [11] User examples: in [src/examples](src/examples/) 1218 1219 >User examples for each of the NN, Fp and curves layers. These 1220 >examples show what are headers to use, and how to interact with 1221 >the abstract mathematical objects of each layer. Other examples beyond 1222 >the basic ones (such as RSA signatures, SSS, etc.) are also present there. 1223 1224The configuration of the library [13] as well as an external dependencies 1225abstraction layer are also provided: 1226 1227 * [12] External dependencies: in [src/external_deps](src/external_deps/) 1228 1229 >These files contain the functions that 1230 >are considered as external dependencies, meaning that their 1231 >implementation is platform dependent (this concerns debug 1232 >output on a console or file, random generation, time measurement). 1233 >If no C standard library is provided, the user must implement 1234 >those functions. 1235 1236 * [13] Configuration files: in [include/libecc/lib_ecc_config.h](include/libecc/lib_ecc_config.h) 1237 1238 >These are top C headers that are used for 1239 >libecc configuration, i.e. activate given hash/curve/signature 1240 >algorithms at compilation time through ifdefs. 1241 1242Finally, various useful scripts are provided: 1243 1244 * [14] Scripts: in [scripts](scripts/) 1245 1246 >Tools to expand the libecc with new user defined curves. 1247 1248Here is a big picture of the library architecture summarizing the links 1249between the modules previously described: 1250 1251<pre> 1252 +-------------------------+ 1253 |EC*DSA signature | 1254 |algorithms | <------------------+ 1255 |(ISO 14888-3) [6] | | 1256 +-----------+-------------+ | 1257 ^ | 1258 | | 1259 +-----------+-------------+ +----------+------------+ 1260 |Curves (SECP, Brainpool, | | Hash | 1261 |FRP, ...) | | functions | 1262 | [5] | | [7] | 1263 +-----------+-------------+ +-----------------------+ 1264 ^ @@@@@@@@@@@@@@@@@@@@@@@@@@@@@ 1265 | @ {Useful auxiliary modules}@ 1266 +-----------+-------------+ @ +------------------------+@ 1267 | Elliptic curves [4] | @ | Utils [8] |@ 1268 | core (scalar mul, ...) | @ +------------------------+@ 1269 +-----------+-------------+ @ | Sig Self tests [9] |@ 1270 ^ @ | Arith Self tests [10] |@ 1271 | @ | User Examples [11] |@ 1272 | @ +------------------------+@ 1273 | @ | External deps [12] |@ 1274 +-----------+-------------+ @ +------------------------+@ 1275 | Fp finite fields [3] | @ | LibECC conf files [13] |@ 1276 | arithmetic | @ +------------------------+@ 1277 +-----------+-------------+ @ | Scripts [14] |@ 1278 ^ @ +------------------------+@ 1279 | @@@@@@@@@@@@@@@@@@@@@@@@@@@@@ 1280 +-----------+-------------+ +------------------------+ 1281 | NN natural [2] | <------+ Machine related | 1282 | numbers arithmetic | | (words, ...) [1] | 1283 +-------------------------+ +------------------------+ 1284 1285</pre> 1286 1287## Integration with hardware acceleration: IPECC 1288 1289On the IPECC branch of the libecc repository, there is an integration 1290with the [IPECC](https://github.com/ANSSI-FR/IPECC) hardware accelerator 1291project. This project provides hardware acceleration for ECC points operations 1292(addition, doubling, scalar multiplication, etc.) with advanced SCA countermeasures. 1293 1294In order to use this accelerator, please follow these steps. First checkout the 1295IPECC branch: 1296 1297<pre> 1298 $ git clone https://github.com/libecc/libecc 1299 $ git checkout -b IPECC 1300</pre> 1301 1302Then fetch the dedicated driver on the [IPECC repository](https://github.com/ANSSI-FR/IPECC) 1303(this will clone the current repository and place the IPECC drivers in the `src/curve` folder): 1304 1305<pre> 1306 $ make install_hw_driver 1307</pre> 1308 1309Then, you can compile the library with hardware acceleration by selecting the underlying platform: 1310 1311<pre> 1312 $ make clean && CC=arm-linux-gnueabihf-gcc EXTRA_CFLAGS="-Wall -Wextra -O3 -g3 -mcpu=cortex-a9 -mfpu=vfpv3 -mfloat-abi=hard -static" VERBOSE=1 USE_EC_HW=1 USE_EC_HW_DEVMEM=1 USE_EC_HW_LOCKING=1 BLINDING=1 make 1313</pre> 1314 1315Please note that `USE_EC_HW=1` selects the hardware accelerator (this is mandatory to activate the hardware acceleration backend in libecc), 1316and `USE_EC_HW_DEVMEM=1` selects the DEVMEM backend (you can use `USE_EC_HW_STANDALONE=1` for the standalone mode, `USE_EC_HW_UIO=1` for UIO, 1317and `USE_EC_HW_SOCKET_EMUL=1` for the socket emulation using the Python server). 1318We also override the `CC` compiler to `arm-linux-gnueabihf-gcc` for the Zynq platform (adapt at your will depending on your 1319target), and add some necessary extra CFLAGS for the platform (as well as a `-static` binary compilation to avoid library dependency issues). 1320Finally, `USE_EC_HW_LOCKING=1` is used here for thread safety during hardware access: this flag is necessary for multi-threading. 1321 1322libecc has been successfully tested on a [Zynq Arty Z7](https://digilent.com/reference/programmable-logic/arty-z7/start) board with 1323a **factor 6** performance improvement compared to pure software on the same platform (with SCA countermeasures): 1324 1325<pre> 1326az7-ecc-axi:/home/petalinux# ./ec_self_tests_sw perf 1327======= Performance test ======================== 1328[+] ECDSA-SHA224/FRP256V1 perf: 6 sign/s and 6 verif/s 1329[+] ECDSA-SHA224/SECP192R1 perf: 9 sign/s and 9 verif/s 1330[+] ECDSA-SHA224/SECP224R1 perf: 7 sign/s and 7 verif/s 1331[+] ECDSA-SHA224/SECP256R1 perf: 6 sign/s and 6 verif/s 1332... 1333 1334az7-ecc-axi:/home/petalinux# ./ec_self_tests_hw perf 1335======= Performance test ======================== 1336[+] ECDSA-SHA224/FRP256V1 perf: 34 sign/s and 32 verif/s 1337[+] ECDSA-SHA224/SECP192R1 perf: 57 sign/s and 52 verif/s 1338[+] ECDSA-SHA224/SECP224R1 perf: 44 sign/s and 39 verif/s 1339[+] ECDSA-SHA224/SECP256R1 perf: 34 sign/s and 32 verif/s 1340[+] ECDSA-SHA224/SECP384R1 perf: 16 sign/s and 15 verif/s 1341[+] ECDSA-SHA224/SECP521R1 perf: 8 sign/s and 8 verif/s 1342[+] ECDSA-SHA224/BRAINPOOLP192R1 perf: 57 sign/s and 52 verif/s 1343[+] ECDSA-SHA224/BRAINPOOLP224R1 perf: 44 sign/s and 40 verif/s 1344</pre> 1345 1346
){kind=link}
){kind=link}
){kind=link}
){kind=link}
){kind=link}