[PATCH 1/4] lib: random: implement Xorshift* RNG

[PATCH 1/4] lib: random: implement Xorshift* RNG

[Ahmad Fatoum]

Xorshift is simpler, faster and better than the LCG we are currently
using. Add it in preparation alongside the LCG until consumers are
migrated.

Signed-off-by: Ahmad Fatoum <a.fatoum@pengutronix.de>
---
 include/stdlib.h | 15 ++++++++
 lib/random.c     | 92 ++++++++++++++++++++++++++++++++++++++++++++++++
 2 files changed, 107 insertions(+)

diff --git a/include/stdlib.h b/include/stdlib.h
index 20bdc0491e3c..12a81cfc31a3 100644
--- a/include/stdlib.h
+++ b/include/stdlib.h
@@ -18,10 +18,25 @@ struct hwrng;
 
 /* fill a buffer with pseudo-random data */
 #if IN_PROPER
+void randbuf_r(u64 *x, void *buf, size_t len);
+void srand_xor(u64 entropy);
+void get_noncrypto_bytes(void *buf, size_t len);
 void get_random_bytes(void *buf, int len);
 int get_crypto_bytes(void *buf, int len);
 int hwrng_get_crypto_bytes(struct hwrng *rng, void *buf, int len);
 #else
+static inline void randbuf_r(u64 *x, void *buf, size_t len)
+{
+	BUG();
+}
+static inline void srand_xor(u64 entropy)
+{
+	BUG();
+}
+static inline void get_noncrypto_bytes(void *buf, size_t len)
+{
+	BUG();
+}
 static inline void get_random_bytes(void *buf, int len)
 {
 	BUG();
diff --git a/lib/random.c b/lib/random.c
index e83935d0e17c..fc4ecdfd3a1d 100644
--- a/lib/random.c
+++ b/lib/random.c
@@ -1,4 +1,15 @@
 // SPDX-License-Identifier: GPL-2.0-only
+/*
+ * The barebox random number generator provides mainly two APIs:
+ *
+ *   - get_noncrypto_bytes: Xorshift*
+ *     - https://en.wikipedia.org/wiki/Xorshift#xorshift*)
+ *     - https://forum.pjrc.com/index.php?threads/teensy-4-1-random-number-generator.61125/#post-243895
+ *
+ *   - get_crypto_bytes: Randomness directly from a HWRNG.
+ *     PRNG fallback only possible with debugging option
+ *     CONFIG_ALLOW_PRNG_FALLBACK set, which will emit a warning at runtime.
+ */
 
 #include <common.h>
 #include <stdlib.h>
@@ -21,6 +32,87 @@ void srand(unsigned int seed)
 	random_seed = seed;
 }
 
