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