- Main Page
- Data Structures
- Files

# havege.c

Go to the documentation of this file.

    00001 /*
    00002  *  HAVEGE: HArdware Volatile Entropy Gathering and Expansion
    00003  *
    00004  *  Copyright (C) 2006-2009, Paul Bakker <polarssl_maintainer at polarssl.org>
    00005  *  All rights reserved.
    00006  *
    00007  *  Joined copyright on original XySSL code with: Christophe Devine
    00008  *
    00009  *  This program is free software; you can redistribute it and/or modify
    00010  *  it under the terms of the GNU General Public License as published by
    00011  *  the Free Software Foundation; either version 2 of the License, or
    00012  *  (at your option) any later version.
    00013  *
    00014  *  This program is distributed in the hope that it will be useful,
    00015  *  but WITHOUT ANY WARRANTY; without even the implied warranty of
    00016  *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
    00017  *  GNU General Public License for more details.
    00018  *
    00019  *  You should have received a copy of the GNU General Public License along
    00020  *  with this program; if not, write to the Free Software Foundation, Inc.,
    00021  *  51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
    00022  */
    00023 /*
    00024  *  The HAVEGE RNG was designed by Andre Seznec in 2002.
    00025  *
    00026  *  http://www.irisa.fr/caps/projects/hipsor/publi.php
    00027  *
    00028  *  Contact: seznec(at)irisa_dot_fr - orocheco(at)irisa_dot_fr
    00029  */
    00030
    00031 #include <string.h>
    00032 #include <time.h>
    00033
    00034 #include "polarssl/config.h"
    00035
    00036 #if defined(POLARSSL_HAVEGE_C)
    00037
    00038 #include "polarssl/havege.h"
    00039 #include "polarssl/timing.h"
    00040
    00041 /* ------------------------------------------------------------------------
    00042  * On average, one iteration accesses two 8-word blocks in the havege WALK
    00043  * table, and generates 16 words in the RES array.
    00044  *
    00045  * The data read in the WALK table is updated and permuted after each use.
    00046  * The result of the hardware clock counter read is used  for this update.
    00047  *
    00048  * 25 conditional tests are present.  The conditional tests are grouped in
    00049  * two nested  groups of 12 conditional tests and 1 test that controls the
    00050  * permutation; on average, there should be 6 tests executed and 3 of them
    00051  * should be mispredicted.
    00052  * ------------------------------------------------------------------------
    00053  */
    00054
    00055 #define SWAP(X,Y) { int *T = X; X = Y; Y = T; }
    00056
    00057 #define TST1_ENTER if( PTEST & 1 ) { PTEST ^= 3; PTEST >>= 1;
    00058 #define TST2_ENTER if( PTEST & 1 ) { PTEST ^= 3; PTEST >>= 1;
    00059
    00060 #define TST1_LEAVE U1++; }
    00061 #define TST2_LEAVE U2++; }
    00062
    00063 #define ONE_ITERATION                                   \
    00064                                                         \
    00065     PTEST = PT1 >> 20;                                  \
    00066                                                         \
    00067     TST1_ENTER  TST1_ENTER  TST1_ENTER  TST1_ENTER      \
    00068     TST1_ENTER  TST1_ENTER  TST1_ENTER  TST1_ENTER      \
    00069     TST1_ENTER  TST1_ENTER  TST1_ENTER  TST1_ENTER      \
    00070                                                         \
    00071     TST1_LEAVE  TST1_LEAVE  TST1_LEAVE  TST1_LEAVE      \
    00072     TST1_LEAVE  TST1_LEAVE  TST1_LEAVE  TST1_LEAVE      \
    00073     TST1_LEAVE  TST1_LEAVE  TST1_LEAVE  TST1_LEAVE      \
    00074                                                         \
    00075     PTX = (PT1 >> 18) & 7;                              \
    00076     PT1 &= 0x1FFF;                                      \
    00077     PT2 &= 0x1FFF;                                      \
    00078     CLK = (int) hardclock();                            \
    00079                                                         \
    00080     i = 0;                                              \
    00081     A = &WALK[PT1    ]; RES[i++] ^= *A;                 \
    00082     B = &WALK[PT2    ]; RES[i++] ^= *B;                 \
    00083     C = &WALK[PT1 ^ 1]; RES[i++] ^= *C;                 \
    00084     D = &WALK[PT2 ^ 4]; RES[i++] ^= *D;                 \
    00085                                                         \
    00086     IN = (*A >> (1)) ^ (*A << (31)) ^ CLK;              \
    00087     *A = (*B >> (2)) ^ (*B << (30)) ^ CLK;              \
    00088     *B = IN ^ U1;                                       \
    00089     *C = (*C >> (3)) ^ (*C << (29)) ^ CLK;              \
    00090     *D = (*D >> (4)) ^ (*D << (28)) ^ CLK;              \
    00091                                                         \
    00092     A = &WALK[PT1 ^ 2]; RES[i++] ^= *A;                 \
    00093     B = &WALK[PT2 ^ 2]; RES[i++] ^= *B;                 \
    00094     C = &WALK[PT1 ^ 3]; RES[i++] ^= *C;                 \
    00095     D = &WALK[PT2 ^ 6]; RES[i++] ^= *D;                 \
    00096                                                         \
    00097     if( PTEST & 1 ) SWAP( A, C );                       \
    00098                                                         \
    00099     IN = (*A >> (5)) ^ (*A << (27)) ^ CLK;              \
    00100     *A = (*B >> (6)) ^ (*B << (26)) ^ CLK;              \
    00101     *B = IN; CLK = (int) hardclock();                   \
    00102     *C = (*C >> (7)) ^ (*C << (25)) ^ CLK;              \
    00103     *D = (*D >> (8)) ^ (*D << (24)) ^ CLK;              \
    00104                                                         \
    00105     A = &WALK[PT1 ^ 4];                                 \
    00106     B = &WALK[PT2 ^ 1];                                 \
    00107                                                         \
    00108     PTEST = PT2 >> 1;                                   \
    00109                                                         \
    00110     PT2 = (RES[(i - 8) ^ PTY] ^ WALK[PT2 ^ PTY ^ 7]);   \
    00111     PT2 = ((PT2 & 0x1FFF) & (~8)) ^ ((PT1 ^ 8) & 0x8);  \
    00112     PTY = (PT2 >> 10) & 7;                              \
    00113                                                         \
    00114     TST2_ENTER  TST2_ENTER  TST2_ENTER  TST2_ENTER      \
    00115     TST2_ENTER  TST2_ENTER  TST2_ENTER  TST2_ENTER      \
    00116     TST2_ENTER  TST2_ENTER  TST2_ENTER  TST2_ENTER      \
    00117                                                         \
    00118     TST2_LEAVE  TST2_LEAVE  TST2_LEAVE  TST2_LEAVE      \
    00119     TST2_LEAVE  TST2_LEAVE  TST2_LEAVE  TST2_LEAVE      \
    00120     TST2_LEAVE  TST2_LEAVE  TST2_LEAVE  TST2_LEAVE      \
    00121                                                         \
    00122     C = &WALK[PT1 ^ 5];                                 \
    00123     D = &WALK[PT2 ^ 5];                                 \
    00124                                                         \
    00125     RES[i++] ^= *A;                                     \
    00126     RES[i++] ^= *B;                                     \
    00127     RES[i++] ^= *C;                                     \
    00128     RES[i++] ^= *D;                                     \
    00129                                                         \
    00130     IN = (*A >> ( 9)) ^ (*A << (23)) ^ CLK;             \
    00131     *A = (*B >> (10)) ^ (*B << (22)) ^ CLK;             \
    00132     *B = IN ^ U2;                                       \
    00133     *C = (*C >> (11)) ^ (*C << (21)) ^ CLK;             \
    00134     *D = (*D >> (12)) ^ (*D << (20)) ^ CLK;             \
    00135                                                         \
    00136     A = &WALK[PT1 ^ 6]; RES[i++] ^= *A;                 \
    00137     B = &WALK[PT2 ^ 3]; RES[i++] ^= *B;                 \
    00138     C = &WALK[PT1 ^ 7]; RES[i++] ^= *C;                 \
    00139     D = &WALK[PT2 ^ 7]; RES[i++] ^= *D;                 \
    00140                                                         \
    00141     IN = (*A >> (13)) ^ (*A << (19)) ^ CLK;             \
    00142     *A = (*B >> (14)) ^ (*B << (18)) ^ CLK;             \
    00143     *B = IN;                                            \
    00144     *C = (*C >> (15)) ^ (*C << (17)) ^ CLK;             \
    00145     *D = (*D >> (16)) ^ (*D << (16)) ^ CLK;             \
    00146                                                         \
    00147     PT1 = ( RES[(i - 8) ^ PTX] ^                        \
    00148             WALK[PT1 ^ PTX ^ 7] ) & (~1);               \
    00149     PT1 ^= (PT2 ^ 0x10) & 0x10;                         \
    00150                                                         \
    00151     for( n++, i = 0; i < 16; i++ )                      \
    00152         hs->pool[n % COLLECT_SIZE] ^= RES[i];
    00153
    00154 /*
    00155  * Entropy gathering function
    00156  */
    00157 static void havege_fill( havege_state *hs )
    00158 {
    00159     int i, n = 0;
    00160     int  U1,  U2, *A, *B, *C, *D;
    00161     int PT1, PT2, *WALK, RES[16];
    00162     int PTX, PTY, CLK, PTEST, IN;
    00163
    00164     WALK = hs->WALK;
    00165     PT1  = hs->PT1;
    00166     PT2  = hs->PT2;
    00167
    00168     PTX  = U1 = 0;
    00169     PTY  = U2 = 0;
    00170
    00171     memset( RES, 0, sizeof( RES ) );
    00172
    00173     while( n < COLLECT_SIZE * 4 )
    00174     {
    00175         ONE_ITERATION
    00176         ONE_ITERATION
    00177         ONE_ITERATION
    00178         ONE_ITERATION
    00179     }
    00180
    00181     hs->PT1 = PT1;
    00182     hs->PT2 = PT2;
    00183
    00184     hs->offset[0] = 0;
    00185     hs->offset[1] = COLLECT_SIZE / 2;
    00186 }
    00187
    00188 /*
    00189  * HAVEGE initialization
    00190  */
    00191 void havege_init( havege_state *hs )
    00192 {
    00193     memset( hs, 0, sizeof( havege_state ) );
    00194
    00195     havege_fill( hs );
    00196 }
    00197
    00198 /*
    00199  * HAVEGE rand function
    00200  */
    00201 int havege_rand( void *p_rng )
    00202 {
    00203     int ret;
    00204     havege_state *hs = (havege_state *) p_rng;
    00205
    00206     if( hs->offset[1] >= COLLECT_SIZE )
    00207         havege_fill( hs );
    00208
    00209     ret  = hs->pool[hs->offset[0]++];
    00210     ret ^= hs->pool[hs->offset[1]++];
    00211
    00212     return( ret );
    00213 }
    00214
    00215 #if defined(POLARSSL_RAND_TEST)
    00216
    00217 #include <stdio.h>
    00218
    00219 int main( int argc, char *argv[] )
    00220 {
    00221     FILE *f;
    00222     time_t t;
    00223     int i, j, k;
    00224     havege_state hs;
    00225     unsigned char buf[1024];
    00226
    00227     if( argc < 2 )
    00228     {
    00229         fprintf( stderr, "usage: %s <output filename>\n", argv[0] );
    00230         return( 1 );
    00231     }
    00232
    00233     if( ( f = fopen( argv[1], "wb+" ) ) == NULL )
    00234     {
    00235         printf( "failed to open '%s' for writing.\n", argv[0] );
    00236         return( 1 );
    00237     }
    00238
    00239     havege_init( &hs );
    00240
    00241     t = time( NULL );
    00242
    00243     for( i = 0, k = 32768; i < k; i++ )
    00244     {
    00245         for( j = 0; j < sizeof( buf ); j++ )
    00246             buf[j] = havege_rand( &hs );
    00247
    00248         fwrite( buf, sizeof( buf ), 1, f );
    00249
    00250         printf( "Generating 32Mb of data in file '%s'... %04.1f" \
    00251                 "%% done\r", argv[1], (100 * (float) (i + 1)) / k );
    00252         fflush( stdout );
    00253     }
    00254
    00255     if( t == time( NULL ) )
    00256         t--;
    00257
    00258     fclose( f );
    00259     return( 0 );
    00260 }
    00261
    00262 #endif
    00263
    00264 #endif