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