>From 741d9b7a46908f2dffc310e1bfa8f71c953f4ca6 Mon Sep 17 00:00:00 2001
From: Frank Dittrich <frank_dittrich@hotmail.com>
Date: Mon, 18 Jun 2012 01:15:56 +0200
Subject: [PATCH] Implement --markov=MODE[:<options>]

---
 doc/MARKOV               |   85 ++++++++++++++----
 run/john.bash_completion |   29 ++++++-
 run/john.conf            |   10 ++-
 src/mkv.c                |  227 ++++++++++++++++++++++++++++++++++-----------
 src/options.c            |    2 +-
 5 files changed, 276 insertions(+), 77 deletions(-)

diff --git a/doc/MARKOV b/doc/MARKOV
index def07a3..0a846ff 100644
--- a/doc/MARKOV
+++ b/doc/MARKOV
@@ -1,19 +1,44 @@
 BASIC USAGE
 The Markov mode is based from [1], tested and applied to "classical" password
 cracking in [2]. This mode similar to the "wordlist" mode because it will only
-crack a fixed quantity of passwords. Its parameters are:
+crack a fixed quantity of passwords.
 
---markov:LEVEL:START:END:LENGTH
+Specify the --markov option on the ommand line to use Markov mode.
+
+You can use any of these forms of the --markov option
+
+--markov[=LEVEL[:START[:END[:LENGTH]]]]
+--markov=MODE[:LEVEL[:START[:END[:LENGTH]]]]
 
 Where:
-* LEVEL is the "Markov level". This value is the maximum strength of passwords
-that are going to be cracked. When LEVEL increases, the quantity of passwords
+* MODE is a particular Markov mode corresponding to a config file section
+[Markov:MODE]. The Markov mode name is not case sensitive.
+If the mode name is not specified, the default mode as specified in section
+[Markov:Default] is used.
+
+* LEVEL is the "Markov level".
+It can be specified as MIN_LEVEL-MAX_LEVEL or as MAX_LEVEL.
+MAX_LEVEL determines the maximum strength of passwords
+that are going to be cracked. When MAX_LEVEL increases, the quantity of passwords
 that are going to be tested increases exponentially.
+MIN_LEVEL determines the minimum strength of passwords that are generated.
+If LEVEL is 0 or not specified on the command line, the LEVEL interval is
+read from config variables in the [Markov:mode] section, or [Markov:Default] section
+if MODE is not specified on the command line, see CONFIGURATION OPTIONS.
+
 * START is the index of the first password that is going to be tested, starting
 with 0.
+
 * END is the index of the last password that is going to be tested. When it is
 set to 0, it will represent the last possible password.
-* LENGTH is the maximum length of the tested passwords.
+
+* LENGTH determines the length of passwords generated.
+It can be specified as MIN_LENGTH-MAX_LENGTH or as MAX_LENGTH.
+MAX_LENGTH the maximum length of the tested passwords.
+MIN_LENGTH is the minimum length of the tested passwords.
+If LENGTH is 0 or not specified on the command line, the LENGTH interval is
+read from config variables in the [Markov:mode] section, or [Markov:Default] section
+if MODE is not specified on the command line, see CONFIGURATION OPTIONS.
 
 using --markov:100:0:0:12 will let john check every password whose length is 12
 or less and whose "Markov strength" is 100 or less.
@@ -78,34 +103,58 @@ Default options for values not specified on the command line are available
 in the john.conf file.
 Unlike previous john versions which required these values to be specified
 in the general [Options] section, starting from this version, these values
-have to be specified in the [Markov:Default] secion.
+have to be specified in the [Markov:Default] secion, if MODE has not been
+specified on the command line.
+Otherwise the Markov options have to be specified in a config file section
+[Markov:MODE].
+
 
 These are the values that can be specified:
 
 Statsfile - This is the path of the "stat" file.
 
-Specifying a Statsfile in the [Markov:Default] section is mandatory 
-for Markov mode, because the Statsfile cannot be specified as a 
-command line parameter with --markov=<params>.
+Specifying a Statsfile is mandatory for Markov mode, because the Statsfile
+cannot be specified as a command line parameter with --markov=<params>.
+
+MkvLvl - the default max. level
+
+MkvLvl should be specified, as a fallback for the maximum Markov level
+when using --markov or --markov=mode (without any additional parameters),
+or if the Markov level specified on the command line is 0.
+
+MkvMaxLen - the default max. length
+
+MkvMaxLen should also be specified, as a fallback for the maximum password
+length when using --markov or --markov=mode (without any additional
+parameters), --markov=<level> or --markov=mode:<level>, or similar options
+that don't include a value for the password length, or if the password length
+specified on the command line is 0.
+
+MkvMinLvl - the default min. level
 
