MSCash Algorithm

Description

What happens when you are in front of a Windows machine, which has a domain account and you can't access the domain (due to network outage or domain server shutdown)? Microsoft solved this problem by saving the hash(es) of the last user(s) that logged into the local machine. These hashes are stored in the Windows registry, by default the last 10 hashes.

Algorithm

Parameters:

Output: Hash value which is a 128 bits value(4 integers of 32 bits) .

  1. Apply NTLM Algorithm to message.
  2. Convert to Unicode the login.
  3. The output of 2 is append to the hash of 1 and apply MD4 Algorithm.

Weakness

This algorithm is better that NTLM Algorithm but also have some weakness like:

  1. Weak salt: Logins aren't random. Exist one important login: “administrator” and you could perform a “rainbow attack” on it. The program “Cain and Abel” use that.
  2. Salt applied very last: The NTLM Algorithm part could make once for all salts.
  3. Second round very informative: In the second round only 25% of the message is unknown.

Secure message length

Modern computer perform at 5 millions of MSCash login-hash/sec aprox. Some calculations:

There are 95 characters printable(this are almost all used in passwords).
With length = 7: 957/5 millions = 162 days

Lower case letter and numbers are 36.
With length = 8: 368/5 millions = 6.6 days

Lower case letter are 26.
With length = 9: 269/5 millions = 12.6 days

This simple calculations means that a MSCash secure password need to be at least 10 character length.

Implementation's optimizations

  1. MD4 cycle eliminate:.
  2. NTLM hash once calculated:.
  3. Accumulative sum reverted:.
  4. Step 48 reverted:.
  5. Calculation on-demand of steps:.
  6. Calculation of constants:.

Sample Code

/* 
Written by Alain Espinosa <alainesp@gmail.com> in 2008
and placed in the public domain.
 
This file contain 6 functions:
1- prepare_key: which take the string to hash and convert to Unicode
and apply the padding rule of MD4. This is save in nt_buffer variable.
2- prepare_login: which take the user login, convert to Unicode
and apply the padding rule of MD4. This is save in login_buffer variable.
3- md4_crypt: which take the nt_buffer and apply the compress function of MD4.
4- mscash_crypt: which take the message and the login and perform mscash hash.
5- convert_hex: which convert the binary output in hexadecimal string. The same format
that exist in John the Ripper files.
6- main: an example of use.
 
The output are in the variable output or in hex_format if you like this one.
 
Notes:
- the mayor length of the key its 27 character. This is a restriction of this
implementation and its very simple to bypass.
- the mayor length of the login its 19 character. This is a restriction of this
implementation and its very simple to bypass.
*/
 
#include <string.h>
#include <stdio.h>
 
//Init values
#define INIT_A 0x67452301
#define INIT_B 0xefcdab89
#define INIT_C 0x98badcfe
#define INIT_D 0x10325476
 
#define SQRT_2 0x5a827999
#define SQRT_3 0x6ed9eba1
 
unsigned int nt_buffer[16];
unsigned int login_buffer[12];
unsigned int output[4];
char hex_format[33];
char itoa16[16] = "0123456789abcdef";
 
