library/havege.c

   1 /*
   2  *      HAVEGE: HArdware Volatile Entropy Gathering and Expansion
   3  *
   4  *      Based on XySSL: Copyright (C) 2006-2008  Christophe Devine
   5  *
   6  *      Copyright (C) 2009      Paul Bakker <polarssl_maintainer at polarssl dot org>
   7  *
   8  *      All rights reserved.
   9  *
  10  *      Redistribution and use in source and binary forms, with or without
  11  *      modification, are permitted provided that the following conditions
  12  *      are met:
  13  *
  14  *        * Redistributions of source code must retain the above copyright
  15  *              notice, this list of conditions and the following disclaimer.
  16  *        * Redistributions in binary form must reproduce the above copyright
  17  *              notice, this list of conditions and the following disclaimer in the
  18  *              documentation and/or other materials provided with the distribution.
  19  *        * Neither the names of PolarSSL or XySSL nor the names of its contributors
  20  *              may be used to endorse or promote products derived from this software
  21  *              without specific prior written permission.
  22  *
  23  *      THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
  24  *      "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
  25  *      LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
  26  *      FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
  27  *      OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
  28  *      SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED
  29  *      TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
  30  *      PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
  31  *      LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
  32  *      NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
  33  *      SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  34  */
  35 /*
  36  *      The HAVEGE RNG was designed by Andre Seznec in 2002.
  37  *
  38  *      http://www.irisa.fr/caps/projects/hipsor/publi.php
  39  *
  40  *      Contact: seznec(at)irisa_dot_fr - orocheco(at)irisa_dot_fr
  41  */
  42
  43 #include <string.h>
  44 #include <time.h>
  45
  46 #include "tropicssl/config.h"
  47
  48 #if defined(TROPICSSL_HAVEGE_C)
  49
  50 #include "tropicssl/havege.h"
  51 #include "tropicssl/timing.h"
  52
  53 /* ------------------------------------------------------------------------
  54  * On average, one iteration accesses two 8-word blocks in the havege WALK
  55  * table, and generates 16 words in the RES array.
  56  *
  57  * The data read in the WALK table is updated and permuted after each use.
  58  * The result of the hardware clock counter read is used  for this update.
  59  *
  60  * 25 conditional tests are present.  The conditional tests are grouped in
  61  * two nested  groups of 12 conditional tests and 1 test that controls the
  62  * permutation; on average, there should be 6 tests executed and 3 of them
  63  * should be mispredicted.
  64  * ------------------------------------------------------------------------
  65  */
  66
  67 #define SWAP(X,Y) { int *T = X; X = Y; Y = T; }
  68
  69 #define TST1_ENTER if( PTEST & 1 ) { PTEST ^= 3; PTEST >>= 1;
  70 #define TST2_ENTER if( PTEST & 1 ) { PTEST ^= 3; PTEST >>= 1;
  71
  72 #define TST1_LEAVE U1++; }
  73 #define TST2_LEAVE U2++; }
  74
  75 #define ONE_ITERATION                                                                   \
  76                                                                                                                 \
  77         PTEST = PT1 >> 20;                                                                      \
  78                                                                                                                 \
  79         TST1_ENTER      TST1_ENTER      TST1_ENTER      TST1_ENTER              \
  80         TST1_ENTER      TST1_ENTER      TST1_ENTER      TST1_ENTER              \
  81         TST1_ENTER      TST1_ENTER      TST1_ENTER      TST1_ENTER              \
  82                                                                                                                 \
  83         TST1_LEAVE      TST1_LEAVE      TST1_LEAVE      TST1_LEAVE              \
  84         TST1_LEAVE      TST1_LEAVE      TST1_LEAVE      TST1_LEAVE              \
  85         TST1_LEAVE      TST1_LEAVE      TST1_LEAVE      TST1_LEAVE              \
  86                                                                                                                 \
  87         PTX = (PT1 >> 18) & 7;                                                          \
  88         PT1 &= 0x1FFF;                                                                          \
  89         PT2 &= 0x1FFF;                                                                          \
  90         CLK = (int) hardclock();                                                        \
  91                                                                                                                 \
  92         i = 0;                                                                                          \
  93         A = &WALK[PT1    ]; RES[i++] ^= *A;                                     \
  94         B = &WALK[PT2    ]; RES[i++] ^= *B;                                     \
  95         C = &WALK[PT1 ^ 1]; RES[i++] ^= *C;                                     \
  96         D = &WALK[PT2 ^ 4]; RES[i++] ^= *D;                                     \
  97                                                                                                                 \
  98         IN = (*A >> (1)) ^ (*A << (31)) ^ CLK;                          \
  99         *A = (*B >> (2)) ^ (*B << (30)) ^ CLK;                          \
 100         *B = IN ^ U1;                                                                           \
 101         *C = (*C >> (3)) ^ (*C << (29)) ^ CLK;                          \
 102         *D = (*D >> (4)) ^ (*D << (28)) ^ CLK;                          \
 103                                                                                                                 \
 104         A = &WALK[PT1 ^ 2]; RES[i++] ^= *A;                                     \
 105         B = &WALK[PT2 ^ 2]; RES[i++] ^= *B;                                     \
 106         C = &WALK[PT1 ^ 3]; RES[i++] ^= *C;                                     \
 107         D = &WALK[PT2 ^ 6]; RES[i++] ^= *D;                                     \
 108                                                                                                                 \
 109         if( PTEST & 1 ) SWAP( A, C );                                           \
 110                                                                                                                 \
 111         IN = (*A >> (5)) ^ (*A << (27)) ^ CLK;                          \
 112         *A = (*B >> (6)) ^ (*B << (26)) ^ CLK;                          \
 113         *B = IN; CLK = (int) hardclock();                                       \
 114         *C = (*C >> (7)) ^ (*C << (25)) ^ CLK;                          \
 115         *D = (*D >> (8)) ^ (*D << (24)) ^ CLK;                          \
 116                                                                                                                 \
 117         A = &WALK[PT1 ^ 4];                                                                     \
 118         B = &WALK[PT2 ^ 1];                                                                     \
 119                                                                                                                 \
 120         PTEST = PT2 >> 1;                                                                       \
 121                                                                                                                 \
 122         PT2 = (RES[(i - 8) ^ PTY] ^ WALK[PT2 ^ PTY ^ 7]);       \
 123         PT2 = ((PT2 & 0x1FFF) & (~8)) ^ ((PT1 ^ 8) & 0x8);      \
 124         PTY = (PT2 >> 10) & 7;                                                          \
 125                                                                                                                 \
 126         TST2_ENTER      TST2_ENTER      TST2_ENTER      TST2_ENTER              \
 127         TST2_ENTER      TST2_ENTER      TST2_ENTER      TST2_ENTER              \
 128         TST2_ENTER      TST2_ENTER      TST2_ENTER      TST2_ENTER              \
 129                                                                                                                 \
 130         TST2_LEAVE      TST2_LEAVE      TST2_LEAVE      TST2_LEAVE              \
 131         TST2_LEAVE      TST2_LEAVE      TST2_LEAVE      TST2_LEAVE              \
 132         TST2_LEAVE      TST2_LEAVE      TST2_LEAVE      TST2_LEAVE              \
 133                                                                                                                 \
 134         C = &WALK[PT1 ^ 5];                                                                     \
 135         D = &WALK[PT2 ^ 5];                                                                     \
 136                                                                                                                 \
 137         RES[i++] ^= *A;                                                                         \
 138         RES[i++] ^= *B;                                                                         \
 139         RES[i++] ^= *C;                                                                         \
 140         RES[i++] ^= *D;                                                                         \
 141                                                                                                                 \
 142         IN = (*A >> ( 9)) ^ (*A << (23)) ^ CLK;                         \
 143         *A = (*B >> (10)) ^ (*B << (22)) ^ CLK;                         \
 144         *B = IN ^ U2;                                                                           \
 145         *C = (*C >> (11)) ^ (*C << (21)) ^ CLK;                         \
 146         *D = (*D >> (12)) ^ (*D << (20)) ^ CLK;                         \
 147                                                                                                                 \
 148         A = &WALK[PT1 ^ 6]; RES[i++] ^= *A;                                     \
 149         B = &WALK[PT2 ^ 3]; RES[i++] ^= *B;                                     \
 150         C = &WALK[PT1 ^ 7]; RES[i++] ^= *C;                                     \
 151         D = &WALK[PT2 ^ 7]; RES[i++] ^= *D;                                     \
 152                                                                                                                 \
 153         IN = (*A >> (13)) ^ (*A << (19)) ^ CLK;                         \
 154         *A = (*B >> (14)) ^ (*B << (18)) ^ CLK;                         \
 155         *B = IN;                                                                                        \
 156         *C = (*C >> (15)) ^ (*C << (17)) ^ CLK;                         \
 157         *D = (*D >> (16)) ^ (*D << (16)) ^ CLK;                         \
 158                                                                                                                 \
 159         PT1 = ( RES[(i - 8) ^ PTX] ^                                            \
 160                         WALK[PT1 ^ PTX ^ 7] ) & (~1);                           \
 161         PT1 ^= (PT2 ^ 0x10) & 0x10;                                                     \
 162                                                                                                                 \
 163         for( n++, i = 0; i < 16; i++ )                                          \
 164                 hs->pool[n % COLLECT_SIZE] ^= RES[i];
 165
 166 /*
 167  * Entropy gathering function
 168  */
 169 static void havege_fill(havege_state * hs)
 170 {
 171         int i, n = 0;
 172         int U1, U2, *A, *B, *C, *D;
 173         int PT1, PT2, *WALK, RES[16];
 174         int PTX, PTY, CLK, PTEST, IN;
 175
 176         WALK = hs->WALK;
 177         PT1 = hs->PT1;
 178         PT2 = hs->PT2;
 179
 180         PTX = U1 = 0;
 181         PTY = U2 = 0;
 182
 183         memset(RES, 0, sizeof(RES));
 184
 185         while (n < COLLECT_SIZE * 4) {
 186         ONE_ITERATION ONE_ITERATION ONE_ITERATION ONE_ITERATION} hs->PT1 = PT1;
 187         hs->PT2 = PT2;
 188
 189         hs->offset[0] = 0;
 190         hs->offset[1] = COLLECT_SIZE / 2;
 191 }
 192
 193 /*
 194  * HAVEGE initialization
 195  */
 196 void havege_init(havege_state * hs)
 197 {
 198         memset(hs, 0, sizeof(havege_state));
 199
 200         havege_fill(hs);
 201 }
 202
 203 /*
 204  * HAVEGE rand function
 205  */
 206 int havege_rand(void *p_rng)
 207 {
 208         int ret;
 209         havege_state *hs = (havege_state *) p_rng;
 210
 211         if (hs->offset[1] >= COLLECT_SIZE)
 212                 havege_fill(hs);
 213
 214         ret = hs->pool[hs->offset[0]++];
 215         ret ^= hs->pool[hs->offset[1]++];
 216
 217         return (ret);
 218 }
 219
 220 #if defined(TROPICSSL_RAND_TEST)
 221
 222 #include <stdio.h>
 223
 224 int main(int argc, char *argv[])
 225 {
 226         FILE *f;
 227         time_t t;
 228         int i, j, k;
 229         havege_state hs;
 230         unsigned char buf[1024];
 231
 232         if (argc < 2) {
 233                 fprintf(stderr, "usage: %s <output filename>\n", argv[0]);
 234                 return (1);
 235         }
 236
 237         if ((f = fopen(argv[1], "wb+")) == NULL) {
 238                 printf("failed to open '%s' for writing.\n", argv[0]);
 239                 return (1);
 240         }
 241
 242         havege_init(&hs);
 243
 244         t = time(NULL);
 245
 246         for (i = 0, k = 32768; i < k; i++) {
 247                 for (j = 0; j < sizeof(buf); j++)
 248                         buf[j] = havege_rand(&hs);
 249
 250                 fwrite(buf, sizeof(buf), 1, f);
 251
 252                 printf("Generating 32Mb of data in file '%s'... %04.1f"
 253                        "%% done\r", argv[1], (100 * (float)(i + 1)) / k);
 254                 fflush(stdout);
 255         }
 256
 257         if (t == time(NULL))
 258                 t--;
 259
 260         fclose(f);
 261         return (0);
 262 }
 263
 264 #endif
 265
 266 #endif