ctr_drbg.c

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