//This is the MD4 compress function
static void md4_crypt()
{
	unsigned int a = INIT_A;
	unsigned int b = INIT_B;
	unsigned int c = INIT_C;
	unsigned int d = INIT_D;
 
	/* Round 1 */
	a += (d ^ (b & (c ^ d)))  +  nt_buffer[0]  ;a = (a << 3 ) | (a >> 29);
	d += (c ^ (a & (b ^ c)))  +  nt_buffer[1]  ;d = (d << 7 ) | (d >> 25);
	c += (b ^ (d & (a ^ b)))  +  nt_buffer[2]  ;c = (c << 11) | (c >> 21);
	b += (a ^ (c & (d ^ a)))  +  nt_buffer[3]  ;b = (b << 19) | (b >> 13);
 
	a += (d ^ (b & (c ^ d)))  +  nt_buffer[4]  ;a = (a << 3 ) | (a >> 29);
	d += (c ^ (a & (b ^ c)))  +  nt_buffer[5]  ;d = (d << 7 ) | (d >> 25);
	c += (b ^ (d & (a ^ b)))  +  nt_buffer[6]  ;c = (c << 11) | (c >> 21);
	b += (a ^ (c & (d ^ a)))  +  nt_buffer[7]  ;b = (b << 19) | (b >> 13);
 
	a += (d ^ (b & (c ^ d)))  +  nt_buffer[8]  ;a = (a << 3 ) | (a >> 29);
	d += (c ^ (a & (b ^ c)))  +  nt_buffer[9]  ;d = (d << 7 ) | (d >> 25);
	c += (b ^ (d & (a ^ b)))  +  nt_buffer[10] ;c = (c << 11) | (c >> 21);
	b += (a ^ (c & (d ^ a)))  +  nt_buffer[11] ;b = (b << 19) | (b >> 13);
 
	a += (d ^ (b & (c ^ d)))  +  nt_buffer[12] ;a = (a << 3 ) | (a >> 29);
	d += (c ^ (a & (b ^ c)))  +  nt_buffer[13] ;d = (d << 7 ) | (d >> 25);
	c += (b ^ (d & (a ^ b)))  +  nt_buffer[14] ;c = (c << 11) | (c >> 21);
	b += (a ^ (c & (d ^ a)))  +  nt_buffer[15] ;b = (b << 19) | (b >> 13);
 
	/* Round 2 */
	a += ((b & (c | d)) | (c & d)) + nt_buffer[0] +SQRT_2; a = (a<<3 ) | (a>>29);
	d += ((a & (b | c)) | (b & c)) + nt_buffer[4] +SQRT_2; d = (d<<5 ) | (d>>27);
	c += ((d & (a | b)) | (a & b)) + nt_buffer[8] +SQRT_2; c = (c<<9 ) | (c>>23);
	b += ((c & (d | a)) | (d & a)) + nt_buffer[12]+SQRT_2; b = (b<<13) | (b>>19);
 
	a += ((b & (c | d)) | (c & d)) + nt_buffer[1] +SQRT_2; a = (a<<3 ) | (a>>29);
	d += ((a & (b | c)) | (b & c)) + nt_buffer[5] +SQRT_2; d = (d<<5 ) | (d>>27);
	c += ((d & (a | b)) | (a & b)) + nt_buffer[9] +SQRT_2; c = (c<<9 ) | (c>>23);
	b += ((c & (d | a)) | (d & a)) + nt_buffer[13]+SQRT_2; b = (b<<13) | (b>>19);
 
	a += ((b & (c | d)) | (c & d)) + nt_buffer[2] +SQRT_2; a = (a<<3 ) | (a>>29);
	d += ((a & (b | c)) | (b & c)) + nt_buffer[6] +SQRT_2; d = (d<<5 ) | (d>>27);
	c += ((d & (a | b)) | (a & b)) + nt_buffer[10]+SQRT_2; c = (c<<9 ) | (c>>23);
	b += ((c & (d | a)) | (d & a)) + nt_buffer[14]+SQRT_2; b = (b<<13) | (b>>19);
 
	a += ((b & (c | d)) | (c & d)) + nt_buffer[3] +SQRT_2; a = (a<<3 ) | (a>>29);
	d += ((a & (b | c)) | (b & c)) + nt_buffer[7] +SQRT_2; d = (d<<5 ) | (d>>27);
	c += ((d & (a | b)) | (a & b)) + nt_buffer[11]+SQRT_2; c = (c<<9 ) | (c>>23);
	b += ((c & (d | a)) | (d & a)) + nt_buffer[15]+SQRT_2; b = (b<<13) | (b>>19);
 
	/* Round 3 */
	a += (d ^ c ^ b) + nt_buffer[0]  +  SQRT_3; a = (a << 3 ) | (a >> 29);
	d += (c ^ b ^ a) + nt_buffer[8]  +  SQRT_3; d = (d << 9 ) | (d >> 23);
	c += (b ^ a ^ d) + nt_buffer[4]  +  SQRT_3; c = (c << 11) | (c >> 21);
	b += (a ^ d ^ c) + nt_buffer[12] +  SQRT_3; b = (b << 15) | (b >> 17);
 
	a += (d ^ c ^ b) + nt_buffer[2]  +  SQRT_3; a = (a << 3 ) | (a >> 29);
	d += (c ^ b ^ a) + nt_buffer[10] +  SQRT_3; d = (d << 9 ) | (d >> 23);
	c += (b ^ a ^ d) + nt_buffer[6]  +  SQRT_3; c = (c << 11) | (c >> 21);
	b += (a ^ d ^ c) + nt_buffer[14] +  SQRT_3; b = (b << 15) | (b >> 17);
 
	a += (d ^ c ^ b) + nt_buffer[1]  +  SQRT_3; a = (a << 3 ) | (a >> 29);
	d += (c ^ b ^ a) + nt_buffer[9]  +  SQRT_3; d = (d << 9 ) | (d >> 23);
	c += (b ^ a ^ d) + nt_buffer[5]  +  SQRT_3; c = (c << 11) | (c >> 21);
	b += (a ^ d ^ c) + nt_buffer[13] +  SQRT_3; b = (b << 15) | (b >> 17);
 
	a += (d ^ c ^ b) + nt_buffer[3]  +  SQRT_3; a = (a << 3 ) | (a >> 29);
	d += (c ^ b ^ a) + nt_buffer[11] +  SQRT_3; d = (d << 9 ) | (d >> 23);
	c += (b ^ a ^ d) + nt_buffer[7]  +  SQRT_3; c = (c << 11) | (c >> 21);
	b += (a ^ d ^ c) + nt_buffer[15] +  SQRT_3; b = (b << 15) | (b >> 17);
 
	output[0] = a + INIT_A;
	output[1] = b + INIT_B;
	output[2] = c + INIT_C;
	output[3] = d + INIT_D;
}	
 