-MkvLvl - the default level
+This value is used to determine the min. level if no Markov level was specified
+or if the Markov level specified on the command line was 0.
+(In other words, when the max. Markov level is read from the Markov mode section,
+the min. Markov level will be read from the Markov mode section as well.)
+If it is not found, the default min. Markov level will be 0.
 
-MkvLvl should be specified in this section, as a fallback for the maximum
-Markov level when using --markov (without any additional parameters)
+MkvMinLen - the default min. length
 
-MkvMaxLen - the default length
+This value is used to determine the min. length of passwords generated if no
+password length was specified or if the password length specified on the
+command line was 0.
+(In other words, when the max. password length is read from the Markov mode
+section, the min. password length will be read from the Markov mode section
+as well.)
+If it is not found, the default min. password length will be 0.
 
-MkvMaxLen should also be specified in this section, as a fallback for the
-maximum password length when using --markov (without any additional
-parameters), --markov=<level>, or similar options that don't include a
-value for the password length.
 
 WHAT IS THE STAT FILE?
 The markov mode is based on statistical data from real passwords. This data is
 stored in the "stat" file. In order to generate a custom stat file, it is
 recommanded to use the new calc_stat command:
 
-./calc_stat "dictionnary file" stats
+./calc_stat <dictionary_file> stats
 
 
 MKVCALCPROBA USAGE
diff --git a/run/john.bash_completion b/run/john.bash_completion
index bc3b0dc..bfcca17 100644
--- a/run/john.bash_completion
+++ b/run/john.bash_completion
@@ -359,7 +359,34 @@ _john()
 			;;
 		--markov)
 			if [[ "${valopts}" == *${cur}* ]] ; then
-				COMPREPLY=( $(compgen -W "--markov --markov=LEVEL[:START[:END[:LENGTH]]]" -- ${cur}) )
+				if [[ "_${__john_completion}" == "_2" ]] ; then
+					COMPREPLY=( $(compgen -W "${cur}=" -- ${cur}) )
+					compopt -o nospace
+				else
+					# FIXME: Should I mention [MIN_LEVEL-] and [MIN_LENGTH-]?
+					#        I think not all jumbo versions support these.
+					# FIXME: How to find out whether --markov=MODE is
+					#        supported?
+					#        Assume it is supported if at least one
+					#        section [Markov:mode] exists, e.g. [Markov:Default]?
+					COMPREPLY=( $(compgen -W "--markov --markov=LEVEL[:START[:END[:LENGTH]]] --markov=MODE --markov=MODE:LEVEL[:START[:END[:LENGTH]]]" -- ${cur}) )
+				fi
+			fi
+			return 0
+			;;
+		-?(-)mar?(k|ko|kov)+(:|=)*)
+			if [[ "${valopts}" == *--markov* ]] ; then
+				# Ignore the  --markov=[MINLVL-]LEVEL[:START[:END[:[MINLEN-]LENGTH]]]?
+				# Just try completion for --markov=MODE for all [Markov:...] sections?
+				if [[ "${hidden}" == *--list=* || "${valopts}" == *--list=* ]] ; then
+					cur=`echo ${cur#*[=:]}|LC_ALL=C tr A-Z a-z`
+					# Don't include subsection names that contain a ':' or that
+					# contain just '-' and digits
+					list=`${first} --list=Markov 2>/dev/null | LC_ALL=C sed 's#^.*:.*$##'|LC_ALL=C sed 's#^[-0-9]*$##'`
+					COMPREPLY=( $(compgen -W "${list}" -- ${cur}) )
+					# no trailing space, just in case the user wants to add :lvl...
+					compopt -o nospace
+				fi
 			fi
 			return 0
 			;;
diff --git a/run/john.conf b/run/john.conf
index 077f3ad..eaa937b 100644
--- a/run/john.conf
+++ b/run/john.conf
@@ -91,8 +91,11 @@ Device = 0
 #cryptsha512_LWS = 64
 #cryptsha512_GWS = 8192
 
+
+# Markov modes, see ../doc/MARKOV for more information
 [Markov:Default]
 # Default Markov mode settings
+#
 # Statsfile cannot be specified on the command line, so 
 # specifying it here is mandatory
 Statsfile = $JOHN/stats
@@ -100,7 +103,12 @@ Statsfile = $JOHN/stats
 # --markov usage without specifying LEVEL and/or LENGTH on the command line
 MkvLvl = 200
 MkvMaxLen = 12
