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