In order to implement hash table one need to map key onto an index in the table - this is done with a hash function: hash(string) ---> number.
Here's a problem. If an attacker knows the hash function, she can produce many strings that will give the same number in return. This usually wasn't a problem, but in the web world it is. It is possible to flood the server (usually in python, ruby, perl) with such crafted requests that, for example, all headers will end up with precisely the same hash value: hash(any_given_header_in_request) ---> fixed value.
This is will result in hash table collision and is generally bad. Normal hash functions can't solve this. This problem of maliciously creating hash collisions is called "hash flooding".
Siphash is an attempt to solve the problem. It is more than a hash function - it's a crypto PRF function and that gives you more guarantees than dumb hash function. Most importantly it takes two values: a "string to hash" and a "crypto key": siphash(string, crypto_key) --> number.
The idea is to generate this "crypto_key" randomly on each program execution, to make sure the attacker can't predict it.
Crypto speaking hash functions may be reversible. There is nothing guaranteeing that they are not. But Siphash is a PRF, and in crypto-speach this means it's not reversible. If you can produce an efficient algorithm to reverse Siphash - ie: given crypto key and hash value predict input string - you can write a good paper and be famous.
I may be misunderstanding you, but isn't the point of a (good) cryptographic hash function that you cannot produce the multiple plaintext which will give the same value, despite knowing the hash function?
That sounds suspiciously like an HMAC.
An HMAC gives you something very nice, but it's of its choosing. If you want a 256-entry cache, the security properties of a 256-bit HMAC result is not a good fit for the needs of a cache key.
If you want an infinitely big cache, an HMAC gives you zero collisions, but in this case what you want is an 8-bit result that spreads nicely over the 256 values, doesn't let an attacker fill one bucket, and doesn't let an attacker learn anything about the other users and their cache entries.
From reading up on it a bit more, it is an MAC[1]. The difference between it and a generic HMAC construction (say with HMAC-SHA256) is that it's intended to specifically be an MAC which leads to more efficiency.
> An HMAC gives you something very nice, but it's of its choosing. If you want a 256-entry cache, the security properties of a 256-bit HMAC result is not a good fit for the needs of a cache key.
It'd be a fine fit from a cryptographic perspective. It's just slow relative to something like this which more catered to the specific problem.
> If you want an infinitely big cache, an HMAC gives you zero collisions, but in this case what you want is an 8-bit result that spreads nicely over the 256 values, doesn't let an attacker fill one bucket, and doesn't let an attacker learn anything about the other users and their cache entries.
The result of SipHash is 8-bytes (not bits). You'd still have to truncate or consolidate the bits to reduce it to 1-byte (8-bits).
Willing to be educated, but won't I get that by just masking off 8 bits off of say SHA-x?
[edit: h(s + secret-bits) & 0xff ]
BLAKE2 is fast for many use cases, but its block size is 64 (for BLAKE2s) and 128 (for BLAKEb) bytes, so hashing anything shorter than the block size will take the same time as hashing the full block. SipHash was designed for fast hashing of short inputs (its block size is 8 bytes), which is why it's good for hash tables and similar uses.
As for performance in different languages: SipHash is pretty fast in any language that has native 64-bit integers, but is not so fast in those which don't (JavaScript). The same applies to BLAKE2b (but not BLAKE2s).
BLAKE2 is slower in Java than MD5 probably because it doesn't use SIMD instructions there, which give a good boost for it (as designed).
Not sure about the SIMD angle & Java. Ref. impl. of Blake2B [in C] doesn't use it [last I looked at it]. I ~think it has to do with the endian bias of the algo.
There are a few optimized implementation in the BLAKE2 code package — https://github.com/BLAKE2/BLAKE2. "Ref" indeed doesn't use SIMD, but other implementations do use them. I think the claim that it's faster than MD5 is based on benchmarking SIMD implementations, and if I remember correctly, the reference one is a bit slower.
Yes, endianness conversion — that is, just reading uint64 or uint32 from byte arrays — if done in the most simple way by bit shifting can be a factor. Another factor that influenced performance of pure Go implementation (should be similar to Java) is bounds checking.
Well, it's supposed to beat MD5 straight up. Granted the claim is a bit hedged.
> if done in the most simple way by bit shifting can be a factor
Do you mean using byte swap instructions or is there an algorithm that I should know about? :)
* * *
Not byte swapping, just simple reading bytes and shifting them into the correct position in uint32 like this:
uint32 result = (b[3] << 24) | (b[2] << 16) | (b[1] << 8) | b[0];
uint32 result = *b;
uint32 result = swap(*b);Sure, have seen those. No biggie, but my point was that vanila B2b (on C) is already neck and neck with MD5.
> uint32 result = (b[3] << 24) | (b[2] << 16) | (b[1] << 8) | b[0];
Yep, akaik that's all you can do on the JVM & of course for 64bit it's even more work. I thought you meant some sort of magic number bit wizzardry :)
Maybe SHA-8 works fine. I don't know. I've never seen any real mathematical investigation of that, and that's the point.
Is it ok to use the same random key with siphash for lots of different hashes as long as the key is secret and mutates once per launch (i.e. generating once on app startup and use it for all hashes)?
Web servers use hash tables for storing per-request data. If an attacker knows the hash function (say, SHA1), they can create a few hundred requests that yield the same hash, giving hundreds of hash collisions and creating a Denial-of-Service attack with the same effect as millions of ordinary requests. It's a form of DoS amplification.
A keyed hash function fixes this by keeping part of the hash algorithm (the key) secret. You can turn e.g. SHA1 into a keyed hash function by e.g. HMAC, but that's computationally expensive. SipHash, being a "natively keyed" hash function, is much faster.