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
participants (4)
-
Adam Shostack -
Dave Kinchlea -
Joshua E. Hill -
The Deviant