Openwall GNU/*/Linux - a small security-enhanced Linux distro for servers
[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]
Date: Sat, 14 Jul 2012 15:01:36 +0400
From: Solar Designer <solar@...nwall.com>
To: john-dev@...ts.openwall.com
Subject: Re: magnum-jumbo and magnum-bleeding (NOT J7), and the source() function

Jim, all -

On Tue, Jul 10, 2012 at 03:24:57PM +0400, Solar Designer wrote:
> On Mon, Jul 09, 2012 at 05:46:31PM -0500, jfoug wrote:
> > I do think the interface for source() (or get_source(), or foo_bar() or
> > whatever) is good.   Passing in the db_password structure pointer, and then
> > 'using' the salt pointer in multiple ways, makes calling source() very easy
> > to do, almost a direct replacement for the original pw->source pointer, AND
> > saves memory, in not wasting space even for another pointer.
> 
> My tentative plan is to reuse the pw->source pointer for the "cold"
> portion of the binary, when we do introduce the hot/cold split.  I do
> not see why you need it for storing the salt.  I think that source()
> should accept "void *binary" and "void *salt" instead of "struct
> db_password *".  Yes, this is two parameters to pass instead of one,
> but so what.  We're not calling source() from so many places that the
> extra parameter would make the source code much less readable.  In fact,
> preserving the separation between a "format" and a "database" is good.
> I might deviate from this separation in another place, but that's for a
> specific good reason, and it'd be an exception that proves the rule. ;-)
> I don't see a good reason like that for source().

This turned out to be trickier than I had expected since there are
places in loader.c where we have a binary, but no corresponding salt (we
can find it with an extra loop, though).  For now, I chose to implement
source() for saltless hashes only.  For salted hashes, it currently
ought to be fmt_default_source(), which simply returns the source passed
into it verbatim.

I have not yet implemented the hot/cold thing.  Instead, I am currently
reusing the source pointer to hold the binary value when it fits into
that field (like for LM hashes on a 64-bit machine).

Attached is a patch demonstrating these changes (relative to the patch
introducing prepare() that I posted yesterday).  I tested this on
10 million of LM hashes.  Memory usage reduced from 1040 MB to 805 MB,
the speed appears to have remained unchanged (maybe there is a speed
difference for smaller hash counts, like 100k).

Alexander

diff -u john-1.7.9.4-newform/src/AFS_fmt.c john-1.7.9.4-newform/src/AFS_fmt.c
--- john-1.7.9.4-newform/src/AFS_fmt.c	2012-07-13 02:51:23 +0000
+++ john-1.7.9.4-newform/src/AFS_fmt.c	2012-07-14 08:33:35 +0000
@@ -450,6 +450,7 @@
 		fmt_default_split,
 		get_binary,
 		salt,
+		fmt_default_source,
 		{
 			binary_hash_0,
 			binary_hash_1,
diff -u john-1.7.9.4-newform/src/BF_fmt.c john-1.7.9.4-newform/src/BF_fmt.c
--- john-1.7.9.4-newform/src/BF_fmt.c	2012-07-13 02:51:51 +0000
+++ john-1.7.9.4-newform/src/BF_fmt.c	2012-07-14 08:33:47 +0000
@@ -293,6 +293,7 @@
 		fmt_default_split,
 		BF_std_get_binary,
 		BF_std_get_salt,
+		fmt_default_source,
 		{
 			binary_hash_0,
 			binary_hash_1,
diff -u john-1.7.9.4-newform/src/BSDI_fmt.c john-1.7.9.4-newform/src/BSDI_fmt.c
--- john-1.7.9.4-newform/src/BSDI_fmt.c	2012-07-13 02:52:04 +0000
+++ john-1.7.9.4-newform/src/BSDI_fmt.c	2012-07-14 08:33:51 +0000
@@ -410,6 +410,7 @@
 			DES_std_get_binary,
 #endif
 		salt,
+		fmt_default_source,
 		{
 			binary_hash_0,
 			binary_hash_1,
diff -u john-1.7.9.4-newform/src/DES_fmt.c john-1.7.9.4-newform/src/DES_fmt.c
--- john-1.7.9.4-newform/src/DES_fmt.c	2012-07-13 02:52:20 +0000
+++ john-1.7.9.4-newform/src/DES_fmt.c	2012-07-14 08:33:57 +0000
@@ -373,6 +373,7 @@
 			DES_std_get_binary,
 #endif
 		salt,
+		fmt_default_source,
 		{
 			binary_hash_0,
 			binary_hash_1,
diff -u john-1.7.9.4-newform/src/LM_fmt.c john-1.7.9.4-newform/src/LM_fmt.c
--- john-1.7.9.4-newform/src/LM_fmt.c	2012-07-13 06:24:18 +0000
+++ john-1.7.9.4-newform/src/LM_fmt.c	2012-07-14 09:56:22 +0000
@@ -38,7 +38,7 @@
 
 #define ALGORITHM_NAME			DES_BS_ALGORITHM_NAME
 
-#define BINARY_SIZE			sizeof(ARCH_WORD_32)
+#define BINARY_SIZE			(sizeof(ARCH_WORD_32) * 2)
 #define SALT_SIZE			0
 
 #define MIN_KEYS_PER_CRYPT		DES_BS_DEPTH
@@ -113,11 +113,16 @@
 	return out;
 }
 
-static void *get_binary(char *ciphertext)
+static void *binary(char *ciphertext)
 {
 	return DES_bs_get_binary_LM(ciphertext + 4);
 }
 
+static char *source(char *source, void *binary)
+{
+	return split(DES_bs_get_source_LM(binary), 0, NULL);
+}
+
 static int binary_hash_0(void *binary)
 {
 	return *(ARCH_WORD_32 *)binary & 0xF;
@@ -160,7 +165,7 @@
 
 static int cmp_exact(char *source, int index)
 {
-	return DES_bs_cmp_one(get_binary(source), 64, index);
+	return DES_bs_cmp_one(binary(source), 64, index);
 }
 
 static char *get_key(int index)
@@ -204,8 +209,9 @@
 		prepare,
 		valid,
 		split,
-		get_binary,
+		binary,
 		fmt_default_salt,
+		source,
 		{
 			binary_hash_0,
 			binary_hash_1,
diff -u john-1.7.9.4-newform/src/MD5_fmt.c john-1.7.9.4-newform/src/MD5_fmt.c
--- john-1.7.9.4-newform/src/MD5_fmt.c	2012-07-13 02:52:44 +0000
+++ john-1.7.9.4-newform/src/MD5_fmt.c	2012-07-14 08:34:08 +0000
@@ -248,6 +248,7 @@
 		fmt_default_split,
 		(void *(*)(char *))MD5_std_get_binary,
 		(void *(*)(char *))MD5_std_get_salt,
+		fmt_default_source,
 		{
 			binary_hash_0,
 			binary_hash_1,
diff -u john-1.7.9.4-newform/src/c3_fmt.c john-1.7.9.4-newform/src/c3_fmt.c
--- john-1.7.9.4-newform/src/c3_fmt.c	2012-07-13 02:52:52 +0000
+++ john-1.7.9.4-newform/src/c3_fmt.c	2012-07-14 08:34:13 +0000
@@ -435,6 +435,7 @@
 		fmt_default_split,
 		binary,
 		salt,
+		fmt_default_source,
 		{
 			binary_hash_0,
 			binary_hash_1,
diff -u john-1.7.9.4-newform/src/dummy.c john-1.7.9.4-newform/src/dummy.c
--- john-1.7.9.4-newform/src/dummy.c	2012-07-13 02:51:03 +0000
+++ john-1.7.9.4-newform/src/dummy.c	2012-07-14 08:34:22 +0000
@@ -277,6 +277,7 @@
 		fmt_default_split,
 		binary,
 		fmt_default_salt,
+		fmt_default_source,
 		{
 			binary_hash_0,
 			binary_hash_1,
diff -u john-1.7.9.4-newform/src/formats.c john-1.7.9.4-newform/src/formats.c
--- john-1.7.9.4-newform/src/formats.c	2012-07-13 03:11:14 +0000
+++ john-1.7.9.4-newform/src/formats.c	2012-07-14 10:28:02 +0000
@@ -54,7 +54,8 @@
 	if (format->params.plaintext_length > PLAINTEXT_BUFFER_SIZE - 3)
 		return "length";
 
-	if (format->methods.valid("*", format)) return "valid";
+	if (format->methods.valid("*", format))
+		return "valid";
 
 	fmt_init(format);
 
@@ -96,6 +97,10 @@
 		memcpy(salt_copy, salt, format->params.salt_size);
 		salt = salt_copy;
 
+		if (strcmp(ciphertext,
+		    format->methods.source(ciphertext, binary)))
+			return "source";
+
 		if ((unsigned int)format->methods.salt_hash(salt) >=
 		    SALT_HASH_SIZE)
 			return "salt_hash";
@@ -216,6 +221,11 @@
 	return ciphertext;
 }
 
+char *fmt_default_source(char *source, void *binary)
+{
+	return source;
+}
+
 int fmt_default_binary_hash(void *binary)
 {
 	return 0;
diff -u john-1.7.9.4-newform/src/formats.h john-1.7.9.4-newform/src/formats.h
--- john-1.7.9.4-newform/src/formats.h	2012-07-13 04:51:58 +0000
+++ john-1.7.9.4-newform/src/formats.h	2012-07-14 08:29:51 +0000
@@ -130,6 +130,10 @@
 /* Converts an ASCII salt to its internal representation */
 	void *(*salt)(char *ciphertext);
 
