[<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
}
};
Download attachment "mysqlSHA1-rev1.patch" of type "application/octet-stream" (11010 bytes)
--
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
Confused about mailing lists and their use?
Read about mailing lists on Wikipedia
and check out these
guidelines on proper formatting of your messages.
