PolarSSL v1.1.4
ctr_drbg.c
Go to the documentation of this file.
00001 /*
00002  *  CTR_DRBG implementation based on AES-256 (NIST SP 800-90)
00003  *
00004  *  Copyright (C) 2006-2011, Brainspark B.V.
00005  *
00006  *  This file is part of PolarSSL (http://www.polarssl.org)
00007  *  Lead Maintainer: Paul Bakker <polarssl_maintainer at polarssl.org>
00008  *
00009  *  All rights reserved.
00010  *
00011  *  This program is free software; you can redistribute it and/or modify
00012  *  it under the terms of the GNU General Public License as published by
00013  *  the Free Software Foundation; either version 2 of the License, or
00014  *  (at your option) any later version.
00015  *
00016  *  This program is distributed in the hope that it will be useful,
00017  *  but WITHOUT ANY WARRANTY; without even the implied warranty of
00018  *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
00019  *  GNU General Public License for more details.
00020  *
00021  *  You should have received a copy of the GNU General Public License along
00022  *  with this program; if not, write to the Free Software Foundation, Inc.,
00023  *  51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
00024  */
00025 /*
00026  *  The NIST SP 800-90 DRBGs are described in the following publucation.
00027  *
00028  *  http://csrc.nist.gov/publications/nistpubs/800-90/SP800-90revised_March2007.pdf
00029  */
00030 
00031 #include "polarssl/config.h"
00032 
00033 #if defined(POLARSSL_CTR_DRBG_C)
00034 
00035 #include "polarssl/ctr_drbg.h"
00036 
00037 #if defined(POLARSSL_FS_IO)
00038 #include <stdio.h>
00039 #endif
00040 
00041 /*
00042  * Non-public function wrapped by ctr_crbg_init(). Necessary to allow NIST
00043  * tests to succeed (which require known length fixed entropy)
00044  */
00045 int ctr_drbg_init_entropy_len(
00046                    ctr_drbg_context *ctx,
00047                    int (*f_entropy)(void *, unsigned char *, size_t),
00048                    void *p_entropy,
00049                    const unsigned char *custom,
00050                    size_t len,
00051                    size_t entropy_len )
00052 {
00053     int ret;
00054     unsigned char key[CTR_DRBG_KEYSIZE];
00055 
00056     memset( ctx, 0, sizeof(ctr_drbg_context) );
00057     memset( key, 0, CTR_DRBG_KEYSIZE );
00058 
00059     ctx->f_entropy = f_entropy;
00060     ctx->p_entropy = p_entropy;
00061 
00062     ctx->entropy_len = entropy_len;
00063     ctx->reseed_interval = CTR_DRBG_RESEED_INTERVAL;
00064 
00065     /*
00066      * Initialize with an empty key
00067      */
00068     aes_setkey_enc( &ctx->aes_ctx, key, CTR_DRBG_KEYBITS );
00069 
00070     if( ( ret = ctr_drbg_reseed( ctx, custom, len ) ) != 0 )
00071         return( ret );
00072 
00073     return( 0 );
00074 }
00075 
00076 int ctr_drbg_init( ctr_drbg_context *ctx,
00077                    int (*f_entropy)(void *, unsigned char *, size_t),
00078                    void *p_entropy,
00079                    const unsigned char *custom,
00080                    size_t len )
00081 {
00082     return( ctr_drbg_init_entropy_len( ctx, f_entropy, p_entropy, custom, len,
00083                                        CTR_DRBG_ENTROPY_LEN ) );
00084 }
00085 
00086 void ctr_drbg_set_prediction_resistance( ctr_drbg_context *ctx, int resistance )
00087 {
00088     ctx->prediction_resistance = resistance;
00089 }
00090 
00091 void ctr_drbg_set_entropy_len( ctr_drbg_context *ctx, size_t len )
00092 {
00093     ctx->entropy_len = len;
00094 }
00095     
00096 void ctr_drbg_set_reseed_interval( ctr_drbg_context *ctx, int interval )
00097 {
00098     ctx->reseed_interval = interval;
00099 }
00100     
00101 int block_cipher_df( unsigned char *output,
00102                      const unsigned char *data, size_t data_len )
00103 {
00104     unsigned char buf[CTR_DRBG_MAX_SEED_INPUT + CTR_DRBG_BLOCKSIZE + 16];
00105     unsigned char tmp[CTR_DRBG_SEEDLEN];
00106     unsigned char key[CTR_DRBG_KEYSIZE];
00107     unsigned char chain[CTR_DRBG_BLOCKSIZE];
00108     unsigned char *p = buf, *iv;
00109     aes_context aes_ctx;
00110 
00111     int i, j, buf_len, use_len;
00112 
00113     memset( buf, 0, CTR_DRBG_MAX_SEED_INPUT + CTR_DRBG_BLOCKSIZE + 16 );
00114 
00115     /*
00116      * Construct IV (16 bytes) and S in buffer
00117      * IV = Counter (in 32-bits) padded to 16 with zeroes
00118      * S = Length input string (in 32-bits) || Length of output (in 32-bits) ||
00119      *     data || 0x80
00120      *     (Total is padded to a multiple of 16-bytes with zeroes)
00121      */
00122     p = buf + CTR_DRBG_BLOCKSIZE;
00123     *p++ = ( data_len >> 24 ) & 0xff;
00124     *p++ = ( data_len >> 16 ) & 0xff;
00125     *p++ = ( data_len >> 8  ) & 0xff;
00126     *p++ = ( data_len       ) & 0xff;
00127     p += 3;
00128     *p++ = CTR_DRBG_SEEDLEN;
00129     memcpy( p, data, data_len );
00130     p[data_len] = 0x80;
00131 
00132     buf_len = CTR_DRBG_BLOCKSIZE + 8 + data_len + 1;
00133 
00134     for( i = 0; i < CTR_DRBG_KEYSIZE; i++ )
00135         key[i] = i;
00136 
00137     aes_setkey_enc( &aes_ctx, key, CTR_DRBG_KEYBITS );
00138 
00139     /*
00140      * Reduce data to POLARSSL_CTR_DRBG_SEEDLEN bytes of data
00141      */
00142     for( j = 0; j < CTR_DRBG_SEEDLEN; j += CTR_DRBG_BLOCKSIZE )
00143     {
00144         p = buf;
00145         memset( chain, 0, CTR_DRBG_BLOCKSIZE );
00146         use_len = buf_len;
00147 
00148         while( use_len > 0 )
00149         {
00150             for( i = 0; i < CTR_DRBG_BLOCKSIZE; i++ )
00151                 chain[i] ^= p[i];
00152             p += CTR_DRBG_BLOCKSIZE;
00153             use_len -= CTR_DRBG_BLOCKSIZE;
00154 
00155             aes_crypt_ecb( &aes_ctx, AES_ENCRYPT, chain, chain );
00156         }
00157         
00158         memcpy( tmp + j, chain, CTR_DRBG_BLOCKSIZE );
00159 
00160         /*
00161          * Update IV
00162          */
00163         buf[3]++;
00164     }
00165 
00166     /*
00167      * Do final encryption with reduced data
00168      */
00169     aes_setkey_enc( &aes_ctx, tmp, CTR_DRBG_KEYBITS );
00170     iv = tmp + CTR_DRBG_KEYSIZE;
00171     p = output;
00172 
00173     for( j = 0; j < CTR_DRBG_SEEDLEN; j += CTR_DRBG_BLOCKSIZE )
00174     {
00175         aes_crypt_ecb( &aes_ctx, AES_ENCRYPT, iv, iv );
00176         memcpy( p, iv, CTR_DRBG_BLOCKSIZE );
00177         p += CTR_DRBG_BLOCKSIZE;
00178     }
00179 
00180     return( 0 );
00181 }
00182 
00183 int ctr_drbg_update_internal( ctr_drbg_context *ctx,
00184                               const unsigned char data[CTR_DRBG_SEEDLEN] )
00185 {
00186     unsigned char tmp[CTR_DRBG_SEEDLEN];
00187     unsigned char *p = tmp;
00188     int cb, i, j;
00189 
00190     memset( tmp, 0, CTR_DRBG_SEEDLEN );
00191 
00192     for( j = 0; j < CTR_DRBG_SEEDLEN; j += CTR_DRBG_BLOCKSIZE )
00193     {
00194         /*
00195          * Increase counter
00196          */
00197         i = CTR_DRBG_BLOCKSIZE - 1;
00198         do {
00199             ctx->counter[i]++;
00200             cb = ctx->counter[i] == 0;
00201         } while( i-- && cb );
00202 
00203         /*
00204          * Crypt counter block
00205          */
00206         aes_crypt_ecb( &ctx->aes_ctx, AES_ENCRYPT, ctx->counter, p );
00207 
00208         p += CTR_DRBG_BLOCKSIZE;
00209     }
00210 
00211     for( i = 0; i < CTR_DRBG_SEEDLEN; i++ )
00212         tmp[i] ^= data[i];
00213 
00214     /*
00215      * Update key and counter
00216      */
00217     aes_setkey_enc( &ctx->aes_ctx, tmp, CTR_DRBG_KEYBITS );
00218     memcpy( ctx->counter, tmp + CTR_DRBG_KEYSIZE, CTR_DRBG_BLOCKSIZE );
00219 
00220     return( 0 );
00221 }
00222 
00223 void ctr_drbg_update( ctr_drbg_context *ctx,
00224                       const unsigned char *additional, size_t add_len )
00225 {
00226     unsigned char add_input[CTR_DRBG_SEEDLEN];
00227 
00228     if( add_len > 0 )
00229     {
00230         block_cipher_df( add_input, additional, add_len );
00231         ctr_drbg_update_internal( ctx, add_input );
00232     }
00233 }
00234 
00235 int ctr_drbg_reseed( ctr_drbg_context *ctx,
00236                      const unsigned char *additional, size_t len )
00237 {
00238     unsigned char seed[CTR_DRBG_MAX_SEED_INPUT];
00239     size_t seedlen = 0;
00240 
00241     if( ctx->entropy_len + len > CTR_DRBG_MAX_SEED_INPUT )
00242         return( POLARSSL_ERR_CTR_DRBG_INPUT_TOO_BIG );
00243 
00244     memset( seed, 0, CTR_DRBG_MAX_SEED_INPUT );
00245 
00246     /*
00247      * Gather enropy_len bytes of entropy to seed state
00248      */
00249     if( 0 != ctx->f_entropy( ctx->p_entropy, seed,
00250                              ctx->entropy_len ) )
00251     {
00252         return( POLARSSL_ERR_CTR_DRBG_ENTROPY_SOURCE_FAILED );
00253     }
00254 
00255     seedlen += ctx->entropy_len;
00256 
00257     /*
00258      * Add additional data
00259      */
00260     if( additional && len )
00261     {
00262         memcpy( seed + seedlen, additional, len );
00263         seedlen += len;
00264     }
00265 
00266     /*
00267      * Reduce to 384 bits
00268      */
00269     block_cipher_df( seed, seed, seedlen );
00270 
00271     /*
00272      * Update state
00273      */
00274     ctr_drbg_update_internal( ctx, seed );
00275     ctx->reseed_counter = 1;
00276 
00277     return( 0 );
00278 }
00279     
00280 int ctr_drbg_random_with_add( void *p_rng,
00281                               unsigned char *output, size_t output_len,
00282                               const unsigned char *additional, size_t add_len )
00283 {
00284     int ret = 0;
00285     ctr_drbg_context *ctx = (ctr_drbg_context *) p_rng;
00286     unsigned char add_input[CTR_DRBG_SEEDLEN];
00287     unsigned char *p = output;
00288     unsigned char tmp[CTR_DRBG_BLOCKSIZE];
00289     int cb, i;
00290     size_t use_len;
00291 
00292     if( output_len > CTR_DRBG_MAX_REQUEST )
00293         return( POLARSSL_ERR_CTR_DRBG_REQUEST_TOO_BIG );
00294 
00295     if( add_len > CTR_DRBG_MAX_INPUT )
00296         return( POLARSSL_ERR_CTR_DRBG_INPUT_TOO_BIG );
00297 
00298     memset( add_input, 0, CTR_DRBG_SEEDLEN );
00299 
00300     if( ctx->reseed_counter > ctx->reseed_interval ||
00301         ctx->prediction_resistance )
00302     {
00303         if( ( ret = ctr_drbg_reseed( ctx, additional, add_len ) ) != 0 )
00304             return( ret );
00305 
00306         add_len = 0;
00307     }
00308 
00309     if( add_len > 0 )
00310     {
00311         block_cipher_df( add_input, additional, add_len );
00312         ctr_drbg_update_internal( ctx, add_input );
00313     }
00314 
00315     while( output_len > 0 )
00316     {
00317         /*
00318          * Increase counter
00319          */
00320         i = CTR_DRBG_BLOCKSIZE - 1;
00321         do {
00322             ctx->counter[i]++;
00323             cb = ctx->counter[i] == 0;
00324         } while( i-- && cb );
00325 
00326         /*
00327          * Crypt counter block
00328          */
00329         aes_crypt_ecb( &ctx->aes_ctx, AES_ENCRYPT, ctx->counter, tmp );
00330 
00331         use_len = (output_len > CTR_DRBG_BLOCKSIZE ) ? CTR_DRBG_BLOCKSIZE : output_len;
00332         /*
00333          * Copy random block to destination
00334          */
00335         memcpy( p, tmp, use_len );
00336         p += use_len;
00337         output_len -= use_len;
00338     }
00339 
00340     ctr_drbg_update_internal( ctx, add_input );
00341 
00342     ctx->reseed_counter++;
00343 
00344     return( 0 );
00345 }
00346 
00347 int ctr_drbg_random( void *p_rng, unsigned char *output, size_t output_len )
00348 {
00349     return ctr_drbg_random_with_add( p_rng, output, output_len, NULL, 0 );
00350 }
00351 
00352 #if defined(POLARSSL_FS_IO)
00353 int ctr_drbg_write_seed_file( ctr_drbg_context *ctx, const char *path )
00354 {
00355     int ret;
00356     FILE *f;
00357     unsigned char buf[ CTR_DRBG_MAX_INPUT ];
00358 
00359     if( ( f = fopen( path, "wb" ) ) == NULL )
00360         return( POLARSSL_ERR_CTR_DRBG_FILE_IO_ERROR );
00361 
00362     if( ( ret = ctr_drbg_random( ctx, buf, CTR_DRBG_MAX_INPUT ) ) != 0 )
00363         return( ret );
00364 
00365     if( fwrite( buf, 1, CTR_DRBG_MAX_INPUT, f ) != CTR_DRBG_MAX_INPUT )
00366     {
00367         fclose( f );
00368         return( POLARSSL_ERR_CTR_DRBG_FILE_IO_ERROR );
00369     }
00370 
00371     fclose( f );
00372     return( 0 );
00373 }
00374 
00375 int ctr_drbg_update_seed_file( ctr_drbg_context *ctx, const char *path )
00376 {
00377     FILE *f;
00378     size_t n;
00379     unsigned char buf[ CTR_DRBG_MAX_INPUT ];
00380 
00381     if( ( f = fopen( path, "rb" ) ) == NULL )
00382         return( POLARSSL_ERR_CTR_DRBG_FILE_IO_ERROR );
00383 
00384     fseek( f, 0, SEEK_END );
00385     n = (size_t) ftell( f );
00386     fseek( f, 0, SEEK_SET );
00387 
00388     if( n > CTR_DRBG_MAX_INPUT )
00389         return( POLARSSL_ERR_CTR_DRBG_INPUT_TOO_BIG );
00390 
00391     if( fread( buf, 1, n, f ) != n )
00392     {
00393         fclose( f );
00394         return( POLARSSL_ERR_CTR_DRBG_FILE_IO_ERROR );
00395     }
00396 
00397     ctr_drbg_update( ctx, buf, n );
00398     
00399     fclose( f );
00400     
00401     return( ctr_drbg_write_seed_file( ctx, path ) );
00402 }
00403 #endif /* POLARSSL_FS_IO */
00404 
00405 #if defined(POLARSSL_SELF_TEST)
00406 
00407 #include <stdio.h>
00408 
00409 unsigned char entropy_source_pr[96] =
00410     { 0xc1, 0x80, 0x81, 0xa6, 0x5d, 0x44, 0x02, 0x16,
00411       0x19, 0xb3, 0xf1, 0x80, 0xb1, 0xc9, 0x20, 0x02,
00412       0x6a, 0x54, 0x6f, 0x0c, 0x70, 0x81, 0x49, 0x8b,
00413       0x6e, 0xa6, 0x62, 0x52, 0x6d, 0x51, 0xb1, 0xcb,
00414       0x58, 0x3b, 0xfa, 0xd5, 0x37, 0x5f, 0xfb, 0xc9,
00415       0xff, 0x46, 0xd2, 0x19, 0xc7, 0x22, 0x3e, 0x95,
00416       0x45, 0x9d, 0x82, 0xe1, 0xe7, 0x22, 0x9f, 0x63,
00417       0x31, 0x69, 0xd2, 0x6b, 0x57, 0x47, 0x4f, 0xa3,
00418       0x37, 0xc9, 0x98, 0x1c, 0x0b, 0xfb, 0x91, 0x31,
00419       0x4d, 0x55, 0xb9, 0xe9, 0x1c, 0x5a, 0x5e, 0xe4,
00420       0x93, 0x92, 0xcf, 0xc5, 0x23, 0x12, 0xd5, 0x56,
00421       0x2c, 0x4a, 0x6e, 0xff, 0xdc, 0x10, 0xd0, 0x68 };
00422 
00423 unsigned char entropy_source_nopr[64] =
00424     { 0x5a, 0x19, 0x4d, 0x5e, 0x2b, 0x31, 0x58, 0x14,
00425       0x54, 0xde, 0xf6, 0x75, 0xfb, 0x79, 0x58, 0xfe,
00426       0xc7, 0xdb, 0x87, 0x3e, 0x56, 0x89, 0xfc, 0x9d,
00427       0x03, 0x21, 0x7c, 0x68, 0xd8, 0x03, 0x38, 0x20,
00428       0xf9, 0xe6, 0x5e, 0x04, 0xd8, 0x56, 0xf3, 0xa9,
00429       0xc4, 0x4a, 0x4c, 0xbd, 0xc1, 0xd0, 0x08, 0x46,
00430       0xf5, 0x98, 0x3d, 0x77, 0x1c, 0x1b, 0x13, 0x7e,
00431       0x4e, 0x0f, 0x9d, 0x8e, 0xf4, 0x09, 0xf9, 0x2e };
00432 
00433 unsigned char nonce_pers_pr[16] =
00434     { 0xd2, 0x54, 0xfc, 0xff, 0x02, 0x1e, 0x69, 0xd2,
00435       0x29, 0xc9, 0xcf, 0xad, 0x85, 0xfa, 0x48, 0x6c };
00436 
00437 unsigned char nonce_pers_nopr[16] =
00438     { 0x1b, 0x54, 0xb8, 0xff, 0x06, 0x42, 0xbf, 0xf5,
00439       0x21, 0xf1, 0x5c, 0x1c, 0x0b, 0x66, 0x5f, 0x3f };
00440 
00441 unsigned char result_pr[16] =
00442     { 0x34, 0x01, 0x16, 0x56, 0xb4, 0x29, 0x00, 0x8f,
00443       0x35, 0x63, 0xec, 0xb5, 0xf2, 0x59, 0x07, 0x23 };
00444 
00445 unsigned char result_nopr[16] =
00446     { 0xa0, 0x54, 0x30, 0x3d, 0x8a, 0x7e, 0xa9, 0x88,
00447       0x9d, 0x90, 0x3e, 0x07, 0x7c, 0x6f, 0x21, 0x8f };
00448 
00449 int test_offset;
00450 int ctr_drbg_self_test_entropy( void *data, unsigned char *buf, size_t len )
00451 {
00452     unsigned char *p = data;
00453     memcpy( buf, p + test_offset, len );
00454     test_offset += 32;
00455     return( 0 );
00456 }
00457 
00458 /*
00459  * Checkup routine
00460  */
00461 int ctr_drbg_self_test( int verbose )
00462 {
00463     ctr_drbg_context ctx;
00464     unsigned char buf[16];
00465 
00466     /*
00467      * Based on a NIST CTR_DRBG test vector (PR = True)
00468      */
00469     if( verbose != 0 )
00470         printf( "  CTR_DRBG (PR = TRUE) : " );
00471 
00472     test_offset = 0;
00473     if( ctr_drbg_init_entropy_len( &ctx, ctr_drbg_self_test_entropy, entropy_source_pr, nonce_pers_pr, 16, 32 ) != 0 )
00474     {
00475         if( verbose != 0 )
00476             printf( "failed\n" );
00477 
00478         return( 1 );
00479     }
00480     ctr_drbg_set_prediction_resistance( &ctx, CTR_DRBG_PR_ON );
00481 
00482     if( ctr_drbg_random( &ctx, buf, CTR_DRBG_BLOCKSIZE ) != 0 )
00483     {
00484         if( verbose != 0 )
00485             printf( "failed\n" );
00486 
00487         return( 1 );
00488     }
00489 
00490     if( ctr_drbg_random( &ctx, buf, CTR_DRBG_BLOCKSIZE ) != 0 )
00491     {
00492         if( verbose != 0 )
00493             printf( "failed\n" );
00494 
00495         return( 1 );
00496     }
00497 
00498     if( memcmp( buf, result_pr, CTR_DRBG_BLOCKSIZE ) != 0 )
00499     {
00500         if( verbose != 0 )
00501             printf( "failed\n" );
00502 
00503         return( 1 );
00504     }
00505     
00506     if( verbose != 0 )
00507         printf( "passed\n" );
00508 
00509     /*
00510      * Based on a NIST CTR_DRBG test vector (PR = FALSE)
00511      */
00512     if( verbose != 0 )
00513         printf( "  CTR_DRBG (PR = FALSE): " );
00514 
00515     test_offset = 0;
00516     if( ctr_drbg_init_entropy_len( &ctx, ctr_drbg_self_test_entropy, entropy_source_nopr, nonce_pers_nopr, 16, 32 ) != 0 )
00517     {
00518         if( verbose != 0 )
00519             printf( "failed\n" );
00520 
00521         return( 1 );
00522     }
00523 
00524     if( ctr_drbg_random( &ctx, buf, 16 ) != 0 )
00525     {
00526         if( verbose != 0 )
00527             printf( "failed\n" );
00528 
00529         return( 1 );
00530     }
00531 
00532     if( ctr_drbg_reseed( &ctx, NULL, 0 ) != 0 )
00533     {
00534         if( verbose != 0 )
00535             printf( "failed\n" );
00536 
00537         return( 1 );
00538     }
00539 
00540     if( ctr_drbg_random( &ctx, buf, 16 ) != 0 )
00541     {
00542         if( verbose != 0 )
00543             printf( "failed\n" );
00544 
00545         return( 1 );
00546     }
00547 
00548     if( memcmp( buf, result_nopr, 16 ) != 0 )
00549     {
00550         if( verbose != 0 )
00551             printf( "failed\n" );
00552 
00553         return( 1 );
00554     }
00555     
00556     if( verbose != 0 )
00557         printf( "passed\n" );
00558 
00559     if( verbose != 0 )
00560             printf( "\n" );
00561 
00562     return( 0 );
00563 }
00564 #endif
00565 
00566 #endif