1/* 2 * Copyright (c) 1999-2013 Apple, Inc. All rights reserved. 3 * 4 * @APPLE_OSREFERENCE_LICENSE_HEADER_START@ 5 * 6 * This file contains Original Code and/or Modifications of Original Code 7 * as defined in and that are subject to the Apple Public Source License 8 * Version 2.0 (the 'License'). You may not use this file except in 9 * compliance with the License. The rights granted to you under the License 10 * may not be used to create, or enable the creation or redistribution of, 11 * unlawful or unlicensed copies of an Apple operating system, or to 12 * circumvent, violate, or enable the circumvention or violation of, any 13 * terms of an Apple operating system software license agreement. 14 * 15 * Please obtain a copy of the License at 16 * http://www.opensource.apple.com/apsl/ and read it before using this file. 17 * 18 * The Original Code and all software distributed under the License are 19 * distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER 20 * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES, 21 * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY, 22 * FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT. 23 * Please see the License for the specific language governing rights and 24 * limitations under the License. 25 * 26 * @APPLE_OSREFERENCE_LICENSE_HEADER_END@ 27 */ 28 29 30#include <string.h> 31#include <kern/cpu_number.h> 32#include <kern/cpu_data.h> 33#include <kern/misc_protos.h> 34#include <kern/thread.h> 35#include <sys/random.h> 36 37#include <corecrypto/ccdrbg.h> 38 39#include <prng/YarrowCoreLib/include/yarrow.h> 40 41#include <libkern/OSByteOrder.h> 42#include <libkern/OSAtomic.h> 43 44#include <mach/mach_time.h> 45 46#include <prng/random.h> 47 48#include "fips_sha1.h" 49 50 51/* 52 WARNING! WARNING! WARNING! WARNING! WARNING! WARNING! WARNING! WARNING! WARNING! 53 54 THIS FILE IS NEEDED TO PASS FIPS ACCEPTANCE FOR THE RANDOM NUMBER GENERATOR. 55 IF YOU ALTER IT IN ANY WAY, WE WILL NEED TO GO THOUGH FIPS ACCEPTANCE AGAIN, 56 AN OPERATION THAT IS VERY EXPENSIVE AND TIME CONSUMING. IN OTHER WORDS, 57 DON'T MESS WITH THIS FILE. 58 59 WARNING! WARNING! WARNING! WARNING! WARNING! WARNING! WARNING! WARNING! WARNING! 60*/ 61/* 62 WARNING! WARNING! WARNING! WARNING! WARNING! WARNING! WARNING! WARNING! WARNING! 63 64 ANY CODE PROTECTED UNDER "#ifdef __arm__" IS SERIOUSLY SUPPOSED TO BE THERE! 65 IF YOU REMOVE ARM CODE, RANDOM WILL NOT MEAN ANYTHING FOR iPHONES ALL OVER. 66 PLEASE DON'T TOUCH __arm__ CODE IN THIS FILE! 67 68 WARNING! WARNING! WARNING! WARNING! WARNING! WARNING! WARNING! WARNING! WARNING! 69*/ 70 71 72#define RESEED_TICKS 50 /* how long a reseed operation can take */ 73 74 75typedef u_int8_t BlockWord; 76enum {kBSize = 20}; 77typedef BlockWord Block[kBSize]; 78enum {kBlockSize = sizeof(Block)}; 79 80struct YarrowContext { 81 PrngRef PrngRef; 82 Block xkey; 83 Block random_data; 84 int bytes_used; 85 unsigned char SelfTestInitialized; 86 u_int32_t LastBlockChecksum; 87 uint64_t bytes_since_reseed; 88}; 89typedef struct YarrowContext *YarrowContextp; 90 91/* define prototypes to keep the compiler happy... */ 92 93void add_blocks(Block a, Block b, BlockWord carry); 94void fips_initialize(YarrowContextp yp); 95void random_block(YarrowContextp yp, Block b, int addOptional); 96u_int32_t CalculateCRC(u_int8_t* buffer, size_t length); 97 98/* 99 * Get 120 bits from yarrow 100 */ 101 102/* 103 * add block b to block a 104 */ 105void 106add_blocks(Block a, Block b, BlockWord carry) 107{ 108 int i = kBlockSize - 1; 109 while (i >= 0) 110 { 111 u_int32_t c = (u_int32_t)carry + 112 (u_int32_t)a[i] + 113 (u_int32_t)b[i]; 114 a[i] = c & 0xff; 115 carry = c >> 8; 116 i -= 1; 117 } 118} 119 120 121 122static char zeros[(512 - kBSize * 8) / 8]; 123 124static const u_int32_t g_crc_table[] = 125{ 126 0x00000000, 0x77073096, 0xEE0E612C, 0x990951BA, 0x076DC419, 0x706AF48F, 0xE963A535, 0x9E6495A3, 127 0x0EDB8832, 0x79DCB8A4, 0xE0D5E91E, 0x97D2D988, 0x09B64C2B, 0x7EB17CBD, 0xE7B82D07, 0x90BF1D91, 128 0x1DB71064, 0x6AB020F2, 0xF3B97148, 0x84BE41DE, 0x1ADAD47D, 0x6DDDE4EB, 0xF4D4B551, 0x83D385C7, 129 0x136C9856, 0x646BA8C0, 0xFD62F97A, 0x8A65C9EC, 0x14015C4F, 0x63066CD9, 0xFA0F3D63, 0x8D080DF5, 130 0x3B6E20C8, 0x4C69105E, 0xD56041E4, 0xA2677172, 0x3C03E4D1, 0x4B04D447, 0xD20D85FD, 0xA50AB56B, 131 0x35B5A8FA, 0x42B2986C, 0xDBBBC9D6, 0xACBCF940, 0x32D86CE3, 0x45DF5C75, 0xDCD60DCF, 0xABD13D59, 132 0x26D930AC, 0x51DE003A, 0xC8D75180, 0xBFD06116, 0x21B4F4B5, 0x56B3C423, 0xCFBA9599, 0xB8BDA50F, 133 0x2802B89E, 0x5F058808, 0xC60CD9B2, 0xB10BE924, 0x2F6F7C87, 0x58684C11, 0xC1611DAB, 0xB6662D3D, 134 0x76DC4190, 0x01DB7106, 0x98D220BC, 0xEFD5102A, 0x71B18589, 0x06B6B51F, 0x9FBFE4A5, 0xE8B8D433, 135 0x7807C9A2, 0x0F00F934, 0x9609A88E, 0xE10E9818, 0x7F6A0DBB, 0x086D3D2D, 0x91646C97, 0xE6635C01, 136 0x6B6B51F4, 0x1C6C6162, 0x856530D8, 0xF262004E, 0x6C0695ED, 0x1B01A57B, 0x8208F4C1, 0xF50FC457, 137 0x65B0D9C6, 0x12B7E950, 0x8BBEB8EA, 0xFCB9887C, 0x62DD1DDF, 0x15DA2D49, 0x8CD37CF3, 0xFBD44C65, 138 0x4DB26158, 0x3AB551CE, 0xA3BC0074, 0xD4BB30E2, 0x4ADFA541, 0x3DD895D7, 0xA4D1C46D, 0xD3D6F4FB, 139 0x4369E96A, 0x346ED9FC, 0xAD678846, 0xDA60B8D0, 0x44042D73, 0x33031DE5, 0xAA0A4C5F, 0xDD0D7CC9, 140 0x5005713C, 0x270241AA, 0xBE0B1010, 0xC90C2086, 0x5768B525, 0x206F85B3, 0xB966D409, 0xCE61E49F, 141 0x5EDEF90E, 0x29D9C998, 0xB0D09822, 0xC7D7A8B4, 0x59B33D17, 0x2EB40D81, 0xB7BD5C3B, 0xC0BA6CAD, 142 0xEDB88320, 0x9ABFB3B6, 0x03B6E20C, 0x74B1D29A, 0xEAD54739, 0x9DD277AF, 0x04DB2615, 0x73DC1683, 143 0xE3630B12, 0x94643B84, 0x0D6D6A3E, 0x7A6A5AA8, 0xE40ECF0B, 0x9309FF9D, 0x0A00AE27, 0x7D079EB1, 144 0xF00F9344, 0x8708A3D2, 0x1E01F268, 0x6906C2FE, 0xF762575D, 0x806567CB, 0x196C3671, 0x6E6B06E7, 145 0xFED41B76, 0x89D32BE0, 0x10DA7A5A, 0x67DD4ACC, 0xF9B9DF6F, 0x8EBEEFF9, 0x17B7BE43, 0x60B08ED5, 146 0xD6D6A3E8, 0xA1D1937E, 0x38D8C2C4, 0x4FDFF252, 0xD1BB67F1, 0xA6BC5767, 0x3FB506DD, 0x48B2364B, 147 0xD80D2BDA, 0xAF0A1B4C, 0x36034AF6, 0x41047A60, 0xDF60EFC3, 0xA867DF55, 0x316E8EEF, 0x4669BE79, 148 0xCB61B38C, 0xBC66831A, 0x256FD2A0, 0x5268E236, 0xCC0C7795, 0xBB0B4703, 0x220216B9, 0x5505262F, 149 0xC5BA3BBE, 0xB2BD0B28, 0x2BB45A92, 0x5CB36A04, 0xC2D7FFA7, 0xB5D0CF31, 0x2CD99E8B, 0x5BDEAE1D, 150 0x9B64C2B0, 0xEC63F226, 0x756AA39C, 0x026D930A, 0x9C0906A9, 0xEB0E363F, 0x72076785, 0x05005713, 151 0x95BF4A82, 0xE2B87A14, 0x7BB12BAE, 0x0CB61B38, 0x92D28E9B, 0xE5D5BE0D, 0x7CDCEFB7, 0x0BDBDF21, 152 0x86D3D2D4, 0xF1D4E242, 0x68DDB3F8, 0x1FDA836E, 0x81BE16CD, 0xF6B9265B, 0x6FB077E1, 0x18B74777, 153 0x88085AE6, 0xFF0F6A70, 0x66063BCA, 0x11010B5C, 0x8F659EFF, 0xF862AE69, 0x616BFFD3, 0x166CCF45, 154 0xA00AE278, 0xD70DD2EE, 0x4E048354, 0x3903B3C2, 0xA7672661, 0xD06016F7, 0x4969474D, 0x3E6E77DB, 155 0xAED16A4A, 0xD9D65ADC, 0x40DF0B66, 0x37D83BF0, 0xA9BCAE53, 0xDEBB9EC5, 0x47B2CF7F, 0x30B5FFE9, 156 0xBDBDF21C, 0xCABAC28A, 0x53B39330, 0x24B4A3A6, 0xBAD03605, 0xCDD70693, 0x54DE5729, 0x23D967BF, 157 0xB3667A2E, 0xC4614AB8, 0x5D681B02, 0x2A6F2B94, 0xB40BBE37, 0xC30C8EA1, 0x5A05DF1B, 0x2D02EF8D, 158}; 159 160/* 161 * Setup for fips compliance 162 */ 163 164/* 165 * calculate a crc-32 checksum 166 */ 167u_int32_t CalculateCRC(u_int8_t* buffer, size_t length) 168{ 169 u_int32_t crc = 0; 170 171 size_t i; 172 for (i = 0; i < length; ++i) 173 { 174 u_int32_t temp = (crc ^ ((u_int32_t) buffer[i])) & 0xFF; 175 crc = (crc >> 8) ^ g_crc_table[temp]; 176 } 177 178 return crc; 179} 180 181/* 182 * get a random block of data per fips 186-2 183 */ 184void 185random_block(YarrowContextp pp, Block b, int addOptional) 186{ 187 SHA1_CTX sha1_ctx; 188 189 int repeatCount = 0; 190 do 191 { 192 // do one iteration 193 194 if (addOptional) 195 { 196 // create an xSeed to add. 197 Block xSeed; 198 prngOutput (pp->PrngRef, (BYTE*) &xSeed, sizeof (xSeed)); 199 200 // add the seed to the previous value of xkey 201 add_blocks (pp->xkey, xSeed, 0); 202 } 203 204 // initialize the value of H 205 FIPS_SHA1Init(&sha1_ctx); 206 207 // to stay compatible with the FIPS specification, we need to flip the bytes in 208 // xkey to little endian byte order. In our case, this makes exactly no difference 209 // (random is random), but we need to do it anyway to keep FIPS happy 210 211 // compute "G" 212 FIPS_SHA1Update(&sha1_ctx, pp->xkey, kBlockSize); 213 214 // add zeros to fill the internal SHA-1 buffer 215 FIPS_SHA1Update (&sha1_ctx, (const u_int8_t *)zeros, sizeof (zeros)); 216 217 // we have to do a byte order correction here because the sha1 math is being done internally 218 // as u_int32_t, not a stream of bytes. Since we maintain our data as a byte stream, we need 219 // to convert 220 221 u_int32_t* finger = (u_int32_t*) b; 222 223 unsigned j; 224 for (j = 0; j < kBlockSize / sizeof (u_int32_t); ++j) 225 { 226 *finger++ = OSSwapHostToBigInt32(sha1_ctx.h.b32[j]); 227 } 228 229 // calculate the CRC-32 of the block 230 u_int32_t new_crc = CalculateCRC(sha1_ctx.h.b8, sizeof (Block)); 231 232 // make sure we don't repeat 233 int cmp = new_crc == pp->LastBlockChecksum; 234 pp->LastBlockChecksum = new_crc; 235 if (!pp->SelfTestInitialized) 236 { 237 pp->SelfTestInitialized = 1; 238 return; 239 } 240 else if (!cmp) 241 { 242 return; 243 } 244 245 repeatCount += 1; 246 247 // fix up the next value of xkey 248 add_blocks (pp->xkey, b, 1); 249 } while (repeatCount < 2); 250 251 /* 252 * If we got here, three sucessive checksums of the random number 253 * generator have been the same. Since the odds of this happening are 254 * 1 in 18,446,744,073,709,551,616, (1 in 18 quintillion) one of the following has 255 * most likely happened: 256 * 257 * 1: There is a significant bug in this code. 258 * 2: There has been a massive system failure. 259 * 3: The universe has ceased to exist. 260 * 261 * There is no good way to recover from any of these cases. We 262 * therefore panic. 263 */ 264 265 panic("FIPS random self-test failed."); 266} 267 268const Block kKnownAnswer = {0x92, 0xb4, 0x04, 0xe5, 0x56, 0x58, 0x8c, 0xed, 0x6c, 0x1a, 0xcd, 0x4e, 0xbf, 0x05, 0x3f, 0x68, 0x09, 0xf7, 0x3a, 0x93}; 269 270void 271fips_initialize(YarrowContextp yp) 272{ 273 /* So that we can do the self test, set the seed to zero */ 274 memset(&yp->xkey, 0, sizeof(yp->xkey)); 275 276 /* other initializations */ 277 memset (zeros, 0, sizeof (zeros)); 278 yp->bytes_used = 0; 279 random_block(yp, yp->random_data, FALSE); 280 281 // check here to see if we got the initial data we were expecting 282 if (memcmp(kKnownAnswer, yp->random_data, kBlockSize) != 0) 283 { 284 panic("FIPS random self test failed"); 285 } 286 287 // now do the random block again to make sure that userland doesn't get predicatable data 288 random_block(yp, yp->random_data, TRUE); 289} 290 291 292static int 293yarrow_init( 294 const struct ccdrbg_info *info, 295 struct ccdrbg_state *drbg, 296 unsigned long entropyLength, const void* entropy, 297 unsigned long nonceLength, const void* nonce, 298 unsigned long psLength, const void* ps) 299{ 300#pragma unused(info) 301#pragma unused(nonceLength) 302#pragma unused(nonce) 303#pragma unused(psLength) 304#pragma unused(ps) 305 YarrowContextp yp = (YarrowContextp) drbg; 306 prng_error_status perr; 307 char buffer[16]; 308 309 yp->SelfTestInitialized = 0; 310 311 /* create a Yarrow object */ 312 perr = prngInitialize(&yp->PrngRef); 313 if (perr != 0) { 314 panic("Couldn't initialize Yarrow, /dev/random will not work."); 315 } 316 317 perr = prngInput(yp->PrngRef, (BYTE*) entropy, (UINT) entropyLength, 318 SYSTEM_SOURCE, (UINT) entropyLength * 8); 319 if (perr != 0) { 320 /* an error, complain */ 321 panic("Couldn't seed Yarrow.\n"); 322 } 323 324 /* turn the data around */ 325 perr = prngOutput(yp->PrngRef, (BYTE*) buffer, (UINT) sizeof(buffer)); 326 327 /* and scramble it some more */ 328 perr = prngForceReseed(yp->PrngRef, RESEED_TICKS); 329 330 fips_initialize(yp); 331 332 yp->bytes_since_reseed = 0; 333 334 return perr; 335} 336 337static int 338yarrow_generate( 339 struct ccdrbg_state *prng, 340 unsigned long outlen, void *out, 341 unsigned long inlen, const void *in) 342{ 343#pragma unused(inlen) 344#pragma unused(in) 345 YarrowContextp yp = (YarrowContextp) prng; 346 int bytes_read = 0; 347 int bytes_remaining = (int) outlen; 348 349 yp->bytes_since_reseed += outlen; 350 if (yp->bytes_since_reseed > RESEED_BYTES) 351 return CCDRBG_STATUS_NEED_RESEED; 352 353 while (bytes_remaining > 0) { 354 int bytes_to_read = MIN(bytes_remaining, 355 kBlockSize - yp->bytes_used); 356 if (bytes_to_read == 0) { 357 random_block(yp, yp->random_data, TRUE); 358 yp->bytes_used = 0; 359 bytes_to_read = MIN(bytes_remaining, kBlockSize); 360 } 361 362 memmove((u_int8_t*) out + bytes_read, 363 ((u_int8_t*)yp->random_data) + yp->bytes_used, 364 bytes_to_read); 365 yp->bytes_used += bytes_to_read; 366 bytes_read += bytes_to_read; 367 bytes_remaining -= bytes_to_read; 368 } 369 370 return CCDRBG_STATUS_OK; 371} 372 373static int 374yarrow_reseed( 375 struct ccdrbg_state *prng, 376 unsigned long entropylen, const void *entropy, 377 unsigned long inlen, const void *in) 378{ 379#pragma unused(inlen) 380#pragma unused(in) 381 YarrowContextp yp = (YarrowContextp) prng; 382 383 (void) prngInput(yp->PrngRef, (BYTE*) entropy, (UINT) entropylen, 384 SYSTEM_SOURCE, (UINT) entropylen * 8); 385 (void) prngForceReseed(yp->PrngRef, RESEED_TICKS); 386 387 yp->bytes_since_reseed = 0; 388 389 return CCDRBG_STATUS_OK; 390} 391 392static void 393yarrow_destroy( 394 struct ccdrbg_state *prng) 395{ 396#pragma unused(prng) 397} 398 399 400void 401ccdrbg_factory_yarrow( 402 struct ccdrbg_info *info, 403 const void *custom) 404{ 405 info->size = sizeof(struct YarrowContext); 406 info->init = yarrow_init; 407 info->generate = yarrow_generate; 408 info->reseed = yarrow_reseed; 409 info->done = yarrow_destroy; 410 info->custom = custom; 411} 412