diff options
Diffstat (limited to 'src/libstrongswan/utils/chunk.c')
| -rw-r--r-- | src/libstrongswan/utils/chunk.c | 251 |
1 files changed, 191 insertions, 60 deletions
diff --git a/src/libstrongswan/utils/chunk.c b/src/libstrongswan/utils/chunk.c index d7f1c31d9..04f3eea7d 100644 --- a/src/libstrongswan/utils/chunk.c +++ b/src/libstrongswan/utils/chunk.c @@ -1,5 +1,5 @@ /* - * Copyright (C) 2008-2009 Tobias Brunner + * Copyright (C) 2008-2013 Tobias Brunner * Copyright (C) 2005-2006 Martin Willi * Copyright (C) 2005 Jan Hutter * Hochschule fuer Technik Rapperswil @@ -16,24 +16,17 @@ */ #include <stdio.h> +#include <sys/types.h> #include <sys/stat.h> +#include <fcntl.h> #include <unistd.h> #include <errno.h> +#include <pthread.h> #include <ctype.h> #include "chunk.h" #include "debug.h" -/* required for chunk_hash */ -#undef get16bits -#if (defined(__GNUC__) && defined(__i386__)) -#define get16bits(d) (*((const u_int16_t*)(d))) -#endif -#if !defined (get16bits) -#define get16bits(d) ((((u_int32_t)(((const u_int8_t*)(d))[1])) << 8)\ - + (u_int32_t)(((const u_int8_t*)(d))[0]) ) -#endif - /** * Empty chunk. */ @@ -579,72 +572,193 @@ bool chunk_printable(chunk_t chunk, chunk_t *sane, char replace) } /** - * Described in header. - * - * The implementation is based on Paul Hsieh's SuperFastHash: - * http://www.azillionmonkeys.com/qed/hash.html + * Helper functions for chunk_mac() */ -u_int32_t chunk_hash_inc(chunk_t chunk, u_int32_t hash) +static inline u_int64_t sipget(u_char *in) { - u_char *data = chunk.ptr; - size_t len = chunk.len; - u_int32_t tmp; - int rem; + u_int64_t v = 0; + int i; - if (!len || data == NULL) + for (i = 0; i < 64; i += 8, ++in) { - return 0; + v |= ((u_int64_t)*in) << i; } + return v; +} - rem = len & 3; - len >>= 2; +static inline u_int64_t siprotate(u_int64_t v, int shift) +{ + return (v << shift) | (v >> (64 - shift)); +} - /* Main loop */ - for (; len > 0; --len) - { - hash += get16bits(data); - tmp = (get16bits(data + 2) << 11) ^ hash; - hash = (hash << 16) ^ tmp; - data += 2 * sizeof(u_int16_t); - hash += hash >> 11; - } +static inline void sipround(u_int64_t *v0, u_int64_t *v1, u_int64_t *v2, + u_int64_t *v3) +{ + *v0 += *v1; + *v1 = siprotate(*v1, 13); + *v1 ^= *v0; + *v0 = siprotate(*v0, 32); + + *v2 += *v3; + *v3 = siprotate(*v3, 16); + *v3 ^= *v2; + + *v2 += *v1; + *v1 = siprotate(*v1, 17); + *v1 ^= *v2; + *v2 = siprotate(*v2, 32); + + *v0 += *v3; + *v3 = siprotate(*v3, 21); + *v3 ^= *v0; +} + +static inline void sipcompress(u_int64_t *v0, u_int64_t *v1, u_int64_t *v2, + u_int64_t *v3, u_int64_t m) +{ + *v3 ^= m; + sipround(v0, v1, v2, v3); + sipround(v0, v1, v2, v3); + *v0 ^= m; +} - /* Handle end cases */ +static inline u_int64_t siplast(size_t len, u_char *pos) +{ + u_int64_t b; + int rem = len & 7; + + b = ((u_int64_t)len) << 56; switch (rem) { + case 7: + b |= ((u_int64_t)pos[6]) << 48; + case 6: + b |= ((u_int64_t)pos[5]) << 40; + case 5: + b |= ((u_int64_t)pos[4]) << 32; + case 4: + b |= ((u_int64_t)pos[3]) << 24; case 3: - { - hash += get16bits(data); - hash ^= hash << 16; - hash ^= data[sizeof(u_int16_t)] << 18; - hash += hash >> 11; - break; - } + b |= ((u_int64_t)pos[2]) << 16; case 2: - { - hash += get16bits(data); - hash ^= hash << 11; - hash += hash >> 17; + b |= ((u_int64_t)pos[1]) << 8; + case 1: + b |= ((u_int64_t)pos[0]); + break; + case 0: break; + } + return b; +} + +/** + * Caculate SipHash-2-4 with an optional first block given as argument. + */ +static u_int64_t chunk_mac_inc(chunk_t chunk, u_char *key, u_int64_t m) +{ + u_int64_t v0, v1, v2, v3, k0, k1; + size_t len = chunk.len; + u_char *pos = chunk.ptr, *end; + + end = chunk.ptr + len - (len % 8); + + k0 = sipget(key); + k1 = sipget(key + 8); + + v0 = k0 ^ 0x736f6d6570736575ULL; + v1 = k1 ^ 0x646f72616e646f6dULL; + v2 = k0 ^ 0x6c7967656e657261ULL; + v3 = k1 ^ 0x7465646279746573ULL; + + if (m) + { + sipcompress(&v0, &v1, &v2, &v3, m); + } + + /* compression with c = 2 */ + for (; pos != end; pos += 8) + { + m = sipget(pos); + sipcompress(&v0, &v1, &v2, &v3, m); + } + sipcompress(&v0, &v1, &v2, &v3, siplast(len, pos)); + + /* finalization with d = 4 */ + v2 ^= 0xff; + sipround(&v0, &v1, &v2, &v3); + sipround(&v0, &v1, &v2, &v3); + sipround(&v0, &v1, &v2, &v3); + sipround(&v0, &v1, &v2, &v3); + return v0 ^ v1 ^ v2 ^ v3; +} + +/** + * Described in header. + */ +u_int64_t chunk_mac(chunk_t chunk, u_char *key) +{ + return chunk_mac_inc(chunk, key, 0); +} + +/** + * Secret key allocated randomly during first use. + */ +static u_char key[16]; + +/** + * Static key used in case predictable hash values are required. + */ +static u_char static_key[] = {0x00, 0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07, + 0x08, 0x09, 0x0a, 0x0b, 0x0c, 0x0d, 0x0e, 0x0f}; + +/** + * Only allocate the key once + */ +static pthread_once_t key_allocated = PTHREAD_ONCE_INIT; + +/** + * Allocate a key on first use, we do this manually to avoid dependencies on + * plugins. + */ +static void allocate_key() +{ + ssize_t len; + size_t done = 0; + int fd; + + fd = open("/dev/urandom", O_RDONLY); + if (fd >= 0) + { + while (done < sizeof(key)) + { + len = read(fd, key + done, sizeof(key) - done); + if (len < 0) + { + break; + } + done += len; } - case 1: + close(fd); + } + /* on error we use random() to generate the key (better than nothing) */ + if (done < sizeof(key)) + { + srandom(time(NULL) + getpid()); + for (; done < sizeof(key); done++) { - hash += *data; - hash ^= hash << 10; - hash += hash >> 1; - break; + key[done] = (u_char)random(); } } +} - /* Force "avalanching" of final 127 bits */ - hash ^= hash << 3; - hash += hash >> 5; - hash ^= hash << 4; - hash += hash >> 17; - hash ^= hash << 25; - hash += hash >> 6; - - return hash; +/** + * Described in header. + */ +u_int32_t chunk_hash_inc(chunk_t chunk, u_int32_t hash) +{ + pthread_once(&key_allocated, allocate_key); + /* we could use a mac of the previous hash, but this is faster */ + return chunk_mac_inc(chunk, key, ((u_int64_t)hash) << 32 | hash); } /** @@ -652,7 +766,24 @@ u_int32_t chunk_hash_inc(chunk_t chunk, u_int32_t hash) */ u_int32_t chunk_hash(chunk_t chunk) { - return chunk_hash_inc(chunk, chunk.len); + pthread_once(&key_allocated, allocate_key); + return chunk_mac(chunk, key); +} + +/** + * Described in header. + */ +u_int32_t chunk_hash_static_inc(chunk_t chunk, u_int32_t hash) +{ /* we could use a mac of the previous hash, but this is faster */ + return chunk_mac_inc(chunk, static_key, ((u_int64_t)hash) << 32 | hash); +} + +/** + * Described in header. + */ +u_int32_t chunk_hash_static(chunk_t chunk) +{ + return chunk_mac(chunk, static_key); } /** |