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