jcs.org
jcs's openbsd hax
openbsd
1/* $OpenBSD: toeplitz.c,v 1.11 2025/07/07 02:28:50 jsg 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
57#include <netinet/in.h>
58
59#include <net/toeplitz.h>
60
61/*
62 * symmetric toeplitz
63 */
64
65static stoeplitz_key stoeplitz_keyseed = STOEPLITZ_KEYSEED;
66static struct stoeplitz_cache stoeplitz_syskey_cache;
67const struct stoeplitz_cache *const
68 stoeplitz_cache = &stoeplitz_syskey_cache;
69
70/* parity of n16: count (mod 2) of ones in the binary representation. */
71int
72parity(uint16_t n16)
73{
74 n16 = ((n16 & 0xaaaa) >> 1) ^ (n16 & 0x5555);
75 n16 = ((n16 & 0xcccc) >> 2) ^ (n16 & 0x3333);
76 n16 = ((n16 & 0xf0f0) >> 4) ^ (n16 & 0x0f0f);
77 n16 = ((n16 & 0xff00) >> 8) ^ (n16 & 0x00ff);
78
79 return (n16);
80}
81
82/*
83 * The Toeplitz matrix obtained from a seed is invertible if and only if the
84 * parity of the seed is 1. Generate such a seed uniformly at random.
85 */
86stoeplitz_key
87stoeplitz_random_seed(void)
88{
89 stoeplitz_key seed;
90
91 seed = arc4random() & UINT16_MAX;
92 if (parity(seed) == 0)
93 seed ^= 1;
94
95 return (seed);
96}
97
98void
99stoeplitz_init(void)
100{
101 stoeplitz_keyseed = stoeplitz_random_seed();
102 stoeplitz_cache_init(&stoeplitz_syskey_cache, stoeplitz_keyseed);
103}
104
105#define NBSK (NBBY * sizeof(stoeplitz_key))
106
107/*
108 * The Toeplitz hash of a 16-bit number considered as a column vector over
109 * the field with two elements is calculated as a matrix multiplication with
110 * a 16x16 circulant Toeplitz matrix T generated by skey.
111 *
112 * The first eight columns H of T generate the remaining eight columns using
113 * the byteswap operation J = swap16: T = [H JH]. Thus, the Toeplitz hash of
114 * n = [hi lo] is computed via the formula T * n = (H * hi) ^ swap16(H * lo).
115 *
116 * Therefore the results H * val for all values of a byte are cached in scache.
117 */
118void
119stoeplitz_cache_init(struct stoeplitz_cache *scache, stoeplitz_key skey)
120{
121 uint16_t column[NBBY];
122 unsigned int b, shift, val;
123
124 bzero(column, sizeof(column));
125
126 /* Calculate the first eight columns H of the Toeplitz matrix T. */
127 for (b = 0; b < NBBY; ++b)
128 column[b] = skey << b | skey >> (NBSK - b);
129
130 /* Cache the results of H * val for all possible values of a byte. */
131 for (val = 0; val < 256; ++val) {
132 uint16_t res = 0;
133
134 for (b = 0; b < NBBY; ++b) {
135 shift = NBBY - b - 1;
136 if (val & (1 << shift))
137 res ^= column[b];
138 }
139 scache->bytes[val] = res;
140 }
141}
142
143uint16_t
144stoeplitz_hash_ip4(const struct stoeplitz_cache *scache,
145 in_addr_t faddr, in_addr_t laddr)
146{
147 return (stoeplitz_hash_n32(scache, faddr ^ laddr));
148}
149
150uint16_t
151stoeplitz_hash_ip4port(const struct stoeplitz_cache *scache,
152 in_addr_t faddr, in_addr_t laddr, in_port_t fport, in_port_t lport)
153{
154 return (stoeplitz_hash_n32(scache, faddr ^ laddr ^ fport ^ lport));
155}
156
157#ifdef INET6
158uint16_t
159stoeplitz_hash_ip6(const struct stoeplitz_cache *scache,
160 const struct in6_addr *faddr6, const struct in6_addr *laddr6)
161{
162 uint32_t n32 = 0;
163 size_t i;
164
165 for (i = 0; i < nitems(faddr6->s6_addr32); i++)
166 n32 ^= faddr6->s6_addr32[i] ^ laddr6->s6_addr32[i];
167
168 return (stoeplitz_hash_n32(scache, n32));
169}
170
171uint16_t
172stoeplitz_hash_ip6port(const struct stoeplitz_cache *scache,
173 const struct in6_addr *faddr6, const struct in6_addr *laddr6,
174 in_port_t fport, in_port_t lport)
175{
176 uint32_t n32 = 0;
177 size_t i;
178
179 for (i = 0; i < nitems(faddr6->s6_addr32); i++)
180 n32 ^= faddr6->s6_addr32[i] ^ laddr6->s6_addr32[i];
181
182 n32 ^= fport ^ lport;
183
184 return (stoeplitz_hash_n32(scache, n32));
185}
186#endif /* INET6 */
187
188uint16_t
189stoeplitz_hash_eaddr(const struct stoeplitz_cache *scache,
190 const uint8_t ea[static 6])
191{
192 const uint16_t *ea16 = (const uint16_t *)ea;
193
194 return (stoeplitz_hash_n16(scache, ea16[0] ^ ea16[1] ^ ea16[2]));
195}
196
197void
198stoeplitz_to_key(void *key, size_t klen)
199{
200 uint8_t *k = key;
201 uint16_t skey = htons(stoeplitz_keyseed);
202 size_t i;
203
204 KASSERT((klen % 2) == 0);
205
206 for (i = 0; i < klen; i += sizeof(skey)) {
207 k[i + 0] = skey >> 8;
208 k[i + 1] = skey;
209 }
210}