Hash.cc

Go to the documentation of this file.

// $Id: Hash.cc,v 1.5 2005/09/07 17:04:18 vern Exp $
//
// Copyright (c) 1995, 1996, 1997, 1998, 1999, 2002
//      The Regents of the University of California.  All rights reserved.
//
// Redistribution and use in source and binary forms, with or without
// modification, are permitted provided that: (1) source code distributions
// retain the above copyright notice and this paragraph in its entirety, (2)
// distributions including binary code include the above copyright notice and
// this paragraph in its entirety in the documentation or other materials
// provided with the distribution, and (3) all advertising materials mentioning
// features or use of this software display the following acknowledgement:
// ``This product includes software developed by the University of California,
// Lawrence Berkeley Laboratory and its contributors.'' Neither the name of
// the University nor the names of its contributors may be used to endorse
// or promote products derived from this software without specific prior
// written permission.
// THIS SOFTWARE IS PROVIDED ``AS IS'' AND WITHOUT ANY EXPRESS OR IMPLIED
// WARRANTIES, INCLUDING, WITHOUT LIMITATION, THE IMPLIED WARRANTIES OF
// MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE.

// The hash function works as follows:
//
// 1) For short data we have a number of universal hash functions:
// UHASH (ax + b (mod p)), H3, Dietzfelbinger and UMAC_NH (UMAC_NH is
// not as strongly universal as the others, but probably enough). All
// these functions require number of random bits linear to the data
// length. And we use them for data no longer than UHASH_KEY_SIZE.
// They are faster than HMAC/MD5 used for longer data, and most hash
// operations are on short data.
//
// 2) As a fall-back, we use HMAC/MD5 (keyed MD5) for data of arbitrary
// length. MD5 is used as a scrambling scheme so that it is difficult
// for the adversary to construct conflicts, though I do not know if
// HMAC/MD5 is provably universal.

#include "config.h"

#include "Hash.h"

// #define USE_UHASH
// #define USE_UMAC_NH
// #define USE_H3
// #define USE_DIETZFELBINGER

int hash_cnt_all = 0, hash_cnt_uhash = 0;

#if defined(USE_UHASH) || defined(USE_UMAC_NH)
uint8 uhash_key[UHASH_KEY_SIZE];
#endif

#ifdef USE_DIETZFELBINGER
#include "TwoWise.h"
const TwoWise* two_wise;
#endif

#ifdef USE_H3
#include "h3.h"
const H3<hash_t, UHASH_KEY_SIZE>* h3;
#endif

void init_hash_function()
        {
        if ( UHASH_KEY_SIZE % 16 != 0 )
                internal_error("uhash key size must be multiply of 16");

        // Both Dietzfelbinger and H3 use random() to generate keys
        // -- is it strong enough?
#ifdef USE_DIETZFELBINGER
        two_wise = new TwoWise((UHASH_KEY_SIZE + 3) >> 2);
#endif

#ifdef USE_H3
        h3 = new H3<hash_t, UHASH_KEY_SIZE>();
#endif

#if defined(USE_UHASH) || defined(USE_UMAC_NH)
        uint32 buf2[5];
        memcpy(buf2, shared_hmac_md5_key, sizeof(shared_hmac_md5_key));

        for ( int i = 0; i < UHASH_KEY_SIZE; i += 16 )
                {
                buf2[4] = i;
                hmac_md5(sizeof(buf2), (const unsigned char*) buf2, uhash_key + i);
                }
#endif
        }

HashKey::HashKey(bro_int_t i)
        {
        key_u.i = i;
        key = (void*) &key_u;
        size = sizeof(i);
        hash = HashBytes(key, size);
        is_our_dynamic = 0;
        }

HashKey::HashKey(bro_uint_t u)
        {
        key_u.i = bro_int_t(u);
        key = (void*) &key_u;
        size = sizeof(u);
        hash = HashBytes(key, size);
        is_our_dynamic = 0;
        }

#ifdef USE_INT64

HashKey::HashKey(uint32 u)
        {
        key_u.u32 = u;
        key = (void*) &key_u;
        size = sizeof(u);
        hash = HashBytes(key, size);
        is_our_dynamic = 0;
        }

#endif // USE_INT64

HashKey::HashKey(const uint32 u[], int n)
        {
        size = n * sizeof(u[0]);
        key = (void*) u;
        hash = HashBytes(key, size);
        is_our_dynamic = 0;
        }

HashKey::HashKey(double d)
        {
        union {
                double d;
                int i[2];
        } u;

        key_u.d = u.d = d;
        key = (void*) &key_u;
        size = sizeof(d);
        hash = HashBytes(key, size);
        is_our_dynamic = 0;
        }

HashKey::HashKey(const void* p)
        {
        key_u.p = p;
        key = (void*) &key_u;
        size = sizeof(p);
        hash = HashBytes(key, size);
        is_our_dynamic = 0;
        }

HashKey::HashKey(const char* s)
        {
        size = strlen(s);       // note - skip final \0
        key = (void*) s;
        hash = HashBytes(key, size);
        is_our_dynamic = 0;
        }

HashKey::HashKey(const BroString* s)
        {
        size = s->Len();
        key = (void*) s->Bytes();
        hash = HashBytes(key, size);
        is_our_dynamic = 0;
        }

HashKey::HashKey(int copy_key, void* arg_key, int arg_size)
        {
        size = arg_size;
        is_our_dynamic = 1;

        if ( copy_key )
                {
                key = (void*) new char[size];
                memcpy(key, arg_key, size);
                }
        else
                key = arg_key;

        hash = HashBytes(key, size);
        }

