Openwall GNU/*/Linux - a small security-enhanced Linux distro for servers
[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]
Date: Sat, 15 Jun 2013 05:06:07 +0400
From: Solar Designer <solar@...nwall.com>
To: john-dev@...ts.openwall.com
Subject: Re: Mask mode for GPU

On Thu, Jun 13, 2013 at 07:37:17PM +0400, Solar Designer wrote:
> [...]  Our rules preprocessor implements something very similar -
> in fact, I think we might want to support its syntax as well.  For a
> trivial implementation, we could simply be calling rpp_*() from the mask
> mode implementation - and it'd just work for rpp's variation of the
> syntax.  However, rpp is mostly unoptimized (it wasn't meant to be used
> from a performance-critical place) and it implements its syntax only
> (not the PasswordsPro/hashcat "mask attack" syntax).

I've attached a proof-of-concept patch (against core) that illustrates
this similarity.  Moreover, it introduces PasswordsPro/hashcat "mask
attack" syntax into rpp (only enabled when invoked from our mask mode).
Mixed syntax works, too:

$ ./john --mask='?u?l[ab]?d??' --stdout | head -3
Press 'q' or Ctrl-C to abort, almost any other key for status
Aaa0?
Aaa1?
Aaa2?

$ ./john --mask='?u?l[ab]?d??' --stdout | tail -3
Press 'q' or Ctrl-C to abort, almost any other key for status
13520p 0:00:00:00 1352Kp/s Zzb9?
Zzb7?
Zzb8?
Zzb9?

Speed on one core in FX-8120 when run against one LM hash:

$ ./john --mask='?u?u?u?u?u?u' --format=lm pw
Loaded 1 password hash (LM [DES 128/128 XOP-16])
Press 'q' or Ctrl-C to abort, almost any other key for status
0g 0:00:00:13 0g/s 23157Kp/s 23157Kc/s 23157KC/s ZZZZXO..ZZZZZZ
Session completed

For comparison, incremental mode locked to the same charset and length:

$ ./john -i=upper6 --format=lm pw
Loaded 1 password hash (LM [DES 128/128 XOP-16])
Press 'q' or Ctrl-C to abort, almost any other key for status
0g 0:00:00:06 0g/s 44448Kp/s 44448Kc/s 44448KC/s UXHZQN..UXHQFQ
Session completed

So, yes, in its present form rpp is slower than our mask mode should be
(it should be faster than incremental, not slower, unless we somehow
make it use incremental's *.chr files).  It's not slow to the point of
being unusable, though.

Not implemented in this PoC are support for: --restore, --node & --fork,
progress indicator.  These are trivial to add (good efficiency and
scalability at --node & --fork is not as trivial, though - would require
changes to rpp.c).  Also not implemented yet are many of the pre-defined
"mask attack" charsets, but these are even more obviously trivial to add.

As to introducing support for format's set_mask() into this - now that's
possibly more difficult than it would be with a specialized implementation.
Yet I think we should not give up on this approach.  Perhaps we'd have
to untie mask mode from rpp, but we may nevertheless start by duplicating
much of rpp's structure and initially even code - and only then proceed
to customize it for optional use of set_mask().

Alexander

diff -urpN -x arch.h -x '*.o' -x run john-1.8.0/src/Makefile john-1.8.0-mask/src/Makefile
--- john-1.8.0/src/Makefile	2013-05-29 23:21:25 +0000
+++ john-1.8.0-mask/src/Makefile	2013-06-14 23:15:06 +0000
@@ -48,8 +48,9 @@ JOHN_OBJS = \
 	dummy.o \
 	batch.o bench.o charset.o common.o compiler.o config.o cracker.o \
 	crc32.o external.o formats.o getopt.o idle.o inc.o john.o list.o \
-	loader.o logger.o math.o memory.o misc.o options.o params.o path.o \
-	recovery.o rpp.o rules.o signals.o single.o status.o tty.o wordlist.o \
+	loader.o logger.o mask.o math.o memory.o misc.o options.o params.o \
+	path.o recovery.o rpp.o rules.o signals.o single.o status.o tty.o \
+	wordlist.o \
 	unshadow.o \
 	unafs.o \
 	unique.o
diff -urpN -x arch.h -x '*.o' -x run john-1.8.0/src/john.c john-1.8.0-mask/src/john.c
--- john-1.8.0/src/john.c	2013-05-29 23:27:25 +0000
+++ john-1.8.0-mask/src/john.c	2013-06-14 23:14:27 +0000
@@ -57,6 +57,7 @@ static int john_omp_threads_new;
 #include "single.h"
 #include "wordlist.h"
 #include "inc.h"
+#include "mask.h"
 #include "external.h"
 #include "batch.h"
 
@@ -592,6 +593,9 @@ static void john_run(void)
 		if (options.flags & FLG_INC_CHK)
 			do_incremental_crack(&database, options.charset);
 		else
+		if (options.flags & FLG_MASK_CHK)
+			do_mask_crack(&database, options.mask);
+		else
 		if (options.flags & FLG_EXTERNAL_CHK)
 			do_external_crack(&database);
 		else
diff -urpN -x arch.h -x '*.o' -x run john-1.8.0/src/mask.c john-1.8.0-mask/src/mask.c
--- john-1.8.0/src/mask.c	1970-01-01 00:00:00 +0000
+++ john-1.8.0-mask/src/mask.c	2013-06-15 00:01:29 +0000
@@ -0,0 +1,60 @@
+/*
+ * This file is part of John the Ripper password cracker,
+ * Copyright (c) 2013 by Solar Designer
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted.
+ *
+ * There's ABSOLUTELY NO WARRANTY, express or implied.
+ */
+
+#include <stdio.h> /* for fprintf(stderr, ...) */
+
+#include "misc.h" /* for error() */
+#include "logger.h"
+#include "status.h"
+#include "options.h"
+#include "rpp.h"
+#include "external.h"
+#include "cracker.h"
+#include "john.h"
+#include "mask.h"
+
+void do_mask_crack(struct db_main *db, char *mask)
+{
+	struct rpp_context ctx;
+	char *word;
+
+	if (options.node_count) {
+		if (john_main_process)
+			fprintf(stderr, "--mask is not yet compatible with --node and --fork\n");
+		error();
+	}
+
+	log_event("Proceeding with mask mode");
+
+	rpp_init_mask(&ctx, mask);
+
+	status_init(NULL, 0);
+
+#if 0
+	rec_restore_mode(restore_state);
+	rec_init(db, save_state);
+
+	crk_init(db, fix_state, NULL);
+#else
+	crk_init(db, NULL, NULL);
+#endif
+
+	while ((word = rpp_next(&ctx))) {
+		if (ext_filter(word))
+			if (crk_process_key(word))
+				break;
+	}
+
+	crk_done();
+
+#if 0
+	rec_done(event_abort);
+#endif
+}
diff -urpN -x arch.h -x '*.o' -x run john-1.8.0/src/mask.h john-1.8.0-mask/src/mask.h
--- john-1.8.0/src/mask.h	1970-01-01 00:00:00 +0000
+++ john-1.8.0-mask/src/mask.h	2013-06-14 23:52:55 +0000
@@ -0,0 +1,25 @@
+/*
+ * This file is part of John the Ripper password cracker,
+ * Copyright (c) 2013 by Solar Designer
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted.
+ *
+ * There's ABSOLUTELY NO WARRANTY, express or implied.
+ */
+
+/*
+ * Mask mode cracker.
+ */
+
+#ifndef _JOHN_MASK_H
+#define _JOHN_MASK_H
+
+#include "loader.h"
+
+/*
+ * Runs the mask mode cracker.
+ */
+extern void do_mask_crack(struct db_main *db, char *mask);
+
+#endif
diff -urpN -x arch.h -x '*.o' -x run john-1.8.0/src/options.c john-1.8.0-mask/src/options.c
--- john-1.8.0/src/options.c	2013-05-29 23:31:53 +0000
+++ john-1.8.0-mask/src/options.c	2013-06-14 23:11:19 +0000
@@ -40,6 +40,8 @@ static struct opt_entry opt_list[] = {
 	{"rules", FLG_RULES, FLG_RULES, FLG_WORDLIST_CHK, FLG_STDIN_CHK},
 	{"incremental", FLG_INC_SET, FLG_CRACKING_CHK,
 		0, 0, OPT_FMT_STR_ALLOC, &options.charset},
+	{"mask", FLG_MASK_SET, FLG_CRACKING_CHK,
+		0, OPT_REQ_PARAM, OPT_FMT_STR_ALLOC, &options.mask},
 	{"external", FLG_EXTERNAL_SET, FLG_EXTERNAL_CHK,
 		0, OPT_REQ_PARAM, OPT_FMT_STR_ALLOC, &options.external},
 	{"stdout", FLG_STDOUT, FLG_STDOUT,
@@ -104,6 +106,7 @@ static struct opt_entry opt_list[] = {
 "--wordlist=FILE --stdin    wordlist mode, read words from FILE or stdin\n" \
 "--rules                    enable word mangling rules for wordlist mode\n" \
 "--incremental[=MODE]       \"incremental\" mode [using section MODE]\n" \
+"--mask=MASK                mask mode using MASK\n" \
 "--external=MODE            external mode or word filter\n" \
 "--stdout[=LENGTH]          just output candidate passwords [cut at LENGTH]\n" \
 "--restore[=NAME]           restore an interrupted session [called NAME]\n" \
diff -urpN -x arch.h -x '*.o' -x run john-1.8.0/src/options.h john-1.8.0-mask/src/options.h
--- john-1.8.0/src/options.h	2013-05-29 23:31:55 +0000
+++ john-1.8.0-mask/src/options.h	2013-06-14 23:18:49 +0000
@@ -52,8 +52,11 @@
 /* Incremental mode enabled */
 #define FLG_INC_CHK			0x00000800
 #define FLG_INC_SET			(FLG_INC_CHK | FLG_CRACKING_SET)
+/* Mask mode enabled */
+#define FLG_MASK_CHK			0x00001000
+#define FLG_MASK_SET			(FLG_MASK_CHK | FLG_CRACKING_SET)
 /* External mode or word filter enabled */
-#define FLG_EXTERNAL_CHK		0x00001000
+#define FLG_EXTERNAL_CHK		0x00002000
 #define FLG_EXTERNAL_SET \
 	(FLG_EXTERNAL_CHK | FLG_ACTION | FLG_CRACKING_SUP | FLG_PWD_SUP)
 /* Batch cracker */
@@ -116,9 +119,12 @@ struct options_main {
 /* Wordlist file name */
 	char *wordlist;
 
-/* Charset file name */
+/* Incremental mode name or charset file name */
 	char *charset;
 
+/* Mask mode's mask */
+	char *mask;
+
 /* External mode or word filter name */
 	char *external;
 
diff -urpN -x arch.h -x '*.o' -x run john-1.8.0/src/rpp.c john-1.8.0-mask/src/rpp.c
--- john-1.8.0/src/rpp.c	2011-02-27 06:52:52 +0000
+++ john-1.8.0-mask/src/rpp.c	2013-06-15 00:28:53 +0000
@@ -1,6 +1,6 @@
 /*
  * This file is part of John the Ripper password cracker,
- * Copyright (c) 1996-98,2006,2009,2010,2011 by Solar Designer
+ * Copyright (c) 1996-98,2006,2009,2010,2011,2013 by Solar Designer
  */
 
 #include <string.h>
@@ -23,6 +23,14 @@ int rpp_init(struct rpp_context *ctx, ch
 	return 1;
 }
 
+void rpp_init_mask(struct rpp_context *ctx, char *mask)
+{
+	ctx->input = &ctx->dummy_list_entry;
+	ctx->input->data = mask;
+	ctx->input->next = NULL;
+	ctx->count = -1;
+}
+
 static void rpp_add_char(struct rpp_range *range, unsigned char c)
 {
 	if (range->flag_r) {
@@ -43,6 +51,7 @@ static void rpp_process_rule(struct rpp_
 {
 	struct rpp_range *range;
 	unsigned char *input, *output, *end;
+	unsigned char *saved_input;
 	unsigned char c1, c2, c;
 	int flag_p, flag_r;
 
@@ -52,6 +61,8 @@ static void rpp_process_rule(struct rpp_
 	flag_p = flag_r = 0;
 	ctx->count = ctx->refs_count = 0;
 
+	saved_input = NULL;
+
 	while (*input && output < end)
 	switch (*input) {
 	case '\\':
@@ -88,8 +99,34 @@ static void rpp_process_rule(struct rpp_
 		}
 		break;
 
+	case '?':
+		if (ctx->input != &ctx->dummy_list_entry) /* not mask mode */
+			goto not_mask;
+		if (*++input == '?')
+			goto not_mask;
+		saved_input = input + 1;
+		switch (*input) {
+		case 'l':
+			input = (unsigned char *)"[a-z]";
+			break;
+		case 'u':
+			input = (unsigned char *)"[A-Z]";
+			break;
+		case 'd':
+			input = (unsigned char *)"[0-9]";
+			break;
+		default:
+			saved_input = NULL;
+			input--;
+			goto not_mask;
+		}
+
 	case '[':
 		if (ctx->count >= RULE_RANGES_MAX) {
+			if (saved_input) {
+				input = saved_input - 2;
+				saved_input = NULL;
+			}
 			*output++ = *input++;
 			break;
 		}
@@ -130,9 +167,14 @@ static void rpp_process_rule(struct rpp_
 		}
 		if (*input) input++;
 
+		if (saved_input) {
+			input = saved_input;
+			saved_input = NULL;
+		}
 		break;
 
 	default:
+not_mask:
 		*output++ = *input++;
 	}
 
diff -urpN -x arch.h -x '*.o' -x run john-1.8.0/src/rpp.h john-1.8.0-mask/src/rpp.h
--- john-1.8.0/src/rpp.h	2010-02-23 17:06:58 +0000
+++ john-1.8.0-mask/src/rpp.h	2013-06-15 00:03:41 +0000
@@ -1,6 +1,6 @@
 /*
  * This file is part of John the Ripper password cracker,
- * Copyright (c) 1996-98,2009,2010 by Solar Designer
+ * Copyright (c) 1996-98,2009,2010,2013 by Solar Designer
  */
 
 /*
@@ -72,6 +72,9 @@ struct rpp_context {
 
 /* Character ranges */
 	struct rpp_range ranges[RULE_RANGES_MAX];
+
+/* Dummy list entry for use in mask mode */
+	struct cfg_line dummy_list_entry;
 };
 
 /*
@@ -81,6 +84,11 @@ struct rpp_context {
 extern int rpp_init(struct rpp_context *ctx, char *subsection);
 
 /*
+ * Initializes the preprocessor's context for the supplied mask.
+ */
+extern void rpp_init_mask(struct rpp_context *ctx, char *mask);
+
+/*
  * Returns a preprocessed rule and moves to the next one.
  */
 extern char *rpp_next(struct rpp_context *ctx);

Powered by blists - more mailing lists

Your e-mail address:

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