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
octet_string_from_mpi(unsigned char ** r_frame,void * space,gcry_mpi_t value,size_t nbytes)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 success 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
_gcry_rsa_pkcs1_encode_for_enc(gcry_mpi_t * r_result,unsigned int nbits,const unsigned char * value,size_t valuelen,const unsigned char * random_override,size_t random_override_len)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
_gcry_rsa_pkcs1_decode_for_enc(unsigned char ** r_result,size_t * r_resultlen,unsigned int nbits,gcry_mpi_t value)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 algorithm 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
_gcry_rsa_pkcs1_encode_for_sig(gcry_mpi_t * r_result,unsigned int nbits,const unsigned char * value,size_t valuelen,int algo)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
_gcry_rsa_pkcs1_encode_raw_for_sig(gcry_mpi_t * r_result,unsigned int nbits,const unsigned char * value,size_t valuelen)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
mgf1(unsigned char * output,size_t outlen,unsigned char * seed,size_t seedlen,int algo)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_err_code_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
_gcry_rsa_oaep_encode(gcry_mpi_t * r_result,unsigned int nbits,int algo,const unsigned char * value,size_t valuelen,const unsigned char * label,size_t labellen,const void * random_override,size_t random_override_len)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
_gcry_rsa_oaep_decode(unsigned char ** r_result,size_t * r_resultlen,unsigned int nbits,int algo,gcry_mpi_t value,const unsigned char * label,size_t labellen)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 chosen 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
_gcry_rsa_pss_encode(gcry_mpi_t * r_result,unsigned int nbits,int algo,const unsigned char * value,size_t valuelen,int saltlen,const void * random_override,size_t random_override_len)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
_gcry_rsa_pss_verify(gcry_mpi_t value,gcry_mpi_t encoded,unsigned int nbits,int algo,size_t saltlen)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 }
1039