# RE: Re: [fw-wiz] CERT vulnerability note VU# 539363 (fwd)

**From:** Ben Nagy (*ben@iagu.net*)

**Date:** 10/19/02

**Next message:**Robert E. Martin: "[fw-wiz] httport 3snf"**Previous message:**Bill Royds: "RE: Re: [fw-wiz] CERT vulnerability note VU# 539363 (fwd)"**In reply to:**Bill Royds: "RE: Re: [fw-wiz] CERT vulnerability note VU# 539363 (fwd)"**Next in thread:**David Wagner: "Re: [fw-wiz] CERT vulnerability note VU# 539363 (fwd)"**Messages sorted by:**[ date ] [ thread ] [ subject ] [ author ] [ attachment ]

From: "Ben Nagy" <ben@iagu.net> To: "'Bill Royds'" <broyds@rogers.com>, <firewall-wizards@honor.icsalabs.com> Date: Sat Oct 19 19:05:01 2002

*> -----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

**Next message:**Robert E. Martin: "[fw-wiz] httport 3snf"**Previous message:**Bill Royds: "RE: Re: [fw-wiz] CERT vulnerability note VU# 539363 (fwd)"**In reply to:**Bill Royds: "RE: Re: [fw-wiz] CERT vulnerability note VU# 539363 (fwd)"**Next in thread:**David Wagner: "Re: [fw-wiz] CERT vulnerability note VU# 539363 (fwd)"**Messages sorted by:**[ date ] [ thread ] [ subject ] [ author ] [ attachment ]