Openwall GNU/*/Linux - a small security-enhanced Linux distro for servers
[<prev] [next>] [thread-next>] [day] [month] [year] [list]
Date: Wed, 16 Sep 2015 05:28:17 +0300
From: Solar Designer <solar@...nwall.com>
To: john-dev@...ts.openwall.com
Subject: larger bitmaps and hash tables

Fred, magnum, all -

I am trying to stop the mess in the "Judy array" thread by starting
separate threads for the various related topics that come up.  Please
help me with this by also using per-topic threads.

Attached are two patches - john-huge-largehash.diff is preparing us for
larger bitmaps and possibly hash tables and cleaning up our use of
integer types a little bit in general (I think we should commit this
one), and john-huge-largehash-plus1.diff increases the size of the
largest bitmap for raw-md5 by a factor of 2 (and breaks other formats).

Previously, my best speed for Fred's testcase on 2x E5420 was:

real    0m55.630s
user    4m7.385s
sys     0m16.687s

With these two patches, I am getting:

real    0m53.729s
user    3m36.475s
sys     0m16.151s

That's still with PASSWORD_HASH_SHR at 0, as I set it in previous
patches (in the "Judy array" thread).  With SHR=1:

real    0m52.976s
user    3m39.218s
sys     0m16.227s

With SHR=2:

real    0m54.221s
user    3m44.508s
sys     0m19.503s

So maybe we should in fact increase our largest bitmap size, and at the
same time use larger SHR (to keep the largest hash table from increasing).

To beat Fred's reported speed, we need to get below:

47*233/250 = 43.8 seconds

adjusted for CPU clock rate difference.

Of course, we'd still be using far more RAM than MDXfind did in that test.

Alexander

diff -urp bleeding-jumbo-opt4/src/loader.c bleeding-jumbo-opt/src/loader.c
--- bleeding-jumbo-opt4/src/loader.c	2015-09-16 00:29:32 +0000
+++ bleeding-jumbo-opt/src/loader.c	2015-09-16 02:00:31 +0000
@@ -196,7 +196,7 @@ void ldr_init_database(struct db_main *d
 static void ldr_init_password_hash(struct db_main *db)
 {
 	int (*func)(void *binary);
-	int size = PASSWORD_HASH_SIZE_FOR_LDR;
+	size_t size = PASSWORD_HASH_SIZE_FOR_LDR;
 
 	if (size >= 2 && mem_saving_level >= 2) {
 		size--;
@@ -212,7 +212,7 @@ static void ldr_init_password_hash(struc
 	if (size < 0)
 		size = 0;
 	db->password_hash_func = func;
-	size = password_hash_sizes[size] * sizeof(struct db_password *);
+	size = (size_t)password_hash_sizes[size] * sizeof(struct db_password *);
 	db->password_hash = mem_alloc(size);
 	memset(db->password_hash, 0, size);
 }
@@ -1449,7 +1449,7 @@ static void ldr_init_hash_for_salt(struc
 {
 	struct db_password *current;
 	int (*hash_func)(void *binary);
-	int bitmap_size, hash_size;
+	size_t bitmap_size, hash_size;
 	int hash;
 
 	if (salt->hash_size < 0) {
diff -urp bleeding-jumbo-opt4/src/params.c bleeding-jumbo-opt/src/params.c
--- bleeding-jumbo-opt4/src/params.c	2015-02-24 06:08:07 +0000
+++ bleeding-jumbo-opt/src/params.c	2015-09-16 02:02:26 +0000
@@ -11,7 +11,7 @@
 #include "params.h"
 #include "memdbg.h"
 
-int password_hash_sizes[PASSWORD_HASH_SIZES] = {
+unsigned int password_hash_sizes[PASSWORD_HASH_SIZES] = {
 	PASSWORD_HASH_SIZE_0,
 	PASSWORD_HASH_SIZE_1,
 	PASSWORD_HASH_SIZE_2,
@@ -21,7 +21,7 @@ int password_hash_sizes[PASSWORD_HASH_SI
 	PASSWORD_HASH_SIZE_6
 };
 
-int password_hash_thresholds[PASSWORD_HASH_SIZES] = {
+unsigned int password_hash_thresholds[PASSWORD_HASH_SIZES] = {
 	PASSWORD_HASH_THRESHOLD_0,
 	PASSWORD_HASH_THRESHOLD_1,
 	PASSWORD_HASH_THRESHOLD_2,
diff -urp bleeding-jumbo-opt4/src/params.h bleeding-jumbo-opt/src/params.h
--- bleeding-jumbo-opt4/src/params.h	2015-09-16 01:15:15 +0000
+++ bleeding-jumbo-opt/src/params.h	2015-09-16 02:03:05 +0000
@@ -226,8 +226,8 @@
 /*
  * Tables of the above values.
  */
