Openwall GNU/*/Linux - a small security-enhanced Linux distro for servers
[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]
Date: Wed, 6 Feb 2013 07:12:34 -0800 (PST)
From: deepika dutta <deepikadutta_19@...oo.com>
To: "john-dev@...ts.openwall.com" <john-dev@...ts.openwall.com>
Subject: Re: mschapv2-bitsliced conversion- openmp support

Hi, I came back after  a long time to John-dev to see your email. 

Actually, I worked on coverting the DES_bs_crypt_plain(), which I had added to do single DES encryption, into SSE implementation.  I have added this function into the x86-sse.S file. Since the code in this file was in assembly language, I tried some copy-pasting from previous code and added some assembly code myself to get the single DES encryption working. I compiled this program using linux-x86-64 option, everything is working fine and the latest banchmarks for bitsliced implementation are given below. You can test for yourself. The patch is attached.

**I have also implemented the single DES encryption code using sse intrinsics 
taking help from your code. This I did for my personal use :) 

Bitsliced DES code in mschapv2 banchmark.
My machine: 64 bit Ubuntu, Intel Core 2 Duo processor.

Generic-Without
 openmp 
Benchmarking: MSCHAPv2 C/R MD4 DES [DES_BS_MSCHAPv2]... DONE
Many salts:    20068K c/s real, 20068K c/s virtual
Only one salt:  
  3322K c/s real, 3322K c/s virtual

Generic-With openmp 
Benchmarking: MSCHAPv2 C/R MD4 DES [DES_BS_MSCHAPv2]... (2xOMP) DONE
Many salts:    37740K c/s real, 19060K c/s virtual
Only one salt:    5648K c/s real, 2852K c/s virtual

linux-x86-64- Without openmp
Benchmarking: MSCHAPv2 C/R MD4 DES [DES_BS_MSCHAPv2-SSE2]... DONE
Many salts:    43646K c/s real, 43646K c/s virtual
Only one salt:    4112K c/s real, 4112K c/s virtual

linux-x86-64- With openmp

Benchmarking: MSCHAPv2 C/R MD4 DES [DES_BS_MSCHAPv2-SSE2]... (2xOMP) DONE
Many salts:    79691K c/s real, 40452K c/s virtual
Only one salt:    6414K c/s real, 3256K c/s virtual


 
Cheers,
Deepika


________________________________
 From: Solar Designer <solar@...nwall.com>
To: john-dev@...ts.openwall.com 
Sent: Sunday, January 20, 2013 12:50 AM
Subject: Re: [john-dev] mschapv2-bitsliced conversion- openmp support
 
magnum -

On Sat, Jan 19, 2013 at 05:21:45PM +0100, magnum wrote:
> I feel bad about not getting Deepika's work included in Jumbo. It's a very skilled contribution compared to to the trivial OpenSSL-powered formats that we are used to. Leaving it in limbo discourages future contributions - from her and from others.

Yes, I feel bad about this too, and I agree that not properly and timely
making use of a contribution discourages further contributions.

> Besides that, it appears to give 2x on single salt and 10x on multiple salts.
> 
> I understand it's not trivial though. I am not quite sure what needs to be done to actually add it to Jumbo. Apparently it only builds using generic. Is there anything I can do, or anything we could ask Deepika to do, to help this forward?

Unfortunately, I'm still of the opinion that I'd need to work on this
myself, and it's still not at the top of my list.  However,
 if you see
how you can integrate the code in some temporary way, please feel free
to go ahead and do it.

Thanks,

Alexander
[ CONTENT OF TYPE text/html SKIPPED ]

diff -urpN john-1.7.9-jumbo-5/src/DES_bs_b.c john.new/src/DES_bs_b.c
--- john-1.7.9-jumbo-5/src/DES_bs_b.c	2011-11-19 02:57:47.000000000 +0000
+++ john.new/src/DES_bs_b.c	2013-02-04 21:06:19.993521598 +0000
@@ -1,12 +1,18 @@
 /*
  * This file is part of John the Ripper password cracker,
  * Copyright (c) 1996-2001,2003,2010,2011 by Solar Designer
+ *
+ * Addition of single DES encryption with no salt by
+ * Deepika Dutta Mishra <dipikadutta at gmail.com> in 2012, no
+ * rights reserved. 
  */
 
 #include "arch.h"
 #include "common.h"
 #include "DES_bs.h"
 
+DES_bs_vector P[64];
+
 #if DES_BS_ASM && defined(_OPENMP) && defined(__GNUC__)
 #warning Assembly code and OpenMP are both requested - will provide the former, but not the latter (for DES-based hashes).  This may likely be corrected by enabling SIMD intrinsics with the C compiler (try adding -msse2 to OMPFLAGS).
 #endif
@@ -1438,13 +1444,6 @@ static MAYBE_INLINE void DES_bs_finalize
 	}
 }
 
-#undef v1
-#undef v2
-#undef v3
-#undef v5
-#undef v6
-#undef v7
-
 #undef kd
 #if DES_BS_VECTOR_LOOPS
 #define kd				[depth]
@@ -1560,4 +1559,195 @@ void DES_bs_crypt_LM(int keys_count)
 		} while (--rounds);
 	}
 }