+static u64 prng_state = 1;
+
+/**
+ * rand_r - return next pseudo-random number depending only on input
+ *
+ * @x: RNG state
+ *
+ * This function runs the Xorshift* algorithm on the state input,
+ * updates the state and returns the next number in the PRNG
+ * sequence.
+ *
+ * Return: a 32 bit pseudo-random number
+ */
+static u32 rand_r(u64 *x)
+{
+	*x ^= *x >> 12;
+	*x ^= *x << 25;
+	*x ^= *x >> 27;
+
+	/*
+	 * Xorshift* fails only the MatrixRank test of BigCrush, however if the
+	 * generator is modified to return only the high 32 bits, then it passes
+	 * BigCrush with zero failures
+	 */
+	return (*x * 0x2545F4914F6CDD1DULL) >> 32;
+}
+
+/**
+ * randbuf_r - fills pseudo-random numbers into buffer depending only on input
+ *
+ * @x:   RNG state
+ * @buf: buffer to fill
+ * @len: size of buffer
+ *
+ * This function runs the Xorshift* algorithm on the state input,
+ * updates the state and fills the buffer with pseudo-random numbers.
+ *
+ * Only use this when you are using a fixed seed and the sequence
+ * should be reproducible (e.g. for NAND test).
+ */
+void randbuf_r(u64 *x, void *buf, size_t len)
+{
+	for (size_t i = 0; i < len; i += 4) {
+		u32 val = rand_r(x);
+		memcpy(buf + i, &val, min_t(size_t, 4, len - i));
+	}
+}
+
+/**
+ * srand_xor - Xor a 64-bit into the existing RNG state
+ *
+ * @entropy: additional 64-bit of entropy
+ *
+ * This function mixes 64-bit of entropy into the exising
+ * state by means of an Xor operation.
+ *
+ * Only use for independent entropy sources.
+ */
+void srand_xor(u64 entropy)
+{
+	prng_state ^= entropy;
+	/* Ensure prng_state is never zero */
+	prng_state += !prng_state;
+	rand_r(&prng_state);
+}
+
+/**
+ * get_noncrypto_bytes - get pseudo random numbers.
+ *
+ * @buf: buffer to fill
+ * @len: length of buffer
+ *
+ * This interface can be good enough to generate MAC address
+ * or use for NAND test. Use get_crypto_bytes for cryptographic
+ * applications.
+ */
+void get_noncrypto_bytes(void *buf, size_t len)
+{
+	randbuf_r(&prng_state, buf, len);
+}
+
 /**
  * get_random_bytes - get pseudo random numbers.
  * This interface can be good enough to generate MAC address
-- 
2.39.5

[PATCH 2/4] clock: always seed Xorshift* from clocksource on startup

[Ahmad Fatoum]

We currently seed the RNG at following places:

  - ubiformat with get_time_ns()
  - MAC address randomization with get_time_ns()
  - seed and nandtest commands retrieve seed via command line

The latter needs to remain to make tests reproducible, but for general
use, let's collect the initial cycle count at clocksource registration
time and feed that to the PRNG.

Additional entropy can be mixed via the same interface at a later time.

Signed-off-by: Ahmad Fatoum <a.fatoum@pengutronix.de>
---
 common/clock.c | 3 +++
 lib/random.c   | 2 +-
 2 files changed, 4 insertions(+), 1 deletion(-)

diff --git a/common/clock.c b/common/clock.c
index b300e5798a16..8d00edca4651 100644
--- a/common/clock.c
+++ b/common/clock.c
@@ -14,6 +14,7 @@
 #include <linux/math64.h>
 #include <clock.h>
 #include <sched.h>
+#include <stdlib.h>
 
 static uint64_t time_ns;
 
@@ -224,5 +225,7 @@ int init_clock(struct clocksource *cs)
 	cs->cycle_last = cs->read() & cs->mask;
 	current_clock = cs;
 
+	srand_xor(cs->cycle_last);
+
 	return 0;
 }
diff --git a/lib/random.c b/lib/random.c
index fc4ecdfd3a1d..51c68dcd427b 100644
--- a/lib/random.c
+++ b/lib/random.c
@@ -2,7 +2,7 @@
 /*
  * The barebox random number generator provides mainly two APIs:
  *
- *   - get_noncrypto_bytes: Xorshift*
+ *   - get_noncrypto_bytes: Xorshift* seeded initially with the cycle counter
  *     - https://en.wikipedia.org/wiki/Xorshift#xorshift*)
  *     - https://forum.pjrc.com/index.php?threads/teensy-4-1-random-number-generator.61125/#post-243895
  *
-- 
2.39.5

[PATCH 3/4] random: replace all rand/srand API with Xorshift

[Ahmad Fatoum]

Use of the rand/srand API is error prone and trips up static analyzers.
Just drop it and expect users to use random32() instead, which is always
seeded and outputs 32-bit integers directly instead of 16-bit.

Signed-off-by: Ahmad Fatoum <a.fatoum@pengutronix.de>
---
 Documentation/user/random.rst |  8 ++++----
 commands/2048.c               |  4 ++--
 commands/nandtest.c           | 11 +++++------
 commands/seed.c               |  2 +-
 common/boot.c                 |  2 +-
 common/ubiformat.c            |  4 +---
 drivers/net/phy/dp83tg720.c   |  2 +-
 include/net.h                 |  3 +--
 include/stdlib.h              | 22 +++++-----------------
 lib/random.c                  | 29 +++++++----------------------
 10 files changed, 28 insertions(+), 59 deletions(-)

diff --git a/Documentation/user/random.rst b/Documentation/user/random.rst
index 95dad72e55a7..dc3c32ffeb95 100644
--- a/Documentation/user/random.rst
+++ b/Documentation/user/random.rst
@@ -11,8 +11,8 @@ Barebox provides two types of RNG sources - PRNG and HWRNG:
   (which may include truly random values). Although sequences that are closer to
   truly random can be generated using hardware random number generators."
   Pseudorandom number generator. https://en.wikipedia.org/wiki/Pseudorandom_number_generator (2017.05.08).
-  The PRNG used by Barebox is LCG (linear congruential generator) non cryptographically
-  secure, so please use with caution.
+  The PRNG used by Barebox is a Xorshift* and is not seeded in a manner appropriate
+  for cryptographic operations, so please use with caution.
 
 - The HWRNG framework is software that makes use of a special hardware feature on
   your CPU, SoC or motherboard. It can‘t provide any guarantee about cryptographic
@@ -23,8 +23,8 @@ API
 
 .. code-block:: c
 
-        /* seed the PRNG. */
-        void srand(unsigned int seed);
+        /* mix extra entropy into the PRNG state. */
+        void srand_xor(u64 seed);
 
         /* Fill the buffer with PRNG bits. */
         void get_random_bytes(void *buf, int len);