-
+# MkvMinLvl and MkvMinLen should not be specified at all in [Markov:Default],
+# or they should be equal to 0 (which is the default if not specified.
+# MkvMinLvl and MkvMinLen can be used in other Markov mode sections
+# except [Markov:Default]
+; MkvMinLvl = 0
+; MkvMinLen = 0
 
 # A user defined character class is named with a single digit, ie. 0..9. After
 # the equal-sign, just list all characters that this class should match. You
diff --git a/src/mkv.c b/src/mkv.c
index 46fe0fd..8c52e47 100644
--- a/src/mkv.c
+++ b/src/mkv.c
@@ -1,6 +1,8 @@
 /*
  * This software is Copyright © 2010 bartavelle, <bartavelle at bandecon.com>, and it is hereby released to the general public under the following terms:
  * Redistribution and use in source and binary forms, with or without modification, are permitted.
+ *
+ * Added --markov=MODE[:<options>] support and other minor adjustments, 2012, Frank Dittrich
  */
 
 #include <stdio.h>
@@ -241,33 +243,95 @@ static int get_progress(int *hundth_perc)
 
 void get_markov_options(struct db_main *db,
                         char *mkv_param,
-                        unsigned int *minlevel, unsigned int *level,
+                        unsigned int *mkv_minlevel, unsigned int *mkv_level,
                         unsigned long long *start, unsigned long long *end,
-                        unsigned int *minlen, unsigned int *maxlen,
+                        unsigned int *mkv_minlen, unsigned int *mkv_maxlen,
                         char **statfile)
 {
-	//struct cfg_section *section;
-	char *token;
-	//char *mode;
+	char * mode = NULL;
+	char *lvl_token = NULL;
+	char *start_token = NULL;
+	char *end_token = NULL;
+	char *len_token = NULL;
+	char *dummy_token = NULL;
+
+	int minlevel, level, minlen, maxlen;
 
-	*level = 0;
 	*start = 0;
 	*end = 0;
-	*maxlen = 0;
-	*minlevel = 0;
-	*minlen = 0;
 
-	if(cfg_get_section(SECTION_MARKOV, SUBSECTION_DEFAULT) == NULL)
+	minlevel = -1;
+	level = -1;
+	minlen = -1;
+	maxlen = -1;
+
+/*
+ * FIXME: strsep() is not portable enough!
+ *        I would prefer it over strtok(), to allow something like
+ *        --markov=mode:0:0:0:10-15
+ *        or
+ *        --markov=mode::0:10000000
+ *        --markov=mode::10000000:20000000
+ *        --markov=mode::20000000:30000000
+ *        instead of
+ *        --markov=mode:0:0:10000000
+ *        --markov=mode:0:10000000:20000000
+ *        --markov=mode:0:20000000:30000000
+ *
+ *        For now, live with strtok(), may be later I need a replacement
+ *        for strsep().
+ */
+	if (mkv_param)
+	{
+		int i;
+		lvl_token = strtok(mkv_param, ":");
+		/* 
+		 * If the first token contains anything else than digits
+		 * (for the Markov level) or '-' (for a level interval),
+		 * then treat it as a section name, and use the next token
+		 * as the Markov level (or level interval)
+		 */
+		for(i = 0; mode == NULL && lvl_token[i] != '\0'; i++)
+		{
+			if((lvl_token[i] < '0' || lvl_token[i] > '9') && lvl_token[i] != '-')
+			{
+				mode = lvl_token;
+				lvl_token = strtok(NULL, ":");
+			}	
+				
+		}
+		start_token = strtok(NULL, ":");
+		end_token = strtok(NULL, ":");
+		len_token = strtok(NULL, ":");
+
+		dummy_token = strtok(NULL, ":");
+		if(dummy_token)
+		{
+#ifdef HAVE_MPI
+			if (mpi_id == 0)
+#endif
+			fprintf(stderr,
+			        "Too many markov parameters specified: %s\n",
+				dummy_token);
+			error();
+		}
+	}
+
+	if(mode == NULL)
+		mode = SUBSECTION_DEFAULT;
+
+	if(cfg_get_section(SECTION_MARKOV, mode) == NULL)
 	{
 #ifdef HAVE_MPI
 		if (mpi_id == 0)
 #endif
 		fprintf(stderr,
 		        "Section [" SECTION_MARKOV "%s] not found\n",
-		        SUBSECTION_DEFAULT);
+		        mode);
 		error();
 	}
