> -----Original Message----- > From: Bill Royds [mailto:broydsat_private] > Sent: Saturday, October 19, 2002 5:57 PM > To: Ben Nagy; firewall-wizardsat_private > Subject: RE: Re: [fw-wiz] CERT vulnerability note VU# 539363 (fwd) > > > You are mixing up two meanings of the word hash. You're right. It was a knee-jerk response. Whups. I'm a jackass. > What is used in table lookup is the meaning used in Perl ( > take a key, do a mathematical transformation on it to get a > direct index into a table), rather than the meaning used in > cryptography (take a string, do a mathematical transform on > it to form a unique signature for the string). They both take > strings, treat them as big numbers, then reduce them to a > smaller number, so they follow the mathematical idea of hash. [...] > For most modern computers, table size as a power of 2 > allows shifts rather than division so Mersenne primes (1 more > than a power of 2 that is prime) are used often as a base for > this kind of hash. But, as you say, since there are > relatively few Mersenne primes and they are well known, it is > not a good idea when you are trying to prevent hash > collision attacks. OK. So, as David said, just use a keyed hash and then you can get your Mersenne prime efficiency as well as much lower attackability. (This may be dumb, again, but if your index-hash algorithm is just to mod the state tuple with a mersenne prime then you could just XOR with a secret number, yeah? I'm sure it's crypto-bad, but it's a lot faster than using a "real" keyed hash, and seems hard to attack.) [...] > If you don't know which prime is used for a base of the > table, it is hard to guess which exact one is used. As Euclid > showed 2500 years ago, there are an infinite number of primes to try. Yeah, but the attacker knows that the prime isn't too big (or else the string may as well be its own index) and it isn't too small (or you have lots of collisions). I'd guess that unless you're dealing with systems that have massive state tables then if you're using your "string mod someprime" alg then it's not actually that hard to guess your prime, assuming that you want efficient table lookups. Cheers, -- Ben Nagy Network Security Specialist Mb: +41792504687 PGP Key ID: 0x1A86E304 _______________________________________________ firewall-wizards mailing list firewall-wizardsat_private http://honor.icsalabs.com/mailman/listinfo/firewall-wizards
This archive was generated by hypermail 2b30 : Sat Oct 19 2002 - 16:21:46 PDT