*** ATTENTION *** YOU MIGHT BE ABOUT TO BE HOSED *** ATTENTION ***

This effectively changes the non-DES password algoritm.

If you have the "securedist" installed you will have no problems with this.
(Though you might want to consider using this password-encryption instead
of the DES-based if your system is likely to be hacked)

If you are running a -current system without the "securedist" installed:
YOU WILL NEED TO CHANGE ALL PASSWORDS !!    There is no backwards mode.

Suggested procedure is:
	Update your sources
	cd /usr/src/lib/libcrypt
	make clean
	make all
	make install
	passwd root
		<set roots new password>
	change password for any other users on the system.

This algorithm is expected to be much better than the traditional DES-
based algorithm.  It uses the MD5 algorithm at what it is best at, as
opposed to the DES algorithm at something it isn't good at at all.  The
algorithm is designed such that it should very hard to shortcut the
calculations needed to build a dictionary, and to make partial knowledge
(Hmm, his password starts with a 'P'...) useless.  Of course if somebody
breaks the MD5 algorithm this looses too.

The salt is 48 bits (8 char @ base64).
The encrypted password is 128 bits.

And I am positively delighted to say that it takes 34 msec to crypt() a
password on a Pentium/60Mhz, so building a dictionary is not really an
option for hackers at the moment.

2 files changed, 125 insertions, 156 deletions

diff --git a/lib/libcrypt/Makefile b/lib/libcrypt/Makefile
index 960e2fb..985f444 100644
--- a/lib/libcrypt/Makefile
+++ b/lib/libcrypt/Makefile
@@ -1,20 +1,22 @@
 #
-# $Id: Makefile,v 1.3 1994/08/12 21:12:37 csgr Exp $
+# $Id: Makefile,v 1.4 1994/08/20 18:13:59 csgr Exp $
 #
 
 LCRYPTBASE= 	libcrypt
 LCRYPTSO=	$(LCRYPTBASE).so.$(SHLIB_MAJOR).$(SHLIB_MINOR)
 
-
 LSCRYPTBASE= 	libscrypt
 LSCRYPTSO=	$(LSCRYPTBASE).so.$(SHLIB_MAJOR).$(SHLIB_MINOR)
 
 # called libscrypt - for scramble crypt!
+.PATH:	${.CURDIR}/../libmd
 LIB=	scrypt
-SRCS=	crypt.c
+SRCS=	crypt.c md5c.c
+CFLAGS+=	-I${.CURDIR}/../libmd
 
 # We only install the links if they do not already exist.
 # This may have to be revised
+
 afterinstall:
 .if !defined(NOPIC) 
 	@cd $(DESTDIR)/$(LIBDIR); \
diff --git a/lib/libcrypt/crypt.c b/lib/libcrypt/crypt.c
index d72660d..fd24e79 100644
--- a/lib/libcrypt/crypt.c
+++ b/lib/libcrypt/crypt.c
@@ -1,54 +1,42 @@
 /*
- * Copyright (c) 1989 The Regents of the University of California.
- * All rights reserved.
+ * ----------------------------------------------------------------------------
+ * "THE BEER-WARE LICENSE" (Revision 42):
+ * <phk@login.dknet.dk> wrote this file.  As long as you retain this notice you
+ * can do whatever you want with this stuff. If we meet some day, and you think
+ * this stuff is worth it, you can buy me a beer in return.   Poul-Henning Kamp
+ * ----------------------------------------------------------------------------
  *
- * This code is derived from software contributed to Berkeley by
- * Tom Truscott.
+ * $Id$
  *
- * Redistribution and use in source and binary forms, with or without
- * modification, are permitted provided that the following conditions
- * are met:
- * 1. Redistributions of source code must retain the above copyright
- *    notice, this list of conditions and the following disclaimer.
- * 2. Redistributions in binary form must reproduce the above copyright
- *    notice, this list of conditions and the following disclaimer in the
- *    documentation and/or other materials provided with the distribution.
- * 3. All advertising materials mentioning features or use of this software
- *    must display the following acknowledgement:
- *	This product includes software developed by the University of
- *	California, Berkeley and its contributors.
- * 4. Neither the name of the University nor the names of its contributors
- *    may be used to endorse or promote products derived from this software
- *    without specific prior written permission.
- *
- * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
- * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
- * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
- * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
- * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
- * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
- * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
- * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
- * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
- * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
- * SUCH DAMAGE.
  */
 
 #if defined(LIBC_SCCS) && !defined(lint)
