random toeplitz seeds

classic Classic list List threaded Threaded
2 messages Options
Reply | Threaded
Open this post in threaded view
|

random toeplitz seeds

Theo Buehler-3
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);
 }
 

Reply | Threaded
Open this post in threaded view
|

Re: random toeplitz seeds

David Gwynne-5
On Fri, Jun 26, 2020 at 07:55:43AM +0200, Theo Buehler wrote:

> 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.

sorry, i didnt see this when you sent it out.

i can't say whether the maths is right or not, but i'm happy to trust
you on it. it's hooked up fine though, so ok by me.

dlg

> 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);
>  }
>  
>