PolarSSL v1.3.1
ctr_drbg.c
Go to the documentation of this file.
1 /*
2  * CTR_DRBG implementation based on AES-256 (NIST SP 800-90)
3  *
4  * Copyright (C) 2006-2013, Brainspark B.V.
5  *
6  * This file is part of PolarSSL (http://www.polarssl.org)
7  * Lead Maintainer: Paul Bakker <polarssl_maintainer at polarssl.org>
8  *
9  * All rights reserved.
10  *
11  * This program is free software; you can redistribute it and/or modify
12  * it under the terms of the GNU General Public License as published by
13  * the Free Software Foundation; either version 2 of the License, or
14  * (at your option) any later version.
15  *
16  * This program is distributed in the hope that it will be useful,
17  * but WITHOUT ANY WARRANTY; without even the implied warranty of
18  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
19  * GNU General Public License for more details.
20  *
21  * You should have received a copy of the GNU General Public License along
22  * with this program; if not, write to the Free Software Foundation, Inc.,
23  * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
24  */
25 /*
26  * The NIST SP 800-90 DRBGs are described in the following publucation.
27  *
28  * http://csrc.nist.gov/publications/nistpubs/800-90/SP800-90revised_March2007.pdf
29  */
30 
31 #include "polarssl/config.h"
32 
33 #if defined(POLARSSL_CTR_DRBG_C)
34 
35 #include "polarssl/ctr_drbg.h"
36 
37 #if defined(POLARSSL_FS_IO)
38 #include <stdio.h>
39 #endif
40 
41 /*
42  * Non-public function wrapped by ctr_crbg_init(). Necessary to allow NIST
43  * tests to succeed (which require known length fixed entropy)
44  */
46  ctr_drbg_context *ctx,
47  int (*f_entropy)(void *, unsigned char *, size_t),
48  void *p_entropy,
49  const unsigned char *custom,
50  size_t len,
51  size_t entropy_len )
52 {
53  int ret;
54  unsigned char key[CTR_DRBG_KEYSIZE];
55 
56  memset( ctx, 0, sizeof(ctr_drbg_context) );
57  memset( key, 0, CTR_DRBG_KEYSIZE );
58 
59  ctx->f_entropy = f_entropy;
60  ctx->p_entropy = p_entropy;
61 
62  ctx->entropy_len = entropy_len;
64 
65  /*
66  * Initialize with an empty key
67  */
69 
70  if( ( ret = ctr_drbg_reseed( ctx, custom, len ) ) != 0 )
71  return( ret );
72 
73  return( 0 );
74 }
75 
77  int (*f_entropy)(void *, unsigned char *, size_t),
78  void *p_entropy,
79  const unsigned char *custom,
80  size_t len )
81 {
82  return( ctr_drbg_init_entropy_len( ctx, f_entropy, p_entropy, custom, len,
84 }
85 
86 void ctr_drbg_set_prediction_resistance( ctr_drbg_context *ctx, int resistance )
87 {
88  ctx->prediction_resistance = resistance;
89 }
90 
91 void ctr_drbg_set_entropy_len( ctr_drbg_context *ctx, size_t len )
92 {
93  ctx->entropy_len = len;
94 }
95 
96 void ctr_drbg_set_reseed_interval( ctr_drbg_context *ctx, int interval )
97 {
98  ctx->reseed_interval = interval;
99 }
100 
101 static int block_cipher_df( unsigned char *output,
102  const unsigned char *data, size_t data_len )
103 {
104  unsigned char buf[CTR_DRBG_MAX_SEED_INPUT + CTR_DRBG_BLOCKSIZE + 16];
105  unsigned char tmp[CTR_DRBG_SEEDLEN];
106  unsigned char key[CTR_DRBG_KEYSIZE];
107  unsigned char chain[CTR_DRBG_BLOCKSIZE];
108  unsigned char *p = buf, *iv;
109  aes_context aes_ctx;
110 
111  int i, j;
112  size_t buf_len, use_len;
113 
114  memset( buf, 0, CTR_DRBG_MAX_SEED_INPUT + CTR_DRBG_BLOCKSIZE + 16 );
115 
116  /*
117  * Construct IV (16 bytes) and S in buffer
118  * IV = Counter (in 32-bits) padded to 16 with zeroes
119  * S = Length input string (in 32-bits) || Length of output (in 32-bits) ||
120  * data || 0x80
121  * (Total is padded to a multiple of 16-bytes with zeroes)
122  */
123  p = buf + CTR_DRBG_BLOCKSIZE;
124  *p++ = ( data_len >> 24 ) & 0xff;
125  *p++ = ( data_len >> 16 ) & 0xff;
126  *p++ = ( data_len >> 8 ) & 0xff;
127  *p++ = ( data_len ) & 0xff;
128  p += 3;
129  *p++ = CTR_DRBG_SEEDLEN;
130  memcpy( p, data, data_len );
131  p[data_len] = 0x80;
132 
133  buf_len = CTR_DRBG_BLOCKSIZE + 8 + data_len + 1;
134 
135  for( i = 0; i < CTR_DRBG_KEYSIZE; i++ )
136  key[i] = i;
137 
138  aes_setkey_enc( &aes_ctx, key, CTR_DRBG_KEYBITS );
139 
140  /*
141  * Reduce data to POLARSSL_CTR_DRBG_SEEDLEN bytes of data
142  */
143  for( j = 0; j < CTR_DRBG_SEEDLEN; j += CTR_DRBG_BLOCKSIZE )
144  {
145  p = buf;
146  memset( chain, 0, CTR_DRBG_BLOCKSIZE );
147  use_len = buf_len;
148 
149  while( use_len > 0 )
150  {
151  for( i = 0; i < CTR_DRBG_BLOCKSIZE; i++ )
152  chain[i] ^= p[i];
153  p += CTR_DRBG_BLOCKSIZE;
154  use_len -= ( use_len >= CTR_DRBG_BLOCKSIZE ) ?
155  CTR_DRBG_BLOCKSIZE : use_len;
156 
157  aes_crypt_ecb( &aes_ctx, AES_ENCRYPT, chain, chain );
158  }
159 
160  memcpy( tmp + j, chain, CTR_DRBG_BLOCKSIZE );
161 
162  /*
163  * Update IV
164  */
165  buf[3]++;
166  }
167 
168  /*
169  * Do final encryption with reduced data
170  */
171  aes_setkey_enc( &aes_ctx, tmp, CTR_DRBG_KEYBITS );
172  iv = tmp + CTR_DRBG_KEYSIZE;
173  p = output;
174 
175  for( j = 0; j < CTR_DRBG_SEEDLEN; j += CTR_DRBG_BLOCKSIZE )
176  {
177  aes_crypt_ecb( &aes_ctx, AES_ENCRYPT, iv, iv );
178  memcpy( p, iv, CTR_DRBG_BLOCKSIZE );
179  p += CTR_DRBG_BLOCKSIZE;
180  }
181 
182  return( 0 );
183 }
184 
185 static int ctr_drbg_update_internal( ctr_drbg_context *ctx,
186  const unsigned char data[CTR_DRBG_SEEDLEN] )
187 {
188  unsigned char tmp[CTR_DRBG_SEEDLEN];
189  unsigned char *p = tmp;
190  int i, j;
191 
192  memset( tmp, 0, CTR_DRBG_SEEDLEN );
193 
194  for( j = 0; j < CTR_DRBG_SEEDLEN; j += CTR_DRBG_BLOCKSIZE )
195  {
196  /*
197  * Increase counter
198  */
199  for( i = CTR_DRBG_BLOCKSIZE; i > 0; i-- )
200  if( ++ctx->counter[i - 1] != 0 )
201  break;
202 
203  /*
204  * Crypt counter block
205  */
206  aes_crypt_ecb( &ctx->aes_ctx, AES_ENCRYPT, ctx->counter, p );
207 
208  p += CTR_DRBG_BLOCKSIZE;
209  }
210 
211  for( i = 0; i < CTR_DRBG_SEEDLEN; i++ )
212  tmp[i] ^= data[i];
213 
214  /*
215  * Update key and counter
216  */
217  aes_setkey_enc( &ctx->aes_ctx, tmp, CTR_DRBG_KEYBITS );
218  memcpy( ctx->counter, tmp + CTR_DRBG_KEYSIZE, CTR_DRBG_BLOCKSIZE );
219 
220  return( 0 );
221 }
222 
224  const unsigned char *additional, size_t add_len )
225 {
226  unsigned char add_input[CTR_DRBG_SEEDLEN];
227 
228  if( add_len > 0 )
229  {
230  block_cipher_df( add_input, additional, add_len );
231  ctr_drbg_update_internal( ctx, add_input );
232  }
233 }
234 
236  const unsigned char *additional, size_t len )
237 {
238  unsigned char seed[CTR_DRBG_MAX_SEED_INPUT];
239  size_t seedlen = 0;
240 
241  if( ctx->entropy_len + len > CTR_DRBG_MAX_SEED_INPUT )
243 
244  memset( seed, 0, CTR_DRBG_MAX_SEED_INPUT );
245 
246  /*
247  * Gather entropy_len bytes of entropy to seed state
248  */
249  if( 0 != ctx->f_entropy( ctx->p_entropy, seed,
250  ctx->entropy_len ) )
251  {
253  }
254 
255  seedlen += ctx->entropy_len;
256 
257  /*
258  * Add additional data
259  */
260  if( additional && len )
261  {
262  memcpy( seed + seedlen, additional, len );
263  seedlen += len;
264  }
265 
266  /*
267  * Reduce to 384 bits
268  */
269  block_cipher_df( seed, seed, seedlen );
270 
271  /*
272  * Update state
273  */
274  ctr_drbg_update_internal( ctx, seed );
275  ctx->reseed_counter = 1;
276 
277  return( 0 );
278 }
279 
280 int ctr_drbg_random_with_add( void *p_rng,
281  unsigned char *output, size_t output_len,
282  const unsigned char *additional, size_t add_len )
283 {
284  int ret = 0;
285  ctr_drbg_context *ctx = (ctr_drbg_context *) p_rng;
286  unsigned char add_input[CTR_DRBG_SEEDLEN];
287  unsigned char *p = output;
288  unsigned char tmp[CTR_DRBG_BLOCKSIZE];
289  int i;
290  size_t use_len;
291 
292  if( output_len > CTR_DRBG_MAX_REQUEST )
294 
295  if( add_len > CTR_DRBG_MAX_INPUT )
297 
298  memset( add_input, 0, CTR_DRBG_SEEDLEN );
299 
300  if( ctx->reseed_counter > ctx->reseed_interval ||
301  ctx->prediction_resistance )
302  {
303  if( ( ret = ctr_drbg_reseed( ctx, additional, add_len ) ) != 0 )
304  return( ret );
305 
306  add_len = 0;
307  }
308 
309  if( add_len > 0 )
310  {
311  block_cipher_df( add_input, additional, add_len );
312  ctr_drbg_update_internal( ctx, add_input );
313  }
314 
315  while( output_len > 0 )
316  {
317  /*
318  * Increase counter
319  */
320  for( i = CTR_DRBG_BLOCKSIZE; i > 0; i-- )
321  if( ++ctx->counter[i - 1] != 0 )
322  break;
323 
324  /*
325  * Crypt counter block
326  */
327  aes_crypt_ecb( &ctx->aes_ctx, AES_ENCRYPT, ctx->counter, tmp );
328 
329  use_len = (output_len > CTR_DRBG_BLOCKSIZE ) ? CTR_DRBG_BLOCKSIZE : output_len;
330  /*
331  * Copy random block to destination
332  */
333  memcpy( p, tmp, use_len );
334  p += use_len;
335  output_len -= use_len;
336  }
337 
338  ctr_drbg_update_internal( ctx, add_input );
339 
340  ctx->reseed_counter++;
341 
342  return( 0 );
343 }
344 
345 int ctr_drbg_random( void *p_rng, unsigned char *output, size_t output_len )
346 {
347  return ctr_drbg_random_with_add( p_rng, output, output_len, NULL, 0 );
348 }
349 
350 #if defined(POLARSSL_FS_IO)
351 int ctr_drbg_write_seed_file( ctr_drbg_context *ctx, const char *path )
352 {
354  FILE *f;
355  unsigned char buf[ CTR_DRBG_MAX_INPUT ];
356 
357  if( ( f = fopen( path, "wb" ) ) == NULL )
359 
360  if( ( ret = ctr_drbg_random( ctx, buf, CTR_DRBG_MAX_INPUT ) ) != 0 )
361  goto exit;
362 
363  if( fwrite( buf, 1, CTR_DRBG_MAX_INPUT, f ) != CTR_DRBG_MAX_INPUT )
364  {
366  goto exit;
367  }
368 
369  ret = 0;
370 
371 exit:
372  fclose( f );
373  return( ret );
374 }
375 
376 int ctr_drbg_update_seed_file( ctr_drbg_context *ctx, const char *path )
377 {
378  FILE *f;
379  size_t n;
380  unsigned char buf[ CTR_DRBG_MAX_INPUT ];
381 
382  if( ( f = fopen( path, "rb" ) ) == NULL )
384 
385  fseek( f, 0, SEEK_END );
386  n = (size_t) ftell( f );
387  fseek( f, 0, SEEK_SET );
388 
389  if( n > CTR_DRBG_MAX_INPUT )
390  {
391  fclose( f );
393  }
394 
395  if( fread( buf, 1, n, f ) != n )
396  {
397  fclose( f );
399  }
400 
401  fclose( f );
402 
403  ctr_drbg_update( ctx, buf, n );
404 
405  return( ctr_drbg_write_seed_file( ctx, path ) );
406 }
407 #endif /* POLARSSL_FS_IO */
408 
409 #if defined(POLARSSL_SELF_TEST)
410 
411 #include <stdio.h>
412 
413 unsigned char entropy_source_pr[96] =
414  { 0xc1, 0x80, 0x81, 0xa6, 0x5d, 0x44, 0x02, 0x16,
415  0x19, 0xb3, 0xf1, 0x80, 0xb1, 0xc9, 0x20, 0x02,
416  0x6a, 0x54, 0x6f, 0x0c, 0x70, 0x81, 0x49, 0x8b,
417  0x6e, 0xa6, 0x62, 0x52, 0x6d, 0x51, 0xb1, 0xcb,
418  0x58, 0x3b, 0xfa, 0xd5, 0x37, 0x5f, 0xfb, 0xc9,
419  0xff, 0x46, 0xd2, 0x19, 0xc7, 0x22, 0x3e, 0x95,
420  0x45, 0x9d, 0x82, 0xe1, 0xe7, 0x22, 0x9f, 0x63,
421  0x31, 0x69, 0xd2, 0x6b, 0x57, 0x47, 0x4f, 0xa3,
422  0x37, 0xc9, 0x98, 0x1c, 0x0b, 0xfb, 0x91, 0x31,
423  0x4d, 0x55, 0xb9, 0xe9, 0x1c, 0x5a, 0x5e, 0xe4,
424  0x93, 0x92, 0xcf, 0xc5, 0x23, 0x12, 0xd5, 0x56,
425  0x2c, 0x4a, 0x6e, 0xff, 0xdc, 0x10, 0xd0, 0x68 };
426 
427 unsigned char entropy_source_nopr[64] =
428  { 0x5a, 0x19, 0x4d, 0x5e, 0x2b, 0x31, 0x58, 0x14,
429  0x54, 0xde, 0xf6, 0x75, 0xfb, 0x79, 0x58, 0xfe,
430  0xc7, 0xdb, 0x87, 0x3e, 0x56, 0x89, 0xfc, 0x9d,
431  0x03, 0x21, 0x7c, 0x68, 0xd8, 0x03, 0x38, 0x20,
432  0xf9, 0xe6, 0x5e, 0x04, 0xd8, 0x56, 0xf3, 0xa9,
433  0xc4, 0x4a, 0x4c, 0xbd, 0xc1, 0xd0, 0x08, 0x46,
434  0xf5, 0x98, 0x3d, 0x77, 0x1c, 0x1b, 0x13, 0x7e,
435  0x4e, 0x0f, 0x9d, 0x8e, 0xf4, 0x09, 0xf9, 0x2e };
436 
437 unsigned char nonce_pers_pr[16] =
438  { 0xd2, 0x54, 0xfc, 0xff, 0x02, 0x1e, 0x69, 0xd2,
439  0x29, 0xc9, 0xcf, 0xad, 0x85, 0xfa, 0x48, 0x6c };
440 
441 unsigned char nonce_pers_nopr[16] =
442  { 0x1b, 0x54, 0xb8, 0xff, 0x06, 0x42, 0xbf, 0xf5,
443  0x21, 0xf1, 0x5c, 0x1c, 0x0b, 0x66, 0x5f, 0x3f };
444 
445 unsigned char result_pr[16] =
446  { 0x34, 0x01, 0x16, 0x56, 0xb4, 0x29, 0x00, 0x8f,
447  0x35, 0x63, 0xec, 0xb5, 0xf2, 0x59, 0x07, 0x23 };
448 
449 unsigned char result_nopr[16] =
450  { 0xa0, 0x54, 0x30, 0x3d, 0x8a, 0x7e, 0xa9, 0x88,
451  0x9d, 0x90, 0x3e, 0x07, 0x7c, 0x6f, 0x21, 0x8f };
452 
453 int test_offset;
454 static int ctr_drbg_self_test_entropy( void *data, unsigned char *buf,
455  size_t len )
456 {
457  unsigned char *p = data;
458  memcpy( buf, p + test_offset, len );
459  test_offset += 32;
460  return( 0 );
461 }
462 
463 /*
464  * Checkup routine
465  */
466 int ctr_drbg_self_test( int verbose )
467 {
468  ctr_drbg_context ctx;
469  unsigned char buf[16];
470 
471  /*
472  * Based on a NIST CTR_DRBG test vector (PR = True)
473  */
474  if( verbose != 0 )
475  printf( " CTR_DRBG (PR = TRUE) : " );
476 
477  test_offset = 0;
478  if( ctr_drbg_init_entropy_len( &ctx, ctr_drbg_self_test_entropy, entropy_source_pr, nonce_pers_pr, 16, 32 ) != 0 )
479  {
480  if( verbose != 0 )
481  printf( "failed\n" );
482 
483  return( 1 );
484  }
486 
487  if( ctr_drbg_random( &ctx, buf, CTR_DRBG_BLOCKSIZE ) != 0 )
488  {
489  if( verbose != 0 )
490  printf( "failed\n" );
491 
492  return( 1 );
493  }
494 
495  if( ctr_drbg_random( &ctx, buf, CTR_DRBG_BLOCKSIZE ) != 0 )
496  {
497  if( verbose != 0 )
498  printf( "failed\n" );
499 
500  return( 1 );
501  }
502 
503  if( memcmp( buf, result_pr, CTR_DRBG_BLOCKSIZE ) != 0 )
504  {
505  if( verbose != 0 )
506  printf( "failed\n" );
507 
508  return( 1 );
509  }
510 
511  if( verbose != 0 )
512  printf( "passed\n" );
513 
514  /*
515  * Based on a NIST CTR_DRBG test vector (PR = FALSE)
516  */
517  if( verbose != 0 )
518  printf( " CTR_DRBG (PR = FALSE): " );
519 
520  test_offset = 0;
521  if( ctr_drbg_init_entropy_len( &ctx, ctr_drbg_self_test_entropy, entropy_source_nopr, nonce_pers_nopr, 16, 32 ) != 0 )
522  {
523  if( verbose != 0 )
524  printf( "failed\n" );
525 
526  return( 1 );
527  }
528 
529  if( ctr_drbg_random( &ctx, buf, 16 ) != 0 )
530  {
531  if( verbose != 0 )
532  printf( "failed\n" );
533 
534  return( 1 );
535  }
536 
537  if( ctr_drbg_reseed( &ctx, NULL, 0 ) != 0 )
538  {
539  if( verbose != 0 )
540  printf( "failed\n" );
541 
542  return( 1 );
543  }
544 
545  if( ctr_drbg_random( &ctx, buf, 16 ) != 0 )
546  {
547  if( verbose != 0 )
548  printf( "failed\n" );
549 
550  return( 1 );
551  }
552 
553  if( memcmp( buf, result_nopr, 16 ) != 0 )
554  {
555  if( verbose != 0 )
556  printf( "failed\n" );
557 
558  return( 1 );
559  }
560 
561  if( verbose != 0 )
562  printf( "passed\n" );
563 
564  if( verbose != 0 )
565  printf( "\n" );
566 
567  return( 0 );
568 }
569 #endif
570 
571 #endif