1135446Strhodes/* 2262706Serwin * Copyright (C) 2004-2007, 2009, 2013, 2014 Internet Systems Consortium, Inc. ("ISC") 3135446Strhodes * Copyright (C) 2003 Internet Software Consortium. 4135446Strhodes * 5193149Sdougb * Permission to use, copy, modify, and/or distribute this software for any 6135446Strhodes * purpose with or without fee is hereby granted, provided that the above 7135446Strhodes * copyright notice and this permission notice appear in all copies. 8135446Strhodes * 9135446Strhodes * THE SOFTWARE IS PROVIDED "AS IS" AND ISC DISCLAIMS ALL WARRANTIES WITH 10135446Strhodes * REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY 11135446Strhodes * AND FITNESS. IN NO EVENT SHALL ISC BE LIABLE FOR ANY SPECIAL, DIRECT, 12135446Strhodes * INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM 13135446Strhodes * LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE 14135446Strhodes * OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR 15135446Strhodes * PERFORMANCE OF THIS SOFTWARE. 16135446Strhodes */ 17135446Strhodes 18234010Sdougb/* $Id: hash.c,v 1.16 2009/09/01 00:22:28 jinmei Exp $ */ 19135446Strhodes 20170222Sdougb/*! \file 21135446Strhodes * Some portion of this code was derived from universal hash function 22193149Sdougb * libraries of Rice University. 23170222Sdougb\section license UH Universal Hashing Library 24135446Strhodes 25135446StrhodesCopyright ((c)) 2002, Rice University 26135446StrhodesAll rights reserved. 27135446Strhodes 28135446StrhodesRedistribution and use in source and binary forms, with or without 29135446Strhodesmodification, are permitted provided that the following conditions are 30135446Strhodesmet: 31135446Strhodes 32135446Strhodes * Redistributions of source code must retain the above copyright 33135446Strhodes notice, this list of conditions and the following disclaimer. 34135446Strhodes 35135446Strhodes * Redistributions in binary form must reproduce the above 36135446Strhodes copyright notice, this list of conditions and the following 37135446Strhodes disclaimer in the documentation and/or other materials provided 38135446Strhodes with the distribution. 39135446Strhodes 40135446Strhodes * Neither the name of Rice University (RICE) nor the names of its 41135446Strhodes contributors may be used to endorse or promote products derived 42135446Strhodes from this software without specific prior written permission. 43135446Strhodes 44135446Strhodes 45135446StrhodesThis software is provided by RICE and the contributors on an "as is" 46135446Strhodesbasis, without any representations or warranties of any kind, express 47135446Strhodesor implied including, but not limited to, representations or 48135446Strhodeswarranties of non-infringement, merchantability or fitness for a 49135446Strhodesparticular purpose. In no event shall RICE or contributors be liable 50135446Strhodesfor any direct, indirect, incidental, special, exemplary, or 51135446Strhodesconsequential damages (including, but not limited to, procurement of 52135446Strhodessubstitute goods or services; loss of use, data, or profits; or 53135446Strhodesbusiness interruption) however caused and on any theory of liability, 54135446Strhodeswhether in contract, strict liability, or tort (including negligence 55135446Strhodesor otherwise) arising in any way out of the use of this software, even 56135446Strhodesif advised of the possibility of such damage. 57135446Strhodes*/ 58135446Strhodes 59135446Strhodes#include <config.h> 60135446Strhodes 61135446Strhodes#include <isc/entropy.h> 62135446Strhodes#include <isc/hash.h> 63135446Strhodes#include <isc/mem.h> 64135446Strhodes#include <isc/magic.h> 65135446Strhodes#include <isc/mutex.h> 66135446Strhodes#include <isc/once.h> 67135446Strhodes#include <isc/random.h> 68135446Strhodes#include <isc/refcount.h> 69135446Strhodes#include <isc/string.h> 70135446Strhodes#include <isc/util.h> 71135446Strhodes 72135446Strhodes#define HASH_MAGIC ISC_MAGIC('H', 'a', 's', 'h') 73135446Strhodes#define VALID_HASH(h) ISC_MAGIC_VALID((h), HASH_MAGIC) 74135446Strhodes 75170222Sdougb/*% 76135446Strhodes * A large 32-bit prime number that specifies the range of the hash output. 77135446Strhodes */ 78135446Strhodes#define PRIME32 0xFFFFFFFB /* 2^32 - 5 */ 79135446Strhodes 80170222Sdougb/*@{*/ 81170222Sdougb/*% 82135446Strhodes * Types of random seed and hash accumulator. Perhaps they can be system 83135446Strhodes * dependent. 84135446Strhodes */ 85135446Strhodestypedef isc_uint32_t hash_accum_t; 86135446Strhodestypedef isc_uint16_t hash_random_t; 87170222Sdougb/*@}*/ 88135446Strhodes 89170222Sdougb/*% isc hash structure */ 90135446Strhodesstruct isc_hash { 91135446Strhodes unsigned int magic; 92135446Strhodes isc_mem_t *mctx; 93135446Strhodes isc_mutex_t lock; 94135446Strhodes isc_boolean_t initialized; 95135446Strhodes isc_refcount_t refcnt; 96170222Sdougb isc_entropy_t *entropy; /*%< entropy source */ 97262706Serwin size_t limit; /*%< upper limit of key length */ 98170222Sdougb size_t vectorlen; /*%< size of the vector below */ 99170222Sdougb hash_random_t *rndvector; /*%< random vector for universal hashing */ 100135446Strhodes}; 101135446Strhodes 102165071Sdougbstatic isc_mutex_t createlock; 103135446Strhodesstatic isc_once_t once = ISC_ONCE_INIT; 104135446Strhodesstatic isc_hash_t *hash = NULL; 105135446Strhodes 106135446Strhodesstatic unsigned char maptolower[] = { 107135446Strhodes 0x00, 0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07, 108135446Strhodes 0x08, 0x09, 0x0a, 0x0b, 0x0c, 0x0d, 0x0e, 0x0f, 109135446Strhodes 0x10, 0x11, 0x12, 0x13, 0x14, 0x15, 0x16, 0x17, 110135446Strhodes 0x18, 0x19, 0x1a, 0x1b, 0x1c, 0x1d, 0x1e, 0x1f, 111135446Strhodes 0x20, 0x21, 0x22, 0x23, 0x24, 0x25, 0x26, 0x27, 112135446Strhodes 0x28, 0x29, 0x2a, 0x2b, 0x2c, 0x2d, 0x2e, 0x2f, 113135446Strhodes 0x30, 0x31, 0x32, 0x33, 0x34, 0x35, 0x36, 0x37, 114135446Strhodes 0x38, 0x39, 0x3a, 0x3b, 0x3c, 0x3d, 0x3e, 0x3f, 115135446Strhodes 0x40, 0x61, 0x62, 0x63, 0x64, 0x65, 0x66, 0x67, 116135446Strhodes 0x68, 0x69, 0x6a, 0x6b, 0x6c, 0x6d, 0x6e, 0x6f, 117135446Strhodes 0x70, 0x71, 0x72, 0x73, 0x74, 0x75, 0x76, 0x77, 118135446Strhodes 0x78, 0x79, 0x7a, 0x5b, 0x5c, 0x5d, 0x5e, 0x5f, 119135446Strhodes 0x60, 0x61, 0x62, 0x63, 0x64, 0x65, 0x66, 0x67, 120135446Strhodes 0x68, 0x69, 0x6a, 0x6b, 0x6c, 0x6d, 0x6e, 0x6f, 121135446Strhodes 0x70, 0x71, 0x72, 0x73, 0x74, 0x75, 0x76, 0x77, 122135446Strhodes 0x78, 0x79, 0x7a, 0x7b, 0x7c, 0x7d, 0x7e, 0x7f, 123135446Strhodes 0x80, 0x81, 0x82, 0x83, 0x84, 0x85, 0x86, 0x87, 124135446Strhodes 0x88, 0x89, 0x8a, 0x8b, 0x8c, 0x8d, 0x8e, 0x8f, 125135446Strhodes 0x90, 0x91, 0x92, 0x93, 0x94, 0x95, 0x96, 0x97, 126135446Strhodes 0x98, 0x99, 0x9a, 0x9b, 0x9c, 0x9d, 0x9e, 0x9f, 127135446Strhodes 0xa0, 0xa1, 0xa2, 0xa3, 0xa4, 0xa5, 0xa6, 0xa7, 128135446Strhodes 0xa8, 0xa9, 0xaa, 0xab, 0xac, 0xad, 0xae, 0xaf, 129135446Strhodes 0xb0, 0xb1, 0xb2, 0xb3, 0xb4, 0xb5, 0xb6, 0xb7, 130135446Strhodes 0xb8, 0xb9, 0xba, 0xbb, 0xbc, 0xbd, 0xbe, 0xbf, 131135446Strhodes 0xc0, 0xc1, 0xc2, 0xc3, 0xc4, 0xc5, 0xc6, 0xc7, 132135446Strhodes 0xc8, 0xc9, 0xca, 0xcb, 0xcc, 0xcd, 0xce, 0xcf, 133135446Strhodes 0xd0, 0xd1, 0xd2, 0xd3, 0xd4, 0xd5, 0xd6, 0xd7, 134135446Strhodes 0xd8, 0xd9, 0xda, 0xdb, 0xdc, 0xdd, 0xde, 0xdf, 135135446Strhodes 0xe0, 0xe1, 0xe2, 0xe3, 0xe4, 0xe5, 0xe6, 0xe7, 136135446Strhodes 0xe8, 0xe9, 0xea, 0xeb, 0xec, 0xed, 0xee, 0xef, 137135446Strhodes 0xf0, 0xf1, 0xf2, 0xf3, 0xf4, 0xf5, 0xf6, 0xf7, 138135446Strhodes 0xf8, 0xf9, 0xfa, 0xfb, 0xfc, 0xfd, 0xfe, 0xff 139135446Strhodes}; 140135446Strhodes 141135446Strhodesisc_result_t 142135446Strhodesisc_hash_ctxcreate(isc_mem_t *mctx, isc_entropy_t *entropy, 143262706Serwin size_t limit, isc_hash_t **hctxp) 144135446Strhodes{ 145170222Sdougb isc_result_t result; 146135446Strhodes isc_hash_t *hctx; 147135446Strhodes size_t vlen; 148135446Strhodes hash_random_t *rv; 149135446Strhodes hash_accum_t overflow_limit; 150135446Strhodes 151135446Strhodes REQUIRE(mctx != NULL); 152135446Strhodes REQUIRE(hctxp != NULL && *hctxp == NULL); 153135446Strhodes 154135446Strhodes /* 155135446Strhodes * Overflow check. Since our implementation only does a modulo 156135446Strhodes * operation at the last stage of hash calculation, the accumulator 157135446Strhodes * must not overflow. 158135446Strhodes */ 159135446Strhodes overflow_limit = 160135446Strhodes 1 << (((sizeof(hash_accum_t) - sizeof(hash_random_t))) * 8); 161135446Strhodes if (overflow_limit < (limit + 1) * 0xff) 162135446Strhodes return (ISC_R_RANGE); 163135446Strhodes 164135446Strhodes hctx = isc_mem_get(mctx, sizeof(isc_hash_t)); 165135446Strhodes if (hctx == NULL) 166135446Strhodes return (ISC_R_NOMEMORY); 167135446Strhodes 168135446Strhodes vlen = sizeof(hash_random_t) * (limit + 1); 169135446Strhodes rv = isc_mem_get(mctx, vlen); 170135446Strhodes if (rv == NULL) { 171170222Sdougb result = ISC_R_NOMEMORY; 172135446Strhodes goto errout; 173135446Strhodes } 174135446Strhodes 175135446Strhodes /* 176135446Strhodes * We need a lock. 177135446Strhodes */ 178170222Sdougb result = isc_mutex_init(&hctx->lock); 179170222Sdougb if (result != ISC_R_SUCCESS) 180135446Strhodes goto errout; 181135446Strhodes 182135446Strhodes /* 183135446Strhodes * From here down, no failures will/can occur. 184135446Strhodes */ 185135446Strhodes hctx->magic = HASH_MAGIC; 186135446Strhodes hctx->mctx = NULL; 187135446Strhodes isc_mem_attach(mctx, &hctx->mctx); 188135446Strhodes hctx->initialized = ISC_FALSE; 189170222Sdougb result = isc_refcount_init(&hctx->refcnt, 1); 190170222Sdougb if (result != ISC_R_SUCCESS) 191170222Sdougb goto cleanup_lock; 192135446Strhodes hctx->entropy = NULL; 193135446Strhodes hctx->limit = limit; 194135446Strhodes hctx->vectorlen = vlen; 195135446Strhodes hctx->rndvector = rv; 196135446Strhodes 197224092Sdougb#ifdef BIND9 198135446Strhodes if (entropy != NULL) 199135446Strhodes isc_entropy_attach(entropy, &hctx->entropy); 200224092Sdougb#else 201224092Sdougb UNUSED(entropy); 202224092Sdougb#endif 203135446Strhodes 204135446Strhodes *hctxp = hctx; 205135446Strhodes return (ISC_R_SUCCESS); 206135446Strhodes 207170222Sdougb cleanup_lock: 208170222Sdougb DESTROYLOCK(&hctx->lock); 209135446Strhodes errout: 210135446Strhodes isc_mem_put(mctx, hctx, sizeof(isc_hash_t)); 211135446Strhodes if (rv != NULL) 212135446Strhodes isc_mem_put(mctx, rv, vlen); 213135446Strhodes 214170222Sdougb return (result); 215135446Strhodes} 216135446Strhodes 217135446Strhodesstatic void 218135446Strhodesinitialize_lock(void) { 219165071Sdougb RUNTIME_CHECK(isc_mutex_init(&createlock) == ISC_R_SUCCESS); 220135446Strhodes} 221135446Strhodes 222135446Strhodesisc_result_t 223135446Strhodesisc_hash_create(isc_mem_t *mctx, isc_entropy_t *entropy, size_t limit) { 224135446Strhodes isc_result_t result = ISC_R_SUCCESS; 225135446Strhodes 226135446Strhodes REQUIRE(mctx != NULL); 227135446Strhodes INSIST(hash == NULL); 228135446Strhodes 229135446Strhodes RUNTIME_CHECK(isc_once_do(&once, initialize_lock) == ISC_R_SUCCESS); 230135446Strhodes 231165071Sdougb LOCK(&createlock); 232135446Strhodes 233135446Strhodes if (hash == NULL) 234135446Strhodes result = isc_hash_ctxcreate(mctx, entropy, limit, &hash); 235135446Strhodes 236165071Sdougb UNLOCK(&createlock); 237135446Strhodes 238135446Strhodes return (result); 239135446Strhodes} 240135446Strhodes 241135446Strhodesvoid 242135446Strhodesisc_hash_ctxinit(isc_hash_t *hctx) { 243135446Strhodes LOCK(&hctx->lock); 244135446Strhodes 245135446Strhodes if (hctx->initialized == ISC_TRUE) 246135446Strhodes goto out; 247135446Strhodes 248135446Strhodes if (hctx->entropy) { 249224092Sdougb#ifdef BIND9 250224092Sdougb isc_result_t result; 251224092Sdougb 252193149Sdougb result = isc_entropy_getdata(hctx->entropy, 253262706Serwin hctx->rndvector, 254262706Serwin (unsigned int)hctx->vectorlen, 255135446Strhodes NULL, 0); 256135446Strhodes INSIST(result == ISC_R_SUCCESS); 257224092Sdougb#else 258224092Sdougb INSIST(0); 259224092Sdougb#endif 260135446Strhodes } else { 261135446Strhodes isc_uint32_t pr; 262262706Serwin size_t i, copylen; 263135446Strhodes unsigned char *p; 264135446Strhodes 265135446Strhodes p = (unsigned char *)hctx->rndvector; 266135446Strhodes for (i = 0; i < hctx->vectorlen; i += copylen, p += copylen) { 267135446Strhodes isc_random_get(&pr); 268135446Strhodes if (i + sizeof(pr) <= hctx->vectorlen) 269135446Strhodes copylen = sizeof(pr); 270135446Strhodes else 271135446Strhodes copylen = hctx->vectorlen - i; 272135446Strhodes 273262706Serwin memmove(p, &pr, copylen); 274135446Strhodes } 275135446Strhodes INSIST(p == (unsigned char *)hctx->rndvector + 276135446Strhodes hctx->vectorlen); 277135446Strhodes } 278135446Strhodes 279135446Strhodes hctx->initialized = ISC_TRUE; 280135446Strhodes 281135446Strhodes out: 282135446Strhodes UNLOCK(&hctx->lock); 283135446Strhodes} 284135446Strhodes 285135446Strhodesvoid 286135446Strhodesisc_hash_init() { 287135446Strhodes INSIST(hash != NULL && VALID_HASH(hash)); 288193149Sdougb 289135446Strhodes isc_hash_ctxinit(hash); 290135446Strhodes} 291135446Strhodes 292135446Strhodesvoid 293135446Strhodesisc_hash_ctxattach(isc_hash_t *hctx, isc_hash_t **hctxp) { 294135446Strhodes REQUIRE(VALID_HASH(hctx)); 295135446Strhodes REQUIRE(hctxp != NULL && *hctxp == NULL); 296135446Strhodes 297135446Strhodes isc_refcount_increment(&hctx->refcnt, NULL); 298135446Strhodes *hctxp = hctx; 299135446Strhodes} 300135446Strhodes 301135446Strhodesstatic void 302135446Strhodesdestroy(isc_hash_t **hctxp) { 303135446Strhodes isc_hash_t *hctx; 304135446Strhodes isc_mem_t *mctx; 305224092Sdougb unsigned char canary0[4], canary1[4]; 306135446Strhodes 307135446Strhodes REQUIRE(hctxp != NULL && *hctxp != NULL); 308135446Strhodes hctx = *hctxp; 309135446Strhodes *hctxp = NULL; 310135446Strhodes 311135446Strhodes LOCK(&hctx->lock); 312135446Strhodes 313135446Strhodes isc_refcount_destroy(&hctx->refcnt); 314135446Strhodes 315135446Strhodes mctx = hctx->mctx; 316224092Sdougb#ifdef BIND9 317135446Strhodes if (hctx->entropy != NULL) 318135446Strhodes isc_entropy_detach(&hctx->entropy); 319224092Sdougb#endif 320135446Strhodes if (hctx->rndvector != NULL) 321135446Strhodes isc_mem_put(mctx, hctx->rndvector, hctx->vectorlen); 322135446Strhodes 323135446Strhodes UNLOCK(&hctx->lock); 324135446Strhodes 325135446Strhodes DESTROYLOCK(&hctx->lock); 326135446Strhodes 327262706Serwin memmove(canary0, hctx + 1, sizeof(canary0)); 328135446Strhodes memset(hctx, 0, sizeof(isc_hash_t)); 329262706Serwin memmove(canary1, hctx + 1, sizeof(canary1)); 330224092Sdougb INSIST(memcmp(canary0, canary1, sizeof(canary0)) == 0); 331135446Strhodes isc_mem_put(mctx, hctx, sizeof(isc_hash_t)); 332135446Strhodes isc_mem_detach(&mctx); 333135446Strhodes} 334135446Strhodes 335135446Strhodesvoid 336135446Strhodesisc_hash_ctxdetach(isc_hash_t **hctxp) { 337135446Strhodes isc_hash_t *hctx; 338135446Strhodes unsigned int refs; 339135446Strhodes 340135446Strhodes REQUIRE(hctxp != NULL && VALID_HASH(*hctxp)); 341135446Strhodes hctx = *hctxp; 342135446Strhodes 343135446Strhodes isc_refcount_decrement(&hctx->refcnt, &refs); 344135446Strhodes if (refs == 0) 345135446Strhodes destroy(&hctx); 346135446Strhodes 347135446Strhodes *hctxp = NULL; 348135446Strhodes} 349135446Strhodes 350135446Strhodesvoid 351135446Strhodesisc_hash_destroy() { 352135446Strhodes unsigned int refs; 353135446Strhodes 354135446Strhodes INSIST(hash != NULL && VALID_HASH(hash)); 355135446Strhodes 356135446Strhodes isc_refcount_decrement(&hash->refcnt, &refs); 357135446Strhodes INSIST(refs == 0); 358135446Strhodes 359135446Strhodes destroy(&hash); 360135446Strhodes} 361135446Strhodes 362135446Strhodesstatic inline unsigned int 363135446Strhodeshash_calc(isc_hash_t *hctx, const unsigned char *key, unsigned int keylen, 364135446Strhodes isc_boolean_t case_sensitive) 365135446Strhodes{ 366135446Strhodes hash_accum_t partial_sum = 0; 367135446Strhodes hash_random_t *p = hctx->rndvector; 368135446Strhodes unsigned int i = 0; 369135446Strhodes 370135446Strhodes /* Make it sure that the hash context is initialized. */ 371135446Strhodes if (hctx->initialized == ISC_FALSE) 372135446Strhodes isc_hash_ctxinit(hctx); 373135446Strhodes 374135446Strhodes if (case_sensitive) { 375135446Strhodes for (i = 0; i < keylen; i++) 376135446Strhodes partial_sum += key[i] * (hash_accum_t)p[i]; 377135446Strhodes } else { 378135446Strhodes for (i = 0; i < keylen; i++) 379135446Strhodes partial_sum += maptolower[key[i]] * (hash_accum_t)p[i]; 380135446Strhodes } 381135446Strhodes 382135446Strhodes partial_sum += p[i]; 383135446Strhodes 384135446Strhodes return ((unsigned int)(partial_sum % PRIME32)); 385135446Strhodes} 386135446Strhodes 387135446Strhodesunsigned int 388135446Strhodesisc_hash_ctxcalc(isc_hash_t *hctx, const unsigned char *key, 389135446Strhodes unsigned int keylen, isc_boolean_t case_sensitive) 390135446Strhodes{ 391135446Strhodes REQUIRE(hctx != NULL && VALID_HASH(hctx)); 392135446Strhodes REQUIRE(keylen <= hctx->limit); 393135446Strhodes 394135446Strhodes return (hash_calc(hctx, key, keylen, case_sensitive)); 395135446Strhodes} 396135446Strhodes 397135446Strhodesunsigned int 398135446Strhodesisc_hash_calc(const unsigned char *key, unsigned int keylen, 399135446Strhodes isc_boolean_t case_sensitive) 400135446Strhodes{ 401135446Strhodes INSIST(hash != NULL && VALID_HASH(hash)); 402135446Strhodes REQUIRE(keylen <= hash->limit); 403135446Strhodes 404135446Strhodes return (hash_calc(hash, key, keylen, case_sensitive)); 405135446Strhodes} 406