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).

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

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

1. Inherent all weakness of MD4 Algorithm.
2. 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.
3. 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.

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.

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

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;
}