src/xyssl/havege.c

   1 /*
   2  *  HAVEGE: HArdware Volatile Entropy Gathering and Expansion
   3  *
   4  *  Copyright (C) 2006-2007  Christophe Devine
   5  *
   6  *  This library is free software; you can redistribute it and/or
   7  *  modify it under the terms of the GNU Lesser General Public
   8  *  License, version 2.1 as published by the Free Software Foundation.
   9  *
  10  *  This library is distributed in the hope that it will be useful,
  11  *  but WITHOUT ANY WARRANTY; without even the implied warranty of
  12  *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  13  *  Lesser General Public License for more details.
  14  *
  15  *  You should have received a copy of the GNU Lesser General Public
  16  *  License along with this library; if not, write to the Free Software
  17  *  Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston,
  18  *  MA  02110-1301  USA
  19  */
  20 /*
  21  *  The HAVEGE RNG was designed by Andre Seznec in 2002.
  22  *
  23  *  http://www.irisa.fr/caps/projects/hipsor/publi.php
  24  *
  25  *  Contact: seznec(at)irisa_dot_fr - orocheco(at)irisa_dot_fr
  26  */
  27
  28 #include <string.h>
  29 #include <time.h>
  30
  31 #include "xyssl/config.h"
  32
  33 #if defined(XYSSL_HAVEGE_C)
  34
  35 #include "xyssl/havege.h"
  36 #include "xyssl/timing.h"
  37
  38 /* ------------------------------------------------------------------------
  39  * On average, one iteration accesses two 8-word blocks in the havege WALK
  40  * table, and generates 16 words in the RES array.
  41  *
  42  * The data read in the WALK table is updated and permuted after each use.
  43  * The result of the hardware clock counter read is used  for this update.
  44  *
  45  * 25 conditional tests are present.  The conditional tests are grouped in
  46  * two nested  groups of 12 conditional tests and 1 test that controls the
  47  * permutation; on average, there should be 6 tests executed and 3 of them
  48  * should be mispredicted.
  49  * ------------------------------------------------------------------------
  50  */
  51
  52 #define SWAP(X,Y) { int *T = X; X = Y; Y = T; }
  53
  54 #define TST1_ENTER if( PTEST & 1 ) { PTEST ^= 3; PTEST >>= 1;
  55 #define TST2_ENTER if( PTEST & 1 ) { PTEST ^= 3; PTEST >>= 1;
  56
  57 #define TST1_LEAVE U1++; }
  58 #define TST2_LEAVE U2++; }
  59
  60 #define ONE_ITERATION                                   \
  61                                                         \
  62     PTEST = PT1 >> 20;                                  \
  63                                                         \
  64     TST1_ENTER  TST1_ENTER  TST1_ENTER  TST1_ENTER      \
  65     TST1_ENTER  TST1_ENTER  TST1_ENTER  TST1_ENTER      \
  66     TST1_ENTER  TST1_ENTER  TST1_ENTER  TST1_ENTER      \
  67                                                         \
  68     TST1_LEAVE  TST1_LEAVE  TST1_LEAVE  TST1_LEAVE      \
  69     TST1_LEAVE  TST1_LEAVE  TST1_LEAVE  TST1_LEAVE      \
  70     TST1_LEAVE  TST1_LEAVE  TST1_LEAVE  TST1_LEAVE      \
  71                                                         \
  72     PTX = (PT1 >> 18) & 7;                              \
  73     PT1 &= 0x1FFF;                                      \
  74     PT2 &= 0x1FFF;                                      \
  75     CLK = (int) hardclock();                            \
  76                                                         \
  77     i = 0;                                              \
  78     A = &WALK[PT1    ]; RES[i++] ^= *A;                 \
  79     B = &WALK[PT2    ]; RES[i++] ^= *B;                 \
  80     C = &WALK[PT1 ^ 1]; RES[i++] ^= *C;                 \
  81     D = &WALK[PT2 ^ 4]; RES[i++] ^= *D;                 \
  82                                                         \
  83     IN = (*A >> (1)) ^ (*A << (31)) ^ CLK;              \
  84     *A = (*B >> (2)) ^ (*B << (30)) ^ CLK;              \
  85     *B = IN ^ U1;                                       \
  86     *C = (*C >> (3)) ^ (*C << (29)) ^ CLK;              \
  87     *D = (*D >> (4)) ^ (*D << (28)) ^ CLK;              \
  88                                                         \
  89     A = &WALK[PT1 ^ 2]; RES[i++] ^= *A;                 \
  90     B = &WALK[PT2 ^ 2]; RES[i++] ^= *B;                 \
  91     C = &WALK[PT1 ^ 3]; RES[i++] ^= *C;                 \
  92     D = &WALK[PT2 ^ 6]; RES[i++] ^= *D;                 \
  93                                                         \
  94     if( PTEST & 1 ) SWAP( A, C );                       \
  95                                                         \
  96     IN = (*A >> (5)) ^ (*A << (27)) ^ CLK;              \
  97     *A = (*B >> (6)) ^ (*B << (26)) ^ CLK;              \
  98     *B = IN; CLK = (int) hardclock();                   \
  99     *C = (*C >> (7)) ^ (*C << (25)) ^ CLK;              \
 100     *D = (*D >> (8)) ^ (*D << (24)) ^ CLK;              \
 101                                                         \
 102     A = &WALK[PT1 ^ 4];                                 \
 103     B = &WALK[PT2 ^ 1];                                 \
 104                                                         \
 105     PTEST = PT2 >> 1;                                   \
 106                                                         \
 107     PT2 = (RES[(i - 8) ^ PTY] ^ WALK[PT2 ^ PTY ^ 7]);   \
 108     PT2 = ((PT2 & 0x1FFF) & (~8)) ^ ((PT1 ^ 8) & 0x8);  \
 109     PTY = (PT2 >> 10) & 7;                              \
 110                                                         \
 111     TST2_ENTER  TST2_ENTER  TST2_ENTER  TST2_ENTER      \
 112     TST2_ENTER  TST2_ENTER  TST2_ENTER  TST2_ENTER      \
 113     TST2_ENTER  TST2_ENTER  TST2_ENTER  TST2_ENTER      \
 114                                                         \
 115     TST2_LEAVE  TST2_LEAVE  TST2_LEAVE  TST2_LEAVE      \
 116     TST2_LEAVE  TST2_LEAVE  TST2_LEAVE  TST2_LEAVE      \
 117     TST2_LEAVE  TST2_LEAVE  TST2_LEAVE  TST2_LEAVE      \
 118                                                         \
 119     C = &WALK[PT1 ^ 5];                                 \
 120     D = &WALK[PT2 ^ 5];                                 \
 121                                                         \
 122     RES[i++] ^= *A;                                     \
 123     RES[i++] ^= *B;                                     \
 124     RES[i++] ^= *C;                                     \
 125     RES[i++] ^= *D;                                     \
 126                                                         \
 127     IN = (*A >> ( 9)) ^ (*A << (23)) ^ CLK;             \
 128     *A = (*B >> (10)) ^ (*B << (22)) ^ CLK;             \
 129     *B = IN ^ U2;                                       \
 130     *C = (*C >> (11)) ^ (*C << (21)) ^ CLK;             \
 131     *D = (*D >> (12)) ^ (*D << (20)) ^ CLK;             \
 132                                                         \
 133     A = &WALK[PT1 ^ 6]; RES[i++] ^= *A;                 \
 134     B = &WALK[PT2 ^ 3]; RES[i++] ^= *B;                 \
 135     C = &WALK[PT1 ^ 7]; RES[i++] ^= *C;                 \
 136     D = &WALK[PT2 ^ 7]; RES[i++] ^= *D;                 \
 137                                                         \
 138     IN = (*A >> (13)) ^ (*A << (19)) ^ CLK;             \
 139     *A = (*B >> (14)) ^ (*B << (18)) ^ CLK;             \
 140     *B = IN;                                            \
 141     *C = (*C >> (15)) ^ (*C << (17)) ^ CLK;             \
 142     *D = (*D >> (16)) ^ (*D << (16)) ^ CLK;             \
 143                                                         \
 144     PT1 = ( RES[(i - 8) ^ PTX] ^                        \
 145             WALK[PT1 ^ PTX ^ 7] ) & (~1);               \
 146     PT1 ^= (PT2 ^ 0x10) & 0x10;                         \
 147                                                         \
 148     for( n++, i = 0; i < 16; i++ )                      \
 149         hs->pool[n % COLLECT_SIZE] ^= RES[i];
 150
 151 /*
 152  * Entropy gathering function
 153  */
 154 static void havege_fill( havege_state *hs )
 155 {
 156     int i, n = 0;
 157     int  U1,  U2, *A, *B, *C, *D;
 158     int PT1, PT2, *WALK, RES[16];
 159     int PTX, PTY, CLK, PTEST, IN;
 160
 161     WALK = hs->WALK;
 162     PT1  = hs->PT1;
 163     PT2  = hs->PT2;
 164
 165     PTX  = U1 = 0;
 166     PTY  = U2 = 0;
 167
 168     memset( RES, 0, sizeof( RES ) );
 169
 170     while( n < COLLECT_SIZE * 4 )
 171     {
 172         ONE_ITERATION
 173         ONE_ITERATION
 174         ONE_ITERATION
 175         ONE_ITERATION
 176     }
 177
 178     hs->PT1 = PT1;
 179     hs->PT2 = PT2;
 180
 181     hs->offset[0] = 0;
 182     hs->offset[1] = COLLECT_SIZE / 2;
 183 }
 184
 185 /*
 186  * HAVEGE initialization
 187  */
 188 void havege_init( havege_state *hs )
 189 {
 190     memset( hs, 0, sizeof( havege_state ) );
 191
 192     havege_fill( hs );
 193 }
 194
 195 /*
 196  * HAVEGE rand function
 197  */
 198 int havege_rand( void *p_rng )
 199 {
 200     int ret;
 201     havege_state *hs = (havege_state *) p_rng;
 202
 203     if( hs->offset[1] >= COLLECT_SIZE )
 204         havege_fill( hs );
 205
 206     ret  = hs->pool[hs->offset[0]++];
 207     ret ^= hs->pool[hs->offset[1]++];
 208
 209     return( ret );
 210 }
 211
 212 #if defined(XYSSL_RAND_TEST)
 213
 214 #include <stdio.h>
 215
 216 int main( int argc, char *argv[] )
 217 {
 218     FILE *f;
 219     time_t t;
 220     int i, j, k;
 221     havege_state hs;
 222     unsigned char buf[1024];
 223
 224     if( argc < 2 )
 225     {
 226         fprintf( stderr, "usage: %s <output filename>\n", argv[0] );
 227         return( 1 );
 228     }
 229
 230     if( ( f = fopen( argv[1], "wb+" ) ) == NULL )
 231     {
 232         printf( "failed to open '%s' for writing.\n", argv[0] );
 233         return( 1 );
 234     }
 235
 236     havege_init( &hs );
 237
 238     t = time( NULL );
 239
 240     for( i = 0, k = 32768; i < k; i++ )
 241     {
 242         for( j = 0; j < sizeof( buf ); j++ )
 243             buf[j] = havege_rand( &hs );
 244
 245         fwrite( buf, sizeof( buf ), 1, f );
 246
 247         printf( "Generating 32Mb of data in file '%s'... %04.1f" \
 248                 "%% done\r", argv[1], (100 * (float) (i + 1)) / k );
 249         fflush( stdout );
 250     }
 251
 252     if( t == time( NULL ) )
 253         t--;
 254
 255     fclose( f );
 256     return( 0 );
 257 }
 258
 259 #endif
 260
 261 #endif