RFC: A UNIX crypt(3) replacement

I'm trying to think of a function to replace UNIX's crypt(3).  
My design criteria are as follows:

	1) I want it to be secure.
	2) I would like to use a cryptographic hash.
	3) I would like to use well understood cryptographic primitives.
	4) I would like to use a salt, and I would like the salt to be
	considerably larger than the current salt.
	5) I would like the process to be able to be more computationally
	intensive than crypt(3).
	6) The ability to use the algorithm in any setting domestic (US)
	and abroad is a concern, but not a primary one.

	#1 is important for the obvious reasons.
	#2 is important because a one way hash allows for a secure way of
checking the original password against the entered password.  No password
should be able to be recovered by simply reading a file, or finding an
internal key.
	#3 is basicly a result of #1
	#4 and 5 makes the password system more resistant to a dictionary-
type attack.  Several of the more popular password guessers (ie: Crack)
get a significant speed increase from the fact that they only have to hash 
each of the words once per salt.  I would like it to be possible for each
user to have an independent salt (for any reasonable system size).  I would
also like this function to be able to be scaled to that it can be slower
than crypt(3).  This will also hinder a dictionary attack.
	#6 is a byproduct of silly legal concerns.

The algorithm that I developed was heavily influenced by RFCs 1852 [1] 
and 1828 [2] (IP Authentication using SHA and MD5, respectively), and 
"Keying Hash Functions for Message Authentication" by Mihir Bellare, 
Ran Canetti, and Hugo Krawczyk [3]

This algorithm borrows several concepts from [3]:
	The idea of the keyed hash, where the key is used as the hash's 
	IV, or Initial Value. Its security is completely based on the
	choice of the key, and the strength of the underlying hash
	function.

	The concept of the NMAC (Nested MAC), and security analysis
	of it.


The Algorithm:

Given that:
. = the concatenation operator
P = the user pass phrase
H(m) = the hash of the message m
l = length of the hash returned by H(m)
H(k,m) = the keyed hash of message m, using key k (as the IV)
N = salt, length l = (n1 . n2) where n1 and n2 are sub-salts
i = the iteration number
E = a temporary value = (e1 . e2)
K = key = (k1,k2), where k1 and k2 are the sub-keys used in the NMAC
NMAC(k, m) = H(k1, H(k2, m))

