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