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-adminat_private [mailto:firewall-wizards-adminat_private]On Behalf Of Ben Nagy Sent: Sat October 19 2002 06:49 To: broydsat_private; firewall-wizardsat_private Subject: RE: Re: [fw-wiz] CERT vulnerability note VU# 539363 (fwd) > -----Original Message----- > From: firewall-wizards-adminat_private > [mailto:firewall-wizards-adminat_private] On Behalf > Of broydsat_private > Sent: Friday, October 18, 2002 6:04 PM > To: Miles Sabin; firewall-wizardsat_private > 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-wizardsat_private http://honor.icsalabs.com/mailman/listinfo/firewall-wizards _______________________________________________ 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 - 09:12:52 PDT