Openwall GNU/*/Linux - a small security-enhanced Linux distro for servers
[<prev] [next>] [thread-next>] [day] [month] [year] [list]
Date: Sat, 10 Nov 2007 16:37:24 +0200
From: "Marti Raudsepp" <marti@...fo.org>
To: "John users list" <john-users@...ts.openwall.com>
Subject: [PATCH] mysqlSHA1_fmt.c: SSE2-enabled MySQL 4.1+ hash cracker

Hi,

The attached patch implements the *new* PASSWORD() hash cracker for
MySQL versions 4.1 and newer.

I've tested it with linux-x86-64, linux-x86-64-32-sse2 and
linux-x86-64-32-mmx and it seems to work for me, though I can give no
warranties for the MMX/SSE-accelerated versions because the shammx
assembly code is totally undocumented.

The SSE2 version performs around 11k c/s on my 1.8GHz Core 2 laptop,
and 7k c/s on Athlon 64 3000+. If this is not enough for you, the
mysqlsha1_set_key routine (inherited from rawSHA1) can really use some
improvements. :)

If you want to try the cracker, use the _attached_ patch.
The following diff lists the changes between rawSHA1 and mysqlSHA1,
for anyone who's interested. Note that I use different indentation
than the original author so this diff will look awkward.

Regards,
Marti Raudsepp

% diff -puw rawSHA1_fmt.c mysqlSHA1_fmt.c

--- rawSHA1_fmt.c	2007-11-03 13:33:46.000000000 +0200
+++ mysqlSHA1_fmt.c	2007-11-10 16:25:12.000000000 +0200
@@ -1,10 +1,24 @@
+// vim: set ts=8 sw=4 et :
 /*
- * Copyright (c) 2004 bartavelle
- * bartavelle@...decon.com
+ * Copyright (c) 2004 bartavelle, bartavelle@...decon.com
+ * Copyright (c) 2007 Marti Raudsepp <marti AT juffo org>
  *
- * Simple MD5 hashes cracker
- * It uses the Solar Designer's md5 implementation
+ * Simple MySQL 4.1+ PASSWORD() hash cracker, rev 1.
+ * Adapted from the original rawSHA1_fmt.c cracker.
  *
+ * Note that many version 4.1 and 5.0 installations still use the old
+ * homebrewn pre-4.1 hash for compatibility with older clients, notably all
+ * Red Hat-based distributions.
+ *
+ * The new PASSWORD() function is unsalted and equivalent to
+ * SHA1(SHA1(password)) where the inner is a binary digest (not hex!) This
+ * means that with the SSE2-boosted SHA1 implementation, it will be several
+ * times faster than John's cracker for the old hash format. (though the old
+ * hash had significant weaknesses, John's code does not take advantage of
+ * that)
+ *
+ * It's a slight improvement over the old hash, but still not something a
+ * reasonable DBMS would use for password storage.
  */

 #include <string.h>
@@ -15,16 +29,21 @@
 #include "formats.h"
 #include "sha.h"

-#define FORMAT_LABEL			"raw-sha1"
-#define FORMAT_NAME			"Raw SHA1"
+//#define X_DEBUG
+#ifdef X_DEBUG
+# include <assert.h>
+#endif
+
+#define FORMAT_LABEL			"mysql-sha1"
+#define FORMAT_NAME			"MySQL 4.1 double-SHA1"
 #ifdef MMX_COEF
 #if (MMX_COEF == 2)
-#define ALGORITHM_NAME			"raw-sha1 MMX"
+#  define ALGORITHM_NAME		"mysql-sha1 MMX"
 #else
-#define ALGORITHM_NAME			"raw-sha1 SSE2"
+#  define ALGORITHM_NAME		"mysql-sha1 SSE2"
 #endif
 #else
-#define ALGORITHM_NAME			"raw-sha1"
+# define ALGORITHM_NAME			"mysql-sha1"
 #endif

 #ifdef MMX_TYPE