+/* Reconstructs the ASCII ciphertext from its binary (saltless only).
+ * Alternatively, in the simplest case simply returns "source" as-is. */
+	char *(*source)(char *source, void *binary);
+
 /* These functions calculate a hash out of a binary ciphertext. To be used
  * for hash table initialization. One of them should be selected depending
  * on the hash table size. */
@@ -223,6 +227,7 @@
     struct fmt_main *self);
 extern void *fmt_default_binary(char *ciphertext);
 extern void *fmt_default_salt(char *ciphertext);
+extern char *fmt_default_source(char *source, void *binary);
 extern int fmt_default_binary_hash(void *binary);
 extern int fmt_default_salt_hash(void *salt);
 extern void fmt_default_set_salt(void *salt);
diff -u john-1.7.9.4-newform/src/loader.c john-1.7.9.4-newform/src/loader.c
--- john-1.7.9.4-newform/src/loader.c	2012-07-13 06:33:19 +0000
+++ john-1.7.9.4-newform/src/loader.c	2012-07-14 10:12:05 +0000
@@ -514,9 +514,10 @@
 			int collisions = 0;
 			if ((current_pw = db->password_hash[pw_hash]))
 			do {
-				if (!memcmp(current_pw->binary, binary,
+				if (!memcmp(binary, current_pw->binary,
 				    format->params.binary_size) &&
-				    !strcmp(current_pw->source, piece)) {
+				    !strcmp(piece, format->methods.source(
+				    current_pw->source, current_pw->binary))) {
 					db->options->flags |= DB_NODUP;
 					break;
 				}
@@ -588,10 +589,18 @@
 		db->password_hash[pw_hash] = current_pw;
 		current_pw->next_hash = last_pw;
 
-		current_pw->binary = alloc_copy_autoalign(
-			format->params.binary_size, binary);
+/* If we're not going to use the source field for its usual purpose, see if we
+ * can pack the binary value in it. */
+		if (format->methods.source != fmt_default_source &&
+		    sizeof(current_pw->source) >= format->params.binary_size)
+			current_pw->binary = memcpy(&current_pw->source,
+				binary, format->params.binary_size);
+		else
+			current_pw->binary = alloc_copy_autoalign(
+				format->params.binary_size, binary);
 
-		current_pw->source = str_alloc_copy(piece);
+		if (format->methods.source == fmt_default_source)
+			current_pw->source = str_alloc_copy(piece);
 
 		if (db->options->flags & DB_WORDS) {
 			if (!words)
@@ -639,10 +648,14 @@
 
 	if ((current = db->password_hash[hash]))
 	do {
-		if (current->binary && !memcmp(current->binary, binary,
-		    format->params.binary_size) &&
-		    !strcmp(current->source, ciphertext))
-			current->binary = NULL;
+		if (!current->binary) /* already marked for removal */
+			continue;
+		if (memcmp(binary, current->binary, format->params.binary_size))
+			continue;
+		if (strcmp(ciphertext,
+		    format->methods.source(current->source, current->binary)))
+			continue;
+		current->binary = NULL; /* mark for removal */
 	} while ((current = current->next_hash));
 }
 
diff -u john-1.7.9.4-newform/src/trip_fmt.c john-1.7.9.4-newform/src/trip_fmt.c
--- john-1.7.9.4-newform/src/trip_fmt.c	2012-07-13 02:53:13 +0000
+++ john-1.7.9.4-newform/src/trip_fmt.c	2012-07-14 08:34:18 +0000
@@ -592,6 +592,7 @@
 		fmt_default_split,
 		get_binary,
 		fmt_default_salt,
+		fmt_default_source,
 		{
 			binary_hash_0,
 			binary_hash_1,
only in patch2:
unchanged:
--- john-1.7.9.4/src/DES_bs.c	2012-01-29 00:48:58 +0000
+++ john-1.7.9.4-newform/src/DES_bs.c	2012-07-14 09:25:17 +0000
@@ -302,6 +302,32 @@ ARCH_WORD_32 *DES_bs_get_binary_LM(char 
 	return DES_bs_get_binary_raw(DES_do_IP(block), 1);
 }
 
+char *DES_bs_get_source_LM(ARCH_WORD_32 *raw)
+{
+	static char out[17];
+	char *p;
+	ARCH_WORD swapped[2], *block, value;
+	int l, h;
+	int index;
+
+	swapped[0] = raw[1];
+	swapped[1] = raw[0];
+
+	block = DES_do_FP(swapped);
+
+	p = out;
+	for (index = 0; index < 16; index += 2) {
+		value = (block[index >> 3] >> ((index << 2) & 0x18)) & 0xff;
+		l = DES_LM_reverse[value & 0xf];
+		h = DES_LM_reverse[value >> 4];
+		*p++ = itoa16[l];
+		*p++ = itoa16[h];
+	}
+	*p = 0;
+
+	return out;
+}
+
 static MAYBE_INLINE int DES_bs_get_hash(int index, int count, int trip)
 {
 	int result;
only in patch2:
unchanged:
--- john-1.7.9.4/src/DES_bs.h	2012-01-29 00:48:58 +0000
+++ john-1.7.9.4-newform/src/DES_bs.h	2012-07-14 09:23:51 +0000
@@ -160,6 +160,11 @@ extern ARCH_WORD_32 *DES_bs_get_binary(c
 extern ARCH_WORD_32 *DES_bs_get_binary_LM(char *ciphertext);
 
 /*
+ * The reverse of DES_bs_get_binary_LM().
+ */
+extern char *DES_bs_get_source_LM(ARCH_WORD_32 *raw);
+
+/*
  * Calculate a hash for a DES_bs_crypt*() output.
  *
  * "t"-suffixed versions of these functions are for tripcodes (they skip
only in patch2:
unchanged:
--- john-1.7.9.4/src/DES_std.c	2006-05-08 06:31:50 +0000
+++ john-1.7.9.4-newform/src/DES_std.c	2012-07-14 09:53:52 +0000
@@ -1,6 +1,6 @@
 /*
  * This file is part of John the Ripper password cracker,
- * Copyright (c) 1996-2001,2005 by Solar Designer
+ * Copyright (c) 1996-2001,2005,2012 by Solar Designer
  */
 
 #include <string.h>
@@ -1088,6 +1088,22 @@ ARCH_WORD *DES_do_IP(ARCH_WORD in[2])
 	return out;
 }
 
+ARCH_WORD *DES_do_FP(ARCH_WORD in[2])
+{
+	static ARCH_WORD out[2];
+	int src, dst;
+
+	out[0] = out[1] = 0;
+	for (src = 0; src < 64; src++) {
+		dst = DES_IP[src ^ 0x20];
+
+		if (in[src >> 5] & (1 << (src & 0x1F)))
+			out[dst >> 5] |= 1 << (dst & 0x1F);
+	}
+
+	return out;
+}
+
 ARCH_WORD *DES_raw_get_binary(char *ciphertext)
 {
 	ARCH_WORD block[3];
only in patch2:
unchanged:
--- john-1.7.9.4/src/DES_std.h	2002-04-10 14:13:25 +0000
+++ john-1.7.9.4-newform/src/DES_std.h	2012-07-14 09:10:38 +0000
@@ -1,6 +1,6 @@
 /*
  * This file is part of John the Ripper password cracker,
- * Copyright (c) 1996-2000 by Solar Designer
+ * Copyright (c) 1996-2000,2012 by Solar Designer
  */
 
 /*
@@ -176,13 +176,18 @@ extern ARCH_WORD DES_std_get_salt(char *
 extern ARCH_WORD DES_raw_get_count(char *ciphertext);
 
 /*
- * Does the Initial Permutation; to be used at startup only (doesn't
- * require that DES_std_init() has been called, is not as fast as it
- * could be).
+ * Does the Initial Permutation; to be used at startup only (doesn't require
+ * that DES_std_init() has been called, is by far not as fast as it could be).
  */
 extern ARCH_WORD *DES_do_IP(ARCH_WORD in[2]);
 
 /*
+ * Ditto for Final Permutation; to be used for reconstruction of source from
+ * binary ciphertext at startup and when a password is successfully cracked.
+ */
+extern ARCH_WORD *DES_do_FP(ARCH_WORD in[2]);
+
+/*
  * Converts an ASCII ciphertext to binary.
  */
 extern ARCH_WORD *DES_raw_get_binary(char *ciphertext);
only in patch2:
unchanged:
--- john-1.7.9.4/src/cracker.c	2012-01-29 00:48:58 +0000
+++ john-1.7.9.4-newform/src/cracker.c	2012-07-14 08:32:46 +0000
@@ -178,7 +178,8 @@ static int crk_process_guess(struct db_s
 	key = crk_methods.get_key(index);
 
 	log_guess(crk_db->options->flags & DB_LOGIN ? pw->login : "?",
-		dupe ? NULL : pw->source, key);
+	    dupe ? NULL :
+	    crk_methods.source(pw->source, pw->binary), key);
 
 	crk_db->guess_count++;
 	status.guess_count++;
@@ -249,7 +250,8 @@ static int crk_password_loop(struct db_s
 			if (crk_methods.cmp_all(pw->binary, crk_key_index))
 			for (index = 0; index < crk_key_index; index++)
 			if (crk_methods.cmp_one(pw->binary, index))
-			if (crk_methods.cmp_exact(pw->source, index)) {
+			if (crk_methods.cmp_exact(crk_methods.source(
+			    pw->source, pw->binary), index)) {
 				if (crk_process_guess(salt, pw, index))
 					return 1;
 				else
@@ -264,7 +266,8 @@ static int crk_password_loop(struct db_s
 			pw = salt->hash[hash >> PASSWORD_HASH_SHR];
 			do {
 				if (crk_methods.cmp_one(pw->binary, index))
-				if (crk_methods.cmp_exact(pw->source, index))
+				if (crk_methods.cmp_exact(crk_methods.source(
+				    pw->source, pw->binary), index))
 				if (crk_process_guess(salt, pw, index))
 					return 1;
 			} while ((pw = pw->next_hash));
only in patch2:
unchanged:
--- john-1.7.9.4/src/loader.h	2012-01-29 00:48:58 +0000
+++ john-1.7.9.4-newform/src/loader.h	2012-07-14 10:15:52 +0000
@@ -15,27 +15,30 @@
 #include "formats.h"
 
 /*
- * Password list (with a fixed salt) entry.
+ * Password hash list entry (with a fixed salt).
  */
 struct db_password {
-/* Pointer to next password with the same salt */
+/* Pointer to next password hash with the same salt */
 	struct db_password *next;
 
-/* Pointer to next password with the same salt and hash (used for a different
- * purpose while loading). */
+/* After loading is completed: pointer to next password hash with the same salt
+ * and hash-of-hash.
+ * While loading: pointer to next password hash with the same hash-of-hash. */
 	struct db_password *next_hash;
 
-/* Some bytes of binary ciphertext for fast comparison */
+/* Hot portion of or full binary ciphertext for fast comparison (aligned) */
 	void *binary;
 
-/* ASCII ciphertext for exact comparison and saving with cracked passwords */
+/* ASCII ciphertext for exact comparison and saving with cracked passwords.
+ * Alternatively, when the source() method is non-default this field is either
+ * unused or this pointer may be reused to hold the binary value above. */
 	char *source;
 
 /* Login field from the password file, with ":1" or ":2" appended if the
  * ciphertext was split into two parts. */
 	char *login;
 
-/* Words from GECOS field -- loaded for "single crack" mode only */
+/* Words from the GECOS field (loaded for "single crack" mode only) */
 	struct list_main *words;
 };
 

Powered by blists - more mailing lists

Your e-mail address:

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