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

["Bill Royds" <broyds () rogers com>]

You are mixing up two meanings of the word hash.
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. 
  But the Perl meaning is  what is used in state table lookup, not the security signature meaning.
  The idea behind the primes is that dividing a big number (the key) by a prime and taking the remainder, will give an 
direct index into a table with number of elements equal to the prime. This is used as an array index, speeding up the 
lookup.
  There may be more than one key hashing into the same index (a hash collision), so a resolution mechanism is also 
employed that is often a linear search among entries with same hash index, but primes make this less likely than other 
table sizes.
  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.

The whole idea behind RSA public key is to find two primes such that using their product as a modulo base for keys. 
Given the product, it is very difficult to find the two primes that are combined.
  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.

-----Original Message-----
From: firewall-wizards-admin () honor icsalabs com
[mailto:firewall-wizards-admin () honor icsalabs com]On Behalf Of Ben Nagy
Sent: Sat October 19 2002 06:49
To: broyds () rogers com; firewall-wizards () honor icsalabs com
Subject: RE: Re: [fw-wiz] CERT vulnerability note VU# 539363 (fwd)


> -----Original Message-----
> From: firewall-wizards-admin () honor icsalabs com 
> [mailto:firewall-wizards-admin () honor icsalabs com] On Behalf 
> Of broyds () rogers com
> Sent: Friday, October 18, 2002 6:04 PM
> To: Miles Sabin; firewall-wizards () honor icsalabs com
> Subject: Re: Re: [fw-wiz] CERT vulnerability note VU# 539363 (fwd)
>
>
> Most hash functions are based on arithmetic modulo a large 
> prime.

Um...

I'm most familiar with the "big" ones, namely MD4, 5 and SHA-1. [1] [2].
They're not.

(You may be thinking of public key crypto)

> Most often this prime is chosen to be close to a power 
> of 2 to optimize address space (often a Mersenne prime), but 
> there is not neccessity for it so the secret would be the 
> prime used as hash base. Guessing prime used is non trivial 
> so it provides some security.

Guessing primes is actually quite easy. Mersenne primes even more so
(not to mention that the mersenne primes are sparse enough to use a
lookup table - there are less than 40 of them). I'm an idiot and can't
code, but even I've written a perl program that uses primes to find
perfect numbers (and thus also finds mersenne primes) which was pretty
fast. The maths is kind of fun. Here's a random reference, but there are
many more [3]. (I used a pre-made list of generator primes to build the
Mersenne numbers, checked for primality with Lucas-Lehmer and then the
relevant perfect number is found at the same time.)

The problem in cryptographic systems that use "arithmetic modulo a large
prime" is usually the discrete logarithm problem. In fact, in many
systems the large prime is specified as part of the standard and isn't
secret at all. See, for example, the way Diffie-Hellman is used in IPSec
IKE. [4]

Back to the cryptographic salt mines for you![5]

Cheers,

[1] SHA, here: http://www.itl.nist.gov/fipspubs/fip180-1.htm
[2] MD5, here: http://www.ietf.org/rfc/rfc1321.txt?number=1321
[3] Perfect Numbers:
http://pw1.netcom.com/~hjsmith/Perfect/Mersenne.html
[4] IKE / DH : http://www.ietf.org/rfc/rfc2409.txt
[5] Is this a "perfect" pun?
--
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

_______________________________________________
firewall-wizards mailing list
firewall-wizards () honor icsalabs com
http://honor.icsalabs.com/mailman/listinfo/firewall-wizards