Line data Source code
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 398 : octet_string_from_mpi (unsigned char **r_frame, void *space,
41 : gcry_mpi_t value, size_t nbytes)
42 : {
43 398 : 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
70 348 : _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 348 : gcry_err_code_t rc = 0;
76 348 : unsigned char *frame = NULL;
77 348 : size_t nframe = (nbits+7) / 8;
78 : int i;
79 : size_t n;
80 : unsigned char *p;
81 :
82 348 : if (valuelen + 7 > nframe || !nframe)
83 : {
84 : /* Can't encode a VALUELEN value in a NFRAME bytes frame. */
85 0 : return GPG_ERR_TOO_SHORT; /* The key is too short. */
86 : }
87 :
88 348 : if ( !(frame = xtrymalloc_secure (nframe)))
89 0 : return gpg_err_code_from_syserror ();
90 :
91 348 : n = 0;
92 348 : frame[n++] = 0;
93 348 : frame[n++] = 2; /* block type */
94 348 : i = nframe - 3 - valuelen;
95 348 : gcry_assert (i > 0);
96 :
97 348 : if (random_override)
98 : {
99 : int j;
100 :
101 300 : if (random_override_len != i)
102 : {
103 0 : xfree (frame);
104 0 : return GPG_ERR_INV_ARG;
105 : }
106 : /* Check that random does not include a zero byte. */
107 31696 : for (j=0; j < random_override_len; j++)
108 31396 : if (!random_override[j])
109 : {
110 0 : xfree (frame);
111 0 : return GPG_ERR_INV_ARG;
112 : }
113 300 : memcpy (frame + n, random_override, random_override_len);
114 300 : n += random_override_len;
115 : }
116 : else
117 : {
118 48 : p = _gcry_random_bytes_secure (i, GCRY_STRONG_RANDOM);
119 : /* Replace zero bytes by new values. */
120 : for (;;)
121 13 : {
122 : int j, k;
123 : unsigned char *pp;
124 :
125 : /* Count the zero bytes. */
126 7015 : for (j=k=0; j < i; j++)
127 : {
128 6954 : if (!p[j])
129 21 : k++;
130 : }
131 61 : if (!k)
132 48 : break; /* Okay: no (more) zero bytes. */
133 :
134 13 : k += k/128 + 3; /* Better get some more. */
135 13 : pp = _gcry_random_bytes_secure (k, GCRY_STRONG_RANDOM);
136 1508 : for (j=0; j < i && k; )
137 : {
138 1482 : if (!p[j])
139 21 : p[j] = pp[--k];
140 1482 : if (p[j])
141 1482 : j++;
142 : }
143 13 : xfree (pp);
144 : }
145 48 : memcpy (frame+n, p, i);
146 48 : n += i;
147 48 : xfree (p);
148 : }
149 :
150 348 : frame[n++] = 0;
151 348 : memcpy (frame+n, value, valuelen);
152 348 : n += valuelen;
153 348 : gcry_assert (n == nframe);
154 :
155 348 : rc = _gcry_mpi_scan (r_result, GCRYMPI_FMT_USG, frame, n, &nframe);
156 348 : if (!rc &&DBG_CIPHER)
157 0 : log_mpidump ("PKCS#1 block type 2 encoded data", *r_result);
158 348 : xfree (frame);
159 :
160 348 : 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 348 : _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 348 : unsigned char *frame = NULL;
174 348 : size_t nframe = (nbits+7) / 8;
175 : size_t n;
176 :
177 348 : *r_result = NULL;
178 :
179 348 : if ( !(frame = xtrymalloc_secure (nframe)))
180 0 : return gpg_err_code_from_syserror ();
181 :
182 348 : err = _gcry_mpi_print (GCRYMPI_FMT_USG, frame, nframe, &n, value);
183 348 : if (err)
184 : {
185 0 : xfree (frame);
186 0 : return gcry_err_code (err);
187 : }
188 :
189 348 : 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 348 : if (nframe < 4)
199 : {
200 0 : xfree (frame);
201 0 : return GPG_ERR_ENCODING_PROBLEM; /* Too short. */
202 : }
203 348 : n = 0;
204 348 : if (!frame[0])
205 0 : n++;
206 348 : if (frame[n++] != 0x02)
207 : {
208 24 : xfree (frame);
209 24 : return GPG_ERR_ENCODING_PROBLEM; /* Wrong block type. */
210 : }
211 :
212 : /* Skip the non-zero random bytes and the terminating zero byte. */
213 324 : for (; n < nframe && frame[n] != 0x00; n++)
214 : ;
215 324 : if (n+1 >= nframe)
216 : {
217 0 : xfree (frame);
218 0 : return GPG_ERR_ENCODING_PROBLEM; /* No zero byte. */
219 : }
220 324 : 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 324 : memmove (frame, frame + n, nframe - n);
225 324 : *r_result = frame;
226 324 : *r_resultlen = nframe - n;
227 :
228 324 : if (DBG_CIPHER)
229 0 : log_printhex ("value extracted from PKCS#1 block type 2 encoded data",
230 : *r_result, *r_resultlen);
231 :
232 324 : 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 906 : _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 906 : gcry_err_code_t rc = 0;
265 : byte asn[100];
266 906 : byte *frame = NULL;
267 906 : size_t nframe = (nbits+7) / 8;
268 : int i;
269 : size_t n;
270 : size_t asnlen, dlen;
271 :
272 906 : asnlen = DIM(asn);
273 906 : dlen = _gcry_md_get_algo_dlen (algo);
274 :
275 906 : if (_gcry_md_algo_info (algo, GCRYCTL_GET_ASNOID, asn, &asnlen))
276 : {
277 : /* We don't have yet all of the above algorithms. */
278 0 : return GPG_ERR_NOT_IMPLEMENTED;
279 : }
280 :
281 906 : if ( valuelen != dlen )
282 : {
283 : /* Hash value does not match the length of digest for
284 : the given algorithm. */
285 0 : return GPG_ERR_CONFLICT;
286 : }
287 :
288 906 : if ( !dlen || dlen + asnlen + 4 > nframe)
289 : {
290 : /* Can't encode an DLEN byte digest MD into an NFRAME byte
291 : frame. */
292 0 : return GPG_ERR_TOO_SHORT;
293 : }
294 :
295 906 : if ( !(frame = xtrymalloc (nframe)) )
296 0 : return gpg_err_code_from_syserror ();
297 :
298 : /* Assemble the pkcs#1 block type 1. */
299 906 : n = 0;
300 906 : frame[n++] = 0;
301 906 : frame[n++] = 1; /* block type */
302 906 : i = nframe - valuelen - asnlen - 3 ;
303 906 : gcry_assert (i > 1);
304 906 : memset (frame+n, 0xff, i );
305 906 : n += i;
306 906 : frame[n++] = 0;
307 906 : memcpy (frame+n, asn, asnlen);
308 906 : n += asnlen;
309 906 : memcpy (frame+n, value, valuelen );
310 906 : n += valuelen;
311 906 : gcry_assert (n == nframe);
312 :
313 : /* Convert it into an MPI. */
314 906 : rc = _gcry_mpi_scan (r_result, GCRYMPI_FMT_USG, frame, n, &nframe);
315 906 : if (!rc && DBG_CIPHER)
316 0 : log_mpidump ("PKCS#1 block type 1 encoded data", *r_result);
317 906 : xfree (frame);
318 :
319 906 : 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 48 : _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 48 : gcry_err_code_t rc = 0;
347 : gcry_error_t err;
348 48 : byte *frame = NULL;
349 48 : size_t nframe = (nbits+7) / 8;
350 : int i;
351 : size_t n;
352 :
353 48 : if ( !valuelen || valuelen + 4 > nframe)
354 : {
355 : /* Can't encode an DLEN byte digest MD into an NFRAME byte
356 : frame. */
357 0 : return GPG_ERR_TOO_SHORT;
358 : }
359 :
360 48 : if ( !(frame = xtrymalloc (nframe)) )
361 0 : return gpg_err_code_from_syserror ();
362 :
363 : /* Assemble the pkcs#1 block type 1. */
364 48 : n = 0;
365 48 : frame[n++] = 0;
366 48 : frame[n++] = 1; /* block type */
367 48 : i = nframe - valuelen - 3 ;
368 48 : gcry_assert (i > 1);
369 48 : memset (frame+n, 0xff, i );
370 48 : n += i;
371 48 : frame[n++] = 0;
372 48 : memcpy (frame+n, value, valuelen );
373 48 : n += valuelen;
374 48 : gcry_assert (n == nframe);
375 :
376 : /* Convert it into an MPI. */
377 48 : err = _gcry_mpi_scan (r_result, GCRYMPI_FMT_USG, frame, n, &nframe);
378 48 : if (err)
379 0 : rc = gcry_err_code (err);
380 48 : else if (DBG_CIPHER)
381 0 : log_mpidump ("PKCS#1 block type 1 encoded data", *r_result);
382 48 : xfree (frame);
383 :
384 48 : return rc;
385 : }
386 :
387 :
388 : /* Mask generation function for OAEP. See RFC-3447 B.2.1. */
389 : static gcry_err_code_t
390 940 : 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 940 : err = _gcry_md_open (&hd, algo, 0);
399 940 : if (err)
400 0 : return err;
401 :
402 940 : 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 940 : nbytes = 0; /* Step 2. */
409 940 : idx = 0;
410 5926 : while ( nbytes < outlen )
411 : {
412 : unsigned char c[4], *digest;
413 :
414 4046 : if (idx)
415 3106 : _gcry_md_reset (hd);
416 :
417 4046 : c[0] = (idx >> 24) & 0xFF;
418 4046 : c[1] = (idx >> 16) & 0xFF;
419 4046 : c[2] = (idx >> 8) & 0xFF;
420 4046 : c[3] = idx & 0xFF;
421 4046 : idx++;
422 :
423 4046 : _gcry_md_write (hd, seed, seedlen);
424 4046 : _gcry_md_write (hd, c, 4);
425 4046 : digest = _gcry_md_read (hd, 0);
426 :
427 4046 : n = (outlen - nbytes < dlen)? (outlen - nbytes) : dlen;
428 4046 : memcpy (output+nbytes, digest, n);
429 4046 : nbytes += n;
430 : }
431 :
432 940 : _gcry_md_close (hd);
433 940 : 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 180 : _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 180 : gcry_err_code_t rc = 0;
475 180 : unsigned char *frame = NULL;
476 180 : size_t nframe = (nbits+7) / 8;
477 : unsigned char *p;
478 : size_t hlen;
479 : size_t n;
480 :
481 180 : *r_result = NULL;
482 :
483 : /* Set defaults for LABEL. */
484 180 : if (!label || !labellen)
485 : {
486 132 : label = (const unsigned char*)"";
487 132 : labellen = 0;
488 : }
489 :
490 180 : 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 180 : if (valuelen > nframe - 2 * hlen - 2 || !nframe)
498 : {
499 : /* Can't encode a VALUELEN value in a NFRAME bytes frame. */
500 0 : return GPG_ERR_TOO_SHORT; /* The key is too short. */
501 : }
502 :
503 : /* Allocate the frame. */
504 180 : frame = xtrycalloc_secure (1, nframe);
505 180 : if (!frame)
506 0 : 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 180 : _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 180 : n = nframe - valuelen - 1;
517 180 : frame[n] = 0x01;
518 180 : memcpy (frame + n + 1, value, valuelen);
519 :
520 : /* Step 3d: Generate seed. We store it where the maskedSeed will go
521 : later. */
522 180 : if (random_override)
523 : {
524 84 : if (random_override_len != hlen)
525 : {
526 0 : xfree (frame);
527 0 : return GPG_ERR_INV_ARG;
528 : }
529 84 : memcpy (frame + 1, random_override, hlen);
530 : }
531 : else
532 96 : _gcry_randomize (frame + 1, hlen, GCRY_STRONG_RANDOM);
533 :
534 : /* Step 2e and 2f: Create maskedDB. */
535 : {
536 : unsigned char *dmask;
537 :
538 180 : dmask = xtrymalloc_secure (nframe - hlen - 1);
539 180 : if (!dmask)
540 : {
541 0 : rc = gpg_err_code_from_syserror ();
542 0 : xfree (frame);
543 0 : return rc;
544 : }
545 180 : rc = mgf1 (dmask, nframe - hlen - 1, frame+1, hlen, algo);
546 180 : if (rc)
547 : {
548 0 : xfree (dmask);
549 0 : xfree (frame);
550 0 : return rc;
551 : }
552 20634 : for (n = 1 + hlen, p = dmask; n < nframe; n++)
553 20454 : frame[n] ^= *p++;
554 180 : xfree (dmask);
555 : }
556 :
557 : /* Step 2g and 2h: Create maskedSeed. */
558 : {
559 : unsigned char *smask;
560 :
561 180 : smask = xtrymalloc_secure (hlen);
562 180 : if (!smask)
563 : {
564 0 : rc = gpg_err_code_from_syserror ();
565 0 : xfree (frame);
566 0 : return rc;
567 : }
568 180 : rc = mgf1 (smask, hlen, frame + 1 + hlen, nframe - hlen - 1, algo);
569 180 : if (rc)
570 : {
571 0 : xfree (smask);
572 0 : xfree (frame);
573 0 : return rc;
574 : }
575 3780 : for (n = 1, p = smask; n < 1 + hlen; n++)
576 3600 : frame[n] ^= *p++;
577 180 : 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 180 : rc = _gcry_mpi_scan (r_result, GCRYMPI_FMT_USG, frame, nframe, NULL);
585 180 : if (!rc && DBG_CIPHER)
586 0 : log_mpidump ("OAEP encoded data", *r_result);
587 180 : xfree (frame);
588 :
589 180 : 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 182 : _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 182 : unsigned char *frame = NULL; /* Encoded messages (EM). */
609 : unsigned char *masked_seed; /* Points into FRAME. */
610 : unsigned char *masked_db; /* Points into FRAME. */
611 182 : unsigned char *seed = NULL; /* Allocated space for the seed and DB. */
612 : unsigned char *db; /* Points into SEED. */
613 182 : 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 182 : size_t nkey = (nbits+7)/8; /* Length of the key in bytes. */
618 182 : int failed = 0; /* Error indicator. */
619 : size_t n;
620 :
621 182 : *r_result = NULL;
622 :
623 : /* This code is implemented as described by rfc-3447 7.1.2. */
624 :
625 : /* Set defaults for LABEL. */
626 182 : if (!label || !labellen)
627 : {
628 134 : label = (const unsigned char*)"";
629 134 : labellen = 0;
630 : }
631 :
632 : /* Get the length of the digest. */
633 182 : hlen = _gcry_md_get_algo_dlen (algo);
634 :
635 : /* Hash the label right away. */
636 182 : lhash = xtrymalloc (hlen);
637 182 : if (!lhash)
638 0 : return gpg_err_code_from_syserror ();
639 182 : _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 182 : rc = octet_string_from_mpi (&frame, NULL, value, nkey);
649 182 : if (rc)
650 : {
651 0 : xfree (lhash);
652 0 : return GPG_ERR_ENCODING_PROBLEM;
653 : }
654 182 : nframe = nkey;
655 :
656 : /* Step 1c: Check that the key is long enough. */
657 182 : if ( nframe < 2 * hlen + 2 )
658 : {
659 0 : xfree (frame);
660 0 : xfree (lhash);
661 0 : 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 182 : seed = xtrymalloc_secure (nframe - 1);
669 182 : if (!seed)
670 : {
671 0 : rc = gpg_err_code_from_syserror ();
672 0 : xfree (frame);
673 0 : xfree (lhash);
674 0 : return rc;
675 : }
676 182 : 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 182 : masked_seed = frame + 1;
687 182 : masked_db = frame + 1 + hlen;
688 182 : db_len = nframe - 1 - hlen;
689 :
690 : /* Step 3c and 3d: seed = maskedSeed ^ mgf(maskedDB, hlen). */
691 182 : if (mgf1 (seed, hlen, masked_db, db_len, algo))
692 0 : failed = 1;
693 3822 : for (n = 0; n < hlen; n++)
694 3640 : seed[n] ^= masked_seed[n];
695 :
696 : /* Step 3e and 3f: db = maskedDB ^ mgf(seed, db_len). */
697 182 : if (mgf1 (db, db_len, seed, hlen, algo))
698 0 : failed = 1;
699 20850 : for (n = 0; n < db_len; n++)
700 20668 : 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 182 : if (memcmp (lhash, db, hlen))
705 26 : failed = 1;
706 13113 : for (n = hlen; n < db_len; n++)
707 13113 : if (db[n] == 0x01)
708 182 : break;
709 182 : if (n == db_len)
710 0 : failed = 1;
711 182 : if (frame[0])
712 0 : failed = 1;
713 :
714 182 : xfree (lhash);
715 182 : xfree (frame);
716 182 : if (failed)
717 : {
718 26 : xfree (seed);
719 26 : 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 156 : n++;
726 156 : memmove (seed, db + n, db_len - n);
727 156 : *r_result = seed;
728 156 : *r_resultlen = db_len - n;
729 156 : seed = NULL;
730 :
731 156 : if (DBG_CIPHER)
732 0 : log_printhex ("value extracted from OAEP encoded data",
733 : *r_result, *r_resultlen);
734 :
735 156 : 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 108 : _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 108 : gcry_err_code_t rc = 0;
784 : size_t hlen; /* Length of the hash digest. */
785 108 : unsigned char *em = NULL; /* Encoded message. */
786 108 : size_t emlen = (nbits+7)/8; /* Length in bytes of EM. */
787 : unsigned char *h; /* Points into EM. */
788 108 : 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 108 : hlen = _gcry_md_get_algo_dlen (algo);
800 108 : gcry_assert (hlen); /* We expect a valid ALGO here. */
801 :
802 : /* Allocate a help buffer and setup some pointers. */
803 108 : buflen = 8 + hlen + saltlen + (emlen - hlen - 1);
804 108 : buf = xtrymalloc (buflen);
805 108 : if (!buf)
806 : {
807 0 : rc = gpg_err_code_from_syserror ();
808 0 : goto leave;
809 : }
810 108 : mhash = buf + 8;
811 108 : salt = mhash + hlen;
812 108 : 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 108 : if (valuelen != hlen)
817 : {
818 0 : rc = GPG_ERR_INV_LENGTH;
819 0 : goto leave;
820 : }
821 108 : memcpy (mhash, value, hlen);
822 :
823 : /* Step 3: Check length constraints. */
824 108 : if (emlen < hlen + saltlen + 2)
825 : {
826 0 : rc = GPG_ERR_TOO_SHORT;
827 0 : goto leave;
828 : }
829 :
830 : /* Allocate space for EM. */
831 108 : em = xtrymalloc (emlen);
832 108 : if (!em)
833 : {
834 0 : rc = gpg_err_code_from_syserror ();
835 0 : goto leave;
836 : }
837 108 : h = em + emlen - 1 - hlen;
838 :
839 : /* Step 4: Create a salt. */
840 108 : if (saltlen)
841 : {
842 108 : if (random_override)
843 : {
844 84 : if (random_override_len != saltlen)
845 : {
846 0 : rc = GPG_ERR_INV_ARG;
847 0 : goto leave;
848 : }
849 84 : memcpy (salt, random_override, saltlen);
850 : }
851 : else
852 24 : _gcry_randomize (salt, saltlen, GCRY_STRONG_RANDOM);
853 : }
854 :
855 : /* Step 5 and 6: M' = Hash(Padding1 || mHash || salt). */
856 108 : memset (buf, 0, 8); /* Padding. */
857 108 : _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 108 : p = em + emlen - 1 - hlen - saltlen - 1;
862 108 : memset (em, 0, p - em);
863 108 : *p++ = 0x01;
864 108 : memcpy (p, salt, saltlen);
865 :
866 : /* Step 9: dbmask = MGF(H, emlen - hlen - 1). */
867 108 : mgf1 (dbmask, emlen - hlen - 1, h, hlen, algo);
868 :
869 : /* Step 10: maskedDB = DB ^ dbMask */
870 12852 : for (n = 0, p = dbmask; n < emlen - hlen - 1; n++, p++)
871 12744 : em[n] ^= *p;
872 :
873 : /* Step 11: Set the leftmost bits to zero. */
874 108 : em[0] &= 0xFF >> (8 * emlen - nbits);
875 :
876 : /* Step 12: EM = maskedDB || H || 0xbc. */
877 108 : em[emlen-1] = 0xbc;
878 :
879 : /* Convert EM into an MPI. */
880 108 : rc = _gcry_mpi_scan (r_result, GCRYMPI_FMT_USG, em, emlen, NULL);
881 108 : if (!rc && DBG_CIPHER)
882 0 : log_mpidump ("PSS encoded data", *r_result);
883 :
884 : leave:
885 108 : if (em)
886 : {
887 108 : wipememory (em, emlen);
888 108 : xfree (em);
889 : }
890 108 : if (buf)
891 : {
892 108 : wipememory (buf, buflen);
893 108 : xfree (buf);
894 : }
895 108 : 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 108 : _gcry_rsa_pss_verify (gcry_mpi_t value, gcry_mpi_t encoded,
907 : unsigned int nbits, int algo, size_t saltlen)
908 : {
909 108 : gcry_err_code_t rc = 0;
910 : size_t hlen; /* Length of the hash digest. */
911 108 : unsigned char *em = NULL; /* Encoded message. */
912 108 : 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 108 : 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 108 : hlen = _gcry_md_get_algo_dlen (algo);
926 108 : 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 108 : buflen = 8 + hlen + saltlen;
941 108 : if (buflen < emlen - hlen - 1)
942 108 : buflen = emlen - hlen - 1;
943 108 : buflen += hlen;
944 108 : buf = xtrymalloc (buflen);
945 108 : if (!buf)
946 : {
947 0 : rc = gpg_err_code_from_syserror ();
948 0 : goto leave;
949 : }
950 108 : dbmask = buf;
951 108 : 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 108 : rc = octet_string_from_mpi (NULL, mhash, value, hlen);
956 108 : if (rc)
957 0 : goto leave;
958 :
959 : /* Convert the signature into an octet string. */
960 108 : rc = octet_string_from_mpi (&em, NULL, encoded, emlen);
961 108 : if (rc)
962 0 : 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 108 : if (emlen < hlen + saltlen + 2)
971 : {
972 0 : rc = GPG_ERR_TOO_SHORT; /* For the hash and saltlen. */
973 0 : goto leave;
974 : }
975 :
976 : /* Step 4: Check last octet. */
977 108 : if (em[emlen - 1] != 0xbc)
978 : {
979 0 : rc = GPG_ERR_BAD_SIGNATURE;
980 0 : goto leave;
981 : }
982 :
983 : /* Step 5: Split EM. */
984 108 : h = em + emlen - 1 - hlen;
985 :
986 : /* Step 6: Check the leftmost bits. */
987 108 : if ((em[0] & ~(0xFF >> (8 * emlen - nbits))))
988 : {
989 0 : rc = GPG_ERR_BAD_SIGNATURE;
990 0 : goto leave;
991 : }
992 :
993 : /* Step 7: dbmask = MGF(H, emlen - hlen - 1). */
994 108 : mgf1 (dbmask, emlen - hlen - 1, h, hlen, algo);
995 :
996 : /* Step 8: maskedDB = DB ^ dbMask. */
997 12852 : for (n = 0, p = dbmask; n < emlen - hlen - 1; n++, p++)
998 12744 : em[n] ^= *p;
999 :
1000 : /* Step 9: Set leftmost bits in DB to zero. */
1001 108 : em[0] &= 0xFF >> (8 * emlen - nbits);
1002 :
1003 : /* Step 10: Check the padding of DB. */
1004 108 : for (n = 0; n < emlen - hlen - saltlen - 2 && !em[n]; n++)
1005 : ;
1006 108 : if (n != emlen - hlen - saltlen - 2 || em[n++] != 1)
1007 : {
1008 0 : rc = GPG_ERR_BAD_SIGNATURE;
1009 0 : goto leave;
1010 : }
1011 :
1012 : /* Step 11: Extract salt from DB. */
1013 108 : salt = em + n;
1014 :
1015 : /* Step 12: M' = (0x)00 00 00 00 00 00 00 00 || mHash || salt */
1016 108 : memset (buf, 0, 8);
1017 108 : memcpy (buf+8, mhash, hlen);
1018 108 : memcpy (buf+8+hlen, salt, saltlen);
1019 :
1020 : /* Step 13: H' = Hash(M'). */
1021 108 : _gcry_md_hash_buffer (algo, buf, buf, 8 + hlen + saltlen);
1022 :
1023 : /* Step 14: Check H == H'. */
1024 108 : rc = memcmp (h, buf, hlen) ? GPG_ERR_BAD_SIGNATURE : GPG_ERR_NO_ERROR;
1025 :
1026 : leave:
1027 108 : if (em)
1028 : {
1029 108 : wipememory (em, emlen);
1030 108 : xfree (em);
1031 : }
1032 108 : if (buf)
1033 : {
1034 108 : wipememory (buf, buflen);
1035 108 : xfree (buf);
1036 : }
1037 108 : return rc;
1038 : }
|
