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

From: Ben Nagy (
Date: 10/19/02

From: "Ben Nagy" <>
To: "'Bill Royds'" <>, <>
Date: Sat Oct 19 19:05:01 2002

> -----Original Message-----
> From: Bill Royds []
> Sent: Saturday, October 19, 2002 5:57 PM
> To: Ben Nagy;
> 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.


Ben Nagy
Network Security Specialist
Mb: +41792504687  PGP Key ID: 0x1A86E304  

Relevant Pages

  • Re: How to write a diff in VB6 for comparing two xml files?
    ... No, the best you could do is to read both into string and use StrCompbut it's inefficient and, but using the hash ... Private Declare Function CryptAcquireContext Lib "AdvAPI32.dll" Alias _ ... Dim HashAAs Byte, HashLenA As Long ...
  • Re: something like switch in c
    ... >> straightforward string comparisions. ... > inner table size and/or add symbols to expand the hash. ... It all depends on the empirical pattern of the actual keys. ... The value of the random number generator is UNCHANGED on ...
  • Re: How to make PKCS#7 signature using CryptoAPI?
    ... Those MSDN samples hash a string PLUS the null byte (so that it ... I tried your sample and had no problem verifying with openssl (after I added ... functions (including CryptSignMessage). ...
  • Re: How to make PKCS#7 signature using CryptoAPI?
    ... "Mitch Gallant" wrote: ... Those MSDN samples hash a string PLUS the null byte (so that it ... functions (including CryptSignMessage). ...
  • Re: Base36
    ... static string tokens = ... But - I don't think you want all those silly characters in the product key. ... I should be able to recalc the hash at the client ... > conversion to long so I can pass each long to the BaseXX converter to get ...