-	*statfile = cfg_get_param(SECTION_MARKOV, SUBSECTION_DEFAULT, "Statsfile");
+
+	*statfile = cfg_get_param(SECTION_MARKOV, mode, "Statsfile");
 	if(*statfile == NULL)
 	{
 		log_event("Statsfile not defined");
@@ -276,114 +340,165 @@ void get_markov_options(struct db_main *db,
 #endif
 		fprintf(stderr,
 		        "Statsfile not defined in section ["
-		        SECTION_MARKOV SUBSECTION_DEFAULT "]\n");
+		        SECTION_MARKOV "%s]\n", mode);
 		error();
 	}
 
-	if (mkv_param)
+	if(lvl_token != NULL)
 	{
-		token = strtok(mkv_param, ":");
-		if(sscanf(token, "%d-%d", minlevel, level) != 2)
+		if(sscanf(lvl_token, "%d-%d", &minlevel, &level) != 2)
 		{
-			*minlevel = 0;
-			if (sscanf(token, "%d", level) != 1)
+			if (sscanf(lvl_token, "%d", &level) != 1)
 			{
 #ifdef HAVE_MPI
 				if (mpi_id == 0)
 #endif
-				fprintf(stderr, "Could not parse markov parameters\n");
+				fprintf(stderr, "Could not parse markov level\n");
 				error();
 			}
+			if(level == 0)
+				/* get min. and max. level from markov section */
+				minlevel = -1;
+			else
+				minlevel = 0;
+
 		}
-		token = strtok(NULL, ":");
-		if( (token != NULL) && (sscanf(token, LLd, start)==1) )
+		if((start_token != NULL) && (sscanf(start_token, LLd, start)==1) )
 		{
-			token = strtok(NULL, ":");
-			if( (token != NULL) && (sscanf(token, LLd, end)==1) )
+			if((end_token != NULL) && (sscanf(end_token, LLd, end)==1) )
 			{
-				token = strtok(NULL, ":");
-				if( (token != NULL) && (sscanf(token, "%d-%d", minlen, maxlen)!=2) )
+				if( (len_token != NULL) && (sscanf(len_token, "%d-%d", &minlen, &maxlen)!=2) )
 				{
-					*minlen = 0;
-					sscanf(token, "%d", maxlen);
+					sscanf(len_token, "%d", &maxlen);
+					if(maxlen == 0)
+						/* get min. and max. length from markov section */
+						minlen = -1;
+					else
+						minlen = 0;
 				}
 			}
+			else if(end_token != NULL)
+			{
+#ifdef HAVE_MPI
+				if (mpi_id == 0)
+#endif
+				fprintf(stderr,
+				        "invalid end: %s\n", end_token);
+				error();
+			}
+		}
+		/*
+		 * Currently I see no use case for MkvStart and MkvEnd as variables
+		 * in a [Markov:mode] section.
+		 * If that changes, I'll need 
+		 * start_token = cfg_get_param(SECTION_MARKOV, mode, "MkvStart")
+		 * and
+		 * sscanf(start_token, LLd, start)
+		 * because the values could be too large for integers
+		 */
+		else if(start_token != NULL)
+		{
+#ifdef HAVE_MPI
+			if (mpi_id == 0)
+#endif
+			fprintf(stderr,
+			        "invalid start: %s\n", start_token);
+			error();
+
 		}
+			
 	}
 
-	if(*level == 0)
-		if( (*level = cfg_get_int(SECTION_MARKOV, SUBSECTION_DEFAULT, "MkvLvl")) == -1 )
+	if(level <= 0)
+		if( (level = cfg_get_int(SECTION_MARKOV, mode, "MkvLvl")) == -1 )
 		{
 			log_event("no markov level defined!");
 #ifdef HAVE_MPI
 			if (mpi_id == 0)
 #endif
-			fprintf(stderr, "no markov level defined!\n");
+			fprintf(stderr,
+			        "no markov level defined in section [" SECTION_MARKOV "%s]\n",
+				mode);
 			error();
 		}
 
