[sw/sca] Add Mersenne Twister PRNG library to improve capture rate
This change introduces a Mersenne Twister PRNG that can be used to generate
random plaintexts on the device. Generating random plaintexts on the device
eliminates the overhead of sending them from the host and can significantly
improve capture rate. The host must use the same PRNG to be able to compute
the plaintext and the ciphertext of each trace.
Signed-off-by: Alphan Ulusoy <alphan@google.com>
diff --git a/sw/device/sca/aes_serial/meson.build b/sw/device/sca/aes_serial/meson.build
index 03a0854..3247f6c 100644
--- a/sw/device/sca/aes_serial/meson.build
+++ b/sw/device/sca/aes_serial/meson.build
@@ -19,6 +19,13 @@
),
)
+sw_sca_aes_serial_prng = declare_dependency(
+ link_with: static_library(
+ 'aes_serial_prng',
+ sources: ['prng.c'],
+ ),
+)
+
sw_sca_aes_serial_simple_serial = declare_dependency(
link_with: static_library(
'aes_serial_simple_serial',
@@ -43,6 +50,7 @@
sw_lib_mmio,
sw_lib_runtime_hart,
sw_lib_runtime_log,
+ sw_sca_aes_serial_prng,
sw_sca_aes_serial_sca,
sw_sca_aes_serial_simple_serial,
],
diff --git a/sw/device/sca/aes_serial/prng.c b/sw/device/sca/aes_serial/prng.c
new file mode 100644
index 0000000..cb25e3c
--- /dev/null
+++ b/sw/device/sca/aes_serial/prng.c
@@ -0,0 +1,178 @@
+// Copyright lowRISC contributors.
+// Copyright (C) 1997 - 2002, Makoto Matsumoto and Takuji Nishimura,
+// All rights reserved.
+// SPDX-License-Identifier: BSD-3-Clause
+//
+// Redistribution and use in source and binary forms, with or without
+// modification, are permitted provided that the following conditions
+// are met:
+//
+// 1. Redistributions of source code must retain the above copyright
+// notice, this list of conditions and the following disclaimer.
+//
+// 2. Redistributions in binary form must reproduce the above copyright
+// notice, this list of conditions and the following disclaimer in the
+// documentation and/or other materials provided with the distribution.
+//
+// 3. The names of its contributors may not be used to endorse or promote
+// products derived from this software without specific prior written
+// permission.
+//
+// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
+// "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
+// LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
+// A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER
+// OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
+// EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
+// PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
+// PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
+// LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
+// NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
+// SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+
+#include <stddef.h>
+#include <stdint.h>
+
+/**
+ * Mersenne Twister PRNG modified from:
+ * http://www.math.sci.hiroshima-u.ac.jp/m-mat/MT/MT2002/CODES/mt19937ar.c
+ *
+ * The code below is identical to the code at the link above except for:
+ * - Unused functions were removed,
+ * - `static` specifier was added to all remaining functions,
+ * - Data types were replaced with compatible types for consistency, and
+ * - `clang-format` was run.
+ */
+
+/* Period parameters */
+#define N 624
+#define M 397
+#define MATRIX_A 0x9908b0dfUL /* constant vector a */
+#define UPPER_MASK 0x80000000UL /* most significant w-r bits */
+#define LOWER_MASK 0x7fffffffUL /* least significant r bits */
+
+static uint32_t mt[N]; /* the array for the state vector */
+static int mti = N + 1; /* mti==N+1 means mt[N] is not initialized */
+
+/* initializes mt[N] with a seed */
+static void init_genrand(uint32_t s) {
+ mt[0] = s & 0xffffffffUL;
+ for (mti = 1; mti < N; mti++) {
+ mt[mti] = (1812433253UL * (mt[mti - 1] ^ (mt[mti - 1] >> 30)) + mti);
+ /* See Knuth TAOCP Vol2. 3rd Ed. P.106 for multiplier. */
+ /* In the previous versions, MSBs of the seed affect */
+ /* only MSBs of the array mt[]. */
+ /* 2002/01/09 modified by Makoto Matsumoto */
+ mt[mti] &= 0xffffffffUL;
+ /* for >32 bit machines */
+ }
+}
+
+/* initialize by an array with array-length */
+/* init_key is the array for initializing keys */
+/* key_length is its length */
+/* slight change for C++, 2004/2/26 */
+static void init_by_array(uint32_t init_key[], int32_t key_length) {
+ int32_t i, j, k;
+ init_genrand(19650218UL);
+ i = 1;
+ j = 0;
+ k = (N > key_length ? N : key_length);
+ for (; k; k--) {
+ mt[i] = (mt[i] ^ ((mt[i - 1] ^ (mt[i - 1] >> 30)) * 1664525UL)) +
+ init_key[j] + j; /* non linear */
+ mt[i] &= 0xffffffffUL; /* for WORDSIZE > 32 machines */
+ i++;
+ j++;
+ if (i >= N) {
+ mt[0] = mt[N - 1];
+ i = 1;
+ }
+ if (j >= key_length)
+ j = 0;
+ }
+ for (k = N - 1; k; k--) {
+ mt[i] = (mt[i] ^ ((mt[i - 1] ^ (mt[i - 1] >> 30)) * 1566083941UL)) -
+ i; /* non linear */
+ mt[i] &= 0xffffffffUL; /* for WORDSIZE > 32 machines */
+ i++;
+ if (i >= N) {
+ mt[0] = mt[N - 1];
+ i = 1;
+ }
+ }
+
+ mt[0] = 0x80000000UL; /* MSB is 1; assuring non-zero initial array */
+}
+
+/* generates a random number on [0,0xffffffff]-interval */
+static uint32_t genrand_int32(void) {
+ uint32_t y;
+ static uint32_t mag01[2] = {0x0UL, MATRIX_A};
+ /* mag01[x] = x * MATRIX_A for x=0,1 */
+
+ if (mti >= N) { /* generate N words at one time */
+ int32_t kk;
+
+ if (mti == N + 1) /* if init_genrand() has not been called, */
+ init_genrand(5489UL); /* a default initial seed is used */
+
+ for (kk = 0; kk < N - M; kk++) {
+ y = (mt[kk] & UPPER_MASK) | (mt[kk + 1] & LOWER_MASK);
+ mt[kk] = mt[kk + M] ^ (y >> 1) ^ mag01[y & 0x1UL];
+ }
+ for (; kk < N - 1; kk++) {
+ y = (mt[kk] & UPPER_MASK) | (mt[kk + 1] & LOWER_MASK);
+ mt[kk] = mt[kk + (M - N)] ^ (y >> 1) ^ mag01[y & 0x1UL];
+ }
+ y = (mt[N - 1] & UPPER_MASK) | (mt[0] & LOWER_MASK);
+ mt[N - 1] = mt[M - 1] ^ (y >> 1) ^ mag01[y & 0x1UL];
+
+ mti = 0;
+ }
+
+ y = mt[mti++];
+
+ /* Tempering */
+ y ^= (y >> 11);
+ y ^= (y << 7) & 0x9d2c5680UL;
+ y ^= (y << 15) & 0xefc60000UL;
+ y ^= (y >> 18);
+
+ return y;
+}
+
+/**
+ * End of Mersenne Twister PRNG modified from:
+ * http://www.math.sci.hiroshima-u.ac.jp/m-mat/MT/MT2002/CODES/mt19937ar.c
+ */
+
+/**
+ * TODO(alphan): Using MT for now as a proof of concept to minimize host-side
+ * changes. We should probably replace this with a PRNG from xoshiro* family
+ * for PRNGs, e.g. xoshiro128++, for better performance and less overhead.
+ */
+
+void prng_seed(uint32_t seed) { init_by_array(&seed, 1); }
+
+uint8_t prng_rand_byte(void) {
+ uint32_t rand = 0;
+ do {
+ /**
+ * Note: We shift right by 23 bits instead of 24 to match the behavior of
+ * `random.randint(0, 255)` in python. This, however, is obviously less
+ * efficient since it introduces a random delay for each byte.
+ *
+ * TODO(alphan): Use `random.randbytes()` on the host side instead of
+ * `ktp.next()` and update this function to match.
+ */
+ rand = genrand_int32() >> 23;
+ } while (rand > 255);
+ return rand;
+}
+
+void prng_rand_bytes(uint8_t *buffer, size_t buffer_len) {
+ for (size_t i = 0; i < buffer_len; ++i) {
+ buffer[i] = prng_rand_byte();
+ }
+}
diff --git a/sw/device/sca/aes_serial/prng.h b/sw/device/sca/aes_serial/prng.h
new file mode 100644
index 0000000..10c1b3c
--- /dev/null
+++ b/sw/device/sca/aes_serial/prng.h
@@ -0,0 +1,62 @@
+// Copyright lowRISC contributors.
+// Licensed under the Apache License, Version 2.0, see LICENSE for details.
+// SPDX-License-Identifier: Apache-2.0
+
+#ifndef OPENTITAN_SW_DEVICE_SCA_AES_SERIAL_PRNG_H_
+#define OPENTITAN_SW_DEVICE_SCA_AES_SERIAL_PRNG_H_
+
+#include <stddef.h>
+
+#ifdef __cplusplus
+extern "C" {
+#endif // __cplusplus
+
+/**
+ * @file
+ * @brief PRNG for side-channel analysis.
+ *
+ * This library provides a Mersenne Twister PRNG that can be used to generate
+ * random plaintexts on the device. Generating random plaintexts on the device
+ * eliminates the overhead of sending them from the host and can significantly
+ * improve capture rate. The host must use the same PRNG to be able to compute
+ * the plaintext and the ciphertext of each trace.
+ *
+ * TODO(alphan): Replace this with a more efficient PRNG after updating
+ * host-side code.
+ */
+
+/**
+ * Initializes the random number generator.
+ *
+ * @param seed Seed to initalize with.
+ */
+void prng_seed(uint32_t seed);
+
+/**
+ * Generates a random byte.
+ *
+ * The behavior of this function matches the behavior of `random.randint(0,
+ * 255)` in python, which is used by ChipWhisperer's `ktp.next()`.
+ *
+ * @return A random byte.
+ */
+uint8_t prng_rand_byte(void);
+
+/**
+ * Fills a buffer with random bytes.
+ *
+ * The behavior of this function matches the behavior of `random.randint(0,
+ * 255)` in python, which is used by ChipWhisperer's `ktp.next()`.
+ *
+ * @param[out] buffer A buffer.
+ * @param buffer_len Size of the buffer.
+ *
+ * @return A random byte.
+ */
+void prng_rand_bytes(uint8_t *buffer, size_t buffer_len);
+
+#ifdef __cplusplus
+} // extern "C"
+#endif // __cplusplus
+
+#endif // OPENTITAN_SW_DEVICE_SCA_AES_SERIAL_PRNG_H_
diff --git a/sw/device/tests/meson.build b/sw/device/tests/meson.build
index 24ad867..58d5b19 100644
--- a/sw/device/tests/meson.build
+++ b/sw/device/tests/meson.build
@@ -16,6 +16,7 @@
subdir('dif')
subdir('rom_ext')
subdir('runtime')
+subdir('sca')
subdir('sim_dv')
subdir('otbn')
diff --git a/sw/device/tests/sca/meson.build b/sw/device/tests/sca/meson.build
new file mode 100644
index 0000000..92ee536
--- /dev/null
+++ b/sw/device/tests/sca/meson.build
@@ -0,0 +1,15 @@
+# Copyright lowRISC contributors.
+# Licensed under the Apache License, Version 2.0, see LICENSE for details.
+# SPDX-License-Identifier: Apache-2.0
+
+test('sca_prng_unittest', executable(
+ 'sca_prng_unittest',
+ sources: [
+ meson.source_root() / 'sw/device/sca/aes_serial/prng.c',
+ 'sca_prng_unittest.cc',
+ ],
+ dependencies: [
+ sw_vendor_gtest,
+ ],
+ native: true,
+))
diff --git a/sw/device/tests/sca/sca_prng_unittest.cc b/sw/device/tests/sca/sca_prng_unittest.cc
new file mode 100644
index 0000000..e945f1e
--- /dev/null
+++ b/sw/device/tests/sca/sca_prng_unittest.cc
@@ -0,0 +1,42 @@
+// Copyright lowRISC contributors.
+// Licensed under the Apache License, Version 2.0, see LICENSE for details.
+// SPDX-License-Identifier: Apache-2.0
+
+#include <algorithm>
+#include "gmock/gmock.h"
+#include "gtest/gtest.h"
+#include "sw/device/sca/aes_serial/prng.h"
+
+namespace sca_prng_unittest {
+namespace {
+
+/**
+ * First 100 return values of `random.randint(0, 255)` with a seed value of `0`.
+ */
+constexpr std::array<uint8_t, 100> kExpected = {
+ 197, 215, 20, 132, 248, 207, 155, 244, 183, 111, 71, 144, 71, 48, 128,
+ 75, 158, 50, 37, 169, 241, 51, 181, 222, 161, 104, 244, 226, 133, 31,
+ 7, 47, 204, 0, 252, 170, 124, 166, 32, 97, 113, 122, 72, 229, 46,
+ 41, 163, 250, 55, 154, 149, 63, 170, 104, 147, 227, 46, 197, 162, 123,
+ 148, 94, 96, 95, 16, 133, 243, 35, 45, 66, 76, 19, 41, 200, 141,
+ 120, 110, 214, 140, 230, 252, 182, 42, 166, 59, 249, 171, 97, 124, 8,
+ 138, 59, 112, 190, 87, 170, 218, 31, 51, 74};
+
+TEST(RandByte, Seed_0) {
+ std::vector<uint8_t> actual(kExpected.size());
+
+ prng_seed(0);
+ std::generate(actual.begin(), actual.end(), prng_rand_byte);
+ EXPECT_THAT(actual, testing::ElementsAreArray(kExpected));
+}
+
+TEST(RandBytes, Seed_0) {
+ std::vector<uint8_t> actual(kExpected.size());
+
+ prng_seed(0);
+ prng_rand_bytes(actual.data(), actual.size());
+ EXPECT_THAT(actual, testing::ElementsAreArray(kExpected));
+}
+
+} // namespace
+} // namespace sca_prng_unittest
diff --git a/util/licence-checker.hjson b/util/licence-checker.hjson
index 68f98b9..d2eb07e 100644
--- a/util/licence-checker.hjson
+++ b/util/licence-checker.hjson
@@ -61,9 +61,10 @@
'site/**/assets/scss/**',
'site/landing/static/js/tiny-slider.js',
'util/opentitan-pgm-fpga/vivado_pgm.tcl',
-
# Code taken from Chromium, so covered by the BSD licence
'sw/otbn/code-snippets/modexp.s',
'sw/otbn/code-snippets/p256.s',
+ # Mersenne Twister PRNG
+ 'sw/device/sca/aes_serial/prng.c',
],
}
