PolarSSL v1.2.12
havege.c
Go to the documentation of this file.
1 
25 /*
26  * The HAVEGE RNG was designed by Andre Seznec in 2002.
27  *
28  * http://www.irisa.fr/caps/projects/hipsor/publi.php
29  *
30  * Contact: seznec(at)irisa_dot_fr - orocheco(at)irisa_dot_fr
31  */
32 
33 #include "polarssl/config.h"
34 
35 #if defined(POLARSSL_HAVEGE_C)
36 
37 #include "polarssl/havege.h"
38 #include "polarssl/timing.h"
39 
40 #include <string.h>
41 #include <time.h>
42 
43 /* ------------------------------------------------------------------------
44  * On average, one iteration accesses two 8-word blocks in the havege WALK
45  * table, and generates 16 words in the RES array.
46  *
47  * The data read in the WALK table is updated and permuted after each use.
48  * The result of the hardware clock counter read is used for this update.
49  *
50  * 25 conditional tests are present. The conditional tests are grouped in
51  * two nested groups of 12 conditional tests and 1 test that controls the
52  * permutation; on average, there should be 6 tests executed and 3 of them
53  * should be mispredicted.
54  * ------------------------------------------------------------------------
55  */
56 
57 #define SWAP(X,Y) { int *T = X; X = Y; Y = T; }
58 
59 #define TST1_ENTER if( PTEST & 1 ) { PTEST ^= 3; PTEST >>= 1;
60 #define TST2_ENTER if( PTEST & 1 ) { PTEST ^= 3; PTEST >>= 1;
61 
62 #define TST1_LEAVE U1++; }
63 #define TST2_LEAVE U2++; }
64 
65 #define ONE_ITERATION \
66  \
67  PTEST = PT1 >> 20; \
68  \
69  TST1_ENTER TST1_ENTER TST1_ENTER TST1_ENTER \
70  TST1_ENTER TST1_ENTER TST1_ENTER TST1_ENTER \
71  TST1_ENTER TST1_ENTER TST1_ENTER TST1_ENTER \
72  \
73  TST1_LEAVE TST1_LEAVE TST1_LEAVE TST1_LEAVE \
74  TST1_LEAVE TST1_LEAVE TST1_LEAVE TST1_LEAVE \
75  TST1_LEAVE TST1_LEAVE TST1_LEAVE TST1_LEAVE \
76  \
77  PTX = (PT1 >> 18) & 7; \
78  PT1 &= 0x1FFF; \
79  PT2 &= 0x1FFF; \
80  CLK = (int) hardclock(); \
81  \
82  i = 0; \
83  A = &WALK[PT1 ]; RES[i++] ^= *A; \
84  B = &WALK[PT2 ]; RES[i++] ^= *B; \
85  C = &WALK[PT1 ^ 1]; RES[i++] ^= *C; \
86  D = &WALK[PT2 ^ 4]; RES[i++] ^= *D; \
87  \
88  IN = (*A >> (1)) ^ (*A << (31)) ^ CLK; \
89  *A = (*B >> (2)) ^ (*B << (30)) ^ CLK; \
90  *B = IN ^ U1; \
91  *C = (*C >> (3)) ^ (*C << (29)) ^ CLK; \
92  *D = (*D >> (4)) ^ (*D << (28)) ^ CLK; \
93  \
94  A = &WALK[PT1 ^ 2]; RES[i++] ^= *A; \
95  B = &WALK[PT2 ^ 2]; RES[i++] ^= *B; \
96  C = &WALK[PT1 ^ 3]; RES[i++] ^= *C; \
97  D = &WALK[PT2 ^ 6]; RES[i++] ^= *D; \
98  \
99  if( PTEST & 1 ) SWAP( A, C ); \
100  \
101  IN = (*A >> (5)) ^ (*A << (27)) ^ CLK; \
102  *A = (*B >> (6)) ^ (*B << (26)) ^ CLK; \
103  *B = IN; CLK = (int) hardclock(); \
104  *C = (*C >> (7)) ^ (*C << (25)) ^ CLK; \
105  *D = (*D >> (8)) ^ (*D << (24)) ^ CLK; \
106  \
107  A = &WALK[PT1 ^ 4]; \
108  B = &WALK[PT2 ^ 1]; \
109  \
110  PTEST = PT2 >> 1; \
111  \
112  PT2 = (RES[(i - 8) ^ PTY] ^ WALK[PT2 ^ PTY ^ 7]); \
113  PT2 = ((PT2 & 0x1FFF) & (~8)) ^ ((PT1 ^ 8) & 0x8); \
114  PTY = (PT2 >> 10) & 7; \
115  \
116  TST2_ENTER TST2_ENTER TST2_ENTER TST2_ENTER \
117  TST2_ENTER TST2_ENTER TST2_ENTER TST2_ENTER \
118  TST2_ENTER TST2_ENTER TST2_ENTER TST2_ENTER \
119  \
120  TST2_LEAVE TST2_LEAVE TST2_LEAVE TST2_LEAVE \
121  TST2_LEAVE TST2_LEAVE TST2_LEAVE TST2_LEAVE \
122  TST2_LEAVE TST2_LEAVE TST2_LEAVE TST2_LEAVE \
123  \
124  C = &WALK[PT1 ^ 5]; \
125  D = &WALK[PT2 ^ 5]; \
126  \
127  RES[i++] ^= *A; \
128  RES[i++] ^= *B; \
129  RES[i++] ^= *C; \
130  RES[i++] ^= *D; \
131  \
132  IN = (*A >> ( 9)) ^ (*A << (23)) ^ CLK; \
133  *A = (*B >> (10)) ^ (*B << (22)) ^ CLK; \
134  *B = IN ^ U2; \
135  *C = (*C >> (11)) ^ (*C << (21)) ^ CLK; \
136  *D = (*D >> (12)) ^ (*D << (20)) ^ CLK; \
137  \
138  A = &WALK[PT1 ^ 6]; RES[i++] ^= *A; \
139  B = &WALK[PT2 ^ 3]; RES[i++] ^= *B; \
140  C = &WALK[PT1 ^ 7]; RES[i++] ^= *C; \
141  D = &WALK[PT2 ^ 7]; RES[i++] ^= *D; \
142  \
143  IN = (*A >> (13)) ^ (*A << (19)) ^ CLK; \
144  *A = (*B >> (14)) ^ (*B << (18)) ^ CLK; \
145  *B = IN; \
146  *C = (*C >> (15)) ^ (*C << (17)) ^ CLK; \
147  *D = (*D >> (16)) ^ (*D << (16)) ^ CLK; \
148  \
149  PT1 = ( RES[(i - 8) ^ PTX] ^ \
150  WALK[PT1 ^ PTX ^ 7] ) & (~1); \
151  PT1 ^= (PT2 ^ 0x10) & 0x10; \
152  \
153  for( n++, i = 0; i < 16; i++ ) \
154  hs->pool[n % COLLECT_SIZE] ^= RES[i];
155 
156 /*
157  * Entropy gathering function
158  */
159 static void havege_fill( havege_state *hs )
160 {
161  int i, n = 0;
162  int U1, U2, *A, *B, *C, *D;
163  int PT1, PT2, *WALK, RES[16];
164  int PTX, PTY, CLK, PTEST, IN;
165 
166  WALK = hs->WALK;
167  PT1 = hs->PT1;
168  PT2 = hs->PT2;
169 
170  PTX = U1 = 0;
171  PTY = U2 = 0;
172 
173  memset( RES, 0, sizeof( RES ) );
174 
175  while( n < COLLECT_SIZE * 4 )
176  {
177  ONE_ITERATION
178  ONE_ITERATION
179  ONE_ITERATION
180  ONE_ITERATION
181  }
182 
183  hs->PT1 = PT1;
184  hs->PT2 = PT2;
185 
186  hs->offset[0] = 0;
187  hs->offset[1] = COLLECT_SIZE / 2;
188 }
189 
190 /*
191  * HAVEGE initialization
192  */
193 void havege_init( havege_state *hs )
194 {
195  memset( hs, 0, sizeof( havege_state ) );
196 
197  havege_fill( hs );
198 }
199 
200 /*
201  * HAVEGE rand function
202  */
203 int havege_random( void *p_rng, unsigned char *buf, size_t len )
204 {
205  int val;
206  size_t use_len;
207  havege_state *hs = (havege_state *) p_rng;
208  unsigned char *p = buf;
209 
210  while( len > 0 )
211  {
212  use_len = len;
213  if( use_len > sizeof(int) )
214  use_len = sizeof(int);
215 
216  if( hs->offset[1] >= COLLECT_SIZE )
217  havege_fill( hs );
218 
219  val = hs->pool[hs->offset[0]++];
220  val ^= hs->pool[hs->offset[1]++];
221 
222  memcpy( p, &val, use_len );
223 
224  len -= use_len;
225  p += use_len;
226  }
227 
228  return( 0 );
229 }
230 
231 #endif
#define COLLECT_SIZE
Definition: havege.h:32
Configuration options (set of defines)
int PT2
Definition: havege.h:39
HAVEGE state structure.
Definition: havege.h:37
HAVEGE: HArdware Volatile Entropy Gathering and Expansion.
int pool[COLLECT_SIZE]
Definition: havege.h:40
int WALK[8192]
Definition: havege.h:41
int havege_random(void *p_rng, unsigned char *output, size_t len)
HAVEGE rand function.
int offset[2]
Definition: havege.h:39
void havege_init(havege_state *hs)
HAVEGE initialization.
int PT1
Definition: havege.h:39
Portable interface to the CPU cycle counter.