Sites with many hundreds of computers networked together often use the same set of usernames and passwords for all machines. In a typical Unix-based environment this means that one machine holds the master copy of the password file and makes the information available to the rest. For most users the only time it is necessary for their password to appear on the network `in clear' is when a new password is being set. This is a weakness that is well worth avoiding.
This paper describes a system developed jointly between Brunel and BNR which uses public-key encryption techniques to avoid exposing passwords while they are being changed. Checks on password quality are enforced, and a very fast password-file update scheme is used. The system has been in use for more than 12 months in environments with over 10,000 active users.
Netpassword was designed to meet the needs of both academic networks and industrial ones. Collaboration between Brunel and Northern Telecom's Bell Northern Research resulted in a very comprehensive requirements list.
The original motivation for this development was speed. With 7,000
registered users and 2,000 more expected, Brunel had a serious problem
as the first thing a new user is advised to do is to change their
password. The conventional
passwd command processes the
password file linearly and holds it locked for the whole operation.
It was common for the
passwd command to take two minutes
to run, with the result that many users found it impossible to change
their passwords in the first week of the academic year.
Compatibility with the installed base of heterogeneous systems was essential. This meant supporting NIS (YP) access to a conventional (non-shadow) password file. Installing Kerberos or a similar system was not an option in the available time.
Security is critical in any program handling passwords so suid operation was to be avoided and passwords were not to pass across the net `in clear'.
Password quality rules were to be enforced, and password ageing was to be supported.
Users were to be able to issue the
passwd command on any
machine on the network rather than having to logon to a particular
machine as had previously been the case. If at all possible,
password changing from DOS machines running PCNFS was to be supported.
The ability to change passwords from inside chroot
environments was considered desirable, for application on firewall
It was decided to separate the user-interface from the actual
password-changing mechanism. This allowed the
command to be an ordinary unprivileged program. The code to update the
password file thus became a network daemon.
When used by root for administrative functions, the user-interface and update mechanism are both in the same program to avoid the problem of reliably identifying the administrator across a network connection.
The main options were: TCP sockets, RPC, or ISODE ROS. RPC was chosen on the grounds that it is reasonably portable and it provides a higher level of abstraction than direct use of sockets. The TCP transport was chosen to obtain `at most once' semantics, though this choice may be reversed in a future version of the code.
Security of data on the network required encryption, and as the data volume is small it was decided to use a public-key system. This choice also simplifies the key-management issues as all clients communicate with a single server.
The Netpassword protocol was extended at BNR (who hold a PKP licence for public-key technology) to pass the arguments across the network securely using public key encryption. This allows the central password strength checks to be made even where there is a risk that the network has been compromised --- a fairly justifiable fear when the environment includes large numbers of personal computers attached to (8)802.3 networks.
The format chosen passes 2 arguments in the remote procedure call -- a number to identify the public key used, so the appropriate private key may be selected, and the cyphertext as a hexadecimal string. The hexadecimal string was readily available from Antti Louko's (email@example.com) arbitrary precision integer arithmetic library and avoids questions of byte-order when handling long numbers across the network. When decrypted the arguments are user, old password, and new password just as in the un-armoured version.
RSA encryption is expensive. On slow machines it was feared that it might be limiting. For the worst case the user is thrown into the change-password procedure by login, and there is then a total of 60 seconds to complete the password change before login kills the passwd sub-process. With netpassword this means that at least 2 encryptions and 2 decryptions must take place as well as the user input and the (remote) quality check. The algorithms used, and the shape of the exponents become crucial. For given data and platform a factor of 4 speedup is obtained by using the Chinese remainder theorem to perform the decryption.
Some tests were made using "large" (military strength) keys --- mainly to make the times longer and therefore measurement easier:
The plaintext is always 27 characters (216 bits)
* Timings : Xenix 386 / 20 Mhz gcc 1024 bit key, average 20 runs * * encrypt 0.5 sec * decrypt 80 sec (conventional) (very variable with data) * 19 sec (chinese remainder theorem) ( +- 5 sec) * 5 sec Sparc Classic (chinese remainder theorem)
The thing to note is that the encryption operation (starting from a short number) is relatively fast even on a PC, so this cost can be largely discounted in the overheads, and it is expected that a significantly more powerful machine will be used as the server.
Reducing the key length to 300 bits brings a proportional speedup.
One of the big problems with the standard
is that it reads every record in the password file, parses it, and
reconstructs it. This is very slow and for files containing several
thousand entries the performance is not acceptable.
Direct use of a DBM database was considered, as was direct
modification of the DBM file used by
options were ruled out at the time because there were other programs
in use that needed to act directly on a standard-format password file.
It was therefore necessary to find a faster way to update the flat
The master password file at Brunel had been held in ascending
UID order for some time because the
user-registration program depends on this. It was therefore decided to
use a binary-chop search algorithm to find the line to be updated and
then to re-write just the encrypted password field.
The search algorithm is complicated by the fact that there is no
quick way to find the start of each record in a file with
variable-length lines. This results in a certain amount of linear
searching from each of the chop-points, but the performance is still
very good. The file is mapped into memory using the mmap
facility, which gives a further performance improvement over the use
of seek and read. This part of the code was modified at
BNR to support the insertion of complete lines and the expansion of
`*' password fields when necessary.
root on the master machine can use the
command for several administrative functions:
Quality checks are enforced by the password-changing daemon, which also provides a service that will check the quality of a proposed password without attempting to change the existing one. The current version does not test as many cases as crack but could be extended to do so. The main checks are:
It is common in industry to require password changes on a regular
basis, typically each month. Early experiments showed that the getpwent
routines on SunOS, Xenix and HP-UX all supported the Unix
System III ageing data in the password field. More usefully the
process also had direct support, and would force the user to change
their password on login when the change criteria were met.
The thing which prevents the general deployment of ageing is that the
daemon as shipped does not support the ageing information.
NT/BNR had received an unofficial patch from SUN to handle this, so
continued support in the new scheme was essential.
The transition to Solaris is delayed by lack of cross platform support
for the Solaris ageing scheme. This is incompatible with everything
By supporting ageing a few extra rules can be enforced:
The requirement is not that passwords are never reused, simply that the cycle is of sufficient length to make it difficult for someone watching another type their password to guess that user's password in the future.
Netpassword prevents reuse by storing old passwords, encrypted with a standard key (to simplify comparison) in a file on the server. The same memory mapping techniques used in the main password changing program are also employed to search and update the used-password file. The number of stored passwords is a compile-time parameter, BNR have found a cycle of 8 passwords (corresponding to 6-10 months) to be adequate for their corporate need.
There is a hidden weakness in the simplest scheme, where only the old password is stored in the file. If the user waits for their password to be disabled, then has it reset by systems staff, they may then change that set password back to the same password they had been using. The system therefore stores both the old and the new passwords encrypted if they are not already present.
In the NT/BNR case it is impossible to limit password changes to use the
netpassword protocol. It is therefore possible for users to set poor
quality passwords by using a service which calls
such as the
change-password dialog box on the Mac Chooser when mounting unix disks.
To minimise the work required to check for poor passwords with
the encrypted passwords set with netpassword can also be stored in a
feedback file to be skipped by the crack run.
The package contains encryption procedures which would infringe PKP patents for RSA if used in the USA or certain other countries without a licence. Use within the UK is not believed to be a problem, so the source will be made available to UK organisations and PKP licencees on application to the authors.
This paper is available on the Web as