1 /* 2 * Copyright (C) Internet Systems Consortium, Inc. ("ISC") 3 * 4 * Permission to use, copy, modify, and/or distribute this software for any 5 * purpose with or without fee is hereby granted, provided that the above 6 * copyright notice and this permission notice appear in all copies. 7 * 8 * THE SOFTWARE IS PROVIDED "AS IS" AND ISC DISCLAIMS ALL WARRANTIES WITH 9 * REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY 10 * AND FITNESS. IN NO EVENT SHALL ISC BE LIABLE FOR ANY SPECIAL, DIRECT, 11 * INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM 12 * LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE 13 * OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR 14 * PERFORMANCE OF THIS SOFTWARE. 15 */ 16 17 /* $Id: hash.c,v 1.6 2020/02/25 05:00:43 jsg Exp $ */ 18 19 /*! \file 20 * Some portion of this code was derived from universal hash function 21 * libraries of Rice University. 22 \section license UH Universal Hashing Library 23 24 Copyright ((c)) 2002, Rice University 25 All rights reserved. 26 27 Redistribution and use in source and binary forms, with or without 28 modification, are permitted provided that the following conditions are 29 met: 30 31 * Redistributions of source code must retain the above copyright 32 notice, this list of conditions and the following disclaimer. 33 34 * Redistributions in binary form must reproduce the above 35 copyright notice, this list of conditions and the following 36 disclaimer in the documentation and/or other materials provided 37 with the distribution. 38 39 * Neither the name of Rice University (RICE) nor the names of its 40 contributors may be used to endorse or promote products derived 41 from this software without specific prior written permission. 42 43 This software is provided by RICE and the contributors on an "as is" 44 basis, without any representations or warranties of any kind, express 45 or implied including, but not limited to, representations or 46 warranties of non-infringement, merchantability or fitness for a 47 particular purpose. In no event shall RICE or contributors be liable 48 for any direct, indirect, incidental, special, exemplary, or 49 consequential damages (including, but not limited to, procurement of 50 substitute goods or services; loss of use, data, or profits; or 51 business interruption) however caused and on any theory of liability, 52 whether in contract, strict liability, or tort (including negligence 53 or otherwise) arising in any way out of the use of this software, even 54 if advised of the possibility of such damage. 55 */ 56 57 #include <stdlib.h> 58 59 #include <isc/hash.h> 60 #include <isc/util.h> 61 62 static unsigned char maptolower[] = { 63 0x00, 0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07, 64 0x08, 0x09, 0x0a, 0x0b, 0x0c, 0x0d, 0x0e, 0x0f, 65 0x10, 0x11, 0x12, 0x13, 0x14, 0x15, 0x16, 0x17, 66 0x18, 0x19, 0x1a, 0x1b, 0x1c, 0x1d, 0x1e, 0x1f, 67 0x20, 0x21, 0x22, 0x23, 0x24, 0x25, 0x26, 0x27, 68 0x28, 0x29, 0x2a, 0x2b, 0x2c, 0x2d, 0x2e, 0x2f, 69 0x30, 0x31, 0x32, 0x33, 0x34, 0x35, 0x36, 0x37, 70 0x38, 0x39, 0x3a, 0x3b, 0x3c, 0x3d, 0x3e, 0x3f, 71 0x40, 0x61, 0x62, 0x63, 0x64, 0x65, 0x66, 0x67, 72 0x68, 0x69, 0x6a, 0x6b, 0x6c, 0x6d, 0x6e, 0x6f, 73 0x70, 0x71, 0x72, 0x73, 0x74, 0x75, 0x76, 0x77, 74 0x78, 0x79, 0x7a, 0x5b, 0x5c, 0x5d, 0x5e, 0x5f, 75 0x60, 0x61, 0x62, 0x63, 0x64, 0x65, 0x66, 0x67, 76 0x68, 0x69, 0x6a, 0x6b, 0x6c, 0x6d, 0x6e, 0x6f, 77 0x70, 0x71, 0x72, 0x73, 0x74, 0x75, 0x76, 0x77, 78 0x78, 0x79, 0x7a, 0x7b, 0x7c, 0x7d, 0x7e, 0x7f, 79 0x80, 0x81, 0x82, 0x83, 0x84, 0x85, 0x86, 0x87, 80 0x88, 0x89, 0x8a, 0x8b, 0x8c, 0x8d, 0x8e, 0x8f, 81 0x90, 0x91, 0x92, 0x93, 0x94, 0x95, 0x96, 0x97, 82 0x98, 0x99, 0x9a, 0x9b, 0x9c, 0x9d, 0x9e, 0x9f, 83 0xa0, 0xa1, 0xa2, 0xa3, 0xa4, 0xa5, 0xa6, 0xa7, 84 0xa8, 0xa9, 0xaa, 0xab, 0xac, 0xad, 0xae, 0xaf, 85 0xb0, 0xb1, 0xb2, 0xb3, 0xb4, 0xb5, 0xb6, 0xb7, 86 0xb8, 0xb9, 0xba, 0xbb, 0xbc, 0xbd, 0xbe, 0xbf, 87 0xc0, 0xc1, 0xc2, 0xc3, 0xc4, 0xc5, 0xc6, 0xc7, 88 0xc8, 0xc9, 0xca, 0xcb, 0xcc, 0xcd, 0xce, 0xcf, 89 0xd0, 0xd1, 0xd2, 0xd3, 0xd4, 0xd5, 0xd6, 0xd7, 90 0xd8, 0xd9, 0xda, 0xdb, 0xdc, 0xdd, 0xde, 0xdf, 91 0xe0, 0xe1, 0xe2, 0xe3, 0xe4, 0xe5, 0xe6, 0xe7, 92 0xe8, 0xe9, 0xea, 0xeb, 0xec, 0xed, 0xee, 0xef, 93 0xf0, 0xf1, 0xf2, 0xf3, 0xf4, 0xf5, 0xf6, 0xf7, 94 0xf8, 0xf9, 0xfa, 0xfb, 0xfc, 0xfd, 0xfe, 0xff 95 }; 96 97 static uint32_t fnv_offset_basis; 98 static isc_boolean_t fnv_once = ISC_FALSE; 99 100 static void 101 fnv_initialize(void) { 102 /* 103 * This function should not leave fnv_offset_basis set to 104 * 0. Also, after this function has been called, if it is called 105 * again, it should not change fnv_offset_basis. 106 */ 107 while (fnv_offset_basis == 0) { 108 fnv_offset_basis = arc4random(); 109 } 110 } 111 112 uint32_t 113 isc_hash_function_reverse(const void *data, size_t length, 114 isc_boolean_t case_sensitive, 115 const uint32_t *previous_hashp) 116 { 117 uint32_t hval; 118 const unsigned char *bp; 119 const unsigned char *be; 120 121 REQUIRE(length == 0 || data != NULL); 122 if (!fnv_once) { 123 fnv_once = ISC_TRUE; 124 fnv_initialize(); 125 } 126 127 hval = previous_hashp != NULL ? 128 *previous_hashp : fnv_offset_basis; 129 130 if (length == 0) 131 return (hval); 132 133 bp = (const unsigned char *) data; 134 be = bp + length; 135 136 /* 137 * Fowler-Noll-Vo FNV-1a hash function. 138 * 139 * NOTE: A random fnv_offset_basis is used by default to avoid 140 * collision attacks as the hash function is reversible. This 141 * makes the mapping non-deterministic, but the distribution in 142 * the domain is still uniform. 143 */ 144 145 if (case_sensitive) { 146 while (be >= bp + 4) { 147 be -= 4; 148 hval ^= (uint32_t) be[3]; 149 hval *= 16777619; 150 hval ^= (uint32_t) be[2]; 151 hval *= 16777619; 152 hval ^= (uint32_t) be[1]; 153 hval *= 16777619; 154 hval ^= (uint32_t) be[0]; 155 hval *= 16777619; 156 } 157 while (--be >= bp) { 158 hval ^= (uint32_t) *be; 159 hval *= 16777619; 160 } 161 } else { 162 while (be >= bp + 4) { 163 be -= 4; 164 hval ^= (uint32_t) maptolower[be[3]]; 165 hval *= 16777619; 166 hval ^= (uint32_t) maptolower[be[2]]; 167 hval *= 16777619; 168 hval ^= (uint32_t) maptolower[be[1]]; 169 hval *= 16777619; 170 hval ^= (uint32_t) maptolower[be[0]]; 171 hval *= 16777619; 172 } 173 while (--be >= bp) { 174 hval ^= (uint32_t) maptolower[*be]; 175 hval *= 16777619; 176 } 177 } 178 179 return (hval); 180 } 181