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>
diff --git a/BUILD.gn b/BUILD.gn
index 86481bc..194db27 100644
--- a/BUILD.gn
+++ b/BUILD.gn
@@ -192,6 +192,7 @@
"$dir_pw_preprocessor:tests",
"$dir_pw_protobuf:tests",
"$dir_pw_protobuf_compiler:tests",
+ "$dir_pw_random:tests",
"$dir_pw_result:tests",
"$dir_pw_ring_buffer:tests",
"$dir_pw_rpc:tests",
diff --git a/docs/BUILD.gn b/docs/BUILD.gn
index ff96e4e..caac883 100644
--- a/docs/BUILD.gn
+++ b/docs/BUILD.gn
@@ -91,6 +91,7 @@
"$dir_pw_presubmit:docs",
"$dir_pw_protobuf:docs",
"$dir_pw_protobuf_compiler:docs",
+ "$dir_pw_random:docs",
"$dir_pw_result:docs",
"$dir_pw_ring_buffer:docs",
"$dir_pw_rpc:docs",
diff --git a/modules.gni b/modules.gni
index 4a4e4dd..915a30d 100644
--- a/modules.gni
+++ b/modules.gni
@@ -51,6 +51,7 @@
dir_pw_presubmit = get_path_info("pw_presubmit", "abspath")
dir_pw_protobuf = get_path_info("pw_protobuf", "abspath")
dir_pw_protobuf_compiler = get_path_info("pw_protobuf_compiler", "abspath")
+ dir_pw_random = get_path_info("pw_random", "abspath")
dir_pw_result = get_path_info("pw_result", "abspath")
dir_pw_ring_buffer = get_path_info("pw_ring_buffer", "abspath")
dir_pw_rpc = get_path_info("pw_rpc", "abspath")
diff --git a/pw_random/BUILD b/pw_random/BUILD
new file mode 100644
index 0000000..d571850
--- /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 0000000..d9dc72a
--- /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 0000000..f1455ea
--- /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 0000000..c0af33c
--- /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 0000000..0554165
--- /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 0000000..660c981
--- /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