GCM: Add support for split data buffers and online operation
[libgcrypt.git] / cipher / rsa-common.c
1 /* rsa-common.c - Supporting functions for RSA
2  * Copyright (C) 2011 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 /* Turn VALUE into an octet string and store it in an allocated buffer
33    at R_FRAME or - if R_RAME is NULL - copy it into the caller
34    provided buffer SPACE; either SPACE or R_FRAME may be used.  If
35    SPACE if not NULL, the caller must provide a buffer of at least
36    NBYTES.  If the resulting octet string is shorter than NBYTES pad
37    it to the left with zeroes.  If VALUE does not fit into NBYTES
38    return an error code.  */
39 static gpg_err_code_t
40 octet_string_from_mpi (unsigned char **r_frame, void *space,
41                        gcry_mpi_t value, size_t nbytes)
42 {
43   return _gcry_mpi_to_octet_string (r_frame, space, value, nbytes);
44 }
45
46
47
48 /* Encode {VALUE,VALUELEN} for an NBITS keys using the pkcs#1 block
49    type 2 padding.  On sucess the result is stored as a new MPI at
50    R_RESULT.  On error the value at R_RESULT is undefined.
51
52    If {RANDOM_OVERRIDE, RANDOM_OVERRIDE_LEN} is given it is used as
53    the seed instead of using a random string for it.  This feature is
54    only useful for regression tests.  Note that this value may not
55    contain zero bytes.
56
57    We encode the value in this way:
58
59      0  2  RND(n bytes)  0  VALUE
60
61    0   is a marker we unfortunately can't encode because we return an
62        MPI which strips all leading zeroes.
63    2   is the block type.
64    RND are non-zero random bytes.
65
66    (Note that OpenPGP includes the cipher algorithm and a checksum in
67    VALUE; the caller needs to prepare the value accordingly.)
68   */
69 gpg_err_code_t
70 _gcry_rsa_pkcs1_encode_for_enc (gcry_mpi_t *r_result, unsigned int nbits,
71                                 const unsigned char *value, size_t valuelen,
72                                 const unsigned char *random_override,
73                                 size_t random_override_len)
74 {
75   gcry_err_code_t rc = 0;
76   gcry_error_t err;
77   unsigned char *frame = NULL;
78   size_t nframe = (nbits+7) / 8;
79   int i;
80   size_t n;
81   unsigned char *p;
82
83   if (valuelen + 7 > nframe || !nframe)
84     {
85       /* Can't encode a VALUELEN value in a NFRAME bytes frame.  */
86       return GPG_ERR_TOO_SHORT; /* The key is too short.  */
87     }
88
89   if ( !(frame = gcry_malloc_secure (nframe)))
90     return gpg_err_code_from_syserror ();
91
92   n = 0;
93   frame[n++] = 0;
94   frame[n++] = 2; /* block type */
95   i = nframe - 3 - valuelen;
96   gcry_assert (i > 0);
97
98   if (random_override)
99     {
100       int j;
101
102       if (random_override_len != i)
103         {
104           gcry_free (frame);
105           return GPG_ERR_INV_ARG;
106         }
107       /* Check that random does not include a zero byte.  */
108       for (j=0; j < random_override_len; j++)
109         if (!random_override[j])
110           {
111             gcry_free (frame);
112             return GPG_ERR_INV_ARG;
113           }
114       memcpy (frame + n, random_override, random_override_len);
115       n += random_override_len;
116     }
117   else
118     {
119       p = gcry_random_bytes_secure (i, GCRY_STRONG_RANDOM);
120       /* Replace zero bytes by new values. */
121       for (;;)
122         {
123           int j, k;
124           unsigned char *pp;
125
126           /* Count the zero bytes. */
127           for (j=k=0; j < i; j++)
128             {
129               if (!p[j])
130                 k++;
131             }
132           if (!k)
133             break; /* Okay: no (more) zero bytes. */
134
135           k += k/128 + 3; /* Better get some more. */
136           pp = gcry_random_bytes_secure (k, GCRY_STRONG_RANDOM);
137           for (j=0; j < i && k; )
138             {
139               if (!p[j])
140                 p[j] = pp[--k];
141               if (p[j])
142                 j++;
143             }
144           gcry_free (pp);
145         }
146       memcpy (frame+n, p, i);
147       n += i;
148       gcry_free (p);
149     }
150
151   frame[n++] = 0;
152   memcpy (frame+n, value, valuelen);
153   n += valuelen;
154   gcry_assert (n == nframe);
155
156   err = gcry_mpi_scan (r_result, GCRYMPI_FMT_USG, frame, n, &nframe);
157   if (err)
158     rc = gcry_err_code (err);
159   else if (DBG_CIPHER)
160     log_mpidump ("PKCS#1 block type 2 encoded data", *r_result);
161   gcry_free (frame);
162
163   return rc;
164 }
165
166
167 /* Decode a plaintext in VALUE assuming pkcs#1 block type 2 padding.
168    NBITS is the size of the secret key.  On success the result is
169    stored as a newly allocated buffer at R_RESULT and its valid length at
170    R_RESULTLEN.  On error NULL is stored at R_RESULT.  */
171 gpg_err_code_t
172 _gcry_rsa_pkcs1_decode_for_enc (unsigned char **r_result, size_t *r_resultlen,
173                                 unsigned int nbits, gcry_mpi_t value)
174 {
175   gcry_error_t err;
176   unsigned char *frame = NULL;
177   size_t nframe = (nbits+7) / 8;
178   size_t n;
179
180   *r_result = NULL;
181
182   if ( !(frame = gcry_malloc_secure (nframe)))
183     return gpg_err_code_from_syserror ();
184
185   err = gcry_mpi_print (GCRYMPI_FMT_USG, frame, nframe, &n, value);
186   if (err)
187     {
188       gcry_free (frame);
189       return gcry_err_code (err);
190     }
191
192   nframe = n; /* Set NFRAME to the actual length.  */
193
194   /* FRAME = 0x00 || 0x02 || PS || 0x00 || M
195
196      pkcs#1 requires that the first byte is zero.  Our MPIs usually
197      strip leading zero bytes; thus we are not able to detect them.
198      However due to the way gcry_mpi_print is implemented we may see
199      leading zero bytes nevertheless.  We handle this by making the
200      first zero byte optional.  */
201   if (nframe < 4)
202     {
203       gcry_free (frame);
204       return GPG_ERR_ENCODING_PROBLEM;  /* Too short.  */
205     }
206   n = 0;
207   if (!frame[0])
208     n++;
209   if (frame[n++] != 0x02)
210     {
211       gcry_free (frame);
212       return GPG_ERR_ENCODING_PROBLEM;  /* Wrong block type.  */
213     }
214
215   /* Skip the non-zero random bytes and the terminating zero byte.  */
216   for (; n < nframe && frame[n] != 0x00; n++)
217     ;
218   if (n+1 >= nframe)
219     {
220       gcry_free (frame);
221       return GPG_ERR_ENCODING_PROBLEM; /* No zero byte.  */
222     }
223   n++; /* Skip the zero byte.  */
224
225   /* To avoid an extra allocation we reuse the frame buffer.  The only
226      caller of this function will anyway free the result soon.  */
227   memmove (frame, frame + n, nframe - n);
228   *r_result = frame;
229   *r_resultlen = nframe - n;
230
231   if (DBG_CIPHER)
232     log_printhex ("value extracted from PKCS#1 block type 2 encoded data",
233                   *r_result, *r_resultlen);
234
235   return 0;
236 }
237
238
239 /* Encode {VALUE,VALUELEN} for an NBITS keys and hash algorith ALGO
240    using the pkcs#1 block type 1 padding.  On success the result is
241    stored as a new MPI at R_RESULT.  On error the value at R_RESULT is
242    undefined.
243
244    We encode the value in this way:
245
246      0  1  PAD(n bytes)  0  ASN(asnlen bytes) VALUE(valuelen bytes)
247
248    0   is a marker we unfortunately can't encode because we return an
249        MPI which strips all leading zeroes.
250    1   is the block type.
251    PAD consists of 0xff bytes.
252    0   marks the end of the padding.
253    ASN is the DER encoding of the hash algorithm; along with the VALUE
254        it yields a valid DER encoding.
255
256    (Note that PGP prior to version 2.3 encoded the message digest as:
257       0   1   MD(16 bytes)   0   PAD(n bytes)   1
258     The MD is always 16 bytes here because it's always MD5.  GnuPG
259     does not not support pre-v2.3 signatures, but I'm including this
260     comment so the information is easily found if needed.)
261 */
262 gpg_err_code_t
263 _gcry_rsa_pkcs1_encode_for_sig (gcry_mpi_t *r_result, unsigned int nbits,
264                                 const unsigned char *value, size_t valuelen,
265                                 int algo)
266 {
267   gcry_err_code_t rc = 0;
268   gcry_error_t err;
269   byte asn[100];
270   byte *frame = NULL;
271   size_t nframe = (nbits+7) / 8;
272   int i;
273   size_t n;
274   size_t asnlen, dlen;
275
276   asnlen = DIM(asn);
277   dlen = gcry_md_get_algo_dlen (algo);
278
279   if (gcry_md_algo_info (algo, GCRYCTL_GET_ASNOID, asn, &asnlen))
280     {
281       /* We don't have yet all of the above algorithms.  */
282       return GPG_ERR_NOT_IMPLEMENTED;
283     }
284
285   if ( valuelen != dlen )
286     {
287       /* Hash value does not match the length of digest for
288          the given algorithm.  */
289       return GPG_ERR_CONFLICT;
290     }
291
292   if ( !dlen || dlen + asnlen + 4 > nframe)
293     {
294       /* Can't encode an DLEN byte digest MD into an NFRAME byte
295          frame.  */
296       return GPG_ERR_TOO_SHORT;
297     }
298
299   if ( !(frame = gcry_malloc (nframe)) )
300     return gpg_err_code_from_syserror ();
301
302   /* Assemble the pkcs#1 block type 1. */
303   n = 0;
304   frame[n++] = 0;
305   frame[n++] = 1; /* block type */
306   i = nframe - valuelen - asnlen - 3 ;
307   gcry_assert (i > 1);
308   memset (frame+n, 0xff, i );
309   n += i;
310   frame[n++] = 0;
311   memcpy (frame+n, asn, asnlen);
312   n += asnlen;
313   memcpy (frame+n, value, valuelen );
314   n += valuelen;
315   gcry_assert (n == nframe);
316
317   /* Convert it into an MPI. */
318   err = gcry_mpi_scan (r_result, GCRYMPI_FMT_USG, frame, n, &nframe);
319   if (err)
320     rc = gcry_err_code (err);
321   else if (DBG_CIPHER)
322     log_mpidump ("PKCS#1 block type 1 encoded data", *r_result);
323   gcry_free (frame);
324
325   return rc;
326 }
327
328
329 /* Mask generation function for OAEP.  See RFC-3447 B.2.1.  */
330 static gcry_err_code_t
331 mgf1 (unsigned char *output, size_t outlen, unsigned char *seed, size_t seedlen,
332       int algo)
333 {
334   size_t dlen, nbytes, n;
335   int idx;
336   gcry_md_hd_t hd;
337   gcry_error_t err;
338
339   err = gcry_md_open (&hd, algo, 0);
340   if (err)
341     return gpg_err_code (err);
342
343   dlen = gcry_md_get_algo_dlen (algo);
344
345   /* We skip step 1 which would be assert(OUTLEN <= 2^32).  The loop
346      in step 3 is merged with step 4 by concatenating no more octets
347      than what would fit into OUTPUT.  The ceiling for the counter IDX
348      is implemented indirectly.  */
349   nbytes = 0;  /* Step 2.  */
350   idx = 0;
351   while ( nbytes < outlen )
352     {
353       unsigned char c[4], *digest;
354
355       if (idx)
356         gcry_md_reset (hd);
357
358       c[0] = (idx >> 24) & 0xFF;
359       c[1] = (idx >> 16) & 0xFF;
360       c[2] = (idx >> 8) & 0xFF;
361       c[3] = idx & 0xFF;
362       idx++;
363
364       gcry_md_write (hd, seed, seedlen);
365       gcry_md_write (hd, c, 4);
366       digest = gcry_md_read (hd, 0);
367
368       n = (outlen - nbytes < dlen)? (outlen - nbytes) : dlen;
369       memcpy (output+nbytes, digest, n);
370       nbytes += n;
371     }
372
373   gcry_md_close (hd);
374   return GPG_ERR_NO_ERROR;
375 }
376
377
378 /* RFC-3447 (pkcs#1 v2.1) OAEP encoding.  NBITS is the length of the
379    key measured in bits.  ALGO is the hash function; it must be a
380    valid and usable algorithm.  {VALUE,VALUELEN} is the message to
381    encrypt.  {LABEL,LABELLEN} is the optional label to be associated
382    with the message, if LABEL is NULL the default is to use the empty
383    string as label.  On success the encoded ciphertext is returned at
384    R_RESULT.
385
386    If {RANDOM_OVERRIDE, RANDOM_OVERRIDE_LEN} is given it is used as
387    the seed instead of using a random string for it.  This feature is
388    only useful for regression tests.
389
390    Here is figure 1 from the RFC depicting the process:
391
392                              +----------+---------+-------+
393                         DB = |  lHash   |    PS   |   M   |
394                              +----------+---------+-------+
395                                             |
396                   +----------+              V
397                   |   seed   |--> MGF ---> xor
398                   +----------+              |
399                         |                   |
400                +--+     V                   |
401                |00|    xor <----- MGF <-----|
402                +--+     |                   |
403                  |      |                   |
404                  V      V                   V
405                +--+----------+----------------------------+
406          EM =  |00|maskedSeed|          maskedDB          |
407                +--+----------+----------------------------+
408   */
409 gpg_err_code_t
410 _gcry_rsa_oaep_encode (gcry_mpi_t *r_result, unsigned int nbits, int algo,
411                        const unsigned char *value, size_t valuelen,
412                        const unsigned char *label, size_t labellen,
413                        const void *random_override, size_t random_override_len)
414 {
415   gcry_err_code_t rc = 0;
416   gcry_error_t err;
417   unsigned char *frame = NULL;
418   size_t nframe = (nbits+7) / 8;
419   unsigned char *p;
420   size_t hlen;
421   size_t n;
422
423   *r_result = NULL;
424
425   /* Set defaults for LABEL.  */
426   if (!label || !labellen)
427     {
428       label = (const unsigned char*)"";
429       labellen = 0;
430     }
431
432   hlen = gcry_md_get_algo_dlen (algo);
433
434   /* We skip step 1a which would be to check that LABELLEN is not
435      greater than 2^61-1.  See rfc-3447 7.1.1. */
436
437   /* Step 1b.  Note that the obsolete rfc-2437 uses the check:
438      valuelen > nframe - 2 * hlen - 1 .  */
439   if (valuelen > nframe - 2 * hlen - 2 || !nframe)
440     {
441       /* Can't encode a VALUELEN value in a NFRAME bytes frame. */
442       return GPG_ERR_TOO_SHORT; /* The key is too short.  */
443     }
444
445   /* Allocate the frame.  */
446   frame = gcry_calloc_secure (1, nframe);
447   if (!frame)
448     return gpg_err_code_from_syserror ();
449
450   /* Step 2a: Compute the hash of the label.  We store it in the frame
451      where later the maskedDB will commence.  */
452   gcry_md_hash_buffer (algo, frame + 1 + hlen, label, labellen);
453
454   /* Step 2b: Set octet string to zero.  */
455   /* This has already been done while allocating FRAME.  */
456
457   /* Step 2c: Create DB by concatenating lHash, PS, 0x01 and M.  */
458   n = nframe - valuelen - 1;
459   frame[n] = 0x01;
460   memcpy (frame + n + 1, value, valuelen);
461
462   /* Step 3d: Generate seed.  We store it where the maskedSeed will go
463      later. */
464   if (random_override)
465     {
466       if (random_override_len != hlen)
467         {
468           gcry_free (frame);
469           return GPG_ERR_INV_ARG;
470         }
471       memcpy (frame + 1, random_override, hlen);
472     }
473   else
474     gcry_randomize (frame + 1, hlen, GCRY_STRONG_RANDOM);
475
476   /* Step 2e and 2f: Create maskedDB.  */
477   {
478     unsigned char *dmask;
479
480     dmask = gcry_malloc_secure (nframe - hlen - 1);
481     if (!dmask)
482       {
483         rc = gpg_err_code_from_syserror ();
484         gcry_free (frame);
485         return rc;
486       }
487     rc = mgf1 (dmask, nframe - hlen - 1, frame+1, hlen, algo);
488     if (rc)
489       {
490         gcry_free (dmask);
491         gcry_free (frame);
492         return rc;
493       }
494     for (n = 1 + hlen, p = dmask; n < nframe; n++)
495       frame[n] ^= *p++;
496     gcry_free (dmask);
497   }
498
499   /* Step 2g and 2h: Create maskedSeed.  */
500   {
501     unsigned char *smask;
502
503     smask = gcry_malloc_secure (hlen);
504     if (!smask)
505       {
506         rc = gpg_err_code_from_syserror ();
507         gcry_free (frame);
508         return rc;
509       }
510     rc = mgf1 (smask, hlen, frame + 1 + hlen, nframe - hlen - 1, algo);
511     if (rc)
512       {
513         gcry_free (smask);
514         gcry_free (frame);
515         return rc;
516       }
517     for (n = 1, p = smask; n < 1 + hlen; n++)
518       frame[n] ^= *p++;
519     gcry_free (smask);
520   }
521
522   /* Step 2i: Concatenate 0x00, maskedSeed and maskedDB.  */
523   /* This has already been done by using in-place operations.  */
524
525   /* Convert the stuff into an MPI as expected by the caller.  */
526   err = gcry_mpi_scan (r_result, GCRYMPI_FMT_USG, frame, nframe, NULL);
527   if (err)
528     rc = gcry_err_code (err);
529   else if (DBG_CIPHER)
530     log_mpidump ("OAEP encoded data", *r_result);
531   gcry_free (frame);
532
533   return rc;
534 }
535
536
537 /* RFC-3447 (pkcs#1 v2.1) OAEP decoding.  NBITS is the length of the
538    key measured in bits.  ALGO is the hash function; it must be a
539    valid and usable algorithm.  VALUE is the raw decrypted message
540    {LABEL,LABELLEN} is the optional label to be associated with the
541    message, if LABEL is NULL the default is to use the empty string as
542    label.  On success the plaintext is returned as a newly allocated
543    buffer at R_RESULT; its valid length is stored at R_RESULTLEN.  On
544    error NULL is stored at R_RESULT.  */
545 gpg_err_code_t
546 _gcry_rsa_oaep_decode (unsigned char **r_result, size_t *r_resultlen,
547                        unsigned int nbits, int algo,
548                        gcry_mpi_t value,
549                        const unsigned char *label, size_t labellen)
550 {
551   gcry_err_code_t rc;
552   unsigned char *frame = NULL; /* Encoded messages (EM).  */
553   unsigned char *masked_seed;  /* Points into FRAME.  */
554   unsigned char *masked_db;    /* Points into FRAME.  */
555   unsigned char *seed = NULL;  /* Allocated space for the seed and DB.  */
556   unsigned char *db;           /* Points into SEED.  */
557   unsigned char *lhash = NULL; /* Hash of the label.  */
558   size_t nframe;               /* Length of the ciphertext (EM).  */
559   size_t hlen;                 /* Length of the hash digest.  */
560   size_t db_len;               /* Length of DB and masked_db.  */
561   size_t nkey = (nbits+7)/8;   /* Length of the key in bytes.  */
562   int failed = 0;              /* Error indicator.  */
563   size_t n;
564
565   *r_result = NULL;
566
567   /* This code is implemented as described by rfc-3447 7.1.2.  */
568
569   /* Set defaults for LABEL.  */
570   if (!label || !labellen)
571     {
572       label = (const unsigned char*)"";
573       labellen = 0;
574     }
575
576   /* Get the length of the digest.  */
577   hlen = gcry_md_get_algo_dlen (algo);
578
579   /* Hash the label right away.  */
580   lhash = gcry_malloc (hlen);
581   if (!lhash)
582     return gpg_err_code_from_syserror ();
583   gcry_md_hash_buffer (algo, lhash, label, labellen);
584
585   /* Turn the MPI into an octet string.  If the octet string is
586      shorter than the key we pad it to the left with zeroes.  This may
587      happen due to the leading zero in OAEP frames and due to the
588      following random octets (seed^mask) which may have leading zero
589      bytes.  This all is needed to cope with our leading zeroes
590      suppressing MPI implementation.  The code implictly implements
591      Step 1b (bail out if NFRAME != N).  */
592   rc = octet_string_from_mpi (&frame, NULL, value, nkey);
593   if (rc)
594     {
595       gcry_free (lhash);
596       return GPG_ERR_ENCODING_PROBLEM;
597     }
598   nframe = nkey;
599
600   /* Step 1c: Check that the key is long enough.  */
601   if ( nframe < 2 * hlen + 2 )
602     {
603       gcry_free (frame);
604       gcry_free (lhash);
605       return GPG_ERR_ENCODING_PROBLEM;
606     }
607
608   /* Step 2 has already been done by the caller and the
609      gcry_mpi_aprint above.  */
610
611   /* Allocate space for SEED and DB.  */
612   seed = gcry_malloc_secure (nframe - 1);
613   if (!seed)
614     {
615       rc = gpg_err_code_from_syserror ();
616       gcry_free (frame);
617       gcry_free (lhash);
618       return rc;
619     }
620   db = seed + hlen;
621
622   /* To avoid choosen ciphertext attacks from now on we make sure to
623      run all code even in the error case; this avoids possible timing
624      attacks as described by Manger.  */
625
626   /* Step 3a: Hash the label.  */
627   /* This has already been done.  */
628
629   /* Step 3b: Separate the encoded message.  */
630   masked_seed = frame + 1;
631   masked_db   = frame + 1 + hlen;
632   db_len      = nframe - 1 - hlen;
633
634   /* Step 3c and 3d: seed = maskedSeed ^ mgf(maskedDB, hlen).  */
635   if (mgf1 (seed, hlen, masked_db, db_len, algo))
636     failed = 1;
637   for (n = 0; n < hlen; n++)
638     seed[n] ^= masked_seed[n];
639
640   /* Step 3e and 3f: db = maskedDB ^ mgf(seed, db_len).  */
641   if (mgf1 (db, db_len, seed, hlen, algo))
642     failed = 1;
643   for (n = 0; n < db_len; n++)
644     db[n] ^= masked_db[n];
645
646   /* Step 3g: Check lhash, an possible empty padding string terminated
647      by 0x01 and the first byte of EM being 0.  */
648   if (memcmp (lhash, db, hlen))
649     failed = 1;
650   for (n = hlen; n < db_len; n++)
651     if (db[n] == 0x01)
652       break;
653   if (n == db_len)
654     failed = 1;
655   if (frame[0])
656     failed = 1;
657
658   gcry_free (lhash);
659   gcry_free (frame);
660   if (failed)
661     {
662       gcry_free (seed);
663       return GPG_ERR_ENCODING_PROBLEM;
664     }
665
666   /* Step 4: Output M.  */
667   /* To avoid an extra allocation we reuse the seed buffer.  The only
668      caller of this function will anyway free the result soon.  */
669   n++;
670   memmove (seed, db + n, db_len - n);
671   *r_result = seed;
672   *r_resultlen = db_len - n;
673   seed = NULL;
674
675   if (DBG_CIPHER)
676     log_printhex ("value extracted from OAEP encoded data",
677                   *r_result, *r_resultlen);
678
679   return 0;
680 }
681
682
683 /* RFC-3447 (pkcs#1 v2.1) PSS encoding.  Encode {VALUE,VALUELEN} for
684    an NBITS key.  Note that VALUE is already the mHash from the
685    picture below.  ALGO is a valid hash algorithm and SALTLEN is the
686    length of salt to be used.  On success the result is stored as a
687    new MPI at R_RESULT.  On error the value at R_RESULT is undefined.
688
689    If {RANDOM_OVERRIDE, RANDOM_OVERRIDE_LEN} is given it is used as
690    the salt instead of using a random string for the salt.  This
691    feature is only useful for regression tests.
692
693    Here is figure 2 from the RFC (errata 595 applied) depicting the
694    process:
695
696                                   +-----------+
697                                   |     M     |
698                                   +-----------+
699                                         |
700                                         V
701                                       Hash
702                                         |
703                                         V
704                           +--------+----------+----------+
705                      M' = |Padding1|  mHash   |   salt   |
706                           +--------+----------+----------+
707                                          |
708                +--------+----------+     V
709          DB =  |Padding2| salt     |   Hash
710                +--------+----------+     |
711                          |               |
712                          V               |    +----+
713                         xor <--- MGF <---|    |0xbc|
714                          |               |    +----+
715                          |               |      |
716                          V               V      V
717                +-------------------+----------+----+
718          EM =  |    maskedDB       |     H    |0xbc|
719                +-------------------+----------+----+
720
721   */
722 gpg_err_code_t
723 _gcry_rsa_pss_encode (gcry_mpi_t *r_result, unsigned int nbits, int algo,
724                       const unsigned char *value, size_t valuelen, int saltlen,
725                       const void *random_override, size_t random_override_len)
726 {
727   gcry_err_code_t rc = 0;
728   gcry_error_t err;
729   size_t hlen;                 /* Length of the hash digest.  */
730   unsigned char *em = NULL;    /* Encoded message.  */
731   size_t emlen = (nbits+7)/8;  /* Length in bytes of EM.  */
732   unsigned char *h;            /* Points into EM.  */
733   unsigned char *buf = NULL;   /* Help buffer.  */
734   size_t buflen;               /* Length of BUF.  */
735   unsigned char *mhash;        /* Points into BUF.  */
736   unsigned char *salt;         /* Points into BUF.  */
737   unsigned char *dbmask;       /* Points into BUF.  */
738   unsigned char *p;
739   size_t n;
740
741   /* This code is implemented as described by rfc-3447 9.1.1.  */
742
743   /* Get the length of the digest.  */
744   hlen = gcry_md_get_algo_dlen (algo);
745   gcry_assert (hlen);  /* We expect a valid ALGO here.  */
746
747   /* Allocate a help buffer and setup some pointers.  */
748   buflen = 8 + hlen + saltlen + (emlen - hlen - 1);
749   buf = gcry_malloc (buflen);
750   if (!buf)
751     {
752       rc = gpg_err_code_from_syserror ();
753       goto leave;
754     }
755   mhash = buf + 8;
756   salt  = mhash + hlen;
757   dbmask= salt + saltlen;
758
759   /* Step 2: That would be: mHash = Hash(M) but our input is already
760      mHash thus we do only a consistency check and copy to MHASH.  */
761   if (valuelen != hlen)
762     {
763       rc = GPG_ERR_INV_LENGTH;
764       goto leave;
765     }
766   memcpy (mhash, value, hlen);
767
768   /* Step 3: Check length constraints.  */
769   if (emlen < hlen + saltlen + 2)
770     {
771       rc = GPG_ERR_TOO_SHORT;
772       goto leave;
773     }
774
775   /* Allocate space for EM.  */
776   em = gcry_malloc (emlen);
777   if (!em)
778     {
779       rc = gpg_err_code_from_syserror ();
780       goto leave;
781     }
782   h = em + emlen - 1 - hlen;
783
784   /* Step 4: Create a salt.  */
785   if (saltlen)
786     {
787       if (random_override)
788         {
789           if (random_override_len != saltlen)
790             {
791               rc = GPG_ERR_INV_ARG;
792               goto leave;
793             }
794           memcpy (salt, random_override, saltlen);
795         }
796       else
797         gcry_randomize (salt, saltlen, GCRY_STRONG_RANDOM);
798     }
799
800   /* Step 5 and 6: M' = Hash(Padding1 || mHash || salt).  */
801   memset (buf, 0, 8);  /* Padding.  */
802   gcry_md_hash_buffer (algo, h, buf, 8 + hlen + saltlen);
803
804   /* Step 7 and 8: DB = PS || 0x01 || salt.  */
805   /* Note that we use EM to store DB and later Xor in-place.  */
806   p = em + emlen - 1 - hlen - saltlen - 1;
807   memset (em, 0, p - em);
808   *p++ = 0x01;
809   memcpy (p, salt, saltlen);
810
811   /* Step 9: dbmask = MGF(H, emlen - hlen - 1).  */
812   mgf1 (dbmask, emlen - hlen - 1, h, hlen, algo);
813
814   /* Step 10: maskedDB = DB ^ dbMask */
815   for (n = 0, p = dbmask; n < emlen - hlen - 1; n++, p++)
816     em[n] ^= *p;
817
818   /* Step 11: Set the leftmost bits to zero.  */
819   em[0] &= 0xFF >> (8 * emlen - nbits);
820
821   /* Step 12: EM = maskedDB || H || 0xbc.  */
822   em[emlen-1] = 0xbc;
823
824   /* Convert EM into an MPI.  */
825   err = gcry_mpi_scan (r_result, GCRYMPI_FMT_USG, em, emlen, NULL);
826   if (err)
827     rc = gcry_err_code (err);
828   else if (DBG_CIPHER)
829     log_mpidump ("PSS encoded data", *r_result);
830
831  leave:
832   if (em)
833     {
834       wipememory (em, emlen);
835       gcry_free (em);
836     }
837   if (buf)
838     {
839       wipememory (buf, buflen);
840       gcry_free (buf);
841     }
842   return rc;
843 }
844
845
846 /* Verify a signature assuming PSS padding.  VALUE is the hash of the
847    message (mHash) encoded as an MPI; its length must match the digest
848    length of ALGO.  ENCODED is the output of the RSA public key
849    function (EM).  NBITS is the size of the public key.  ALGO is the
850    hash algorithm and SALTLEN is the length of the used salt.  The
851    function returns 0 on success or on error code.  */
852 gpg_err_code_t
853 _gcry_rsa_pss_verify (gcry_mpi_t value, gcry_mpi_t encoded,
854                       unsigned int nbits, int algo, size_t saltlen)
855 {
856   gcry_err_code_t rc = 0;
857   size_t hlen;                 /* Length of the hash digest.  */
858   unsigned char *em = NULL;    /* Encoded message.  */
859   size_t emlen = (nbits+7)/8;  /* Length in bytes of EM.  */
860   unsigned char *salt;         /* Points into EM.  */
861   unsigned char *h;            /* Points into EM.  */
862   unsigned char *buf = NULL;   /* Help buffer.  */
863   size_t buflen;               /* Length of BUF.  */
864   unsigned char *dbmask;       /* Points into BUF.  */
865   unsigned char *mhash;        /* Points into BUF.  */
866   unsigned char *p;
867   size_t n;
868
869   /* This code is implemented as described by rfc-3447 9.1.2.  */
870
871   /* Get the length of the digest.  */
872   hlen = gcry_md_get_algo_dlen (algo);
873   gcry_assert (hlen);  /* We expect a valid ALGO here.  */
874
875   /* Allocate a help buffer and setup some pointers.
876      This buffer is used for two purposes:
877         +------------------------------+-------+
878      1. | dbmask                       | mHash |
879         +------------------------------+-------+
880            emlen - hlen - 1              hlen
881
882         +----------+-------+---------+-+-------+
883      2. | padding1 | mHash | salt    | | mHash |
884         +----------+-------+---------+-+-------+
885              8       hlen    saltlen     hlen
886   */
887   buflen = 8 + hlen + saltlen;
888   if (buflen < emlen - hlen - 1)
889     buflen = emlen - hlen - 1;
890   buflen += hlen;
891   buf = gcry_malloc (buflen);
892   if (!buf)
893     {
894       rc = gpg_err_code_from_syserror ();
895       goto leave;
896     }
897   dbmask = buf;
898   mhash = buf + buflen - hlen;
899
900   /* Step 2: That would be: mHash = Hash(M) but our input is already
901      mHash thus we only need to convert VALUE into MHASH.  */
902   rc = octet_string_from_mpi (NULL, mhash, value, hlen);
903   if (rc)
904     goto leave;
905
906   /* Convert the signature into an octet string.  */
907   rc = octet_string_from_mpi (&em, NULL, encoded, emlen);
908   if (rc)
909     goto leave;
910
911   /* Step 3: Check length of EM.  Because we internally use MPI
912      functions we can't do this properly; EMLEN is always the length
913      of the key because octet_string_from_mpi needs to left pad the
914      result with zero to cope with the fact that our MPIs suppress all
915      leading zeroes.  Thus what we test here are merely the digest and
916      salt lengths to the key.  */
917   if (emlen < hlen + saltlen + 2)
918     {
919       rc = GPG_ERR_TOO_SHORT; /* For the hash and saltlen.  */
920       goto leave;
921     }
922
923   /* Step 4: Check last octet.  */
924   if (em[emlen - 1] != 0xbc)
925     {
926       rc = GPG_ERR_BAD_SIGNATURE;
927       goto leave;
928     }
929
930   /* Step 5: Split EM.  */
931   h = em + emlen - 1 - hlen;
932
933   /* Step 6: Check the leftmost bits.  */
934   if ((em[0] & ~(0xFF >> (8 * emlen - nbits))))
935     {
936       rc = GPG_ERR_BAD_SIGNATURE;
937       goto leave;
938     }
939
940   /* Step 7: dbmask = MGF(H, emlen - hlen - 1).  */
941   mgf1 (dbmask, emlen - hlen - 1, h, hlen, algo);
942
943   /* Step 8: maskedDB = DB ^ dbMask.  */
944   for (n = 0, p = dbmask; n < emlen - hlen - 1; n++, p++)
945     em[n] ^= *p;
946
947   /* Step 9: Set leftmost bits in DB to zero.  */
948   em[0] &= 0xFF >> (8 * emlen - nbits);
949
950   /* Step 10: Check the padding of DB.  */
951   for (n = 0; n < emlen - hlen - saltlen - 2 && !em[n]; n++)
952     ;
953   if (n != emlen - hlen - saltlen - 2 || em[n++] != 1)
954     {
955       rc = GPG_ERR_BAD_SIGNATURE;
956       goto leave;
957     }
958
959   /* Step 11: Extract salt from DB.  */
960   salt = em + n;
961
962   /* Step 12:  M' = (0x)00 00 00 00 00 00 00 00 || mHash || salt */
963   memset (buf, 0, 8);
964   memcpy (buf+8, mhash, hlen);
965   memcpy (buf+8+hlen, salt, saltlen);
966
967   /* Step 13:  H' = Hash(M').  */
968   gcry_md_hash_buffer (algo, buf, buf, 8 + hlen + saltlen);
969
970   /* Step 14:  Check H == H'.   */
971   rc = memcmp (h, buf, hlen) ? GPG_ERR_BAD_SIGNATURE : GPG_ERR_NO_ERROR;
972
973  leave:
974   if (em)
975     {
976       wipememory (em, emlen);
977       gcry_free (em);
978     }
979   if (buf)
980     {
981       wipememory (buf, buflen);
982       gcry_free (buf);
983     }
984   return rc;
985 }