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