1 /* $OpenBSD: toeplitz.c,v 1.9 2020/09/01 19:18:26 tb 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 /*-
55 * Copyright (c) 2019 Ryo Shimizu
56 * All rights reserved.
57 *
58 * Redistribution and use in source and binary forms, with or without
59 * modification, are permitted provided that the following conditions
60 * are met:
61 * 1. Redistributions of source code must retain the above copyright
62 * notice, this list of conditions and the following disclaimer.
63 * 2. Redistributions in binary form must reproduce the above copyright
64 * notice, this list of conditions and the following disclaimer in the
65 * documentation and/or other materials provided with the distribution.
66 *
67 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS
68 * OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
69 * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
70 * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT,
71 * INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
72 * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
73 * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
74 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
75 * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING
76 * IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
77 * POSSIBILITY OF SUCH DAMAGE.
78 */
79
80 #include <sys/param.h>
81 #include <sys/systm.h>
82 #include <sys/kernel.h>
83 #include <sys/sysctl.h>
84 #include <sys/cprng.h>
85
86 #include <netinet/in.h>
87
88 #include <net/toeplitz.h>
89
90 /*
91 * symmetric toeplitz
92 */
93
94 static stoeplitz_key stoeplitz_keyseed = STOEPLITZ_KEYSEED;
95 static struct stoeplitz_cache stoeplitz_syskey_cache;
96 const struct stoeplitz_cache *const
97 stoeplitz_cache = &stoeplitz_syskey_cache;
98
99 /* parity of n16: count (mod 2) of ones in the binary representation. */
100 static int
parity(uint16_t n16)101 parity(uint16_t n16)
102 {
103 n16 = ((n16 & 0xaaaa) >> 1) ^ (n16 & 0x5555);
104 n16 = ((n16 & 0xcccc) >> 2) ^ (n16 & 0x3333);
105 n16 = ((n16 & 0xf0f0) >> 4) ^ (n16 & 0x0f0f);
106 n16 = ((n16 & 0xff00) >> 8) ^ (n16 & 0x00ff);
107
108 return (n16);
109 }
110
111 /*
112 * The Toeplitz matrix obtained from a seed is invertible if and only if the
113 * parity of the seed is 1. Generate such a seed uniformly at random.
114 */
115 static stoeplitz_key
stoeplitz_random_seed(void)116 stoeplitz_random_seed(void)
117 {
118 stoeplitz_key seed;
119
120 seed = cprng_strong32() & UINT16_MAX;
121 if (parity(seed) == 0)
122 seed ^= 1;
123
124 return (seed);
125 }
126
127 void
stoeplitz_init(void)128 stoeplitz_init(void)
129 {
130 stoeplitz_keyseed = stoeplitz_random_seed();
131 stoeplitz_cache_init(&stoeplitz_syskey_cache, stoeplitz_keyseed);
132 }
133
134 #define NBSK (NBBY * sizeof(stoeplitz_key))
135
136 /*
137 * The Toeplitz hash of a 16-bit number considered as a column vector over
138 * the field with two elements is calculated as a matrix multiplication with
139 * a 16x16 circulant Toeplitz matrix T generated by skey.
140 *
141 * The first eight columns H of T generate the remaining eight columns using
142 * the byteswap operation J = swap16: T = [H JH]. Thus, the Toeplitz hash of
143 * n = [hi lo] is computed via the formula T * n = (H * hi) ^ swap16(H * lo).
144 *
145 * Therefore the results H * val for all values of a byte are cached in scache.
146 */
147 void
stoeplitz_cache_init(struct stoeplitz_cache * scache,stoeplitz_key skey)148 stoeplitz_cache_init(struct stoeplitz_cache *scache, stoeplitz_key skey)
149 {
150 uint16_t column[NBBY];
151 unsigned int b, shift, val;
152
153 bzero(column, sizeof(column));
154
155 /* Calculate the first eight columns H of the Toeplitz matrix T. */
156 for (b = 0; b < NBBY; ++b)
157 column[b] = skey << b | skey >> (NBSK - b);
158
159 /* Cache the results of H * val for all possible values of a byte. */
160 for (val = 0; val < 256; ++val) {
161 uint16_t res = 0;
162
163 for (b = 0; b < NBBY; ++b) {
164 shift = NBBY - b - 1;
165 if (val & (1 << shift))
166 res ^= column[b];
167 }
168 scache->bytes[val] = res;
169 }
170 }
171
172 uint16_t
stoeplitz_hash_ip4(const struct stoeplitz_cache * scache,in_addr_t faddr,in_addr_t laddr)173 stoeplitz_hash_ip4(const struct stoeplitz_cache *scache,
174 in_addr_t faddr, in_addr_t laddr)
175 {
176 return (stoeplitz_hash_n32(scache, faddr ^ laddr));
177 }
178
179 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)180 stoeplitz_hash_ip4port(const struct stoeplitz_cache *scache,
181 in_addr_t faddr, in_addr_t laddr, in_port_t fport, in_port_t lport)
182 {
183 return (stoeplitz_hash_n32(scache, faddr ^ laddr ^ fport ^ lport));
184 }
185
186 #ifdef INET6
187 uint16_t
stoeplitz_hash_ip6(const struct stoeplitz_cache * scache,const struct in6_addr * faddr6,const struct in6_addr * laddr6)188 stoeplitz_hash_ip6(const struct stoeplitz_cache *scache,
189 const struct in6_addr *faddr6, const struct in6_addr *laddr6)
190 {
191 uint32_t n32 = 0;
192 size_t i;
193
194 for (i = 0; i < __arraycount(faddr6->s6_addr32); i++)
195 n32 ^= faddr6->s6_addr32[i] ^ laddr6->s6_addr32[i];
196
197 return (stoeplitz_hash_n32(scache, n32));
198 }
199
200 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)201 stoeplitz_hash_ip6port(const struct stoeplitz_cache *scache,
202 const struct in6_addr *faddr6, const struct in6_addr *laddr6,
203 in_port_t fport, in_port_t lport)
204 {
205 uint32_t n32 = 0;
206 size_t i;
207
208 for (i = 0; i < __arraycount(faddr6->s6_addr32); i++)
209 n32 ^= faddr6->s6_addr32[i] ^ laddr6->s6_addr32[i];
210
211 n32 ^= fport ^ lport;
212
213 return (stoeplitz_hash_n32(scache, n32));
214 }
215 #endif /* INET6 */
216
217 void
stoeplitz_to_key(void * key,size_t klen)218 stoeplitz_to_key(void *key, size_t klen)
219 {
220 uint8_t *k = key;
221 uint16_t skey = htons(stoeplitz_keyseed);
222 size_t i;
223
224 KASSERT((klen % 2) == 0);
225
226 for (i = 0; i < klen; i += sizeof(skey)) {
227 k[i + 0] = skey >> 8;
228 k[i + 1] = skey;
229 }
230 }
231
232 /*
233 * e.g.)
234 *
235 * struct in_addr src, dst;
236 * uint16_t srcport, dstport;
237 * toeplitz_vhash(rsskey[], sizeof(rsskey),
238 * &src, sizeof(src),
239 * &dst, sizeof(dst),
240 * &srcport, sizeof(srcport),
241 * &dstport, sizeof(dstport),
242 * NULL);
243 *
244 * struct in6_addr src6, dst6;
245 * toeplitz_vhash(rsskey[], sizeof(rsskey),
246 * &src6, sizeof(src6),
247 * &dst6, sizeof(dst6),
248 * NULL);
249 *
250 * struct ip *ip;
251 * struct tcphdr *tcp;
252 * toeplitz_vhash(rsskey[], sizeof(rsskey),
253 * &ip->ip_src, sizeof(ip->ip_src),
254 * &ip->ip_dst, sizeof(ip->ip_dst),
255 * &tcp->th_sport, sizeof(tcp->th_sport),
256 * &tcp->th_dport, sizeof(tcp->th_dport),
257 * NULL);
258 *
259 */
260 uint32_t
toeplitz_vhash(const uint8_t * keyp,size_t keylen,...)261 toeplitz_vhash(const uint8_t *keyp, size_t keylen, ...)
262 {
263 va_list ap;
264 uint32_t hash, v;
265 size_t datalen;
266 uint8_t *datap, key, data;
267 const uint8_t *keyend;
268
269 keyend = keyp + keylen;
270
271 /* first 32bit is initial vector */
272 v = *keyp++;
273 v <<= 8;
274 v |= *keyp++;
275 v <<= 8;
276 v |= *keyp++;
277 v <<= 8;
278 v |= *keyp++;
279
280 hash = 0;
281 va_start(ap, keylen);
282
283 while ((datap = va_arg(ap, uint8_t *)) != NULL) {
284 for (datalen = va_arg(ap, size_t); datalen > 0; datalen--) {
285 /* fetch key and input data by 8bit */
286 if (keyp < keyend)
287 key = *keyp++;
288 else
289 key = 0;
290 data = *datap++;
291
292 #define XOR_AND_FETCH_BIT(x) \
293 if (data & __BIT(x)) \
294 hash ^= v; \
295 v <<= 1; \
296 if (key & __BIT(x)) \
297 v |= 1;
298
299 XOR_AND_FETCH_BIT(7);
300 XOR_AND_FETCH_BIT(6);
301 XOR_AND_FETCH_BIT(5);
302 XOR_AND_FETCH_BIT(4);
303 XOR_AND_FETCH_BIT(3);
304 XOR_AND_FETCH_BIT(2);
305 XOR_AND_FETCH_BIT(1);
306 XOR_AND_FETCH_BIT(0);
307
308 #undef XOR_AND_FETCH_BIT
309 }
310 }
311 va_end(ap);
312
313 return hash;
314 }
315