pw_random: Create module

Creates the pw_random module, starting it off with a random number
generator interface and an implementation based on the xorshift*
algorithm.

Change-Id: Ideda3eb9b713c586ce12230b8f572d079435d949
Reviewed-on: https://pigweed-review.googlesource.com/c/pigweed/pigweed/+/15362
Commit-Queue: Armando Montanez <amontanez@google.com>
Reviewed-by: Keir Mierle <keir@google.com>

6 files changed, 444 insertions, 0 deletions

diff --git a/pw_random/BUILD b/pw_random/BUILD
new file mode 100644
index 000000000..d57185002
--- /dev/null
+++ b/pw_random/BUILD
@@ -0,0 +1,41 @@
+# Copyright 2020 The Pigweed Authors
+#
+# Licensed under the Apache License, Version 2.0 (the "License"); you may not
+# use this file except in compliance with the License. You may obtain a copy of
+# the License at
+#
+#     https://www.apache.org/licenses/LICENSE-2.0
+#
+# Unless required by applicable law or agreed to in writing, software
+# distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
+# WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the
+# License for the specific language governing permissions and limitations under
+# the License.
+
+load(
+    "//pw_build:pigweed.bzl",
+    "pw_cc_library",
+    "pw_cc_test",
+)
+
+package(default_visibility = ["//visibility:public"])
+
+licenses(["notice"])  # Apache License 2.0
+
+pw_cc_library(
+    name = "pw_random",
+    hdrs = [
+        "public/pw_random/random.h",
+        "public/pw_random/xor_shift.h",
+    ],
+    includes = ["public"],
+)
+
+pw_cc_test(
+    name = "xor_shift_test",
+    srcs = ["xor_shift_test.cc"],
+    deps = [
+        ":pw_random",
+        "//pw_unit_test",
+    ],
+)
diff --git a/pw_random/BUILD.gn b/pw_random/BUILD.gn
new file mode 100644
index 000000000..d9dc72a67
--- /dev/null
+++ b/pw_random/BUILD.gn
@@ -0,0 +1,49 @@
+# Copyright 2020 The Pigweed Authors
+#
+# Licensed under the Apache License, Version 2.0 (the "License"); you may not
+# use this file except in compliance with the License. You may obtain a copy of
+# the License at
+#
+#     https://www.apache.org/licenses/LICENSE-2.0
+#
+# Unless required by applicable law or agreed to in writing, software
+# distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
+# WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the
+# License for the specific language governing permissions and limitations under
+# the License.
+
+# gn-format disable
+import("//build_overrides/pigweed.gni")
+
+import("$dir_pw_build/target_types.gni")
+import("$dir_pw_docgen/docs.gni")
+import("$dir_pw_unit_test/test.gni")
+config("default_config") {
+  include_dirs = [ "public" ]
+}
+
+pw_source_set("pw_random") {
+  public_configs = [ ":default_config" ]
+  public = [
+    "public/pw_random/random.h",
+    "public/pw_random/xor_shift.h",
+  ]
+  public_deps = [
+    dir_pw_bytes,
+    dir_pw_span,
+    dir_pw_status,
+  ]
+}
+
+pw_test_group("tests") {
+  tests = [ ":xor_shift_star_test" ]
+}
+
+pw_test("xor_shift_star_test") {
+  deps = [ ":pw_random" ]
+  sources = [ "xor_shift_test.cc" ]
+}
+
+pw_doc_group("docs") {
+  sources = [ "docs.rst" ]
+}
diff --git a/pw_random/docs.rst b/pw_random/docs.rst
new file mode 100644
index 000000000..f1455ea9e
--- /dev/null
+++ b/pw_random/docs.rst
@@ -0,0 +1,69 @@
+.. _chapter-pw-random:
+
+.. default-domain:: cpp
+
+.. highlight:: sh
+
+---------
+pw_random
+---------
+Pigweed's ``pw_random`` module provides a generic interface for random number
+generators, as well as some practical embedded-friendly implementations. While
+this module does not provide drivers for hardware random number generators, it
+acts as a user-friendly layer that can be used to abstract away such hardware.
+
+Embedded systems have the propensity to be more deterministic than your typical
+PC. Sometimes this is a good thing. Other times, it's valuable to have some
+random numbers that aren't predictable. In security contexts or areas where
+things must be marked with a unique ID, this is especially important. Depending
+on the project, true hardware random number generation peripherals may or may
+not be available. Even if RNG hardware is present, it might not always be active
+or accessible. ``pw_random`` provides libraries that make these situations
+easier to manage.
+
+Using RandomGenerator
+=====================
+There's two sides to a RandomGenerator; the input, and the output. The outputs
+are relatively straightforward; ``GetInt()`` randomizes the passed integer
+reference, and ``Get()`` dumps random values into a the passed span. The inputs
+are in the form of the ``InjectEntropy*()`` functions. These functions are used
+to "seed" the random generator. In some implementations, this can simply be
+resetting the seed of a PRNG, while in others it might directly populate a
+limited buffer of random data. In all cases, entropy injection is used to
+improve the randomness of calls to ``Get*()``.
+
+It might not be easy to find sources of entropy in a system, but in general a
+few bits of noise from ADCs or other highly variable inputs can be accumulated
+in a RandomGenerator over time to improve randomness. Such an approach might
+not be sufficient for security, but it could help for less strict uses.
+
+Algorithms
+==========
+xorshift*
+---------
+The ``xorshift*`` algorithm is a pseudo-random number generation algorithm. It's
+very simple in principle; the state is represented as an integer that, with each
+generation, performs exclusive OR operations on different left/right bit shifts
+of itself. The "*" refers to a final multiplication that is applied to the
+output value.
+
+Pigweed's implementation augments this with an ability to inject entropy to
+reseed the generator throughout its lifetime. When entropy is injected, the
+results of the generator are no longer completely deterministic based on the
+original seed.
+
+Note that this generator is NOT cryptographically secure.
+
+For more information, see:
+
+ * https://en.wikipedia.org/wiki/Xorshift
+ * https://www.jstatsoft.org/article/view/v008i14
+ * http://vigna.di.unimi.it/ftp/papers/xorshift.pdf
+
+Future Work
+===========
+A simple "entropy pool" implementation could buffer incoming entropy later use
+instead of requiring an application to directly poll the hardware RNG peripheral
+when the random data is needed. This would let a device collect entropy when
+idling, improving the latency of potentially performance-sensitive areas where
+random numbers are needed.
diff --git a/pw_random/public/pw_random/random.h b/pw_random/public/pw_random/random.h
new file mode 100644
index 000000000..c0af33c82
--- /dev/null
+++ b/pw_random/public/pw_random/random.h
@@ -0,0 +1,56 @@
+// Copyright 2020 The Pigweed Authors
+//
+// Licensed under the Apache License, Version 2.0 (the "License"); you may not
+// use this file except in compliance with the License. You may obtain a copy of
+// the License at
+//
+//     https://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
+// WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the
+// License for the specific language governing permissions and limitations under
+// the License.
+#pragma once
+
+#include <cstdint>
+#include <span>
+
+#include "pw_bytes/span.h"
+#include "pw_status/status_with_size.h"
+
+namespace pw::random {
+
+// A random generator uses injected entropy to generate random values. Many of
+// the guarantees for this interface are provided at the level of the
+// implementations. In general:
+//  * DO NOT assume a generator is cryptographically secure.
+//  * DO NOT assume uniformity of generated data.
+//  * DO assume a generator can be exhausted.
+class RandomGenerator {
+ public:
+  virtual ~RandomGenerator() = default;
+
+  template <class T>
+  StatusWithSize GetInt(T& dest) {
+    static_assert(std::is_integral<T>::value,
+                  "Use Get() for non-integral types");
+    return Get({reinterpret_cast<std::byte*>(&dest), sizeof(T)});
+  }
+
+  // Populates the destination buffer with a randomly generated value. Returns:
+  //  OK - Successfully filled the destination buffer with random data.
+  //  RESOURCE_EXHAUSTED - Filled the buffer with the returned number of bytes.
+  //    The returned size is number of complete bytes with random data.
+  virtual StatusWithSize Get(ByteSpan dest) = 0;
+
+  // Injects entropy into the pool. `data` may have up to 32 bits of random
+  // entropy. If the number of bits of entropy is less than 32, entropy is
+  // assumed to be stored in the least significant bits of `data`.
+  virtual void InjectEntropyBits(uint32_t data, uint_fast8_t num_bits) = 0;
+
+  // Injects entropy into the pool.
+  virtual void InjectEntropy(ConstByteSpan data) = 0;
+};
+
+}  // namespace pw::random
diff --git a/pw_random/public/pw_random/xor_shift.h b/pw_random/public/pw_random/xor_shift.h
new file mode 100644
index 000000000..05541655d
--- /dev/null
+++ b/pw_random/public/pw_random/xor_shift.h
@@ -0,0 +1,107 @@
+// Copyright 2020 The Pigweed Authors
+//
+// Licensed under the Apache License, Version 2.0 (the "License"); you may not
+// use this file except in compliance with the License. You may obtain a copy of
+// the License at
+//
+//     https://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
+// WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the
+// License for the specific language governing permissions and limitations under
+// the License.
+#pragma once
+
+#include <cstdint>
+#include <cstring>
+#include <span>
+
+#include "pw_bytes/span.h"
+#include "pw_random/random.h"
+#include "pw_status/status_with_size.h"
+
+namespace pw::random {
+
+// This is the "xorshift*" algorithm which is a bit stronger than plain XOR
+// shift thanks to the nonlinear transformation at the end (multiplication).
+//
+// See: https://en.wikipedia.org/wiki/Xorshift
+//
+// This random generator is NOT cryptographically secure, and incorporates
+// pseudo-random generation to extrapolate any true injected entropy. The
+// distribution is not guaranteed to be uniform.
+class XorShiftStarRng64 : public RandomGenerator {
+ public:
+  XorShiftStarRng64(uint64_t initial_seed) : state_(initial_seed) {}
+
+  // This generator uses entropy-seeded PRNG to never exhaust its random number
+  // pool.
+  StatusWithSize Get(ByteSpan dest) override {
+    const size_t bytes_written = dest.size_bytes();
+    while (!dest.empty()) {
+      uint64_t random = Regenerate();
+      size_t copy_size = std::min(dest.size_bytes(), sizeof(state_));
+      std::memcpy(dest.data(), &random, copy_size);
+      dest = dest.subspan(copy_size);
+    }
+
+    return StatusWithSize(bytes_written);
+  }
+
+  // Entropy is injected by rotating the state by the number of entropy bits
+  // before xoring the entropy with the current state. This ensures seeding
+  // the random value with single bits will progressively fill the state with
+  // more entropy.
+  void InjectEntropyBits(uint32_t data, uint_fast8_t num_bits) override {
+    if (num_bits == 0) {
+      return;
+    } else if (num_bits > 32) {
+      num_bits = 32;
+    }
+
+    // Rotate state.
+    uint64_t untouched_state = state_ >> (kNumStateBits - num_bits);
+    state_ = untouched_state | (state_ << num_bits);
+    // Zero-out all irrelevant bits, then XOR entropy into state.
+    uint32_t mask = (1 << num_bits) - 1;
+    state_ ^= (data & mask);
+  }
+
+  void InjectEntropy(ConstByteSpan data) override {
+    while (!data.empty()) {
+      size_t chunk_size = std::min(data.size_bytes(), sizeof(state_));
+      uint64_t entropy = 0;
+      std::memcpy(&entropy, data.data(), chunk_size);
+      // Rotate state. When chunk_size == sizeof(state_), this does nothing.
+      uint64_t old_state = state_ >> (kNumStateBits - 8 * chunk_size);
+      state_ = old_state | (state_ << (8 * chunk_size));
+      // XOR entropy into state.
+      state_ ^= entropy;
+      data = data.subspan(chunk_size);
+    }
+  }
+
+ private:
+  // Calculate and return the next value based on the "xorshift*" algorithm
+  uint64_t Regenerate() {
+    // State must be nonzero, or the algorithm will get stuck and always return
+    // zero.
+    if (state_ == 0) {
+      state_--;
+    }
+    state_ ^= state_ >> 12;
+    state_ ^= state_ << 25;
+    state_ ^= state_ >> 27;
+    return state_ * kMultConst;
+  }
+  uint64_t state_;
+  static constexpr uint8_t kNumStateBits = sizeof(state_) * 8;
+
+  // For information on why this constant was selected, see:
+  // https://www.jstatsoft.org/article/view/v008i14
+  // http://vigna.di.unimi.it/ftp/papers/xorshift.pdf
+  static constexpr uint64_t kMultConst = 0x2545F4914F6CDD1D;
+};
+
+}  // namespace pw::random
diff --git a/pw_random/xor_shift_test.cc b/pw_random/xor_shift_test.cc
new file mode 100644
index 000000000..660c98148
--- /dev/null
+++ b/pw_random/xor_shift_test.cc
@@ -0,0 +1,122 @@
+// Copyright 2020 The Pigweed Authors
+//
+// Licensed under the Apache License, Version 2.0 (the "License"); you may not
+// use this file except in compliance with the License. You may obtain a copy of
+// the License at
+//
+//     https://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
+// WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the
+// License for the specific language governing permissions and limitations under
+// the License.
+#include "pw_random/xor_shift.h"
+
+#include <cinttypes>
+#include <cstddef>
+#include <cstdint>
+#include <cstdio>
+
+#include "gtest/gtest.h"
+
+namespace pw::random {
+namespace {
+
+constexpr uint64_t seed1 = 5;
+constexpr uint64_t result1[] = {
+    0x423212e85fb37474u,
+    0x96051f25a1aadc74u,
+    0x8ac1f520f5595a79u,
+    0x7587fe57095b7c11u,
+};
+constexpr int result1_count = sizeof(result1) / sizeof(result1[0]);
+
+constexpr uint64_t seed2 = 0x21feabcd5fb37474u;
+constexpr uint64_t result2[] = {
+    0x568ea260a4f3e793u,
+    0x5ea87d669ab04d36u,
+    0x77a8675eec48ae8bu,
+};
+constexpr int result2_count = sizeof(result2) / sizeof(result2[0]);
+
+TEST(XorShiftStarRng64, ValidateSeries1) {
+  XorShiftStarRng64 rng(seed1);
+  for (size_t i = 0; i < result1_count; ++i) {
+    uint64_t val = 0;
+    EXPECT_EQ(rng.GetInt(val).status(), Status::OK);
+    EXPECT_EQ(val, result1[i]);
+  }
+}
+
+TEST(XorShiftStarRng64, ValidateSeries2) {
+  XorShiftStarRng64 rng(seed2);
+  for (size_t i = 0; i < result2_count; ++i) {
+    uint64_t val = 0;
+    EXPECT_EQ(rng.GetInt(val).status(), Status::OK);
+    EXPECT_EQ(val, result2[i]);
+  }
+}
+
+TEST(XorShiftStarRng64, InjectEntropyBits) {
+  XorShiftStarRng64 rng(seed1);
+  uint64_t val = 0;
+  rng.InjectEntropyBits(0x1, 1);
+  EXPECT_EQ(rng.GetInt(val).status(), Status::OK);
+  EXPECT_NE(val, result1[0]);
+}
+
+// Ensure injecting the same entropy integer, but different bit counts causes
+// the randomly generated number to differ.
+TEST(XorShiftStarRng64, EntropyBitCount) {
+  XorShiftStarRng64 rng_1(seed1);
+  uint64_t first_val = 0;
+  rng_1.InjectEntropyBits(0x1, 1);
+  EXPECT_EQ(rng_1.GetInt(first_val).status(), Status::OK);
+
+  // Use the same starting seed.
+  XorShiftStarRng64 rng_2(seed1);
+  uint64_t second_val = 0;
+  // Use a different number of entropy bits.
+  rng_2.InjectEntropyBits(0x1, 2);
+  EXPECT_EQ(rng_2.GetInt(second_val).status(), Status::OK);
+
+  EXPECT_NE(first_val, second_val);
+}
+
+// Ensure injecting the same integer bit-by-bit applies the same transformation
+// as all in one call. This lets applications decide which is more convenient
+// without worrying about algorithmic changes.
+TEST(XorShiftStarRng64, IncrementalEntropy) {
+  XorShiftStarRng64 rng_1(seed1);
+  uint64_t first_val = 0;
+  rng_1.InjectEntropyBits(0x6, 3);
+  EXPECT_EQ(rng_1.GetInt(first_val).status(), Status::OK);
+
+  // Use the same starting seed.
+  XorShiftStarRng64 rng_2(seed1);
+  uint64_t second_val = 0;
+  // Use a different number of injection calls. 6 = 0b110
+  rng_2.InjectEntropyBits(0x1, 1);
+  rng_2.InjectEntropyBits(0x1, 1);
+  rng_2.InjectEntropyBits(0x0, 1);
+  EXPECT_EQ(rng_2.GetInt(second_val).status(), Status::OK);
+
+  EXPECT_EQ(first_val, second_val);
+}
+
+TEST(XorShiftStarRng64, InjectEntropy) {
+  XorShiftStarRng64 rng(seed1);
+  uint64_t val = 0;
+  constexpr std::array<const std::byte, 5> entropy{std::byte(0xaf),
+                                                   std::byte(0x9b),
+                                                   std::byte(0x33),
+                                                   std::byte(0x17),
+                                                   std::byte(0x02)};
+  rng.InjectEntropy(entropy);
+  EXPECT_EQ(rng.GetInt(val).status(), Status::OK);
+  EXPECT_NE(val, result1[0]);
+}
+
+}  // namespace
+}  // namespace pw::random