From:	SMTP%"RELAY-INFO-VAX@CRVAX.SRI.COM" 31-JAN-1994 09:00:31.05
To:	EVERHART
CC:	
Subj:	RE: Password hashing algorithm

Message-Id: <9401290236.AA19605@uu3.psi.com>
Date: Fri, 28 Jan 94 21:36:48 EDT
From: Jerry Leichter <leichter@lrw.com>
To: INFO-VAX@SRI.COM
Subject: RE: Password hashing algorithm
X-Vms-Mail-To: UUCP%"ewilts@vmsmail.gov.bc.ca"

	I'm looking for documentation on a one-way password-hashing algorithm.
	We're using a product now for which the password can be decrypted and
	I'd like to point the vendor at a one-way encryption method.  Is VMS's
	Purdy algorithm documented anywhere?

There's a reference in the listings (which I don't have handy) to an article
that appeared many years ago in, I think, the Communications of the ACM.  I'm
sure someone will be able to dig up the reference.

The Unix password hashing algorithm is based on variants of DES - the "salt"
value perturbs the DES encryption tables.  I don't recall ever seeing the
exact techniques in print, though they are widely known, as Unix-style pass-
word hashing has been re-implemented in several free Unix implementations.

A technique I saw proposed many years ago, but never really fully analyzed,
works as follows.  Choose two functions p0(x) and p1(x).  Both functions
should map 32-bit (say) integers to themselves, and should be close to 1-1
functions over that range.  The functions must NOT commute (i.e., in general
we must have p0(p1(x)) != p1(p0(x))) or obey any other simple relations.  A
possible choice is p0(x) = 3x + 1 (ignoring overflows) and
p1(x) = (x ROT 5) XOR hex 30303030, where "ROT 5" rotates the bits in x 5
positions to the right.  If the input key is k, written out as bits
k31 k30 ... k0, then define

		h(k) = pk31(pk30( ... (pk0(k))...)

where pk31 means p0 if k31=0, p1 if k31=1.  Of course, reducing k to only 32
bits makes brute-force attacks too easy.  If k is, say, 64 bits - a common
size for this kind of work - you can split it into two 32 bit halves, then
do the same thing on both halves side by side, XOR'ing the value on the right
side into the left every couple of rounds, and the value on the left into the
right similarly.

Almost any hash function you define this way should be proof against even a
fairly sophisticated attack.  (Whether it will survive someone who really
applies some mathematics to it, I couldn't say.  How important is this all
to you?)

					      I should add that this routine
	will not be running on VMS (it will be Mac-based) so that I can't call
	$HASH_PASSWORD.

							-- Jerry