Line data Source code
1 : /* dsa-common.c - Common code for DSA
2 : * Copyright (C) 1998, 1999 Free Software Foundation, Inc.
3 : * Copyright (C) 2013 g10 Code GmbH
4 : *
5 : * This file is part of Libgcrypt.
6 : *
7 : * Libgcrypt is free software; you can redistribute it and/or modify
8 : * it under the terms of the GNU Lesser General Public License as
9 : * published by the Free Software Foundation; either version 2.1 of
10 : * the License, or (at your option) any later version.
11 : *
12 : * Libgcrypt is distributed in the hope that it will be useful,
13 : * but WITHOUT ANY WARRANTY; without even the implied warranty of
14 : * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 : * GNU Lesser General Public License for more details.
16 : *
17 : * You should have received a copy of the GNU Lesser General Public
18 : * License along with this program; if not, see <http://www.gnu.org/licenses/>.
19 : */
20 :
21 : #include <config.h>
22 : #include <stdio.h>
23 : #include <stdlib.h>
24 : #include <string.h>
25 :
26 : #include "g10lib.h"
27 : #include "mpi.h"
28 : #include "cipher.h"
29 : #include "pubkey-internal.h"
30 :
31 :
32 : /*
33 : * Generate a random secret exponent K less than Q.
34 : * Note that ECDSA uses this code also to generate D.
35 : */
36 : gcry_mpi_t
37 192 : _gcry_dsa_gen_k (gcry_mpi_t q, int security_level)
38 : {
39 192 : gcry_mpi_t k = mpi_alloc_secure (mpi_get_nlimbs (q));
40 192 : unsigned int nbits = mpi_get_nbits (q);
41 192 : unsigned int nbytes = (nbits+7)/8;
42 192 : char *rndbuf = NULL;
43 :
44 : /* To learn why we don't use mpi_mod to get the requested bit size,
45 : read the paper: "The Insecurity of the Digital Signature
46 : Algorithm with Partially Known Nonces" by Nguyen and Shparlinski.
47 : Journal of Cryptology, New York. Vol 15, nr 3 (2003) */
48 :
49 192 : if (DBG_CIPHER)
50 0 : log_debug ("choosing a random k of %u bits at seclevel %d\n",
51 : nbits, security_level);
52 : for (;;)
53 : {
54 280 : if ( !rndbuf || nbits < 32 )
55 : {
56 192 : xfree (rndbuf);
57 192 : rndbuf = _gcry_random_bytes_secure (nbytes, security_level);
58 : }
59 : else
60 : { /* Change only some of the higher bits. We could improve
61 : this by directly requesting more memory at the first call
62 : to get_random_bytes() and use these extra bytes here.
63 : However the required management code is more complex and
64 : thus we better use this simple method. */
65 44 : char *pp = _gcry_random_bytes_secure (4, security_level);
66 44 : memcpy (rndbuf, pp, 4);
67 44 : xfree (pp);
68 : }
69 236 : _gcry_mpi_set_buffer (k, rndbuf, nbytes, 0);
70 :
71 : /* Make sure we have the requested number of bits. This code
72 : looks a bit funny but it is easy to understand if you
73 : consider that mpi_set_highbit clears all higher bits. We
74 : don't have a clear_highbit, thus we first set the high bit
75 : and then clear it again. */
76 236 : if (mpi_test_bit (k, nbits-1))
77 120 : mpi_set_highbit (k, nbits-1);
78 : else
79 : {
80 116 : mpi_set_highbit (k, nbits-1);
81 116 : mpi_clear_bit (k, nbits-1);
82 : }
83 :
84 236 : if (!(mpi_cmp (k, q) < 0)) /* check: k < q */
85 : {
86 44 : if (DBG_CIPHER)
87 0 : log_debug ("\tk too large - again\n");
88 44 : continue; /* no */
89 : }
90 192 : if (!(mpi_cmp_ui (k, 0) > 0)) /* check: k > 0 */
91 : {
92 0 : if (DBG_CIPHER)
93 0 : log_debug ("\tk is zero - again\n");
94 0 : continue; /* no */
95 : }
96 192 : break; /* okay */
97 : }
98 192 : xfree (rndbuf);
99 :
100 192 : return k;
101 : }
102 :
103 :
104 : /* Turn VALUE into an octet string and store it in an allocated buffer
105 : at R_FRAME. If the resulting octet string is shorter than NBYTES
106 : the result will be left padded with zeroes. If VALUE does not fit
107 : into NBYTES an error code is returned. */
108 : static gpg_err_code_t
109 152 : int2octets (unsigned char **r_frame, gcry_mpi_t value, size_t nbytes)
110 : {
111 : gpg_err_code_t rc;
112 : size_t nframe, noff, n;
113 : unsigned char *frame;
114 :
115 152 : rc = _gcry_mpi_print (GCRYMPI_FMT_USG, NULL, 0, &nframe, value);
116 152 : if (rc)
117 0 : return rc;
118 152 : if (nframe > nbytes)
119 0 : return GPG_ERR_TOO_LARGE; /* Value too long to fit into NBYTES. */
120 :
121 152 : noff = (nframe < nbytes)? nbytes - nframe : 0;
122 152 : n = nframe + noff;
123 152 : frame = mpi_is_secure (value)? xtrymalloc_secure (n) : xtrymalloc (n);
124 152 : if (!frame)
125 0 : return gpg_err_code_from_syserror ();
126 152 : if (noff)
127 40 : memset (frame, 0, noff);
128 152 : nframe += noff;
129 152 : rc = _gcry_mpi_print (GCRYMPI_FMT_USG, frame+noff, nframe-noff, NULL, value);
130 152 : if (rc)
131 : {
132 0 : xfree (frame);
133 0 : return rc;
134 : }
135 :
136 152 : *r_frame = frame;
137 152 : return 0;
138 : }
139 :
140 :
141 : /* Connert the bit string BITS of length NBITS into an octet string
142 : with a length of (QBITS+7)/8 bytes. On success store the result at
143 : R_FRAME. */
144 : static gpg_err_code_t
145 76 : bits2octets (unsigned char **r_frame,
146 : const void *bits, unsigned int nbits,
147 : gcry_mpi_t q, unsigned int qbits)
148 : {
149 : gpg_err_code_t rc;
150 : gcry_mpi_t z1;
151 :
152 : /* z1 = bits2int (b) */
153 76 : rc = _gcry_mpi_scan (&z1, GCRYMPI_FMT_USG, bits, (nbits+7)/8, NULL);
154 76 : if (rc)
155 0 : return rc;
156 76 : if (nbits > qbits)
157 34 : mpi_rshift (z1, z1, nbits - qbits);
158 :
159 : /* z2 - z1 mod q */
160 76 : if (mpi_cmp (z1, q) >= 0)
161 5 : mpi_sub (z1, z1, q);
162 :
163 : /* Convert to an octet string. */
164 76 : rc = int2octets (r_frame, z1, (qbits+7)/8);
165 :
166 76 : mpi_free (z1);
167 76 : return rc;
168 : }
169 :
170 :
171 : /*
172 : * Generate a deterministic secret exponent K less than DSA_Q. H1 is
173 : * the to be signed digest with a length of HLEN bytes. HALGO is the
174 : * algorithm used to create the hash. On success the value for K is
175 : * stored at R_K.
176 : */
177 : gpg_err_code_t
178 76 : _gcry_dsa_gen_rfc6979_k (gcry_mpi_t *r_k,
179 : gcry_mpi_t dsa_q, gcry_mpi_t dsa_x,
180 : const unsigned char *h1, unsigned int hlen,
181 : int halgo, unsigned int extraloops)
182 : {
183 : gpg_err_code_t rc;
184 76 : unsigned char *V = NULL;
185 76 : unsigned char *K = NULL;
186 76 : unsigned char *x_buf = NULL;
187 76 : unsigned char *h1_buf = NULL;
188 76 : gcry_md_hd_t hd = NULL;
189 76 : unsigned char *t = NULL;
190 76 : gcry_mpi_t k = NULL;
191 : unsigned int tbits, qbits;
192 : int i;
193 :
194 76 : qbits = mpi_get_nbits (dsa_q);
195 :
196 76 : if (!qbits || !h1 || !hlen)
197 0 : return GPG_ERR_EINVAL;
198 :
199 76 : if (_gcry_md_get_algo_dlen (halgo) != hlen)
200 0 : return GPG_ERR_DIGEST_ALGO;
201 :
202 : /* Step b: V = 0x01 0x01 0x01 ... 0x01 */
203 76 : V = xtrymalloc (hlen);
204 76 : if (!V)
205 : {
206 0 : rc = gpg_err_code_from_syserror ();
207 0 : goto leave;
208 : }
209 2956 : for (i=0; i < hlen; i++)
210 2880 : V[i] = 1;
211 :
212 : /* Step c: K = 0x00 0x00 0x00 ... 0x00 */
213 76 : K = xtrycalloc (1, hlen);
214 76 : if (!K)
215 : {
216 0 : rc = gpg_err_code_from_syserror ();
217 0 : goto leave;
218 : }
219 :
220 76 : rc = int2octets (&x_buf, dsa_x, (qbits+7)/8);
221 76 : if (rc)
222 0 : goto leave;
223 :
224 76 : rc = bits2octets (&h1_buf, h1, hlen*8, dsa_q, qbits);
225 76 : if (rc)
226 0 : goto leave;
227 :
228 : /* Create a handle to compute the HMACs. */
229 76 : rc = _gcry_md_open (&hd, halgo, (GCRY_MD_FLAG_SECURE | GCRY_MD_FLAG_HMAC));
230 76 : if (rc)
231 0 : goto leave;
232 :
233 : /* Step d: K = HMAC_K(V || 0x00 || int2octets(x) || bits2octets(h1) */
234 76 : rc = _gcry_md_setkey (hd, K, hlen);
235 76 : if (rc)
236 0 : goto leave;
237 76 : _gcry_md_write (hd, V, hlen);
238 76 : _gcry_md_write (hd, "", 1);
239 76 : _gcry_md_write (hd, x_buf, (qbits+7)/8);
240 76 : _gcry_md_write (hd, h1_buf, (qbits+7)/8);
241 76 : memcpy (K, _gcry_md_read (hd, 0), hlen);
242 :
243 : /* Step e: V = HMAC_K(V) */
244 76 : rc = _gcry_md_setkey (hd, K, hlen);
245 76 : if (rc)
246 0 : goto leave;
247 76 : _gcry_md_write (hd, V, hlen);
248 76 : memcpy (V, _gcry_md_read (hd, 0), hlen);
249 :
250 : /* Step f: K = HMAC_K(V || 0x01 || int2octets(x) || bits2octets(h1) */
251 76 : rc = _gcry_md_setkey (hd, K, hlen);
252 76 : if (rc)
253 0 : goto leave;
254 76 : _gcry_md_write (hd, V, hlen);
255 76 : _gcry_md_write (hd, "\x01", 1);
256 76 : _gcry_md_write (hd, x_buf, (qbits+7)/8);
257 76 : _gcry_md_write (hd, h1_buf, (qbits+7)/8);
258 76 : memcpy (K, _gcry_md_read (hd, 0), hlen);
259 :
260 : /* Step g: V = HMAC_K(V) */
261 76 : rc = _gcry_md_setkey (hd, K, hlen);
262 76 : if (rc)
263 0 : goto leave;
264 76 : _gcry_md_write (hd, V, hlen);
265 76 : memcpy (V, _gcry_md_read (hd, 0), hlen);
266 :
267 : /* Step h. */
268 76 : t = xtrymalloc ((qbits+7)/8+hlen);
269 76 : if (!t)
270 : {
271 0 : rc = gpg_err_code_from_syserror ();
272 0 : goto leave;
273 : }
274 :
275 : again:
276 326 : for (tbits = 0; tbits < qbits;)
277 : {
278 : /* V = HMAC_K(V) */
279 134 : rc = _gcry_md_setkey (hd, K, hlen);
280 134 : if (rc)
281 0 : goto leave;
282 134 : _gcry_md_write (hd, V, hlen);
283 134 : memcpy (V, _gcry_md_read (hd, 0), hlen);
284 :
285 : /* T = T || V */
286 134 : memcpy (t+(tbits+7)/8, V, hlen);
287 134 : tbits += 8*hlen;
288 : }
289 :
290 : /* k = bits2int (T) */
291 96 : mpi_free (k);
292 96 : k = NULL;
293 96 : rc = _gcry_mpi_scan (&k, GCRYMPI_FMT_USG, t, (tbits+7)/8, NULL);
294 96 : if (rc)
295 0 : goto leave;
296 96 : if (tbits > qbits)
297 81 : mpi_rshift (k, k, tbits - qbits);
298 :
299 : /* Check: k < q and k > 1 */
300 96 : if (!(mpi_cmp (k, dsa_q) < 0 && mpi_cmp_ui (k, 0) > 0))
301 : {
302 : /* K = HMAC_K(V || 0x00) */
303 20 : rc = _gcry_md_setkey (hd, K, hlen);
304 20 : if (rc)
305 0 : goto leave;
306 20 : _gcry_md_write (hd, V, hlen);
307 20 : _gcry_md_write (hd, "", 1);
308 20 : memcpy (K, _gcry_md_read (hd, 0), hlen);
309 :
310 : /* V = HMAC_K(V) */
311 20 : rc = _gcry_md_setkey (hd, K, hlen);
312 20 : if (rc)
313 0 : goto leave;
314 20 : _gcry_md_write (hd, V, hlen);
315 20 : memcpy (V, _gcry_md_read (hd, 0), hlen);
316 :
317 20 : goto again;
318 : }
319 :
320 : /* The caller may have requested that we introduce some extra loops.
321 : This is for example useful if the caller wants another value for
322 : K because the last returned one yielded an R of 0. Because this
323 : is very unlikely we implement it in a straightforward way. */
324 76 : if (extraloops)
325 : {
326 0 : extraloops--;
327 :
328 : /* K = HMAC_K(V || 0x00) */
329 0 : rc = _gcry_md_setkey (hd, K, hlen);
330 0 : if (rc)
331 0 : goto leave;
332 0 : _gcry_md_write (hd, V, hlen);
333 0 : _gcry_md_write (hd, "", 1);
334 0 : memcpy (K, _gcry_md_read (hd, 0), hlen);
335 :
336 : /* V = HMAC_K(V) */
337 0 : rc = _gcry_md_setkey (hd, K, hlen);
338 0 : if (rc)
339 0 : goto leave;
340 0 : _gcry_md_write (hd, V, hlen);
341 0 : memcpy (V, _gcry_md_read (hd, 0), hlen);
342 :
343 0 : goto again;
344 : }
345 :
346 : /* log_mpidump (" k", k); */
347 :
348 : leave:
349 76 : xfree (t);
350 76 : _gcry_md_close (hd);
351 76 : xfree (h1_buf);
352 76 : xfree (x_buf);
353 76 : xfree (K);
354 76 : xfree (V);
355 :
356 76 : if (rc)
357 0 : mpi_free (k);
358 : else
359 76 : *r_k = k;
360 76 : return rc;
361 : }
362 :
363 : /*
364 : * Truncate opaque hash value to qbits for DSA.
365 : * Non-opaque input is not truncated, in hope that user
366 : * knows what is passed. It is not possible to correctly
367 : * trucate non-opaque inputs.
368 : */
369 : gpg_err_code_t
370 521 : _gcry_dsa_normalize_hash (gcry_mpi_t input,
371 : gcry_mpi_t *out,
372 : unsigned int qbits)
373 : {
374 521 : gpg_err_code_t rc = 0;
375 : const void *abuf;
376 : unsigned int abits;
377 : gcry_mpi_t hash;
378 :
379 521 : if (mpi_is_opaque (input))
380 : {
381 108 : abuf = mpi_get_opaque (input, &abits);
382 108 : rc = _gcry_mpi_scan (&hash, GCRYMPI_FMT_USG, abuf, (abits+7)/8, NULL);
383 108 : if (rc)
384 0 : return rc;
385 216 : if (abits > qbits)
386 48 : mpi_rshift (hash, hash, abits - qbits);
387 : }
388 : else
389 413 : hash = input;
390 :
391 521 : *out = hash;
392 :
393 521 : return rc;
394 : }
|
