gmp: Fix RSA signature verification for m >= n
[strongswan.git] / src / libstrongswan / plugins / gmp / gmp_rsa_public_key.c
1 /*
2 * Copyright (C) 2005-2009 Martin Willi
3 * Copyright (C) 2005 Jan Hutter
4 * Hochschule fuer Technik Rapperswil
5 *
6 * This program is free software; you can redistribute it and/or modify it
7 * under the terms of the GNU General Public License as published by the
8 * Free Software Foundation; either version 2 of the License, or (at your
9 * option) any later version. See <http://www.fsf.org/copyleft/gpl.txt>.
10 *
11 * This program is distributed in the hope that it will be useful, but
12 * WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
13 * or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
14 * for more details.
15 */
16
17 #include <gmp.h>
18 #include <sys/stat.h>
19 #include <unistd.h>
20 #include <stdio.h>
21 #include <string.h>
22
23 #include "gmp_rsa_public_key.h"
24
25 #include <utils/debug.h>
26 #include <asn1/oid.h>
27 #include <asn1/asn1.h>
28 #include <asn1/asn1_parser.h>
29 #include <crypto/hashers/hasher.h>
30
31 #ifdef HAVE_MPZ_POWM_SEC
32 # undef mpz_powm
33 # define mpz_powm mpz_powm_sec
34 #endif
35
36 typedef struct private_gmp_rsa_public_key_t private_gmp_rsa_public_key_t;
37
38 /**
39 * Private data structure with signing context.
40 */
41 struct private_gmp_rsa_public_key_t {
42 /**
43 * Public interface for this signer.
44 */
45 gmp_rsa_public_key_t public;
46
47 /**
48 * Public modulus.
49 */
50 mpz_t n;
51
52 /**
53 * Public exponent.
54 */
55 mpz_t e;
56
57 /**
58 * Keysize in bytes.
59 */
60 size_t k;
61
62 /**
63 * reference counter
64 */
65 refcount_t ref;
66 };
67
68 /**
69 * Shared functions defined in gmp_rsa_private_key.c
70 */
71 extern chunk_t gmp_mpz_to_chunk(const mpz_t value);
72
73 /**
74 * RSAEP algorithm specified in PKCS#1.
75 */
76 static chunk_t rsaep(private_gmp_rsa_public_key_t *this, chunk_t data)
77 {
78 mpz_t m, c;
79 chunk_t encrypted;
80
81 mpz_init(m);
82 mpz_import(m, data.len, 1, 1, 1, 0, data.ptr);
83
84 if (mpz_cmp_ui(m, 0) <= 0 || mpz_cmp(m, this->n) >= 0)
85 { /* m must be <= n-1, and while 0 is technically a valid value, it
86 * doesn't really make sense here, so we filter that too */
87 mpz_clear(m);
88 return chunk_empty;
89 }
90
91 mpz_init(c);
92 mpz_powm(c, m, this->e, this->n);
93
94 encrypted.len = this->k;
95 encrypted.ptr = mpz_export(NULL, NULL, 1, encrypted.len, 1, 0, c);
96 if (encrypted.ptr == NULL)
97 {
98 encrypted.len = 0;
99 }
100
101 mpz_clear(c);
102 mpz_clear(m);
103
104 return encrypted;
105 }
106
107 /**
108 * RSAVP1 algorithm specified in PKCS#1.
109 */
110 static chunk_t rsavp1(private_gmp_rsa_public_key_t *this, chunk_t data)
111 {
112 return rsaep(this, data);
113 }
114
115 /**
116 * ASN.1 definition of digestInfo
117 */
118 static const asn1Object_t digestInfoObjects[] = {
119 { 0, "digestInfo", ASN1_SEQUENCE, ASN1_OBJ }, /* 0 */
120 { 1, "digestAlgorithm", ASN1_EOC, ASN1_RAW }, /* 1 */
121 { 1, "digest", ASN1_OCTET_STRING, ASN1_BODY }, /* 2 */
122 { 0, "exit", ASN1_EOC, ASN1_EXIT }
123 };
124 #define DIGEST_INFO 0
125 #define DIGEST_INFO_ALGORITHM 1
126 #define DIGEST_INFO_DIGEST 2
127
128 /**
129 * Verification of an EMPSA PKCS1 signature described in PKCS#1
130 */
131 static bool verify_emsa_pkcs1_signature(private_gmp_rsa_public_key_t *this,
132 hash_algorithm_t algorithm,
133 chunk_t data, chunk_t signature)
134 {
135 chunk_t em_ori, em;
136 bool success = FALSE;
137
138 /* remove any preceding 0-bytes from signature */
139 while (signature.len && *(signature.ptr) == 0x00)
140 {
141 signature = chunk_skip(signature, 1);
142 }
143
144 if (signature.len == 0 || signature.len > this->k)
145 {
146 return FALSE;
147 }
148
149 /* unpack signature */
150 em_ori = em = rsavp1(this, signature);
151
152 /* result should look like this:
153 * EM = 0x00 || 0x01 || PS || 0x00 || T.
154 * PS = 0xFF padding, with length to fill em
155 * T = oid || hash
156 */
157
158 /* check magic bytes */
159 if (em.len < 2 || *(em.ptr) != 0x00 || *(em.ptr+1) != 0x01)
160 {
161 goto end;
162 }
163 em = chunk_skip(em, 2);
164
165 /* find magic 0x00 */
166 while (em.len > 0)
167 {
168 if (*em.ptr == 0x00)
169 {
170 /* found magic byte, stop */
171 em = chunk_skip(em, 1);
172 break;
173 }
174 else if (*em.ptr != 0xFF)
175 {
176 /* bad padding, decryption failed ?!*/
177 goto end;
178 }
179 em = chunk_skip(em, 1);
180 }
181
182 if (em.len == 0)
183 {
184 /* no digestInfo found */
185 goto end;
186 }
187
188 if (algorithm == HASH_UNKNOWN)
189 { /* IKEv1 signatures without digestInfo */
190 if (em.len != data.len)
191 {
192 DBG1(DBG_LIB, "hash size in signature is %u bytes instead of"
193 " %u bytes", em.len, data.len);
194 goto end;
195 }
196 success = memeq_const(em.ptr, data.ptr, data.len);
197 }
198 else
199 { /* IKEv2 and X.509 certificate signatures */
200 asn1_parser_t *parser;
201 chunk_t object;
202 int objectID;
203 hash_algorithm_t hash_algorithm = HASH_UNKNOWN;
204
205 DBG2(DBG_LIB, "signature verification:");
206 parser = asn1_parser_create(digestInfoObjects, em);
207
208 while (parser->iterate(parser, &objectID, &object))
209 {
210 switch (objectID)
211 {
212 case DIGEST_INFO:
213 {
214 if (em.len > object.len)
215 {
216 DBG1(DBG_LIB, "digestInfo field in signature is"
217 " followed by %u surplus bytes",
218 em.len - object.len);
219 goto end_parser;
220 }
221 break;
222 }
223 case DIGEST_INFO_ALGORITHM:
224 {
225 int hash_oid = asn1_parse_algorithmIdentifier(object,
226 parser->get_level(parser)+1, NULL);
227
228 hash_algorithm = hasher_algorithm_from_oid(hash_oid);
229 if (hash_algorithm == HASH_UNKNOWN || hash_algorithm != algorithm)
230 {
231 DBG1(DBG_LIB, "expected hash algorithm %N, but found"
232 " %N (OID: %#B)", hash_algorithm_names, algorithm,
233 hash_algorithm_names, hash_algorithm, &object);
234 goto end_parser;
235 }
236 break;
237 }
238 case DIGEST_INFO_DIGEST:
239 {
240 chunk_t hash;
241 hasher_t *hasher;
242
243 hasher = lib->crypto->create_hasher(lib->crypto, hash_algorithm);
244 if (hasher == NULL)
245 {
246 DBG1(DBG_LIB, "hash algorithm %N not supported",
247 hash_algorithm_names, hash_algorithm);
248 goto end_parser;
249 }
250
251 if (object.len != hasher->get_hash_size(hasher))
252 {
253 DBG1(DBG_LIB, "hash size in signature is %u bytes"
254 " instead of %u bytes", object.len,
255 hasher->get_hash_size(hasher));
256 hasher->destroy(hasher);
257 goto end_parser;
258 }
259
260 /* build our own hash and compare */
261 if (!hasher->allocate_hash(hasher, data, &hash))
262 {
263 hasher->destroy(hasher);
264 goto end_parser;
265 }
266 hasher->destroy(hasher);
267 success = memeq_const(object.ptr, hash.ptr, hash.len);
268 free(hash.ptr);
269 break;
270 }
271 default:
272 break;
273 }
274 }
275
276 end_parser:
277 success &= parser->success(parser);
278 parser->destroy(parser);
279 }
280
281 end:
282 free(em_ori.ptr);
283 return success;
284 }
285
286 METHOD(public_key_t, get_type, key_type_t,
287 private_gmp_rsa_public_key_t *this)
288 {
289 return KEY_RSA;
290 }
291
292 METHOD(public_key_t, verify, bool,
293 private_gmp_rsa_public_key_t *this, signature_scheme_t scheme,
294 chunk_t data, chunk_t signature)
295 {
296 switch (scheme)
297 {
298 case SIGN_RSA_EMSA_PKCS1_NULL:
299 return verify_emsa_pkcs1_signature(this, HASH_UNKNOWN, data, signature);
300 case SIGN_RSA_EMSA_PKCS1_SHA2_224:
301 return verify_emsa_pkcs1_signature(this, HASH_SHA224, data, signature);
302 case SIGN_RSA_EMSA_PKCS1_SHA2_256:
303 return verify_emsa_pkcs1_signature(this, HASH_SHA256, data, signature);
304 case SIGN_RSA_EMSA_PKCS1_SHA2_384:
305 return verify_emsa_pkcs1_signature(this, HASH_SHA384, data, signature);
306 case SIGN_RSA_EMSA_PKCS1_SHA2_512:
307 return verify_emsa_pkcs1_signature(this, HASH_SHA512, data, signature);
308 case SIGN_RSA_EMSA_PKCS1_SHA3_224:
309 return verify_emsa_pkcs1_signature(this, HASH_SHA3_224, data, signature);
310 case SIGN_RSA_EMSA_PKCS1_SHA3_256:
311 return verify_emsa_pkcs1_signature(this, HASH_SHA3_256, data, signature);
312 case SIGN_RSA_EMSA_PKCS1_SHA3_384:
313 return verify_emsa_pkcs1_signature(this, HASH_SHA3_384, data, signature);
314 case SIGN_RSA_EMSA_PKCS1_SHA3_512:
315 return verify_emsa_pkcs1_signature(this, HASH_SHA3_512, data, signature);
316 case SIGN_RSA_EMSA_PKCS1_SHA1:
317 return verify_emsa_pkcs1_signature(this, HASH_SHA1, data, signature);
318 case SIGN_RSA_EMSA_PKCS1_MD5:
319 return verify_emsa_pkcs1_signature(this, HASH_MD5, data, signature);
320 default:
321 DBG1(DBG_LIB, "signature scheme %N not supported in RSA",
322 signature_scheme_names, scheme);
323 return FALSE;
324 }
325 }
326
327 #define MIN_PS_PADDING 8
328
329 METHOD(public_key_t, encrypt_, bool,
330 private_gmp_rsa_public_key_t *this, encryption_scheme_t scheme,
331 chunk_t plain, chunk_t *crypto)
332 {
333 chunk_t em;
334 u_char *pos;
335 int padding;
336 rng_t *rng;
337
338 if (scheme != ENCRYPT_RSA_PKCS1)
339 {
340 DBG1(DBG_LIB, "encryption scheme %N not supported",
341 encryption_scheme_names, scheme);
342 return FALSE;
343 }
344 /* number of pseudo-random padding octets */
345 padding = this->k - plain.len - 3;
346 if (padding < MIN_PS_PADDING)
347 {
348 DBG1(DBG_LIB, "pseudo-random padding must be at least %d octets",
349 MIN_PS_PADDING);
350 return FALSE;
351 }
352 rng = lib->crypto->create_rng(lib->crypto, RNG_WEAK);
353 if (rng == NULL)
354 {
355 DBG1(DBG_LIB, "no random generator available");
356 return FALSE;
357 }
358
359 /* padding according to PKCS#1 7.2.1 (RSAES-PKCS1-v1.5-ENCRYPT) */
360 DBG2(DBG_LIB, "padding %u bytes of data to the rsa modulus size of"
361 " %u bytes", plain.len, this->k);
362 em.len = this->k;
363 em.ptr = malloc(em.len);
364 pos = em.ptr;
365 *pos++ = 0x00;
366 *pos++ = 0x02;
367
368 /* fill with pseudo random octets */
369 if (!rng_get_bytes_not_zero(rng, padding, pos, TRUE))
370 {
371 DBG1(DBG_LIB, "failed to allocate padding");
372 chunk_clear(&em);
373 rng->destroy(rng);
374 return FALSE;
375 }
376 rng->destroy(rng);
377
378 pos += padding;
379
380 /* append the padding terminator */
381 *pos++ = 0x00;
382
383 /* now add the data */
384 memcpy(pos, plain.ptr, plain.len);
385 DBG3(DBG_LIB, "padded data before rsa encryption: %B", &em);
386
387 /* rsa encryption using PKCS#1 RSAEP */
388 *crypto = rsaep(this, em);
389 DBG3(DBG_LIB, "rsa encrypted data: %B", crypto);
390 chunk_clear(&em);
391 return TRUE;
392 }
393
394 METHOD(public_key_t, get_keysize, int,
395 private_gmp_rsa_public_key_t *this)
396 {
397 return mpz_sizeinbase(this->n, 2);
398 }
399
400 METHOD(public_key_t, get_encoding, bool,
401 private_gmp_rsa_public_key_t *this, cred_encoding_type_t type,
402 chunk_t *encoding)
403 {
404 chunk_t n, e;
405 bool success;
406
407 n = gmp_mpz_to_chunk(this->n);
408 e = gmp_mpz_to_chunk(this->e);
409
410 success = lib->encoding->encode(lib->encoding, type, NULL, encoding,
411 CRED_PART_RSA_MODULUS, n, CRED_PART_RSA_PUB_EXP, e, CRED_PART_END);
412 chunk_free(&n);
413 chunk_free(&e);
414
415 return success;
416 }
417
418 METHOD(public_key_t, get_fingerprint, bool,
419 private_gmp_rsa_public_key_t *this, cred_encoding_type_t type, chunk_t *fp)
420 {
421 chunk_t n, e;
422 bool success;
423
424 if (lib->encoding->get_cache(lib->encoding, type, this, fp))
425 {
426 return TRUE;
427 }
428 n = gmp_mpz_to_chunk(this->n);
429 e = gmp_mpz_to_chunk(this->e);
430
431 success = lib->encoding->encode(lib->encoding, type, this, fp,
432 CRED_PART_RSA_MODULUS, n, CRED_PART_RSA_PUB_EXP, e, CRED_PART_END);
433 chunk_free(&n);
434 chunk_free(&e);
435
436 return success;
437 }
438
439 METHOD(public_key_t, get_ref, public_key_t*,
440 private_gmp_rsa_public_key_t *this)
441 {
442 ref_get(&this->ref);
443 return &this->public.key;
444 }
445
446 METHOD(public_key_t, destroy, void,
447 private_gmp_rsa_public_key_t *this)
448 {
449 if (ref_put(&this->ref))
450 {
451 mpz_clear(this->n);
452 mpz_clear(this->e);
453 lib->encoding->clear_cache(lib->encoding, this);
454 free(this);
455 }
456 }
457
458 /**
459 * See header.
460 */
461 gmp_rsa_public_key_t *gmp_rsa_public_key_load(key_type_t type, va_list args)
462 {
463 private_gmp_rsa_public_key_t *this;
464 chunk_t n, e;
465
466 n = e = chunk_empty;
467 while (TRUE)
468 {
469 switch (va_arg(args, builder_part_t))
470 {
471 case BUILD_RSA_MODULUS:
472 n = va_arg(args, chunk_t);
473 continue;
474 case BUILD_RSA_PUB_EXP:
475 e = va_arg(args, chunk_t);
476 continue;
477 case BUILD_END:
478 break;
479 default:
480 return NULL;
481 }
482 break;
483 }
484 if (!e.len || !n.len || (n.ptr[n.len-1] & 0x01) == 0)
485 {
486 return NULL;
487 }
488
489 INIT(this,
490 .public = {
491 .key = {
492 .get_type = _get_type,
493 .verify = _verify,
494 .encrypt = _encrypt_,
495 .equals = public_key_equals,
496 .get_keysize = _get_keysize,
497 .get_fingerprint = _get_fingerprint,
498 .has_fingerprint = public_key_has_fingerprint,
499 .get_encoding = _get_encoding,
500 .get_ref = _get_ref,
501 .destroy = _destroy,
502 },
503 },
504 .ref = 1,
505 );
506
507 mpz_init(this->n);
508 mpz_init(this->e);
509
510 mpz_import(this->n, n.len, 1, 1, 1, 0, n.ptr);
511 mpz_import(this->e, e.len, 1, 1, 1, 0, e.ptr);
512
513 this->k = (mpz_sizeinbase(this->n, 2) + 7) / BITS_PER_BYTE;
514
515 if (!mpz_sgn(this->e))
516 {
517 destroy(this);
518 return NULL;
519 }
520 return &this->public;
521 }