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