diff --git a/commands/2048.c b/commands/2048.c
index 3ad9c0f3ae37..c8b35bdb7d0a 100644
--- a/commands/2048.c
+++ b/commands/2048.c
@@ -233,10 +233,10 @@ static void addRandom(uint16_t board[SIZE][SIZE])
 	}
 
 	if (len>0) {
-		r = rand()%len;
+		r = random32()%len;
 		x = list[r][0];
 		y = list[r][1];
-		n = ((rand()%10)/9+1)*2;
+		n = ((random32()%10)/9+1)*2;
 		board[x][y]=n;
 	}
 }
diff --git a/commands/nandtest.c b/commands/nandtest.c
index bc138646a460..fa64d9ccea0b 100644
--- a/commands/nandtest.c
+++ b/commands/nandtest.c
@@ -25,7 +25,8 @@ static struct region_info_user memregion;
 static struct mtd_info_user meminfo;
 static struct mtd_ecc_stats oldstats, newstats;
 
-static int fd, seed;
+static int fd;
+static u64 seed;
 /* Markbad option flag */
 static int markbad;
 
@@ -184,7 +185,7 @@ static int erase_and_write(loff_t ofs, unsigned char *data,
 	 * debugging information. */
 	ret = memcmp(data, rbuf, meminfo.erasesize);
 	if (ret < 0) {
-		printf("\ncompare failed. seed %d\n", seed);
+		printf("\ncompare failed. seed %llu\n", seed);
 		for (i = 0; i < meminfo.erasesize; i++) {
 			if (data[i] != rbuf[i])
 				printf("Block 0x%llx byte 0x%0x (page 0x%x offset 0x%x) is %02x should be %02x\n",
@@ -236,7 +237,7 @@ static int do_nandtest(int argc, char *argv[])
 			markbad = 1;
 			break;
 		case 's':
-			seed = simple_strtoul(optarg, NULL, 0);
+			seed = simple_strtoull(optarg, NULL, 0);
 			break;
 		case 'i':
 			nr_iterations = simple_strtoul(optarg, NULL, 0);
@@ -352,8 +353,6 @@ static int do_nandtest(int argc, char *argv[])
 				test_ofs < flash_end;
 				test_ofs += meminfo.erasesize) {
 			pb_update(test_ofs);
-			srand(seed);
-			seed = rand();
 
 			if (ioctl(fd, MEMGETBADBLOCK, &test_ofs)) {
 				printf("\nBad block at 0x%08llx\n",
@@ -364,7 +363,7 @@ static int do_nandtest(int argc, char *argv[])
 			if (do_nandtest_ro) {
 				ret = read_corrected(test_ofs, rbuf, length);
 			} else {
-				get_random_bytes(wbuf, meminfo.erasesize);
+				randbuf_r(&seed, wbuf, meminfo.erasesize);
 				ret = erase_and_write(test_ofs, wbuf,
 						rbuf, length);
 			}
diff --git a/commands/seed.c b/commands/seed.c
index 3947208834ff..3495fab1fd27 100644
--- a/commands/seed.c
+++ b/commands/seed.c
@@ -12,7 +12,7 @@ static int do_seed(int argc, char *argv[])
 		return COMMAND_ERROR_USAGE;
 
 	if (isdigit(*argv[1])) {
-		srand(simple_strtoul(argv[1], NULL, 0));
+		srand_xor(simple_strtoull(argv[1], NULL, 0));
 		return 0;
 	}
 
diff --git a/common/boot.c b/common/boot.c
index 6aa2b1394961..e1844c470888 100644
--- a/common/boot.c
+++ b/common/boot.c
@@ -360,7 +360,7 @@ static char *parse_nfs_url(const char *url)
 		mountpath = xstrdup(prevpath);
 	} else {
 		mountpath = basprintf("/mnt/nfs-%s-bootentries-%08x", host,
-					rand());
+					random32());
 		if (port)
 			options = basprintf("mountport=%s,port=%s", port,
 					      port);
diff --git a/common/ubiformat.c b/common/ubiformat.c
index d8399ad9d6a0..c9256983b501 100644
--- a/common/ubiformat.c
+++ b/common/ubiformat.c
@@ -488,10 +488,8 @@ int ubiformat(struct mtd_info *mtd, struct ubiformat_args *args)
 	if (!args->ubi_ver)
 		args->ubi_ver = 1;
 
-	if (!args->image_seq) {
-		srand(get_time_ns());
+	if (!args->image_seq)
 		args->image_seq = random32();
-	}
 
 	if (!is_power_of_2(mtd->writesize)) {
 		errmsg("min. I/O size is %d, but should be power of 2",
diff --git a/drivers/net/phy/dp83tg720.c b/drivers/net/phy/dp83tg720.c
index a9e5560adc85..0e02f714fea7 100644
--- a/drivers/net/phy/dp83tg720.c
+++ b/drivers/net/phy/dp83tg720.c
@@ -81,7 +81,7 @@ static int dp83tg720_phy_init(struct phy_device *phydev)
 	 * the link partner.  The polling interval is set to 150ms +/- 50ms.
 	 */
 	phydev->polling_interval = (DP83TG720S_POLL_TIMEOUT_MS +
-				    (rand() % 10) * 10) * MSECOND;
+				    prandom_u32_max(100)) * MSECOND;
 
 	/* According to the "DP83TG720R-Q1 1000BASE-T1 Automotive Ethernet PHY
 	 * datasheet (Rev. C)" - "T6.2 Post reset stabilization-time prior to
diff --git a/include/net.h b/include/net.h
index 52f6a0fa97ad..439e0a4c9b61 100644
--- a/include/net.h
+++ b/include/net.h
@@ -423,8 +423,7 @@ int generate_ether_addr(u8 *addr, int ethid);
  */
 static inline void random_ether_addr(u8 *addr)
 {
-	srand(get_time_ns());
-	get_random_bytes(addr, ETH_ALEN);
+	get_noncrypto_bytes(addr, ETH_ALEN);
 	addr[0] &= 0xfe;	/* clear multicast bit */
 	addr[0] |= 0x02;	/* set local assignment bit (IEEE802) */
 }
diff --git a/include/stdlib.h b/include/stdlib.h
index 12a81cfc31a3..36613eb34a99 100644
--- a/include/stdlib.h
+++ b/include/stdlib.h
@@ -6,20 +6,13 @@
 #include <types.h>
 #include <malloc.h>
 
-#define RAND_MAX 32767
-
-/* return a pseudo-random integer in the range [0, RAND_MAX] */
-unsigned int rand(void);
-
-/* set the seed for rand () */
-void srand(unsigned int seed);
-
 struct hwrng;
 
 /* fill a buffer with pseudo-random data */
 #if IN_PROPER
 void randbuf_r(u64 *x, void *buf, size_t len);
 void srand_xor(u64 entropy);
+u32 random32(void);
 void get_noncrypto_bytes(void *buf, size_t len);
 void get_random_bytes(void *buf, int len);
 int get_crypto_bytes(void *buf, int len);
@@ -33,6 +26,10 @@ static inline void srand_xor(u64 entropy)
 {
 	BUG();
 }
+static inline u32 random32(void)
+{
+	BUG();
+}
 static inline void get_noncrypto_bytes(void *buf, size_t len)
 {
 	BUG();
@@ -51,15 +48,6 @@ static inline int hwrng_get_crypto_bytes(struct hwrng *rng, void *buf, int len)
 }
 #endif
 
-static inline u32 random32(void)
-{
-	u32 ret;
-
-	get_random_bytes(&ret, 4);
-
-	return ret;
-}
-
 static inline u32 prandom_u32_max(u32 ep_ro)
 {
 	return (u32)(((u64) random32() * ep_ro) >> 32);
diff --git a/lib/random.c b/lib/random.c
index 51c68dcd427b..36fb1ec08f05 100644
--- a/lib/random.c
+++ b/lib/random.c
@@ -15,23 +15,6 @@
 #include <stdlib.h>
 #include <linux/hw_random.h>
 
-static unsigned int random_seed;
-
-#if RAND_MAX > 32767
-#error this rand implementation is for RAND_MAX < 32678 only.
-#endif
-
-unsigned int rand(void)
-{
-	random_seed = random_seed * 1103515245 + 12345;
-	return (random_seed / 65536) % (RAND_MAX + 1);
-}
-
-void srand(unsigned int seed)
-{
-	random_seed = seed;
-}
-
 static u64 prng_state = 1;
 
 /**
@@ -113,17 +96,19 @@ void get_noncrypto_bytes(void *buf, size_t len)
 	randbuf_r(&prng_state, buf, len);
 }
 
+u32 random32(void)
+{
+	return rand_r(&prng_state);
+}
+
 /**
  * get_random_bytes - get pseudo random numbers.
  * This interface can be good enough to generate MAC address
  * or use for NAND test.
  */
-void get_random_bytes(void *_buf, int len)
+void get_random_bytes(void *buf, int len)
 {
-	char *buf = _buf;
-
-	while (len--)
-		*buf++ = rand() % 256;
+	get_noncrypto_bytes(buf, len);
 }
 
 int hwrng_get_crypto_bytes(struct hwrng *rng, void *buf, int len)
-- 
2.39.5

[PATCH 4/4] random: replace get_random_bytes with get_noncrypto_bytes

[Ahmad Fatoum]

get_random_bytes provides random numbers suitable for crypto on Linux,
but in barebox we do not maintain an entropy pool suitable for that.

Instead we have get_crypto_bytes, which gets randomness out of a HWRNG.
Providing the get_random_bytes API with different semantics than in
Linux is thus a security footgun that we should avoid.

Rename it thus to get_noncrypto_bytes and have get_random_bytes generate
an error to assist porting.

Signed-off-by: Ahmad Fatoum <a.fatoum@pengutronix.de>
---
 Documentation/user/random.rst |  2 +-
 commands/stddev.c             |  2 +-
 drivers/mtd/ubi/attach.c      |  4 ++--
 include/stdlib.h              |  9 ++++-----
 lib/random.c                  | 12 +-----------
 lib/uuid.c                    |  4 ++--
 6 files changed, 11 insertions(+), 22 deletions(-)

diff --git a/Documentation/user/random.rst b/Documentation/user/random.rst
index dc3c32ffeb95..39a0a25e0570 100644
--- a/Documentation/user/random.rst
+++ b/Documentation/user/random.rst
@@ -27,7 +27,7 @@ API
         void srand_xor(u64 seed);
 
         /* Fill the buffer with PRNG bits. */
-        void get_random_bytes(void *buf, int len);
+        void get_noncrypto_bytes(void *buf, int len);
 
         /* Fill the buffer with bits provided by HWRNG.
          * This function may fail with a message “error: no HWRNG available!”
diff --git a/commands/stddev.c b/commands/stddev.c
index e9b7dcc0d2f3..e537bf8dacf6 100644
--- a/commands/stddev.c
+++ b/commands/stddev.c
@@ -87,7 +87,7 @@ device_initcall(null_init);
 
 static ssize_t prng_read(struct cdev *cdev, void *buf, size_t count, loff_t offset, ulong flags)
 {
-	get_random_bytes(buf, count);
+	get_noncrypto_bytes(buf, count);
 	return count;
 }
 
diff --git a/drivers/mtd/ubi/attach.c b/drivers/mtd/ubi/attach.c
index 0e7c61e053fb..44fe435e4163 100644
--- a/drivers/mtd/ubi/attach.c
+++ b/drivers/mtd/ubi/attach.c
@@ -1246,8 +1246,8 @@ static int late_analysis(struct ubi_device *ubi, struct ubi_attach_info *ai)
 		if (ai->maybe_bad_peb_count <= 2) {
 			ai->is_empty = 1;
 			ubi_msg(ubi, "empty MTD device detected");
-			get_random_bytes(&ubi->image_seq,
-					 sizeof(ubi->image_seq));
+			get_noncrypto_bytes(&ubi->image_seq,
+					    sizeof(ubi->image_seq));
 		} else {
 			ubi_err(ubi, "MTD device is not UBI-formatted and possibly contains non-UBI data - refusing it");
 			return -EINVAL;
diff --git a/include/stdlib.h b/include/stdlib.h
index 36613eb34a99..f0f7cfd2ed28 100644
--- a/include/stdlib.h
+++ b/include/stdlib.h
@@ -14,7 +14,6 @@ void randbuf_r(u64 *x, void *buf, size_t len);
 void srand_xor(u64 entropy);
 u32 random32(void);
 void get_noncrypto_bytes(void *buf, size_t len);
-void get_random_bytes(void *buf, int len);
 int get_crypto_bytes(void *buf, int len);
 int hwrng_get_crypto_bytes(struct hwrng *rng, void *buf, int len);
 #else
@@ -34,10 +33,6 @@ static inline void get_noncrypto_bytes(void *buf, size_t len)
 {
 	BUG();
 }
-static inline void get_random_bytes(void *buf, int len)
-{
-	BUG();
-}
 static inline int get_crypto_bytes(void *buf, int len)
 {
 	return -ENOSYS;
@@ -53,4 +48,8 @@ static inline u32 prandom_u32_max(u32 ep_ro)
 	return (u32)(((u64) random32() * ep_ro) >> 32);
 }
 
+extern void __compiletime_error(
+	"Depending on use case, use either get_crypto_bytes or get_noncrypto_bytes."
+) get_random_bytes(void *buf, int len);
+
 #endif /* __STDLIB_H */
diff --git a/lib/random.c b/lib/random.c
index 36fb1ec08f05..889d314e0fad 100644
--- a/lib/random.c
+++ b/lib/random.c
@@ -101,16 +101,6 @@ u32 random32(void)
 	return rand_r(&prng_state);
 }
 
-/**
- * get_random_bytes - get pseudo random numbers.
- * This interface can be good enough to generate MAC address
- * or use for NAND test.
- */
-void get_random_bytes(void *buf, int len)
-{
-	get_noncrypto_bytes(buf, len);
-}
-
 int hwrng_get_crypto_bytes(struct hwrng *rng, void *buf, int len)
 {
 	while (len) {
@@ -151,7 +141,7 @@ int get_crypto_bytes(void *buf, int len)
 
 	pr_warn("falling back to Pseudo RNG source!\n");
 
-	get_random_bytes(buf, len);
+	get_noncrypto_bytes(buf, len);
 
 	return 0;
 }
diff --git a/lib/uuid.c b/lib/uuid.c
index 1c134bfb4b15..96f6f4674c0a 100644
--- a/lib/uuid.c
+++ b/lib/uuid.c
@@ -31,7 +31,7 @@ const u8 uuid_index[16] = {0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15};
  */
 void generate_random_uuid(unsigned char uuid[16])
 {
-	get_random_bytes(uuid, 16);
+	get_noncrypto_bytes(uuid, 16);
 	/* Set UUID version to 4 --- truly random generation */
 	uuid[6] = (uuid[6] & 0x0F) | 0x40;
 	/* Set the UUID variant to DCE */
@@ -41,7 +41,7 @@ EXPORT_SYMBOL(generate_random_uuid);
 
 void generate_random_guid(unsigned char guid[16])
 {
-	get_random_bytes(guid, 16);
+	get_noncrypto_bytes(guid, 16);
 	/* Set GUID version to 4 --- truly random generation */
 	guid[7] = (guid[7] & 0x0F) | 0x40;
 	/* Set the GUID variant to DCE */
-- 
2.39.5