From 3dd9b31dc4fc935543d4142dfdd9a88e3ef6dcd8 Mon Sep 17 00:00:00 2001 From: "Dr. Stephen Henson" Date: Mon, 31 Jan 2011 19:44:09 +0000 Subject: [PATCH] Provisional, experimental support for DSA2 parameter generation algorithm. Not properly integrated or tested yet. --- crypto/dsa/dsa.h | 3 + crypto/dsa/dsa_err.c | 3 + crypto/dsa/dsa_gen.c | 268 +++++++++++++++++++++++++++++++++++++++++- crypto/dsa/dsa_locl.h | 5 + crypto/err/openssl.ec | 1 + fips/dsa/fips_dssvs.c | 94 ++++++++++++++- fips/fips.h | 1 + 7 files changed, 368 insertions(+), 7 deletions(-) diff --git a/crypto/dsa/dsa.h b/crypto/dsa/dsa.h index d232f67fdb..06a7b1431d 100644 --- a/crypto/dsa/dsa.h +++ b/crypto/dsa/dsa.h @@ -296,6 +296,7 @@ void ERR_load_DSA_strings(void); #define DSA_F_DSAPARAMS_PRINT_FP 101 #define DSA_F_DSA_BUILTIN_KEYGEN 124 #define DSA_F_DSA_BUILTIN_PARAMGEN 125 +#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_NEW_METHOD 103 @@ -323,12 +324,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_KEY_SIZE_TOO_SMALL 111 #define DSA_R_MISSING_PARAMETERS 101 #define DSA_R_MODULUS_TOO_LARGE 103 #define DSA_R_NEED_NEW_SETUP_VALUES 110 #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 3241e57a8e..a46fade4c6 100644 --- a/crypto/dsa/dsa_err.c +++ b/crypto/dsa/dsa_err.c @@ -76,6 +76,7 @@ static ERR_STRING_DATA DSA_str_functs[]= {ERR_FUNC(DSA_F_DSAPARAMS_PRINT_FP), "DSAparams_print_fp"}, {ERR_FUNC(DSA_F_DSA_BUILTIN_KEYGEN), "DSA_BUILTIN_KEYGEN"}, {ERR_FUNC(DSA_F_DSA_BUILTIN_PARAMGEN), "DSA_BUILTIN_PARAMGEN"}, +{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_NEW_METHOD), "DSA_new_method"}, @@ -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_KEY_SIZE_TOO_SMALL) ,"key size too small"}, {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_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 d5a41c249a..7f8ee8f727 100644 --- a/crypto/dsa/dsa_gen.c +++ b/crypto/dsa/dsa_gen.c @@ -136,8 +136,7 @@ int dsa_builtin_paramgen(DSA *ret, size_t bits, size_t qbits, #ifdef OPENSSL_FIPS if(FIPS_selftest_failed()) { - FIPSerr(FIPS_F_DSA_BUILTIN_PARAMGEN, - FIPS_R_FIPS_SELFTEST_FAILED); + FIPSerr(FIPS_F_DSA_BUILTIN_PARAMGEN, FIPS_R_FIPS_SELFTEST_FAILED); goto err; } @@ -369,4 +368,269 @@ err: if (mont != NULL) BN_MONT_CTX_free(mont); return ok; } + +/* Permissible parameter values for (L,N): see FIPS186-3 4.2 */ + +static int dsa2_check_params(size_t L, size_t N) + { + if (L == 1024 && N == 160) + return 1; + if (L == 2048 && N == 224) + return 1; + if (L == 2048 && N == 256) + return 1; + if (L == 3072 && N == 256) + return 1; + return 0; + } + +/* 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, + unsigned char *seed_out, + int *counter_ret, unsigned long *h_ret, BN_GENCB *cb) + { + int ok=-1; + unsigned char *seed = 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; + unsigned int h=2; + +#ifdef OPENSSL_FIPS + if(FIPS_selftest_failed()) + { + FIPSerr(FIPS_F_DSA_BUILTIN_PARAMGEN2, + FIPS_R_FIPS_SELFTEST_FAILED); + goto err; + } +#endif + if (!dsa2_check_params(L, N)) + { + DSAerr(DSA_F_DSA_BUILTIN_PARAMGEN2, DSA_R_INVALID_PARAMETERS); + ok = 0; + goto err; + } + + if (evpmd == NULL) + { + if (N == 160) + evpmd = EVP_sha1(); + else if (N == 224) + evpmd = EVP_sha224(); + else + evpmd = EVP_sha256(); + } + + mdsize = M_EVP_MD_size(evpmd); + + if (seed_len == 0) + seed_len = mdsize; + + seed = OPENSSL_malloc(seed_len); + + if (!seed) + 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); + q = BN_CTX_get(ctx); + X = BN_CTX_get(ctx); + c = BN_CTX_get(ctx); + p = BN_CTX_get(ctx); + test = 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) + RAND_pseudo_bytes(seed, qsize); + /* 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 */ + } + + 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 >= 4096) break; + } + } +end: + if(!BN_GENCB_call(cb, 2, 1)) + goto err; + + /* 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 (!BN_set_word(test,h)) goto err; + if (!BN_MONT_CTX_set(mont,p,ctx)) goto err; + + for (;;) + { + /* g=test^r0%p */ + if (!BN_mod_exp_mont(g,test,r0,p,ctx,mont)) goto err; + if (!BN_is_one(g)) break; + if (!BN_add(test,test,BN_value_one())) goto err; + h++; + } + + if(!BN_GENCB_call(cb, 3, 1)) + goto err; + + ok=1; +err: + if (ok) + { + if(ret->p) BN_free(ret->p); + if(ret->q) BN_free(ret->q); + if(ret->g) BN_free(ret->g); + ret->p=BN_dup(p); + ret->q=BN_dup(q); + 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_out) + memcpy(seed_out, seed, seed_len); + } + if (seed) + OPENSSL_free(seed); + if(ctx) + { + BN_CTX_end(ctx); + BN_CTX_free(ctx); + } + if (mont != NULL) BN_MONT_CTX_free(mont); + return ok; + } #endif diff --git a/crypto/dsa/dsa_locl.h b/crypto/dsa/dsa_locl.h index 21e2e45242..4e07c7cbab 100644 --- a/crypto/dsa/dsa_locl.h +++ b/crypto/dsa/dsa_locl.h @@ -58,3 +58,8 @@ 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 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); diff --git a/crypto/err/openssl.ec b/crypto/err/openssl.ec index e0554b4342..3beb239e3a 100644 --- a/crypto/err/openssl.ec +++ b/crypto/err/openssl.ec @@ -35,6 +35,7 @@ L TS crypto/ts/ts.h crypto/ts/ts_err.c L HMAC crypto/hmac/hmac.h crypto/hmac/hmac_err.c L CMS crypto/cms/cms.h crypto/cms/cms_err.c L JPAKE crypto/jpake/jpake.h crypto/jpake/jpake_err.c +L FIPS fips/fips.h crypto/fips_err.h # additional header files to be scanned for function names L NONE crypto/x509/x509_vfy.h NONE diff --git a/fips/dsa/fips_dssvs.c b/fips/dsa/fips_dssvs.c index 4610557f7b..5e9d83900c 100644 --- a/fips/dsa/fips_dssvs.c +++ b/fips/dsa/fips_dssvs.c @@ -22,6 +22,64 @@ int main(int argc, char **argv) #include "fips_utl.h" +static int parse_mod(char *line, int *pdsa2, int *pL, int *pN, + const EVP_MD **pmd) + { + char lbuf[10240]; + char *keyword, *value; + + char *p; + p = strchr(line, ','); + if (!p) + { + *pL = atoi(line); + *pdsa2 = 0; + *pN = 160; + *pmd = EVP_sha1(); + return 1; + } + *pdsa2 = 1; + *p = 0; + if (!parse_line(&keyword, &value, lbuf, line)) + return 0; + if (strcmp(keyword, "L")) + return 0; + *pL = atoi(value); + strcpy(line, p + 1); + p = strchr(line, ','); + if (!p) + return 0; + *p = 0; + if (!parse_line(&keyword, &value, lbuf, line)) + return 0; + if (strcmp(keyword, "N")) + return 0; + *pN = atoi(value); + strcpy(line, p + 1); + p = strchr(line, ']'); + if (!p) + return 0; + *p = 0; + p = line; + while(isspace(*p)) + p++; + if (!strcmp(p, "SHA-1")) + *pmd = EVP_sha1(); + else if (!strcmp(p, "SHA-224")) + *pmd = EVP_sha224(); + else if (!strcmp(p, "SHA-256")) + *pmd = EVP_sha256(); + else if (!strcmp(p, "SHA-384")) + *pmd = EVP_sha384(); + else if (!strcmp(p, "SHA-512")) + *pmd = EVP_sha512(); + else + return 0; + return 1; + } + + + static void pbn(const char *name, BIGNUM *bn) { int len, i; @@ -69,6 +127,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 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); static void pqg() { @@ -85,7 +147,9 @@ static void pqg() continue; } if(!strcmp(keyword,"[mod")) + { nmod=atoi(value); + } else if(!strcmp(keyword,"N")) { int n=atoi(value); @@ -126,7 +190,9 @@ static void pqgver() int counter, counter2; unsigned long h, h2; DSA *dsa=NULL; - int nmod=0; + int dsa2, L, N; + const EVP_MD *md = NULL; + int seedlen; unsigned char seed[1024]; while(fgets(buf,sizeof buf,stdin) != NULL) @@ -138,7 +204,13 @@ static void pqgver() } fputs(buf, stdout); if(!strcmp(keyword,"[mod")) - nmod=atoi(value); + { + if (!parse_mod(value, &dsa2, &L, &N, &md)) + { + fprintf(stderr, "Mod Parse Error\n"); + exit (1); + } + } else if(!strcmp(keyword,"P")) p=hex2bn(value); else if(!strcmp(keyword,"Q")) @@ -147,8 +219,8 @@ static void pqgver() g=hex2bn(value); else if(!strcmp(keyword,"Seed")) { - int slen = hex2bin(value, seed); - if (slen != 20) + seedlen = hex2bin(value, seed); + if (!dsa2 && seedlen != 20) { fprintf(stderr, "Seed parse length error\n"); exit (1); @@ -165,8 +237,20 @@ static void pqgver() exit (1); } dsa = FIPS_dsa_new(); - if (!DSA_generate_parameters_ex(dsa, nmod,seed,20 ,&counter2,&h2,NULL)) + if (!dsa2 && !dsa_builtin_paramgen(dsa, L, N, md, + seed, seedlen, NULL, + &counter2, &h2, NULL)) + { + fprintf(stderr, "Parameter Generation error\n"); + exit(1); + } + if (dsa2 && dsa_builtin_paramgen2(dsa, L, N, md, + seed, seedlen, NULL, + &counter2, &h2, NULL) < 0) + { + fprintf(stderr, "Parameter Generation error\n"); exit(1); + } if (BN_cmp(dsa->p, p) || BN_cmp(dsa->q, q) || BN_cmp(dsa->g, g) || (counter != counter2) || (h != h2)) printf("Result = F\n"); diff --git a/fips/fips.h b/fips/fips.h index a49611d9b5..ea01f9fc4b 100644 --- a/fips/fips.h +++ b/fips/fips.h @@ -157,6 +157,7 @@ void ERR_load_FIPS_strings(void); /* Function codes. */ #define FIPS_F_DH_BUILTIN_GENPARAMS 100 #define FIPS_F_DSA_BUILTIN_PARAMGEN 101 +#define FIPS_F_DSA_BUILTIN_PARAMGEN2 126 #define FIPS_F_DSA_DO_SIGN 102 #define FIPS_F_DSA_DO_VERIFY 103 #define FIPS_F_EVP_CIPHERINIT_EX 124 -- 2.25.1