Generally speaking, the kernel community doesn't like to add external dependencies. And then including it in the kernel tree gives some advantages: architecture-specific speed hacks can be applied, kernel-specific utilities can be used in the implementation.
Technically I think it could be built as a dynamically loadable kernel module and shipped separately from the kernel image under /lib/modules.
This does not make sense if the functionality is always needed, in which case it should be statically compiled in.
In any case there is no benefit of developping separately considering that the module must call functionality from the kernel (at least for the entropy part) so the code is tightly bound to the kernel (and to specific versions of the kernel at that).
The functionality could also live in userland, and the kernel could start a process, which links the libsiphash shared library. The process could then communicate with the kernel by other means, reducing dependencies. And of course that would be too slow.
I haven't been actively watching SipHash but I do subscribe to the linux-hardening list and have seen a little bit of the discussion - my understanding is there are a bunch of potential applications in the kernel in areas that already use other hash functions, such as TCP sequence numbers, which are security sensitive, where SipHash could be faster and/or more secure.
Hash functions aren't included in the kernel for exposure to userspace, they're included for internal kernel use.
Hopefully not "primary" for long. These are just the first uses I saw to immediately convert to siphash with the least amount of controversy to actually get siphash in the kernel. Now that these have landed, other developers can gradually start using it in more and more places. Who knows what the "primary" use will be after 4.11.
When in the kernel you don't really have access to most of the standard library so there's no real guarantee that "libsiphash" wouldn't need symbols defined elsewhere.
The kernel does allow for loadable modules but the point of some of these hashes is to replace calls to some md5 and sha equivalents inside the kernel itself. As a result, the symbols would need to be defined at compile time (so these functions need to be compiled in).
This isn't intended for userspace developers to use - they should use a libsiphash. This is intended for use where the kernel needs cryptographically strong hash tables and such, which happens about as often in the kernel as in any userspace program of comparable complexity and functionality.
As someone who's not at all versed in cryptography, (yet) anyone want to put this in more laymen terms? Maybe compare it to an existing cryptographical-method I might understand or at least know of?
ELI5 (distilled from wikipedia page linked by GP, forgive me any errors):
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.
Except if the hash is SHA1 (or any other non-compromised cryptographic hash) they would have a very difficult time creating requests that yield the same hash, that aren't the same request, right?
I'm not sure, but I think if you're just interested in creating N collisions, as opposed to finding something that collides with given plaintext X, that the birthday paradox gives you a huge performance increase and makes it feasible. Also, I think many still use MD5 in applications where SipHash is intended (at least the Linux kernel does).
Hash tables are very important data structures in the computer science world. Hash tables allow you to have amortized O(1) access cost to arbitrary elements - like key/value (often called: map, dict).
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've been looking at using this recently, and had a stupid question about using it -
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)?
The danger in your scheme is that an attacker who finds a way to see lots of keyed hash values in one hash table can flood a different hash table. You should keep a 16 byte key per hash table.
Thanks, I'll only have one set of hashes. My question was really is it ok to use one key per table of hashes, or does it have to be one key per hash. I think you're saying one per table is fine, but wanted to be sure I wasn't doing it wrong. I'll have another look for examples.
> Here's a problem. If an attacker knows the hash function, she can produce many strings that will give the same number in return.
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?
In practice you take X lower bits of the hash value. For example 10 bits if the hash table size is 1024. It's trivial to find many input stings which hash(string) % 1024 == fixed value, for any, even best cryptographic hash function.
> 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.
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.
> 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.
Willing to be educated, but won't I get that by just masking off 8 bits off of say SHA-x?
People do that. I've done it myself. But all the math about SHA's security properties is about absence of collisions in the full result, not about relative frequency in a small part of the result.
Maybe SHA-8 works fine. I don't know. I've never seen any real mathematical investigation of that, and that's the point.
A secure cryptographic hash function's collision resistance should be MIN(output_length/2, claimed_security). For example, SHA-256 collision security is 128 bits with 256-bit output, but if you truncate output to 128 bits, collision resistance will be 64 bits.
Good to know. Is that a general statement or only true for specific subset of languages? Blake2B, for example, is demonstrably faster than MD5 in C, etc., but just barely faster than SHA-1 on the JVM.
All collision-resistant secure cryptographic hash functions (whew) should have this property (BLAKE2, SHA-3, Skein, etc.) (Note: those vulnerable to length extension — e.g. SHA-1, SHA-2 — should be used in HMAC construction for keying.)
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).
Great stuff, thanks. (Just realized who you are! Like your Go work.)
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.
"BLAKE2 comes in two main flavors: BLAKE2b is optimized for 64-bit platforms, and BLAKE2s for smaller architectures. On 64-bit platforms, BLAKE2 is often faster than MD5, yet provides security similar to that of SHA-3. We specify parallel versions BLAKE2bp and BLAKE2sp that are up to 4 and 8 times faster, by taking advantage of SIMD and/or multiple cores."
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? :)
It still sounds like an HMAC albeit with a 64-bit output rather than a larger (say 256-bit) output.
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).
it is a lot like an HMAC. The advantage of something like SipHash is just that it's faster for the same security, not that it's fundamentally different from HMAC.
dict (in python) or hashtables in PHP are amazing data structure that are ON AVERAGE o(1) in complexity for most operations.
But, in worst case they are O(n) where n is the depht of the linked list under the hood.
Hash tables have an immutable as a key of arbitrary size for which an hash is generated in a predictable way thus hash table are mainly hash => value.
Problem occurs when there are collisions of hash values. You must then follow the linked list and check on the exact value of the immutable used as a key with a complete check
If hash function is deterministic then collision can be triggered in order to create DOS slowing down the computer.
O(1) on a 400cycle operation (memory fetching) that becomes o(1024) now requires <1 000 0000> cycles on average (complete comparaison + memory fetching). You basically can turned a 2016 computer into a 1980 computer (in terms of speed)
Hash tables are used when you have sparse data structure, like caches for ephemeral ports (for a firewall) that has a fixed space bigger than memory.
A practical attack for slowing down a FW (thus making it useless) would be to use combinations of IP/port to generates colliding hashes. Hashtables are used a lot in keeping states of stuff. Like connections, sessions ....
Coincidently with python 2.7 cames the concern of predictable hash functions (basically close to CRC) that were fast to compute but predictable. Hence making a DoS easy to engineer when working with webservers (POST/GET parameters are stored in such data structures).
The python concern seems to have spread and raise awareness on the concern.
And then someone was like we need randomisation, but without side channel attack (timing) and thus, a class of hash function known as cryptographic hash function: fast to compute, hard to predict and assymmetrically hard to invert senstivite to an initial customisable parameter (called a key or secret)....
Per that argument, AES is insecure because if I know the key, I can decrypt your messages and even fake a message with valid CMAC authentication tag.
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.
18-30 bit: ~4m for an attackable subset (linear time). The typical size in a kernel is 13bit.
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).
> usually by poking into memory or by solving via order-exposure and timing attacks.
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.
"Poking into kernel memory" is not possible without a serious security vulnerability. That's not within this 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?
> The only SipHash security you get is seed hiding. Once you got it, it's insecure.
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.
The only way we know to make a secure hash function is with a random seed. This is the "correct" way to do it. Anything else claiming "cryptographical strong" without a secret random seed is coolaid.
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.
Nonsense. The only way we know to make a secure hash table function is either via universal hashing (academic literature), via non-linear collision iteration (i.e. java) or by detecting an DoS attack (by counting the collisions (i.e. djbdns).
Please look at the literature. It's embarrassing.
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.
Not if the function is not random. A random seed for a fixed known function only gives you a few bits of randomness.
This random seed is easily detectable from inside, and harder to detect from outside via ordering exposure and timings.
This is not a random function.
Double hashing with random seeds would qualify as universal hashing though.
This is a nice "worst case" feature of siphash. However I don't think its authors would recommend using it in case you know outputs will be easily observable.
It's worst cast in the model of security that hash tables are usually evaluated under. The authors of Siphash state as much:
> 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.
What I'm saying is that not revealing key from observing outputs is a required feature for such PRF to be cryptographically secure. What you cited is a "worst case" for hash table implementation — a hash table revealing its indices; which is fine with SipHash exactly because it's a cryptographic PRF. Network traffic authentication is basically, appending the output of SipHash(packet) to packet and then checking it — again, having many such outputs should not reveal the secret key or allow forging packets, because SipHash is a secure MAC.
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.
> A random seed for a fixed known function only gives you a few bits of randomness.
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.
It's OK to be wrong on HN, and even OK to be militantly wrong, but you can't be uncivil. The people you're talking to are very familiar with the literature --- seemingly more familiar than you are, although I'm holding onto hope that this is just a really bad miscommunication --- and don't deserve invective.
> Nonsense. The only way we know to make a secure hash table function is either via universal hashing (academic literature).
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.
Saying you can read the hash seed from memory sounds like a "wrong side of the airtight hatchway" problem.
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?
No. The problem is the commit message, not yet the implementation. What will follow is what followed at all the other cases: ruby, python, php, rust, ...
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.
Sorry but you still haven't substantiated your argument with any such "proof".
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.
You are the troll when you dont see the obvious proofs.
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.
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.
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.
A 128-bit key is more than plenty; don't be ridiculous.
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.
This is nonsense, of the class of nonsense that regularly comes up on Raymond Chen's blog with the title, "It rather involved being on the other side of this airtight hatchway." https://blogs.msdn.microsoft.com/oldnewthing/20141217-00/?p=... is a good example.
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."
Oh, apparently so! https://twitter.com/szbalint/status/795992687556042752 Making weird but reasonable-sounding claims about cryptanalysis of SipHash seems to be his MO. More Googling finds an amazing history of poorly-reasoned complaints about Perl's adoption of SipHash.
Masterful trolling, rurban. We all took you seriously.
rurban has been proselytizing against use of psuedorandom functions (such as SipHash) for hash tables for a while now. He appears to truly believe that using PRFs for this purpose is inappropriate.
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.
You are again misinformed. A hash function is only of limited usefulness against hash floods. The only mitigation is seed hiding. This is useful for current attacks, where collisions can trivially be predicted with simple, fast hash function.
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.
Since you claim to have made all sorts of cryptographic advances and have various attacks on Siphash, I invite you to run the following code on your main hard drive.
If you can recover your data afterwards, congratulations! You should publish an academic paper! If not, then neither I nor anybody else understands your [lack of a compelling] argument.
79 comments
[ 0.23 ms ] story [ 160 ms ] threadWhat's the purpose of including this in the kernel itself? Why couldn't developers just use some kind of "libsiphash" instead?
Edit: although I think the developers could include it as a statically linked library at compile time even if it's used in the kernel?
Header: https://git.kernel.org/cgit/linux/kernel/git/davem/net-next....
Source: https://git.kernel.org/cgit/linux/kernel/git/davem/net-next....
Technically I think it could be built as a dynamically loadable kernel module and shipped separately from the kernel image under /lib/modules. This does not make sense if the functionality is always needed, in which case it should be statically compiled in.
In any case there is no benefit of developping separately considering that the module must call functionality from the kernel (at least for the entropy part) so the code is tightly bound to the kernel (and to specific versions of the kernel at that).
The functionality could also live in userland, and the kernel could start a process, which links the libsiphash shared library. The process could then communicate with the kernel by other means, reducing dependencies. And of course that would be too slow.
Hash functions aren't included in the kernel for exposure to userspace, they're included for internal kernel use.
edit: see e.g. this email from Linus: http://www.openwall.com/lists/kernel-hardening/2016/12/13/5
The kernel does allow for loadable modules but the point of some of these hashes is to replace calls to some md5 and sha equivalents inside the kernel itself. As a result, the symbols would need to be defined at compile time (so these functions need to be compiled in).
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.
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.
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)?
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.
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 ]
Maybe SHA-8 works fine. I don't know. I've never seen any real mathematical investigation of that, and that's the point.
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:
Which is slower than or if LE is not native: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 :)
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).
[1]: https://en.wikipedia.org/wiki/SipHash
But, in worst case they are O(n) where n is the depht of the linked list under the hood.
Hash tables have an immutable as a key of arbitrary size for which an hash is generated in a predictable way thus hash table are mainly hash => value.
Problem occurs when there are collisions of hash values. You must then follow the linked list and check on the exact value of the immutable used as a key with a complete check
If hash function is deterministic then collision can be triggered in order to create DOS slowing down the computer.
O(1) on a 400cycle operation (memory fetching) that becomes o(1024) now requires <1 000 0000> cycles on average (complete comparaison + memory fetching). You basically can turned a 2016 computer into a 1980 computer (in terms of speed)
Hash tables are used when you have sparse data structure, like caches for ephemeral ports (for a firewall) that has a fixed space bigger than memory.
A practical attack for slowing down a FW (thus making it useless) would be to use combinations of IP/port to generates colliding hashes. Hashtables are used a lot in keeping states of stuff. Like connections, sessions ....
Coincidently with python 2.7 cames the concern of predictable hash functions (basically close to CRC) that were fast to compute but predictable. Hence making a DoS easy to engineer when working with webservers (POST/GET parameters are stored in such data structures).
The python concern seems to have spread and raise awareness on the concern.
And then someone was like we need randomisation, but without side channel attack (timing) and thus, a class of hash function known as cryptographic hash function: fast to compute, hard to predict and assymmetrically hard to invert senstivite to an initial customisable parameter (called a key or secret)....
To sum up: nothing new under the sun.
Now even the kernel devs are drinking the coolaid, verbatim copying wrong claims from the SipHash authors.
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:
18-30 bit: ~4m for an attackable subset (linear time). The typical size in a kernel is 13bit.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.
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.
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.
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.
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 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.
1. Compile it:
2. Run it as root on your drive: If you can recover your data afterwards, congratulations! You should publish an academic paper! If not, then neither I nor anybody else understands your [lack of a compelling] argument.~=~=~=~=~=~=~=~=~=~=~=~=~=~=~=~=~=