conntrack performance/DoS formula
A message that is not in the archive (sent off-list or not yet received): [email protected]
Quoted 8 lines · Patrick Schaaf
Quoted 4 lines
You can now use '-c NUMBER' to set a seed for the CRC32 hash. You can now use '-C' (without parameter) to set a random seed for the CRC32 hash. These options are for testing the idea of "attack compensation by inserting local variance". I'd like to hear opinions on this.
At a higher level, though, I don't see much value in preventing an attacker from filling a single bucket when he can almost as easily do much more harm by filling the entire conntrack database!
On the other hand, if we do have a way to prevent an attacker from filling the conntrack database, this does become interesting again. Assuming, of course, the attacker can't skew the crc hash results by feeding you particular data without knowing your seed. I still hope to hear from some experts out there on this subject.
And now, since I think this is a useful approach it's worth while to mention the following:
static u32 hash_crc32(struct ct_key *key)
{
u32 crc = crc32_seed;
u32 v32;
u16 v16;
crc = crc32(crc, (const char *) &key->proto, sizeof(key->proto));
v32 = ntohl(key->sip);
crc = crc32(crc, (const char *) &v32, sizeof(v32));
v32 = ntohl(key->dip);
crc = crc32(crc, (const char *) &v32, sizeof(v32));
v16 = ntohs(key->sport);
crc = crc32(crc, (const char *) &v16, sizeof(v16));
v16 = ntohs(key->dport);
crc = crc32(crc, (const char *) &v16, sizeof(v16));
return crc;}
Isn't that the same (modulo order of data) as this?
return crc32(crc, (const char *) key, sizeof(struct ct_key));
On my 200MHz machine
your crc my change hash_conntrack 1.5usec 1.1usec .2usec gcc -o cttest cttest.c 1.1usec .53usec .14usec gcc -O9 -o cttest cttest.c
Hi Don,
Quoted 2 lines
And now, since I think this is a useful approach it's worth while to mention the following:
I'm doing some gnuplot pictures right now, and crc32 really does come out as preferrable regarding list length distributions for varying bucket sizes. I'll post a link to a presentation of that analysis later today.
[regarding the hash_crc32() in my test program]
Quoted 3 lines
Isn't that the same (modulo order of data) as this?
return crc32(crc, (const char *) key, sizeof(struct ct_key));
The problem with this is not so much order of data, which would be the same for all calls on a local machine (i.e. at least consistent). The problem is possible padding in the structure. While such padding in the real in-kernel tuple data structure would be space wastage, it _is_ possible in principle for a C compiler to introduce such padding.
Quoted 4 lines
On my 200MHz machine
your crc my change hash_conntrack 1.5usec 1.1usec .2usec gcc -o cttest cttest.c 1.1usec .53usec .14usec gcc -O9 -o cttest cttest.c
I'm sure that there's much more speed to be had over the crc32() function I borrowed from zlibc. That one is a general N-byte crc32, and here we always have a fixed amount of bytes. Thus, for production, we would look into completely unrolling the crc32 loop. I'll look into microoptimizating this if and only if it is decided to have crc32 as a (possibly alternative) hash function for conntrack. It's not worth the effort for the test program alone.
Thanks nevertheless for bringing this up; it is an important issue when we want to deploy crc32.
best regards
Patrick
Re: conntrack performance/DoS formula -- answer
In reply to a message not in the archiveThe answer from my friendly crypto expert:
Quoted 52 lines · Richard Schroeppel
Quoted 1 line
Problem: a firewall tries to track "connections" going through it
(roughly identified by ip addresses and ports of source and destination) by keeping the currently active connections in a hash table. If the hashing algorithm is something simple and well known, such as
bucket index = srcip+destip+srcport+destport mod tablesize and each bucket contains a list of entries
then an attacker can send data that creates very long lists in very few buckets, i.e., you might as well not have a hash table. And this makes the firewall spend all its time searching the table.One suggestion was to change the hash function above to crc where you start with a seed that is known only to the firewall (chosen randomly at startup). The question is whether the attacker can still send data that causes the table to differ significantly from the result of a uniform hash. I don't know enough about crc and hope you know more. The real question is what's a cheap computation that can't be attacked in this way. Crc is already significantly more expensive than +/mod above.
A cheap trick: At boot time, the firewall makes up 4 private 32-bit random odd numbers A,B,C,D.
The new formula for the bucket index is
A*srcip + B*destip + C*srcport + D*destport
masked with 0x7fff...fff to make it positive, then continue with mod tablesize. I suggest tablesize be prime, or at least odd. Also, it shouldn't divide ABCD, and even better has no common factor with ABCD.This scheme can be broken by a determined attack, if the attacker can figure out (probably any one of) A,B,C,D.
He might do this by timing firewall activity based on his inputs, if the timing data is available to high enough resolution. My guess is that the timing data isn't available, and would be obscured by normal traffic, but maybe in the middle of the night he could get something to work.As a last resort defense, if the firewall detects such an attack, due to hash bucket overflow, it could try to cope by splitting the bucket based on a secondary hash with other coefficients, and/or early expiration of random bucket entries.
Or, if an attack is noticed, choose a new random A'B'C'D', and rehash the old table, or rebuild a new table from scratch.If you use the CRC scheme and the attacker knows some details of the CRC, he can cause some bucket overflow. The scheme matters. In some cases, the starting seed would be irrelevant, affecting only which bucket got the overflow.
If multiply is too costly, you get nearly the same effect by creating a random table at boot with maybe 256*10 entries, and adding up Table[srcip-leftmost-byte] etc. But the Pentium multiplier is pretty fast, maybe faster than memory access.