README.md
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 11 Copyright (C) 2017-2023 12 13 This software is licensed under a dual BSD and GPL v2 license. 14 See [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 28 This software implements a library for elliptic curves based 29 cryptography (ECC). The API supports signature algorithms specified 30 in the [ISO 14888-3:2018](https://www.iso.org/standard/76382.html) 31 standard 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, 48 GOST 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)), 50 SHAKE256 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 55 ECDSA comes in two variants: the classical non-deterministic one, and the **deterministic** ECDSA 56 as described in [RFC 6979](https://datatracker.ietf.org/doc/html/rfc6979). The deterministic version 57 generates nonces using a HMAC-DRBG process, and is suitable for situations where there is 58 no RNG or where entropy sources are considered weak (please note that any leak on these nonces 59 bits can lead to devastating attacks exploiting the [Hidden Number Problem](https://eprint.iacr.org/2020/615.pdf)). 60 On the downside, the deterministic version of ECDSA is susceptible to [fault attacks](https://eprint.iacr.org/2017/1014.pdf). 61 Hence, one will have to **carefully select** the suitable version to use depending on the usage and 62 attack context (i.e. which of side-channel attacks or fault attacks are easier to perform). 63 The same applies to BIGN that comes in two flavours as standardized in [STB 34.101.45-2013](https://github.com/bcrypto/bign): 64 non-deterministic and deterministic (following an iterative generation process using the BELT hash function and its underlying block cipher). 65 66 The library also supports EdDSA (Ed25519 and Ed448) as defined in [RFC 8032](https://datatracker.ietf.org/doc/html/rfc8032) with 67 all their variants (with context, pre-hashed). 68 Since the core of the library supports short Weierstrass curves, and as 69 EdDSA 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) 71 draft. Isogenies are transformations (homomorphisms that are almost isomorphisms) between 72 curves models, allowing to implement operations on one model by operating with 73 formulas on another model. Concretely, in our case we perform computations on 74 the Weierstrass WEI25519 that is isogenic to Ed25519 (Twisted Edwards) 75 and Curve25519 (Montgomery) curves. This, of course, induces overheads in computations 76 while having the great benefit of keeping the library core mathematical foundations simple 77 and keep the defense-in-depth (regarding software security and side-channels) focused on 78 a rather limited part: see the discussions below on libecc efforts with regards to security. 79 80 Please 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 82 variant. Hence, when using EdDSA one will have to either ensure that the usage context naturally prevents 83 such attacks, that the platform implements countermeasures (e.g. using secure MCUs, etc.) or that 84 other means allow to detect/mitigate such attacks (e.g. on the compilation toolchain side). 85 86 Please refer to [this CFRG thread](https://mailarchive.ietf.org/arch/browse/cfrg/?gbt=1&index=5l3XCLHLCVfOmnkcv4mo2-pEV94) 87 for more insight on why deterministic versus non-deterministic EC signature schemes is still an open debate 88 and 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 92 that preserve some "reversible" projective point coordinate information in the signature value. 93 This is the case for some "Schnorr" based schemes, namely ECFSDSA ("full Schnorr" from ISO14888-3), EdDSA and BIP0340. 94 Batch verification allows (thanks to the Bos-Coster algorithm) to bring speedups between 2 to 6.5 times 95 the regular verification for batches of at least 10 signatures, which is not negligible depending on the usage. 96 Beware that for the specific case of BIP0340, results might depend on the underlying prime of the curve, since 97 the batch verification makes heavy use of square root residues and the Tonelli-Shanks algorithm complexity 98 is sensitive to the prime "form" (e.g. is equal to 1 modulo 4, etc.). Finally, beware that the speedup of 99 batch verification comes at an increased memory cost: the Bos-Coster algorithm requires a scratchpad memory space 100 that increases linearly with the number of signatures to be checked. 101 102 103 Regarding 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) 105 versions to comply with the standard test vectors (provided in the form of X.509 certificates). 106 This version of the algorithm **differs** from the ISO/IEC 14888-3 description and test vectors, 107 the main difference coming from the way the hash of the message to be signed/verified is processed: 108 in the RFCs, the little endian representation of the hash is taken as big number while in ISO/IEC the big endian 109 representation is used. This seems (to be confirmed) to be a discrepancy of ISO/IEC 14888-3 algorithm description 110 that must be fixed there. In order to allow users to still be able to reproduce the ISO/IEC behavior, we provide 111 a 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 118 library. Classical ECDH over Weierstrass curves is implemented in the form 119 of ECC-CDH (Elliptic Curve Cryptography Cofactor Diffie-Hellman) as described 120 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. Montgomery curves 121 based algorithms (Curve25519 and Curve448) are included as specified in [RFC7748](https://datatracker.ietf.org/doc/html/rfc7748), 122 although the implementation somehow diverges from the canonical ones as u coordinates on the curve 123 quadratic twist are rejected (this is due to the underlying usage of isogenies to 124 handle Montgomery curves). This divergence does not impact the ECDH use case though. 125 126 127 Advanced usages of this library also include the possible implementation 128 of elliptic curve based protocols as well as any algorithm 129 on top of prime fields based elliptic curves (or prime fields, or rings 130 of integers). Many examples are present in the [src/examples](src/examples) 131 folder, 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) 134 standard. This implementation also comes with the integration of deprecated hash 135 functions such as MD2, MD4, MD5, SHA-0, SHA-1, MDC-2, GOSTR34-11-94 and so on in order to be compliant with existing 136 signatures (e.g. in X.509). These primitives are **not** included in the core 137 library on purpose: they are **dangerous and broken** and must only be used for 138 tests 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 147 allowed size for big numbers is **4096 bits** with word size **64 bits** (this will be less 148 for word sizes 16 and 32 bits). This is due to an internal limitation of libecc 149 on big numbers allocation documented [here](include/libecc/nn/nn_config.h). We can live with 150 this limitation as the library is primarily intended to focus on ECC based algorithms. 151 However, one should be aware that for example RSA with modulus > 4096 will fail (as well 152 and DSA and other El-Gamal based algorithms): these primitives are only included as 153 examples and should be used with care. 154 155 **NOTE**: handling 4096 bits NN numbers must be explicitly configured at compilation 156 time using the `-DUSER_NN_BIT_LEN=4096` toggle in the `CFLAGS` or `EXTRA_CFLAGS` as explained 157 in [the dedicated section](https://github.com/ANSSI-FR/libecc#modifying-the-big-numbers-size). 158 159 160 Compared to other cryptographic libraries providing such 161 features, 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 183 The main [Makefile](Makefile) is in the root directory, and compiling is as simple as 184 executing: 185 186 <pre> 187 $ make 188 </pre> 189 190 By default, compilation is quiet. **Verbose compilation** (i.e. showing all the compilation 191 executed commands) can be achieved using the `VERBOSE=1` toggle: 192 193 <pre> 194 $ VERBOSE=1 make 195 </pre> 196 197 This 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 244 most distros) by using the `OPENMP_SELF_TESTS=1` compilation toggle. This requires 245 the `WITH_STDLIB` option (as it obviously uses the standard library). Performance 246 tests 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 250 provided signature algorithm/curve/hash function triplet. The tool can also be 251 used to generate signature keys. 252 253 Generate keys for ECKCDSA over the BRAINPOOLP512R1 curve, with 254 the 'mykeypair' prefix: 255 <pre> 256 $ ./build/ec_utils gen_keys BRAINPOOLP512R1 ECKCDSA mykeypair 257 </pre> 258 259 This will create four files. Two 260 binary '.bin' files corresponding to the private key (mykeypair\_private\_key.bin) 261 and the public key (mykeypair\_public\_key.bin). Two header '.h' files are also 262 created, corresponding to a C style header version of the keys so that these can 263 be 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 265 possible sanity checks when they are used (e.g. to detect passing of an ECDSA 266 private key to an ECKCDSA signature call, etc). 267 268 Once the key pair has been created, 269 one 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 271 the signature. BRAINPOOLP512R1 and ECKCDSA are explicitly given (matching the 272 type of key we generated during previous step). Note that the call would yield 273 an error if invalid parameters were given (thanks to the metadata elements 274 described 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 279 numbers concatenated (the length of this file should be 1024 bits = 2 x 512 bits). The signature can now be verified with 280 the '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** 287 containing a header, raw binary and their signature (see the 'struct\_sign' and 'struct\_verify' commands for a help on 288 this 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 293 Since it is possible to use libecc as a NN (**positive** Natural Numbers), Fp (Finite field over primes) or EC curve layer library, 294 we 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 324 has neither been designed to be efficient nor robust against side channel attacks). Their purpose is only to show basic usage of the 325 libarith and libec libraries. 326 327 The **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, 329 the Elliptic Curves layer, and the signature layer. 330 331 More 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, 334 SHA-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, 338 GOSTR34-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 339 will 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 340 efforts have been made when developing these signature algorithms, using them in production code should be decided with care (e.g. regarding 341 side-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 348 libecc is provided with arithmetic random tests for the low level NN and Fp routines (addition, subtraction, logical 349 operations, multiplication and Montgomery multiplication, ...). 350 351 These tests are located inside the [src/arithmetic_tests/](src/arithmetic_tests/) folder. More specifically, the tests 352 are 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 355 static library and performing a set of tests given on the standard input or in a file. The tests have a specific ASCII 356 format with expected input/output as big numbers, and crafted **opcodes** defining the operation type (addition over 357 NN, over Fp, ...). 358 * [src/arithmetic_tests/arithmetic_tests_generator.py](src/arithmetic_tests/arithmetic_tests_generator.py): a python 359 script that generates a set of arithmetic tests. 360 361 ### Building with the meson build system 362 363 In 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 370 Please note that you will need `meson`, `ninja` and `dunamai` (that can be installed from the Python `pip` installer). 371 372 Most of libecc compilation options have been migrated, please check the output of the `meson configure` command to get 373 a complete list of these (in the 'Project options' category). For instance, compiling libecc with a word size of 32 and 374 a 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 384 libecc can be statically configured at compilation time: the user can tune what curves, hash functions and signature 385 algorithms are embedded in 'libsign.a' and all the binaries using it. 386 387 The main entry point to configure/tune the library is [include/libecc/lib_ecc_config.h](include/libecc/lib_ecc_config.h). By default libecc 388 embeds 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 390 FRP256V1 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 408 As another example, if one wants to build a custom project supporting only 409 ECFSDA using SHA3-256 on BrainpoolP256R1, this can be done by keeping only the 410 following 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 423 libecc supports 16, 32 and 64 bits word sizes. Though this word size is usually inferred during compilation 424 and 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 430 Please refer to the [portability guide](#libecc-portability-guide) for details on this. 431 432 #### Modifying the big numbers size 433 434 libecc infers the Natural Numbers maximum length from the **curves** parameters that have been statically 435 defined in [include/libecc/lib_ecc_config.h](include/libecc/lib_ecc_config.h). Though this behaviour is perfectly fine and transparent 436 for the user when dealing with the elliptic curves and signature layers, this can become a limitation when building 437 code around the NN and Fp arithmetic layers. The user will be stuck with a hard coded maximum size of numbers depending 438 on the curve that is used by libecc, which can be a nonsense if he is only interested in the big number basic 439 algorithmic side (when the default curves are used, this maximum size is 521 bits, corresponding to SECP521 440 parameters). 441 442 libecc provides a way to **overload the NN maximum size**, with a strong limit depending on the word size (around 443 5300 bits for 64-bit words, around 2650 bits for 32-bit words, and around 1300 bits for 16-bit words). See 444 the comments in [include/libecc/nn/nn_config.h](include/libecc/nn/nn_config.h) for more details about this. In order to manually increase 445 the 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` 447 with `-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**, 450 and could produce executables with dangerous runtime behaviour. In order to prevent possible honest mistakes, there is 451 a 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 454 should produce: 455 456 <pre> 457 ... 458 arithmetic_tests.c:(.text+0x3af21) : undefined reference to « nn_consistency_check_maxbitlen521wordsize32 » 459 ... 460 </pre> 461 462 #### Small RAM footprint devices (small stack usage) 463 464 In order to squeeze the stack usage on very constrained devices, a `SMALLSTACK` toggle can be activated. Beware that this toggle 465 removes some countermeasures (Itoh et al. masking) in order to fit in 8KB of RAM stack usage. Also beware that this is incompatible 466 with EdDSA and X25519 as these specific functions need more than this amount of stack because of the isogenies usage (you should get 467 a 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 476 Though libecc has been designed to be compiled with a static embedding of all its features (i.e. no dynamic modules 477 loading), 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 479 supported**. 480 * Expanded with new hash functions and new signature algorithms with some coding effort, but clean and well defined 481 APIs should ease this task. 482 483 ### Adding user defined curves 484 485 A companion python script [scripts/expand_libecc.py](scripts/expand_libecc.py) will transparently add (and remove) new 486 user defined curves in the source tree of the project. The '.h' headers defining the new curves 487 will be created in a dedicated folder: [include/libecc/curves/user_defined/](include/libecc/curves/user_defined/). 488 489 The 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 496 In order to add a curve, one can give explicit parameters (prime, order, ...) on the command line or 497 provide a [RFC3279](https://www.ietf.org/rfc/rfc3279.txt) formatted ASN.1 file (DER or PEM) with the 498 parameters. 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 501 Let's show how we can add the BRAINPOOLP320R1 supported by OpenSSL. We use the `ecparam` option of 502 the `openssl` command line: 503 504 <pre> 505 $ openssl ecparam -param_enc explicit -outform DER -name brainpoolP320r1 -out brainpoolP320r1.der 506 </pre> 507 508 This creates a DER file 'brainpoolP320r1.der' embedding the parameters (beware of the `-param_enc explicit` 509 option 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 516 This will create a new header file 'ec_params_user_defined_mynewcurve.h' in the [include/libecc/curves/user_defined/](include/libecc/curves/user_defined/) 517 folder, and it will modify some libecc core files to transparently add this curve for the next compilation (modified files 518 are [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 521 The test vectors generation can take some time since all the possible triplets (curve, hash function, signature algorithm) are 522 processed with the new curve. 523 524 After 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 541 It 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 554 It 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 561 It 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 566 Finally, 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 569 with explicit parameters given on the command line. Of course, since these curves are already embedded in 570 libecc, there is no real use of generating them - the script is only here to serve as a showcase for expanding 571 the library with explicit parameters. 572 * [scripts/gen_openssl_curves_tests.sh](scripts/gen_openssl_curves_tests.sh): this script enumerates all OpenSSL 573 named curves, generates a DER file with their parameters, and adds them to libecc. 574 575 ### Adding new hash and signature algorithms 576 577 Obviously, adding new algorithms (hash or signature) will require adding new code. 578 579 #### Adding new hash functions 580 We 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 581 algorithm 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 590 These libecc API functions are in fact redirections to the core routines of the hash algorithm, and 591 the user is expected to add the specific implementation in '.c' and '.h' files inside the [src/hash/](src/hash/) 592 folder. See [src/hash/sha224.c](src/hash/sha224.c) and [include/libecc/hash/sha224.h](include/libecc/hash/sha224.h) for a practical 593 example of how to do this with SHA-224. 594 595 Finally, the user is expected to update the libecc main configuration file [include/libecc/lib_ecc_config.h](include/libecc/lib_ecc_config.h) 596 with the `WITH_MY_NEW_HASH` toggle ('my_new_hash' being the new hash function). 597 598 #### Adding new signature algorithms 599 In 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). 601 The signature algorithm should be added in compliance with the API described in the `ec_sig_mapping struct`. This 602 API 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 611 These libecc APIs have to be plugged to the core signature functions, and the user is expected to handle this implementation 612 with 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 614 Finally, the user is expected to update the libecc main configuration file [include/libecc/lib_ecc_config.h](include/libecc/lib_ecc_config.h) 615 with the `WITH_MY_NEW_SIGN_ALG` toggle ('my_new_sign_alg' being the new signature algorithm). 616 617 ## <a name="performance"></a> Performance 618 619 As already stated, libecc has not been designed with performance in mind, but 620 with **simplicity** and **portability** as guiding principles; this implies 621 several 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** 624 routines or the adaptation to CPUs quirks at execution time (e.g. a CPU with very slow shift instructions). [OpenSSL](https://www.openssl.org/) 625 is an example of such libraries with good and homogeneous performance in mind on most heterogeneous platforms (with the lack of 626 portability 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. 628 This means for instance that curves using pseudo-Mersenne primes (such as NIST's SECP curves) won't be faster than 629 curves using generic random primes (such as Brainpool curves), though pseudo-Mersenne primes can benefit from a 630 dedicated 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. 632 Consequently, 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 634 such 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 637 Nonetheless and despite all these elements, **libecc is on par with some other general purpose and portable cryptographic 638 libraries** such as [mbedTLS](https://tls.mbed.org) (see the performance figures given below). 639 640 We present hereafter the ECDSA performance comparison of libecc with mbedTLS and OpenSSL on various platforms representing 641 different 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, 645 a 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 652 a PowerPC architecture. 653 654 For 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 677 IAD (Internet Access Devices), NAS (Network Attached Storage), STB (Set Top Boxes) and smartphones. 678 This 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 680 Cortex-A53 core. This SoC can be found in the Raspberry Pi 3, and also represents what can 681 be found in recent Smartphones. 682 * **Atom D2700** is a small x86 CPU typically embedded in NAS devices. Though its "embedded" 683 coloration, 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 705 The 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 707 chosen WORDSIZE (16, 32, 64), the compilation options (optimization for space `-Os` or speed `-O3`) and the 708 target (depending on the instructions encoding, produced binary code can be more or less compact). 709 A 521-bit curve with SHA-256 hash function and ECDSA signature should fit in 38 Kilo Bytes of flash and around 710 16 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 713 constant data should end up in the flash/EEPROM section with a read only access to them: no RAM memory should 714 be consumed by these. The libecc read/write data are only made of local variables on the stack. Hence, RAM 715 consumption (essentially made of arrays representing internal objects such as numbers, point on curves ...) 716 should 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) 718 can 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 720 is such an example. Compilers and toolchains for such architectures usually copy read only data in RAM at run time, 721 and/or provide [non-standard ways](http://www.atmel.com/webdoc/avrlibcreferencemanual/pgmspace_1pgmspace_strings.html) 722 to access read only data in flash/EEPROM program memory (through specific macros, pragmas, functions). The 723 first case means that the RAM consumption will increase for libecc compared to the stack only usage (because of 724 the runtime copy). The second case means that libecc code will have to be **adapted** to the platform if the user 725 want to keep RAM usage at its lowest. In any case, tracking where `const` qualified data reside will be important 726 when the amount of RAM is a critical matter. 727 728 A 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). 730 It 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, 732 as 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 735 multiplication instruction, the multiplication is implemented using a builtin software function. This yields 736 in poor performance with WORDSIZE=64 compared to WORDSIZE=32 (this might be explained by the calling cost to 737 the 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 747 In order to compare the libecc performance on these embedded platforms, we give figures for mbedTLS on 748 Cortex-M3 taken from a [recent study by ARM](http://csrc.nist.gov/groups/ST/lwc-workshop2015/presentations/session7-vincent.pdf). 749 As we have previously discussed, only the figures without NIST curves specific optimizations are of interest 750 for 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 762 rough lower limit for RAM usage). 763 764 765 ## <a name="compatibility-and-portability"></a> Compatibility and Portability 766 767 ### libecc compatibility 768 769 When dealing with the **portability** of a program across various platforms, many issues are 770 in 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** 775 programming 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 777 include a compiler and a linker, both with possibly specific flags and limitations. 778 779 Regarding 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 782 compatible compiler. The code is **endian neutral**, meaning that libecc should work on little endian 783 and big endian platforms. 784 * The Makefile has been tested with clang and gcc under Linux, as well as gcc cross-compilation variants 785 such as **mingw** for Windows or gcc **Mac OS** version. In order to adapt the makefile behaviour when the 786 compiler 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 788 for 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) 789 header, it is still possible to compile libecc by exporting LIBECC_NOSTDLIB=1: in this case, the code will try to 790 guess 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), 792 an error is thrown at compilation time asking the user to provide implementations for **external dependencies** 793 in [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 801 Some other external dependencies could arise depending on the compilation chain and/or the platform. Such an example is the 802 implementation 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 808 Compiling for Cortex-M targets should be straightforward using the arm-gcc none-eabi (for bare metal) cross-compiler as 809 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 810 the 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 818 where `$(TARGET_OPTS)` are the flags specific to the considered target: `-mcpu=cortex-m3 -mthumb` for Cortex-M3 for example. The word size 819 flag 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 821 containing the `main` calling function, and the linking part will depend on the 822 target platform (in addition to the target CPU): one will use the **linker scripts** provided by the platform/board manufacturer to produce 823 a firmware suitable for the target (ST for STM32, NXP for LPC, Atmel for SAM, ...). 824 825 If the external dependencies have been implemented by the user, it is also possible to build a self-tests binary by adding the 826 GNU 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** 837 so that no stack overflow errors occur. These errors can be tricky to detect since they generally produce hard faults silently at 838 run time. Also, a `SMALLSTACK=1` compilation toggle allows to limit stack consumption further: you can use it carefully if your device 839 does not have enough stack for the regular compilation options (use with care as some side channels countermeasures are deactivated, and this 840 mode 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 843 program size in flash. As already stated, the libc footprint is not included in the figured that have been given in 844 the [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/) 847 configured to use the [ARM compiler](http://www2.keil.com/mdk5/compiler/5/). 848 849 ### <a name="libecc-portability-guide"></a> libecc portability guide 850 851 This section is dedicated to giving some more details on how to compile libecc when non-GNU compilers 852 are used (i.e. C compilers that do not support gcc syntax), and/or when compiling with environments that 853 do not provide a **GNU make** compilation style (this is generally the case for all-in-one IDEs such as 854 Visual Studio or other BSP and SDK provided by proprietary integrated circuits founders and board manufacturers). 855 856 #### 1 - Compilers and C99 standard compliance 857 858 As we have already stated, libecc requires a C99 compiler. More specifically, libecc makes use of 859 only 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 865 Hence, 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**. 867 Such 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 870 big 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 874 to define `static inline` functions. These functions will have to be moved to '.c' files, and one will have to 875 deal with minor adaptations. 876 * The usage of variadic macros is marginal and can be removed with minimal efforts: these are only used 877 to deal with debug helpers in [src/utils](src/utils). 878 879 #### 2 - Compiling with environments without GNU make 880 881 libecc uses a GNU style [Makefile](Makefile) to automate the compilation process. One can however use other 882 compilation 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 914 Compiling binaries (such as `ec_self_tests` and `ec_utils`) is nothing more than compiling concerned '.c' files under [src/tests](src/tests) 915 and linking them with `libsign.a`. 916 917 #### 3 - Dealing with the standard library and stdint 918 919 Some 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 921 detect the best size depending on the platform, but if the platform is not recognized the user is expected to 922 provide 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 925 are used for two things in the project: 926 * Defining standard types through the `stdint.h` header. 927 Though using this header helps libecc to properly define basic types in [include/libecc/words/types.h](include/libecc/words/types.h), it is not 928 required to use it and some heuristics can be used to define these types without standard headers (see explanations on that 929 in [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` 931 flag means that one has to provide these. 932 933 In any case, if the user forgot to provide important preprocessing flags whenever they are necessary, **errors will be thrown** during 934 the 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` 935 not defined), heuristics are used to guess primitive types sizes. These heuristics can fail and the user will have to adapt the types 936 definitions accordingly depending on the platform. 937 938 #### <a name="overloading-makefile-variables"></a> 4 - Overloading Makefile variables 939 940 When compiling using compilers that are not compatible with the gcc syntax, but still using a GNU make 941 compilation environment, it is possible to **adpat the Makefile behavior**. In addition to the `LIBECC_NOSTDLIB=1` 942 environment 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 946 shadow 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 948 the 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 951 As a simple example of when and how to use this environment variables overloading system, let's take the following case: 952 one 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 954 libecc Makefile, an error will be triggered. It is possible to overcome this issue by overloading the `CFLAGS` with 955 the 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 961 As we can see, we keep the other `CFLAGS` from default compilation while replacing `-fstack-protector-strong` with 962 the **less efficient but more compatible** `-fstack-protector-all`. 963 964 In addition to compilation flags, it is also possible to overload the library **word sizes** as well as **debug** 965 modes through Makefile targets: 966 * `make debug` will compile a debug version of the library and binaries, with debugging symbols. 967 Setting 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` 971 flags under gcc). These targets allow cross-compilation for a 32-bit (respectively 64-bit) target under a 64-bit (respectively 972 32-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, 975 a: `CFLAGS="-fstack-protector-all" make debug16` 976 will 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 981 As an example to show how to adapt the compilation process to compilers that are not compatible with the 982 GNU 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 986 other 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 991 We suppose that the user has also provided the **external dependencies** for print, random and time 992 functions (otherwise explicit errors will be thrown by #error directives). 993 994 We will show how overloading the Makefile flags can be of use in this case. Say that we want 995 to compile libecc in order to embed it in a Game Boy ROM. The Game Boy console uses a proprietary 996 version of the Z80 MCU supported by SDCC under the target name `gbz80`. 997 998 Hence, 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 1001 to 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 1005 This 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 1013 As we have explained, when the platform is not recognized one has to specify the word size. We will 1014 do it by overloading `WORDSIZE=16`: the Z80 is an 8-bit CPU, so it seems reasonable to fit the word 1015 size to 16-bit (8-bit half words). The second attempt will go further but will fail at some point when 1016 trying 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 1023 However, one can notice that the static libraries and some object files have been compiled, which is a 1024 first step! Compiling a full binary is a bit technical due to the fact that SDCC does not know how 1025 to deal with '.o' object files and '.a' archives. However, we can find our way out of this by renaming 1026 the 'libsign.a' to 'libsign.lib', and adding missing objects in the library. Compiling the `ec_self_tests` 1027 binary 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)) 1029 as 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` 1031 function. 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 1037 Then, 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 1042 This should create a `ec_self_tests.ihx`, which has an [Intel HEX](https://fr.wikipedia.org/wiki/HEX_(Intel)) 1043 file format for firmware programming. From this file, it is usually straightforward to create a Game Boy ROM file 1044 that can be interpreted by an [emulator](http://m.peponas.free.fr/gngb/) (there are however some quirks related 1045 to 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 1048 compatible with the GNU C one. Consequently, fully porting libecc to the Game Boy platform is left as 1049 a complementary work, and this is not a "so easy" task. Among other things, one will have to deal with 1050 the ROM size limitation of 32KB that can be solved using [bank switching](http://gbdev.gg8.se/wiki/articles/Memory_Bank_Controllers), 1051 which will involve some code and compilation tuning. Another issue would be the RAM size of 8KB and 1052 properly 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 1058 Though **some efforts** have been made to have (most of) the core algorithms 1059 constant time, turning libecc into a library shielded against side channel attacks 1060 is still a **work in progress**. 1061 1062 Beyond pure algorithmic considerations, many aspects of a program can turn 1063 secret leakage resistance into a very complex problem, especially when writing 1064 portable C code. Among other things, we can list the following: 1065 1066 * Low level issues can arise when dealing with heterogeneous platforms (some 1067 instructions 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 1070 branch prediction unit, ...). When dealing with a portable source code 1071 meant to run on most platforms, it is not an easy task to think of all these 1072 leakage sources. 1073 1074 For a thorough discussion about cryptography and constant time challenges, 1075 one can check [this page](https://bearssl.org/constanttime.html). 1076 1077 ### Signature algorithm blinding 1078 1079 In order to avoid a range of attacks on the signature algorithm exploiting various 1080 side 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) 1082 for more details), **blinding** operations can be used. 1083 1084 Since such security countermeasures have a **significant performance hit** on the signature algorithm, we have 1085 decided to leave the activation of such countermeasures as a **voluntary decision** to the end user. 1086 The performance impact might be acceptable or not depending on the context where the signature is performed, and whether attackers exploiting side channels 1087 are indeed considered in the threat model of the specific use case. 1088 Of course, for **security critical use cases we recommend the blinding usage 1089 despite its performance cost**. 1090 1091 Compiling 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 1102 All 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 1106 operations are (tentatively) used to limit leakage of different operations, 1107 even though this task is very complex to achieve (especially in pure C). See 1108 the discussion above. 1109 * DDPA (Data DPA) is thwarted using blinding of the point (projective 1110 coordinates) and of the scalar (with adding a random multiple of the 1111 curve order with maximum entropy). Because of its major impact on 1112 performance, 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 1115 masked variant. See the article "A Practical Countermeasure against 1116 Address-Bit Differential Power Analysis" by Itoh, Izu and Takenaka for more information. 1117 1118 All these countermeasures must, of course, be validated on the specific target 1119 where the library runs with leakage assessments. Because of the very nature of 1120 C code and CPU microarchitectural details, it is very complex without such a leakage 1121 assessment (that again depends on the target) to be sure that SCA protection 1122 is indeed efficient. 1123 1124 ### libecc against FIA (Fault Injection Attacks) 1125 1126 Efforts made to render libecc robust against FIA are a **work in progress**, and 1127 will require **substantial additions**. As for SCA robustness, many elements 1128 might depend on the low-level compilation process and are difficult to handle 1129 at high-level in pure C. 1130 1131 For now, we check if points are on the curve when entering and leaving the 1132 scalar multiplication algorithm, as well as when importing external public points. 1133 Efforts are also made to sanity check the signature and verification contexts whenever possible, 1134 as well as all the intermediate contexts (natural numbers, fields, hash functions, etc.). 1135 1136 Currently, 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 1142 The public header of the libecc API are in the [include/libecc/](include/libecc/) 1143 folder. 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 1193 In addition to the core source code of the library, various resources 1194 are also present in the source tree. We describe them hereafter. 1195 1196 Some self tests are provided for the signature algorithms over all the curves 1197 and using all the hash functions [9], as well as tests targeting arithmetic 1198 operations 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 1214 Some examples to help the user interact with the NN, Fp and cruves layers 1215 are 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 1224 The configuration of the library [13] as well as an external dependencies 1225 abstraction 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 1242 Finally, 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 1248 Here is a big picture of the library architecture summarizing the links 1249 between 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 1289 On the IPECC branch of the libecc repository, there is an integration 1290 with the [IPECC](https://github.com/ANSSI-FR/IPECC) hardware accelerator 1291 project. This project provides hardware acceleration for ECC points operations 1292 (addition, doubling, scalar multiplication, etc.) with advanced SCA countermeasures. 1293 1294 In order to use this accelerator, please follow these steps. First checkout the 1295 IPECC branch: 1296 1297 <pre> 1298 $ git clone https://github.com/libecc/libecc 1299 $ git checkout -b IPECC 1300 </pre> 1301 1302 Then 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 1309 Then, 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 1315 Please note that `USE_EC_HW=1` selects the hardware accelerator (this is mandatory to activate the hardware acceleration backend in libecc), 1316 and `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, 1317 and `USE_EC_HW_SOCKET_EMUL=1` for the socket emulation using the Python server). 1318 We also override the `CC` compiler to `arm-linux-gnueabihf-gcc` for the Zynq platform (adapt at your will depending on your 1319 target), and add some necessary extra CFLAGS for the platform (as well as a `-static` binary compilation to avoid library dependency issues). 1320 Finally, `USE_EC_HW_LOCKING=1` is used here for thread safety during hardware access: this flag is necessary for multi-threading. 1321 1322 libecc has been successfully tested on a [Zynq Arty Z7](https://digilent.com/reference/programmable-logic/arty-z7/start) board with 1323 a **factor 6** performance improvement compared to pure software on the same platform (with SCA countermeasures): 1324 1325 <pre> 1326 az7-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 1334 az7-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