NTLM Algorithm [Openwall Community Wiki]

NTLM Algorithm

Description

This is the format for save the passwords in modern Windows. The hash length are 128 bits and work for local account and Domain account (Active Directory account).

Algorithm

Parameter: Message which is the string to hash.
Output: Hash value which is a 128 bits value(4 integers of 32 bits).

Convert the message to Unicode: Add the byte zero at each character.
Apply MD4 Algorithm at message.

Weakness

Inherent all weakness of MD4 Algorithm.
Zero Unicode Weakness: Because almost always the password are ASCII strings the attacker has knowledge of half of the message and the positions of its.
Saltless: This can be exploit fundamentally in two ways.
1. Load all hash and iterate possible message calculating the hash only once time.
2. Use and “space-time tradeoff” attack like “rainbow attack” ¹⁾. This option we think are inappropriate because NTLM hash calculation is very fast in modern computers.

Secure message length

Modern computer perform at 10 millions of NTLM hash/sec aprox. Some calculations:

There are 95 characters printable(this are almost all used in passwords).
With length = 7: 95⁷/10⁷ = 81 days

Lower case letter and numbers are 36.
With length = 8: 36⁸/10⁷ = 3.3 days

Lower case letter are 26.
With length = 9: 26⁹/10⁷ = 6.3 days

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

Implementation's optimizations

MD4 cycle eliminate:.
Accumulative sum reverted:.
Step 48 reverted:.
Calculation on-demand of steps:.
Calculation of constants:.

Sample Code

You could look a Perl implementation in theAuthen::Passphrase::NTHash module of CPAN.

/* 
Written by Alain Espinosa <alainesp@gmail.com> in 2008
and placed in the public domain.
 
This file contain 4 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- ntlm_crypt: which take the nt_buffer and apply the compress function of MD4.
3- convert_hex: which convert the binary output in hexadecimal string. The same format
that exist in John the Ripper files.
4- 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.
*/
 
#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 output[4];
char hex_format[33];
char itoa16[16] = "0123456789abcdef";
 
//This is the MD4 compress function
static void ntlm_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 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 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_key("password");
	ntlm_crypt();
	convert_hex();
	printf(hex_format);
	return 0;
}

¹⁾ Philippe Oechslin, 2003, “Making a Faster Cryptanalytical Time-Memory Trade-Off”, Advances in Cryptology - CRYPTO 2003, 23rd Annual International Cryptology Conference