dsa_ossl.c 15 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502
  1. /*
  2. * Copyright 1995-2023 The OpenSSL Project Authors. All Rights Reserved.
  3. *
  4. * Licensed under the Apache License 2.0 (the "License"). You may not use
  5. * this file except in compliance with the License. You can obtain a copy
  6. * in the file LICENSE in the source distribution or at
  7. * https://www.openssl.org/source/license.html
  8. */
  9. /*
  10. * DSA low level APIs are deprecated for public use, but still ok for
  11. * internal use.
  12. */
  13. #include "internal/deprecated.h"
  14. #include <stdio.h>
  15. #include "internal/cryptlib.h"
  16. #include "crypto/bn.h"
  17. #include <openssl/bn.h>
  18. #include <openssl/sha.h>
  19. #include "dsa_local.h"
  20. #include <openssl/asn1.h>
  21. #include "internal/deterministic_nonce.h"
  22. #define MIN_DSA_SIGN_QBITS 128
  23. #define MAX_DSA_SIGN_RETRIES 8
  24. static DSA_SIG *dsa_do_sign(const unsigned char *dgst, int dlen, DSA *dsa);
  25. static int dsa_sign_setup_no_digest(DSA *dsa, BN_CTX *ctx_in, BIGNUM **kinvp,
  26. BIGNUM **rp);
  27. static int dsa_sign_setup(DSA *dsa, BN_CTX *ctx_in, BIGNUM **kinvp,
  28. BIGNUM **rp, const unsigned char *dgst, int dlen,
  29. unsigned int nonce_type, const char *digestname,
  30. OSSL_LIB_CTX *libctx, const char *propq);
  31. static int dsa_do_verify(const unsigned char *dgst, int dgst_len,
  32. DSA_SIG *sig, DSA *dsa);
  33. static int dsa_init(DSA *dsa);
  34. static int dsa_finish(DSA *dsa);
  35. static BIGNUM *dsa_mod_inverse_fermat(const BIGNUM *k, const BIGNUM *q,
  36. BN_CTX *ctx);
  37. static DSA_METHOD openssl_dsa_meth = {
  38. "OpenSSL DSA method",
  39. dsa_do_sign,
  40. dsa_sign_setup_no_digest,
  41. dsa_do_verify,
  42. NULL, /* dsa_mod_exp, */
  43. NULL, /* dsa_bn_mod_exp, */
  44. dsa_init,
  45. dsa_finish,
  46. DSA_FLAG_FIPS_METHOD,
  47. NULL,
  48. NULL,
  49. NULL
  50. };
  51. static const DSA_METHOD *default_DSA_method = &openssl_dsa_meth;
  52. #ifndef FIPS_MODULE
  53. void DSA_set_default_method(const DSA_METHOD *meth)
  54. {
  55. default_DSA_method = meth;
  56. }
  57. #endif /* FIPS_MODULE */
  58. const DSA_METHOD *DSA_get_default_method(void)
  59. {
  60. return default_DSA_method;
  61. }
  62. const DSA_METHOD *DSA_OpenSSL(void)
  63. {
  64. return &openssl_dsa_meth;
  65. }
  66. DSA_SIG *ossl_dsa_do_sign_int(const unsigned char *dgst, int dlen, DSA *dsa,
  67. unsigned int nonce_type, const char *digestname,
  68. OSSL_LIB_CTX *libctx, const char *propq)
  69. {
  70. BIGNUM *kinv = NULL;
  71. BIGNUM *m, *blind, *blindm, *tmp;
  72. BN_CTX *ctx = NULL;
  73. int reason = ERR_R_BN_LIB;
  74. DSA_SIG *ret = NULL;
  75. int rv = 0;
  76. int retries = 0;
  77. if (dsa->params.p == NULL
  78. || dsa->params.q == NULL
  79. || dsa->params.g == NULL) {
  80. reason = DSA_R_MISSING_PARAMETERS;
  81. goto err;
  82. }
  83. if (dsa->priv_key == NULL) {
  84. reason = DSA_R_MISSING_PRIVATE_KEY;
  85. goto err;
  86. }
  87. ret = DSA_SIG_new();
  88. if (ret == NULL)
  89. goto err;
  90. ret->r = BN_new();
  91. ret->s = BN_new();
  92. if (ret->r == NULL || ret->s == NULL)
  93. goto err;
  94. ctx = BN_CTX_new_ex(dsa->libctx);
  95. if (ctx == NULL)
  96. goto err;
  97. m = BN_CTX_get(ctx);
  98. blind = BN_CTX_get(ctx);
  99. blindm = BN_CTX_get(ctx);
  100. tmp = BN_CTX_get(ctx);
  101. if (tmp == NULL)
  102. goto err;
  103. redo:
  104. if (!dsa_sign_setup(dsa, ctx, &kinv, &ret->r, dgst, dlen,
  105. nonce_type, digestname, libctx, propq))
  106. goto err;
  107. if (dlen > BN_num_bytes(dsa->params.q))
  108. /*
  109. * if the digest length is greater than the size of q use the
  110. * BN_num_bits(dsa->q) leftmost bits of the digest, see fips 186-3,
  111. * 4.2
  112. */
  113. dlen = BN_num_bytes(dsa->params.q);
  114. if (BN_bin2bn(dgst, dlen, m) == NULL)
  115. goto err;
  116. /*
  117. * The normal signature calculation is:
  118. *
  119. * s := k^-1 * (m + r * priv_key) mod q
  120. *
  121. * We will blind this to protect against side channel attacks
  122. *
  123. * s := blind^-1 * k^-1 * (blind * m + blind * r * priv_key) mod q
  124. */
  125. /*
  126. * Generate a blinding value
  127. * The size of q is tested in dsa_sign_setup() so there should not be an infinite loop here.
  128. */
  129. do {
  130. if (!BN_priv_rand_ex(blind, BN_num_bits(dsa->params.q) - 1,
  131. BN_RAND_TOP_ANY, BN_RAND_BOTTOM_ANY, 0, ctx))
  132. goto err;
  133. } while (BN_is_zero(blind));
  134. BN_set_flags(blind, BN_FLG_CONSTTIME);
  135. BN_set_flags(blindm, BN_FLG_CONSTTIME);
  136. BN_set_flags(tmp, BN_FLG_CONSTTIME);
  137. /* tmp := blind * priv_key * r mod q */
  138. if (!BN_mod_mul(tmp, blind, dsa->priv_key, dsa->params.q, ctx))
  139. goto err;
  140. if (!BN_mod_mul(tmp, tmp, ret->r, dsa->params.q, ctx))
  141. goto err;
  142. /* blindm := blind * m mod q */
  143. if (!BN_mod_mul(blindm, blind, m, dsa->params.q, ctx))
  144. goto err;
  145. /* s : = (blind * priv_key * r) + (blind * m) mod q */
  146. if (!BN_mod_add_quick(ret->s, tmp, blindm, dsa->params.q))
  147. goto err;
  148. /* s := s * k^-1 mod q */
  149. if (!BN_mod_mul(ret->s, ret->s, kinv, dsa->params.q, ctx))
  150. goto err;
  151. /* s:= s * blind^-1 mod q */
  152. if (BN_mod_inverse(blind, blind, dsa->params.q, ctx) == NULL)
  153. goto err;
  154. if (!BN_mod_mul(ret->s, ret->s, blind, dsa->params.q, ctx))
  155. goto err;
  156. /*
  157. * Redo if r or s is zero as required by FIPS 186-4: Section 4.6
  158. * This is very unlikely.
  159. * Limit the retries so there is no possibility of an infinite
  160. * loop for bad domain parameter values.
  161. */
  162. if (BN_is_zero(ret->r) || BN_is_zero(ret->s)) {
  163. if (retries++ > MAX_DSA_SIGN_RETRIES) {
  164. reason = DSA_R_TOO_MANY_RETRIES;
  165. goto err;
  166. }
  167. goto redo;
  168. }
  169. rv = 1;
  170. err:
  171. if (rv == 0) {
  172. ERR_raise(ERR_LIB_DSA, reason);
  173. DSA_SIG_free(ret);
  174. ret = NULL;
  175. }
  176. BN_CTX_free(ctx);
  177. BN_clear_free(kinv);
  178. return ret;
  179. }
  180. static DSA_SIG *dsa_do_sign(const unsigned char *dgst, int dlen, DSA *dsa)
  181. {
  182. return ossl_dsa_do_sign_int(dgst, dlen, dsa,
  183. 0, NULL, NULL, NULL);
  184. }
  185. static int dsa_sign_setup_no_digest(DSA *dsa, BN_CTX *ctx_in,
  186. BIGNUM **kinvp, BIGNUM **rp)
  187. {
  188. return dsa_sign_setup(dsa, ctx_in, kinvp, rp, NULL, 0,
  189. 0, NULL, NULL, NULL);
  190. }
  191. static int dsa_sign_setup(DSA *dsa, BN_CTX *ctx_in,
  192. BIGNUM **kinvp, BIGNUM **rp,
  193. const unsigned char *dgst, int dlen,
  194. unsigned int nonce_type, const char *digestname,
  195. OSSL_LIB_CTX *libctx, const char *propq)
  196. {
  197. BN_CTX *ctx = NULL;
  198. BIGNUM *k, *kinv = NULL, *r = *rp;
  199. BIGNUM *l;
  200. int ret = 0;
  201. int q_bits, q_words;
  202. if (!dsa->params.p || !dsa->params.q || !dsa->params.g) {
  203. ERR_raise(ERR_LIB_DSA, DSA_R_MISSING_PARAMETERS);
  204. return 0;
  205. }
  206. /* Reject obviously invalid parameters */
  207. if (BN_is_zero(dsa->params.p)
  208. || BN_is_zero(dsa->params.q)
  209. || BN_is_zero(dsa->params.g)
  210. || BN_is_negative(dsa->params.p)
  211. || BN_is_negative(dsa->params.q)
  212. || BN_is_negative(dsa->params.g)) {
  213. ERR_raise(ERR_LIB_DSA, DSA_R_INVALID_PARAMETERS);
  214. return 0;
  215. }
  216. if (dsa->priv_key == NULL) {
  217. ERR_raise(ERR_LIB_DSA, DSA_R_MISSING_PRIVATE_KEY);
  218. return 0;
  219. }
  220. k = BN_new();
  221. l = BN_new();
  222. if (k == NULL || l == NULL)
  223. goto err;
  224. if (ctx_in == NULL) {
  225. /* if you don't pass in ctx_in you get a default libctx */
  226. if ((ctx = BN_CTX_new_ex(NULL)) == NULL)
  227. goto err;
  228. } else
  229. ctx = ctx_in;
  230. /* Preallocate space */
  231. q_bits = BN_num_bits(dsa->params.q);
  232. q_words = bn_get_top(dsa->params.q);
  233. if (q_bits < MIN_DSA_SIGN_QBITS
  234. || !bn_wexpand(k, q_words + 2)
  235. || !bn_wexpand(l, q_words + 2))
  236. goto err;
  237. /* Get random k */
  238. do {
  239. if (dgst != NULL) {
  240. if (nonce_type == 1) {
  241. #ifndef FIPS_MODULE
  242. if (!ossl_gen_deterministic_nonce_rfc6979(k, dsa->params.q,
  243. dsa->priv_key,
  244. dgst, dlen,
  245. digestname,
  246. libctx, propq))
  247. #endif
  248. goto err;
  249. } else {
  250. /*
  251. * We calculate k from SHA512(private_key + H(message) + random).
  252. * This protects the private key from a weak PRNG.
  253. */
  254. if (!BN_generate_dsa_nonce(k, dsa->params.q, dsa->priv_key, dgst,
  255. dlen, ctx))
  256. goto err;
  257. }
  258. } else if (!BN_priv_rand_range_ex(k, dsa->params.q, 0, ctx))
  259. goto err;
  260. } while (BN_is_zero(k));
  261. BN_set_flags(k, BN_FLG_CONSTTIME);
  262. BN_set_flags(l, BN_FLG_CONSTTIME);
  263. if (dsa->flags & DSA_FLAG_CACHE_MONT_P) {
  264. if (!BN_MONT_CTX_set_locked(&dsa->method_mont_p,
  265. dsa->lock, dsa->params.p, ctx))
  266. goto err;
  267. }
  268. /* Compute r = (g^k mod p) mod q */
  269. /*
  270. * We do not want timing information to leak the length of k, so we
  271. * compute G^k using an equivalent scalar of fixed bit-length.
  272. *
  273. * We unconditionally perform both of these additions to prevent a
  274. * small timing information leakage. We then choose the sum that is
  275. * one bit longer than the modulus.
  276. *
  277. * There are some concerns about the efficacy of doing this. More
  278. * specifically refer to the discussion starting with:
  279. * https://github.com/openssl/openssl/pull/7486#discussion_r228323705
  280. * The fix is to rework BN so these gymnastics aren't required.
  281. */
  282. if (!BN_add(l, k, dsa->params.q)
  283. || !BN_add(k, l, dsa->params.q))
  284. goto err;
  285. BN_consttime_swap(BN_is_bit_set(l, q_bits), k, l, q_words + 2);
  286. if ((dsa)->meth->bn_mod_exp != NULL) {
  287. if (!dsa->meth->bn_mod_exp(dsa, r, dsa->params.g, k, dsa->params.p,
  288. ctx, dsa->method_mont_p))
  289. goto err;
  290. } else {
  291. if (!BN_mod_exp_mont(r, dsa->params.g, k, dsa->params.p, ctx,
  292. dsa->method_mont_p))
  293. goto err;
  294. }
  295. if (!BN_mod(r, r, dsa->params.q, ctx))
  296. goto err;
  297. /* Compute part of 's = inv(k) (m + xr) mod q' */
  298. if ((kinv = dsa_mod_inverse_fermat(k, dsa->params.q, ctx)) == NULL)
  299. goto err;
  300. BN_clear_free(*kinvp);
  301. *kinvp = kinv;
  302. kinv = NULL;
  303. ret = 1;
  304. err:
  305. if (!ret)
  306. ERR_raise(ERR_LIB_DSA, ERR_R_BN_LIB);
  307. if (ctx != ctx_in)
  308. BN_CTX_free(ctx);
  309. BN_clear_free(k);
  310. BN_clear_free(l);
  311. return ret;
  312. }
  313. static int dsa_do_verify(const unsigned char *dgst, int dgst_len,
  314. DSA_SIG *sig, DSA *dsa)
  315. {
  316. BN_CTX *ctx;
  317. BIGNUM *u1, *u2, *t1;
  318. BN_MONT_CTX *mont = NULL;
  319. const BIGNUM *r, *s;
  320. int ret = -1, i;
  321. if (dsa->params.p == NULL
  322. || dsa->params.q == NULL
  323. || dsa->params.g == NULL) {
  324. ERR_raise(ERR_LIB_DSA, DSA_R_MISSING_PARAMETERS);
  325. return -1;
  326. }
  327. i = BN_num_bits(dsa->params.q);
  328. /* fips 186-3 allows only different sizes for q */
  329. if (i != 160 && i != 224 && i != 256) {
  330. ERR_raise(ERR_LIB_DSA, DSA_R_BAD_Q_VALUE);
  331. return -1;
  332. }
  333. if (BN_num_bits(dsa->params.p) > OPENSSL_DSA_MAX_MODULUS_BITS) {
  334. ERR_raise(ERR_LIB_DSA, DSA_R_MODULUS_TOO_LARGE);
  335. return -1;
  336. }
  337. u1 = BN_new();
  338. u2 = BN_new();
  339. t1 = BN_new();
  340. ctx = BN_CTX_new_ex(NULL); /* verify does not need a libctx */
  341. if (u1 == NULL || u2 == NULL || t1 == NULL || ctx == NULL)
  342. goto err;
  343. DSA_SIG_get0(sig, &r, &s);
  344. if (BN_is_zero(r) || BN_is_negative(r) ||
  345. BN_ucmp(r, dsa->params.q) >= 0) {
  346. ret = 0;
  347. goto err;
  348. }
  349. if (BN_is_zero(s) || BN_is_negative(s) ||
  350. BN_ucmp(s, dsa->params.q) >= 0) {
  351. ret = 0;
  352. goto err;
  353. }
  354. /*
  355. * Calculate W = inv(S) mod Q save W in u2
  356. */
  357. if ((BN_mod_inverse(u2, s, dsa->params.q, ctx)) == NULL)
  358. goto err;
  359. /* save M in u1 */
  360. if (dgst_len > (i >> 3))
  361. /*
  362. * if the digest length is greater than the size of q use the
  363. * BN_num_bits(dsa->q) leftmost bits of the digest, see fips 186-3,
  364. * 4.2
  365. */
  366. dgst_len = (i >> 3);
  367. if (BN_bin2bn(dgst, dgst_len, u1) == NULL)
  368. goto err;
  369. /* u1 = M * w mod q */
  370. if (!BN_mod_mul(u1, u1, u2, dsa->params.q, ctx))
  371. goto err;
  372. /* u2 = r * w mod q */
  373. if (!BN_mod_mul(u2, r, u2, dsa->params.q, ctx))
  374. goto err;
  375. if (dsa->flags & DSA_FLAG_CACHE_MONT_P) {
  376. mont = BN_MONT_CTX_set_locked(&dsa->method_mont_p,
  377. dsa->lock, dsa->params.p, ctx);
  378. if (!mont)
  379. goto err;
  380. }
  381. if (dsa->meth->dsa_mod_exp != NULL) {
  382. if (!dsa->meth->dsa_mod_exp(dsa, t1, dsa->params.g, u1, dsa->pub_key, u2,
  383. dsa->params.p, ctx, mont))
  384. goto err;
  385. } else {
  386. if (!BN_mod_exp2_mont(t1, dsa->params.g, u1, dsa->pub_key, u2,
  387. dsa->params.p, ctx, mont))
  388. goto err;
  389. }
  390. /* let u1 = u1 mod q */
  391. if (!BN_mod(u1, t1, dsa->params.q, ctx))
  392. goto err;
  393. /*
  394. * V is now in u1. If the signature is correct, it will be equal to R.
  395. */
  396. ret = (BN_ucmp(u1, r) == 0);
  397. err:
  398. if (ret < 0)
  399. ERR_raise(ERR_LIB_DSA, ERR_R_BN_LIB);
  400. BN_CTX_free(ctx);
  401. BN_free(u1);
  402. BN_free(u2);
  403. BN_free(t1);
  404. return ret;
  405. }
  406. static int dsa_init(DSA *dsa)
  407. {
  408. dsa->flags |= DSA_FLAG_CACHE_MONT_P;
  409. ossl_ffc_params_init(&dsa->params);
  410. dsa->dirty_cnt++;
  411. return 1;
  412. }
  413. static int dsa_finish(DSA *dsa)
  414. {
  415. BN_MONT_CTX_free(dsa->method_mont_p);
  416. return 1;
  417. }
  418. /*
  419. * Compute the inverse of k modulo q.
  420. * Since q is prime, Fermat's Little Theorem applies, which reduces this to
  421. * mod-exp operation. Both the exponent and modulus are public information
  422. * so a mod-exp that doesn't leak the base is sufficient. A newly allocated
  423. * BIGNUM is returned which the caller must free.
  424. */
  425. static BIGNUM *dsa_mod_inverse_fermat(const BIGNUM *k, const BIGNUM *q,
  426. BN_CTX *ctx)
  427. {
  428. BIGNUM *res = NULL;
  429. BIGNUM *r, *e;
  430. if ((r = BN_new()) == NULL)
  431. return NULL;
  432. BN_CTX_start(ctx);
  433. if ((e = BN_CTX_get(ctx)) != NULL
  434. && BN_set_word(r, 2)
  435. && BN_sub(e, q, r)
  436. && BN_mod_exp_mont(r, k, e, q, ctx, NULL))
  437. res = r;
  438. else
  439. BN_free(r);
  440. BN_CTX_end(ctx);
  441. return res;
  442. }