RE: Re: CERT vulnerability note VU# 539363 (fwd)

["Ben Nagy" <ben () iagu net>]

> -----Original Message-----
> From: Bill Royds [mailto:broyds () rogers com] 
> Sent: Saturday, October 19, 2002 5:57 PM
> To: Ben Nagy; firewall-wizards () honor icsalabs com
> 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-wizards () honor icsalabs com
http://honor.icsalabs.com/mailman/listinfo/firewall-wizards