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