Skip to contentSkip to conversation

cttest-0.3 (conntrack hashing)

DISCUSSION Don Cohen 4 participants 7 messages Jul 8, 2002 1 message not in the archive netfilter

lore
Share & tools
lore

A message that is not in the archive (sent off-list or not yet received): [email protected]

Don Cohen

author
#1 lore raw
Quoted 5 lines

From: Martin Josefsson <[email protected]>
The rt hash doesn't do well at all on your data. The winner on your data is crc32 which is very robust in all tests on all data it seems. It's just a shame that it's so cpu-consuming compared to the other hashes.

You're missing the main point here. I believe that crc is very easy to attack. It's clearly trivial without choosing a random initial seed.

Quoted 4 lines

From: Patrick Schaaf <[email protected]>
The abcd hash also fares very well, if we disregard the results for the (avoidable) bad bucket counts. abcd plus prime bucket counts would be as good as crc32, if I did not overlook some result.

I believe that odd is just as good as prime.

Quoted 1 line

For the abcd hash, random generation of the multipliers is also an option.

Not an option but a necessity if you want to prevent attack. Actually, recall my proposal that when a bucket overflows you choose new coefficients and rehash the whole table. I think this is also a necessity. But if you do that, then I guess it wouldn't be so bad to always start with the same coefficients - just waiting for the first attack.

Quoted 3 lines

But I'll stay undecided on the issue for some more time. We are still lacking any data from genuine web servers, and we only have a vague feeling about what an attacker may do.

Unfortunately it's way too easy to come up with new candidate functions. It's much harder to find convicing evidence that
(1) they perform well in the sense of approximating the random distribution
(2) convince yourself that they're hard to attack.
Cttest is useful for showing that (1) is NOT true, but offers only weak evidence that (1) IS true, other than for particular data. And, of course, it does not offer any evidence for (2).

My friend the crypto expert told me that crc is easy to attack, and suggested ABCD(EF) because it has the right properties to resist attack. It would take more work for me to demonstrate that crc is bad, and to better understand ABCD and possibly adjust it, but just on the basis of expert opinion, I think it's worth working on ABCD and giving up on crc and most of the others.

I welcome input from any other crypto experts out there.

#2 lore raw

Don,

Quoted 6 lines

My friend the crypto expert told me that crc is easy to attack, and suggested ABCD(EF) because it has the right properties to resist attack. It would take more work for me to demonstrate that crc is bad, and to better understand ABCD and possibly adjust it, but just on the basis of expert opinion, I think it's worth working on ABCD and giving up on crc and most of the others.

I have nothing against ABCD at this point, but I won't give up too easily on the crc thing. There could be choice, maybe in the form of an extra patch-o-matic section.

However, I agree that ABCD is generally the way to go, as far as the main kernel is concerned. However, before we start pushing any change into that general direction, I would love to A) see more pictures from different sources, and B) see you or others continue to explore attack schemes on the hashes.

To aid A) I'll probably respin cttest once or twice without diddling with any hashes, just making the report and index generation more useful for different viewpoints.

Regarding B) I personally don't have much drive to think about it. I entered this endeavour in order to understand how to choose the hash table size for some real setups where I start to use conntrack, and I'm content with what we found out.

Quoted 1 line

I welcome input from any other crypto experts out there.

Strongly seconded. I'm not a crypto expert, and I won't start playing one here on the mailing list. I'm an experimental opportunist, and I stand by that :)

best regards
Patrick

author
#3 lore raw

It turns out that your question about endianness was right on the mark. My suboptimal results were related to the fact that the more variable parts of the data were in the high bits and I was not doing a good job of causing those to influence the results.
The original idea of stuff like ans += ans >>16 was to spread the variation in the high bits to the low bits where they would affect mod 2^i for small i. The version below works better.

I assume that 32x32=>64 bit multiplication is not too expensive.