@@ -35,7 +54,7 @@
 #define BENCHMARK_LENGTH		-1

 #define PLAINTEXT_LENGTH		32
-#define CIPHERTEXT_LENGTH		40
+#define CIPHERTEXT_LENGTH		41

 #define BINARY_SIZE			20
 #define SALT_SIZE			0
@@ -45,16 +64,24 @@
 #define MAX_KEYS_PER_CRYPT		MMX_COEF
 //#define GETPOS(i, index)		( (index)*4 + (i& (0xffffffff-3)
)*MMX_COEF + ((i)&3) ) //std getpos
 #define GETPOS(i, index)		( (index)*4 + (i& (0xffffffff-3) )*MMX_COEF
+ (3-((i)&3)) ) //for endianity conversion
+# define BYTESWAP(n) ( \
+        (((n)&0x000000ff) << 24) | \
+        (((n)&0x0000ff00) << 8 ) | \
+        (((n)&0x00ff0000) >> 8 ) | \
+        (((n)&0xff000000) >> 24) )
 #else
 #define MIN_KEYS_PER_CRYPT		1
 #define MAX_KEYS_PER_CRYPT		1
 #endif

-static struct fmt_tests rawsha1_tests[] = {
-	{"A9993E364706816ABA3E25717850C26C9CD0D89D", "abc"},
-	{"2fbf0eba37de1d1d633bc1ed943b907f9b360d4c", "azertyuiop1"},
-	{"f879f8090e92232ed07092ebed6dc6170457a21d", "azertyuiop2"},
-	{"1813c12f25e64931f3833b26e999e26e81f9ad24", "azertyuiop3"},
+static struct fmt_tests mysqlsha1_tests[] = {
+    {"*5AD8F88516BD021DD43F171E2C785C69F8E54ADB", "tere"},
+    {"*2C905879F74F28F8570989947D06A8429FB943E6", "verysecretpassword"},
+    {"*A8A397146B1A5F8C8CF26404668EFD762A1B7B82",
"________________________________"},
+    {"*F9F1470004E888963FB466A5452C9CBD9DF6239C",
"12345678123456781234567812345678"},
+    {"*97CF7A3ACBE0CA58D5391AC8377B5D9AC11D46D9", "' OR 1 /*'"},
+    {"*2470C0C06DEE42FD1618BB99005ADCA2EC9D1E19", "password"},
+    {"*7534F9EAEE5B69A586D1E9C1ACE3E3F9F6FCC446", "5"},
 	{NULL}
 };

@@ -62,6 +89,18 @@ static struct fmt_tests rawsha1_tests[]
 static char saved_key[PLAINTEXT_LENGTH*MMX_COEF*2 + 1] __attribute__
((aligned(16)));
 static char crypt_key[80*4*MMX_COEF+1] __attribute__ ((aligned(16)));
 unsigned long total_len;
+
+/* Intermediate key which stores the hashes between two SHA1 operations. Don't
+ * ask me why it has to be so long ;) */
+static char interm_key[80*4*MMX_COEF*2 + 1] __attribute__
((aligned(16))) = {0};
+
+# if MMX_COEF > 2
+/* argument to shammx(); all intermediary plaintexts are 20 bytes long */
+#  define TMPKEY_LENGTHS 0x14141414
+# else
+#  define TMPKEY_LENGTHS 0x00140014
+# endif
+
 unsigned char out[PLAINTEXT_LENGTH];
 #else
 static char saved_key[PLAINTEXT_LENGTH + 1];
@@ -74,28 +113,47 @@ static int valid(char *ciphertext)
 	int i;

 	if (strlen(ciphertext) != CIPHERTEXT_LENGTH) return 0;
-	for (i = 0; i < CIPHERTEXT_LENGTH; i++){
-		if (!(  (('0' <= ciphertext[i])&&(ciphertext[i] <= '9')) ||
-					(('a' <= ciphertext[i])&&(ciphertext[i] <= 'f'))
+    if (ciphertext[0] != '*')
+        return 0;
+    for (i = 1; i < CIPHERTEXT_LENGTH; i++){
+        if (!( (('0' <= ciphertext[i])&&(ciphertext[i] <= '9'))
+           || (('a' <= ciphertext[i])&&(ciphertext[i] <= 'f'))
 					|| (('A' <= ciphertext[i])&&(ciphertext[i] <= 'F'))))
+        {
 			return 0;
 	}
+    }
 	return 1;
 }

-static void rawsha1_set_salt(void *salt) { }
+static void mysqlsha1_set_salt(void *salt) { }

-static void rawsha1_init(void)
+static void mysqlsha1_init(void)
 {
 #ifdef MMX_COEF
-	memset(saved_key, 0, PLAINTEXT_LENGTH*MMX_COEF*2 + 1);
+    memset(saved_key, 0, sizeof saved_key);
+    memset(interm_key, 0, sizeof interm_key);
+    /* input strings have to be terminated by 0x80. The input strings in
+     * interm_key have a static length (20 bytes) so we can set them just once.
+     */
+    const int offset = (MMX_COEF*BINARY_SIZE)/4;
+
+    ((unsigned*)interm_key)[offset+0] = BYTESWAP(0x80);
+    ((unsigned*)interm_key)[offset+1] = BYTESWAP(0x80);
+# if MMX_COEF > 2
+    ((unsigned*)interm_key)[offset+2] = BYTESWAP(0x80);
+    ((unsigned*)interm_key)[offset+3] = BYTESWAP(0x80);
+# endif
 #endif
 }

-static void rawsha1_set_key(char *key, int index) {
+static void mysqlsha1_set_key(char *key, int index) {
 #ifdef MMX_COEF
 	int len;
 	int i;
+    /* FIXME: we're wasting 22% time in set_key with SSE2 (rawSHA1 is wasting
+     * nearly 50%!). The huge memset() is probably a culprit, but also the
+     * bytewise byte-order swapping code (see GETPOS macro above). */
 	
 	if(index==0)
 	{
@@ -116,7 +174,7 @@ static void rawsha1_set_key(char *key, i
 #endif
 }

-static char *rawsha1_get_key(int index) {
+static char *mysqlsha1_get_key(int index) {
 #ifdef MMX_COEF
 	unsigned int i,s;
 	
@@ -130,7 +188,7 @@ static char *rawsha1_get_key(int index)
 #endif
 }

-static int rawsha1_cmp_all(void *binary, int index) {
+static int mysqlsha1_cmp_all(void *binary, int index) {
 	int i=0;
 #ifdef MMX_COEF
 	while(i< (BINARY_SIZE/4) )
@@ -157,11 +215,11 @@ static int rawsha1_cmp_all(void *binary,
 	return 1;
 }

-static int rawsha1_cmp_exact(char *source, int count){
+static int mysqlsha1_cmp_exact(char *source, int count){
   return (1);
 }

-static int rawsha1_cmp_one(void * binary, int index)
+static int mysqlsha1_cmp_one(void *binary, int index)
 {
 #ifdef MMX_COEF
 	int i = 0;
@@ -170,27 +228,51 @@ static int rawsha1_cmp_one(void * binary
 			return 0;
 	return 1;
 #else
-	return rawsha1_cmp_all(binary, index);
+    return mysqlsha1_cmp_all(binary, index);
 #endif
 }

-static void rawsha1_crypt_all(int count) {
-  // get plaintext input in saved_key put it into ciphertext crypt_key
+static void mysqlsha1_crypt_all(int count) {
 #ifdef MMX_COEF
+    unsigned int i;
+
 	shammx(crypt_key, saved_key, total_len);
+
+    for(i = 0; i < MMX_COEF*BINARY_SIZE/sizeof(unsigned); i++)
+    {
+        ((unsigned*)interm_key)[i] = BYTESWAP(((unsigned*)crypt_key)[i]);
+    }
+
+    /* Verify that the 0x80 padding hasn't been overwritten. */
+# ifdef X_DEBUG
+    assert(((unsigned*)interm_key)[i+0] == BYTESWAP(0x80));
+    assert(((unsigned*)interm_key)[i+1] == BYTESWAP(0x80));
+#  if MMX_COEF > 2
+    assert(((unsigned*)interm_key)[i+2] == BYTESWAP(0x80));
+    assert(((unsigned*)interm_key)[i+3] == BYTESWAP(0x80));
+#  endif
+# endif /* X_DEBUG */
+
+    shammx(crypt_key, interm_key, TMPKEY_LENGTHS);
+
 #else
 	SHA1_Init( &ctx );
 	SHA1_Update( &ctx, saved_key, strlen( saved_key ) );
 	SHA1_Final( crypt_key, &ctx);
-#endif

+    SHA1_Init(&ctx);
+    SHA1_Update(&ctx, crypt_key, BINARY_SIZE);
+    SHA1_Final(crypt_key, &ctx);
+#endif
 }

-static void * rawsha1_binary(char *ciphertext)
+static void *mysqlsha1_binary(char *ciphertext)
 {
 	static char realcipher[BINARY_SIZE];
 	int i;
 	
+    // ignore first character '*'
+    ciphertext += 1;
 	for(i=0;i<BINARY_SIZE;i++)
 	{
 		realcipher[i] = atoi16[ARCH_INDEX(ciphertext[i*2])]*16 +
atoi16[ARCH_INDEX(ciphertext[i*2+1])];
@@ -228,7 +310,7 @@ static int get_hash_2(int index)
   return ((unsigned long *)crypt_key)[index] & 0xFFF;
 }

-struct fmt_main fmt_rawSHA1 = {
+struct fmt_main fmt_mysqlSHA1 = {
 	{
 		FORMAT_LABEL,
 		FORMAT_NAME,
@@ -241,12 +323,12 @@ struct fmt_main fmt_rawSHA1 = {
 		MIN_KEYS_PER_CRYPT,
 		MAX_KEYS_PER_CRYPT,
 		FMT_CASE | FMT_8_BIT,
-		rawsha1_tests
+        mysqlsha1_tests
 	}, {
-		rawsha1_init,
+        mysqlsha1_init,
 		valid,
 		fmt_default_split,
-		rawsha1_binary,
+        mysqlsha1_binary,
 		fmt_default_salt,
 		{
 			binary_hash_0,
@@ -254,18 +336,18 @@ struct fmt_main fmt_rawSHA1 = {
 			binary_hash_2
 		},
 		fmt_default_salt_hash,
-		rawsha1_set_salt,
-		rawsha1_set_key,
-		rawsha1_get_key,
+        mysqlsha1_set_salt,
+        mysqlsha1_set_key,
+        mysqlsha1_get_key,
 		fmt_default_clear_keys,
-		rawsha1_crypt_all,
+        mysqlsha1_crypt_all,
 		{
 			get_hash_0,
 			get_hash_1,
 			get_hash_2
 		},
-		rawsha1_cmp_all,
-		rawsha1_cmp_one,
-		rawsha1_cmp_exact
+        mysqlsha1_cmp_all,
+        mysqlsha1_cmp_one,
+        mysqlsha1_cmp_exact
 	}
 };

[ CONTENT OF TYPE application/octet-stream SKIPPED ]

-- 
To unsubscribe, e-mail john-users-unsubscribe@...ts.openwall.com and reply
to the automated confirmation request that will be sent to you.

Powered by blists - more mailing lists

Your e-mail address:

Powered by Openwall GNU/*/Linux - Powered by OpenVZ