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