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
67 static stoeplitz_key stoeplitz_keyseed = STOEPLITZ_KEYSEED;
68 static struct stoeplitz_cache stoeplitz_syskey_cache;
69 const struct stoeplitz_cache *const
70 stoeplitz_cache = &stoeplitz_syskey_cache;
71
72 /* parity of n16: count (mod 2) of ones in the binary representation. */
73 int
parity(uint16_t n16)74 parity(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 */
88 stoeplitz_key
stoeplitz_random_seed(void)89 stoeplitz_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
100 void
stoeplitz_init(void)101 stoeplitz_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 */
120 void
stoeplitz_cache_init(struct stoeplitz_cache * scache,stoeplitz_key skey)121 stoeplitz_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
145 uint16_t
stoeplitz_hash_ip4(const struct stoeplitz_cache * scache,in_addr_t faddr,in_addr_t laddr)146 stoeplitz_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
152 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)153 stoeplitz_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
160 uint16_t
stoeplitz_hash_ip6(const struct stoeplitz_cache * scache,const struct in6_addr * faddr6,const struct in6_addr * laddr6)161 stoeplitz_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
173 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)174 stoeplitz_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
190 uint16_t
stoeplitz_hash_eaddr(const struct stoeplitz_cache * scache,const uint8_t ea[static6])191 stoeplitz_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
199 void
stoeplitz_to_key(void * key,size_t klen)200 stoeplitz_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