+
+
+#if DES_bs_mt
+static MAYBE_INLINE void DES_bs_finalize_keys_plain(int t)
+#else
+static MAYBE_INLINE void DES_bs_finalize_keys_plain(void)
+#endif
+{
+#if DES_BS_VECTOR_LOOPS_K
+	int depth;
+#endif
+
+	for_each_depth_k() {
+      DES_bs_vector *kp = (DES_bs_vector *)&DES_bs_all.K[0] DEPTH_K;
+      int ic;
+      for (ic = 0; ic < 8; ic++) {
+               DES_bs_vector *vp =
+               (DES_bs_vector *)&DES_bs_all.xkeys.v[ic][0] DEPTH_K;
+               LOAD_V
+               FINALIZE_NEXT_KEY_BIT_0
+               FINALIZE_NEXT_KEY_BIT_1
+               FINALIZE_NEXT_KEY_BIT_2
+               FINALIZE_NEXT_KEY_BIT_3
+               FINALIZE_NEXT_KEY_BIT_4
+               FINALIZE_NEXT_KEY_BIT_5
+               FINALIZE_NEXT_KEY_BIT_6
+              }
+	}
+}
+
+#undef v1
+#undef v2
+#undef v3
+#undef v5
+#undef v6
+#undef v7
+
+
+/* Single Des Encryption with no salt */
+#undef kd
+#if DES_BS_VECTOR_LOOPS
+#define kd				[depth]
+#else
+#define kd				[0]
+#endif
+
+#if DES_BS_VECTOR
+#define INDX [index]
+#else
+#define INDX
+#endif
+
+void DES_bs_crypt_plain(int keys_count)
+{
+#if DES_bs_mt
+	int t, n = (keys_count + (DES_BS_DEPTH - 1)) / DES_BS_DEPTH;
+#endif
+
+
+#ifdef _OPENMP
+#pragma omp parallel for default(none) private(t) shared(n, DES_bs_all_p, keys_count,P)
 #endif
+	for_each_t(n) {
+			ARCH_WORD **k;
+			int rounds;
+	#if DES_BS_VECTOR_LOOPS
+			int depth;
+	#endif
+			int i;
+	#if DES_BS_VECTOR
+        	int index;
+	#endif
+
+	for(i=0; i<64; i++)
+	{
+	#if DES_BS_VECTOR
+                for(index=0; index<DES_BS_VECTOR_SIZE; index++)
+	#endif
+			DES_bs_all.B[i]INDX = P[i]INDX;
+	}
+
+#if DES_bs_mt
+		DES_bs_finalize_keys_plain(t);
+#else
+		DES_bs_finalize_keys_plain();
+#endif
+
+	k = DES_bs_all.KS.p;
+	rounds = 8;
+
+	do {
+		for_each_depth()
+		s1(y(31, 0), y(0, 1), y(1, 2),
+			y(2, 3), y(3, 4), y(4, 5),
+			z(40), z(48), z(54), z(62));
+		for_each_depth()
+		s2(y(3, 6), y(4, 7), y(5, 8),
+			y(6, 9), y(7, 10), y(8, 11),
+			z(44), z(59), z(33), z(49));
+		for_each_depth()
+		s3(y(7, 12), y(8, 13), y(9, 14),
+			y(10, 15), y(11, 16), y(12, 17),
+			z(55), z(47), z(61), z(37));
+		for_each_depth()
+		s4(y(11, 18), y(12, 19), y(13, 20),
+			y(14, 21), y(15, 22), y(16, 23),
+			z(57), z(51), z(41), z(32));
+		for_each_depth()
+		s5(y(15, 24), y(16, 25), y(17, 26),
+			y(18, 27), y(19, 28), y(20, 29),
+			z(39), z(45), z(56), z(34));
+		for_each_depth()
+		s6(y(19, 30), y(20, 31), y(21, 32),
+			y(22, 33), y(23, 34), y(24, 35),
+			z(35), z(60), z(42), z(50));
+		for_each_depth()
+		s7(y(23, 36), y(24, 37), y(25, 38),
+			y(26, 39), y(27, 40), y(28, 41),
+			z(63), z(43), z(53), z(38));
+		for_each_depth()
+		s8(y(27, 42), y(28, 43), y(29, 44),
+			y(30, 45), y(31, 46), y(0, 47),
+			z(36), z(58), z(46), z(52));
+
+		for_each_depth()
+		s1(y(63, 48), y(32, 49), y(33, 50),
+			y(34, 51), y(35, 52), y(36, 53),
+			z(8), z(16), z(22), z(30));
+		for_each_depth()
+		s2(y(35, 54), y(36, 55), y(37, 56),
+			y(38, 57), y(39, 58), y(40, 59),
+			z(12), z(27), z(1), z(17));
+		for_each_depth()
+		s3(y(39, 60), y(40, 61), y(41, 62),
+			y(42, 63), y(43, 64), y(44, 65),
+			z(23), z(15), z(29), z(5));
+		for_each_depth()
+		s4(y(43, 66), y(44, 67), y(45, 68),
+			y(46, 69), y(47, 70), y(48, 71),
+			z(25), z(19), z(9), z(0));
+		for_each_depth()
+		s5(y(47, 72), y(48, 73), y(49, 74),
+			y(50, 75), y(51, 76), y(52, 77),
+			z(7), z(13), z(24), z(2));
+		for_each_depth()
+		s6(y(51, 78), y(52, 79), y(53, 80),
+			y(54, 81), y(55, 82), y(56, 83),
+			z(3), z(28), z(10), z(18));
+		for_each_depth()
+		s7(y(55, 84), y(56, 85), y(57, 86),
+			y(58, 87), y(59, 88), y(60, 89),
+			z(31), z(11), z(21), z(6));
+		for_each_depth()
+		s8(y(59, 90), y(60, 91), y(61, 92),
+			y(62, 93), y(63, 94), y(32, 95),
+			z(4), z(26), z(14), z(20));
+
+		k += 96;
+	} while (--rounds);
+}}
+#endif
+
+#ifdef INDX
+#undef INDX
+#endif
+
+#if DES_BS_VECTOR
+#define INDX [k]
+#else
+#define INDX
+#endif
+
+void DES_bs_generate_plaintext(unsigned char *plaintext)
+{
+	int i, j;
+#if DES_BS_VECTOR
+	int k;
+#endif
+
+	/* Set same plaintext for all bit layers */
+	for (i = 0; i < 64; i++) {
+		j = (int) (plaintext[i/8] >> (7-(i%8))) & 0x01;
+		if(j==1)
+				j = -1;
+#if DES_BS_VECTOR
+		for(k=0; k<DES_BS_VECTOR_SIZE; k++)
+#endif
+			P[i]INDX = j;
+		}
+}
+
+
diff -urpN john-1.7.9-jumbo-5/src/DES_bs.c john.new/src/DES_bs.c
--- john-1.7.9-jumbo-5/src/DES_bs.c	2011-12-15 20:57:19.000000000 +0000
+++ john.new/src/DES_bs.c	2013-02-04 20:19:05.615466650 +0000
@@ -1,6 +1,11 @@
 /*
  * This file is part of John the Ripper password cracker,
  * Copyright (c) 1996-2002,2005,2010,2011 by Solar Designer
+ *
+ * Addition of single DES encryption with no salt by
+ * Deepika Dutta Mishra <dipikadutta at gmail.com> in 
+ * 2012, no rights reserved.
+ *
  */
 
 #include <string.h>
