1/* $OpenBSD: toeplitz.c,v 1.10 2021/02/21 02:37:38 dlg Exp $ */
2
3/*
4 * Copyright (c) 2009 The DragonFly Project.  All rights reserved.
5 *
6 * This code is derived from software contributed to The DragonFly Project
7 * by Sepherosa Ziehau <sepherosa@gmail.com>
8 *
9 * Redistribution and use in source and binary forms, with or without
10 * modification, are permitted provided that the following conditions
11 * are met:
12 *
13 * 1. Redistributions of source code must retain the above copyright
14 *    notice, this list of conditions and the following disclaimer.
15 * 2. Redistributions in binary form must reproduce the above copyright
16 *    notice, this list of conditions and the following disclaimer in
17 *    the documentation and/or other materials provided with the
18 *    distribution.
19 * 3. Neither the name of The DragonFly Project nor the names of its
20 *    contributors may be used to endorse or promote products derived
21 *    from this software without specific, prior written permission.
22 *
23 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
24 * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
25 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
26 * FOR A PARTICULAR PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE
27 * COPYRIGHT HOLDERS OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
28 * INCIDENTAL, SPECIAL, EXEMPLARY OR CONSEQUENTIAL DAMAGES (INCLUDING,
29 * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
30 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED
31 * AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
32 * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
33 * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
34 * SUCH DAMAGE.
35 */
36
37/*
38 * Copyright (c) 2019 David Gwynne <dlg@openbsd.org>
39 * Copyright (c) 2020 Theo Buehler <tb@openbsd.org>
40 *
41 * Permission to use, copy, modify, and distribute this software for any
42 * purpose with or without fee is hereby granted, provided that the above
43 * copyright notice and this permission notice appear in all copies.
44 *
45 * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
46 * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
47 * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
48 * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
49 * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
50 * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
51 * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
52 */
53
54#include <sys/param.h>
55#include <sys/systm.h>
56#include <sys/kernel.h>
57#include <sys/sysctl.h>
58
59#include <netinet/in.h>
60
61#include <net/toeplitz.h>
62
63/*
64 * symmetric toeplitz
65 */
66
67static stoeplitz_key		stoeplitz_keyseed = STOEPLITZ_KEYSEED;
68static struct stoeplitz_cache	stoeplitz_syskey_cache;
69const struct stoeplitz_cache *const
70				stoeplitz_cache = &stoeplitz_syskey_cache;
71
72/* parity of n16: count (mod 2) of ones in the binary representation. */
73int
74parity(uint16_t n16)
75{
76	n16 = ((n16 & 0xaaaa) >> 1) ^ (n16 & 0x5555);
77	n16 = ((n16 & 0xcccc) >> 2) ^ (n16 & 0x3333);
78	n16 = ((n16 & 0xf0f0) >> 4) ^ (n16 & 0x0f0f);
79	n16 = ((n16 & 0xff00) >> 8) ^ (n16 & 0x00ff);
80
81	return (n16);
82}
83
84/*
85 * The Toeplitz matrix obtained from a seed is invertible if and only if the
86 * parity of the seed is 1. Generate such a seed uniformly at random.
87 */
88stoeplitz_key
89stoeplitz_random_seed(void)
90{
91	stoeplitz_key seed;
92
93	seed = arc4random() & UINT16_MAX;
94	if (parity(seed) == 0)
95		seed ^= 1;
96
97	return (seed);
98}
99
100void
101stoeplitz_init(void)
102{
103	stoeplitz_keyseed = stoeplitz_random_seed();
104	stoeplitz_cache_init(&stoeplitz_syskey_cache, stoeplitz_keyseed);
105}
106
107#define NBSK (NBBY * sizeof(stoeplitz_key))
108
109/*
110 * The Toeplitz hash of a 16-bit number considered as a column vector over
111 * the field with two elements is calculated as a matrix multiplication with
112 * a 16x16 circulant Toeplitz matrix T generated by skey.
113 *
114 * The first eight columns H of T generate the remaining eight columns using
115 * the byteswap operation J = swap16:  T = [H JH].  Thus, the Toeplitz hash of
116 * n = [hi lo] is computed via the formula T * n = (H * hi) ^ swap16(H * lo).
117 *
118 * Therefore the results H * val for all values of a byte are cached in scache.
119 */
120void
121stoeplitz_cache_init(struct stoeplitz_cache *scache, stoeplitz_key skey)
122{
123	uint16_t column[NBBY];
124	unsigned int b, shift, val;
125
126	bzero(column, sizeof(column));
127
128	/* Calculate the first eight columns H of the Toeplitz matrix T. */
129	for (b = 0; b < NBBY; ++b)
130		column[b] = skey << b | skey >> (NBSK - b);
131
132	/* Cache the results of H * val for all possible values of a byte. */
133	for (val = 0; val < 256; ++val) {
134		uint16_t res = 0;
135
136		for (b = 0; b < NBBY; ++b) {
137			shift = NBBY - b - 1;
138			if (val & (1 << shift))
139				res ^= column[b];
140		}
141		scache->bytes[val] = res;
142	}
143}
144
145uint16_t
146stoeplitz_hash_ip4(const struct stoeplitz_cache *scache,
147    in_addr_t faddr, in_addr_t laddr)
148{
149	return (stoeplitz_hash_n32(scache, faddr ^ laddr));
150}
151
152uint16_t
153stoeplitz_hash_ip4port(const struct stoeplitz_cache *scache,
154    in_addr_t faddr, in_addr_t laddr, in_port_t fport, in_port_t lport)
155{
156	return (stoeplitz_hash_n32(scache, faddr ^ laddr ^ fport ^ lport));
157}
158
159#ifdef INET6
160uint16_t
161stoeplitz_hash_ip6(const struct stoeplitz_cache *scache,
162    const struct in6_addr *faddr6, const struct in6_addr *laddr6)
163{
164	uint32_t n32 = 0;
165	size_t i;
166
167	for (i = 0; i < nitems(faddr6->s6_addr32); i++)
168		n32 ^= faddr6->s6_addr32[i] ^ laddr6->s6_addr32[i];
169
170	return (stoeplitz_hash_n32(scache, n32));
171}
172
173uint16_t
174stoeplitz_hash_ip6port(const struct stoeplitz_cache *scache,
175    const struct in6_addr *faddr6, const struct in6_addr *laddr6,
176    in_port_t fport, in_port_t lport)
177{
178	uint32_t n32 = 0;
179	size_t i;
180
181	for (i = 0; i < nitems(faddr6->s6_addr32); i++)
182		n32 ^= faddr6->s6_addr32[i] ^ laddr6->s6_addr32[i];
183
184	n32 ^= fport ^ lport;
185
186	return (stoeplitz_hash_n32(scache, n32));
187}
188#endif /* INET6 */
189
190uint16_t
191stoeplitz_hash_eaddr(const struct stoeplitz_cache *scache,
192    const uint8_t ea[static 6])
193{
194	const uint16_t *ea16 = (const uint16_t *)ea;
195
196	return (stoeplitz_hash_n16(scache, ea16[0] ^ ea16[1] ^ ea16[2]));
197}
198
199void
200stoeplitz_to_key(void *key, size_t klen)
201{
202	uint8_t *k = key;
203	uint16_t skey = htons(stoeplitz_keyseed);
204	size_t i;
205
206	KASSERT((klen % 2) == 0);
207
208	for (i = 0; i < klen; i += sizeof(skey)) {
209		k[i + 0] = skey >> 8;
210		k[i + 1] = skey;
211	}
212}
213