-	if (*level > MAX_MKV_LVL) {
-		log_event("! Level = %d is too large (max=%d)", *level, MAX_MKV_LVL);
+	if (level > MAX_MKV_LVL) {
+		log_event("! Level = %d is too large (max=%d)", level, MAX_MKV_LVL);
+#ifdef HAVE_MPI
+		if (mpi_id == 0)
+#endif
+		fprintf(stderr, "Warning: Level = %d is too large (max = %d)\n", level, MAX_MKV_LVL);
+		level = MAX_MKV_LVL;
+	}
+
+	if(minlevel < 0)
+		if( (minlevel = cfg_get_int(SECTION_MARKOV, mode, "MkvMinLvl")) == -1 )
+			minlevel = 0;
+
+	if(level<minlevel)
+	{
 #ifdef HAVE_MPI
 		if (mpi_id == 0)
 #endif
-		fprintf(stderr, "Warning: Level = %d is too large (max = %d)\n", *level, MAX_MKV_LVL);
-		*level = MAX_MKV_LVL;
+		fprintf(stderr, "Warning: max level(%d) < min level(%d), min level set to %d\n", level, minlevel, level);
+		minlevel = level;
 	}
 
-	if(*maxlen == 0)
-		if( (*maxlen = cfg_get_int(SECTION_MARKOV, SUBSECTION_DEFAULT, "MkvMaxLen")) == -1 )
+	if(maxlen <= 0)
+		if( (maxlen = cfg_get_int(SECTION_MARKOV, mode, "MkvMaxLen")) == -1 )
 		{
 			log_event("no markov max length defined!");
 #ifdef HAVE_MPI
 			if (mpi_id == 0)
 #endif
-			fprintf(stderr, "no markov max length defined!\n");
+			fprintf(stderr,
+			        "no markov max length defined in section [" SECTION_MARKOV "%s]\n",
+			        mode);
 			error();
 		}
 
 	if (db->format->params.plaintext_length <= MAX_MKV_LEN &&
-	    *maxlen > db->format->params.plaintext_length)
+	    maxlen > db->format->params.plaintext_length)
 	{
 		log_event("! MaxLen = %d is too large for this hash type",
-			*maxlen);
+			maxlen);
 #ifdef HAVE_MPI
 		if (mpi_id == 0)
 #endif
 		fprintf(stderr, "Warning: "
 			"MaxLen = %d is too large for the current hash type, "
 			"reduced to %d\n",
-			*maxlen, db->format->params.plaintext_length);
-		*maxlen = db->format->params.plaintext_length;
+			maxlen, db->format->params.plaintext_length);
+		maxlen = db->format->params.plaintext_length;
 	}
 	else
-	if (*maxlen > MAX_MKV_LEN)
+	if (maxlen > MAX_MKV_LEN)
 	{
-		log_event("! MaxLen = %d is too large (max=%d)", *maxlen, MAX_MKV_LEN);
+		log_event("! MaxLen = %d is too large (max=%d)", maxlen, MAX_MKV_LEN);
 #ifdef HAVE_MPI
 		if (mpi_id == 0)
 #endif
-		fprintf(stderr, "Warning: Maxlen = %d is too large (max = %d)\n", *maxlen, MAX_MKV_LEN);
-		*maxlen = MAX_MKV_LEN;
+		fprintf(stderr, "Warning: Maxlen = %d is too large (max = %d)\n", maxlen, MAX_MKV_LEN);
+		maxlen = MAX_MKV_LEN;
 	}
 
-	if(*level<*minlevel)
-	{
-#ifdef HAVE_MPI
-		if (mpi_id == 0)
-#endif
-		fprintf(stderr, "Warning: max level(%d) < min level(%d), min level set to %d\n", *level, *minlevel, *level);
-		*minlevel = *level;
-	}
-	if(*minlen > *maxlen)
+	if(minlen < 0)
+		if( (minlen = cfg_get_int(SECTION_MARKOV, mode, "MkvMinLen")) == -1 )
+			minlen = 0;
+
+	if(minlen > maxlen)
 	{
 #ifdef HAVE_MPI
 		if (mpi_id == 0)
 #endif
-		fprintf(stderr, "Warning: minimum length(%d) < maximum length(%d), minimum length set to %d\n", *minlen, *maxlen, *maxlen);
-		*minlen = *maxlen;
+		fprintf(stderr, "Warning: minimum length(%d) < maximum length(%d), minimum length set to %d\n", minlen, maxlen, maxlen);
+		minlen = maxlen;
 	}
 
+	*mkv_minlen = minlen;
+	*mkv_maxlen = maxlen;
+	*mkv_minlevel = minlevel;
+	*mkv_level = level;
 }
 void do_markov_crack(struct db_main *db, char *mkv_param)
 {
diff --git a/src/options.c b/src/options.c
index 98f148c..7dd73cb 100644
--- a/src/options.c
+++ b/src/options.c
@@ -170,7 +170,7 @@ static struct opt_entry opt_list[] = {
 "                          full list, use --list=encodings\n" \
 "--rules[=SECTION]         enable word mangling rules for wordlist mode\n" \
 "--incremental[=MODE]      \"incremental\" mode [using section MODE]\n" \
-"--markov[=LEVEL[:opts]]   \"Markov\" mode (see documentation)\n" \
+"--markov[=options]        \"Markov\" mode (see doc/MARKOV)\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" \
-- 
1.7.7.6