_ Git - BearSSL/blob - inc/bearssl_rsa.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_RSA_H__
  26 #define BR_BEARSSL_RSA_H__
  27
  28 #include <stddef.h>
  29 #include <stdint.h>
  30
  31 /** \file bearssl_rsa.h
  32  *
  33  * # RSA
  34  *
  35  * This file documents the RSA implementations provided with BearSSL.
  36  * Note that the SSL engine accesses these implementations through a
  37  * configurable API, so it is possible to, for instance, run a SSL
  38  * server which uses a RSA engine which is not based on this code.
  39  *
  40  * ## Key Elements
  41  *
  42  * RSA public and private keys consist in lists of big integers. All
  43  * such integers are represented with big-endian unsigned notation:
  44  * first byte is the most significant, and the value is positive (so
  45  * there is no dedicated "sign bit"). Public and private key structures
  46  * thus contain, for each such integer, a pointer to the first value byte
  47  * (`unsigned char *`), and a length (`size_t`) which is the number of
  48  * relevant bytes. As a general rule, minimal-length encoding is not
  49  * enforced: values may have extra leading bytes of value 0.
  50  *
  51  * RSA public keys consist in two integers:
  52  *
  53  *   - the modulus (`n`);
  54  *   - the public exponent (`e`).
  55  *
  56  * RSA private keys, as defined in
  57  * [PKCS#1](https://tools.ietf.org/html/rfc3447), contain eight integers:
  58  *
  59  *   - the modulus (`n`);
  60  *   - the public exponent (`e`);
  61  *   - the private exponent (`d`);
  62  *   - the first prime factor (`p`);
  63  *   - the second prime factor (`q`);
  64  *   - the first reduced exponent (`dp`, which is `d` modulo `p-1`);
  65  *   - the second reduced exponent (`dq`, which is `d` modulo `q-1`);
  66  *   - the CRT coefficient (`iq`, the inverse of `q` modulo `p`).
  67  *
  68  * However, the implementations defined in BearSSL use only five of
  69  * these integers: `p`, `q`, `dp`, `dq` and `iq`.
  70  *
  71  * ## Security Features and Limitations
  72  *
  73  * The implementations contained in BearSSL have the following limitations
  74  * and features:
  75  *
  76  *   - They are constant-time. This means that the execution time and
  77  *     memory access pattern may depend on the _lengths_ of the private
  78  *     key components, but not on their value, nor on the value of
  79  *     the operand. Note that this property is not achieved through
  80  *     random masking, but "true" constant-time code.
  81  *
  82  *   - They support only private keys with two prime factors. RSA private
  83  *     key with three or more prime factors are nominally supported, but
  84  *     rarely used; they may offer faster operations, at the expense of
  85  *     more code and potentially a reduction in security if there are
  86  *     "too many" prime factors.
  87  *
  88  *   - The public exponent may have arbitrary length. Of course, it is
  89  *     a good idea to keep public exponents small, so that public key
  90  *     operations are fast; but, contrary to some widely deployed
  91  *     implementations, BearSSL has no problem with public exponent
  92  *     longer than 32 bits.
  93  *
  94  *   - The two prime factors of the modulus need not have the same length
  95  *     (but severely imbalanced factor lengths might reduce security).
  96  *     Similarly, there is no requirement that the first factor (`p`)
  97  *     be greater than the second factor (`q`).
  98  *
  99  *   - Prime factors and modulus must be smaller than a compile-time limit.
 100  *     This is made necessary by the use of fixed-size stack buffers, and
 101  *     the limit has been adjusted to keep stack usage under 2 kB for the
 102  *     RSA operations. Currently, the maximum modulus size is 4096 bits,
 103  *     and the maximum prime factor size is 2080 bits.
 104  *
 105  *   - The RSA functions themselves do not enforce lower size limits,
 106  *     except that which is absolutely necessary for the operation to
 107  *     mathematically make sense (e.g. a PKCS#1 v1.5 signature with
 108  *     SHA-1 requires a modulus of at least 361 bits). It is up to users
 109  *     of this code to enforce size limitations when appropriate (e.g.
 110  *     the X.509 validation engine, by default, rejects RSA keys of
 111  *     less than 1017 bits).
 112  *
 113  *   - Within the size constraints expressed above, arbitrary bit lengths
 114  *     are supported. There is no requirement that prime factors or
 115  *     modulus have a size multiple of 8 or 16.
 116  *
 117  *   - When verifying PKCS#1 v1.5 signatures, both variants of the hash
 118  *     function identifying header (with and without the ASN.1 NULL) are
 119  *     supported. When producing such signatures, the variant with the
 120  *     ASN.1 NULL is used.
 121  *
 122  * ## Implementations
 123  *
 124  * Three RSA implementations are included:
 125  *
 126  *   - The **i32** implementation internally represents big integers
 127  *     as arrays of 32-bit integers. It is perfunctory and portable,
 128  *     but not very efficient.
 129  *
 130  *   - The **i31** implementation uses 32-bit integers, each containing
 131  *     31 bits worth of integer data. The i31 implementation is somewhat
 132  *     faster than the i32 implementation (the reduced integer size makes
 133  *     carry propagation easier) for a similar code footprint, but uses
 134  *     very slightly larger stack buffers (about 4% bigger).
 135  *
 136  *   - The **i15** implementation uses 16-bit integers, each containing
 137  *     15 bits worth of integer data. Multiplication results fit on
 138  *     32 bits, so this won't use the "widening" multiplication routine
 139  *     on ARM Cortex M0/M0+, for much better performance and constant-time
 140  *     execution.
 141  */
 142
 143 /**
 144  * \brief RSA public key.
 145  *
 146  * The structure references the modulus and the public exponent. Both
 147  * integers use unsigned big-endian representation; extra leading bytes
 148  * of value 0 are allowed.
 149  */
 150 typedef struct {
 151         /** \brief Modulus. */
 152         unsigned char *n;
 153         /** \brief Modulus length (in bytes). */
 154         size_t nlen;
 155         /** \brief Public exponent. */
 156         unsigned char *e;
 157         /** \brief Public exponent length (in bytes). */
 158         size_t elen;
 159 } br_rsa_public_key;
 160
 161 /**
 162  * \brief RSA private key.
 163  *
 164  * The structure references the primvate factors, reduced private
 165  * exponents, and CRT coefficient. It also contains the bit length of
 166  * the modulus. The big integers use unsigned big-endian representation;
 167  * extra leading bytes of value 0 are allowed. However, the modulus bit
 168  * length (`n_bitlen`) MUST be exact.
 169  */
 170 typedef struct {
 171         /** \brief Modulus bit length (in bits, exact value). */
 172         uint32_t n_bitlen;
 173         /** \brief First prime factor. */
 174         unsigned char *p;
 175         /** \brief First prime factor length (in bytes). */
 176         size_t plen;
 177         /** \brief Second prime factor. */
 178         unsigned char *q;
 179         /** \brief Second prime factor length (in bytes). */
 180         size_t qlen;
 181         /** \brief First reduced private exponent. */
 182         unsigned char *dp;
 183         /** \brief First reduced private exponent length (in bytes). */
 184         size_t dplen;
 185         /** \brief Second reduced private exponent. */
 186         unsigned char *dq;
 187         /** \brief Second reduced private exponent length (in bytes). */
 188         size_t dqlen;
 189         /** \brief CRT coefficient. */
 190         unsigned char *iq;
 191         /** \brief CRT coefficient length (in bytes). */
 192         size_t iqlen;
 193 } br_rsa_private_key;
 194
 195 /**
 196  * \brief Type for a RSA public key engine.
 197  *
 198  * The public key engine performs the modular exponentiation of the
 199  * provided value with the public exponent. The value is modified in
 200  * place.
 201  *
 202  * The value length (`xlen`) is verified to have _exactly_ the same
 203  * length as the modulus (actual modulus length, without extra leading
 204  * zeros in the modulus representation in memory). If the length does
 205  * not match, then this function returns 0 and `x[]` is unmodified.
 206  *
 207  * It `xlen` is correct, then `x[]` is modified. Returned value is 1
 208  * on success, 0 on error. Error conditions include an oversized `x[]`
 209  * (the array has the same length as the modulus, but the numerical value
 210  * is not lower than the modulus) and an invalid modulus (e.g. an even
 211  * integer). If an error is reported, then the new contents of `x[]` are
 212  * unspecified.
 213  *
 214  * \param x      operand to exponentiate.
 215  * \param xlen   length of the operand (in bytes).
 216  * \param pk     RSA public key.
 217  * \return  1 on success, 0 on error.
 218  */
 219 typedef uint32_t (*br_rsa_public)(unsigned char *x, size_t xlen,
 220         const br_rsa_public_key *pk);
 221
 222 /**
 223  * \brief Type for a RSA signature verification engine (PKCS#1 v1.5).
 224  *
 225  * Parameters are:
 226  *
 227  *   - The signature itself. The provided array is NOT modified.
 228  *
 229  *   - The encoded OID for the hash function. The provided array must begin
 230  *     with a single byte that contains the length of the OID value (in
 231  *     bytes), followed by exactly that many bytes. This parameter may
 232  *     also be `NULL`, in which case the raw hash value should be used
 233  *     with the PKCS#1 v1.5 "type 1" padding (as used in SSL/TLS up
 234  *     to TLS-1.1, with a 36-byte hash value).
 235  *
 236  *   - The hash output length, in bytes.
 237  *
 238  *   - The public key.
 239  *
 240  *   - An output buffer for the hash value. The caller must still compare
 241  *     it with the hash of the data over which the signature is computed.
 242  *
 243  * **Constraints:**
 244  *
 245  *   - Hash length MUST be no more than 64 bytes.
 246  *
 247  *   - OID value length MUST be no more than 32 bytes (i.e. `hash_oid[0]`
 248  *     must have a value in the 0..32 range, inclusive).
 249  *
 250  * This function verifies that the signature length (`xlen`) matches the
 251  * modulus length (this function returns 0 on mismatch). If the modulus
 252  * size exceeds the maximum supported RSA size, then the function also
 253  * returns 0.
 254  *
 255  * Returned value is 1 on success, 0 on error.
 256  *
 257  * Implementations of this type need not be constant-time.
 258  *
 259  * \param x          signature buffer.
 260  * \param xlen       signature length (in bytes).
 261  * \param hash_oid   encoded hash algorithm OID (or `NULL`).
 262  * \param hash_len   expected hash value length (in bytes).
 263  * \param pk         RSA public key.
 264  * \param hash_out   output buffer for the hash value.
 265  * \return  1 on success, 0 on error.
 266  */
 267 typedef uint32_t (*br_rsa_pkcs1_vrfy)(const unsigned char *x, size_t xlen,
 268         const unsigned char *hash_oid, size_t hash_len,
 269         const br_rsa_public_key *pk, unsigned char *hash_out);
 270
 271 /**
 272  * \brief Type for a RSA private key engine.
 273  *
 274  * The `x[]` buffer is modified in place, and its length is inferred from
 275  * the modulus length (`x[]` is assumed to have a length of
 276  * `(sk->n_bitlen+7)/8` bytes).
 277  *
 278  * Returned value is 1 on success, 0 on error.
 279  *
 280  * \param x    operand to exponentiate.
 281  * \param sk   RSA private key.
 282  * \return  1 on success, 0 on error.
 283  */
 284 typedef uint32_t (*br_rsa_private)(unsigned char *x,
 285         const br_rsa_private_key *sk);
 286
 287 /**
 288  * \brief Type for a RSA signature generation engine (PKCS#1 v1.5).
 289  *
 290  * Parameters are:
 291  *
 292  *   - The encoded OID for the hash function. The provided array must begin
 293  *     with a single byte that contains the length of the OID value (in
 294  *     bytes), followed by exactly that many bytes. This parameter may
 295  *     also be `NULL`, in which case the raw hash value should be used
 296  *     with the PKCS#1 v1.5 "type 1" padding (as used in SSL/TLS up
 297  *     to TLS-1.1, with a 36-byte hash value).
 298  *
 299  *   - The hash value computes over the data to sign (its length is
 300  *     expressed in bytes).
 301  *
 302  *   - The RSA private key.
 303  *
 304  *   - The output buffer, that receives the signature.
 305  *
 306  * Returned value is 1 on success, 0 on error. Error conditions include
 307  * a too small modulus for the provided hash OID and value, or some
 308  * invalid key parameters. The signature length is exactly
 309  * `(sk->n_bitlen+7)/8` bytes.
 310  *
 311  * This function is expected to be constant-time with regards to the
 312  * private key bytes (lengths of the modulus and the individual factors
 313  * may leak, though) and to the hashed data.
 314  *
 315  * \param hash_oid   encoded hash algorithm OID (or `NULL`).
 316  * \param hash       hash value.
 317  * \param hash_len   hash value length (in bytes).
 318  * \param sk         RSA private key.
 319  * \param x          output buffer for the signature value.
 320  * \return  1 on success, 0 on error.
 321  */
 322 typedef uint32_t (*br_rsa_pkcs1_sign)(const unsigned char *hash_oid,
 323         const unsigned char *hash, size_t hash_len,
 324         const br_rsa_private_key *sk, unsigned char *x);
 325
 326 /*
 327  * RSA "i32" engine. Integers are internally represented as arrays of
 328  * 32-bit integers, and the core multiplication primitive is the
 329  * 32x32->64 multiplication.
 330  */
 331
 332 /**
 333  * \brief RSA public key engine "i32".
 334  *
 335  * \see br_rsa_public
 336  *
 337  * \param x      operand to exponentiate.
 338  * \param xlen   length of the operand (in bytes).
 339  * \param pk     RSA public key.
 340  * \return  1 on success, 0 on error.
 341  */
 342 uint32_t br_rsa_i32_public(unsigned char *x, size_t xlen,
 343         const br_rsa_public_key *pk);
 344
 345 /**
 346  * \brief RSA signature verification engine "i32".
 347  *
 348  * \see br_rsa_pkcs1_vrfy
 349  *
 350  * \param x          signature buffer.
 351  * \param xlen       signature length (in bytes).
 352  * \param hash_oid   encoded hash algorithm OID (or `NULL`).
 353  * \param hash_len   expected hash value length (in bytes).
 354  * \param pk         RSA public key.
 355  * \param hash_out   output buffer for the hash value.
 356  * \return  1 on success, 0 on error.
 357  */
 358 uint32_t br_rsa_i32_pkcs1_vrfy(const unsigned char *x, size_t xlen,
 359         const unsigned char *hash_oid, size_t hash_len,
 360         const br_rsa_public_key *pk, unsigned char *hash_out);
 361
 362 /**
 363  * \brief RSA private key engine "i32".
 364  *
 365  * \see br_rsa_private
 366  *
 367  * \param x    operand to exponentiate.
 368  * \param sk   RSA private key.
 369  * \return  1 on success, 0 on error.
 370  */
 371 uint32_t br_rsa_i32_private(unsigned char *x,
 372         const br_rsa_private_key *sk);
 373
 374 /**
 375  * \brief RSA signature generation engine "i32".
 376  *
 377  * \see br_rsa_pkcs1_sign
 378  *
 379  * \param hash_oid   encoded hash algorithm OID (or `NULL`).
 380  * \param hash       hash value.
 381  * \param hash_len   hash value length (in bytes).
 382  * \param sk         RSA private key.
 383  * \param x          output buffer for the hash value.
 384  * \return  1 on success, 0 on error.
 385  */
 386 uint32_t br_rsa_i32_pkcs1_sign(const unsigned char *hash_oid,
 387         const unsigned char *hash, size_t hash_len,
 388         const br_rsa_private_key *sk, unsigned char *x);
 389
 390 /*
 391  * RSA "i31" engine. Similar to i32, but only 31 bits are used per 32-bit
 392  * word. This uses slightly more stack space (about 4% more) and code
 393  * space, but it quite faster.
 394  */
 395
 396 /**
 397  * \brief RSA public key engine "i31".
 398  *
 399  * \see br_rsa_public
 400  *
 401  * \param x      operand to exponentiate.
 402  * \param xlen   length of the operand (in bytes).
 403  * \param pk     RSA public key.
 404  * \return  1 on success, 0 on error.
 405  */
 406 uint32_t br_rsa_i31_public(unsigned char *x, size_t xlen,
 407         const br_rsa_public_key *pk);
 408
 409 /**
 410  * \brief RSA signature verification engine "i31".
 411  *
 412  * \see br_rsa_pkcs1_vrfy
 413  *
 414  * \param x          signature buffer.
 415  * \param xlen       signature length (in bytes).
 416  * \param hash_oid   encoded hash algorithm OID (or `NULL`).
 417  * \param hash_len   expected hash value length (in bytes).
 418  * \param pk         RSA public key.
 419  * \param hash_out   output buffer for the hash value.
 420  * \return  1 on success, 0 on error.
 421  */
 422 uint32_t br_rsa_i31_pkcs1_vrfy(const unsigned char *x, size_t xlen,
 423         const unsigned char *hash_oid, size_t hash_len,
 424         const br_rsa_public_key *pk, unsigned char *hash_out);
 425
 426 /**
 427  * \brief RSA private key engine "i31".
 428  *
 429  * \see br_rsa_private
 430  *
 431  * \param x    operand to exponentiate.
 432  * \param sk   RSA private key.
 433  * \return  1 on success, 0 on error.
 434  */
 435 uint32_t br_rsa_i31_private(unsigned char *x,
 436         const br_rsa_private_key *sk);
 437
 438 /**
 439  * \brief RSA signature generation engine "i31".
 440  *
 441  * \see br_rsa_pkcs1_sign
 442  *
 443  * \param hash_oid   encoded hash algorithm OID (or `NULL`).
 444  * \param hash       hash value.
 445  * \param hash_len   hash value length (in bytes).
 446  * \param sk         RSA private key.
 447  * \param x          output buffer for the hash value.
 448  * \return  1 on success, 0 on error.
 449  */
 450 uint32_t br_rsa_i31_pkcs1_sign(const unsigned char *hash_oid,
 451         const unsigned char *hash, size_t hash_len,
 452         const br_rsa_private_key *sk, unsigned char *x);
 453
 454 /*
 455  * RSA "i15" engine. Integers are represented as 15-bit integers, so
 456  * the code uses only 32-bit multiplication (no 64-bit result), which
 457  * is vastly faster (and constant-time) on the ARM Cortex M0/M0+.
 458  */
 459
 460 /**
 461  * \brief RSA public key engine "i15".
 462  *
 463  * \see br_rsa_public
 464  *
 465  * \param x      operand to exponentiate.
 466  * \param xlen   length of the operand (in bytes).
 467  * \param pk     RSA public key.
 468  * \return  1 on success, 0 on error.
 469  */
 470 uint32_t br_rsa_i15_public(unsigned char *x, size_t xlen,
 471         const br_rsa_public_key *pk);
 472
 473 /**
 474  * \brief RSA signature verification engine "i15".
 475  *
 476  * \see br_rsa_pkcs1_vrfy
 477  *
 478  * \param x          signature buffer.
 479  * \param xlen       signature length (in bytes).
 480  * \param hash_oid   encoded hash algorithm OID (or `NULL`).
 481  * \param hash_len   expected hash value length (in bytes).
 482  * \param pk         RSA public key.
 483  * \param hash_out   output buffer for the hash value.
 484  * \return  1 on success, 0 on error.
 485  */
 486 uint32_t br_rsa_i15_pkcs1_vrfy(const unsigned char *x, size_t xlen,
 487         const unsigned char *hash_oid, size_t hash_len,
 488         const br_rsa_public_key *pk, unsigned char *hash_out);
 489
 490 /**
 491  * \brief RSA private key engine "i15".
 492  *
 493  * \see br_rsa_private
 494  *
 495  * \param x    operand to exponentiate.
 496  * \param sk   RSA private key.
 497  * \return  1 on success, 0 on error.
 498  */
 499 uint32_t br_rsa_i15_private(unsigned char *x,
 500         const br_rsa_private_key *sk);
 501
 502 /**
 503  * \brief RSA signature generation engine "i15".
 504  *
 505  * \see br_rsa_pkcs1_sign
 506  *
 507  * \param hash_oid   encoded hash algorithm OID (or `NULL`).
 508  * \param hash       hash value.
 509  * \param hash_len   hash value length (in bytes).
 510  * \param sk         RSA private key.
 511  * \param x          output buffer for the hash value.
 512  * \return  1 on success, 0 on error.
 513  */
 514 uint32_t br_rsa_i15_pkcs1_sign(const unsigned char *hash_oid,
 515         const unsigned char *hash, size_t hash_len,
 516         const br_rsa_private_key *sk, unsigned char *x);
 517
 518 /**
 519  * \brief Get "default" RSA implementation (public-key operations).
 520  *
 521  * This returns the preferred implementation of RSA (public-key operations)
 522  * on the current system.
 523  *
 524  * \return  the default implementation.
 525  */
 526 br_rsa_public br_rsa_public_get_default(void);
 527
 528 /**
 529  * \brief Get "default" RSA implementation (private-key operations).
 530  *
 531  * This returns the preferred implementation of RSA (private-key operations)
 532  * on the current system.
 533  *
 534  * \return  the default implementation.
 535  */
 536 br_rsa_private br_rsa_private_get_default(void);
 537
 538 /**
 539  * \brief Get "default" RSA implementation (PKCS#1 signature verification).
 540  *
 541  * This returns the preferred implementation of RSA (signature verification)
 542  * on the current system.
 543  *
 544  * \return  the default implementation.
 545  */
 546 br_rsa_pkcs1_vrfy br_rsa_pkcs1_vrfy_get_default(void);
 547
 548 /**
 549  * \brief Get "default" RSA implementation (PKCS#1 signature generation).
 550  *
 551  * This returns the preferred implementation of RSA (signature generation)
 552  * on the current system.
 553  *
 554  * \return  the default implementation.
 555  */
 556 br_rsa_pkcs1_sign br_rsa_pkcs1_sign_get_default(void);
 557
 558 /**
 559  * \brief RSA decryption helper, for SSL/TLS.
 560  *
 561  * This function performs the RSA decryption for a RSA-based key exchange
 562  * in a SSL/TLS server. The provided RSA engine is used. The `data`
 563  * parameter points to the value to decrypt, of length `len` bytes. On
 564  * success, the 48-byte pre-master secret is copied into `data`, starting
 565  * at the first byte of that buffer; on error, the contents of `data`
 566  * become indeterminate.
 567  *
 568  * This function first checks that the provided value length (`len`) is
 569  * not lower than 59 bytes, and matches the RSA modulus length; if neither
 570  * of this property is met, then this function returns 0 and the buffer
 571  * is unmodified.
 572  *
 573  * Otherwise, decryption and then padding verification are performed, both
 574  * in constant-time. A decryption error, or a bad padding, or an
 575  * incorrect decrypted value length are reported with a returned value of
 576  * 0; on success, 1 is returned. The caller (SSL server engine) is supposed
 577  * to proceed with a random pre-master secret in case of error.
 578  *
 579  * \param core   RSA private key engine.
 580  * \param sk     RSA private key.
 581  * \param data   input/output buffer.
 582  * \param len    length (in bytes) of the data to decrypt.
 583  * \return  1 on success, 0 on error.
 584  */
 585 uint32_t br_rsa_ssl_decrypt(br_rsa_private core, const br_rsa_private_key *sk,
 586         unsigned char *data, size_t len);
 587
 588 #endif