Branch data Line data Source code
1 : : // $Id: Hash.cc 6219 2008-10-01 05:39:07Z vern $
2 : : //
3 : : // See the file "COPYING" in the main distribution directory for copyright.
4 : :
5 : : // The hash function works as follows:
6 : : //
7 : : // 1) For short data we have a number of universal hash functions:
8 : : // UHASH_CW (ax + b (mod p)), H3, Dietzfelbinger and UMAC_NH (UMAC_NH is
9 : : // not as strongly universal as the others, but probably enough). All
10 : : // these functions require number of random bits linear to the data
11 : : // length. And we use them for data no longer than UHASH_KEY_SIZE.
12 : : // They are faster than HMAC/MD5 used for longer data, and most hash
13 : : // operations are on short data.
14 : : //
15 : : // 2) As a fall-back, we use HMAC/MD5 (keyed MD5) for data of arbitrary
16 : : // length. MD5 is used as a scrambling scheme so that it is difficult
17 : : // for the adversary to construct conflicts, though I do not know if
18 : : // HMAC/MD5 is provably universal.
19 : :
20 : : #include "config.h"
21 : :
22 : : #include "Hash.h"
23 : :
24 : : // Define *one* of the following as the universal hash function family to use.
25 : :
26 : : // #define USE_DIETZFELBINGER // TwoWise
27 : : #define USE_H3
28 : : // #define USE_UHASH_CW
29 : : // #define USE_UMAC_NH
30 : :
31 : : int hash_cnt_all = 0, hash_cnt_uhash = 0;
32 : :
33 : : #if defined(USE_DIETZFELBINGER)
34 : :
35 : : #include "TwoWise.h"
36 : : const TwoWise* two_wise = 0;
37 : :
38 : : #elif defined(USE_H3)
39 : :
40 : : #include "H3.h"
41 : : const H3<hash_t, UHASH_KEY_SIZE>* h3;
42 : :
43 : : #elif defined(USE_UHASH_CW)
44 : :
45 : : // The Carter-Wegman family of universal hash functions.
46 : : // f(x) = (sum(a_i * x_i) mod p) mod N
47 : : // where p is a prime number between N and 2N.
48 : : // Here N = 2^32.
49 : :
50 : : class UHashCW {
51 : : typedef uint32 word_t;
52 : : public:
53 : : UHashCW(int arg_max_key_size)
54 : : {
55 : : max_num_words = (arg_max_key_size + sizeof(word_t) - 1) /
56 : : sizeof(word_t);
57 : :
58 : : a = new word_t[max_num_words + 1];
59 : : x = new word_t[max_num_words + 1];
60 : :
61 : : for ( int i = 0; i < max_num_words + 1; ++i )
62 : : a[i] = rand32bit();
63 : :
64 : : b = rand64bit();
65 : : }
66 : :
67 : : ~UHashCW()
68 : : {
69 : : delete [] a;
70 : : delete [] x;
71 : : }
72 : :
73 : : uint32 hash(int len, const u_char* data) const
74 : : {
75 : : int xlen = (len + sizeof(word_t) - 1) / sizeof(word_t);
76 : : ASSERT(xlen <= max_num_words);
77 : :
78 : : x[xlen] = 0;
79 : : x[xlen-1] = 0; // pad with 0
80 : :
81 : : memcpy(static_cast<void *>(x), data, len);
82 : :
83 : : uint64 h = b;
84 : : for ( int i = 0; i < xlen; ++i )
85 : : h += (static_cast<uint64>(x[i]) * a[i]);
86 : :
87 : : h += static_cast<uint64>(len) * a[xlen];
88 : :
89 : : // h = h % kPrime
90 : : //
91 : : // Here we use a trick given that h is a Mersenne prime:
92 : : //
93 : : // Let K = 2^61. Let h = a * K + b.
94 : : // Thus, h = a * (K-1) + (a + b).
95 : :
96 : : h = (h & kPrime) + (h >> 61);
97 : : if ( h >= kPrime )
98 : : h -= kPrime;
99 : :
100 : : // h = h % 2^32
101 : : return static_cast<uint32>(0xffffffffUL & h);
102 : : }
103 : :
104 : : protected:
105 : : static const uint64 kPrime = (static_cast<uint64>(1) << 61) - 1;
106 : :
107 : : int max_num_words;
108 : : word_t* a;
109 : : uint64 b;
110 : : word_t* x;
111 : : };
112 : :
113 : : const UHashCW* uhash_cw = 0;
114 : :
115 : : #elif defined(USE_UMAC_NH)
116 : :
117 : : // Use the NH hash function proposed in UMAC.
118 : : // (See http://www.cs.ucdavis.edu/~rogaway/umac/)
119 : : //
120 : : // Essentially, it is computed as:
121 : : //
122 : : // H = (x_0 +_16 k_0) * (x_1 +_16 k_1) +
123 : : // (x_2 +_16 k_2) * (x_3 +_16 k_3) + ...
124 : : //
125 : : // where {k_i} are keys for universal hashing,
126 : : // {x_i} are data words, and +_16 means plus mod 2^16.
127 : : //
128 : : // This is faster than UHASH_CW because no modulo operation
129 : : // is needed. But note that it is 2^-16 universal, while the
130 : : // other universal functions are (almost) 2^-32 universal.
131 : : //
132 : : // Note: UMAC now has a code release under a BSD-like license, and we may want
133 : : // to consider using it instead of our home-grown code.
134 : :
135 : : #ifndef DEBUG
136 : : #error "UMAC/NH is experimental code."
137 : : #endif
138 : :
139 : : class UMacNH {
140 : : // NH uses 16-bit words
141 : : typedef uint16 word_t;
142 : : public:
143 : : UMacNH(int arg_max_key_size)
144 : : {
145 : : max_num_words = (arg_max_key_size + sizeof(word_t) - 1) /
146 : : sizeof(word_t);
147 : :
148 : : // Make max_num_words 2n+1
149 : : if ( max_num_words % 2 == 0 )
150 : : ++max_num_words;
151 : :
152 : : a = new word_t[max_num_words + 1];
153 : : x = new word_t[max_num_words + 1];
154 : :
155 : : for ( int i = 0; i < max_num_words + 1; ++i )
156 : : a[i] = rand16bit();
157 : : }
158 : :
159 : : ~UMacNH()
160 : : {
161 : : delete [] a;
162 : : delete [] x;
163 : : }
164 : :
165 : : uint32 hash(int len, const u_char* data) const
166 : : {
167 : : int xlen = (len + sizeof(word_t) - 1) / sizeof(word_t);
168 : : if ( xlen % 2 == 0 )
169 : : ++xlen;
170 : :
171 : : ASSERT(xlen <= max_num_words);
172 : :
173 : : x[xlen] = len;
174 : : x[xlen-1] = 0; // pad with 0
175 : : if ( xlen >= 2 )
176 : : x[xlen-2] = 0;
177 : :
178 : : memcpy(static_cast<void *>(x), data, len);
179 : :
180 : : uint32 h = 0;
181 : : for ( int i = 0; i <= xlen; i += 2 )
182 : : h += (static_cast<uint32>(x[i] + a[i]) *
183 : : static_cast<uint32>(x[i+1] + a[i+1]));
184 : :
185 : : return h;
186 : : }
187 : :
188 : : protected:
189 : : int max_num_words;
190 : : word_t* a;
191 : : word_t* x;
192 : : };
193 : :
194 : : const UMacNH* umac_nh = 0;
195 : :
196 : : #else
197 : :
198 : : #ifdef DEBUG
199 : : #error "No universal hash function is used."
200 : : #endif
201 : :
202 : : #endif
203 : :
204 : 3 : void init_hash_function()
205 : : {
206 : : // Make sure we have already called init_random_seed().
207 [ - + ]: 3 : ASSERT(hmac_key_set);
208 : :
209 : : // Both Dietzfelbinger and H3 use random() to generate keys
210 : : // -- is it strong enough?
211 : : #if defined(USE_DIETZFELBINGER)
212 : : two_wise = new TwoWise((UHASH_KEY_SIZE + 3) >> 2);
213 : : #elif defined(USE_H3)
214 : 3 : h3 = new H3<hash_t, UHASH_KEY_SIZE>();
215 : : #elif defined(USE_UHASH_CW)
216 : : uhash_cw = new UHashCW(UHASH_KEY_SIZE);
217 : : #elif defined(USE_UMAC_NH)
218 : : umac_nh = new UMacNH(UHASH_KEY_SIZE);
219 : : #endif
220 : 3 : }
221 : :
222 : 22414 : HashKey::HashKey(bro_int_t i)
223 : : {
224 : 22414 : key_u.i = i;
225 : 22414 : key = (void*) &key_u;
226 : 22414 : size = sizeof(i);
227 : 22414 : hash = HashBytes(key, size);
228 : 22414 : is_our_dynamic = 0;
229 : 22414 : }
230 : :
231 : 0 : HashKey::HashKey(bro_uint_t u)
232 : : {
233 : 0 : key_u.i = bro_int_t(u);
234 : 0 : key = (void*) &key_u;
235 : 0 : size = sizeof(u);
236 : 0 : hash = HashBytes(key, size);
237 : 0 : is_our_dynamic = 0;
238 : 0 : }
239 : :
240 : 3893 : HashKey::HashKey(uint32 u)
241 : : {
242 : 3893 : key_u.u32 = u;
243 : 3893 : key = (void*) &key_u;
244 : 3893 : size = sizeof(u);
245 : 3893 : hash = HashBytes(key, size);
246 : 3893 : is_our_dynamic = 0;
247 : 3893 : }
248 : :
249 : 14 : HashKey::HashKey(const uint32 u[], int n)
250 : : {
251 : 14 : size = n * sizeof(u[0]);
252 : 14 : key = (void*) u;
253 : 14 : hash = HashBytes(key, size);
254 : 14 : is_our_dynamic = 0;
255 : 14 : }
256 : :
257 : 0 : HashKey::HashKey(double d)
258 : : {
259 : : union {
260 : : double d;
261 : : int i[2];
262 : : } u;
263 : :
264 : 0 : key_u.d = u.d = d;
265 : 0 : key = (void*) &key_u;
266 : 0 : size = sizeof(d);
267 : 0 : hash = HashBytes(key, size);
268 : 0 : is_our_dynamic = 0;
269 : 0 : }
270 : :
271 : 0 : HashKey::HashKey(const void* p)
272 : : {
273 : 0 : key_u.p = p;
274 : 0 : key = (void*) &key_u;
275 : 0 : size = sizeof(p);
276 : 0 : hash = HashBytes(key, size);
277 : 0 : is_our_dynamic = 0;
278 : 0 : }
279 : :
280 : 108568 : HashKey::HashKey(const char* s)
281 : : {
282 : 108568 : size = strlen(s); // note - skip final \0
283 : 108568 : key = (void*) s;
284 : 108568 : hash = HashBytes(key, size);
285 : 108568 : is_our_dynamic = 0;
286 : 108568 : }
287 : :
288 : 59006 : HashKey::HashKey(const BroString* s)
289 : : {
290 : 59006 : size = s->Len();
291 : 59006 : key = (void*) s->Bytes();
292 : 59006 : hash = HashBytes(key, size);
293 : 59006 : is_our_dynamic = 0;
294 : 59006 : }
295 : :
296 : 25536 : HashKey::HashKey(int copy_key, void* arg_key, int arg_size)
297 : : {
298 : 25536 : size = arg_size;
299 : 25536 : is_our_dynamic = 1;
300 : :
301 [ + + ][ # # ]: 25536 : if ( copy_key )
302 : : {
303 : 24810 : key = (void*) new char[size];
304 : 24810 : memcpy(key, arg_key, size);
305 : : }
306 : : else
307 : 726 : key = arg_key;
308 : :
309 : 25536 : hash = HashBytes(key, size);
310 : 25536 : }
311 : :
312 : 13751 : HashKey::HashKey(const void* arg_key, int arg_size, hash_t arg_hash)
313 : : {
314 : 13751 : size = arg_size;
315 : 13751 : hash = arg_hash;
316 : 13751 : key = CopyKey(arg_key, size);
317 : 13751 : is_our_dynamic = 1;
318 : 13751 : }
319 : :
320 : : HashKey::HashKey(const void* arg_key, int arg_size, hash_t arg_hash,
321 : 61 : bool /* dont_copy */)
322 : : {
323 : 61 : size = arg_size;
324 : 61 : hash = arg_hash;
325 : 61 : key = const_cast<void*>(arg_key);
326 : 61 : is_our_dynamic = 0;
327 : 61 : }
328 : :
329 : 21362 : HashKey::HashKey(const void* bytes, int arg_size)
330 : : {
331 : 21362 : size = arg_size;
332 : 21362 : key = CopyKey(bytes, size);
333 : 21362 : hash = HashBytes(key, size);
334 : 21362 : is_our_dynamic = 1;
335 : 21362 : }
336 : :
337 : 45428 : void* HashKey::TakeKey()
338 : : {
339 [ + + ]: 45428 : if ( is_our_dynamic )
340 : : {
341 : 4343 : is_our_dynamic = 0;
342 : 4343 : return key;
343 : : }
344 : : else
345 : 45428 : return CopyKey(key, size);
346 : : }
347 : :
348 : 76198 : void* HashKey::CopyKey(const void* k, int s) const
349 : : {
350 : 76198 : void* k_copy = (void*) new char[s];
351 : 76198 : memcpy(k_copy, k, s);
352 : 76198 : return k_copy;
353 : : }
354 : :
355 : 240793 : hash_t HashKey::HashBytes(const void* bytes, int size)
356 : : {
357 : 240793 : ++hash_cnt_all;
358 : :
359 [ + + ]: 240793 : if ( size <= UHASH_KEY_SIZE )
360 : : {
361 : 217750 : const uint8* b = reinterpret_cast<const uint8*>(bytes);
362 : 217750 : ++hash_cnt_uhash;
363 : : #if defined(USE_DIETZFELBINGER)
364 : : return two_wise->Hash(size, b);
365 : : #elif defined(USE_H3)
366 : : // H3 doesn't check if size is zero
367 [ + + ]: 217750 : return ( size == 0 ) ? 0 : (*h3)(bytes, size);
368 : : #elif defined(USE_UHASH_CW)
369 : : return uhash_cw->hash(size, b);
370 : : #elif defined(USE_UMAC_NH)
371 : : return umac_nh->hash(size, b);
372 : : #else
373 : : --hash_cnt_uhash;
374 : : #endif
375 : : }
376 : :
377 : : // Fall back to HMAC/MD5 for longer data (which is usually rare).
378 : : hash_t digest[16];
379 : 23043 : hmac_md5(size, (unsigned char*) bytes, (unsigned char*) digest);
380 : 240793 : return digest[0];
381 [ + - ][ + - ]: 6 : }
|
