This adds an stoeplitz_random_seed() function that generates a random
Toeplitz key seed with an invertible matrix T. This is necessary and
sufficient for the hash to spread out over all 65536 possible values.
While it is clear from T * (-1) == 0 that seeds with parity 0 are bad,
I don't have a neat and clean proof for the fact that a seed with
parity 1 always generates an invertible Toeplitz matrix. It's not hard
to check, but rather tedious.
I'm unsure how to hook it up. I enabled random seeds by using the
function in stoeplitz_init(), but that's just for illustration.
Index: sys/net/toeplitz.c
===================================================================
RCS file: /var/cvs/src/sys/net/toeplitz.c,v
retrieving revision 1.7
diff -u -p -r1.7 toeplitz.c
--- sys/net/toeplitz.c 19 Jun 2020 08:48:15 -0000 1.7
+++ sys/net/toeplitz.c 25 Jun 2020 18:43:02 -0000
@@ -69,9 +69,38 @@ static struct stoeplitz_cache stoeplitz_
const struct stoeplitz_cache *const
stoeplitz_cache = &stoeplitz_syskey_cache;
+/* parity of n16: count (mod 2) of ones in the binary representation. */
+int
+parity(uint16_t n16)
+{
+ n16 = ((n16 & 0xaaaa) >> 1) ^ (n16 & 0x5555);
+ n16 = ((n16 & 0xcccc) >> 2) ^ (n16 & 0x3333);
+ n16 = ((n16 & 0xf0f0) >> 4) ^ (n16 & 0x0f0f);
+ n16 = ((n16 & 0xff00) >> 8) ^ (n16 & 0x00ff);
+
+ return (n16);
+}
+
+/*
+ * The Toeplitz matrix obtained from a seed is invertible if and only if the
+ * parity of the seed is 1. Generate such a seed uniformly at random.
+ */
+stoeplitz_key
+stoeplitz_random_seed(void)
+{
+ stoeplitz_key seed;
+
+ seed = arc4random() & UINT16_MAX;
+ if (parity(seed) == 0)
+ seed ^= 1;
+
+ return (seed);
+}
+
void
stoeplitz_init(void)
{
+ stoeplitz_keyseed = stoeplitz_random_seed();
stoeplitz_cache_init(&stoeplitz_syskey_cache, stoeplitz_keyseed);
}
