usr/src/common/crypto/dsa/dsa_impl.c

   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 }