agb@cscosl.ncsu.edu (Alan Bishop) (12/15/89)
Howdy. I'm interested in finding some figures for the speed of crypt(3). My goal is to get some numbers on how long it would take to encrypt a list of likely passwords (such as the words in /usr/dict/words) and how long it would take intruders run every userid on a system through crypt(3) with the appropriate salt. First, what kind of speed can I expect to find with the distributed form of crypt(3) on machines that most universities would have or have access to? For example, on a lightly loaded uVAX II, running 10 words through crypt takes around 12 seconds. This comes out to around 8 hours to run /usr/dict/words (~25000 words) through it with a given salt. Second, are there 'improved' versions of crypt(3) floating around? If so, what kind of speed improvements do they show? How widely distributed are they? (Should we assume that anyone trying to break into our systems has a faster version, or just a small percentage of them?) Third, what kind of speed can you get with a hardware implementation of crypt(3)? Who has done this and how difficult is it? Lastly, can you mail me a list of any references you have about the speed of crypt(3) or crypt look-alikes? Thanks. alan
trt@rti.UUCP (Thomas Truscott) (12/28/89)
> First, what kind of speed can I expect to find with the distributed > form of crypt(3) on machines that most universities would have or have > access to? The standard crypt(3) encrypts about 2 passwords/MIP. Of course this depends heavily on the machine architecture and compiler. I don't know of any vendors that ship a sped-up crypt(3). > Second, are there 'improved' versions of crypt(3) floating around? The fast crypt in the Internet Worm floated around for a while! The fastest crypt(3) I know of was described in Crypto '89 in the paper "A High-Speed Crypt Implementation" by David C Feldmeier. It can encrypt nearly 1100 passwords/second on a DECstation 3100. (The standard crypt does about 19 passwords/second.) Contact dcf@thumper.bellcore.com for more info. I have a version of crypt(3) derived from Bob Baldwin's "fdes" program that does about 600 passwords/second on the DECstation 3100. It is the fastest "practical" version of crypt(3) I know of (i.e. one can simply "cp crypt.c /usr/src/lib/libc/gen/crypt.c" to replace the standard version). I have sent copies of this version to several people (including the BSD 4.x folks) but am reluctant to post it to Usenet because of the "export restrictions" nonsense. An article by Matt Bishop in the Usenix "Computing Systems" journal (vol. 1 number 3 1988 I think) described a fast password encryptor and compared it with others. > Third, what kind of speed can you get with a hardware implementation of > crypt(3)? Who has done this and how difficult is it? crypt(3) uses DES which is slow in software and fast in hardware. And the hardware is cheap so it can be replicated. Using hardware to find DES keys by exhaustive search is easily within the budget of major governments. So crypt(3) is similarly vulnerable. I don't know of anyone working on hardware crypt(3) though. They work on hardware DES instead. Tom Truscott
norstar@tnl.UUCP (Daniel Ray) (12/31/89)
In article <3364@rti.UUCP>, trt@rti.UUCP (Thomas Truscott) writes:
...
crypt(3) uses DES which is slow in software and fast in hardware.
And the hardware is cheap so it can be replicated.
Using hardware to find DES keys by exhaustive search is easily
within the budget of major governments.
...
I wonder what is the chance that the NSA has a complete database of all
possible /etc/passwd encrypted strings, for all 4098 salts... I'll just
bet they can look up any password, in a few microseconds!
The key to password security (assuming we stay with a crypt(3)-type
hashing scheme with shorter length passwords) seems to be having a unique
scheme for each machine. When a new UNIX system is installed, it could
use its own key (instead of always the string of nulls crypt(3) uses), then
link the login/su/passwd programs on the spot with that site's specific
configuration. This would make your crypt(3) work differently from my
crypt(3). Many more possibilities, much harder to crack outside your own
site. Same should apply to the shadow scheme. Each site uses a different
secret passwd file, a different directory and path each time. An intruder
wouldn't know where to look for the encrypted strings. That's what we do
here on TNL. Just as the proliferation of viruses is hindered by the
variation of operating environments, so can breaking a password system
be blocked by site-specific implementations.
norstar
The Northern Lights, Burlington Vermont |
tnl dialins: 802-865-3614 at 300-2400 bps. ` | /
------------------------------------------ --- * ---
uucp: uunet!uvm-gen!tnl!norstar or / | .
{decvax,linus}!dartvax!uvm-gen!tnl!norstar | gwyn@smoke.BRL.MIL (Doug Gwyn) (01/05/90)
In article <235@tnl.UUCP> norstar@tnl.UUCP (Daniel Ray) writes: >The key to password security (assuming we stay with a crypt(3)-type >hashing scheme with shorter length passwords) seems to be having a unique >scheme for each machine. No, a much simpler and better solution is to keep the encrypted passwords unreadable (except of course to specific privileged programs that perform password validation etc.).
norstar@tnl.UUCP (Daniel Ray) (01/07/90)
In article <11885@smoke.BRL.MIL>, gwyn@smoke.BRL.MIL (Doug Gwyn) writes: > In article <235@tnl.UUCP> norstar@tnl.UUCP (Daniel Ray) writes: > >The key to password security (assuming we stay with a crypt(3)-type > >hashing scheme with shorter length passwords) seems to be having a unique > >scheme for each machine. > > No, a much simpler and better solution is to keep the encrypted > passwords unreadable (except of course to specific privileged > programs that perform password validation etc.). what I meant was that BOTH a unique crypt() function AND an unreadable password file are good ideas. Hopefully the shadow (or other) unreadable password file, containing the encrypted strings, will suffice. If, however, a user manages to get a copy of the password file, then he/she may still be stopped if the crypt() algorithm is unique to that machine. Security may be best if it is not too standardized. Individual quirks and modifications will inhibit generalized sweeps for defects or holes. A cracker will have to struggle if the target machine is different from the norm. Viruses and worms (such as the Morris internet worm) won't work if the assumptions are wrong for that machine. A BUILT-IN mechanism for machine individualization can go a long way towards increasing the time necessary to break security. This theme is what nature herself uses to insure survival. While one organism may succumb to a new disease, another, because it is different, will remain immune. Long live survival through variation! norstar The Northern Lights, Burlington Vermont | The first rule tnl dialins: 802-865-3614 at 300-2400 bps. ` | / of security is ------------------------------------------ --- * --- that there IS NO uucp: uunet!uvm-gen!tnl!norstar or / | . security... {decvax,linus}!dartvax!uvm-gen!tnl!norstar |