//This is the mscash algorithm
static void mscash_crypt()
{
	//Find NTLM hash
	md4_crypt();
	//Copy the hash and the Unicode login
	memcpy(nt_buffer,output,4*4);
	memcpy(nt_buffer+4,login_buffer,12*4);
	//Second round of MD4
	md4_crypt();
}
//This include the Unicode conversion and the padding
static void prepare_key(char *key)
{
	int i=0;
	int length=strlen(key);
	memset(nt_buffer,0,16*4);
	//The length of key need to be <= 27
	for(;i<length/2;i++)	
		nt_buffer[i] = key[2*i] | (key[2*i+1]<<16);
 
	//padding
	if(length%2==1)
		nt_buffer[i] = key[length-1] | 0x800000;
	else
		nt_buffer[i]=0x80;
	//put the length
	nt_buffer[14] = length << 4;
}
 
//This include the Unicode conversion and the padding
static void prepare_login(char *login)
{
	int i=0;
	int length=strlen(login);
	memset(login_buffer,0,12*4);
	//The length of login need to be <= 19
	for(;i<length/2;i++)	
		login_buffer[i] = login[2*i] | (login[2*i+1]<<16);
 
	//padding
	if(length%2==1)
		login_buffer[i] = login[length-1] | 0x800000;
	else
		login_buffer[i]=0x80;
	//put the length - need to add 128 (16*8) for hash
        login_buffer[10] = (length << 4) + 128;
}
 
//This convert the output to hexadecimal form
static void convert_hex()
{
	int i=0;
	//Iterate the integer
	for(;i<4;i++)
	{
		int j=0;
		unsigned int n=output[i];
		//iterate the bytes of the integer		
		for(;j<4;j++)
		{
			unsigned int convert=n%256;
			hex_format[i*8+j*2+1]=itoa16[convert%16];
			convert=convert/16;
			hex_format[i*8+j*2+0]=itoa16[convert%16];
			n=n/256;
		}	
	}
	//null terminate the string
	hex_format[33]=0;
}
 
//Sample main
int main()
{
	prepare_login("administrator");
	prepare_key("password");
	mscash_crypt();
 
	convert_hex();
	printf(hex_format);
}