_ Git - BearSSL/blob - inc/bearssl_ec.h

   1 /*
   2  * Copyright (c) 2016 Thomas Pornin <pornin@bolet.org>
   3  *
   4  * Permission is hereby granted, free of charge, to any person obtaining
   5  * a copy of this software and associated documentation files (the
   6  * "Software"), to deal in the Software without restriction, including
   7  * without limitation the rights to use, copy, modify, merge, publish,
   8  * distribute, sublicense, and/or sell copies of the Software, and to
   9  * permit persons to whom the Software is furnished to do so, subject to
  10  * the following conditions:
  11  *
  12  * The above copyright notice and this permission notice shall be
  13  * included in all copies or substantial portions of the Software.
  14  *
  15  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
  16  * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
  17  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
  18  * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS
  19  * BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN
  20  * ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
  21  * CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
  22  * SOFTWARE.
  23  */
  24
  25 #ifndef BR_BEARSSL_EC_H__
  26 #define BR_BEARSSL_EC_H__
  27
  28 #include <stddef.h>
  29 #include <stdint.h>
  30
  31 /** \file bearssl_ec.h
  32  *
  33  * # Elliptic Curves
  34  *
  35  * This file documents the EC implementations provided with BearSSL, and
  36  * ECDSA.
  37  *
  38  * ## Elliptic Curve API
  39  *
  40  * Only "named curves" are supported. Each EC implementation supports
  41  * one or several named curves, identified by symbolic identifiers.
  42  * These identifiers are small integers, that correspond to the values
  43  * registered by the
  44  * [IANA](http://www.iana.org/assignments/tls-parameters/tls-parameters.xhtml#tls-parameters-8).
  45  *
  46  * Since all currently defined elliptic curve identifiers are in the 0..31
  47  * range, it is convenient to encode support of some curves in a 32-bit
  48  * word, such that bit x corresponds to curve of identifier x.
  49  *
  50  * An EC implementation is incarnated by a `br_ec_impl` instance, that
  51  * offers the following fields:
  52  *
  53  *   - `supported_curves`
  54  *
  55  *      A 32-bit word that documents the identifiers of the curves supported
  56  *      by this implementation.
  57  *
  58  *   - `generator()`
  59  *
  60  *      Callback method that returns a pointer to the conventional generator
  61  *      point for that curve.
  62  *
  63  *   - `order()`
  64  *
  65  *      Callback method that returns a pointer to the subgroup order for
  66  *      that curve. That value uses unsigned big-endian encoding.
  67  *
  68  *   - `mul()`
  69  *
  70  *      Multiply a curve point with an integer.
  71  *
  72  *   - `muladd()`
  73  *
  74  *      Multiply two curve points by two integers, and return the sum of
  75  *      the two products.
  76  *
  77  * All curve points are represented in uncompressed format. The `mul()`
  78  * and `muladd()` methods take care to validate that the provided points
  79  * are really part of the relevant curve subgroup.
  80  *
  81  * For all point multiplication functions, the following holds:
  82  *
  83  *   - Functions validate that the provided points are valid members
  84  *     of the relevant curve subgroup. An error is reported if that is
  85  *     not the case.
  86  *
  87  *   - Processing is constant-time, even if the point operands are not
  88  *     valid. This holds for both the source and resulting points, and
  89  *     the multipliers (integers). Only the byte length of the provided
  90  *     multiplier arrays (not their actual value length in bits) may
  91  *     leak through timing-based side channels.
  92  *
  93  *   - The multipliers (integers) MUST be lower than the subgroup order.
  94  *     If this property is not met, then the result is indeterminate,
  95  *     but an error value is not ncessearily returned.
  96  *
  97  *
  98  * ## ECDSA
  99  *
 100  * ECDSA signatures have two standard formats, called "raw" and "asn1".
 101  * Internally, such a signature is a pair of modular integers `(r,s)`.
 102  * The "raw" format is the concatenation of the unsigned big-endian
 103  * encodings of these two integers, possibly left-padded with zeros so
 104  * that they have the same encoded length. The "asn1" format is the
 105  * DER encoding of an ASN.1 structure that contains the two integer
 106  * values:
 107  *
 108  *     ECDSASignature ::= SEQUENCE {
 109  *         r   INTEGER,
 110  *         s   INTEGER
 111  *     }
 112  *
 113  * In general, in all of X.509 and SSL/TLS, the "asn1" format is used.
 114  * BearSSL offers ECDSA implementations for both formats; conversion
 115  * functions between the two formats are also provided. Conversion of a
 116  * "raw" format signature into "asn1" may enlarge a signature by no more
 117  * than 9 bytes for all supported curves; conversely, conversion of an
 118  * "asn1" signature to "raw" may expand the signature but the "raw"
 119  * length will never be more than twice the length of the "asn1" length
 120  * (and usually it will be shorter).
 121  *
 122  * Note that for a given signature, the "raw" format is not fully
 123  * deterministic, in that it does not enforce a minimal common length.
 124  */
 125
 126 /*
 127  * Standard curve ID. These ID are equal to the assigned numerical
 128  * identifiers assigned to these curves for TLS:
 129  *    http://www.iana.org/assignments/tls-parameters/tls-parameters.xhtml#tls-parameters-8
 130  */
 131
 132 /** \brief Identifier for named curve sect163k1. */
 133 #define BR_EC_sect163k1           1
 134
 135 /** \brief Identifier for named curve sect163r1. */
 136 #define BR_EC_sect163r1           2
 137
 138 /** \brief Identifier for named curve sect163r2. */
 139 #define BR_EC_sect163r2           3
 140
 141 /** \brief Identifier for named curve sect193r1. */
 142 #define BR_EC_sect193r1           4
 143
 144 /** \brief Identifier for named curve sect193r2. */
 145 #define BR_EC_sect193r2           5
 146
 147 /** \brief Identifier for named curve sect233k1. */
 148 #define BR_EC_sect233k1           6
 149
 150 /** \brief Identifier for named curve sect233r1. */
 151 #define BR_EC_sect233r1           7
 152
 153 /** \brief Identifier for named curve sect239k1. */
 154 #define BR_EC_sect239k1           8
 155
 156 /** \brief Identifier for named curve sect283k1. */
 157 #define BR_EC_sect283k1           9
 158
 159 /** \brief Identifier for named curve sect283r1. */
 160 #define BR_EC_sect283r1          10
 161
 162 /** \brief Identifier for named curve sect409k1. */
 163 #define BR_EC_sect409k1          11
 164
 165 /** \brief Identifier for named curve sect409r1. */
 166 #define BR_EC_sect409r1          12
 167
 168 /** \brief Identifier for named curve sect571k1. */
 169 #define BR_EC_sect571k1          13
 170
 171 /** \brief Identifier for named curve sect571r1. */
 172 #define BR_EC_sect571r1          14
 173
 174 /** \brief Identifier for named curve secp160k1. */
 175 #define BR_EC_secp160k1          15
 176
 177 /** \brief Identifier for named curve secp160r1. */
 178 #define BR_EC_secp160r1          16
 179
 180 /** \brief Identifier for named curve secp160r2. */
 181 #define BR_EC_secp160r2          17
 182
 183 /** \brief Identifier for named curve secp192k1. */
 184 #define BR_EC_secp192k1          18
 185
 186 /** \brief Identifier for named curve secp192r1. */
 187 #define BR_EC_secp192r1          19
 188
 189 /** \brief Identifier for named curve secp224k1. */
 190 #define BR_EC_secp224k1          20
 191
 192 /** \brief Identifier for named curve secp224r1. */
 193 #define BR_EC_secp224r1          21
 194
 195 /** \brief Identifier for named curve secp256k1. */
 196 #define BR_EC_secp256k1          22
 197
 198 /** \brief Identifier for named curve secp256r1. */
 199 #define BR_EC_secp256r1          23
 200
 201 /** \brief Identifier for named curve secp384r1. */
 202 #define BR_EC_secp384r1          24
 203
 204 /** \brief Identifier for named curve secp521r1. */
 205 #define BR_EC_secp521r1          25
 206
 207 /** \brief Identifier for named curve brainpoolP256r1. */
 208 #define BR_EC_brainpoolP256r1    26
 209
 210 /** \brief Identifier for named curve brainpoolP384r1. */
 211 #define BR_EC_brainpoolP384r1    27
 212
 213 /** \brief Identifier for named curve brainpoolP512r1. */
 214 #define BR_EC_brainpoolP512r1    28
 215
 216 /**
 217  * \brief Structure for an EC public key.
 218  */
 219 typedef struct {
 220         /** \brief Identifier for the curve used by this key. */
 221         int curve;
 222         /** \brief Public curve point (uncompressed format). */
 223         unsigned char *q;
 224         /** \brief Length of public curve point (in bytes). */
 225         size_t qlen;
 226 } br_ec_public_key;
 227
 228 /**
 229  * \brief Structure for an EC private key.
 230  *
 231  * The private key is an integer modulo the curve subgroup order. The
 232  * encoding below tolerates extra leading zeros. In general, it is
 233  * recommended that the private key has the same length as the curve
 234  * subgroup order.
 235  */
 236 typedef struct {
 237         /** \brief Identifier for the curve used by this key. */
 238         int curve;
 239         /** \brief Private key (integer, unsigned big-endian encoding). */
 240         unsigned char *x;
 241         /** \brief Private key length (in bytes). */
 242         size_t xlen;
 243 } br_ec_private_key;
 244
 245 /**
 246  * \brief Type for an EC implementation.
 247  */
 248 typedef struct {
 249         /**
 250          * \brief Supported curves.
 251          *
 252          * This word is a bitfield: bit `x` is set if the curve of ID `x`
 253          * is supported. E.g. an implementation supporting both NIST P-256
 254          * (secp256r1, ID 23) and NIST P-384 (secp384r1, ID 24) will have
 255          * value `0x01800000` in this field.
 256          */
 257         uint32_t supported_curves;
 258
 259         /**
 260          * \brief Get the conventional generator.
 261          *
 262          * This function returns the conventional generator (encoded
 263          * curve point) for the specified curve. This function MUST NOT
 264          * be called if the curve is not supported.
 265          *
 266          * \param curve   curve identifier.
 267          * \param len     receiver for the encoded generator length (in bytes).
 268          * \return  the encoded generator.
 269          */
 270         const unsigned char *(*generator)(int curve, size_t *len);
 271
 272         /**
 273          * \brief Get the subgroup order.
 274          *
 275          * This function returns the order of the subgroup generated by
 276          * the conventional generator, for the specified curve. Unsigned
 277          * big-endian encoding is used. This function MUST NOT be called
 278          * if the curve is not supported.
 279          *
 280          * \param curve   curve identifier.
 281          * \param len     receiver for the encoded order length (in bytes).
 282          * \return  the encoded order.
 283          */
 284         const unsigned char *(*order)(int curve, size_t *len);
 285
 286         /**
 287          * \brief Multiply a curve point by an integer.
 288          *
 289          * The source point is provided in array `G` (of size `Glen` bytes);
 290          * the multiplication result is written over it. The multiplier
 291          * `x` (of size `xlen` bytes) uses unsigned big-endian encoding.
 292          *
 293          * Rules:
 294          *
 295          *   - The specified curve MUST be supported.
 296          *
 297          *   - The source point must be a valid point on the relevant curve
 298          *     subgroup (and not the "point at infinity" either). If this is
 299          *     not the case, then this function returns an error (0).
 300          *
 301          *   - The multiplier integer MUST be non-zero and less than the
 302          *     curve subgroup order. If the integer is zero, then an
 303          *     error is reported, but if the integer is not lower than
 304          *     the subgroup order, then the result is indeterminate and an
 305          *     error code is not guaranteed.
 306          *
 307          * Returned value is 1 on success, 0 on error. On error, the
 308          * contents of `G` are indeterminate.
 309          *
 310          * \param G       point to multiply.
 311          * \param Glen    length of the encoded point (in bytes).
 312          * \param x       multiplier (unsigned big-endian).
 313          * \param xlen    multiplier length (in bytes).
 314          * \param curve   curve identifier.
 315          * \return  1 on success, 0 on error.
 316          */
 317         uint32_t (*mul)(unsigned char *G, size_t Glen,
 318                 const unsigned char *x, size_t xlen, int curve);
 319
 320         /**
 321          * \brief Multiply two points by two integers and add the
 322          * results.
 323          *
 324          * The point `x*A + y*B` is computed and written back in the `A`
 325          * array.
 326          *
 327          * Rules:
 328          *
 329          *   - The specified curve MUST be supported.
 330          *
 331          *   - The source points (`A` and `B`)  must be valid points on
 332          *     the relevant curve subgroup (and not the "point at
 333          *     infinity" either). If this is not the case, then this
 334          *     function returns an error (0).
 335          *
 336          *   - The multiplier integers (`x` and `y`) MUST be non-zero
 337          *     and less than the curve subgroup order. If either integer
 338          *     is zero, then an error is reported, but if one of them is
 339          *     not lower than the subgroup order, then the result is
 340          *     indeterminate and an error code is not guaranteed.
 341          *
 342          *   - If the final result is the point at infinity, then an
 343          *     error is returned.
 344          *
 345          * Returned value is 1 on success, 0 on error. On error, the
 346          * contents of `A` are indeterminate.
 347          *
 348          * \param A       first point to multiply.
 349          * \param B       second point to multiply.
 350          * \param len     common length of the encoded points (in bytes).
 351          * \param x       multiplier for `A` (unsigned big-endian).
 352          * \param xlen    length of multiplier for `A` (in bytes).
 353          * \param y       multiplier for `A` (unsigned big-endian).
 354          * \param ylen    length of multiplier for `A` (in bytes).
 355          * \param curve   curve identifier.
 356          * \return  1 on success, 0 on error.
 357          */
 358         uint32_t (*muladd)(unsigned char *A, const unsigned char *B, size_t len,
 359                 const unsigned char *x, size_t xlen,
 360                 const unsigned char *y, size_t ylen, int curve);
 361 } br_ec_impl;
 362
 363 /**
 364  * \brief EC implementation "i31".
 365  *
 366  * This implementation internally uses generic code for modular integers,
 367  * with a representation as sequences of 31-bit words. It supports secp256r1,
 368  * secp384r1 and secp521r1 (aka NIST curves P-256, P-384 and P-521).
 369  */
 370 extern const br_ec_impl br_ec_prime_i31;
 371
 372 /**
 373  * \brief EC implementation "i15".
 374  *
 375  * This implementation internally uses generic code for modular integers,
 376  * with a representation as sequences of 15-bit words. It supports secp256r1,
 377  * secp384r1 and secp521r1 (aka NIST curves P-256, P-384 and P-521).
 378  */
 379 extern const br_ec_impl br_ec_prime_i15;
 380
 381 /**
 382  * \brief EC implementation "i15" for P-256.
 383  *
 384  * This implementation uses specialised code for curve secp256r1 (also
 385  * known as NIST P-256), with Karatsuba decomposition, and fast modular
 386  * reduction thanks to the field modulus special format. Only 32-bit
 387  * multiplications are used (with 32-bit results, not 64-bit).
 388  */
 389 extern const br_ec_impl br_ec_p256_i15;
 390
 391 /**
 392  * \brief Convert a signature from "raw" to "asn1".
 393  *
 394  * Conversion is done "in place" and the new length is returned.
 395  * Conversion may enlarge the signature, but by no more than 9 bytes at
 396  * most. On error, 0 is returned (error conditions include an odd raw
 397  * signature length, or an oversized integer).
 398  *
 399  * \param sig       signature to convert.
 400  * \param sig_len   signature length (in bytes).
 401  * \return  the new signature length, or 0 on error.
 402  */
 403 size_t br_ecdsa_raw_to_asn1(void *sig, size_t sig_len);
 404
 405 /**
 406  * \brief Convert a signature from "asn1" to "raw".
 407  *
 408  * Conversion is done "in place" and the new length is returned.
 409  * Conversion may enlarge the signature, but the new signature length
 410  * will be less than twice the source length at most. On error, 0 is
 411  * returned (error conditions include an invalid ASN.1 structure or an
 412  * oversized integer).
 413  *
 414  * \param sig       signature to convert.
 415  * \param sig_len   signature length (in bytes).
 416  * \return  the new signature length, or 0 on error.
 417  */
 418 size_t br_ecdsa_asn1_to_raw(void *sig, size_t sig_len);
 419
 420 /**
 421  * \brief Type for an ECDSA signer function.
 422  *
 423  * A pointer to the EC implementation is provided. The hash value is
 424  * assumed to have the length inferred from the designated hash function
 425  * class.
 426  *
 427  * Signature is written in the buffer pointed to by `sig`, and the length
 428  * (in bytes) is returned. On error, nothing is written in the buffer,
 429  * and 0 is returned. This function returns 0 if the specified curve is
 430  * not supported by the provided EC implementation.
 431  *
 432  * The signature format is either "raw" or "asn1", depending on the
 433  * implementation; maximum length is predictable from the implemented
 434  * curve:
 435  *
 436  * | curve      | raw | asn1 |
 437  * | :--------- | --: | ---: |
 438  * | NIST P-256 |  64 |   72 |
 439  * | NIST P-384 |  96 |  104 |
 440  * | NIST P-521 | 132 |  139 |
 441  *
 442  * \param impl         EC implementation to use.
 443  * \param hf           hash function used to process the data.
 444  * \param hash_value   signed data (hashed).
 445  * \param sk           EC private key.
 446  * \param sig          destination buffer.
 447  * \return  the signature length (in bytes), or 0 on error.
 448  */
 449 typedef size_t (*br_ecdsa_sign)(const br_ec_impl *impl,
 450         const br_hash_class *hf, const void *hash_value,
 451         const br_ec_private_key *sk, void *sig);
 452
 453 /**
 454  * \brief Type for an ECDSA signature verification function.
 455  *
 456  * A pointer to the EC implementation is provided. The hashed value,
 457  * computed over the purportedly signed data, is also provided with
 458  * its length.
 459  *
 460  * The signature format is either "raw" or "asn1", depending on the
 461  * implementation.
 462  *
 463  * Returned value is 1 on success (valid signature), 0 on error. This
 464  * function returns 0 if the specified curve is not supported by the
 465  * provided EC implementation.
 466  *
 467  * \param impl       EC implementation to use.
 468  * \param hash       signed data (hashed).
 469  * \param hash_len   hash value length (in bytes).
 470  * \param pk         EC public key.
 471  * \param sig        signature.
 472  * \param sig_len    signature length (in bytes).
 473  * \return  1 on success, 0 on error.
 474  */
 475 typedef uint32_t (*br_ecdsa_vrfy)(const br_ec_impl *impl,
 476         const void *hash, size_t hash_len,
 477         const br_ec_public_key *pk, const void *sig, size_t sig_len);
 478
 479 /**
 480  * \brief ECDSA signature generator, "i31" implementation, "asn1" format.
 481  *
 482  * \see br_ecdsa_sign()
 483  *
 484  * \param impl         EC implementation to use.
 485  * \param hf           hash function used to process the data.
 486  * \param hash_value   signed data (hashed).
 487  * \param sk           EC private key.
 488  * \param sig          destination buffer.
 489  * \return  the signature length (in bytes), or 0 on error.
 490  */
 491 size_t br_ecdsa_i31_sign_asn1(const br_ec_impl *impl,
 492         const br_hash_class *hf, const void *hash_value,
 493         const br_ec_private_key *sk, void *sig);
 494
 495 /**
 496  * \brief ECDSA signature generator, "i31" implementation, "raw" format.
 497  *
 498  * \see br_ecdsa_sign()
 499  *
 500  * \param impl         EC implementation to use.
 501  * \param hf           hash function used to process the data.
 502  * \param hash_value   signed data (hashed).
 503  * \param sk           EC private key.
 504  * \param sig          destination buffer.
 505  * \return  the signature length (in bytes), or 0 on error.
 506  */
 507 size_t br_ecdsa_i31_sign_raw(const br_ec_impl *impl,
 508         const br_hash_class *hf, const void *hash_value,
 509         const br_ec_private_key *sk, void *sig);
 510
 511 /**
 512  * \brief ECDSA signature verifier, "i31" implementation, "asn1" format.
 513  *
 514  * \see br_ecdsa_vrfy()
 515  *
 516  * \param impl       EC implementation to use.
 517  * \param hash       signed data (hashed).
 518  * \param hash_len   hash value length (in bytes).
 519  * \param pk         EC public key.
 520  * \param sig        signature.
 521  * \param sig_len    signature length (in bytes).
 522  * \return  1 on success, 0 on error.
 523  */
 524 uint32_t br_ecdsa_i31_vrfy_asn1(const br_ec_impl *impl,
 525         const void *hash, size_t hash_len,
 526         const br_ec_public_key *pk, const void *sig, size_t sig_len);
 527
 528 /**
 529  * \brief ECDSA signature verifier, "i31" implementation, "raw" format.
 530  *
 531  * \see br_ecdsa_vrfy()
 532  *
 533  * \param impl       EC implementation to use.
 534  * \param hash       signed data (hashed).
 535  * \param hash_len   hash value length (in bytes).
 536  * \param pk         EC public key.
 537  * \param sig        signature.
 538  * \param sig_len    signature length (in bytes).
 539  * \return  1 on success, 0 on error.
 540  */
 541 uint32_t br_ecdsa_i31_vrfy_raw(const br_ec_impl *impl,
 542         const void *hash, size_t hash_len,
 543         const br_ec_public_key *pk, const void *sig, size_t sig_len);
 544
 545 /**
 546  * \brief ECDSA signature generator, "i15" implementation, "asn1" format.
 547  *
 548  * \see br_ecdsa_sign()
 549  *
 550  * \param impl         EC implementation to use.
 551  * \param hf           hash function used to process the data.
 552  * \param hash_value   signed data (hashed).
 553  * \param sk           EC private key.
 554  * \param sig          destination buffer.
 555  * \return  the signature length (in bytes), or 0 on error.
 556  */
 557 size_t br_ecdsa_i15_sign_asn1(const br_ec_impl *impl,
 558         const br_hash_class *hf, const void *hash_value,
 559         const br_ec_private_key *sk, void *sig);
 560
 561 /**
 562  * \brief ECDSA signature generator, "i15" implementation, "raw" format.
 563  *
 564  * \see br_ecdsa_sign()
 565  *
 566  * \param impl         EC implementation to use.
 567  * \param hf           hash function used to process the data.
 568  * \param hash_value   signed data (hashed).
 569  * \param sk           EC private key.
 570  * \param sig          destination buffer.
 571  * \return  the signature length (in bytes), or 0 on error.
 572  */
 573 size_t br_ecdsa_i15_sign_raw(const br_ec_impl *impl,
 574         const br_hash_class *hf, const void *hash_value,
 575         const br_ec_private_key *sk, void *sig);
 576
 577 /**
 578  * \brief ECDSA signature verifier, "i15" implementation, "asn1" format.
 579  *
 580  * \see br_ecdsa_vrfy()
 581  *
 582  * \param impl       EC implementation to use.
 583  * \param hash       signed data (hashed).
 584  * \param hash_len   hash value length (in bytes).
 585  * \param pk         EC public key.
 586  * \param sig        signature.
 587  * \param sig_len    signature length (in bytes).
 588  * \return  1 on success, 0 on error.
 589  */
 590 uint32_t br_ecdsa_i15_vrfy_asn1(const br_ec_impl *impl,
 591         const void *hash, size_t hash_len,
 592         const br_ec_public_key *pk, const void *sig, size_t sig_len);
 593
 594 /**
 595  * \brief ECDSA signature verifier, "i15" implementation, "raw" format.
 596  *
 597  * \see br_ecdsa_vrfy()
 598  *
 599  * \param impl       EC implementation to use.
 600  * \param hash       signed data (hashed).
 601  * \param hash_len   hash value length (in bytes).
 602  * \param pk         EC public key.
 603  * \param sig        signature.
 604  * \param sig_len    signature length (in bytes).
 605  * \return  1 on success, 0 on error.
 606  */
 607 uint32_t br_ecdsa_i15_vrfy_raw(const br_ec_impl *impl,
 608         const void *hash, size_t hash_len,
 609         const br_ec_public_key *pk, const void *sig, size_t sig_len);
 610
 611 #endif