In several cases a value is said to be equal to the concatenation
of two other values (we'll take N as an example); ie 
N = (n1 . n2)
This means that N is divided into two equal sized chunks, n1 and n2.
(n1 . n2) = N

initially:
(1) E = H (P)
(2) k1 = (e1 . n1), k2 = (e2 . n2)
(3) T0 = NMAC(K, n)

And then:
(4) T(i) = NMAC(K, T(i-1) . n . T(i-1))
(repeat (4) a number of times)

In (1) the user pass phrase is hashed using the non keyed hash, and the 
resulting value is kept in E. 

In (2) k1 is formed by concatenating the first half of E and the
first half of the salt.  k2 is formed by concatenating the second
half of the key with the second half of the salt.  Now each sub-key
is of length l.

In (3) the NMAC of n is assigned to T0

and then in (4) T(i) is calculated by doing the NMAC of the value
of the previous hash concatenated with n concatenated with the value
the previous hash.

Step (4) is repeated a known number of iterations.

"Keying Hash Functions..." [3] seems to imply that the security of this
hash would be based on the length of l and the underlying hash function, H.  
Because of the way that K is used, the security granted is a function 
of l/2, not l.  (For further explanation see [3])

I was thinking of implementing this using SHA-1.  
This would lead to a 160 bit value for l, hence the security would be 
based on an 80 bit key.

Some modifications that I have considered, and would like feedback on
are:

I was thinking of making the keys used for the hash come from the
previous hashes, and then hash a constant string.  ie:
T(i) = NMAC(T(i-2) . T(i-1), P . n . P)
instead of having a more-or-less constant key, and constantly changing
what is being hashed.

I also am not sure that the string that I'm hashing is ideal.  
Would (n . P . n ) be better?

- -------------------------------------------------------------------------
[1] Metzger, P. and Simpson, W. "Request for Comments: 1852, 
	IP Authentication using Keyed SHA"

[2] Metzger, P. and Simpson, W. "Request for Comments: 1828,
	IP Authentication using Keyed MD5"

[3] Bellare, Mihir and Canetti, Ran and Krawczyk, Hugo. "Keying
	Hash Functions for Message Authentication"

I very much appreciate comments on any portion of this, or on my general
approach.
			Thanks,
			Joshua


-----------------------------Joshua E. Hill-----------------------------
|   If you not part of the solution, you're part of the precipitate    |
-------jehill@<gauss.elee|galaxy.csc|w6bhz|tuba.aix>.calpoly.edu--------

On Sat, 16 Nov 1996, Joshua E. Hill wrote:

> 
> 	I'm trying to think of a function to replace UNIX's crypt(3).  
> My design criteria are as follows:
> 

Why? UNIX passwords with password shadowing are as secure as any password
system is going to get.  If your security holes are with passwords, its
because your admin is to lazy to install needed security provissions, not
because the system of checking passwords is bad.

If you're worried about network sniffing and the like, get SSH.  Other
than that you're wasting your time.

 --Deviant
Without followers, evil cannot spread.
                -- Spock, "And The Children Shall Lead", stardate 5029.5

The Deviant wrote:
| On Sat, 16 Nov 1996, Joshua E. Hill wrote:
| > 	I'm trying to think of a function to replace UNIX's crypt(3).  
| > My design criteria are as follows:

| Why? UNIX passwords with password shadowing are as secure as any password
| system is going to get.  If your security holes are with passwords, its
| because your admin is to lazy to install needed security provissions, not
| because the system of checking passwords is bad.

	A longer salt would make running crack against a large
password file slower.

Adam

-- 
"It is seldom that liberty of any kind is lost all at once."
					               -Hume

On Sun, 17 Nov 1996, Adam Shostack wrote:

> The Deviant wrote:
> | On Sat, 16 Nov 1996, Joshua E. Hill wrote:
> | > 	I'm trying to think of a function to replace UNIX's crypt(3).  
> | > My design criteria are as follows:
> 
> | Why? UNIX passwords with password shadowing are as secure as any password
> | system is going to get.  If your security holes are with passwords, its
> | because your admin is to lazy to install needed security provissions, not
> | because the system of checking passwords is bad.
> 
> 	A longer salt would make running crack against a large
> password file slower.

While thats all well and good, it shouldn't be necisary.  If passwords are
shadowed, one must have root access before one can run crack against the
password list, at which time it is innefective.

> 
> Adam
> 
> -- 
> "It is seldom that liberty of any kind is lost all at once."
> 					               -Hume

Nice sig... I think I'll add it to my list...

 --Deviant
"First things first -- but not necessarily in that order"
                -- The Doctor, "Doctor Who"

Unless you're running yp, or if your wu-ftpd leaves a core
with the password entries still in memory, or sendmail can be used to
read any file on the system...

	Belt *and* suspenders, and a lot more simplicity than wu-ftpd
or sendmail offers you.

Adam
The Deviant wrote:
| On Sun, 17 Nov 1996, Adam Shostack wrote:
| > The Deviant wrote:
| > | On Sat, 16 Nov 1996, Joshua E. Hill wrote:
| > | > 	I'm trying to think of a function to replace UNIX's crypt(3).  
| > | > My design criteria are as follows:
| > 
| > | Why? UNIX passwords with password shadowing are as secure as any password
| > | system is going to get.  If your security holes are with passwords, its
| > | because your admin is to lazy to install needed security provissions, not
| > | because the system of checking passwords is bad.
| > 
| > 	A longer salt would make running crack against a large
| > password file slower.
| 
| While thats all well and good, it shouldn't be necisary.  If passwords are
| shadowed, one must have root access before one can run crack against the
| password list, at which time it is innefective.


-- 
"It is seldom that liberty of any kind is lost all at once."
					               -Hume

On Sun, 17 Nov 1996, The Deviant wrote:

> On Sun, 17 Nov 1996, Adam Shostack wrote:
> > 	A longer salt would make running crack against a large
> > password file slower.
> 
> While thats all well and good, it shouldn't be necisary.  If passwords are
> shadowed, one must have root access before one can run crack against the
> password list, at which time it is innefective.

I couldn't disagree more (not that I necessarily agree or disagree with
Adam's approach). Sure, once you have root you don't need any other
access, until the hole is found and closed that gave root in the first
place. After that, that /etc/shadow file with the lousy passwords (that
seem inevitable with folks using /etc/shadow as they get complacent
with a false sense of security) provide the would-be cracker with a set
of local accounts to (try to) break in again. Local accounts are
definitely an advantage should you be looking for way to break any Unix
variant.

The moral of the story is: ALWAYS ensure that whatever passwords you
have on your unix system are not beatable by crack, don't rely upon
hiding them because if you are wrong you are in it up to your neck!

cheers, kinch

On Sun, 17 Nov 1996, Dave Kinchlea wrote:

> On Sun, 17 Nov 1996, The Deviant wrote:
> 
> > On Sun, 17 Nov 1996, Adam Shostack wrote:
> > > 	A longer salt would make running crack against a large
> > > password file slower.
> > 
> > While thats all well and good, it shouldn't be necisary.  If passwords are
> > shadowed, one must have root access before one can run crack against the
> > password list, at which time it is innefective.
> 
> I couldn't disagree more (not that I necessarily agree or disagree with
> Adam's approach). Sure, once you have root you don't need any other
> access, until the hole is found and closed that gave root in the first
> place. After that, that /etc/shadow file with the lousy passwords (that
> seem inevitable with folks using /etc/shadow as they get complacent
> with a false sense of security) provide the would-be cracker with a set
> of local accounts to (try to) break in again. Local accounts are
> definitely an advantage should you be looking for way to break any Unix
> variant.
> 
> The moral of the story is: ALWAYS ensure that whatever passwords you
> have on your unix system are not beatable by crack, don't rely upon
> hiding them because if you are wrong you are in it up to your neck!
> 
> cheers, kinch
> 

Oh.. you misunderstand what I'm saying... I'm not saying its unemportant
for you to have good passwords or anything like that, I'm just pointing
out that rather than replace the entire system, its more prudent to fully
install it.

I still think admins should run crack against their own lists, etc., but
that still shouldn't be a problem to a good cracker.  If you've just
gotten root on a system, you start backdooring everything, not trying to
crack the password list.

 --Deviant
Even God cannot change the past.
                -- Joseph Stalin

On Sun, 17 Nov 1996, The Deviant wrote:
> 
> Oh.. you misunderstand what I'm saying... I'm not saying its unemportant
> for you to have good passwords or anything like that, I'm just pointing
> out that rather than replace the entire system, its more prudent to fully
> install it.
> 
> I still think admins should run crack against their own lists, etc., but
> that still shouldn't be a problem to a good cracker.  If you've just
> gotten root on a system, you start backdooring everything, not trying to
> crack the password list.

Well, this certainly *IS* a different statement than I read from you
before. I don't find anything to disagree with here. Though, if your
passwords can't be cracked, what is the need for shadow passwords? It
simply introduces more variables and offers no more security.

cheers

On Sun, 17 Nov 1996, Dave Kinchlea wrote:

> On Sun, 17 Nov 1996, The Deviant wrote:
> > 
> > Oh.. you misunderstand what I'm saying... I'm not saying its unemportant
> > for you to have good passwords or anything like that, I'm just pointing
> > out that rather than replace the entire system, its more prudent to fully
> > install it.
> > 
> > I still think admins should run crack against their own lists, etc., but
> > that still shouldn't be a problem to a good cracker.  If you've just
> > gotten root on a system, you start backdooring everything, not trying to
> > crack the password list.
> 
> Well, this certainly *IS* a different statement than I read from you
> before. I don't find anything to disagree with here. Though, if your
> passwords can't be cracked, what is the need for shadow passwords? It
> simply introduces more variables and offers no more security.

While thats all well and good, its also easier said than done.  A creative
cracker can beat a lot of password filter routines.  As somebody said to
me earlier, belt _and_ suspenders works best. ;)

 --Deviant
Blood flows down one leg and up the other.

On Sun, 17 Nov 1996, The Deviant wrote:
> > 
> > Well, this certainly *IS* a different statement than I read from you
> > before. I don't find anything to disagree with here. Though, if your
> > passwords can't be cracked, what is the need for shadow passwords? It
> > simply introduces more variables and offers no more security.
> 
> While thats all well and good, its also easier said than done.  A creative
> cracker can beat a lot of password filter routines.  As somebody said to
> me earlier, belt _and_ suspenders works best. ;)

Agreed, for a large number of users (say >1,000) it is quite difficult
for one thing, running crack can be too time consuming to be feasible. 
For a small number of users (many of the LANs I administer have less
than 30 users), however, it is not at all difficult. It helps, of
course, if you can trust your local users --- possible when there are
only a few and you know them all, impossible when there are many and
they are faceless. 

The less work I have to do to keep the systems/network secure, the more
time I can make available for *real* work on those system. Few sites can
afford a full-time security person, that is the reality that I live in
anyway. 

cheers, kinch