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

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

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