-/* from static char sccsid[] = "@(#)crypt.c	5.11 (Berkeley) 6/25/91"; */
-static char rcsid[] = "$Header: /a/cvs/386BSD/src/lib/libc/gen/crypt.c,v 1.6 1993/08/29 22:03:56 nate Exp $";
+static char rcsid[] = "$Header$";
 #endif /* LIBC_SCCS and not lint */
 
 #include <unistd.h>
 #include <stdio.h>
+#include <md5.h>
+
+static unsigned char itoa64[] =		/* 0 ... 63 => ascii - 64 */
+	"./0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz";
+
+static void
+to64(s, v, n)
+	char *s;
+	unsigned long v;
+	int n;
+{
+	while (--n >= 0) {
+		*s++ = itoa64[v&0x3f];
+		v >>= 6;
+	}
+}
 
 /*
  * UNIX password
  * 
- * This is just a scrambler which can be used in the case when the
- * real libcrypt is not around.
- *
- * Developed by Nate Williams
+ * Use MD5 for what it is best at...
  */
 
 char *
@@ -56,129 +44,108 @@ crypt(pw, salt)
 	register const char *pw;
 	register const char *salt;
 {
-	static char     password[14];
-	long            matrix[128], *m, vector[2];
-	char            a, b, *p;
-	int             i, value;
-	unsigned short  crc;
-	unsigned long   t;
-
-	/* Ugly hack, but I'm too lazy to find the real problem - NW */
-	bzero(matrix, 128 * sizeof(long));
-
-	if (salt[0]) {
-		a = salt[0];
-		if (salt[1])
-			b = salt[1];
+	static char	*magic = "$1$";	/*
+						 * This string is magic for
+						 * this algorithm.  Having
+						 * it this way, we can get
+						 * get better later on
+						 */
+	static char     passwd[120], *p;
+	static const char *sp,*ep;
+	unsigned char	final[16];
+	int sl,pl,i,j;
+	MD5_CTX	ctx,ctx1;
+	unsigned long l;
+
+	/* Refine the Salt first */
+	sp = salt;
+
+	/* If it starts with the magic string, then skip that */
+	if(!strncmp(sp,magic,strlen(magic)))
+		sp += strlen(magic);
+
+	/* It stops at the first '$', max 8 chars */
+	for(ep=sp;*ep && *ep != '$' && ep < (sp+8);ep++)
+		continue;
+
+	/* get the length of the true salt */
+	sl = ep - sp;
+
+	MD5Init(&ctx);
+
+	/* The password first, since that is what is most unknown */
+	MD5Update(&ctx,pw,strlen(pw));
+
+	/* Then our magic string */
+	MD5Update(&ctx,magic,strlen(magic));
+
+	/* Then the raw salt */
+	MD5Update(&ctx,sp,sl);
+
+	/* Then just as many characters of the MD5(pw,salt,pw) */
+	MD5Init(&ctx1);
+	MD5Update(&ctx1,pw,strlen(pw));
+	MD5Update(&ctx1,sp,sl);
+	MD5Update(&ctx1,pw,strlen(pw));
+	MD5Final(final,&ctx1);
+	for(pl = strlen(pw); pl > 0; pl -= 16) 
+		MD5Update(&ctx,final,pl>16 ? 16 : pl);
+
+	/* Don't leave anything around in vm they could use. */
+	memset(final,0,sizeof final);
+
+	/* Then something really weird... */
+	for (j=0,i = strlen(pw); i ; i >>= 1)
+		if(i&1)
+		    MD5Update(&ctx, final+j, 1);
 		else
-			b = a;
-	} else
-		a = b = '0';
-	password[0] = a;
-	password[1] = b;
-	if (a > 'Z')
-		a -= 6;
-	if (a > '9')
-		a -= 7;
-	if (b > 'Z')
-		b -= 6;
-	if (b > '9')
-		b -= 7;
-	a -= '.';
-	b -= '.';
-	value = (a | (b << 6)) & 07777;
-
-	crc = value;
-	value += 1000;
-	b = 0;
-	p = (char *)pw;
-	while (value--) {
-		if (crc & 0x8000)
-			crc = (crc << 1) ^ 0x1021;
+		    MD5Update(&ctx, pw+j, 1);
+
+	/* Now make the output string */
+	strcpy(passwd,magic);
+	strncat(passwd,sp,sl);
+	strcat(passwd,"$");
+
+	MD5Final(final,&ctx);
+
+	/* 
+	 * and now, just to make sure things don't run too fast 
+	 * On a 60 Mhz Pentium this takes 34 msec, so you would
+	 * need 30 seconds to build a 1000 entry dictionary...
+	 */
+	for(i=0;i<1000;i++) {
+		MD5Init(&ctx1);
+		if(i & 1)
+			MD5Update(&ctx1,pw,strlen(pw));
 		else
-			crc <<= 1;
-		if (!b) {
-			b = 8;
-			if (!(i = *p++)) {
-				p = (char *)pw;
-				i = *p++;
-			}
-		}
-		if (i & 0x80)
-			crc ^= 1;
-		i <<= 1;
-		b--;
-	}
+			MD5Update(&ctx1,final,16);
 
-	m = matrix;
-	matrix[0] = 0;
-	a = 32;
-	for (value = 07777; value >= 0; value--) {
-		*m <<= 1;
-		if (crc & 0x8000) {
-			*m |= 1;
-			crc = (crc << 1) ^ 0x1021;
-		} else
-			crc <<= 1;
-		if (!b) {
-			b = 8;
-			if (!(i = *p++)) {
-				p = (char *)pw;
-				i = *p++;
-			}
-		}
-		if (i & 0x80)
-			crc ^= 1;
-		i <<= 1;
-		b--;
-		if (!(a--)) {
-			a = 32;
-			*++m = 0;
-		}
-	}
+		if(i % 3)
+			MD5Update(&ctx1,sp,sl);
 
-	vector[0] = 0;
-	vector[1] = 0;
-	p = (char *) vector;
-	for (i = 0; i < 7; i++)
-		if (pw[i])
-			*p++ = pw[i];
+		if(i % 7)
+			MD5Update(&ctx1,pw,strlen(pw));
+
+		if(i & 1)
+			MD5Update(&ctx1,final,16);
 		else
-			break;
-
-	p = password + 2;
-	a = 6;
-	m = matrix;
-	*p = 0;
-	for (i = 077; i >= 0; i--) {
-		t = *m++;
-		t = t ^ *m++;
-		t = t ^ vector[0];
-		t = t ^ vector[1];
-		b = 0;
-		while (t) {
-			if (t & 1)
-				b = 1 - b;
-			t >>= 1;
-		}
-		a--;
-		if (b)
-			*p |= 1 << a;
-		if (!a) {
-			a = 6;
-			*++p = 0;
-		}
+			MD5Update(&ctx1,pw,strlen(pw));
+		MD5Final(final,&ctx1);
 	}
 
-	for (i = 2; i < 13; i++) {
-		password[i] += '.';
-		if (password[i] > '9')
-			password[i] += 7;
-		if (password[i] > 'Z')
-			password[i] += 6;
-	}
-	password[13] = 0;
+	p = passwd + strlen(passwd);
+	
+	l = (final[ 0]<<16) | (final[ 6]<<8) | final[12]; to64(p,l,4); p += 4;
+	l = (final[ 1]<<16) | (final[ 7]<<8) | final[13]; to64(p,l,4); p += 4;
+	l = (final[ 2]<<16) | (final[ 8]<<8) | final[14]; to64(p,l,4); p += 4;
+	l = (final[ 3]<<16) | (final[ 9]<<8) | final[15]; to64(p,l,4); p += 4;
+	l = (final[ 4]<<16) | (final[10]<<8) | final[ 5]; to64(p,l,4); p += 4;
+	l =                    final[11]                ; to64(p,l,2); p += 2;
+	*p = '\0';
+
+	/* Don't leave anything around in vm they could use. */
+	memset(final,0,sizeof final);
 
-	return password;
+	return passwd;
 }