cryptlib  3.4.1
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Properties Macros
kg_dlp.c
Go to the documentation of this file.
1 /****************************************************************************
2 * *
3 * cryptlib DLP Key Generation/Checking Routines *
4 * Copyright Peter Gutmann 1997-2008 *
5 * *
6 ****************************************************************************/
7 
8 #define PKC_CONTEXT /* Indicate that we're working with PKC contexts */
9 #if defined( INC_ALL )
10  #include "crypt.h"
11  #include "context.h"
12  #include "keygen.h"
13 #else
14  #include "crypt.h"
15  #include "context/context.h"
16  #include "context/keygen.h"
17 #endif /* Compiler-specific includes */
18 
19 #if defined( USE_DH ) || defined( USE_DSA ) || defined( USE_ELGAMAL )
20 
21 /****************************************************************************
22 * *
23 * Utility Functions *
24 * *
25 ****************************************************************************/
26 
27 /* Enable various side-channel protection mechanisms */
28 
29 CHECK_RETVAL STDC_NONNULL_ARG( ( 1 ) ) \
30 static int enableSidechannelProtection( INOUT PKC_INFO *pkcInfo,
31  IN_ALGO const CRYPT_ALGO_TYPE cryptAlgo )
32  {
33  assert( isWritePtr( pkcInfo, sizeof( PKC_INFO ) ) );
34 
35  REQUIRES( isDlpAlgo( cryptAlgo ) );
36 
37  /* Use constant-time modexp() to protect the private key from timing
38  channels */
39  BN_set_flags( &pkcInfo->dlpParam_x, BN_FLG_EXP_CONSTTIME );
40 
41  /* Checksum the bignums to try and detect fault attacks. Since we're
42  setting the checksum at this point there's no need to check the
43  return value */
44  ( void ) calculateBignumChecksum( pkcInfo, cryptAlgo );
45 
46  return( CRYPT_OK );
47  }
48 
49 /****************************************************************************
50 * *
51 * Determine Discrete Log Exponent Bits *
52 * *
53 ****************************************************************************/
54 
55 /* The following function (provided by Colin Plumb) is used to calculate the
56  appropriate size exponent for a given prime size which is required to
57  provide equivalent security from small-exponent attacks.
58 
59  This is based on a paper by Michael Wiener on | The function defined
60  the difficulty of the two attacks, which has | below (not part of the
61  the following table: | original paper)
62  | produces the following
63  Table 1: Subgroup Sizes to Match Field Sizes | results:
64  |
65  Size of p Cost of each attack Size of q | Output Error
66  (bits) (instructions or (bits) | (+ is safe)
67  modular multiplies) |
68  |
69  512 9 x 10^17 119 | 137 +18
70  768 6 x 10^21 145 | 153 +8
71  1024 7 x 10^24 165 | 169 +4
72  1280 3 x 10^27 183 | 184 +1
73  1536 7 x 10^29 198 | 198 +0
74  1792 9 x 10^31 212 | 212 +0
75  2048 8 x 10^33 225 | 225 +0
76  2304 5 x 10^35 237 | 237 +0
77  2560 3 x 10^37 249 | 249 +0
78  2816 1 x 10^39 259 | 260 +1
79  3072 3 x 10^40 269 | 270 +1
80  3328 8 x 10^41 279 | 280 +1
81  3584 2 x 10^43 288 | 289 +1
82  3840 4 x 10^44 296 | 297 +1
83  4096 7 x 10^45 305 | 305 +0
84  4352 1 x 10^47 313 | 313 +0
85  4608 2 x 10^48 320 | 321 +1
86  4864 2 x 10^49 328 | 329 +1
87  5120 3 x 10^50 335 | 337 +2
88 
89  This function fits a curve to this, which overestimates the size of the
90  exponent required, but by a very small amount in the important 1000-4000
91  bit range. It is a quadratic curve up to 3840 bits, and a linear curve
92  past that. They are designed to be C(1) (have the same value and the same
93  slope) at the point where they meet */
94 
95 #define AN 1L /* a = -AN/AD/65536, the quadratic coefficient */
96 #define AD 3L
97 #define M 8L /* Slope = M/256, i.e. 1/32 where linear starts */
98 #define TX 3840L /* X value at the slope point, where linear starts */
99 #define TY 297L /* Y value at the slope point, where linear starts */
100 
101 /* For a slope of M at the point (TX,TY) we only have one degree of freedom
102  left in a quadratic curve so use the coefficient of x^2, namely a, as
103  that free parameter.
104 
105  y = -AN/AD*((x-TX)/256)^2 + M*(x-TX)/256 + TY
106  = -AN*(x-TX)*(x-TX)/AD/256/256 + M*x/256 - M*TX/256 + TY
107  = -AN*x*x/AD/256/256 + 2*AN*x*TX/AD/256/256 - AN*TX*TX/AD/256/256 \
108  + M*x/256 - M*TX/256 + TY
109  = -AN*(x/256)^2/AD + 2*AN*(TX/256)*(x/256)/AD + M*(x/256) \
110  - AN*(TX/256)^2/AD - M*(TX/256) + TY
111  = (AN*(2*TX/256 - x/256) + M*AD)*x/256/AD - (AN*(TX/256)/AD + M)*TX/256 \
112  + TY
113  = (AN*(2*TX/256 - x/256) + M*AD)*x/256/AD \
114  - (AN*(TX/256) + M*AD)*TX/256/AD + TY
115  = ((M*AD + AN*(2*TX/256 - x/256))*x - (AN*(TX/256)+M*AD)*TX)/256/AD + TY
116  = ((M*AD + AN*(2*TX - x)/256)*x - (AN*(TX/256)+M*AD)*TX)/256/AD + TY
117  = ((M*AD + AN*(2*TX - x)/256)*x - (M*AD + AN*TX/256)*TX)/256/AD + TY
118  = (((256*M*AD+2*AN*TX-AN*x)/256)*x - (M*AD + AN*TX/256)*TX)/256/AD + TY
119 
120  Since this is for the range 0...TX, in order to avoid having any
121  intermediate results less than 0, we need one final rearrangement, and a
122  compiler can easily take the constant-folding from there...
123 
124  = TY + (((256*M*AD+2*AN*TX-AN*x)/256)*x - (M*AD + AN*TX/256)*TX)/256/AD
125  = TY - ((M*AD + AN*TX/256)*TX - ((256*M*AD+2*AN*TX-AN*x)/256)*x)/256/AD */
126 
127 CHECK_RETVAL \
128 static int getDLPexpSize( IN_LENGTH_SHORT_MIN( MIN_PKCSIZE * 8 ) \
129  const int primeBits )
130  {
131  long value; /* Necessary to avoid problems with 16-bit compilers */
132 
133  REQUIRES( primeBits >= bytesToBits( MIN_PKCSIZE ) && \
134  primeBits <= bytesToBits( CRYPT_MAX_PKCSIZE ) );
135 
136  /* If it's over TX bits, it's linear */
137  if( primeBits > TX )
138  value = M * primeBits / 256 - M * TX / 256 + TY;
139  else
140  {
141  /* It's quadratic */
142  value = TY - ( ( M * AD + AN * TX / 256 ) * TX - \
143  ( ( 256 * M * AD + AN * 2 * TX - AN * primeBits ) / 256 ) * \
144  primeBits ) / ( AD * 256 );
145  }
146  ENSURES( value >= 160 && value < 1000 );
147 
148  /* At this point we run into a problem with SSH, it hardcodes the
149  exponent size at 160 bits no matter what the prime size is so that
150  there's no increase in security when the key size is increased.
151  Because this function generates an exponent whose size matches the
152  security level of the key, it can't be used to generate DSA keys for
153  use with SSH. In order to provide at least basic keys usable with
154  SSH and also for backwards compatiblity with older (non-SSH)
155  implementations that hardcode DSA key parameters at { 1024, 160 } we
156  always return a fixed exponent size of 160 bits if the key size is
157  around 1024 bits */
158  if( primeBits <= 1028 )
159  return( 160 );
160 
161  return( ( int ) value );
162  }
163 
164 /****************************************************************************
165 * *
166 * Generate DL Primes *
167 * *
168 * Original findGeneratorForPQ() and generateDLPPublicValues() are *
169 * copyright Kevin J. Bluck 1998. Remainder copyright Peter Gutmann *
170 * 1998-2008. *
171 * *
172 ****************************************************************************/
173 
174 /* DLP-based PKCs have various requirements for the generated parameters:
175 
176  DSA: p, q, and g of preset lengths (currently p isn't fixed at exactly
177  n * 64 bits because of the way the Lim-Lee algorithm works, it's
178  possible to get this by iterating the multiplication step until the
179  result is exactly n * 64 bits but this doesn't seem worth the
180  effort), x = 1...q-1.
181  PKCS #3 DH: No g (it's fixed at 2) or q. Keys of this type can be
182  generated if required, but the current code is configured to always
183  generate X9.42 DH keys.
184  X9.42 DH: p, q, and g as for DSA but without the 160-bit SHA1-enforced
185  upper limit on q in original versions of the DSA specification so
186  that p can go above 1024 bits (newer versions of the spec finally
187  allow larger p and q values in conjunction with post-SHA1 hash
188  algorithms), x = 2...q-2.
189  Elgamal: As X9.42 DH */
190 
191 /* The maximum number of factors required to generate a prime using the Lim-
192  Lee algorithm. The value 160 is the minimum safe exponent size */
193 
194 #define MAX_NO_FACTORS ( ( bytesToBits( CRYPT_MAX_PKCSIZE ) / 160 ) + 1 )
195 
196 /* The maximum number of small primes required to generate a prime using the
197  Lim-Lee algorithm. There's no fixed bound on this value, but in the worst
198  case we start with
199  ~ CRYPT_MAX_PKCSIZE_bits / getDLPexpSize( CRYPT_MAX_PKCSIZE_bits ) primes
200  = ~ 13 values, and add one more prime on each retry. Typically we need
201  10-15 for keys in the most commonly-used range 512-2048 bits. In order
202  to simplify the handling of values we allow for 128 primes, which has a
203  vanishingly small probability of failing and also provides a safe upper
204  bound for the number of retries (there's something wrong with the
205  algorithm if it requires anywhere near this many retries) */
206 
207 #define MAX_NO_PRIMES 128
208 
209 /* Select a generator g for the prime moduli p and q. g will be chosen to
210  be of prime order q, where q divides (p - 1), i.e. g generates the
211  subgroup of order q in the multiplicative group of GF(p)
212  (traditionally for PKCS #3 DH g is fixed at 2 which is safe even when
213  it's not a primitive root since it still covers half of the space of
214  possible residues, however we always generate a FIPS 186-style g value) */
215 
216 CHECK_RETVAL STDC_NONNULL_ARG( ( 1 ) ) \
217 static int findGeneratorForPQ( INOUT PKC_INFO *pkcInfo )
218  {
219  BIGNUM *p = &pkcInfo->dlpParam_p, *q = &pkcInfo->dlpParam_q;
220  BIGNUM *g = &pkcInfo->dlpParam_g;
221  BIGNUM *j = &pkcInfo->tmp1, *gCounter = &pkcInfo->tmp2;
222  int bnStatus = BN_STATUS, iterationCount;
223 
224  assert( isWritePtr( pkcInfo, sizeof( PKC_INFO ) ) );
225 
226  /* j = (p - 1) / q */
227  CK( BN_sub_word( p, 1 ) );
228  CK( BN_div( j, NULL, p, q, pkcInfo->bnCTX ) );
229  CK( BN_add_word( p, 1 ) );
230  if( bnStatusError( bnStatus ) )
231  return( getBnStatus( bnStatus ) );
232 
233  /* Starting gCounter at 3, set g = (gCounter ^ j) mod p until g != 1.
234  Although FIPS 196/X9.30/X9.42 merely require that 1 < g < p-1, if we
235  use small integers it makes this operation much faster. Note that
236  we can't use a Montgomery modexp at this point since we haven't
237  evaluated the Montgomery form of p yet */
238  CK( BN_set_word( gCounter, 2 ) );
239  if( bnStatusError( bnStatus ) )
240  return( getBnStatus( bnStatus ) );
241  for( iterationCount = 0; iterationCount < FAILSAFE_ITERATIONS_MED;
242  iterationCount++ )
243  {
244  CK( BN_add_word( gCounter, 1 ) );
245  CK( BN_mod_exp( g, gCounter, j, p, pkcInfo->bnCTX ) );
246  if( bnStatusError( bnStatus ) )
247  return( getBnStatus( bnStatus ) );
248  if( !BN_is_one( g ) )
249  break;
250  }
251  ENSURES( iterationCount < FAILSAFE_ITERATIONS_MED );
252 
253  return( CRYPT_OK );
254  }
255 
256 /* Generate prime numbers for DLP-based PKC's using the Lim-Lee algorithm:
257 
258  p = 2 * q * ( prime[1] * ... prime[n] ) + 1 */
259 
260 CHECK_RETVAL STDC_NONNULL_ARG( ( 1 ) ) \
261 static int generateDLPPublicValues( INOUT PKC_INFO *pkcInfo,
262  IN_LENGTH_SHORT_MIN( MIN_PKCSIZE * 8 ) \
263  const int pBits )
264  {
265  const int safeExpSizeBits = getDLPexpSize( pBits );
266  const int noChecks = getNoPrimeChecks( pBits );
267  const int qBits = safeExpSizeBits;
268  BIGNUM llPrimes[ MAX_NO_PRIMES + 8 ], llProducts[ MAX_NO_FACTORS + 8 ];
269  BIGNUM *p = &pkcInfo->dlpParam_p, *q = &pkcInfo->dlpParam_q;
270  BOOLEAN primeFound;
271  int indices[ MAX_NO_FACTORS + 8 ];
272  int nPrimes, nFactors, factorBits, i, iterationCount;
273  int bnStatus = BN_STATUS, status;
274 
275  assert( isWritePtr( pkcInfo, sizeof( PKC_INFO ) ) );
276  assert( bytesToBits( MIN_PKCSIZE ) > 512 || \
277  getDLPexpSize( 512 ) == 160 );
278  assert( bytesToBits( MIN_PKCSIZE ) > 1024 || \
279  getDLPexpSize( 1024 ) == 160 );
280  /* 1024-bit keys have special handling for pre-FIPS 186-3
281  compatibility */
282  assert( bytesToBits( MIN_PKCSIZE ) > 1030 || \
283  getDLPexpSize( 1030 ) == 168 );
284  assert( bytesToBits( MIN_PKCSIZE ) > 1536 || \
285  getDLPexpSize( 1536 ) == 198 );
286  assert( getDLPexpSize( 2048 ) == 225 );
287  assert( getDLPexpSize( 3072 ) == 270 );
288  assert( getDLPexpSize( 4096 ) == 305 );
289 
290  REQUIRES( pBits >= bytesToBits( MIN_PKCSIZE ) && \
291  pBits <= bytesToBits( CRYPT_MAX_PKCSIZE ) );
292  REQUIRES( qBits >= 160 && qBits <= pBits && \
293  qBits <= bytesToBits( CRYPT_MAX_PKCSIZE ) );
294  REQUIRES( safeExpSizeBits >= 160 && safeExpSizeBits < 512 );
295 
296  /* Determine how many factors we need and the size in bits of the
297  factors */
298  factorBits = ( pBits - qBits ) - 1;
299  nFactors = nPrimes = ( factorBits / safeExpSizeBits ) + 1;
300  factorBits /= nFactors;
301  ENSURES( factorBits > 0 && \
302  factorBits <= bytesToBits( CRYPT_MAX_PKCSIZE ) && \
303  nFactors > 0 && nFactors <= MAX_NO_FACTORS && \
304  nPrimes > 0 && nPrimes <= MAX_NO_PRIMES );
305 
306  /* Generate a random prime q and multiply by 2 to form the base for the
307  other factors */
308  status = generatePrime( pkcInfo, q, qBits, CRYPT_UNUSED );
309  if( cryptStatusError( status ) )
310  return( status );
311  CK( BN_lshift1( q, q ) );
312  if( bnStatusError( bnStatus ) )
313  return( getBnStatus( bnStatus ) );
314 
315  /* Set up the permutation control arrays and generate the first nFactors
316  factors */
317  memset( llProducts, 0, MAX_NO_FACTORS * sizeof( BIGNUM ) );
318  for( i = 0; i < MAX_NO_FACTORS; i++ )
319  BN_init( &llProducts[ i ] );
320  memset( llPrimes, 0, MAX_NO_PRIMES * sizeof( BIGNUM ) );
321  for( i = 0; i < MAX_NO_PRIMES; i++ )
322  BN_init( &llPrimes[ i ] );
323  for( i = 0; i < nFactors; i++ )
324  {
325  status = generatePrime( pkcInfo, &llPrimes[ i ], factorBits,
326  CRYPT_UNUSED );
327  if( cryptStatusError( status ) )
328  goto cleanup;
329  }
330 
331  for( primeFound = FALSE, iterationCount = 0;
332  !primeFound && iterationCount < FAILSAFE_ITERATIONS_LARGE;
333  iterationCount++ )
334  {
335  int indexMoved, innerIterationCount;
336 
337  /* Initialize the indices for the permutation. We try the first
338  nFactors factors first since any new primes will be added at the
339  end */
340  indices[ nFactors - 1 ] = nPrimes - 1;
341  for( i = nFactors - 2; i >= 0; i-- )
342  indices[ i ] = indices[ i + 1 ] - 1;
343  CK( BN_mul( &llProducts[ nFactors - 1 ], q, &llPrimes[ nPrimes - 1 ],
344  pkcInfo->bnCTX ) );
345  if( bnStatusError( bnStatus ) )
346  {
347  status = getBnStatus( bnStatus );
348  goto cleanup;
349  }
350  indexMoved = nFactors - 2;
351 
352  /* Test all possible new prime permutations until a prime is found or
353  we run out of permutations */
354  for( innerIterationCount = 0;
355  indices[ nFactors - 1 ] > 0 && \
356  innerIterationCount < ( FAILSAFE_ITERATIONS_LARGE * 10 );
357  innerIterationCount++ )
358  {
359  /* Assemble a new candidate prime 2 * q * primes + 1 from the
360  currently indexed random primes */
361  for( i = indexMoved; bnStatusOK( bnStatus ) && i >= 0; i-- )
362  {
363  CK( BN_mul( &llProducts[ i ], &llProducts[ i + 1 ],
364  &llPrimes[ indices[ i ] ], pkcInfo->bnCTX ) );
365  }
366  CKPTR( BN_copy( p, &llProducts[ 0 ] ) );
367  CK( BN_add_word( p, 1 ) );
368  if( bnStatusError( bnStatus ) )
369  {
370  status = getBnStatus( bnStatus );
371  goto cleanup;
372  }
373 
374  /* If the candidate has a good chance of being prime, try a
375  probabilistic test and exit if it succeeds */
376  if( primeSieve( p ) )
377  {
378  status = primeProbable( pkcInfo, p, noChecks );
379  if( cryptStatusError( status ) )
380  goto cleanup;
381  if( status == TRUE )
382  {
383  primeFound = TRUE;
384  break;
385  }
386  }
387 
388  /* Find the lowest index which is not already at the lowest
389  possible point and move it down one */
390  for( i = 0; i < nFactors; i++ )
391  {
392  if( indices[ i ] > i )
393  {
394  indices[ i ]--;
395  indexMoved = i;
396  break;
397  }
398  }
399 
400  /* If we moved down the highest index we've exhausted all of the
401  permutations so we have to start over with another prime */
402  if( ( indexMoved >= nFactors - 1 ) || ( i >= nFactors ) )
403  break;
404 
405  /* We haven't changed the highest index, take all of the indices
406  below the one that we moved down and move them up so that
407  they're packed up as high as they'll go */
408  for( i = indexMoved - 1; i >= 0; i-- )
409  indices[ i ] = indices[ i + 1 ] - 1;
410  }
411  ENSURES( innerIterationCount < ( FAILSAFE_ITERATIONS_LARGE * 10 ) );
412 
413  /* If we haven't found a prime yet, add a new prime to the pool and
414  try again */
415  if( !primeFound )
416  {
417  if( nPrimes >= MAX_NO_PRIMES )
418  {
419  /* We've run through an extraordinary number of primes,
420  something is wrong */
421  DEBUG_DIAG(( "Iterated through %d primes trying to "
422  "generate DLP key", MAX_NO_PRIMES ));
423  assert( DEBUG_WARN );
424  status = CRYPT_ERROR_FAILED;
425  goto cleanup;
426  }
427  status = generatePrime( pkcInfo, &llPrimes[ nPrimes++ ], factorBits,
428  CRYPT_UNUSED );
429  if( cryptStatusError( status ) )
430  goto cleanup;
431  }
432  }
433  ENSURES( iterationCount < FAILSAFE_ITERATIONS_LARGE );
434 
435  /* Recover the original value of q by dividing by 2 and find a generator
436  suitable for p and q */
437  CK( BN_rshift1( q, q ) );
438  if( bnStatusError( bnStatus ) )
439  {
440  status = getBnStatus( bnStatus );
441  goto cleanup;
442  }
443  status = findGeneratorForPQ( pkcInfo );
444 
445 cleanup:
446 
447  /* Free the local storage */
448  for( i = 0; i < nPrimes; i++ )
449  BN_clear_free( &llPrimes[ i ] );
450  for( i = 0; i < nFactors; i++ )
451  BN_clear_free( &llProducts[ i ] );
452  zeroise( llPrimes, MAX_NO_PRIMES * sizeof( BIGNUM ) );
453  zeroise( llProducts, MAX_NO_FACTORS * sizeof( BIGNUM ) );
454 
455  return( status );
456  }
457 
458 /* Generate the DLP private value x and public value y */
459 
460 CHECK_RETVAL STDC_NONNULL_ARG( ( 1 ) ) \
461 static int generateDLPPrivateValue( INOUT PKC_INFO *pkcInfo )
462  {
463  BIGNUM *x = &pkcInfo->dlpParam_x, *q = &pkcInfo->dlpParam_q;
464  const int qBits = BN_num_bits( q );
465  int bnStatus = BN_STATUS, status;
466 
467  assert( isWritePtr( pkcInfo, sizeof( PKC_INFO ) ) );
468 
469  /* If it's a PKCS #3 DH key there won't be a q value present so we have
470  to estimate the appropriate x size in the same way that we estimated
471  the q size when we generated the public key components */
472  if( BN_is_zero( q ) )
473  {
474  return( generateBignum( x,
475  getDLPexpSize( BN_num_bits( &pkcInfo->dlpParam_p ) ),
476  0xC0, 0 ) );
477  }
478 
479  /* Generate the DLP private value x s.t. 2 <= x <= q-2 (this is the
480  lowest common denominator of FIPS 186's 1...q-1 and X9.42's 2...q-2).
481  Because the mod q-2 is expensive we do a quick check to make sure
482  that it's really necessary before calling it */
483  status = generateBignum( x, qBits, 0xC0, 0 );
484  if( cryptStatusError( status ) )
485  return( status );
486  CK( BN_sub_word( q, 2 ) );
487  if( BN_cmp( x, q ) > 0 )
488  {
489  /* Trim x down to size. Actually we get the upper bound as q-3,
490  but over a 160-bit (minimum) number range this doesn't matter */
491  CK( BN_mod( x, x, q, pkcInfo->bnCTX ) );
492 
493  /* If the value that we ended up with is too small, just generate a
494  new value one bit shorter, which guarantees that it'll fit the
495  criteria (the target is a suitably large random value, not the
496  closest possible fit within the range) */
497  if( bnStatusOK( bnStatus ) && BN_num_bits( x ) < qBits - 5 )
498  status = generateBignum( x, qBits - 1, 0xC0, 0 );
499  }
500  CK( BN_add_word( q, 2 ) );
501 
502  return( cryptStatusError( status ) ? status : getBnStatus( bnStatus ) );
503  }
504 
505 CHECK_RETVAL STDC_NONNULL_ARG( ( 1 ) ) \
506 static int generateDLPPublicValue( INOUT PKC_INFO *pkcInfo )
507  {
508  BIGNUM *p = &pkcInfo->dlpParam_p, *g = &pkcInfo->dlpParam_g;
509  BIGNUM *x = &pkcInfo->dlpParam_x, *y = &pkcInfo->dlpParam_y;
510  int bnStatus = BN_STATUS;
511 
512  assert( isWritePtr( pkcInfo, sizeof( PKC_INFO ) ) );
513 
514  CK( BN_mod_exp_mont( y, g, x, p, pkcInfo->bnCTX,
515  &pkcInfo->dlpParam_mont_p ) );
516  if( bnStatusError( bnStatus ) )
517  return( getBnStatus( bnStatus ) );
518 
519  return( CRYPT_OK );
520  }
521 
522 /****************************************************************************
523 * *
524 * Check a DLP Key *
525 * *
526 ****************************************************************************/
527 
528 /* Perform validity checks on the public key. We have to make the PKC_INFO
529  data non-const because the bignum code wants to modify some of the values
530  as it's working with them */
531 
532 CHECK_RETVAL STDC_NONNULL_ARG( ( 1 ) ) \
533 static int checkDLPDomainParameters( INOUT PKC_INFO *pkcInfo,
534  const BOOLEAN isPKCS3,
535  const BOOLEAN isFullyInitialised )
536  {
537  BIGNUM *p = &pkcInfo->dlpParam_p, *g = &pkcInfo->dlpParam_g;
538  BIGNUM *tmp = &pkcInfo->tmp1;
539  int length, bnStatus = BN_STATUS;
540 
541  assert( isWritePtr( pkcInfo, sizeof( PKC_INFO ) ) );
542 
543  /* Verify that pLen >= DLPPARAM_MIN_P, pLen <= DLPPARAM_MAX_P */
544  length = BN_num_bytes( p );
545  if( isShortPKCKey( length ) )
546  {
547  /* Special-case handling for insecure-sized public keys */
548  return( CRYPT_ERROR_NOSECURE );
549  }
550  if( length < DLPPARAM_MIN_P || length > DLPPARAM_MAX_P )
551  return( CRYPT_ARGERROR_STR1 );
552 
553  /* Verify that p is not (obviously) composite */
554  if( !primeSieve( p ) )
555  return( CRYPT_ARGERROR_STR1 );
556 
557  /* Verify that gLen >= DLPPARAM_MIN_G, gLen <= DLPPARAM_MAX_G */
558  length = BN_num_bytes( g );
559  if( length < DLPPARAM_MIN_G || length > DLPPARAM_MAX_G )
560  return( CRYPT_ARGERROR_STR1 );
561 
562  /* Verify that g < 256 if it's straight PKCS #3 DH. This isn't strictly
563  necessary but use of g in DH typically sets g = 2, the only reason for
564  setting it to a larger value is either stupidity or a deliberate DoS,
565  neither of which we want to encourage. FIPS 186/X9.42 use a g
566  parameter the same size as p so we can't limit the size as for
567  PKCS #3 */
568  if( isPKCS3 && BN_num_bits( g ) > 8 )
569  return( CRYPT_ARGERROR_STR1 );
570 
571  /* Verify that 2 <= g <= p - 2 */
572  if( BN_num_bits( g ) < 2 )
573  return( CRYPT_ARGERROR_STR1 );
574  CKPTR( BN_copy( tmp, p ) );
575  CK( BN_sub_word( tmp, 2 ) );
576  if( bnStatusError( bnStatus ) || BN_cmp( g, tmp ) > 0 )
577  return( CRYPT_ARGERROR_STR1 );
578 
579  /* If it's a PKCS #3 key then the only public values are p and g and
580  we're done */
581  if( isPKCS3 )
582  return( CRYPT_OK );
583 
584  /* Verify that qLen >= DLPPARAM_MIN_Q, qLen <= DLPPARAM_MAX_Q */
585  length = BN_num_bytes( &pkcInfo->dlpParam_q );
586  if( length < DLPPARAM_MIN_Q || length > DLPPARAM_MAX_Q )
587  return( CRYPT_ARGERROR_STR1 );
588 
589  /* Verify that q is not (obviously) composite */
590  if( !primeSieve( &pkcInfo->dlpParam_q ) )
591  return( CRYPT_ARGERROR_STR1 );
592 
593  /* Verify that g is a generator of order q. This check requires
594  initialisation of values that may not have been performed yet at this
595  point, in which case the check is performed inline in the main
596  initCheckDLPkey() code below */
597  if( !isFullyInitialised )
598  return( CRYPT_OK );
599  CK( BN_mod_exp_mont( tmp, g, &pkcInfo->dlpParam_q, p, pkcInfo->bnCTX,
600  &pkcInfo->dlpParam_mont_p ) );
601  if( bnStatusError( bnStatus ) || !BN_is_one( tmp ) )
602  return( CRYPT_ARGERROR_STR1 );
603 
604  return( CRYPT_OK );
605  }
606 
607 CHECK_RETVAL STDC_NONNULL_ARG( ( 1 ) ) \
608 static int checkDLPPublicKey( INOUT PKC_INFO *pkcInfo,
609  const BOOLEAN isPKCS3 )
610  {
611  BIGNUM *p = &pkcInfo->dlpParam_p, *y = &pkcInfo->dlpParam_y;
612  BIGNUM *tmp = &pkcInfo->tmp1;
613  int bnStatus = BN_STATUS, length;
614 
615  assert( isWritePtr( pkcInfo, sizeof( PKC_INFO ) ) );
616 
617  /* Verify that yLen >= DLPPARAM_MIN_Y, yLen <= DLPPARAM_MAX_Y */
618  length = BN_num_bytes( y );
619  if( length < DLPPARAM_MIN_Y || length > DLPPARAM_MAX_Y )
620  return( CRYPT_ARGERROR_STR1 );
621 
622  /* Verify that y < p */
623  if( BN_cmp( y, p ) >= 0 )
624  return( CRYPT_ARGERROR_STR1 );
625 
626  /* Verify that y has the correct order in the subgroup */
627  if( !isPKCS3 )
628  {
629  CK( BN_mod_exp_mont( tmp, y, &pkcInfo->dlpParam_q, p,
630  pkcInfo->bnCTX, &pkcInfo->dlpParam_mont_p ) );
631  if( bnStatusError( bnStatus ) || !BN_is_one( tmp ) )
632  return( CRYPT_ARGERROR_STR1 );
633  }
634 
635  return( CRYPT_OK );
636  }
637 
638 /* Perform validity checks on the private key */
639 
640 CHECK_RETVAL STDC_NONNULL_ARG( ( 1 ) ) \
641 static int checkDLPPrivateKey( INOUT PKC_INFO *pkcInfo )
642  {
643  BIGNUM *p = &pkcInfo->dlpParam_p, *g = &pkcInfo->dlpParam_g;
644  BIGNUM *x = &pkcInfo->dlpParam_x, *y = &pkcInfo->dlpParam_y;
645  BIGNUM *tmp = &pkcInfo->tmp1;
646  int bnStatus = BN_STATUS, length;
647 
648  assert( isWritePtr( pkcInfo, sizeof( PKC_INFO ) ) );
649 
650  /* Verify that xLen >= DLPPARAM_MIN_X, xLen <= DLPPARAM_MAX_X */
651  length = BN_num_bytes( x );
652  if( length < DLPPARAM_MIN_X || length > DLPPARAM_MAX_X )
653  return( CRYPT_ARGERROR_STR1 );
654 
655  /* Verify that g^x mod p == y */
656  CK( BN_mod_exp_mont( tmp, g, x, p, pkcInfo->bnCTX,
657  &pkcInfo->dlpParam_mont_p ) );
658  if( bnStatusError( bnStatus ) || BN_cmp( tmp, y ) )
659  return( CRYPT_ARGERROR_STR1 );
660 
661  return( CRYPT_OK );
662  }
663 
664 /****************************************************************************
665 * *
666 * Generate/Initialise a DLP Key *
667 * *
668 ****************************************************************************/
669 
670 /* Generate and check a generic DLP key */
671 
672 CHECK_RETVAL STDC_NONNULL_ARG( ( 1 ) ) \
673 int generateDLPkey( INOUT CONTEXT_INFO *contextInfoPtr,
674  IN_LENGTH_SHORT_MIN( MIN_PKCSIZE * 8 ) const int keyBits )
675  {
676  PKC_INFO *pkcInfo = contextInfoPtr->ctxPKC;
677  BIGNUM *p = &pkcInfo->dlpParam_p;
678  int bnStatus = BN_STATUS, status;
679 
680  assert( isWritePtr( contextInfoPtr, sizeof( CONTEXT_INFO ) ) );
681 
682  REQUIRES( keyBits >= bytesToBits( MIN_PKCSIZE ) && \
683  keyBits <= bytesToBits( CRYPT_MAX_PKCSIZE ) );
684 
685  /* Generate the domain parameters */
686  pkcInfo->keySizeBits = keyBits;
687  status = generateDLPPublicValues( pkcInfo, keyBits );
688  if( cryptStatusError( status ) )
689  return( status );
690 
691  /* Generate the private key */
692  status = generateDLPPrivateValue( pkcInfo );
693  if( cryptStatusError( status ) )
694  return( status );
695 
696  /* Since the keygen is randomised it may occur that the final size of
697  the public value that determines its nominal size is slightly smaller
698  than the requested nominal size. To handle this we recalculate the
699  effective key size after we've finished generating the public value
700  that determines its nominal size */
701  pkcInfo->keySizeBits = BN_num_bits( p );
702 
703  /* Evaluate the Montgomery form of p and calculate y */
704  CK( BN_MONT_CTX_set( &pkcInfo->dlpParam_mont_p, p, pkcInfo->bnCTX ) );
705  if( bnStatusError( bnStatus ) )
706  return( getBnStatus( bnStatus ) );
707  status = generateDLPPublicValue( pkcInfo );
708  if( cryptStatusError( status ) )
709  return( status );
710 
711  /* Make sure that the generated values are valid */
712  status = checkDLPDomainParameters( pkcInfo, FALSE, TRUE );
713  if( cryptStatusOK( status ) )
714  status = checkDLPPublicKey( pkcInfo, FALSE );
715  if( cryptStatusOK( status ) )
716  status = checkDLPPrivateKey( pkcInfo );
717  if( cryptStatusError( status ) )
718  return( status );
719 
720  /* Enable side-channel protection if required */
721  if( !( contextInfoPtr->flags & CONTEXT_FLAG_SIDECHANNELPROTECTION ) )
722  return( CRYPT_OK );
723  return( enableSidechannelProtection( pkcInfo,
724  contextInfoPtr->capabilityInfo->cryptAlgo ) );
725  }
726 
727 /* Initialise and check a DLP key. If the isDH flag is set then it's a DH
728  key and we generate the x value (and by extension the y value) if it's
729  not present. If the isPKCS3 flag is set then it's a PKCS #3 key rather
730  than FIPS 186/X9.42, without a q value */
731 
732 CHECK_RETVAL STDC_NONNULL_ARG( ( 1 ) ) \
733 int initCheckDLPkey( INOUT CONTEXT_INFO *contextInfoPtr,
734  const BOOLEAN isDH, const BOOLEAN isPKCS3 )
735  {
736  PKC_INFO *pkcInfo = contextInfoPtr->ctxPKC;
737  BIGNUM *p = &pkcInfo->dlpParam_p, *g = &pkcInfo->dlpParam_g;
738  BIGNUM *x = &pkcInfo->dlpParam_x, *y = &pkcInfo->dlpParam_y;
739  BIGNUM *tmp = &pkcInfo->tmp1;
740  const BOOLEAN isPrivateKey = \
741  ( contextInfoPtr->flags & CONTEXT_FLAG_ISPUBLICKEY ) ? FALSE : TRUE;
742  BOOLEAN generatedX = FALSE;
743  int bnStatus = BN_STATUS, status;
744 
745  assert( isWritePtr( contextInfoPtr, sizeof( CONTEXT_INFO ) ) );
746 
747  /* Make sure that the necessary key parameters have been initialised.
748  Since PKCS #3 doesn't use the q parameter we only require it for
749  algorithms that specifically use FIPS 186 values. DH keys are a bit
750  more complicated because they function as both public and private
751  keys so we don't require an x parameter if it's a DH key */
752  if( BN_is_zero( p ) || BN_is_zero( g ) )
753  return( CRYPT_ARGERROR_STR1 );
754  if( !isPKCS3 && BN_is_zero( &pkcInfo->dlpParam_q ) )
755  return( CRYPT_ARGERROR_STR1 );
756  if( isPrivateKey && !isDH && BN_is_zero( x ) )
757  return( CRYPT_ARGERROR_STR1 );
758 
759  /* Make sure that the domain paramters are valid */
760  status = checkDLPDomainParameters( pkcInfo, isPKCS3, FALSE );
761  if( cryptStatusError( status ) )
762  return( status );
763 
764  /* Evaluate the Montgomery form of p, needed for further operations */
765  CK( BN_MONT_CTX_set( &pkcInfo->dlpParam_mont_p, p, pkcInfo->bnCTX ) );
766  if( bnStatusError( bnStatus ) )
767  return( getBnStatus( bnStatus ) );
768  pkcInfo->keySizeBits = BN_num_bits( p );
769 
770  /* Special-case verification for non-PKCS #3 (i.e. FIPS 186) keys. We
771  have to do this at this point rather than in
772  checkDLPDomainParameters() because it requires initialisation of
773  values that haven't been set up yet when checkDLPDomainParameters()
774  is called */
775  if( !isPKCS3 )
776  {
777  /* Verify that g is a generator of order q */
778  CK( BN_mod_exp_mont( tmp, g, &pkcInfo->dlpParam_q, p, pkcInfo->bnCTX,
779  &pkcInfo->dlpParam_mont_p ) );
780  if( bnStatusError( bnStatus ) || !BN_is_one( tmp ) )
781  return( CRYPT_ARGERROR_STR1 );
782  }
783 
784  /* If it's a DH key and there's no x value present, generate one now.
785  This is needed because all DH keys are effectively private keys. We
786  also update the context flags to reflect this change in status */
787  if( isDH && BN_is_zero( x ) )
788  {
789  status = generateDLPPrivateValue( pkcInfo );
790  if( cryptStatusError( status ) )
791  return( status );
792  contextInfoPtr->flags &= ~CONTEXT_FLAG_ISPUBLICKEY;
793  generatedX = TRUE;
794  }
795 
796  /* Some sources (specifically PKCS #11) don't make y available for
797  private keys so if the caller is trying to load a private key with a
798  zero y value we calculate it for them. First, we check to make sure
799  that we have x available to calculate y */
800  if( BN_is_zero( y ) && BN_is_zero( x ) )
801  return( CRYPT_ARGERROR_STR1 );
802 
803  /* Calculate y if required. This is a bit odd because if we've
804  generated a new x value it'll cause any existing y value to be
805  overwritten by a new one based on the newly-generated x value. This
806  means that if we load a DH key from a certificate containing an
807  existing y value then this process will overwrite the value with a
808  new one, so that the context associated with the certificate will
809  contain a y value that differs from the one in the certificate. This
810  is unfortunate, but again because of the DH key duality we need to
811  have both an x and a y value present otherwise the key is useless and
812  in order to get an x value we have to recreate the y value.
813 
814  This process (and DLP public-key ops in general) can be trapdoored as
815  follows to leak the x value over two consecutive exchanges (due to
816  Adam Young and Moti Yung, "Kleptography: Using Cryptography Against
817  Cryptography" and "The Prevalence of Kleptographic Attacks on
818  Discrete-Log Based Cryptosystems"). In the following, x and y are
819  the public and private values and xA and yA are the attacker's public
820  and private values (in this particular example x, y are used as DH
821  values and xA and yA as Elgamal values):
822 
823  y1 = g^x1 mod p, saving x1.
824  z = g^x1 * yA^-(a * x1 - b) mod p, where a, b are constants.
825  x2 = hash( z ).
826  y2 = g^x2 mod p.
827 
828  The attacker intercepts the two DH values and computes:
829 
830  r = y1^a * g^b mod p.
831  z = y1 / r^xA mod p.
832  if y2 == g^hash( z ) mod p then x1 is hash( z ).
833  z = z / g^W, where W is a fixed odd integer.
834  if y2 == g^hash( z ) mod p then x1 is hash( z ).
835 
836  This is why it's a good idea to use public code for this sort of
837  thing... */
838  if( BN_is_zero( y ) || generatedX )
839  {
840  status = generateDLPPublicValue( pkcInfo );
841  if( cryptStatusError( status ) )
842  return( status );
843  }
844 
845  /* Make sure that the public key is valid */
846  status = checkDLPPublicKey( pkcInfo, isPKCS3 );
847  if( cryptStatusError( status ) )
848  return( status );
849 
850  /* Make sure that the private key is valid */
851  if( isPrivateKey || generatedX )
852  {
853  status = checkDLPPrivateKey( pkcInfo );
854  if( cryptStatusError( status ) )
855  return( status );
856  }
857 
858  /* Enable side-channel protection if required */
859  if( !( contextInfoPtr->flags & CONTEXT_FLAG_SIDECHANNELPROTECTION ) )
860  return( CRYPT_OK );
861  return( enableSidechannelProtection( pkcInfo,
862  contextInfoPtr->capabilityInfo->cryptAlgo ) );
863  }
864 #endif /* USE_DH || USE_DSA || USE_ELGAMAL */
Generated on Thu Jan 10 2013 10:00:45 for cryptlib by   doxygen 1.8.2