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 */

25 #ifndef BR_BEARSSL_RSA_H__

26 #define BR_BEARSSL_RSA_H__

28 #include <stddef.h>

29 #include <stdint.h>

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 */

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 */

151 /** \brief Modulus. */

153 /** \brief Modulus length (in bytes). */

155 /** \brief Public exponent. */

157 /** \brief Public exponent length (in bytes). */

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 */

171 /** \brief Modulus bit length (in bits, exact value). */

173 /** \brief First prime factor. */

175 /** \brief First prime factor length (in bytes). */

177 /** \brief Second prime factor. */

179 /** \brief Second prime factor length (in bytes). */

181 /** \brief First reduced private exponent. */

183 /** \brief First reduced private exponent length (in bytes). */

185 /** \brief Second reduced private exponent. */

187 /** \brief Second reduced private exponent length (in bytes). */

189 /** \brief CRT coefficient. */

191 /** \brief CRT coefficient length (in bytes). */

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 */

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 */

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 */

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 */

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 */

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 */

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 */

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 */

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 */

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 */

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 */

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 */

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 */

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 */

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 */

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 */

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 */

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 */

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 */

518 /**

519 * \brief RSA decryption helper, for SSL/TLS.

520 *

521 * This function performs the RSA decryption for a RSA-based key exchange

522 * in a SSL/TLS server. The provided RSA engine is used. The `data`

523 * parameter points to the value to decrypt, of length `len` bytes. On

524 * success, the 48-byte pre-master secret is copied into `data`, starting

525 * at the first byte of that buffer; on error, the contents of `data`

526 * become indeterminate.

527 *

528 * This function first checks that the provided value length (`len`) is

529 * not lower than 59 bytes, and matches the RSA modulus length; if neither

530 * of this property is met, then this function returns 0 and the buffer

531 * is unmodified.

532 *

533 * Otherwise, decryption and then padding verification are performed, both

534 * in constant-time. A decryption error, or a bad padding, or an

535 * incorrect decrypted value length are reported with a returned value of

536 * 0; on success, 1 is returned. The caller (SSL server engine) is supposed

537 * to proceed with a random pre-master secret in case of error.

538 *

539 * \param core RSA private key engine.

540 * \param sk RSA private key.

541 * \param data input/output buffer.

542 * \param len length (in bytes) of the data to decrypt.

543 * \return 1 on success, 0 on error.

544 */

548 #endif