The Sun NFS Cryptosystem

The Sun security option [39] in their NFS is built into the basic Sun Remote Procedure Call (RPC) and provides authentication of both users and machines using a combination of the Needham-Schroeder [33] protocol which uses DES, and a public key cryptosystem that is a modification of the Diffie-Hellman key exchange system [14]. It has long been known that the Sun system is not very secure. There are problems with the Needham-Schroeder protocol [13], which make it possible to defeat the timestamp system. Furthermore, the ``yellow pages'' that contain the public authentication information are not authenticated, so one can attack the security of the system by installing a bogus file. However, so far it appears that nobody has pointed out that the public key subsystem that is used by Sun is very weak. This fact makes it possible to impersonate any user with very little effort and leaving few traces.

In the Sun system, there is a prime p and an integer g that are the same for all users on all machines around the world that use this software. Each user or machine has a secret key m, and $g^m \bmod p$is public. Authentication involves proving that one possesses the key m. For details see [39].

Both the paper [39] and the comments in the software refer to pas a 128-bit prime. Actually, though,

p = 5213619424271520371687014113170182341777563603680354416779 (3)

and p has 192 bits. Both p and $\frac{p-1}{2}$ are primes. The integer g=3, and the comments in the software refer to g as being a primitive root modulo p. However, g is a quadratic residue modulo p. (This has no effect on the security of the system.) Curiously enough, 2 is a primitive root modulo p. Probably the confusion is due to the fact that originally the system was built with a 128-bit prime for which 2 was not primitive. When the length of the prime was increased, the verification of primitivity was apparently forgotten.

To break the Sun system and impersonate a user with public key x, it is only necessary to find one of the two values of m, 0 < m < p-2, such that

$$g^m \equiv x \bmod p.$$ (4)

This paper shows that this can be done very fast.