1// Copyright 2016 The Fuchsia Authors 2// 3// Use of this source code is governed by a MIT-style 4// license that can be found in the LICENSE file or at 5// https://opensource.org/licenses/MIT 6 7#include <assert.h> 8#include <string.h> 9 10#include <err.h> 11#include <explicit-memory/bytes.h> 12#include <fbl/atomic.h> 13#include <fbl/auto_call.h> 14#include <fbl/mutex.h> 15#include <kernel/auto_lock.h> 16#include <lib/crypto/prng.h> 17#include <openssl/chacha.h> 18#include <openssl/sha.h> 19#include <pow2.h> 20#include <zircon/compiler.h> 21#include <zircon/types.h> 22 23namespace crypto { 24namespace { 25 26const uint128_t kNonceOverflow = ((uint128_t)1ULL) << 96; 27 28} // namespace 29 30PRNG::PRNG(const void* data, size_t size) 31 : PRNG(data, size, NonThreadSafeTag()) { 32 BecomeThreadSafe(); 33} 34 35PRNG::PRNG(const void* data, size_t size, NonThreadSafeTag tag) 36 : nonce_(0), accumulated_(0) { 37 memset(key_, 0, sizeof(key_)); 38 memset(&ready_, 0, sizeof(ready_)); 39 AddEntropy(data, size); 40} 41 42PRNG::~PRNG() { 43 mandatory_memset(key_, 0, sizeof(key_)); 44 nonce_ = 0; 45} 46 47void PRNG::AddEntropy(const void* data, size_t size) { 48 DEBUG_ASSERT(data || size == 0); 49 ASSERT(size <= kMaxEntropy); 50 // Concurrent calls to |AddEntropy| must run sequentially. 51 fbl::AutoLock guard(&mutex_); 52 // Save the key on the stack, but guarantee we clean them up 53 uint8_t key[sizeof(key_)]; 54 auto cleanup = 55 fbl::MakeAutoCall([&] { mandatory_memset(key, 0, sizeof(key)); }); 56 // We mix all of the entropy with the previous key to make the PRNG state 57 // depend on both the entropy added and the sequence in which it was added. 58 SHA256_CTX ctx; 59 SHA256_Init(&ctx); 60 SHA256_Update(&ctx, data, size); 61 { 62 AutoSpinLock guard(&spinlock_); 63 memcpy(key, key_, sizeof(key)); 64 } 65 SHA256_Update(&ctx, key, sizeof(key)); 66 SHA256_Final(key, &ctx); 67 { 68 AutoSpinLock guard(&spinlock_); 69 memcpy(key_, key, sizeof(key_)); 70 } 71 // Increment how much entropy has been added, and signal if we have enough. 72 if (is_thread_safe() && 73 accumulated_.fetch_add(size) + size >= kMinEntropy) { 74 event_signal(&ready_, true /* reschedule */); 75 } 76} 77 78void PRNG::Draw(void* out, size_t size) { 79 DEBUG_ASSERT(out || size == 0); 80 ASSERT(size <= kMaxDrawLen); 81 // Wait if other threads should add entropy. 82 if (is_thread_safe() && accumulated_.load() < kMinEntropy) { 83 event_wait(&ready_); 84 } 85 // Save these on the stack, but guarantee we clean them up 86 uint8_t key[sizeof(key_)]; 87 uint128_t nonce; 88 auto cleanup = fbl::MakeAutoCall([&] { 89 mandatory_memset(key, 0, sizeof(key)); 90 nonce = 0; 91 }); 92 { 93 AutoSpinLock guard(&spinlock_); 94 nonce = ++nonce_; 95 memcpy(key, key_, sizeof(key)); 96 } 97 ASSERT(nonce < kNonceOverflow); 98 static_assert(__BYTE_ORDER__ == __ORDER_LITTLE_ENDIAN__, "must be LE"); 99 uint8_t* nonce_u8 = reinterpret_cast<uint8_t*>(&nonce); 100 uint8_t* buf = reinterpret_cast<uint8_t*>(out); 101 102 // We randomize |buf| by encrypting it with a key that is never exposed to 103 // the caller, and a 96-bit nonce that changes on each call. We don't zero 104 // |buf| because the encrypted output meets the criteria of the PRNG 105 // regardless of its original contents. We reset the counter to 0 on each 106 // request; it can't overflow because of the limit on the overall size. 107 CRYPTO_chacha_20(buf, buf, size, key, nonce_u8, 0); 108} 109 110uint64_t PRNG::RandInt(uint64_t exclusive_upper_bound) { 111 ASSERT(exclusive_upper_bound != 0); 112 113 const uint log2 = log2_ulong_ceil(exclusive_upper_bound); 114 const size_t mask = (log2 != sizeof(uint64_t) * CHAR_BIT) 115 ? (uint64_t(1) << log2) - 1 116 : UINT64_MAX; 117 DEBUG_ASSERT(exclusive_upper_bound - 1 <= mask); 118 119 // This loop should terminate very fast, since the probability that the 120 // drawn value is >= exclusive_upper_bound is less than 0.5. This is the 121 // classic discard out-of-range values approach. 122 while (true) { 123 uint64_t v; 124 Draw(reinterpret_cast<uint8_t*>(&v), 125 sizeof(uint64_t) / sizeof(uint8_t)); 126 v &= mask; 127 if (v < exclusive_upper_bound) { 128 return v; 129 } 130 } 131} 132 133// It is safe to call this function from PRNG's constructor provided 134// |ready_| and |accumulated_| initialized. 135void PRNG::BecomeThreadSafe() { 136 ASSERT(!event_initialized(&ready_)); 137 event_init(&ready_, accumulated_.load() < kMinEntropy, 0); 138} 139 140bool PRNG::is_thread_safe() const { 141 // Safe to read event.magic; it is read-only in a threaded context 142 return event_initialized(&ready_); 143} 144 145} // namespace crypto 146