HashKey::HashKey(const void* arg_key, int arg_size, hash_t arg_hash)
        {
        size = arg_size;
        hash = arg_hash;
        key = CopyKey(arg_key, size);
        is_our_dynamic = 1;
        }

HashKey::HashKey(const void* arg_key, int arg_size, hash_t arg_hash,
                bool /* dont_copy */)
        {
        size = arg_size;
        hash = arg_hash;
        key = const_cast<void*>(arg_key);
        is_our_dynamic = 0;
        }

HashKey::HashKey(const void* bytes, int arg_size)
        {
        size = arg_size;
        key = CopyKey(bytes, size);
        hash = HashBytes(key, size);
        is_our_dynamic = 1;
        }

void* HashKey::TakeKey()
        {
        if ( is_our_dynamic )
                {
                is_our_dynamic = 0;
                return key;
                }
        else
                return CopyKey(key, size);
        }

void* HashKey::CopyKey(const void* k, int s) const
        {
        void* k_copy = (void*) new char[s];
        memcpy(k_copy, k, s);
        return k_copy;
        }

hash_t HashKey::HashBytes(const void* bytes, int size)
        {
#ifdef USE_OLD_BRO_HASH
        // ### Shall we remove this?
        const unsigned char* cp = (const unsigned char*) bytes;
        hash_t h = 0;

        for ( int i = 0; i < size; ++i )
                // Overflow is okay here.
                h = (h >> 31) + (h << 1) + cp[i];

        return h;
#endif /* USE_OLD_BRO_HASH */

        ++hash_cnt_all;

#ifdef USE_H3
        if ( size == 0 ) // H3 doesn't check if size is zero
                return 0;

        if ( size <= UHASH_KEY_SIZE )
                {
                ++hash_cnt_uhash;
                return (*h3)(bytes, size);
                }
#endif /* USE_H3 */

#ifdef USE_DIETZFELBINGER
        if ( size <= UHASH_KEY_SIZE )
                {
                ++hash_cnt_uhash;
                return two_wise->Hash(size, bytes);
                }
#endif /* USE_DIETZFELBINGER */

#ifdef USE_UMAC_NH
        // Use the NH hash function proposed in UMAC.
        // (See http://www.cs.ucdavis.edu/~rogaway/umac/)
        //
        // Essentially, it is computed as:
        // H = (x_0 +_16 k_0) * (x_1 +_16 k_1) +
        //      (x_2 +_16 k_2) * (x_3 +_16 k_3) + ...
        // where {k_i} are keys for universal hashing,
        // {x_i} are data words, and +_16 means plus mod 2^16.
        //
        // This is faster than UHASH because no modulo operation
        // is needed.

        typedef uint16 uhash_word_t;
        typedef uint32 uhash_dword_t;

        if ( (unsigned int) size <= UHASH_KEY_SIZE - sizeof(uhash_word_t) )
                {
                ++hash_cnt_uhash;

                const uhash_word_t* uhash = (const uhash_word_t *) uhash_key;
                const uint8* data = (const uint8 *) bytes;
                uhash_dword_t sum = 0;

                int i, j, k;
                uhash_word_t x, y;
                k = 0;

                for ( i = 0; i + sizeof(uhash_word_t) < size; )
                        {
                        x = 0;

                        for ( j = 0; j < sizeof(uhash_word_t) && i + j < size; ++j )
                                x = (x << 8) | data[i+j];

                        i += j;
                        x += uhash[k++];
                        y = 0;

                        for ( j = 0; j < sizeof(uhash_word_t) && i + j < size; ++j )
                                y = (y << 8) | data[i+j];

                        i += j;
                        y += uhash[k++];

                        sum += ((uhash_dword_t) x) * ((uhash_dword_t) y);
                        }

                x = 0;
                for ( j = 0; j < sizeof(uhash_word_t) && i + j < size; ++j )
                        x = (x << 8) | data[i+j];
                x += uhash[k++];

                y = size + uhash[k++];
                sum += ((uhash_dword_t) x) * ((uhash_dword_t) y);

                return hash_t(sum);
                }
#endif /* USE_UMAC_NH */

#ifdef USE_UHASH
        // Universal hashing by division (ax mod p).
        typedef uint32 uhash_word_t;

        // We do this typedef here rather than in util.h because
        // "long long" is not in fact ANSI C++ (though it *is* ANSI C),
        // so if it turns out to be problematic we can turn it off
        // by not using UHASH.
        typedef unsigned long long uint64;

        typedef uint64 uhash_dword_t;

        if ( (unsigned int) size <= UHASH_KEY_SIZE - sizeof(uhash_word_t) )
                {
                ++hash_cnt_uhash;

                const uhash_word_t* uhash = (const uhash_word_t *) uhash_key;
                static const uhash_dword_t uhash_prime = (uint64) 1 << 32 + 15;

                uhash_dword_t sum =
                        (uhash_dword_t) (size + 1) *
                        ((uhash_dword_t) uhash[0] + 1);

                int i, j, k;
                const uint8* data = (const uint8*) bytes;
                for ( i = 0, k = 1; i < size; i += sizeof(uhash_word_t), ++k )
                        {
                        uhash_dword_t x = 0;
                        for ( j = 0; unsigned(j) < sizeof(uhash_word_t) && i + j < size; ++j )
                                x = (x << 8) | (uhash_dword_t) data[i+j];

                        sum += ((x + 1) * ((uhash_dword_t) uhash[k] + 1)) %
                                uhash_prime;
                        }

                return hash_t((sum % uhash_prime) & 0xffffffff);
                }

#endif /* USE_UHASH */

        // Fall back to HMAC/MD5 for longer data (which is usually rare).
        hash_t digest[16];
        hmac_md5(size, (unsigned char*) bytes, (unsigned char*) digest);
        return digest[0];
        }

---