rfc6979.c 13 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360
  1. /*
  2. * Code to generate 'nonce' values for DSA signature algorithms, in a
  3. * deterministic way.
  4. */
  5. #include "ssh.h"
  6. #include "mpint.h"
  7. #include "misc.h"
  8. /*
  9. * All DSA-type signature systems depend on a nonce - a random number
  10. * generated during the signing operation.
  11. *
  12. * This nonce is a weak point of DSA and needs careful protection,
  13. * for multiple reasons:
  14. *
  15. * 1. If an attacker in possession of your public key and a single
  16. * signature can find out or guess the nonce you used in that
  17. * signature, they can immediately recover your _private key_.
  18. *
  19. * 2. If you reuse the same nonce in two different signatures, this
  20. * will be instantly obvious to the attacker (one of the two
  21. * values making up the signature will match), and again, they can
  22. * immediately recover the private key as soon as they notice this.
  23. *
  24. * 3. In at least one system, information about your private key is
  25. * leaked merely by generating nonces with a significant bias.
  26. *
  27. * Attacks #1 and #2 work across all of integer DSA, NIST-style ECDSA,
  28. * and EdDSA. The details vary, but the headline effects are the same.
  29. *
  30. * So we must be very careful with our nonces. They must be generated
  31. * with uniform distribution, but also, they must avoid depending on
  32. * any random number generator that has the slightest doubt about its
  33. * reliability.
  34. *
  35. * In particular, PuTTY's policy is that for this purpose we don't
  36. * _even_ trust the PRNG we use for other cryptography. This is mostly
  37. * a concern because of Windows, where system entropy sources are
  38. * limited and we have doubts about their trustworthiness
  39. * - even CryptGenRandom. PuTTY compensates as best it can with its
  40. * own ongoing entropy collection, and we trust that for session keys,
  41. * but revealing the private key that goes with a long-term public key
  42. * is a far worse outcome than revealing one SSH session key, and for
  43. * keeping your private key safe, we don't think the available Windows
  44. * entropy gives us enough confidence.
  45. *
  46. * A common strategy these days (although <hipster>PuTTY was doing it
  47. * before it was cool</hipster>) is to avoid using a PRNG based on
  48. * system entropy at all. Instead, you use a deterministic PRNG that
  49. * starts from a fixed input seed, and in that input seed you include
  50. * the message to be signed and the _private key_.
  51. *
  52. * Including the private key in the seed is counterintuitive, but does
  53. * actually make sense. A deterministic nonce generation strategy must
  54. * use _some_ piece of input that the attacker doesn't have, or else
  55. * they'd be able to repeat the entire computation and construct the
  56. * same nonce you did. And the one thing they don't know is the
  57. * private key! So we include that in the seed data (under enough
  58. * layers of overcautious hashing to protect it against exposure), and
  59. * then they _can't_ repeat the same construction. Moreover, if they
  60. * _could_, they'd already know the private key, so they wouldn't need
  61. * to perform an attack of this kind at all!
  62. *
  63. * (This trick doesn't, _per se_, protect against reuse of nonces.
  64. * That is left to chance, which is enough, because the space of
  65. * nonces is large enough to make it adequately unlikely. But it
  66. * avoids escalating the reuse risk due to inadequate entropy.)
  67. *
  68. * For integer DSA and ECDSA, the system we use for deterministic
  69. * generation of k is exactly the one specified in RFC 6979. We
  70. * switched to this from the old system that PuTTY used to use before
  71. * that RFC came out. The old system had a critical bug: it did not
  72. * always generate _enough_ data to get uniform distribution, because
  73. * its output was a single SHA-512 hash. We could have fixed that
  74. * minimally, by concatenating multiple hashes, but it seemed more
  75. * sensible to switch to a system that comes with test vectors.
  76. *
  77. * One downside of RFC 6979 is that it's based on rejection sampling
  78. * (that is, you generate a random number and keep retrying until it's
  79. * in range). This makes it play badly with our side-channel test
  80. * system, which wants every execution trace of a supposedly
  81. * constant-time operation to be the same. To work around this
  82. * awkwardness, we break up the algorithm further, into a setup phase
  83. * and an 'attempt to generate an output' phase, each of which is
  84. * individually constant-time.
  85. */
  86. struct RFC6979 {
  87. /*
  88. * Size of the cyclic group over which we're doing DSA.
  89. * Equivalently, the multiplicative order of g (for integer DSA)
  90. * or the curve's base point (for ECDSA). For integer DSA this is
  91. * also the same thing as the small prime q from the key
  92. * parameters.
  93. *
  94. * This pointer is not owned. Freeing this structure will not free
  95. * it, and freeing the pointed-to integer before freeing this
  96. * structure will make this structure dangerous to use.
  97. */
  98. mp_int *q;
  99. /*
  100. * The private key integer, which is always the discrete log of
  101. * the public key with respect to the group generator.
  102. *
  103. * This pointer is not owned. Freeing this structure will not free
  104. * it, and freeing the pointed-to integer before freeing this
  105. * structure will make this structure dangerous to use.
  106. */
  107. mp_int *x;
  108. /*
  109. * Cached values derived from q: its length in bits, and in bytes.
  110. */
  111. size_t qbits, qbytes;
  112. /*
  113. * Reusable hash and MAC objects.
  114. */
  115. ssh_hash *hash;
  116. ssh2_mac *mac;
  117. /*
  118. * Cached value: the output length of the hash.
  119. */
  120. size_t hlen;
  121. /*
  122. * The byte string V used in the algorithm.
  123. */
  124. unsigned char V[MAX_HASH_LEN];
  125. /*
  126. * The string T to use during each attempt, and how many
  127. * hash-sized blocks to fill it with.
  128. */
  129. size_t T_nblocks;
  130. unsigned char *T;
  131. };
  132. static mp_int *bits2int(ptrlen b, RFC6979 *s)
  133. {
  134. if (b.len > s->qbytes)
  135. b.len = s->qbytes;
  136. mp_int *x = mp_from_bytes_be(b);
  137. /*
  138. * Rationale for using mp_rshift_fixed_into and not
  139. * mp_rshift_safe_into: the shift count is derived from the
  140. * difference between the length of the modulus q, and the length
  141. * of the input bit string, i.e. between the _sizes_ of things
  142. * involved in the protocol. But the sizes aren't secret. Only the
  143. * actual values of integers and bit strings of those sizes are
  144. * secret. So it's OK for the shift count to be known to an
  145. * attacker - they'd know it anyway just from which DSA algorithm
  146. * we were using.
  147. */
  148. if (b.len * 8 > s->qbits)
  149. mp_rshift_fixed_into(x, x, b.len * 8 - s->qbits);
  150. return x;
  151. }
  152. static void BinarySink_put_int2octets(BinarySink *bs, mp_int *x, RFC6979 *s)
  153. {
  154. mp_int *x_mod_q = mp_mod(x, s->q);
  155. for (size_t i = s->qbytes; i-- > 0 ;)
  156. put_byte(bs, mp_get_byte(x_mod_q, i));
  157. mp_free(x_mod_q);
  158. }
  159. static void BinarySink_put_bits2octets(BinarySink *bs, ptrlen b, RFC6979 *s)
  160. {
  161. mp_int *x = bits2int(b, s);
  162. BinarySink_put_int2octets(bs, x, s);
  163. mp_free(x);
  164. }
  165. #define put_int2octets(bs, x, s) \
  166. BinarySink_put_int2octets(BinarySink_UPCAST(bs), x, s)
  167. #define put_bits2octets(bs, b, s) \
  168. BinarySink_put_bits2octets(BinarySink_UPCAST(bs), b, s)
  169. RFC6979 *rfc6979_new(const ssh_hashalg *hashalg, mp_int *q, mp_int *x)
  170. {
  171. /* Make the state structure. */
  172. RFC6979 *s = snew(RFC6979);
  173. s->q = q;
  174. s->x = x;
  175. s->qbits = mp_get_nbits(q);
  176. s->qbytes = (s->qbits + 7) >> 3;
  177. s->hash = ssh_hash_new(hashalg);
  178. s->mac = hmac_new_from_hash(hashalg);
  179. s->hlen = hashalg->hlen;
  180. /* In each attempt, we concatenate enough hash blocks to be
  181. * greater than qbits in size. */
  182. size_t hbits = 8 * s->hlen;
  183. s->T_nblocks = (s->qbits + hbits - 1) / hbits;
  184. s->T = snewn(s->T_nblocks * s->hlen, unsigned char);
  185. return s;
  186. }
  187. void rfc6979_setup(RFC6979 *s, ptrlen message)
  188. {
  189. unsigned char h1[MAX_HASH_LEN];
  190. unsigned char K[MAX_HASH_LEN];
  191. /* 3.2 (a): hash the message to get h1. */
  192. ssh_hash_reset(s->hash);
  193. put_datapl(s->hash, message);
  194. ssh_hash_digest(s->hash, h1);
  195. /* 3.2 (b): set V to a sequence of 0x01 bytes the same size as the
  196. * hash function's output. */
  197. memset(s->V, 1, s->hlen);
  198. /* 3.2 (c): set the initial HMAC key K to all zeroes, again the
  199. * same size as the hash function's output. */
  200. memset(K, 0, s->hlen);
  201. ssh2_mac_setkey(s->mac, make_ptrlen(K, s->hlen));
  202. /* 3.2 (d): compute the MAC of V, the private key, and h1, with
  203. * key K, making a new key to replace K. */
  204. ssh2_mac_start(s->mac);
  205. put_data(s->mac, s->V, s->hlen);
  206. put_byte(s->mac, 0);
  207. put_int2octets(s->mac, s->x, s);
  208. put_bits2octets(s->mac, make_ptrlen(h1, s->hlen), s);
  209. ssh2_mac_genresult(s->mac, K);
  210. ssh2_mac_setkey(s->mac, make_ptrlen(K, s->hlen));
  211. /* 3.2 (e): replace V with its HMAC using the new K. */
  212. ssh2_mac_start(s->mac);
  213. put_data(s->mac, s->V, s->hlen);
  214. ssh2_mac_genresult(s->mac, s->V);
  215. /* 3.2 (f): repeat step (d), only using the new K in place of the
  216. * initial all-zeroes one, and with the extra byte in the middle
  217. * of the MAC preimage being 1 rather than 0. */
  218. ssh2_mac_start(s->mac);
  219. put_data(s->mac, s->V, s->hlen);
  220. put_byte(s->mac, 1);
  221. put_int2octets(s->mac, s->x, s);
  222. put_bits2octets(s->mac, make_ptrlen(h1, s->hlen), s);
  223. ssh2_mac_genresult(s->mac, K);
  224. ssh2_mac_setkey(s->mac, make_ptrlen(K, s->hlen));
  225. /* 3.2 (g): repeat step (e), using the again-replaced K. */
  226. ssh2_mac_start(s->mac);
  227. put_data(s->mac, s->V, s->hlen);
  228. ssh2_mac_genresult(s->mac, s->V);
  229. smemclr(h1, sizeof(h1));
  230. smemclr(K, sizeof(K));
  231. }
  232. RFC6979Result rfc6979_attempt(RFC6979 *s)
  233. {
  234. RFC6979Result result;
  235. /* 3.2 (h) 1: set T to the empty string */
  236. /* 3.2 (h) 2: make lots of output by concatenating MACs of V */
  237. for (size_t i = 0; i < s->T_nblocks; i++) {
  238. ssh2_mac_start(s->mac);
  239. put_data(s->mac, s->V, s->hlen);
  240. ssh2_mac_genresult(s->mac, s->V);
  241. memcpy(s->T + i * s->hlen, s->V, s->hlen);
  242. }
  243. /* 3.2 (h) 3: if we have a number in [1, q-1], return it ... */
  244. result.k = bits2int(make_ptrlen(s->T, s->T_nblocks * s->hlen), s);
  245. result.ok = mp_hs_integer(result.k, 1) & ~mp_cmp_hs(result.k, s->q);
  246. /*
  247. * Perturb K and regenerate V ready for the next attempt.
  248. *
  249. * We do this unconditionally, whether or not the k we just
  250. * generated is acceptable. The time cost isn't large compared to
  251. * the public-key operation we're going to do next (not to mention
  252. * the larger number of these same operations we've already done),
  253. * and it makes side-channel testing easier if this function is
  254. * constant-time from beginning to end.
  255. *
  256. * In other rejection-sampling situations, particularly prime
  257. * generation, we're not this careful: it's enough to ensure that
  258. * _successful_ attempts run in constant time, Failures can do
  259. * whatever they like, on the theory that the only information
  260. * they _have_ to potentially expose via side channels is
  261. * information that was subsequently thrown away without being
  262. * used for anything important. (Hence, for example, it's fine to
  263. * have multiple different early-exit paths for failures you
  264. * detect at different times.)
  265. *
  266. * But here, the situation is different. Prime generation attempts
  267. * are independent of each other. These are not. All our
  268. * iterations round this loop use the _same_ secret data set up by
  269. * rfc6979_new(), and also, the perturbation step we're about to
  270. * compute will be used by the next iteration if there is one. So
  271. * it's absolutely _not_ true that a failed iteration deals
  272. * exclusively with data that won't contribute to the eventual
  273. * output. Hence, we have to be careful about the failures as well
  274. * as the successes.
  275. *
  276. * (Even so, it would be OK to make successes and failures take
  277. * different amounts of time, as long as each of those amounts was
  278. * consistent. But it's easier for testing to make them the same.)
  279. */
  280. ssh2_mac_start(s->mac);
  281. put_data(s->mac, s->V, s->hlen);
  282. put_byte(s->mac, 0);
  283. unsigned char K[MAX_HASH_LEN];
  284. ssh2_mac_genresult(s->mac, K);
  285. ssh2_mac_setkey(s->mac, make_ptrlen(K, s->hlen));
  286. smemclr(K, sizeof(K));
  287. ssh2_mac_start(s->mac);
  288. put_data(s->mac, s->V, s->hlen);
  289. ssh2_mac_genresult(s->mac, s->V);
  290. return result;
  291. }
  292. void rfc6979_free(RFC6979 *s)
  293. {
  294. /* We don't free s->q or s->x: our caller still owns those. */
  295. ssh_hash_free(s->hash);
  296. ssh2_mac_free(s->mac);
  297. smemclr(s->T, s->T_nblocks * s->hlen);
  298. sfree(s->T);
  299. /* Clear the whole structure before freeing. Most fields aren't
  300. * sensitive (pointers or well-known length values), but V is, and
  301. * it's easier to clear the whole lot than fiddle about
  302. * identifying the sensitive fields. */
  303. smemclr(s, sizeof(*s));
  304. sfree(s);
  305. }
  306. mp_int *rfc6979(
  307. const ssh_hashalg *hashalg, mp_int *q, mp_int *x, ptrlen message)
  308. {
  309. RFC6979 *s = rfc6979_new(hashalg, q, x);
  310. rfc6979_setup(s, message);
  311. RFC6979Result result;
  312. while (true) {
  313. result = rfc6979_attempt(s);
  314. if (result.ok)
  315. break;
  316. else
  317. mp_free(result.k);
  318. }
  319. rfc6979_free(s);
  320. return result.k;
  321. }