security/nss/lib/freebl/dsa.c

   1 /*
   2  *
   3  * ***** BEGIN LICENSE BLOCK *****
   4  * Version: MPL 1.1/GPL 2.0/LGPL 2.1
   5  *
   6  * The contents of this file are subject to the Mozilla Public License Version
   7  * 1.1 (the "License"); you may not use this file except in compliance with
   8  * the License. You may obtain a copy of the License at
   9  * http://www.mozilla.org/MPL/
  10  *
  11  * Software distributed under the License is distributed on an "AS IS" basis,
  12  * WITHOUT WARRANTY OF ANY KIND, either express or implied. See the License
  13  * for the specific language governing rights and limitations under the
  14  * License.
  15  *
  16  * The Original Code is the Netscape security libraries.
  17  *
  18  * The Initial Developer of the Original Code is
  19  * Netscape Communications Corporation.
  20  * Portions created by the Initial Developer are Copyright (C) 1994-2000
  21  * the Initial Developer. All Rights Reserved.
  22  *
  23  * Contributor(s):
  24  *
  25  * Alternatively, the contents of this file may be used under the terms of
  26  * either the GNU General Public License Version 2 or later (the "GPL"), or
  27  * the GNU Lesser General Public License Version 2.1 or later (the "LGPL"),
  28  * in which case the provisions of the GPL or the LGPL are applicable instead
  29  * of those above. If you wish to allow use of your version of this file only
  30  * under the terms of either the GPL or the LGPL, and not to allow others to
  31  * use your version of this file under the terms of the MPL, indicate your
  32  * decision by deleting the provisions above and replace them with the notice
  33  * and other provisions required by the GPL or the LGPL. If you do not delete
  34  * the provisions above, a recipient may use your version of this file under
  35  * the terms of any one of the MPL, the GPL or the LGPL.
  36  *
  37  * ***** END LICENSE BLOCK ***** */
  38 /* $Id: dsa.c,v 1.18 2005/10/12 00:48:25 wtchang%redhat.com Exp $ */
  39
  40 #include "secerr.h"
  41
  42 #include "prtypes.h"
  43 #include "prinit.h"
  44 #include "blapi.h"
  45 #include "nssilock.h"
  46 #include "secitem.h"
  47 #include "blapi.h"
  48 #include "mpi.h"
  49 #include "secmpi.h"
  50
  51  /* XXX to be replaced by define in blapit.h */
  52 #define NSS_FREEBL_DSA_DEFAULT_CHUNKSIZE 2048
  53
  54 /* DSA-specific random number function defined in prng_fips1861.c. */
  55 extern SECStatus
  56 DSA_GenerateGlobalRandomBytes(void *dest, size_t len, const unsigned char *q);
  57
  58 static void translate_mpi_error(mp_err err)
  59 {
  60     MP_TO_SEC_ERROR(err);
  61 }
  62
  63 SECStatus
  64 dsa_NewKey(const PQGParams *params, DSAPrivateKey **privKey,
  65            const unsigned char *xb)
  66 {
  67     mp_int p, g;
  68     mp_int x, y;
  69     mp_err err;
  70     PRArenaPool *arena;
  71     DSAPrivateKey *key;
  72     /* Check args. */
  73     if (!params || !privKey) {
  74         PORT_SetError(SEC_ERROR_INVALID_ARGS);
  75         return SECFailure;
  76     }
  77     /* Initialize an arena for the DSA key. */
  78     arena = PORT_NewArena(NSS_FREEBL_DSA_DEFAULT_CHUNKSIZE);
  79     if (!arena) {
  80         PORT_SetError(SEC_ERROR_NO_MEMORY);
  81         return SECFailure;
  82     }
  83     key = (DSAPrivateKey *)PORT_ArenaZAlloc(arena, sizeof(DSAPrivateKey));
  84     if (!key) {
  85         PORT_SetError(SEC_ERROR_NO_MEMORY);
  86         PORT_FreeArena(arena, PR_TRUE);
  87         return SECFailure;
  88     }
  89     key->params.arena = arena;
  90     /* Initialize MPI integers. */
  91     MP_DIGITS(&p) = 0;
  92     MP_DIGITS(&g) = 0;
  93     MP_DIGITS(&x) = 0;
  94     MP_DIGITS(&y) = 0;
  95     CHECK_MPI_OK( mp_init(&p) );
  96     CHECK_MPI_OK( mp_init(&g) );
  97     CHECK_MPI_OK( mp_init(&x) );
  98     CHECK_MPI_OK( mp_init(&y) );
  99     /* Copy over the PQG params */
 100     CHECK_MPI_OK( SECITEM_CopyItem(arena, &key->params.prime,
 101                                           &params->prime) );
 102     CHECK_MPI_OK( SECITEM_CopyItem(arena, &key->params.subPrime,
 103                                           &params->subPrime) );
 104     CHECK_MPI_OK( SECITEM_CopyItem(arena, &key->params.base, &params->base) );
 105     /* Convert stored p, g, and received x into MPI integers. */
 106     SECITEM_TO_MPINT(params->prime, &p);
 107     SECITEM_TO_MPINT(params->base,  &g);
 108     OCTETS_TO_MPINT(xb, &x, DSA_SUBPRIME_LEN);
 109     /* Store x in private key */
 110     SECITEM_AllocItem(arena, &key->privateValue, DSA_SUBPRIME_LEN);
 111     memcpy(key->privateValue.data, xb, DSA_SUBPRIME_LEN);
 112     /* Compute public key y = g**x mod p */
 113     CHECK_MPI_OK( mp_exptmod(&g, &x, &p, &y) );
 114     /* Store y in public key */
 115     MPINT_TO_SECITEM(&y, &key->publicValue, arena);
 116     *privKey = key;
 117     key = NULL;
 118 cleanup:
 119     mp_clear(&p);
 120     mp_clear(&g);
 121     mp_clear(&x);
 122     mp_clear(&y);
 123     if (key)
 124         PORT_FreeArena(key->params.arena, PR_TRUE);
 125     if (err) {
 126         translate_mpi_error(err);
 127         return SECFailure;
 128     }
 129     return SECSuccess;
 130 }
 131
 132 /*
 133 ** Generate and return a new DSA public and private key pair,
 134 **      both of which are encoded into a single DSAPrivateKey struct.
 135 **      "params" is a pointer to the PQG parameters for the domain
 136 **      Uses a random seed.
 137 */
 138 SECStatus
 139 DSA_NewKey(const PQGParams *params, DSAPrivateKey **privKey)
 140 {
 141     SECStatus rv;
 142     unsigned char seed[DSA_SUBPRIME_LEN];
 143     int retries = 10;
 144     int i;
 145     PRBool good;
 146
 147     do {
 148         /* Generate seed bytes for x according to FIPS 186-1 appendix 3 */
 149         if (DSA_GenerateGlobalRandomBytes(seed, DSA_SUBPRIME_LEN,
 150                                           params->subPrime.data))
 151             return SECFailure;
 152         /* Disallow values of 0 and 1 for x. */
 153         good = PR_FALSE;
 154         for (i = 0; i < DSA_SUBPRIME_LEN-1; i++) {
 155             if (seed[i] != 0) {
 156                 good = PR_TRUE;
 157                 break;
 158             }
 159         }
 160         if (!good && seed[i] > 1) {
 161             good = PR_TRUE;
 162         }
 163     } while (!good && --retries > 0);
 164
 165     if (!good) {
 166         PORT_SetError(SEC_ERROR_NEED_RANDOM);
 167         return SECFailure;
 168     }
 169
 170     /* Generate a new DSA key using random seed. */
 171     rv = dsa_NewKey(params, privKey, seed);
 172     return rv;
 173 }
 174
 175 /* For FIPS compliance testing. Seed must be exactly 20 bytes long */
 176 SECStatus
 177 DSA_NewKeyFromSeed(const PQGParams *params,
 178                    const unsigned char *seed,
 179                    DSAPrivateKey **privKey)
 180 {
 181     SECStatus rv;
 182     rv = dsa_NewKey(params, privKey, seed);
 183     return rv;
 184 }
 185
 186 static SECStatus
 187 dsa_SignDigest(DSAPrivateKey *key, SECItem *signature, const SECItem *digest,
 188                const unsigned char *kb)
 189 {
 190     mp_int p, q, g;  /* PQG parameters */
 191     mp_int x, k;     /* private key & pseudo-random integer */
 192     mp_int r, s;     /* tuple (r, s) is signature) */
 193     mp_err err   = MP_OKAY;
 194     SECStatus rv = SECSuccess;
 195
 196     /* FIPS-compliance dictates that digest is a SHA1 hash. */
 197     /* Check args. */
 198     if (!key || !signature || !digest ||
 199         (signature->len < DSA_SIGNATURE_LEN) ||
 200         (digest->len != SHA1_LENGTH)) {
 201         PORT_SetError(SEC_ERROR_INVALID_ARGS);
 202         return SECFailure;
 203     }
 204
 205     /* Initialize MPI integers. */
 206     MP_DIGITS(&p) = 0;
 207     MP_DIGITS(&q) = 0;
 208     MP_DIGITS(&g) = 0;
 209     MP_DIGITS(&x) = 0;
 210     MP_DIGITS(&k) = 0;
 211     MP_DIGITS(&r) = 0;
 212     MP_DIGITS(&s) = 0;
 213     CHECK_MPI_OK( mp_init(&p) );
 214     CHECK_MPI_OK( mp_init(&q) );
 215     CHECK_MPI_OK( mp_init(&g) );
 216     CHECK_MPI_OK( mp_init(&x) );
 217     CHECK_MPI_OK( mp_init(&k) );
 218     CHECK_MPI_OK( mp_init(&r) );
 219     CHECK_MPI_OK( mp_init(&s) );
 220     /*
 221     ** Convert stored PQG and private key into MPI integers.
 222     */
 223     SECITEM_TO_MPINT(key->params.prime,    &p);
 224     SECITEM_TO_MPINT(key->params.subPrime, &q);
 225     SECITEM_TO_MPINT(key->params.base,     &g);
 226     SECITEM_TO_MPINT(key->privateValue,    &x);
 227     OCTETS_TO_MPINT(kb, &k, DSA_SUBPRIME_LEN);
 228     /*
 229     ** FIPS 186-1, Section 5, Step 1
 230     **
 231     ** r = (g**k mod p) mod q
 232     */
 233     CHECK_MPI_OK( mp_exptmod(&g, &k, &p, &r) ); /* r = g**k mod p */
 234     CHECK_MPI_OK(     mp_mod(&r, &q, &r) );     /* r = r mod q    */
 235     /*
 236     ** FIPS 186-1, Section 5, Step 2
 237     **
 238     ** s = (k**-1 * (SHA1(M) + x*r)) mod q
 239     */
 240     SECITEM_TO_MPINT(*digest, &s);         /* s = SHA1(M)     */
 241     CHECK_MPI_OK( mp_invmod(&k, &q, &k) );      /* k = k**-1 mod q */
 242     CHECK_MPI_OK( mp_mulmod(&x, &r, &q, &x) );  /* x = x * r mod q */
 243     CHECK_MPI_OK( mp_addmod(&s, &x, &q, &s) );  /* s = s + x mod q */
 244     CHECK_MPI_OK( mp_mulmod(&s, &k, &q, &s) );  /* s = s * k mod q */
 245     /*
 246     ** verify r != 0 and s != 0
 247     ** mentioned as optional in FIPS 186-1.
 248     */
 249     if (mp_cmp_z(&r) == 0 || mp_cmp_z(&s) == 0) {
 250         PORT_SetError(SEC_ERROR_NEED_RANDOM);
 251         rv = SECFailure;
 252         goto cleanup;
 253     }
 254     /*
 255     ** Step 4
 256     **
 257     ** Signature is tuple (r, s)
 258     */
 259     err = mp_to_fixlen_octets(&r, signature->data, DSA_SUBPRIME_LEN);
 260     if (err < 0) goto cleanup;
 261     err = mp_to_fixlen_octets(&s, signature->data + DSA_SUBPRIME_LEN,
 262                                   DSA_SUBPRIME_LEN);
 263     if (err < 0) goto cleanup;
 264     err = MP_OKAY;
 265     signature->len = DSA_SIGNATURE_LEN;
 266 cleanup:
 267     mp_clear(&p);
 268     mp_clear(&q);
 269     mp_clear(&g);
 270     mp_clear(&x);
 271     mp_clear(&k);
 272     mp_clear(&r);
 273     mp_clear(&s);
 274     if (err) {
 275         translate_mpi_error(err);
 276         rv = SECFailure;
 277     }
 278     return rv;
 279 }
 280
 281 /* signature is caller-supplied buffer of at least 40 bytes.
 282 ** On input,  signature->len == size of buffer to hold signature.
 283 **            digest->len    == size of digest.
 284 ** On output, signature->len == size of signature in buffer.
 285 ** Uses a random seed.
 286 */
 287 SECStatus
 288 DSA_SignDigest(DSAPrivateKey *key, SECItem *signature, const SECItem *digest)
 289 {
 290     SECStatus rv;
 291     int       retries = 10;
 292     unsigned char kSeed[DSA_SUBPRIME_LEN];
 293     int       i;
 294     PRBool    good;
 295
 296     PORT_SetError(0);
 297     do {
 298         rv = DSA_GenerateGlobalRandomBytes(kSeed, DSA_SUBPRIME_LEN,
 299                                            key->params.subPrime.data);
 300         if (rv != SECSuccess)
 301             break;
 302         /* Disallow a value of 0 for k. */
 303         good = PR_FALSE;
 304         for (i = 0; i < DSA_SUBPRIME_LEN; i++) {
 305             if (kSeed[i] != 0) {
 306                 good = PR_TRUE;
 307                 break;
 308             }
 309         }
 310         if (!good) {
 311             PORT_SetError(SEC_ERROR_NEED_RANDOM);
 312             rv = SECFailure;
 313             continue;
 314         }
 315         rv = dsa_SignDigest(key, signature, digest, kSeed);
 316     } while (rv != SECSuccess && PORT_GetError() == SEC_ERROR_NEED_RANDOM &&
 317              --retries > 0);
 318     return rv;
 319 }
 320
 321 /* For FIPS compliance testing. Seed must be exactly 20 bytes. */
 322 SECStatus
 323 DSA_SignDigestWithSeed(DSAPrivateKey * key,
 324                        SECItem *       signature,
 325                        const SECItem * digest,
 326                        const unsigned char * seed)
 327 {
 328     SECStatus rv;
 329     rv = dsa_SignDigest(key, signature, digest, seed);
 330     return rv;
 331 }
 332
 333 /* signature is caller-supplied buffer of at least 20 bytes.
 334 ** On input,  signature->len == size of buffer to hold signature.
 335 **            digest->len    == size of digest.
 336 */
 337 SECStatus
 338 DSA_VerifyDigest(DSAPublicKey *key, const SECItem *signature,
 339                  const SECItem *digest)
 340 {
 341     /* FIPS-compliance dictates that digest is a SHA1 hash. */
 342     mp_int p, q, g;      /* PQG parameters */
 343     mp_int r_, s_;       /* tuple (r', s') is received signature) */
 344     mp_int u1, u2, v, w; /* intermediate values used in verification */
 345     mp_int y;            /* public key */
 346     mp_err err;
 347     SECStatus verified = SECFailure;
 348
 349     /* Check args. */
 350     if (!key || !signature || !digest ||
 351         (signature->len != DSA_SIGNATURE_LEN) ||
 352         (digest->len != SHA1_LENGTH)) {
 353         PORT_SetError(SEC_ERROR_INVALID_ARGS);
 354         return SECFailure;
 355     }
 356     /* Initialize MPI integers. */
 357     MP_DIGITS(&p)  = 0;
 358     MP_DIGITS(&q)  = 0;
 359     MP_DIGITS(&g)  = 0;
 360     MP_DIGITS(&y)  = 0;
 361     MP_DIGITS(&r_) = 0;
 362     MP_DIGITS(&s_) = 0;
 363     MP_DIGITS(&u1) = 0;
 364     MP_DIGITS(&u2) = 0;
 365     MP_DIGITS(&v)  = 0;
 366     MP_DIGITS(&w)  = 0;
 367     CHECK_MPI_OK( mp_init(&p)  );
 368     CHECK_MPI_OK( mp_init(&q)  );
 369     CHECK_MPI_OK( mp_init(&g)  );
 370     CHECK_MPI_OK( mp_init(&y)  );
 371     CHECK_MPI_OK( mp_init(&r_) );
 372     CHECK_MPI_OK( mp_init(&s_) );
 373     CHECK_MPI_OK( mp_init(&u1) );
 374     CHECK_MPI_OK( mp_init(&u2) );
 375     CHECK_MPI_OK( mp_init(&v)  );
 376     CHECK_MPI_OK( mp_init(&w)  );
 377     /*
 378     ** Convert stored PQG and public key into MPI integers.
 379     */
 380     SECITEM_TO_MPINT(key->params.prime,    &p);
 381     SECITEM_TO_MPINT(key->params.subPrime, &q);
 382     SECITEM_TO_MPINT(key->params.base,     &g);
 383     SECITEM_TO_MPINT(key->publicValue,     &y);
 384     /*
 385     ** Convert received signature (r', s') into MPI integers.
 386     */
 387     OCTETS_TO_MPINT(signature->data, &r_, DSA_SUBPRIME_LEN);
 388     OCTETS_TO_MPINT(signature->data + DSA_SUBPRIME_LEN, &s_, DSA_SUBPRIME_LEN);
 389     /*
 390     ** Verify that 0 < r' < q and 0 < s' < q
 391     */
 392     if (mp_cmp_z(&r_) <= 0 || mp_cmp_z(&s_) <= 0 ||
 393         mp_cmp(&r_, &q) >= 0 || mp_cmp(&s_, &q) >= 0) {
 394         /* err is zero here. */
 395         PORT_SetError(SEC_ERROR_BAD_SIGNATURE);
 396         goto cleanup; /* will return verified == SECFailure */
 397     }
 398     /*
 399     ** FIPS 186-1, Section 6, Step 1
 400     **
 401     ** w = (s')**-1 mod q
 402     */
 403     CHECK_MPI_OK( mp_invmod(&s_, &q, &w) );      /* w = (s')**-1 mod q */
 404     /*
 405     ** FIPS 186-1, Section 6, Step 2
 406     **
 407     ** u1 = ((SHA1(M')) * w) mod q
 408     */
 409     SECITEM_TO_MPINT(*digest, &u1);              /* u1 = SHA1(M')     */
 410     CHECK_MPI_OK( mp_mulmod(&u1, &w, &q, &u1) ); /* u1 = u1 * w mod q */
 411     /*
 412     ** FIPS 186-1, Section 6, Step 3
 413     **
 414     ** u2 = ((r') * w) mod q
 415     */
 416     CHECK_MPI_OK( mp_mulmod(&r_, &w, &q, &u2) );
 417     /*
 418     ** FIPS 186-1, Section 6, Step 4
 419     **
 420     ** v = ((g**u1 * y**u2) mod p) mod q
 421     */
 422     CHECK_MPI_OK( mp_exptmod(&g, &u1, &p, &g) ); /* g = g**u1 mod p */
 423     CHECK_MPI_OK( mp_exptmod(&y, &u2, &p, &y) ); /* y = y**u2 mod p */
 424     CHECK_MPI_OK(  mp_mulmod(&g, &y, &p, &v)  ); /* v = g * y mod p */
 425     CHECK_MPI_OK(     mp_mod(&v, &q, &v)      ); /* v = v mod q     */
 426     /*
 427     ** Verification:  v == r'
 428     */
 429     if (mp_cmp(&v, &r_)) {
 430         PORT_SetError(SEC_ERROR_BAD_SIGNATURE);
 431         verified = SECFailure; /* Signature failed to verify. */
 432     } else {
 433         verified = SECSuccess; /* Signature verified. */
 434     }
 435 cleanup:
 436     mp_clear(&p);
 437     mp_clear(&q);
 438     mp_clear(&g);
 439     mp_clear(&y);
 440     mp_clear(&r_);
 441     mp_clear(&s_);
 442     mp_clear(&u1);
 443     mp_clear(&u2);
 444     mp_clear(&v);
 445     mp_clear(&w);
 446     if (err) {
 447         translate_mpi_error(err);
 448     }
 449     return verified;
 450 }