ctr_drbg.c

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