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