Counter argument: http://perl11.org/blog/seed.html
Now even the kernel devs are drinking the coolaid, verbatim copying wrong claims from the SipHash authors.
Now even the kernel devs are drinking the coolaid, verbatim copying wrong claims from the SipHash authors.
Specifically, the argument here is that SipHash is insecure because you can read the private key out of the process's memory, or you can convince the process to dump its private key by setting an environment variable.
But anyone who can read your process memory or set environment variables has a million easier ways to attack your process. The thing SipHash is protecting you from is not yourself. It's protecting you from attackers on the network, that is, not on your machine, giving you malicious data to abuse your hash table. Nobody can protect you from attackers who can run opcodes in your Perl VM.
In the kernel, there's no such thing as a Perl VM or environment variables. There is a such thing as private kernel memory, and it is kept secret from userspace and (of course) from other people on the network, for very good reason. If you can read kernel memory, or execute kernel code, you have already won.
This is like a military officer saying, "These improved missile launchers don't keep us safe. There's a secret code to launch the missiles, and if the enemy happens to captures our capital and breaks into our military installations and kidnaps the president and steals the launch codes, they can launch our own missiles against us."
Masterful trolling, rurban. We all took you seriously.
If I can already read bytes from the running executable, I can just smash it to bits. If I can run processes on the machine at all, I don't need to slow it down with hash collisions, I can just fork bomb.
Can you usefully attack without having that kind of access?
They will replace SHA1 with siphash (already done in this branch), their open-addressing with chaining and primes with power of 2. So they will loose all the previous performance and security by the false security and performance claim of siphash.
siphash essentially says: we are DoS secure and we are fast. Both is provable wrong.
It looks like you also made a "prediction" about what's going to be decided by people who certainly aren't you in the future.
Got a cryptographically secure PRF that's faster than Siphash for small inputs and has undergone extensive cryptanalysis? If so, I'm all ears. If not, get lost, troll.
There's a real use case for a secure PRF fast for small inputs. That's why this code has been added.
1. DOS proof: a hash function can never lead to DoS proofness. Every hash function can be trivially brute forced to find enough collisions for such an attack. When you need to protect against such a worst case you don't make your hash function slower and get limited seed hiding, you rather check for such an attack and mitigate it directly, at the collision resolution.
2. Slowness: see my smhasher page. The slowest of all hash functions which is used in hash tables.
I don't see a usecase for a slow PRF in net. All other PRF's are faster. I also don't see more security, only less. SHA1 replaced by SipHash surely makes it faster, but not safer.
That's true. Calling it "cryptographically secure" could easily send the wrong signals. It's meant for network traffic authentication and hash-tables. Using it in all places where you previously used SHA is not a good idea. Hopefully the kernel developers will know when it's suitable.
Siphash is secure in the same sense as AES, HMAC and a CSPRNG: seeing many consecutive values does reveal the key and does not allow predicting the next value.
Timings:
BITS SIZE TIME
8 - 255 0.003s
9 - 511 0.006s
10 - 1023 0.033s
11 - 2047 0.12s
12 - 4095 0.45s
13 - 8191 1.82s
14 - 16383 7.6s
15 - 32767 31s
16 - 65535 2m2s
18 - 262143 4m3s 23770
The only SipHash security you get is seed hiding. Once you got it, it's insecure. You get the seed by various means, usually by poking into memory or by solving via order-exposure and timing attacks. This commit doesn't mention anything of it, because it followed the flawed siphash chapter 6, which only knows about chained hash tables.
So far only the linux kernel, glibc and java were the only immune hash tables to such nonsense. Now only java and glibc is remaining. I should have done that CCC talk this year about the disturbing siphash security theatre out there.
Thanks god the kernel still uses primes, so you need a full 32bit attack. But with this commit message I fear this will erode also to power of 2 sooner or later to use a simple bit test instead of mod (or the mult. trick).
Can you explain how to conduct "order-exposure and timing attacks" against SipHash? The page you link describes how to conduct "poking into memory", which is outside of the threat model.
"Order-exposure and timing attacks" -- which types of attacks against SipHash do you have in mind? Could you elaborate, instead of your misinformed hand-waving?
Isn't that the case for every cryptographic primitive? I mean, that's sort of the point of private keys, yes? Once you have the key, you can decrypt AES ciphertext, create signatures with RSA, and forge valid MAC tags.
Not sure what point you're making here.
Acquiring random seed is much deeper security attack than hash flooding network connection. If you can get the seed, why would you do DDoS-attack. You do DDoS attacks when you can't get in and do more severe attacks.
It's like braking into someones house to get the spare key so you can get in and rob them.
E.g. the commit replaced the secure SHA1 with a 256bit key in net/ipv4/syncookies.c with a less secure siphash with a 128bit key. https://git.kernel.org/cgit/linux/kernel/git/davem/net-next....
https://git.kernel.org/cgit/linux/kernel/git/davem/net-next.... talks about siphash being more secure than MD5 and SHA1. It's only more secure than trivial fast hash functions, like DJB33* or FNV1, but not MD5. These guys want to maintain your networking code!
The new Documentation/siphash.txt on the other hand is correct. But it simply refers to the siphash pdf without refuting the wrong chapter 6 parts, which lead to the wide-spread hash table insecurity amongst most popular dynamic languages.
The prior partial sha1/md5 implementation usage was pretty dubious.
Siphash has significant performance improvements for things like syncookies and secure sequence numbers.
Your comment about knowing the address of the key and taking it out of kernel memory... wtf? If you can read arbitrary kernel memory, it's already game over. The whole attack model relies on ring 0 being ring 0.
If you can access memory, you are already in and don't need to do hash flooding to being with.
(If you figure out how to leak keys from kernel space, you've uncovered a grave vulnerability, way worse than anything discussed here.)
Every argument I've seen from rurban is predicated upon the assumption that the seed will be leaked by the application, either by directly leaking the key's contents or by an algorithmic attack on the output of the algorithm. As you mention, the former would constitute a grave vulnerability in the application (the kernel, in this case). The latter would constitute a grave vulnerability in the algorithm.
As for assessing whether there are vulnerabilities in the algorithm, we have an academic field (cryptanalysis) that exists to inform us when such vulnerabilities exist. Cryptanalysts' efforts have given us substantial assurance that the algorithms we use everyday (e.g. AES, HMAC, ChaCha, GMAC) are both pseudo-random and adequately prevent disclosure of their keys. SipHash was explicitly designed to be resistant to cryptanalytic attack, by two well-regarded cryptographers (Bernstein and Aumasson). They designed it targeting a specific cryptographic strength/performance trade-off, and to my knowledge it is the best contender for building a flood resistant hash table.
zx2c4, I look forward to using your code. Thank you for making the Linux kernel more secure.
But the siphash paper and all arguments I heard from the siphash = DoS proof proponents don't know anything about current hash table security analysis, and come up with wrong claims all over (fast and DoS proof), which is trivially refutable.
A hash table firstly needs to be fast. Otherwise you are better of with a patricia tree. To mitigate hash flood attacks, you don't start by making it slow by using 2x slower hash functions with only limited usefulness against said attacks. You rather mitigate the attack vector, where you need to do it: In the collision resolution. This is were you get from O(1) to O(n) and not in the hash function.
Robin-Hood has predefined max-collisions, double-hashing is dos proof, all other open or chained hash tables can trivially detect such an attack with zero cost with no need to slow a hash table down by 2. And with only limited added security.
Yes, internal seed exposure is not your attack vector. This exposure is only to simplify my argument. You still get at the seed by analysing external information. You got the ordering and you got timing information. Even with a 64bit seed this is not enough security to label siphash dos-proof. Again, calling a hash function hash table dos-proof is pure security theatre and provable wrong.
SipHash was only designed to mitigate timing attacks against the hash function and to mix the seed properly inside the loop, but not against timing attacks in the collisions. Using it as hash table function is totally useless.
> and to my knowledge it is the best contender for building a flood resistant hash table.
It is in fact the worst contender. The best contender is a fast simple hash function and protect against hash flood attacks where they happen. in the collisions. you don't make the general case 2x slower, while the worst case is still vulnerable. the only advantage of siphash for the worst case is that it protects from trivial seed exposure known for 2 years already.
zx2c4 is not making the net code more secure, he is just making it slower. this is mere openbsd theatre. and by replacing sha1 with siphash for the cookies it is even less secure.
It is true that timing attacks to guess the key could be an issue, but I have yet to see reports of this having been done. Also, it wouldn't be hard to fix in the hash table implementations.
A random seed helps, but doesn't guarantee DoS-safeness. Same for SipHash. Using SipHash doesn't give you a DoS-safe hash table if you use chained hashing. It only makes it slower and hides the seed better.
Secure hash functions do not exist with hash tables. I'm tried of hearing all this nonsense all over. SipHash is a secure PRF, but we don't care for "Pseudo Random Functions", we look for hash functions.
Building a hash table with a function randomly selected from a PRF is universal hashing.
Double hashing with random seeds would qualify as universal hashing though.
> Stopping advanced hash flooding. The _worst possible_ exposure of hash-table indices would simply show the attacker H(m) mod `for any attacker-selected string m. We advocate protecting against this maximum possible exposure, so that applications do not have to worry about how much exposure they actually provide. The attacker’s goal, given this exposure, is to find many strings m having a single value H(m) mod `. https://131002.net/siphash/siphash.pdf
They also state that the "Target applications include network traffic authentication and hash-table lookups protected against hash-flooding denial-of-service attacks".
It's nice to have a fast random hash function, that is also reasonably cryptographically strong, in case an attacked gets access to the hash values. That doesn't mean it's as cryptographically strong as hash functions specifically designed for full exposure.
I'm just saying, use it for hash-tables, but don't use it as a general replacement for HMAC-SHA-1 in your encryption schemes. At least I don't see the authors recommending that anywhere.
You're correct — it shouldn't replace HMAC in most cases mainly due to its short output (64 bits) and because it received less analysis than common cryptographic hash functions/MACs.
SipHash is a family of functions (a PRF), and requires a user-supplied 128-bit random key to select a function in the PRF. Can you explain why you believe this "only gives you a few bits of randomness"? Why would it not give you 128 bits of randomness?
The kernel implementation here says that you're supposed to use get_random_bytes on a siphash_key_t (see the article posted), which gives you 128 bits of high-quality randomness.
This is my point. A universal hash function is a random distribution over deterministic functions. You can always create a single deterministic function with a seed in such a way, that it acts as drawing a random function from a distribution.
I don't know that siphash is universal, certainly not all seeded functions are. Perhaps that's your point. I'm just saying that using randomness is the only way to create universality.
Actually the Aumasson, Bernstein paper http://cr.yp.to/siphash/siphash-20120918.pdf has some interesting considerations on timing attacks against universal hash functions.