Subject: Re: Easy cracking From: smb@research.att.com To: Marc Horowitz <marc@GZA.COM> Cc: jim@Tadpole.COM (Jim Thompson), cypherpunks@toad.com, honey@citi.umich.edu Date: Wed, 29 Sep 93 14:32:27 EDT >> The same kind of thing happened at Sun, except with the >> secure rpc stuff. Had a guy send mail saying, "I know your >> two primes." Sun replied, "No way." (And lauged internally.) I'm not sure this is how it happened, but the person (maybe there's more than one?) who did this is a cypherpunk, who will identify himself if he wants. He also wrote a paper on this. The first version of the paper had the private key at the top of the first page, but it got removed because certain spooks got upset. ?? As far as I know, Sun's secure RPC uses Diffie-Hellman with a 192-bit modulus. LaMacchia and Odlyzko solved the discrete log problem for that size, but there's no single private key to disclose. The discrete log problem is "brittle" -- you have to do a lot of precomputation work for any particular modulus, but once you've done that work finding individual discrete logs is easy. We had received a "challenge number" from someone at Sun (i.e. they gave us g^x mod p, and we had to find x). We included both numbers in our paper. Interestingly enough, although Sun used a 192-bit prime, the comments in the source code refer to p as a 128-bit prime. Also, g=3 for the Sun RPC system, and code comments refer to g as a primitive root modulo p. But 3 isn't a primitive root modulo this particular p. We suspected that someone at Sun decided 128 bits was too short, and increased the length of the modulus to 192 (still too short) without changing the comments and verifying the primitivity of g. --bal P.S. I've put a PostScript version of the paper up for anonymous FTP, if you're interested in the details. Get the file martigny.ai.mit.edu:/pub/bal/field.ps