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