From: Brian A. LaMacchia <bal@martigny.ai.mit.edu>
Date: Wed, 29 Sep 93 12:41:47 PDT
To: honey@citi.umich.edu
Subject: Re: Easy cracking
Message-ID: <9309291937.AA01203@toad.com>
MIME-Version: 1.0
Content-Type: text/plain


   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