xref: /illumos-gate/usr/src/common/crypto/dsa/dsa_impl.c (revision 5633e4f8e97f7c73a0a130a449ccfd2c034561ce) 
1 /*
2  * CDDL HEADER START
3  *
4  * The contents of this file are subject to the terms of the
5  * Common Development and Distribution License (the "License").
6  * You may not use this file except in compliance with the License.
7  *
8  * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE
9  * or http://www.opensolaris.org/os/licensing.
10  * See the License for the specific language governing permissions
11  * and limitations under the License.
12  *
13  * When distributing Covered Code, include this CDDL HEADER in each
14  * file and include the License file at usr/src/OPENSOLARIS.LICENSE.
15  * If applicable, add the following below this CDDL HEADER, with the
16  * fields enclosed by brackets "[]" replaced with your own identifying
17  * information: Portions Copyright [yyyy] [name of copyright owner]
18  *
19  * CDDL HEADER END
20  */
21 
22 /*
23  * Copyright (c) 2003, 2010, Oracle and/or its affiliates. All rights reserved.
24  */
25 
26 /*
27  * This file contains DSA helper routines common to
28  * the PKCS11 soft token code and the kernel DSA code.
29  */
30 
31 #include <sys/types.h>
32 #include <bignum.h>
33 
34 #ifdef _KERNEL
35 #include <sys/param.h>
36 #else
37 #include <strings.h>
38 #include <cryptoutil.h>
39 #endif
40 
41 #include <sys/crypto/common.h>
42 #include "dsa_impl.h"
43 
44 
45 static CK_RV
46 convert_rv(BIG_ERR_CODE err)
47 {
48 	switch (err) {
49 
50 	case BIG_OK:
51 		return (CKR_OK);
52 
53 	case BIG_NO_MEM:
54 		return (CKR_HOST_MEMORY);
55 
56 	case BIG_NO_RANDOM:
57 		return (CKR_DEVICE_ERROR);
58 
59 	case BIG_INVALID_ARGS:
60 		return (CKR_ARGUMENTS_BAD);
61 
62 	case BIG_DIV_BY_0:
63 	default:
64 		return (CKR_GENERAL_ERROR);
65 	}
66 }
67 
68 /* size is in bits */
69 static BIG_ERR_CODE
70 DSA_key_init(DSAkey *key, int size)
71 {
72 	BIG_ERR_CODE err = BIG_OK;
73 	int len, len160;
74 
75 	len = BITLEN2BIGNUMLEN(size);
76 	len160 = BIG_CHUNKS_FOR_160BITS;
77 	key->size = size;
78 	if ((err = big_init(&(key->q), len160)) != BIG_OK)
79 		return (err);
80 	if ((err = big_init(&(key->p), len)) != BIG_OK)
81 		goto ret1;
82 	if ((err = big_init(&(key->g), len)) != BIG_OK)
83 		goto ret2;
84 	if ((err = big_init(&(key->x), len160)) != BIG_OK)
85 		goto ret3;
86 	if ((err = big_init(&(key->y), len)) != BIG_OK)
87 		goto ret4;
88 	if ((err = big_init(&(key->k), len160)) != BIG_OK)
89 		goto ret5;
90 	if ((err = big_init(&(key->r), len160)) != BIG_OK)
91 		goto ret6;
92 	if ((err = big_init(&(key->s), len160)) != BIG_OK)
93 		goto ret7;
94 	if ((err = big_init(&(key->v), len160)) != BIG_OK)
95 		goto ret8;
96 
97 	return (BIG_OK);
98 
99 ret8:
100 	big_finish(&(key->s));
101 ret7:
102 	big_finish(&(key->r));
103 ret6:
104 	big_finish(&(key->k));
105 ret5:
106 	big_finish(&(key->y));
107 ret4:
108 	big_finish(&(key->x));
109 ret3:
110 	big_finish(&(key->g));
111 ret2:
112 	big_finish(&(key->p));
113 ret1:
114 	big_finish(&(key->q));
115 	return (err);
116 }
117 
118 static void
119 DSA_key_finish(DSAkey *key)
120 {
121 
122 	big_finish(&(key->v));
123 	big_finish(&(key->s));
124 	big_finish(&(key->r));
125 	big_finish(&(key->k));
126 	big_finish(&(key->y));
127 	big_finish(&(key->x));
128 	big_finish(&(key->g));
129 	big_finish(&(key->p));
130 	big_finish(&(key->q));
131 
132 }
133 
134 /*
135  * Generate DSA private x and public y from prime p, subprime q, and base g.
136  */
137 static CK_RV
138 generate_dsa_key(DSAkey *key, int (*rfunc)(void *, size_t))
139 {
140 	BIG_ERR_CODE err;
141 	int (*rf)(void *, size_t);
142 
143 	rf = rfunc;
144 	if (rf == NULL) {
145 #ifdef _KERNEL
146 		rf = random_get_pseudo_bytes;
147 #else
148 		rf = pkcs11_get_urandom;
149 #endif
150 	}
151 	do {
152 		if ((err = big_random(&(key->x), DSA_SUBPRIME_BITS, rf)) !=
153 		    BIG_OK) {
154 			return (convert_rv(err));
155 		}
156 	} while (big_cmp_abs(&(key->x), &(key->q)) > 0);
157 
158 	if ((err = big_modexp(&(key->y), &(key->g), (&key->x), (&key->p),
159 	    NULL)) != BIG_OK)
160 		return (convert_rv(err));
161 
162 	return (CKR_OK);
163 }
164 
165 CK_RV
166 dsa_genkey_pair(DSAbytekey *bkey)
167 {
168 	CK_RV rv = CKR_OK;
169 	BIG_ERR_CODE brv;
170 	DSAkey	dsakey;
171 	uint32_t prime_bytes;
172 	uint32_t subprime_bytes;
173 
174 	prime_bytes = CRYPTO_BITS2BYTES(bkey->prime_bits);
175 
176 	if ((prime_bytes < MIN_DSA_KEY_LEN) ||
177 	    (prime_bytes > MAX_DSA_KEY_LEN)) {
178 		return (CKR_ATTRIBUTE_VALUE_INVALID);
179 	}
180 
181 	/*
182 	 * There is no check here that prime_bits must be a multiple of 64,
183 	 * and thus that prime_bytes must be a multiple of 8.
184 	 */
185 
186 	subprime_bytes = CRYPTO_BITS2BYTES(bkey->subprime_bits);
187 
188 	if (subprime_bytes != DSA_SUBPRIME_BYTES) {
189 		return (CKR_ATTRIBUTE_VALUE_INVALID);
190 	}
191 
192 	if (bkey->public_y == NULL || bkey->private_x == NULL) {
193 		return (CKR_ARGUMENTS_BAD);
194 	}
195 
196 	/*
197 	 * Initialize the DSA key.
198 	 * Note: big_extend takes length in words.
199 	 */
200 	if ((brv = DSA_key_init(&dsakey, bkey->prime_bits)) != BIG_OK) {
201 		rv = convert_rv(brv);
202 		goto cleanexit;
203 	}
204 
205 	/* Convert prime p to bignum. */
206 	if ((brv = big_extend(&(dsakey.p),
207 	    CHARLEN2BIGNUMLEN(prime_bytes))) != BIG_OK) {
208 		rv = convert_rv(brv);
209 		goto cleanexit;
210 	}
211 	bytestring2bignum(&(dsakey.p), bkey->prime, prime_bytes);
212 
213 	/* Convert prime q to bignum. */
214 	if ((brv = big_extend(&(dsakey.q),
215 	    CHARLEN2BIGNUMLEN(subprime_bytes))) != BIG_OK) {
216 		rv = convert_rv(brv);
217 		goto cleanexit;
218 	}
219 	bytestring2bignum(&(dsakey.q), bkey->subprime, subprime_bytes);
220 
221 	/* Convert base g to bignum. */
222 	if ((brv = big_extend(&(dsakey.g),
223 	    CHARLEN2BIGNUMLEN(bkey->base_bytes))) != BIG_OK) {
224 		rv = convert_rv(brv);
225 		goto cleanexit;
226 	}
227 	bytestring2bignum(&(dsakey.g), bkey->base, bkey->base_bytes);
228 
229 	/*
230 	 * Generate DSA key pair.
231 	 * Note: bignum.len is length of value in words.
232 	 */
233 	if ((rv = generate_dsa_key(&dsakey, bkey->rfunc)) !=
234 	    CKR_OK) {
235 		goto cleanexit;
236 	}
237 
238 	bkey->public_y_bits = CRYPTO_BYTES2BITS(prime_bytes);
239 	bignum2bytestring(bkey->public_y, &(dsakey.y), prime_bytes);
240 
241 	bkey->private_x_bits = CRYPTO_BYTES2BITS(DSA_SUBPRIME_BYTES);
242 	bignum2bytestring(bkey->private_x, &(dsakey.x), DSA_SUBPRIME_BYTES);
243 
244 cleanexit:
245 	DSA_key_finish(&dsakey);
246 
247 	return (rv);
248 }
249 
250 /*
251  * DSA sign operation
252  */
253 CK_RV
254 dsa_sign(DSAbytekey *bkey, uchar_t *in, uint32_t inlen, uchar_t *out)
255 {
256 	CK_RV rv = CKR_OK;
257 	BIG_ERR_CODE brv;
258 	DSAkey dsakey;
259 	BIGNUM msg, tmp, tmp1;
260 	uint32_t prime_bytes;
261 	uint32_t subprime_bytes;
262 	uint32_t value_bytes;
263 	int (*rf)(void *, size_t);
264 
265 	prime_bytes = CRYPTO_BITS2BYTES(bkey->prime_bits);
266 	subprime_bytes = CRYPTO_BITS2BYTES(bkey->subprime_bits);
267 
268 	if (DSA_SUBPRIME_BYTES != subprime_bytes) {
269 		return (CKR_KEY_SIZE_RANGE);
270 	}
271 
272 	value_bytes = CRYPTO_BITS2BYTES(bkey->private_x_bits);	/* len of x */
273 
274 	if (DSA_SUBPRIME_BYTES < value_bytes) {
275 		return (CKR_KEY_SIZE_RANGE);
276 	}
277 
278 	/*
279 	 * Initialize the DH key.
280 	 * Note: big_extend takes length in words.
281 	 */
282 	if ((brv = DSA_key_init(&dsakey, bkey->prime_bits)) != BIG_OK) {
283 		return (CKR_HOST_MEMORY);
284 	}
285 
286 	if ((brv = big_extend(&(dsakey.p),
287 	    CHARLEN2BIGNUMLEN(prime_bytes))) != BIG_OK) {
288 		rv = convert_rv(brv);
289 		goto clean1;
290 	}
291 	bytestring2bignum(&(dsakey.p), bkey->prime, prime_bytes);
292 
293 	if ((brv = big_extend(&(dsakey.q),
294 	    CHARLEN2BIGNUMLEN(subprime_bytes))) != BIG_OK) {
295 		rv = convert_rv(brv);
296 		goto clean1;
297 	}
298 	bytestring2bignum(&(dsakey.q), bkey->subprime, subprime_bytes);
299 
300 	if ((brv = big_extend(&(dsakey.g),
301 	    CHARLEN2BIGNUMLEN(bkey->base_bytes))) != BIG_OK) {
302 		rv = convert_rv(brv);
303 		goto clean1;
304 	}
305 	bytestring2bignum(&(dsakey.g), bkey->base, bkey->base_bytes);
306 
307 	if ((brv = big_extend(&(dsakey.x),
308 	    CHARLEN2BIGNUMLEN(value_bytes))) != BIG_OK) {
309 		rv = convert_rv(brv);
310 		goto clean1;
311 	}
312 	bytestring2bignum(&(dsakey.x), bkey->private_x, value_bytes);
313 
314 	if ((brv = big_init(&msg, BIG_CHUNKS_FOR_160BITS)) != BIG_OK) {
315 		rv = convert_rv(brv);
316 		goto clean1;
317 	}
318 	bytestring2bignum(&msg, in, inlen);
319 
320 	/*
321 	 * Compute signature.
322 	 */
323 	if ((brv = big_init(&tmp, CHARLEN2BIGNUMLEN(prime_bytes) +
324 	    2 * BIG_CHUNKS_FOR_160BITS + 1)) != BIG_OK) {
325 		rv = convert_rv(brv);
326 		goto clean2;
327 	}
328 	if ((brv = big_init(&tmp1, 2 * BIG_CHUNKS_FOR_160BITS + 1)) != BIG_OK) {
329 		rv = convert_rv(brv);
330 		goto clean3;
331 	}
332 
333 	rf = bkey->rfunc;
334 	if (rf == NULL) {
335 #ifdef _KERNEL
336 		rf = random_get_pseudo_bytes;
337 #else
338 		rf = pkcs11_get_urandom;
339 #endif
340 	}
341 	if ((brv = big_random(&(dsakey.k), DSA_SUBPRIME_BITS, rf)) != BIG_OK) {
342 		rv = convert_rv(brv);
343 		goto clean4;
344 	}
345 
346 	if ((brv = big_div_pos(NULL, &(dsakey.k), &(dsakey.k),
347 	    &(dsakey.q))) != BIG_OK) {
348 		rv = convert_rv(brv);
349 		goto clean4;
350 	}
351 
352 	if ((brv = big_modexp(&tmp, &(dsakey.g), &(dsakey.k), &(dsakey.p),
353 	    NULL)) != BIG_OK) {
354 		rv = convert_rv(brv);
355 		goto clean4;
356 	}
357 
358 	if ((brv = big_div_pos(NULL, &(dsakey.r), &tmp, &(dsakey.q))) !=
359 	    BIG_OK) {
360 		rv = convert_rv(brv);
361 		goto clean4;
362 	}
363 
364 
365 	if ((brv = big_ext_gcd_pos(NULL, NULL, &tmp, &(dsakey.q),
366 	    &(dsakey.k))) != BIG_OK) {
367 		rv = convert_rv(brv);
368 		goto clean4;
369 	}
370 
371 	if (tmp.sign == -1)
372 		if ((brv = big_add(&tmp, &tmp, &(dsakey.q))) != BIG_OK) {
373 			rv = convert_rv(brv);
374 			goto clean4;			/* tmp <- k^-1 */
375 		}
376 
377 	if ((brv = big_mul(&tmp1, &(dsakey.x), &(dsakey.r))) != BIG_OK) {
378 		rv = convert_rv(brv);
379 		goto clean4;
380 	}
381 
382 	if ((brv = big_add(&tmp1, &tmp1, &msg)) != BIG_OK) {
383 		rv = convert_rv(brv);
384 		goto clean4;
385 	}
386 
387 	if ((brv = big_mul(&tmp, &tmp1, &tmp)) != BIG_OK) {
388 		rv = convert_rv(brv);
389 		goto clean4;
390 	}
391 
392 	if ((brv = big_div_pos(NULL, &(dsakey.s), &tmp, &(dsakey.q))) !=
393 	    BIG_OK) {
394 		rv = convert_rv(brv);
395 		goto clean4;
396 	}
397 
398 	/*
399 	 * Signature is in DSA key r and s values, copy to out
400 	 */
401 	bignum2bytestring(out, &(dsakey.r), DSA_SUBPRIME_BYTES);
402 	bignum2bytestring(out + DSA_SUBPRIME_BYTES, &(dsakey.s),
403 	    DSA_SUBPRIME_BYTES);
404 
405 clean4:
406 	big_finish(&tmp1);
407 clean3:
408 	big_finish(&tmp);
409 clean2:
410 	big_finish(&msg);
411 clean1:
412 	DSA_key_finish(&dsakey);
413 
414 	return (rv);
415 }
416 
417 /*
418  * DSA verify operation
419  */
420 CK_RV
421 dsa_verify(DSAbytekey *bkey, uchar_t *data, uchar_t *sig)
422 {
423 	CK_RV rv = CKR_OK;
424 	BIG_ERR_CODE brv;
425 	DSAkey dsakey;
426 	BIGNUM msg, tmp1, tmp2, tmp3;
427 	uint32_t prime_bytes;
428 	uint32_t subprime_bytes;
429 	uint32_t value_bytes;
430 
431 	prime_bytes = CRYPTO_BITS2BYTES(bkey->prime_bits);
432 	subprime_bytes = CRYPTO_BITS2BYTES(bkey->subprime_bits);
433 
434 	if (DSA_SUBPRIME_BYTES != subprime_bytes) {
435 		return (CKR_KEY_SIZE_RANGE);
436 	}
437 
438 	if (prime_bytes < bkey->base_bytes) {
439 		return (CKR_KEY_SIZE_RANGE);
440 	}
441 
442 	value_bytes = CRYPTO_BITS2BYTES(bkey->public_y_bits);	/* len of y */
443 	if (prime_bytes < value_bytes) {
444 		return (CKR_KEY_SIZE_RANGE);
445 	}
446 
447 	/*
448 	 * Initialize the DSA key.
449 	 * Note: big_extend takes length in words.
450 	 */
451 	if (DSA_key_init(&dsakey, bkey->prime_bits) != BIG_OK) {
452 		return (CKR_HOST_MEMORY);
453 	}
454 
455 	if ((brv = big_extend(&(dsakey.p),
456 	    CHARLEN2BIGNUMLEN(prime_bytes))) != BIG_OK) {
457 		rv = convert_rv(brv);
458 		goto clean1;
459 	}
460 	bytestring2bignum(&(dsakey.p), bkey->prime, prime_bytes);
461 
462 	if ((brv = big_extend(&(dsakey.q),
463 	    CHARLEN2BIGNUMLEN(subprime_bytes))) != BIG_OK) {
464 		rv = convert_rv(brv);
465 		goto clean1;
466 	}
467 	bytestring2bignum(&(dsakey.q), bkey->subprime, subprime_bytes);
468 
469 	if ((brv = big_extend(&(dsakey.g),
470 	    CHARLEN2BIGNUMLEN(bkey->base_bytes))) != BIG_OK) {
471 		rv = convert_rv(brv);
472 		goto clean1;
473 	}
474 	bytestring2bignum(&(dsakey.g), bkey->base, bkey->base_bytes);
475 
476 	if ((brv = big_extend(&(dsakey.y),
477 	    CHARLEN2BIGNUMLEN(value_bytes))) != BIG_OK) {
478 		rv = convert_rv(brv);
479 		goto clean1;
480 	}
481 	bytestring2bignum(&(dsakey.y), bkey->public_y, value_bytes);
482 
483 	/*
484 	 * Copy signature to DSA key r and s values
485 	 */
486 	if ((brv = big_extend(&(dsakey.r),
487 	    CHARLEN2BIGNUMLEN(DSA_SUBPRIME_BYTES))) != BIG_OK) {
488 		rv = convert_rv(brv);
489 		goto clean1;
490 	}
491 	bytestring2bignum(&(dsakey.r), sig, DSA_SUBPRIME_BYTES);
492 
493 	if ((brv = big_extend(&(dsakey.s),
494 	    CHARLEN2BIGNUMLEN(DSA_SUBPRIME_BYTES))) != BIG_OK) {
495 		rv = convert_rv(brv);
496 		goto clean1;
497 	}
498 	bytestring2bignum(&(dsakey.s), sig + DSA_SUBPRIME_BYTES,
499 	    DSA_SUBPRIME_BYTES);
500 
501 
502 	if (big_init(&msg, BIG_CHUNKS_FOR_160BITS) != BIG_OK) {
503 		rv = CKR_HOST_MEMORY;
504 		goto clean1;
505 	}
506 	bytestring2bignum(&msg, data, DSA_SUBPRIME_BYTES);
507 
508 	if (big_init(&tmp1, 2 * CHARLEN2BIGNUMLEN(prime_bytes)) != BIG_OK) {
509 		rv = CKR_HOST_MEMORY;
510 		goto clean2;
511 	}
512 	if (big_init(&tmp2, CHARLEN2BIGNUMLEN(prime_bytes)) != BIG_OK) {
513 		rv = CKR_HOST_MEMORY;
514 		goto clean3;
515 	}
516 	if (big_init(&tmp3, 2 * BIG_CHUNKS_FOR_160BITS) != BIG_OK) {
517 		rv = CKR_HOST_MEMORY;
518 		goto clean4;
519 	}
520 
521 	/*
522 	 * Verify signature against msg.
523 	 */
524 	if (big_ext_gcd_pos(NULL, &tmp2, NULL, &(dsakey.s), &(dsakey.q)) !=
525 	    BIG_OK) {
526 		rv = convert_rv(brv);
527 		goto clean5;
528 	}
529 
530 	if (tmp2.sign == -1)
531 		if (big_add(&tmp2, &tmp2, &(dsakey.q)) != BIG_OK) {
532 			rv = convert_rv(brv);
533 			goto clean5;			/* tmp2 <- w */
534 		}
535 
536 	if (big_mul(&tmp1, &msg, &tmp2) != BIG_OK) {
537 		rv = convert_rv(brv);
538 		goto clean5;
539 	}
540 
541 	if (big_div_pos(NULL, &tmp1, &tmp1, &(dsakey.q)) != BIG_OK) {
542 		rv = convert_rv(brv);
543 		goto clean5;				/* tmp1 <- u_1 */
544 	}
545 
546 	if (big_mul(&tmp2, &tmp2, &(dsakey.r)) != BIG_OK) {
547 		rv = convert_rv(brv);
548 		goto clean5;
549 	}
550 
551 	if (big_div_pos(NULL, &tmp2, &tmp2, &(dsakey.q)) != BIG_OK) {
552 		rv = convert_rv(brv);
553 		goto clean5;				/* tmp2 <- u_2 */
554 	}
555 
556 	if (big_modexp(&tmp1, &(dsakey.g), &tmp1, &(dsakey.p), NULL) !=
557 	    BIG_OK) {
558 		rv = convert_rv(brv);
559 		goto clean5;
560 	}
561 
562 	if (big_modexp(&tmp2, &(dsakey.y), &tmp2, &(dsakey.p), NULL) !=
563 	    BIG_OK) {
564 		rv = convert_rv(brv);
565 		goto clean5;
566 	}
567 
568 	if (big_mul(&tmp1, &tmp1, &tmp2) != BIG_OK) {
569 		rv = convert_rv(brv);
570 		goto clean5;
571 	}
572 
573 	if (big_div_pos(NULL, &tmp1, &tmp1, &(dsakey.p)) != BIG_OK) {
574 		rv = convert_rv(brv);
575 		goto clean5;
576 	}
577 
578 	if (big_div_pos(NULL, &tmp1, &tmp1, &(dsakey.q)) != BIG_OK) {
579 		rv = convert_rv(brv);
580 		goto clean5;
581 	}
582 
583 	if (big_cmp_abs(&tmp1, &(dsakey.r)) == 0)
584 		rv = CKR_OK;
585 	else
586 		rv = CKR_SIGNATURE_INVALID;
587 
588 clean5:
589 	big_finish(&tmp3);
590 clean4:
591 	big_finish(&tmp2);
592 clean3:
593 	big_finish(&tmp1);
594 clean2:
595 	big_finish(&msg);
596 clean1:
597 	DSA_key_finish(&dsakey);
598 
599 	return (rv);
600 }
601