1 /** 2 * \brief HAVEGE: HArdware Volatile Entropy Gathering and Expansion 3 * 4 * Copyright (C) 2006-2015, ARM Limited, All Rights Reserved 5 * SPDX-License-Identifier: GPL-2.0 6 * 7 * This program is free software; you can redistribute it and/or modify 8 * it under the terms of the GNU General Public License as published by 9 * the Free Software Foundation; either version 2 of the License, or 10 * (at your option) any later version. 11 * 12 * This program is distributed in the hope that it will be useful, 13 * but WITHOUT ANY WARRANTY; without even the implied warranty of 14 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 15 * GNU General Public License for more details. 16 * 17 * You should have received a copy of the GNU General Public License along 18 * with this program; if not, write to the Free Software Foundation, Inc., 19 * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA. 20 * 21 * This file is part of mbed TLS (https://tls.mbed.org) 22 */ 23 /* 24 * The HAVEGE RNG was designed by Andre Seznec in 2002. 25 * 26 * http://www.irisa.fr/caps/projects/hipsor/publi.php 27 * 28 * Contact: seznec(at)irisa_dot_fr - orocheco(at)irisa_dot_fr 29 */ 30 31 #if !defined(MBEDTLS_CONFIG_FILE) 32 #include "mbedtls/config.h" 33 #else 34 #include MBEDTLS_CONFIG_FILE 35 #endif 36 37 #if defined(MBEDTLS_HAVEGE_C) 38 39 #include "mbedtls/havege.h" 40 #include "mbedtls/timing.h" 41 42 #include <limits.h> 43 #include <string.h> 44 45 /* If int isn't capable of storing 2^32 distinct values, the code of this 46 * module may cause a processor trap or a miscalculation. If int is more 47 * than 32 bits, the code may not calculate the intended values. */ 48 #if INT_MIN + 1 != -0x7fffffff 49 #error "The HAVEGE module requires int to be exactly 32 bits, with INT_MIN = -2^31." 50 #endif 51 #if UINT_MAX != 0xffffffff 52 #error "The HAVEGE module requires unsigned to be exactly 32 bits." 53 #endif 54 55 /* Implementation that should never be optimized out by the compiler */ 56 static void mbedtls_zeroize( void *v, size_t n ) { 57 volatile unsigned char *p = v; while( n-- ) *p++ = 0; 58 } 59 60 /* ------------------------------------------------------------------------ 61 * On average, one iteration accesses two 8-word blocks in the havege WALK 62 * table, and generates 16 words in the RES array. 63 * 64 * The data read in the WALK table is updated and permuted after each use. 65 * The result of the hardware clock counter read is used for this update. 66 * 67 * 25 conditional tests are present. The conditional tests are grouped in 68 * two nested groups of 12 conditional tests and 1 test that controls the 69 * permutation; on average, there should be 6 tests executed and 3 of them 70 * should be mispredicted. 71 * ------------------------------------------------------------------------ 72 */ 73 74 #define SWAP(X,Y) { unsigned *T = (X); (X) = (Y); (Y) = T; } 75 76 #define TST1_ENTER if( PTEST & 1 ) { PTEST ^= 3; PTEST >>= 1; 77 #define TST2_ENTER if( PTEST & 1 ) { PTEST ^= 3; PTEST >>= 1; 78 79 #define TST1_LEAVE U1++; } 80 #define TST2_LEAVE U2++; } 81 82 #define ONE_ITERATION \ 83 \ 84 PTEST = PT1 >> 20; \ 85 \ 86 TST1_ENTER TST1_ENTER TST1_ENTER TST1_ENTER \ 87 TST1_ENTER TST1_ENTER TST1_ENTER TST1_ENTER \ 88 TST1_ENTER TST1_ENTER TST1_ENTER TST1_ENTER \ 89 \ 90 TST1_LEAVE TST1_LEAVE TST1_LEAVE TST1_LEAVE \ 91 TST1_LEAVE TST1_LEAVE TST1_LEAVE TST1_LEAVE \ 92 TST1_LEAVE TST1_LEAVE TST1_LEAVE TST1_LEAVE \ 93 \ 94 PTX = (PT1 >> 18) & 7; \ 95 PT1 &= 0x1FFF; \ 96 PT2 &= 0x1FFF; \ 97 CLK = (unsigned) mbedtls_timing_hardclock(); \ 98 \ 99 i = 0; \ 100 A = &WALK[PT1 ]; RES[i++] ^= *A; \ 101 B = &WALK[PT2 ]; RES[i++] ^= *B; \ 102 C = &WALK[PT1 ^ 1]; RES[i++] ^= *C; \ 103 D = &WALK[PT2 ^ 4]; RES[i++] ^= *D; \ 104 \ 105 IN = (*A >> (1)) ^ (*A << (31)) ^ CLK; \ 106 *A = (*B >> (2)) ^ (*B << (30)) ^ CLK; \ 107 *B = IN ^ U1; \ 108 *C = (*C >> (3)) ^ (*C << (29)) ^ CLK; \ 109 *D = (*D >> (4)) ^ (*D << (28)) ^ CLK; \ 110 \ 111 A = &WALK[PT1 ^ 2]; RES[i++] ^= *A; \ 112 B = &WALK[PT2 ^ 2]; RES[i++] ^= *B; \ 113 C = &WALK[PT1 ^ 3]; RES[i++] ^= *C; \ 114 D = &WALK[PT2 ^ 6]; RES[i++] ^= *D; \ 115 \ 116 if( PTEST & 1 ) SWAP( A, C ); \ 117 \ 118 IN = (*A >> (5)) ^ (*A << (27)) ^ CLK; \ 119 *A = (*B >> (6)) ^ (*B << (26)) ^ CLK; \ 120 *B = IN; CLK = (unsigned) mbedtls_timing_hardclock(); \ 121 *C = (*C >> (7)) ^ (*C << (25)) ^ CLK; \ 122 *D = (*D >> (8)) ^ (*D << (24)) ^ CLK; \ 123 \ 124 A = &WALK[PT1 ^ 4]; \ 125 B = &WALK[PT2 ^ 1]; \ 126 \ 127 PTEST = PT2 >> 1; \ 128 \ 129 PT2 = (RES[(i - 8) ^ PTY] ^ WALK[PT2 ^ PTY ^ 7]); \ 130 PT2 = ((PT2 & 0x1FFF) & (~8)) ^ ((PT1 ^ 8) & 0x8); \ 131 PTY = (PT2 >> 10) & 7; \ 132 \ 133 TST2_ENTER TST2_ENTER TST2_ENTER TST2_ENTER \ 134 TST2_ENTER TST2_ENTER TST2_ENTER TST2_ENTER \ 135 TST2_ENTER TST2_ENTER TST2_ENTER TST2_ENTER \ 136 \ 137 TST2_LEAVE TST2_LEAVE TST2_LEAVE TST2_LEAVE \ 138 TST2_LEAVE TST2_LEAVE TST2_LEAVE TST2_LEAVE \ 139 TST2_LEAVE TST2_LEAVE TST2_LEAVE TST2_LEAVE \ 140 \ 141 C = &WALK[PT1 ^ 5]; \ 142 D = &WALK[PT2 ^ 5]; \ 143 \ 144 RES[i++] ^= *A; \ 145 RES[i++] ^= *B; \ 146 RES[i++] ^= *C; \ 147 RES[i++] ^= *D; \ 148 \ 149 IN = (*A >> ( 9)) ^ (*A << (23)) ^ CLK; \ 150 *A = (*B >> (10)) ^ (*B << (22)) ^ CLK; \ 151 *B = IN ^ U2; \ 152 *C = (*C >> (11)) ^ (*C << (21)) ^ CLK; \ 153 *D = (*D >> (12)) ^ (*D << (20)) ^ CLK; \ 154 \ 155 A = &WALK[PT1 ^ 6]; RES[i++] ^= *A; \ 156 B = &WALK[PT2 ^ 3]; RES[i++] ^= *B; \ 157 C = &WALK[PT1 ^ 7]; RES[i++] ^= *C; \ 158 D = &WALK[PT2 ^ 7]; RES[i++] ^= *D; \ 159 \ 160 IN = (*A >> (13)) ^ (*A << (19)) ^ CLK; \ 161 *A = (*B >> (14)) ^ (*B << (18)) ^ CLK; \ 162 *B = IN; \ 163 *C = (*C >> (15)) ^ (*C << (17)) ^ CLK; \ 164 *D = (*D >> (16)) ^ (*D << (16)) ^ CLK; \ 165 \ 166 PT1 = ( RES[( i - 8 ) ^ PTX] ^ \ 167 WALK[PT1 ^ PTX ^ 7] ) & (~1); \ 168 PT1 ^= (PT2 ^ 0x10) & 0x10; \ 169 \ 170 for( n++, i = 0; i < 16; i++ ) \ 171 POOL[n % MBEDTLS_HAVEGE_COLLECT_SIZE] ^= RES[i]; 172 173 /* 174 * Entropy gathering function 175 */ 176 static void havege_fill( mbedtls_havege_state *hs ) 177 { 178 unsigned i, n = 0; 179 unsigned U1, U2, *A, *B, *C, *D; 180 unsigned PT1, PT2, *WALK, *POOL, RES[16]; 181 unsigned PTX, PTY, CLK, PTEST, IN; 182 183 WALK = (unsigned *) hs->WALK; 184 POOL = (unsigned *) hs->pool; 185 PT1 = hs->PT1; 186 PT2 = hs->PT2; 187 188 PTX = U1 = 0; 189 PTY = U2 = 0; 190 191 (void)PTX; 192 193 memset( RES, 0, sizeof( RES ) ); 194 195 while( n < MBEDTLS_HAVEGE_COLLECT_SIZE * 4 ) 196 { 197 ONE_ITERATION 198 ONE_ITERATION 199 ONE_ITERATION 200 ONE_ITERATION 201 } 202 203 hs->PT1 = PT1; 204 hs->PT2 = PT2; 205 206 hs->offset[0] = 0; 207 hs->offset[1] = MBEDTLS_HAVEGE_COLLECT_SIZE / 2; 208 } 209 210 /* 211 * HAVEGE initialization 212 */ 213 void mbedtls_havege_init( mbedtls_havege_state *hs ) 214 { 215 memset( hs, 0, sizeof( mbedtls_havege_state ) ); 216 217 havege_fill( hs ); 218 } 219 220 void mbedtls_havege_free( mbedtls_havege_state *hs ) 221 { 222 if( hs == NULL ) 223 return; 224 225 mbedtls_zeroize( hs, sizeof( mbedtls_havege_state ) ); 226 } 227 228 /* 229 * HAVEGE rand function 230 */ 231 int mbedtls_havege_random( void *p_rng, unsigned char *buf, size_t len ) 232 { 233 int val; 234 size_t use_len; 235 mbedtls_havege_state *hs = (mbedtls_havege_state *) p_rng; 236 unsigned char *p = buf; 237 238 while( len > 0 ) 239 { 240 use_len = len; 241 if( use_len > sizeof(int) ) 242 use_len = sizeof(int); 243 244 if( hs->offset[1] >= MBEDTLS_HAVEGE_COLLECT_SIZE ) 245 havege_fill( hs ); 246 247 val = hs->pool[hs->offset[0]++]; 248 val ^= hs->pool[hs->offset[1]++]; 249 250 memcpy( p, &val, use_len ); 251 252 len -= use_len; 253 p += use_len; 254 } 255 256 return( 0 ); 257 } 258 259 #endif /* MBEDTLS_HAVEGE_C */ 260