-extern int password_hash_sizes[PASSWORD_HASH_SIZES];
-extern int password_hash_thresholds[PASSWORD_HASH_SIZES];
+extern unsigned int password_hash_sizes[PASSWORD_HASH_SIZES];
+extern unsigned int password_hash_thresholds[PASSWORD_HASH_SIZES];
 
 /*
  * How much smaller should the hash tables be than bitmaps in terms of entry

diff -urp bleeding-jumbo-opt5/src/formats.c bleeding-jumbo-opt/src/formats.c
--- bleeding-jumbo-opt5/src/formats.c	2015-09-11 15:40:58 +0000
+++ bleeding-jumbo-opt/src/formats.c	2015-09-16 02:08:06 +0000
@@ -1562,7 +1562,7 @@ int fmt_default_binary_hash_5(void * bin
 
 int fmt_default_binary_hash_6(void * binary)
 {
-	return *(ARCH_WORD_32 *) binary & 0x7FFFFFF;
+	return *(ARCH_WORD_32 *) binary & 0xFFFFFFF;
 }
 
 int fmt_default_salt_hash(void *salt)
diff -urp bleeding-jumbo-opt5/src/params.h bleeding-jumbo-opt/src/params.h
--- bleeding-jumbo-opt5/src/params.h	2015-09-16 02:03:05 +0000
+++ bleeding-jumbo-opt/src/params.h	2015-09-16 02:08:24 +0000
@@ -208,7 +208,7 @@
 #define PASSWORD_HASH_SIZE_3		0x10000
 #define PASSWORD_HASH_SIZE_4		0x100000
 #define PASSWORD_HASH_SIZE_5		0x1000000
-#define PASSWORD_HASH_SIZE_6		0x8000000
+#define PASSWORD_HASH_SIZE_6		0x10000000
 
 /*
  * Password hash table thresholds.  These are the counts of entries required
diff -urp bleeding-jumbo-opt5/src/rawMD5_fmt_plug.c bleeding-jumbo-opt/src/rawMD5_fmt_plug.c
--- bleeding-jumbo-opt5/src/rawMD5_fmt_plug.c	2015-09-15 00:00:46 +0000
+++ bleeding-jumbo-opt/src/rawMD5_fmt_plug.c	2015-09-16 02:09:04 +0000
@@ -414,7 +414,7 @@ static int get_hash_2(int index) { retur
 static int get_hash_3(int index) { return ((ARCH_WORD_32*)crypt_key)[SIMD_INDEX] & 0xffff; }
 static int get_hash_4(int index) { return ((ARCH_WORD_32*)crypt_key)[SIMD_INDEX] & 0xfffff; }
 static int get_hash_5(int index) { return ((ARCH_WORD_32*)crypt_key)[SIMD_INDEX] & 0xffffff; }
-static int get_hash_6(int index) { return ((ARCH_WORD_32*)crypt_key)[SIMD_INDEX] & 0x7ffffff; }
+static int get_hash_6(int index) { return ((ARCH_WORD_32*)crypt_key)[SIMD_INDEX] & 0xfffffff; }
 #else
 static int get_hash_0(int index) { return ((ARCH_WORD_32*)crypt_key)[index] & 0xf; }
 static int get_hash_1(int index) { return ((ARCH_WORD_32*)crypt_key)[index] & 0xff; }
@@ -422,7 +422,7 @@ static int get_hash_2(int index) { retur
 static int get_hash_3(int index) { return ((ARCH_WORD_32*)crypt_key)[index] & 0xffff; }
 static int get_hash_4(int index) { return ((ARCH_WORD_32*)crypt_key)[index] & 0xfffff; }
 static int get_hash_5(int index) { return ((ARCH_WORD_32*)crypt_key)[index] & 0xffffff; }
-static int get_hash_6(int index) { return ((ARCH_WORD_32*)crypt_key)[index] & 0x7ffffff; }
+static int get_hash_6(int index) { return ((ARCH_WORD_32*)crypt_key)[index] & 0xfffffff; }
 #endif
 
 struct fmt_main fmt_rawMD5 = {

Powered by blists - more mailing lists

Your e-mail address:

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