static u32 hash_conntrack(struct ct_key *key)
{
unsigned long long ls, ld, lsp, ldp, sum;
ls = (unsigned long long) key->sip * A;
ld = (unsigned long long) key->dip * B;
lsp = (unsigned long long) C * key->sport;
ldp = (unsigned long long) D * key->dport;
sum =

    (ls + (ls >> 32) +
     ld + (ld >> 32) +
     lsp + (lsp >> 32) +
     ldp + (ldp >> 32) +
     E * key->proto) ^ F;

return sum;

With the standard data -u I got these results
table size: max bucket sizes
256:167 512:88 1K:51 2K:31 4K:20 8K:13 16K:9 32K:9 64K:7 256K:4
which are pretty close to expected.

The theory is that in multiplying a 32 bit number, such as sip, by random 32 bit A, bit i of A influences bits i thru i+31 of the result. By adding (or xoring, etc) bits 32-63 to bits 0-31 we get a 32 bit result in which each bit of sip influences each bit of the result. The same thing works for 16 bit sport. Actually, if you like, you can pack sport and dport into a single 32 bit word and multiply by C (or D), which saves one multiply. I figure it hardly matters whether I do the analogous thing for proto, since it's so short.

#4 lore raw
Quoted 2 lines · Don Cohen

I figure it hardly matters whether I do the analogous thing for proto, since it's so short.

Actually you could consider proto almost a constant.. I don't think you really gain anything by obfuscating this.. just adding it to the result to make sure different protocols hash into different buckets should suffice just fine me thinks.. but sure, being paranoid does not hurt other than CPU time.. but it should be allowed to influence the hash value.

Related note: You only have sport/dport for known protocols such as TCP/UDP/ICMP. On unknown protocols (proto_generic tracking) sport/dport will be all 0, meaning there is only one single conntrack entry per sip/dip/proto tuple for such protocols..

Regards
Henrik

author
#5 lore raw
Quoted 11 lines · Henrik Nordstrom
Quoted 2 lines · Don Cohen

I figure it hardly matters whether I do the analogous thing for proto, since it's so short.

Actually you could consider proto almost a constant.. I don't think you really gain anything by obfuscating this.. just adding it to the result to make sure different protocols hash into different buckets should suffice just fine me thinks.. but sure, being paranoid does not hurt other than CPU time.. but it should be allowed to influence the hash value.

I agree it's just trying to err on the side of caution. It's nearly constant in non-attack traffic, but it's something over which the attacker has total control.
I admit I don't see how he can befefit from knowing that E=1.

Quoted 4 lines

Related note: You only have sport/dport for known protocols such as TCP/UDP/ICMP. On unknown protocols (proto_generic tracking) sport/dport will be all 0, meaning there is only one single conntrack entry per sip/dip/proto tuple for such protocols..

Ok. The attacker then does not control the port values supplied to the hash, which can only benefit us.

#6 lore raw
In reply to Don Cohen

I analyzed the part res ^= (res >> 24); res ^= (res >> 8); a little more in the rt_hash. What it really does is that it applies the hi bits in the 32bit integer on the low ones. This means that we wont just throw them away when we apply the %-operation on it. This is what keeps the good distribution. So i just added those two line to abcd (and got abcd_rt). Showed up to be very good:

http://aaricia.hemmet.chalmers.se/~gozem/cttest/0.4/

And specially:
http://aaricia.hemmet.chalmers.se/~gozem/cttest/0.4/1abcd/sizes.262143.html

The hashfunction:
static u32 hash_abcd_rt(struct ct_key *key)

{
        u32 res;

PER_HASH_TIMER_1(
res = 0x47441DFB * key->sip
+ 0x57655A7D * key->dip
+ 0x1C7F1D2D * key->sport
+ 0xDF91D738 * key->dport
+ key->proto;
res ^= (res >> 24);
res ^= (res >> 8);

);
        return res;
}

Since we wanted to try other architectures than x86 i tried to run the calculations on my school that has SUN and solaris. After much trixing with the cttest-0.4 scripts and program (since they were clearly not Solaris compatible) i managed to get some results. Without the timing of the function since that part was Linux specific. Atleast this is a test on a big-endian machine:

#uname -a
SunOS licia.dtek.chalmers.se 5.8 Generic_108528-14 sun4u sparc SUNW,Sun-Fire-280

http://www.dtek.chalmers.se/~d97gozem/cttest/0.4/

All graphs here look about equally good. I dont know if there is a bug somewhere in cttest that might do this.

Signature · 1 line
/Joakim Axelsson A.K.A Gozem@EFnet & OPN
#7 lore raw
Quoted 8 lines

big-endian machine:
#uname -a
SunOS licia.dtek.chalmers.se 5.8 Generic_108528-14 sun4u sparc SUNW,Sun-Fire-280

http://www.dtek.chalmers.se/~d97gozem/cttest/0.4/

All graphs here look about equally good. I dont know if there is a bug somewhere in cttest that might do this.

I don't think so. Thanks for the run. It seems like abcd does not show detoriation at even table sizes, on big endian systems. To confirm this, I just added ntohl/ntohs to the abcd hash, and it really comes out nicely.

Don, hope this helps your analysis.

static u32 hash_abcd_host(struct ct_key *key)

{
        u32 res;

PER_HASH_TIMER_1(
res = 0x47441DFB * ntohl(key->sip)
+ 0x57655A7D * ntohl(key->dip)
+ 0x1C7F1D2D * ntohs(key->sport)
+ 0xDF91D738 * ntohs(key->dport)
+ key->proto;

);
        return res;
}

Slightly surprising, this code runs about half as fast as the normal abcd, on my little endian box.

best regards
Patrick