@@ -35,6 +40,7 @@ int DES_bs_nt = 0;
 DES_bs_combined *DES_bs_all_p = NULL;
 #elif !DES_BS_ASM
 DES_bs_combined CC_CACHE_ALIGN DES_bs_all;
+DES_bs_vector P[64];
 #endif
 
 static unsigned char DES_LM_KP[56] = {
@@ -101,6 +107,7 @@ void DES_bs_init(int LM, int cpt)
 			k = DES_bs_all.KS.p;
 		else
 			k = DES_bs_all.KSp;
+
 #else
 		k = DES_bs_all.KS.p;
 #endif
@@ -117,7 +124,7 @@ void DES_bs_init(int LM, int cpt)
 				bit ^= 070;
 				bit -= bit >> 3;
 				bit = 55 - bit;
-				if (LM) bit = DES_LM_KP[bit];
+				if (LM == 1) bit = DES_LM_KP[bit];
 				*k++ = &DES_bs_all.K[bit] START;
 			}
 		}
@@ -130,7 +137,7 @@ void DES_bs_init(int LM, int cpt)
 			DES_bs_all.pxkeys[index] =
 			    &DES_bs_all.xkeys.c[0][index & 7][index >> 3];
 
-		if (LM) {
+		if (LM ==1) {
 			for (c = 0; c < 0x100; c++)
 #ifdef BENCH_BUILD
 			if (c >= 'a' && c <= 'z')
@@ -140,7 +147,7 @@ void DES_bs_init(int LM, int cpt)
 #else
 			DES_bs_all.E.u[c] = CP_up[c];
 #endif
-		} else {
+		} else if(LM==0) {
 			for (index = 0; index < 48; index++)
 				DES_bs_all.Ens[index] =
 				    &DES_bs_all.B[DES_E[index]];
diff -urpN john-1.7.9-jumbo-5/src/DES_bs.h john.new/src/DES_bs.h
--- john-1.7.9-jumbo-5/src/DES_bs.h	2011-11-23 06:54:50.000000000 +0000
+++ john.new/src/DES_bs.h	2013-02-04 20:19:05.615466650 +0000
@@ -71,6 +71,10 @@ typedef struct {
 	DES_bs_vector *Ens[48];	/* Pointers into B[] for non-salted E */
 } DES_bs_combined;
 
+//store plaintext//
+extern DES_bs_vector P[64];
+
+
 #if defined(_OPENMP) && !DES_BS_ASM
 #define DES_bs_mt			1
 #define DES_bs_cpt			32
@@ -180,4 +184,6 @@ extern int DES_bs_cmp_all(ARCH_WORD *bin
  */
 extern int DES_bs_cmp_one(ARCH_WORD *binary, int count, int index);
 
+extern void DES_bs_crypt_plain(int keys_count);
+extern void DES_bs_generate_plaintext(unsigned char *plaintext);
 #endif
diff -urpN john-1.7.9-jumbo-5/src/DES_std.c john.new/src/DES_std.c
--- john-1.7.9-jumbo-5/src/DES_std.c	2011-12-15 20:57:19.000000000 +0000
+++ john.new/src/DES_std.c	2013-02-04 20:19:05.615466650 +0000
@@ -269,7 +269,8 @@ unsigned char DES_E[48] = {
 	27, 28, 29, 30, 31, 0
 };
 
-static unsigned char DES_IP[64] = {
+
+unsigned char DES_IP[64] = {
 	57, 49, 41, 33, 25, 17, 9, 1,
 	59, 51, 43, 35, 27, 19, 11, 3,
 	61, 53, 45, 37, 29, 21, 13, 5,
diff -urpN john-1.7.9-jumbo-5/src/DES_std.h john.new/src/DES_std.h
--- john-1.7.9-jumbo-5/src/DES_std.h	2011-12-15 20:57:19.000000000 +0000
+++ john.new/src/DES_std.h	2013-02-04 20:19:05.615466650 +0000
@@ -25,7 +25,7 @@ extern unsigned char DES_E[48];
 extern unsigned char DES_PC1[56];
 extern unsigned char DES_ROT[16];
 extern unsigned char DES_PC2[48];
-
+extern unsigned char DES_IP[64];
 /*
  * Current key schedule.
  */
diff -urpN john-1.7.9-jumbo-5/src/MSCHAPv2_fmt_plug.c john.new/src/MSCHAPv2_fmt_plug.c
--- john-1.7.9-jumbo-5/src/MSCHAPv2_fmt_plug.c	2011-12-15 22:24:44.000000000 +0000
+++ john.new/src/MSCHAPv2_fmt_plug.c	2013-02-06 14:46:27.174595682 +0000
@@ -7,6 +7,10 @@
  * Modified for performance, OMP and utf-8 support
  * by magnum 2010-2011, no rights reserved
  *
+ * Modified for using Bitsliced DES by Deepika Dutta Mishra
+ * <dipikadutta at gmail.com> in 2012, no rights reserved. 
+ * Supports Openmp.
+ *
  * This algorithm is designed for performing brute-force cracking of the
  * MSCHAPv2 challenge/response sets exchanged during network-based
  * authentication attempts. The captured challenge/response set from these
@@ -23,7 +27,9 @@
  * http://freeradius.org/rfc/rfc2759.txt
  *
  */
-
+#include "arch.h"
+#include "DES_std.h"
+#include "DES_bs.h"
 #include <string.h>
 #ifdef _OPENMP
 #include <omp.h>
@@ -36,7 +42,6 @@
 #include "memory.h"
 
 #include "sha.h"
-#include <openssl/des.h>
 
 #ifndef uchar
 #define uchar unsigned char
@@ -44,7 +49,12 @@
 
 #define FORMAT_LABEL         "mschapv2"
 #define FORMAT_NAME          "MSCHAPv2 C/R MD4 DES"
-#define ALGORITHM_NAME       "mschapv2"
+#if DES_BS_VECTOR 
+#define ALGORITHM_NAME       "DES_BS_MSCHAPv2-SSE2"
+#else
+#define ALGORITHM_NAME       "DES_BS_MSCHAPv2"
+#endif
+
 #define BENCHMARK_COMMENT    ""
 #define BENCHMARK_LENGTH     0
 #define PLAINTEXT_LENGTH     125 /* lmcons.h - PWLEN (256) ? 127 ? */
@@ -58,13 +68,8 @@
 #define TOTAL_LENGTH         13 + USERNAME_LENGTH + CHALLENGE_LENGTH + CIPHERTEXT_LENGTH
 
 // these may be altered in init() if running OMP
-#define MIN_KEYS_PER_CRYPT	1
-#define THREAD_RATIO		256
-#ifdef _OPENMP
-#define MAX_KEYS_PER_CRYPT	0x10000
-#else
-#define MAX_KEYS_PER_CRYPT	THREAD_RATIO
-#endif
+#define MIN_KEYS_PER_CRYPT	DES_BS_DEPTH
+#define MAX_KEYS_PER_CRYPT      DES_BS_DEPTH
 
 static struct fmt_tests tests[] = {
   {"$MSCHAPv2$4c092fd3fd98236502e8591100046326$b912ce522524d33123a982cf330a57f8e953fa7974042b5d$6a4915d0ce61d42be533640a75391925$1111", "2222"},
@@ -86,30 +91,25 @@ static struct fmt_tests tests[] = {
 static uchar (*saved_plain)[PLAINTEXT_LENGTH + 1];
 static int (*saved_len);
 static uchar (*saved_key)[21];
-static uchar (*output)[PARTIAL_BINARY_SIZE];
 static uchar *challenge;
 static int keys_prepared;
+static void mschapv2_set_salt(void *salt);
 
 #include "unicode.h"
 
 static void init(struct fmt_main *pFmt)
 {
-#ifdef _OPENMP
-	int n = MIN_KEYS_PER_CRYPT * omp_get_max_threads();
-	if (n < MIN_KEYS_PER_CRYPT)
-		n = MIN_KEYS_PER_CRYPT;
-	if (n > MAX_KEYS_PER_CRYPT)
-		n = MAX_KEYS_PER_CRYPT;
-	pFmt->params.min_keys_per_crypt = n;
-	n = n * (n << 1) * THREAD_RATIO;
-	if (n > MAX_KEYS_PER_CRYPT)
-		n = MAX_KEYS_PER_CRYPT;
-	pFmt->params.max_keys_per_crypt = n;
-#endif
+
+	/* LM =2 for DES encryption with no salt and no iterations */
+	DES_bs_init(2, DES_bs_cpt);
+	#if DES_bs_mt
+		pFmt->params.min_keys_per_crypt = DES_bs_min_kpc;
+		pFmt->params.max_keys_per_crypt = DES_bs_max_kpc;
+	#endif
+
 	saved_plain = mem_calloc_tiny(sizeof(*saved_plain) * pFmt->params.max_keys_per_crypt, MEM_ALIGN_NONE);
 	saved_len = mem_calloc_tiny(sizeof(*saved_len) * pFmt->params.max_keys_per_crypt, MEM_ALIGN_WORD);
 	saved_key = mem_calloc_tiny(sizeof(*saved_key) * pFmt->params.max_keys_per_crypt, MEM_ALIGN_NONE);
-	output = mem_alloc_tiny(sizeof(*output) * pFmt->params.max_keys_per_crypt, MEM_ALIGN_WORD);
 }
 
 static int mschapv2_valid(char *ciphertext, struct fmt_main *pFmt)
@@ -202,13 +202,50 @@ static char *mschapv2_split(char *cipher
   return out;
 }
 
+static void *generate_des_format(uchar* binary)
+{
+  static ARCH_WORD block[6];
+  int chr, src,dst,i;
+  uchar value, mask;
+  ARCH_WORD *ptr;
+
+  memset(block, 0, sizeof(ARCH_WORD) * 6);
+
+  for (chr = 0; chr < 24; chr=chr + 8)
+  {
+  	dst = 0;
+  	for(i=0; i<8; i++)
+  	{
+  		value = binary[chr + i];
+  		mask = 0x80;
+
+  		for (src = 0; src < 8; src++) {
+  			if (value & mask)
+  				block[(chr/4) + (dst>>5)]|= 1 << (dst & 0x1F);
+  			mask >>= 1;
+  			dst++;
+  		}
+  	}
+  }
+
+  /* Apply initial permutation on ciphertext blocks */
+  for(i=0; i<6; i=i+2)
+  {
+	  ptr = (ARCH_WORD *)DES_do_IP(&block[i]);
+	  block[i] = ptr[1];
+	  block[i+1] = ptr[0];
+  }
+
+  return block;
+}
+
 static void *mschapv2_get_binary(char *ciphertext)
 {
-  static uchar *binary;
+  uchar *binary;
   int i;
+  ARCH_WORD *ptr;
 
-  if (!binary) binary = mem_alloc_tiny(BINARY_SIZE, MEM_ALIGN_WORD);
-
+  binary = mem_alloc_tiny(BINARY_SIZE, MEM_ALIGN_WORD);
   ciphertext += 10 + 16*2 + 1; /* Skip - $MSCHAPv2$, Authenticator Challenge */
 
   for (i=0; i<BINARY_SIZE; i++)
@@ -216,32 +253,41 @@ static void *mschapv2_get_binary(char *c
     binary[i] = (atoi16[ARCH_INDEX(ciphertext[i*2])])<<4;
     binary[i] |= (atoi16[ARCH_INDEX(ciphertext[i*2+1])]);
   }
-  return binary;
+
+  /* Set binary in DES format */
+  ptr = generate_des_format(binary);
+  return ptr;
 }
 
-static inline void setup_des_key(unsigned char key_56[], DES_key_schedule *ks)
+
+static inline void setup_des_key(unsigned char key_56[], int index)
 {
-  DES_cblock key;
+  char key[8];
+
+   /* Right shift key bytes by 1 to bring in openssl format */
+   /* Each byte of key is xored with 0x80 to pass check for 0 in DES_bs_set_key() */
 
-  key[0] = key_56[0];
-  key[1] = (key_56[0] << 7) | (key_56[1] >> 1);
-  key[2] = (key_56[1] << 6) | (key_56[2] >> 2);
-  key[3] = (key_56[2] << 5) | (key_56[3] >> 3);
-  key[4] = (key_56[3] << 4) | (key_56[4] >> 4);
-  key[5] = (key_56[4] << 3) | (key_56[5] >> 5);
-  key[6] = (key_56[5] << 2) | (key_56[6] >> 6);
-  key[7] = (key_56[6] << 1);
+   key[0] = (key_56[0] >> 1) | 0x80;
+   key[1] = (((key_56[0] << 7) | (key_56[1] >> 1)) >>1) | 0x80;
+   key[2] = (((key_56[1] << 6) | (key_56[2] >> 2)) >>1) | 0x80;
+   key[3] = (((key_56[2] << 5) | (key_56[3] >> 3)) >>1) | 0x80;
+   key[4] = (((key_56[3] << 4) | (key_56[4] >> 4)) >>1) | 0x80;
+   key[5] = (((key_56[4] << 3) | (key_56[5] >> 5)) >>1) | 0x80;
+   key[6] = (((key_56[5] << 2) | (key_56[6] >> 6)) >>1) | 0x80;
+   key[7] = ((key_56[6] << 1) >>1 ) | 0x80;
 
-  DES_set_key(&key, ks);
+  DES_bs_set_key((char*)key, index);
 }
 
+
 /* Calculate the MSCHAPv2 response for the given challenge, using the
    specified authentication identity (username), password and client
    nonce.
 */
+
 static void mschapv2_crypt_all(int count)
 {
-	DES_key_schedule ks;
+
 	int i;
 
 	if (!keys_prepared) {
@@ -258,54 +304,67 @@ static void mschapv2_crypt_all(int count
 
 			/* NULL-padding the 16-byte hash to 21-bytes is made in cmp_exact if needed */
 		}
-		keys_prepared = 1;
-	}
-
 #ifdef _OPENMP
-#pragma omp parallel for default(none) private(i, ks) shared(count, output, challenge, saved_key)
+#pragma omp parallel for
 #endif
-	for(i=0; i<count; i++) {
+		for(i=0; i<count; i++)
+		    	setup_des_key(saved_key[i], i);
 
-		/* Just do first DES for a partial binary */
-		setup_des_key(saved_key[i], &ks);
-		DES_ecb_encrypt((DES_cblock*)challenge, (DES_cblock*)output[i], &ks, DES_ENCRYPT);
+		keys_prepared = 1;
 	}
+
+	/* Bitsliced des encryption */
+	DES_bs_crypt_plain(count);
+
 }
 
+
 static int mschapv2_cmp_all(void *binary, int count)
 {
-	int index = 0;
-	for(; index<count; index++)
-		if (!memcmp(output[index], binary, PARTIAL_BINARY_SIZE))
-			return 1;
-	return 0;
+	return DES_bs_cmp_all((ARCH_WORD *)binary, count);
 }
 
 static int mschapv2_cmp_one(void *binary, int index)
 {
-	return (!memcmp(output[index], binary, PARTIAL_BINARY_SIZE));
+	return DES_bs_cmp_one((ARCH_WORD *)binary, 32, index);
 }
 
 static int mschapv2_cmp_exact(char *source, int index)
 {
-	DES_key_schedule ks;
-	uchar binary[24];
+
+	ARCH_WORD *binary;
 
 	/* NULL-pad 16-byte NTLM hash to 21-bytes (postponed until now) */
 	memset(&saved_key[index][16], 0, 5);
 
-	/* Split resultant value into three 7-byte thirds
-	   DES-encrypt challenge using each third as a key
-	   Concatenate three 8-byte resulting values to form 24-byte LM response
-	*/
-	setup_des_key(saved_key[index], &ks);
-	DES_ecb_encrypt((DES_cblock*)challenge, (DES_cblock*)binary, &ks, DES_ENCRYPT);
-	setup_des_key(&saved_key[index][7], &ks);
-	DES_ecb_encrypt((DES_cblock*)challenge, (DES_cblock*)&binary[8], &ks, DES_ENCRYPT);
-	setup_des_key(&saved_key[index][14], &ks);
-	DES_ecb_encrypt((DES_cblock*)challenge, (DES_cblock*)&binary[16], &ks, DES_ENCRYPT);
+	binary = mschapv2_get_binary(source);
+	if (!DES_bs_cmp_one(binary, 64, index))
+	{
+		setup_des_key(saved_key[0], 0);
+		return 0;
+	}
+
+	setup_des_key(&saved_key[index][7], 0);
+	DES_bs_crypt_plain(1);
+	binary = mschapv2_get_binary(source);
+	if (!DES_bs_cmp_one(&binary[2], 64, 0))
+	{
+		setup_des_key(saved_key[0], 0);
+		return 0;
+	}
+
+
+	setup_des_key(&saved_key[index][14], 0);
+	DES_bs_crypt_plain(1);
+	binary = mschapv2_get_binary(source);
+	if (!DES_bs_cmp_one(&binary[4], 64, 0))
+	{
+		setup_des_key(saved_key[0], 0);
+		return 0;
+	}
 
-	return !memcmp(binary, mschapv2_get_binary(source), BINARY_SIZE);
+	setup_des_key(saved_key[0], 0);
+	return 1;
 }
 
 /* We're essentially using three salts, but we're going to generate a single value here for later use.
@@ -316,11 +375,15 @@ static void *mschapv2_get_salt(char *cip
   static unsigned char binary_salt[SALT_SIZE];
   static SHA_CTX ctx;
   unsigned char tmp[16];
-  int i;
+  int i, cnt;
+  uchar j;
   char *pos = NULL;
   unsigned char digest[20];
+  unsigned char temp[SALT_SIZE];
 
   memset(binary_salt, 0, SALT_SIZE);
+  memset(temp, 0, SALT_SIZE);
+
   memset(digest, 0, 20);
   SHA1_Init(&ctx);
 
@@ -351,12 +414,22 @@ static void *mschapv2_get_salt(char *cip
   SHA1_Final(digest, &ctx);
   memcpy(binary_salt, digest, SALT_SIZE);
 
+  /* Apply IP to salt */
+  for (i = 0; i < 64; i++) {
+  		cnt = DES_IP[i ^ 0x20];
+  		j = (uchar)((binary_salt[cnt >> 3] >> (7 - (cnt & 7))) & 1);
+  		temp[i/8] |= j << (7 - (i % 8));
+  }
+
+  memcpy(binary_salt, temp, SALT_SIZE);
   return (void*)binary_salt;
 }
 
 static void mschapv2_set_salt(void *salt)
 {
-	challenge = salt;
+	challenge = salt; 
+	DES_bs_generate_plaintext(challenge);
+
 }
 
 static void mschapv2_set_key(char *key, int index)
@@ -378,52 +451,52 @@ static int salt_hash(void *salt)
 
 static int binary_hash_0(void *binary)
 {
-	return *(ARCH_WORD_32 *)binary & 0xF;
+	return *(ARCH_WORD *)binary & 0xF;
 }
 
 static int binary_hash_1(void *binary)
 {
-	return *(ARCH_WORD_32 *)binary & 0xFF;
+	return *(ARCH_WORD *)binary & 0xFF;
 }
 
 static int binary_hash_2(void *binary)
 {
-	return *(ARCH_WORD_32 *)binary & 0xFFF;
+	return *(ARCH_WORD *)binary & 0xFFF;
 }
 
 static int binary_hash_3(void *binary)
 {
-	return *(ARCH_WORD_32 *)binary & 0xFFFF;
+	return *(ARCH_WORD *)binary & 0xFFFF;
 }
 
 static int binary_hash_4(void *binary)
 {
-	return *(ARCH_WORD_32 *)binary & 0xFFFFF;
+	return *(ARCH_WORD *)binary & 0xFFFFF;
 }
 
 static int get_hash_0(int index)
 {
-	return *(ARCH_WORD_32 *)output[index] & 0xF;
+	return DES_bs_get_hash_0(index);
 }
 
 static int get_hash_1(int index)
 {
-	return *(ARCH_WORD_32 *)output[index] & 0xFF;
+	return DES_bs_get_hash_1(index);
 }
 
 static int get_hash_2(int index)
 {
-	return *(ARCH_WORD_32 *)output[index] & 0xFFF;
+	return DES_bs_get_hash_2(index);
 }
 
 static int get_hash_3(int index)
 {
-	return *(ARCH_WORD_32 *)output[index] & 0xFFFF;
+	return DES_bs_get_hash_3(index);
 }
 
 static int get_hash_4(int index)
 {
-	return *(ARCH_WORD_32 *)output[index] & 0xFFFFF;
+	return DES_bs_get_hash_4(index);
 }
 
 struct fmt_main fmt_MSCHAPv2 = {
diff -urpN john-1.7.9-jumbo-5/src/x86-64.S john.new/src/x86-64.S
--- john-1.7.9-jumbo-5/src/x86-64.S	2011-12-15 20:57:20.000000000 +0000
+++ john.new/src/x86-64.S	2013-02-04 20:19:05.619466691 +0000
@@ -42,6 +42,8 @@
 #define DES_bs_crypt			_DES_bs_crypt
 #define DES_bs_crypt_25			_DES_bs_crypt_25
 #define DES_bs_crypt_LM			_DES_bs_crypt_LM
+#define P						_P
+#define DES_bs_crypt_plain		_DES_bs_crypt_plain
 #endif
 
 #ifdef __sun
@@ -62,6 +64,11 @@
 .bss
 #endif
 
+.globl P
+DO_ALIGN(6)
+P:
+DO_SPACE(nvec(64))
+
 .globl DES_bs_all
 DO_ALIGN(6)
 DES_bs_all:
@@ -92,6 +99,7 @@ DO_SPACE(nptr(48))
 #define E(i)				DES_bs_all_E+nptr(i)(%rip)
 #define B(i)				DES_bs_all_B+nvec(i)(%rip)
 #define tmp_at(i)			DES_bs_all_tmp+nvec(i)(%rip)
+#define P(i)				P+nvec(i)
 
 #define pnot				tmp_at(0)
 
@@ -1336,6 +1344,196 @@ DES_bs_crypt_LM_loop:
 	jnz DES_bs_crypt_LM_loop
 	ret
 
+#define rounds				%eax
+
+DO_ALIGN(6)
+.globl DES_bs_crypt_plain
+DES_bs_crypt_plain:
+	movdqa mask01,%xmm7
+	movdqa mask02,%xmm8
+	leaq DES_bs_all_xkeys(%rip),v_ptr
+	movdqa mask04,%xmm9
+	movdqa mask08,%xmm10
+	leaq DES_bs_all_K(%rip),k_ptr
+	movdqa mask10,%xmm11
+	movdqa mask20,%xmm12
+	movl $8,iterations
+	movdqa mask40,%xmm13
+DES_bs_finalize_keys_plain_loop:
+	FINALIZE_NEXT_KEY_BITS_0_6
+	addq $nvec(7),k_ptr
+	addq $nvec(8),v_ptr
+	subl $1,iterations
+	jnz DES_bs_finalize_keys_plain_loop
+	leaq DES_bs_all_KS_p(%rip),k_ptr
+	leaq DES_bs_all_KS_v(%rip),v_ptr
+	
+	movdqa P(0),%xmm4
+	movdqa %xmm4,B(0)
+	movdqa P(1),%xmm4
+	movdqa %xmm4,B(1)
+	movdqa P(2),%xmm4
+	movdqa %xmm4,B(2)
+	movdqa P(3),%xmm4
+	movdqa %xmm4,B(3)
+	movdqa P(4),%xmm4
+	movdqa %xmm4,B(4)
+	movdqa P(5),%xmm4
+	movdqa %xmm4,B(5)
+	movdqa P(6),%xmm4
+	movdqa %xmm4,B(6)
+	movdqa P(7),%xmm4
+	movdqa %xmm4,B(7)
+	movdqa P(8),%xmm4
+	movdqa %xmm4,B(8)
+	movdqa P(9),%xmm4
+	movdqa %xmm4,B(9)
+	movdqa P(10),%xmm4
+	movdqa %xmm4,B(10)
+	movdqa P(11),%xmm4
+	movdqa %xmm4,B(11)
+	movdqa P(12),%xmm4
+	movdqa %xmm4,B(12)
+	movdqa P(13),%xmm4
+	movdqa %xmm4,B(13)
+	movdqa P(14),%xmm4
+	movdqa %xmm4,B(14)
+	movdqa P(15),%xmm4
+	movdqa %xmm4,B(15)
+	movdqa P(16),%xmm4
+	movdqa %xmm4,B(16)
+	movdqa P(17),%xmm4
+	movdqa %xmm4,B(17)
+	movdqa P(18),%xmm4
+	movdqa %xmm4,B(18)
+	movdqa P(19),%xmm4
+	movdqa %xmm4,B(19)
+	movdqa P(20),%xmm4
+	movdqa %xmm4,B(20)
+	movdqa P(21),%xmm4
+	movdqa %xmm4,B(21)
+	movdqa P(22),%xmm4
+	movdqa %xmm4,B(22)
+	movdqa P(23),%xmm4
+	movdqa %xmm4,B(23)
+	movdqa P(24),%xmm4
+	movdqa %xmm4,B(24)
+	movdqa P(25),%xmm4
+	movdqa %xmm4,B(25)
+	movdqa P(26),%xmm4
+	movdqa %xmm4,B(26)
+	movdqa P(27),%xmm4
+	movdqa %xmm4,B(27)
+	movdqa P(28),%xmm4
+	movdqa %xmm4,B(28)
+	movdqa P(29),%xmm4
+	movdqa %xmm4,B(29)
+	movdqa P(30),%xmm4
+	movdqa %xmm4,B(30)
+	movdqa P(31),%xmm4
+	movdqa %xmm4,B(31)
+	movdqa P(32),%xmm4
+	movdqa %xmm4,B(32)
+	movdqa P(33),%xmm4
+	movdqa %xmm4,B(33)
+	movdqa P(34),%xmm4
+	movdqa %xmm4,B(34)
+	movdqa P(35),%xmm4
+	movdqa %xmm4,B(35)
+	movdqa P(36),%xmm4
+	movdqa %xmm4,B(36)
+	movdqa P(37),%xmm4
+	movdqa %xmm4,B(37)
+	movdqa P(38),%xmm4
+	movdqa %xmm4,B(38)
+	movdqa P(39),%xmm4
+	movdqa %xmm4,B(39)
+	movdqa P(40),%xmm4
+	movdqa %xmm4,B(40)
+	movdqa P(41),%xmm4
+	movdqa %xmm4,B(41)
+	movdqa P(42),%xmm4
+	movdqa %xmm4,B(42)
+	movdqa P(43),%xmm4
+	movdqa %xmm4,B(43)
+	movdqa P(44),%xmm4
+	movdqa %xmm4,B(44)
+	movdqa P(45),%xmm4
+	movdqa %xmm4,B(45)
+	movdqa P(46),%xmm4
+	movdqa %xmm4,B(46)
+	movdqa P(47),%xmm4
+	movdqa %xmm4,B(47)
+	movdqa P(48),%xmm4
+	movdqa %xmm4,B(48)
+	movdqa P(49),%xmm4
+	movdqa %xmm4,B(49)
+	movdqa P(50),%xmm4
+	movdqa %xmm4,B(50)
+	movdqa P(51),%xmm4
+	movdqa %xmm4,B(51)
+	movdqa P(52),%xmm4
+	movdqa %xmm4,B(52)
+	movdqa P(53),%xmm4
+	movdqa %xmm4,B(53)
+	movdqa P(54),%xmm4
+	movdqa %xmm4,B(54)
+	movdqa P(55),%xmm4
+	movdqa %xmm4,B(55)
+	movdqa P(56),%xmm4
+	movdqa %xmm4,B(56)
+	movdqa P(57),%xmm4
+	movdqa %xmm4,B(57)
+	movdqa P(58),%xmm4
+	movdqa %xmm4,B(58)
+	movdqa P(59),%xmm4
+	movdqa %xmm4,B(59)
+	movdqa P(60),%xmm4
+	movdqa %xmm4,B(60)
+	movdqa P(61),%xmm4
+	movdqa %xmm4,B(61)
+	movdqa P(62),%xmm4
+	movdqa %xmm4,B(62)
+	movdqa P(63),%xmm4
+	movdqa %xmm4,B(63)
+	movl $8,rounds
+DES_bs_crypt_plain_loop:
+	xor_B_KS_p(31, 0, 0, 1, 1, 2, 2, 3, 3, 4, 4, 5)
+	S1(B(40), B(48), B(54), B(62))
+	xor_B_KS_p(3, 6, 4, 7, 5, 8, 6, 9, 7, 10, 8, 11)
+	S2(B(44), B(59), B(33), B(49))
+	xor_B_KS_p(7, 12, 8, 13, 9, 14, 10, 15, 11, 16, 12, 17)
+	S3(B(55), B(47), B(61), B(37))
+	xor_B_KS_p(11, 18, 12, 19, 13, 20, 14, 21, 15, 22, 16, 23)
+	S4(B(57), B(51), B(41), B(32))
+	xor_B_KS_p(15, 24, 16, 25, 17, 26, 18, 27, 19, 28, 20, 29)
+	S5(B(39), B(45), B(56), B(34))
+	xor_B_KS_p(19, 30, 20, 31, 21, 32, 22, 33, 23, 34, 24, 35)
+	S6(B(35), B(60), B(42), B(50))
+	xor_B_KS_p(23, 36, 24, 37, 25, 38, 26, 39, 27, 40, 28, 41)
+	S7(B(63), B(43), B(53), B(38))
+	xor_B_KS_p(27, 42, 28, 43, 29, 44, 30, 45, 31, 46, 0, 47)
+	S8(B(36), B(58), B(46), B(52))
+	xor_B_KS_p(63, 48, 32, 49, 33, 50, 34, 51, 35, 52, 36, 53)
+	S1(B(8), B(16), B(22), B(30))
+	xor_B_KS_p(35, 54, 36, 55, 37, 56, 38, 57, 39, 58, 40, 59)
+	S2(B(12), B(27), B(1), B(17))
+	xor_B_KS_p(39, 60, 40, 61, 41, 62, 42, 63, 43, 64, 44, 65)
+	S3(B(23), B(15), B(29), B(5))
+	xor_B_KS_p(43, 66, 44, 67, 45, 68, 46, 69, 47, 70, 48, 71)
+	S4(B(25), B(19), B(9), B(0))
+	xor_B_KS_p(47, 72, 48, 73, 49, 74, 50, 75, 51, 76, 52, 77)
+	S5(B(7), B(13), B(24), B(2))
+	xor_B_KS_p(51, 78, 52, 79, 53, 80, 54, 81, 55, 82, 56, 83)
+	S6(B(3), B(28), B(10), B(18))
+	xor_B_KS_p(55, 84, 56, 85, 57, 86, 58, 87, 59, 88, 60, 89)
+	S7(B(31), B(11), B(21), B(6))
+	xor_B_KS_p(59, 90, 60, 91, 61, 92, 62, 93, 63, 94, 32, 95)
+	addq $nptr(96),k_ptr
+	S8(B(4), B(26), B(14), B(20))
+	subl $1,rounds
+	jnz DES_bs_crypt_plain_loop
+	ret
 #endif
 
 #if defined(CPU_REQ_AVX) || defined(CPU_REQ_XOP)
diff -urpN john-1.7.9-jumbo-5/src/x86-sse.S john.new/src/x86-sse.S
--- john-1.7.9-jumbo-5/src/x86-sse.S	2011-12-15 20:57:20.000000000 +0000
+++ john.new/src/x86-sse.S	2013-02-04 20:19:05.619466691 +0000
@@ -23,6 +23,10 @@
  *
  * ...with changes in the jumbo patch, by Alain Espinosa (starting with a
  * comment further down this file).
+ * 
+ *
+ * Addition of single DES encryption with no salt by Deepika Dutta Mishra 
+ * <dipikadutta at gmail.com> in 2012, no rights reserved.
  */
 
 #include "arch.h"
@@ -54,6 +58,8 @@
 #define DES_bs_crypt			_DES_bs_crypt
 #define DES_bs_crypt_25			_DES_bs_crypt_25
 #define DES_bs_crypt_LM			_DES_bs_crypt_LM
+#define P						_P
+#define DES_bs_crypt_plain		_DES_bs_crypt_plain
 #endif
 
 #ifdef __sun
@@ -74,6 +80,10 @@
 .bss
 #endif
 
+DO_ALIGN(6)
+.global P
+DO_SPACE(nptr(64))
+
 .globl DES_bs_all
 DO_ALIGN(6)
 DES_bs_all:
@@ -1389,8 +1399,87 @@ DES_bs_crypt_LM_loop:
 	popl %esi
 	ret
 
-#endif
+DO_ALIGN(6)
+copy:
+        pushl   %ebp
+        movl    %esp, %ebp
+        subl    $16, %esp
+        movl    $P, -8(%ebp)
+        movl    $B, -4(%ebp)
+        movl    $0, -12(%ebp)
+        jmp     .L2
+.L3:
+        movl    -12(%ebp), %eax
+        sall    $4, %eax
+        addl    -4(%ebp), %eax
+        movl    -12(%ebp), %edx
+        sall    $4, %edx
+        addl    -8(%ebp), %edx
+        movaps  (%edx), %xmm0
+        movaps  %xmm0, (%eax)
+        addl    $1, -12(%ebp)
+.L2:
+        cmpl    $63, -12(%ebp)
+        jle     .L3
+        leave
+        ret
+
 
+DO_ALIGN(6)
+.globl DES_bs_crypt_plain
+DES_bs_crypt_plain:
+	copy
+	movl $DES_bs_all_xkeys,v_ptr
+	movl $DES_bs_all_K,k_ptr
+DES_bs_finalize_keys_plain_loop:
+	FINALIZE_NEXT_KEY_BITS_0_6
+	addl $nvec(7),k_ptr
+	cmpl $DES_bs_all_K+nvec(56),k_ptr
+	jb DES_bs_finalize_keys_plain_loop
+	pxor zero,zero
+	pushl %esi
+	pcmpeqd ones,ones
+	movl $DES_bs_all_KS_p,k_ptr
+DES_bs_crypt_plain_loop:
+	xor_B_KS_p(31, 0, 0, 1, 1, 2, 2, 3, 3, 4, 4, 5)
+	S1(B(40), B(48), B(54), B(62), a6_p)
+	xor_B_KS_p(3, 6, 4, 7, 5, 8, 6, 9, 7, 10, 8, 11)
+	S2(B(44), B(59), B(33), B(49), a6_p)
+	xor_B_KS_p(7, 12, 8, 13, 9, 14, 10, 15, 11, 16, 12, 17)
+	S3(B(55), B(47), B(61), B(37), a6_p)
+	xor_B_KS_p(11, 18, 12, 19, 13, 20, 14, 21, 15, 22, 16, 23)
+	S4(B(57), B(51), B(41), B(32), a6_p)
+	xor_B_KS_p(15, 24, 16, 25, 17, 26, 18, 27, 19, 28, 20, 29)
+	S5(B(39), B(45), B(56), B(34), a6_p)
+	xor_B_KS_p(19, 30, 20, 31, 21, 32, 22, 33, 23, 34, 24, 35)
+	S6(B(35), B(60), B(42), B(50), a6_p)
+	xor_B_KS_p(23, 36, 24, 37, 25, 38, 26, 39, 27, 40, 28, 41)
+	S7(B(63), B(43), B(53), B(38), a6_p)
+	xor_B_KS_p(27, 42, 28, 43, 29, 44, 30, 45, 31, 46, 0, 47)
+	S8(B(36), B(58), B(46), B(52), a6_p)
+	xor_B_KS_p(63, 48, 32, 49, 33, 50, 34, 51, 35, 52, 36, 53)
+	S1(B(8), B(16), B(22), B(30), a6_p)
+	xor_B_KS_p(35, 54, 36, 55, 37, 56, 38, 57, 39, 58, 40, 59)
+	S2(B(12), B(27), B(1), B(17), a6_p)
+	xor_B_KS_p(39, 60, 40, 61, 41, 62, 42, 63, 43, 64, 44, 65)
+	S3(B(23), B(15), B(29), B(5), a6_p)
+	xor_B_KS_p(43, 66, 44, 67, 45, 68, 46, 69, 47, 70, 48, 71)
+	S4(B(25), B(19), B(9), B(0), a6_p)
+	xor_B_KS_p(47, 72, 48, 73, 49, 74, 50, 75, 51, 76, 52, 77)
+	S5(B(7), B(13), B(24), B(2), a6_p)
+	xor_B_KS_p(51, 78, 52, 79, 53, 80, 54, 81, 55, 82, 56, 83)
+	S6(B(3), B(28), B(10), B(18), a6_p)
+	xor_B_KS_p(55, 84, 56, 85, 57, 86, 58, 87, 59, 88, 60, 89)
+	S7(B(31), B(11), B(21), B(6), a6_p)
+	xor_B_KS_p(59, 90, 60, 91, 61, 92, 62, 93, 63, 94, 32, 95)
+	addl $nptr(96),k_ptr
+	S8(B(4), B(26), B(14), B(20), a6_p)
+	decl rounds
+	jnz DES_bs_crypt_LM_loop
+	popl %esi
+	ret
+
+#endif
 
 /* The following was written by Alain Espinosa <alainesp at gmail.com> in 2007.
  * No copyright is claimed, and the software is hereby placed in the public domain.

Powered by blists - more mailing lists

Your e-mail address:

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