From 3fa23ff0f1f8a54e06e829c2a5ee587e1cd1ec13 Mon Sep 17 00:00:00 2001 From: "Dr. Stephen Henson" Date: Wed, 18 Sep 2013 14:18:46 +0100 Subject: [PATCH] Add FIPS 186-2 DSA parameter generation algorithm. Backport support for FIPS 186-2 DSA parameter generation from HEAD. Redirect to FIPS in FIPS mode and workaround prototype error. --- crypto/dsa/dsa.h | 3 + crypto/dsa/dsa_err.c | 5 +- crypto/dsa/dsa_gen.c | 364 ++++++++++++++++++++++++++++++++++++++++++ crypto/dsa/dsa_locl.h | 7 + 4 files changed, 378 insertions(+), 1 deletion(-) diff --git a/crypto/dsa/dsa.h b/crypto/dsa/dsa.h index a6f6d0b0b2..81e267012d 100644 --- a/crypto/dsa/dsa.h +++ b/crypto/dsa/dsa.h @@ -285,6 +285,7 @@ void ERR_load_DSA_strings(void); #define DSA_F_DO_DSA_PRINT 104 #define DSA_F_DSAPARAMS_PRINT 100 #define DSA_F_DSAPARAMS_PRINT_FP 101 +#define DSA_F_DSA_BUILTIN_PARAMGEN2 126 #define DSA_F_DSA_DO_SIGN 112 #define DSA_F_DSA_DO_VERIFY 113 #define DSA_F_DSA_GENERATE_KEY 124 @@ -314,12 +315,14 @@ void ERR_load_DSA_strings(void); #define DSA_R_DATA_TOO_LARGE_FOR_KEY_SIZE 100 #define DSA_R_DECODE_ERROR 104 #define DSA_R_INVALID_DIGEST_TYPE 106 +#define DSA_R_INVALID_PARAMETERS 112 #define DSA_R_MISSING_PARAMETERS 101 #define DSA_R_MODULUS_TOO_LARGE 103 #define DSA_R_NEED_NEW_SETUP_VALUES 110 #define DSA_R_NON_FIPS_DSA_METHOD 111 #define DSA_R_NO_PARAMETERS_SET 107 #define DSA_R_PARAMETER_ENCODING_ERROR 105 +#define DSA_R_Q_NOT_PRIME 113 #ifdef __cplusplus } diff --git a/crypto/dsa/dsa_err.c b/crypto/dsa/dsa_err.c index 00545b7b9f..696ca61b21 100644 --- a/crypto/dsa/dsa_err.c +++ b/crypto/dsa/dsa_err.c @@ -1,6 +1,6 @@ /* crypto/dsa/dsa_err.c */ /* ==================================================================== - * Copyright (c) 1999-2011 The OpenSSL Project. All rights reserved. + * Copyright (c) 1999-2013 The OpenSSL Project. All rights reserved. * * Redistribution and use in source and binary forms, with or without * modification, are permitted provided that the following conditions @@ -74,6 +74,7 @@ static ERR_STRING_DATA DSA_str_functs[]= {ERR_FUNC(DSA_F_DO_DSA_PRINT), "DO_DSA_PRINT"}, {ERR_FUNC(DSA_F_DSAPARAMS_PRINT), "DSAparams_print"}, {ERR_FUNC(DSA_F_DSAPARAMS_PRINT_FP), "DSAparams_print_fp"}, +{ERR_FUNC(DSA_F_DSA_BUILTIN_PARAMGEN2), "DSA_BUILTIN_PARAMGEN2"}, {ERR_FUNC(DSA_F_DSA_DO_SIGN), "DSA_do_sign"}, {ERR_FUNC(DSA_F_DSA_DO_VERIFY), "DSA_do_verify"}, {ERR_FUNC(DSA_F_DSA_GENERATE_KEY), "DSA_generate_key"}, @@ -106,12 +107,14 @@ static ERR_STRING_DATA DSA_str_reasons[]= {ERR_REASON(DSA_R_DATA_TOO_LARGE_FOR_KEY_SIZE),"data too large for key size"}, {ERR_REASON(DSA_R_DECODE_ERROR) ,"decode error"}, {ERR_REASON(DSA_R_INVALID_DIGEST_TYPE) ,"invalid digest type"}, +{ERR_REASON(DSA_R_INVALID_PARAMETERS) ,"invalid parameters"}, {ERR_REASON(DSA_R_MISSING_PARAMETERS) ,"missing parameters"}, {ERR_REASON(DSA_R_MODULUS_TOO_LARGE) ,"modulus too large"}, {ERR_REASON(DSA_R_NEED_NEW_SETUP_VALUES) ,"need new setup values"}, {ERR_REASON(DSA_R_NON_FIPS_DSA_METHOD) ,"non fips dsa method"}, {ERR_REASON(DSA_R_NO_PARAMETERS_SET) ,"no parameters set"}, {ERR_REASON(DSA_R_PARAMETER_ENCODING_ERROR),"parameter encoding error"}, +{ERR_REASON(DSA_R_Q_NOT_PRIME) ,"q not prime"}, {0,NULL} }; diff --git a/crypto/dsa/dsa_gen.c b/crypto/dsa/dsa_gen.c index c398761d0d..d8ded8324c 100644 --- a/crypto/dsa/dsa_gen.c +++ b/crypto/dsa/dsa_gen.c @@ -82,6 +82,8 @@ #include "dsa_locl.h" #ifdef OPENSSL_FIPS +/* Workaround bug in prototype */ +#define fips_dsa_builtin_paramgen2 fips_dsa_paramgen_bad #include #endif @@ -368,4 +370,366 @@ err: if (mont != NULL) BN_MONT_CTX_free(mont); return ok; } + +#ifdef OPENSSL_FIPS +#undef fips_dsa_builtin_paramgen2 +extern int fips_dsa_builtin_paramgen2(DSA *ret, size_t L, size_t N, + const EVP_MD *evpmd, const unsigned char *seed_in, size_t seed_len, + int idx, unsigned char *seed_out, + int *counter_ret, unsigned long *h_ret, BN_GENCB *cb); +#endif + +/* This is a parameter generation algorithm for the DSA2 algorithm as + * described in FIPS 186-3. + */ + +int dsa_builtin_paramgen2(DSA *ret, size_t L, size_t N, + const EVP_MD *evpmd, const unsigned char *seed_in, size_t seed_len, + int idx, unsigned char *seed_out, + int *counter_ret, unsigned long *h_ret, BN_GENCB *cb) + { + int ok=-1; + unsigned char *seed = NULL, *seed_tmp = NULL; + unsigned char md[EVP_MAX_MD_SIZE]; + int mdsize; + BIGNUM *r0,*W,*X,*c,*test; + BIGNUM *g=NULL,*q=NULL,*p=NULL; + BN_MONT_CTX *mont=NULL; + int i, k, n=0, m=0, qsize = N >> 3; + int counter=0; + int r=0; + BN_CTX *ctx=NULL; + EVP_MD_CTX mctx; + unsigned int h=2; + +#ifdef OPENSSL_FIPS + + if (FIPS_mode()) + return fips_dsa_builtin_paramgen2(ret, L, N, evpmd, + seed_in, seed_len, idx, + seed_out, counter_ret, + h_ret, cb); +#endif + + EVP_MD_CTX_init(&mctx); + + if (evpmd == NULL) + { + if (N == 160) + evpmd = EVP_sha1(); + else if (N == 224) + evpmd = EVP_sha224(); + else + evpmd = EVP_sha256(); + } + + mdsize = EVP_MD_size(evpmd); + /* If unverificable g generation only don't need seed */ + if (!ret->p || !ret->q || idx >= 0) + { + if (seed_len == 0) + seed_len = mdsize; + + seed = OPENSSL_malloc(seed_len); + + if (seed_out) + seed_tmp = seed_out; + else + seed_tmp = OPENSSL_malloc(seed_len); + + if (!seed || !seed_tmp) + goto err; + + if (seed_in) + memcpy(seed, seed_in, seed_len); + + } + + if ((ctx=BN_CTX_new()) == NULL) + goto err; + + if ((mont=BN_MONT_CTX_new()) == NULL) + goto err; + + BN_CTX_start(ctx); + r0 = BN_CTX_get(ctx); + g = BN_CTX_get(ctx); + W = BN_CTX_get(ctx); + X = BN_CTX_get(ctx); + c = BN_CTX_get(ctx); + test = BN_CTX_get(ctx); + + /* if p, q already supplied generate g only */ + if (ret->p && ret->q) + { + p = ret->p; + q = ret->q; + if (idx >= 0) + memcpy(seed_tmp, seed, seed_len); + goto g_only; + } + else + { + p = BN_CTX_get(ctx); + q = BN_CTX_get(ctx); + } + + if (!BN_lshift(test,BN_value_one(),L-1)) + goto err; + for (;;) + { + for (;;) /* find q */ + { + unsigned char *pmd; + /* step 1 */ + if(!BN_GENCB_call(cb, 0, m++)) + goto err; + + if (!seed_in) + { + if (RAND_pseudo_bytes(seed, seed_len) < 0) + goto err; + } + /* step 2 */ + if (!EVP_Digest(seed, seed_len, md, NULL, evpmd, NULL)) + goto err; + /* Take least significant bits of md */ + if (mdsize > qsize) + pmd = md + mdsize - qsize; + else + pmd = md; + + if (mdsize < qsize) + memset(md + mdsize, 0, qsize - mdsize); + + /* step 3 */ + pmd[0] |= 0x80; + pmd[qsize-1] |= 0x01; + if (!BN_bin2bn(pmd, qsize, q)) + goto err; + + /* step 4 */ + r = BN_is_prime_fasttest_ex(q, DSS_prime_checks, ctx, + seed_in ? 1 : 0, cb); + if (r > 0) + break; + if (r != 0) + goto err; + /* Provided seed didn't produce a prime: error */ + if (seed_in) + { + ok = 0; + DSAerr(DSA_F_DSA_BUILTIN_PARAMGEN2, DSA_R_Q_NOT_PRIME); + goto err; + } + + /* do a callback call */ + /* step 5 */ + } + /* Copy seed to seed_out before we mess with it */ + if (seed_out) + memcpy(seed_out, seed, seed_len); + + if(!BN_GENCB_call(cb, 2, 0)) goto err; + if(!BN_GENCB_call(cb, 3, 0)) goto err; + + /* step 6 */ + counter=0; + /* "offset = 1" */ + + n=(L-1)/(mdsize << 3); + + for (;;) + { + if ((counter != 0) && !BN_GENCB_call(cb, 0, counter)) + goto err; + + /* step 7 */ + BN_zero(W); + /* now 'buf' contains "SEED + offset - 1" */ + for (k=0; k<=n; k++) + { + /* obtain "SEED + offset + k" by incrementing: */ + for (i = seed_len-1; i >= 0; i--) + { + seed[i]++; + if (seed[i] != 0) + break; + } + + if (!EVP_Digest(seed, seed_len, md ,NULL, evpmd, + NULL)) + goto err; + + /* step 8 */ + if (!BN_bin2bn(md, mdsize, r0)) + goto err; + if (!BN_lshift(r0,r0,(mdsize << 3)*k)) goto err; + if (!BN_add(W,W,r0)) goto err; + } + + /* more of step 8 */ + if (!BN_mask_bits(W,L-1)) goto err; + if (!BN_copy(X,W)) goto err; + if (!BN_add(X,X,test)) goto err; + + /* step 9 */ + if (!BN_lshift1(r0,q)) goto err; + if (!BN_mod(c,X,r0,ctx)) goto err; + if (!BN_sub(r0,c,BN_value_one())) goto err; + if (!BN_sub(p,X,r0)) goto err; + + /* step 10 */ + if (BN_cmp(p,test) >= 0) + { + /* step 11 */ + r = BN_is_prime_fasttest_ex(p, DSS_prime_checks, + ctx, 1, cb); + if (r > 0) + goto end; /* found it */ + if (r != 0) + goto err; + } + + /* step 13 */ + counter++; + /* "offset = offset + n + 1" */ + + /* step 14 */ + if (counter >= (int)(4 * L)) break; + } + if (seed_in) + { + ok = 0; + DSAerr(DSA_F_DSA_BUILTIN_PARAMGEN2, DSA_R_INVALID_PARAMETERS); + goto err; + } + } +end: + if(!BN_GENCB_call(cb, 2, 1)) + goto err; + + g_only: + + /* We now need to generate g */ + /* Set r0=(p-1)/q */ + if (!BN_sub(test,p,BN_value_one())) goto err; + if (!BN_div(r0,NULL,test,q,ctx)) goto err; + + if (idx < 0) + { + if (!BN_set_word(test,h)) + goto err; + } + else + h = 1; + if (!BN_MONT_CTX_set(mont,p,ctx)) goto err; + + for (;;) + { + static const unsigned char ggen[4] = {0x67,0x67,0x65,0x6e}; + if (idx >= 0) + { + md[0] = idx & 0xff; + md[1] = (h >> 8) & 0xff; + md[2] = h & 0xff; + if (!EVP_DigestInit_ex(&mctx, evpmd, NULL)) + goto err; + if (!EVP_DigestUpdate(&mctx, seed_tmp, seed_len)) + goto err; + if (!EVP_DigestUpdate(&mctx, ggen, sizeof(ggen))) + goto err; + if (!EVP_DigestUpdate(&mctx, md, 3)) + goto err; + if (!EVP_DigestFinal_ex(&mctx, md, NULL)) + goto err; + if (!BN_bin2bn(md, mdsize, test)) + goto err; + } + /* g=test^r0%p */ + if (!BN_mod_exp_mont(g,test,r0,p,ctx,mont)) goto err; + if (!BN_is_one(g)) break; + if (idx < 0 && !BN_add(test,test,BN_value_one())) goto err; + h++; + if ( idx >= 0 && h > 0xffff) + goto err; + } + + if(!BN_GENCB_call(cb, 3, 1)) + goto err; + + ok=1; +err: + if (ok == 1) + { + if (p != ret->p) + { + if(ret->p) BN_free(ret->p); + ret->p=BN_dup(p); + } + if (q != ret->q) + { + if(ret->q) BN_free(ret->q); + ret->q=BN_dup(q); + } + if(ret->g) BN_free(ret->g); + ret->g=BN_dup(g); + if (ret->p == NULL || ret->q == NULL || ret->g == NULL) + { + ok=-1; + goto err; + } + if (counter_ret != NULL) *counter_ret=counter; + if (h_ret != NULL) *h_ret=h; + } + if (seed) + OPENSSL_free(seed); + if (seed_out != seed_tmp) + OPENSSL_free(seed_tmp); + if(ctx) + { + BN_CTX_end(ctx); + BN_CTX_free(ctx); + } + if (mont != NULL) BN_MONT_CTX_free(mont); + EVP_MD_CTX_cleanup(&mctx); + return ok; + } + +int dsa_paramgen_check_g(DSA *dsa) + { + BN_CTX *ctx; + BIGNUM *tmp; + BN_MONT_CTX *mont = NULL; + int rv = -1; + ctx = BN_CTX_new(); + if (!ctx) + return -1; + BN_CTX_start(ctx); + if (BN_cmp(dsa->g, BN_value_one()) <= 0) + return 0; + if (BN_cmp(dsa->g, dsa->p) >= 0) + return 0; + tmp = BN_CTX_get(ctx); + if (!tmp) + goto err; + if ((mont=BN_MONT_CTX_new()) == NULL) + goto err; + if (!BN_MONT_CTX_set(mont,dsa->p,ctx)) + goto err; + /* Work out g^q mod p */ + if (!BN_mod_exp_mont(tmp,dsa->g,dsa->q, dsa->p, ctx, mont)) + goto err; + if (!BN_cmp(tmp, BN_value_one())) + rv = 1; + else + rv = 0; + err: + BN_CTX_end(ctx); + if (mont) + BN_MONT_CTX_free(mont); + BN_CTX_free(ctx); + return rv; + + } #endif diff --git a/crypto/dsa/dsa_locl.h b/crypto/dsa/dsa_locl.h index 21e2e45242..f385a7e861 100644 --- a/crypto/dsa/dsa_locl.h +++ b/crypto/dsa/dsa_locl.h @@ -58,3 +58,10 @@ int dsa_builtin_paramgen(DSA *ret, size_t bits, size_t qbits, const EVP_MD *evpmd, const unsigned char *seed_in, size_t seed_len, unsigned char *seed_out, int *counter_ret, unsigned long *h_ret, BN_GENCB *cb); + +int dsa_builtin_paramgen2(DSA *ret, size_t L, size_t N, + const EVP_MD *evpmd, const unsigned char *seed_in, size_t seed_len, + int idx, unsigned char *seed_out, + int *counter_ret, unsigned long *h_ret, BN_GENCB *cb); + +int dsa_paramgen_check_g(DSA *dsa); -- 2.25.1