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