4 This code is part of LDAP Account Manager (http://www.sourceforge.net/projects/lam)
5 Copyright (C) 2004 Roland Gruber
7 This program is free software; you can redistribute it and/or modify
8 it under the terms of the GNU General Public License as published by
9 the Free Software Foundation; either version 2 of the License, or
10 (at your option) any later version.
12 This program is distributed in the hope that it will be useful,
13 but WITHOUT ANY WARRANTY; without even the implied warranty of
14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 GNU General Public License for more details.
17 You should have received a copy of the GNU General Public License
18 along with this program; if not, write to the Free Software
19 Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
24 * This class provides functions to calculate Samba NT and LM hashes.
26 * The code is a conversion from createntlm.pl (Benjamin Kuit) and smbdes.c/md4.c (Andrew Tridgell).
28 * @author Roland Gruber
34 * Calculates NT and LM hashes.
36 * The important functions are lmhash($password) and nthash($password).
42 # Contants used in lanlam hash calculations
43 # Ported from SAMBA/source/libsmb/smbdes.c:perm1[56]
44 var $perm1 = array(57, 49, 41, 33, 25, 17, 9,
45 1, 58, 50, 42, 34, 26, 18,
46 10, 2, 59, 51, 43, 35, 27,
47 19, 11, 3, 60, 52, 44, 36,
48 63, 55, 47, 39, 31, 23, 15,
49 7, 62, 54, 46, 38, 30, 22,
50 14, 6, 61, 53, 45, 37, 29,
51 21, 13, 5, 28, 20, 12, 4);
52 # Ported from SAMBA/source/libsmb/smbdes.c:perm2[48]
53 var $perm2 = array(14, 17, 11, 24, 1, 5,
57 41, 52, 31, 37, 47, 55,
58 30, 40, 51, 45, 33, 48,
59 44, 49, 39, 56, 34, 53,
60 46, 42, 50, 36, 29, 32);
61 # Ported from SAMBA/source/libsmb/smbdes.c:perm3[64]
62 var $perm3 = array(58, 50, 42, 34, 26, 18, 10, 2,
63 60, 52, 44, 36, 28, 20, 12, 4,
64 62, 54, 46, 38, 30, 22, 14, 6,
65 64, 56, 48, 40, 32, 24, 16, 8,
66 57, 49, 41, 33, 25, 17, 9, 1,
67 59, 51, 43, 35, 27, 19, 11, 3,
68 61, 53, 45, 37, 29, 21, 13, 5,
69 63, 55, 47, 39, 31, 23, 15, 7);
70 # Ported from SAMBA/source/libsmb/smbdes.c:perm4[48]
71 var $perm4 = array(32, 1, 2, 3, 4, 5,
74 12, 13, 14, 15, 16, 17,
75 16, 17, 18, 19, 20, 21,
76 20, 21, 22, 23, 24, 25,
77 24, 25, 26, 27, 28, 29,
78 28, 29, 30, 31, 32, 1);
79 # Ported from SAMBA/source/libsmb/smbdes.c:perm5[32]
80 var $perm5 = array(16, 7, 20, 21,
88 # Ported from SAMBA/source/libsmb/smbdes.c:perm6[64]
89 var $perm6 = array(40, 8, 48, 16, 56, 24, 64, 32,
90 39, 7, 47, 15, 55, 23, 63, 31,
91 38, 6, 46, 14, 54, 22, 62, 30,
92 37, 5, 45, 13, 53, 21, 61, 29,
93 36, 4, 44, 12, 52, 20, 60, 28,
94 35, 3, 43, 11, 51, 19, 59, 27,
95 34, 2, 42, 10, 50, 18, 58, 26,
96 33, 1, 41, 9, 49, 17, 57, 25);
97 # Ported from SAMBA/source/libsmb/smbdes.c:sc[16]
98 var $sc = array(1, 1, 2, 2, 2, 2, 2, 2, 1, 2, 2, 2, 2, 2, 2, 1);
99 # Ported from SAMBA/source/libsmb/smbdes.c:sbox[8][4][16]
100 # Side note, I used cut and paste for all these numbers, I did NOT
101 # type them all in =)
102 var $sbox = array(array(array(14, 4, 13, 1, 2, 15, 11, 8, 3, 10, 6, 12, 5, 9, 0, 7),
103 array( 0, 15, 7, 4, 14, 2, 13, 1, 10, 6, 12, 11, 9, 5, 3, 8),
104 array( 4, 1, 14, 8, 13, 6, 2, 11, 15, 12, 9, 7, 3, 10, 5, 0),
105 array(15, 12, 8, 2, 4, 9, 1, 7, 5, 11, 3, 14, 10, 0, 6, 13)),
106 array(array(15, 1, 8, 14, 6, 11, 3, 4, 9, 7, 2, 13, 12, 0, 5, 10),
107 array( 3, 13, 4, 7, 15, 2, 8, 14, 12, 0, 1, 10, 6, 9, 11, 5),
108 array( 0, 14, 7, 11, 10, 4, 13, 1, 5, 8, 12, 6, 9, 3, 2, 15),
109 array(13, 8, 10, 1, 3, 15, 4, 2, 11, 6, 7, 12, 0, 5, 14, 9)),
110 array(array(10, 0, 9, 14, 6, 3, 15, 5, 1, 13, 12, 7, 11, 4, 2, 8),
111 array(13, 7, 0, 9, 3, 4, 6, 10, 2, 8, 5, 14, 12, 11, 15, 1),
112 array(13, 6, 4, 9, 8, 15, 3, 0, 11, 1, 2, 12, 5, 10, 14, 7),
113 array( 1, 10, 13, 0, 6, 9, 8, 7, 4, 15, 14, 3, 11, 5, 2, 12)),
114 array(array( 7, 13, 14, 3, 0, 6, 9, 10, 1, 2, 8, 5, 11, 12, 4, 15),
115 array(13, 8, 11, 5, 6, 15, 0, 3, 4, 7, 2, 12, 1, 10, 14, 9),
116 array(10, 6, 9, 0, 12, 11, 7, 13, 15, 1, 3, 14, 5, 2, 8, 4),
117 array( 3, 15, 0, 6, 10, 1, 13, 8, 9, 4, 5, 11, 12, 7, 2, 14)),
118 array(array( 2, 12, 4, 1, 7, 10, 11, 6, 8, 5, 3, 15, 13, 0, 14, 9),
119 array(14, 11, 2, 12, 4, 7, 13, 1, 5, 0, 15, 10, 3, 9, 8, 6),
120 array( 4, 2, 1, 11, 10, 13, 7, 8, 15, 9, 12, 5, 6, 3, 0, 14),
121 array(11, 8, 12, 7, 1, 14, 2, 13, 6, 15, 0, 9, 10, 4, 5, 3)),
122 array(array(12, 1, 10, 15, 9, 2, 6, 8, 0, 13, 3, 4, 14, 7, 5, 11),
123 array(10, 15, 4, 2, 7, 12, 9, 5, 6, 1, 13, 14, 0, 11, 3, 8),
124 array( 9, 14, 15, 5, 2, 8, 12, 3, 7, 0, 4, 10, 1, 13, 11, 6),
125 array( 4, 3, 2, 12, 9, 5, 15, 10, 11, 14, 1, 7, 6, 0, 8, 13)),
126 array(array( 4, 11, 2, 14, 15, 0, 8, 13, 3, 12, 9, 7, 5, 10, 6, 1),
127 array(13, 0, 11, 7, 4, 9, 1, 10, 14, 3, 5, 12, 2, 15, 8, 6),
128 array( 1, 4, 11, 13, 12, 3, 7, 14, 10, 15, 6, 8, 0, 5, 9, 2),
129 array( 6, 11, 13, 8, 1, 4, 10, 7, 9, 5, 0, 15, 14, 2, 3, 12)),
130 array(array(13, 2, 8, 4, 6, 15, 11, 1, 10, 9, 3, 14, 5, 0, 12, 7),
131 array( 1, 15, 13, 8, 10, 3, 7, 4, 12, 5, 6, 11, 0, 14, 9, 2),
132 array( 7, 11, 4, 1, 9, 12, 14, 2, 0, 6, 10, 13, 15, 3, 5, 8),
133 array( 2, 1, 14, 7, 4, 10, 8, 13, 15, 12, 9, 0, 3, 5, 6, 11)));
136 * Fixes too large numbers
139 if ($i < 0) return 4294967296 - $i;
144 * @param integer count
148 function lshift($count, $data) {
150 for ($i = 0; $i < sizeof($data); $i++) {
151 $ret[$i] = $data[($i + $count)%sizeof($data)];
157 * @param array in input data
158 * @param array p permutation
161 function permute($in, $p, $n) {
163 for ($i = 0; $i < $n; $i++) {
164 $ret[$i] = $in[$p[$i] - 1]?1:0;
174 function mxor($in1, $in2) {
176 for ($i = 0; $i < sizeof($in1); $i++) {
177 $ret[$i] = $in1[$i] ^ $in2[$i];
185 * @param boolean $forw
188 function doHash($in, $key, $forw) {
191 $pk1 = $this->permute($key, $this->perm1, 56);
195 for ($i = 0; $i < 28; $i++) {
197 $d[$i] = $pk1[28 + $i];
200 for ($i = 0; $i < 16; $i++) {
201 $c = $this->lshift($this->sc[$i], $c);
202 $d = $this->lshift($this->sc[$i], $d);
205 for ($k = 0; $k < sizeof($d); $k++) $cd[] = $d[$k];
206 $ki[$i] = $this->permute($cd, $this->perm2, 48);
209 $pd1 = $this->permute($in, $this->perm3, 64);
213 for ($i = 0; $i < 32; $i++) {
215 $r[$i] = $pd1[32 + $i];
218 for ($i = 0; $i < 16; $i++) {
219 $er = $this->permute($r, $this->perm4, 48);
220 if ($forw) $erk = $this->mxor($er, $ki[$i]);
221 else $erk = $this->mxor($er, $ki[15 - $i]);
223 for ($j = 0; $j < 8; $j++) {
224 for ($k = 0; $k < 6; $k++) {
225 $b[$j][$k] = $erk[($j * 6) + $k];
228 for ($j = 0; $j < 8; $j++) {
231 $m = ($b[$j][0] << 1) | $b[$j][5];
232 $n = ($b[$j][1] << 3) | ($b[$j][2] << 2) | ($b[$j][3] << 1) | $b[$j][4];
234 for ($k = 0; $k < 4; $k++) {
235 $b[$j][$k]=($this->sbox[$j][$m][$n] & (1 << (3-$k)))?1:0;
239 for ($j = 0; $j < 8; $j++) {
240 for ($k = 0; $k < 4; $k++) {
241 $cb[($j * 4) + $k] = $b[$j][$k];
244 $pcb = $this->permute($cb, $this->perm5, 32);
245 $r2 = $this->mxor($l, $pcb);
246 for ($k = 0; $k < 32; $k++) $l[$k] = $r[$k];
247 for ($k = 0; $k < 32; $k++) $r[$k] = $r2[$k];
250 for ($i = 0; $i < sizeof($l); $i++) $rl[] = $l[$i];
251 return $this->permute($rl, $this->perm6, 64);
254 function str_to_key($str) {
255 $key[0] = $this->unsigned_shift_r($str[0], 1);
256 $key[1] = (($str[0]&0x01)<<6) | $this->unsigned_shift_r($str[1], 2);
257 $key[2] = (($str[1]&0x03)<<5) | $this->unsigned_shift_r($str[2], 3);
258 $key[3] = (($str[2]&0x07)<<4) | $this->unsigned_shift_r($str[3], 4);
259 $key[4] = (($str[3]&0x0F)<<3) | $this->unsigned_shift_r($str[4], 5);
260 $key[5] = (($str[4]&0x1F)<<2) | $this->unsigned_shift_r($str[5], 6);
261 $key[6] = (($str[5]&0x3F)<<1) | $this->unsigned_shift_r($str[6], 7);
262 $key[7] = $str[6]&0x7F;
263 for ($i = 0; $i < 8; $i++) {
264 $key[$i] = ($key[$i] << 1);
269 function smb_hash($in, $key, $forw){
270 $key2 = $this->str_to_key($key);
272 for ($i = 0; $i < 64; $i++) {
273 $inb[$i] = ($in[$i/8] & (1<<(7-($i%8)))) ? 1:0;
274 $keyb[$i] = ($key2[$i/8] & (1<<(7-($i%8)))) ? 1:0;
277 $outb = $this->dohash($inb, $keyb, $forw);
278 for ($i = 0; $i < 8; $i++) {
281 for ($i = 0; $i < 65; $i++) {
282 if ( isset($outb[$i]) && $outb[$i] ) {
283 $out[$i/8] |= (1<<(7-($i%8)));
289 function E_P16($in) {
290 $p14 = array_values(unpack("C*",$in));
291 $sp8 = array(0x4b, 0x47, 0x53, 0x21, 0x40, 0x23, 0x24, 0x25);
294 for ($i = 0; $i < 7; $i++) {
295 $p14_1[$i] = $p14[$i];
296 $p14_2[$i] = $p14[$i + 7];
298 $p16_1 = $this->smb_hash($sp8, $p14_1, true);
299 $p16_2 = $this->smb_hash($sp8, $p14_2, true);
301 for ($i = 0; $i < sizeof($p16_2); $i++) {
308 * Calculates the LM hash of a given password.
310 * @param string $password password
311 * @return string hash value
313 function lmhash($password = "") {
314 $password = strtoupper($password);
315 $password = substr($password,0,14);
316 $password = str_pad($password, 14, chr(0));
317 $p16 = $this->E_P16($password);
318 for ($i = 0; $i < sizeof($p16); $i++) {
319 $p16[$i] = sprintf("%02X", $p16[$i]);
321 return join("", $p16);
325 * Calculates the NT hash of a given password.
327 * @param string $password password
328 * @return string hash value
330 function nthash($password = "") {
331 $password = substr($password,0,128);
333 for ($i = 0; $i < strlen($password); $i++) $password2 .= $password[$i] . chr(0);
334 $password = $password2;
335 $hex = $this->mdfour($password);
336 for ($i = 0; $i < sizeof($hex); $i++) {
337 $hex[$i] = sprintf("%02X", $hex[$i]);
339 return join("", $hex);
343 # Ported from SAMBA/source/lib/md4.c:F,G and H respectfully
344 function F($X, $Y, $Z) {
345 $ret = (($X&$Y) | ((~((int)$X))&$Z));
346 if ($this->x($ret) > 4294967296) {
347 $ret = (2*4294967296) - $this->x($ret);
352 function G($X, $Y, $Z) {
353 return ($X&$Y) | ($X&$Z) | ($Y&$Z);
356 function H($X, $Y, $Z) {
360 # Ported from SAMBA/source/lib/md4.c:mdfour
361 function mdfour($in) {
362 $in = unpack("C*",$in);
363 $in = array_values($in);
364 $b = sizeof($in) * 8;
365 $A = array(0x67452301, 0xefcdab89, 0x98badcfe, 0x10325476);
366 while (sizeof($in) > 64 ) {
367 $M = $this->copy64($in);
368 $this->mdfour64($A[0], $A[1], $A[2], $A[3], $M);
370 for ($i = 64; $i < sizeof($in); $i++) $new_in[] = $in[$i];
375 for ($i = sizeof($buf) - 1; $i < 127; $i++) $buf[] = 0;
376 if ( sizeof($in) <= 55 ) {
377 $temp = $this->copy4($b);
382 $M = $this->copy64($buf);
383 $this->mdfour64($A[0], $A[1], $A[2], $A[3], $M);
386 $temp = $this->copy4($b);
387 $buf[120] = $temp[0];
388 $buf[121] = $temp[1];
389 $buf[122] = $temp[2];
390 $buf[123] = $temp[3];
391 $M = $this->copy64($buf);
392 $this->mdfour64($A[0], $A[1], $A[2], $A[3], $M);
394 for ($i = 64; $i < sizeof($buf); $i++) $temp[] = $buf[$i];
395 $M = $this->copy64($temp);
396 $this->mdfour64($A[0], $A[1], $A[2], $A[3], $M);
399 $temp = $this->copy4($A[0]);
400 for ($i = 0; $i < 4; $i++) $out[] = $temp[$i];
401 $temp = $this->copy4($A[1]);
402 for ($i = 0; $i < 4; $i++) $out[] = $temp[$i];
403 $temp = $this->copy4($A[2]);
404 for ($i = 0; $i < 4; $i++) $out[] = $temp[$i];
405 $temp = $this->copy4($A[3]);
406 for ($i = 0; $i < 4; $i++) $out[] = $temp[$i];
410 # Ported from SAMBA/source/lib/md4.c:copy4
414 $out[1] = $this->unsigned_shift_r($x, 8)&0xFF;
415 $out[2] = $this->unsigned_shift_r($x, 16)&0xFF;
416 $out[3] = $this->unsigned_shift_r($x, 24)&0xFF;
420 # Ported from SAMBA/source/lib/md4.c:copy64
421 function copy64($in) {
422 for ($i = 0; $i < 16; $i++) {
423 $M[$i] = ($in[$i*4+3]<<24) | ($in[$i*4+2]<<16) | ($in[$i*4+1]<<8) | ($in[$i*4+0]<<0);
428 # Ported from SAMBA/source/lib/md4.c:mdfour64
429 function mdfour64(&$A, &$B, &$C, &$D, $M) {
431 for ($i = 0; $i < 16; $i++) $X[] = $M[$i];
436 $this->ROUND1($A,$B,$C,$D, 0, 3, $X);
437 $this->ROUND1($D,$A,$B,$C, 1, 7, $X);
438 $this->ROUND1($C,$D,$A,$B, 2, 11, $X);
439 $this->ROUND1($B,$C,$D,$A, 3, 19, $X);
440 $this->ROUND1($A,$B,$C,$D, 4, 3, $X); $this->ROUND1($D,$A,$B,$C, 5, 7, $X);
441 $this->ROUND1($C,$D,$A,$B, 6, 11, $X); $this->ROUND1($B,$C,$D,$A, 7, 19, $X);
442 $this->ROUND1($A,$B,$C,$D, 8, 3, $X); $this->ROUND1($D,$A,$B,$C, 9, 7, $X);
443 $this->ROUND1($C,$D,$A,$B, 10, 11, $X); $this->ROUND1($B,$C,$D,$A, 11, 19, $X);
444 $this->ROUND1($A,$B,$C,$D, 12, 3, $X); $this->ROUND1($D,$A,$B,$C, 13, 7, $X);
445 $this->ROUND1($C,$D,$A,$B, 14, 11, $X); $this->ROUND1($B,$C,$D,$A, 15, 19, $X);
446 $this->ROUND2($A,$B,$C,$D, 0, 3, $X); $this->ROUND2($D,$A,$B,$C, 4, 5, $X);
447 $this->ROUND2($C,$D,$A,$B, 8, 9, $X); $this->ROUND2($B,$C,$D,$A, 12, 13, $X);
448 $this->ROUND2($A,$B,$C,$D, 1, 3, $X); $this->ROUND2($D,$A,$B,$C, 5, 5, $X);
449 $this->ROUND2($C,$D,$A,$B, 9, 9, $X); $this->ROUND2($B,$C,$D,$A, 13, 13, $X);
450 $this->ROUND2($A,$B,$C,$D, 2, 3, $X); $this->ROUND2($D,$A,$B,$C, 6, 5, $X);
451 $this->ROUND2($C,$D,$A,$B, 10, 9, $X); $this->ROUND2($B,$C,$D,$A, 14, 13, $X);
452 $this->ROUND2($A,$B,$C,$D, 3, 3, $X); $this->ROUND2($D,$A,$B,$C, 7, 5, $X);
453 $this->ROUND2($C,$D,$A,$B, 11, 9, $X); $this->ROUND2($B,$C,$D,$A, 15, 13, $X);
454 $this->ROUND3($A,$B,$C,$D, 0, 3, $X); $this->ROUND3($D,$A,$B,$C, 8, 9, $X);
455 $this->ROUND3($C,$D,$A,$B, 4, 11, $X); $this->ROUND3($B,$C,$D,$A, 12, 15, $X);
456 $this->ROUND3($A,$B,$C,$D, 2, 3, $X); $this->ROUND3($D,$A,$B,$C, 10, 9, $X);
457 $this->ROUND3($C,$D,$A,$B, 6, 11, $X); $this->ROUND3($B,$C,$D,$A, 14, 15, $X);
458 $this->ROUND3($A,$B,$C,$D, 1, 3, $X); $this->ROUND3($D,$A,$B,$C, 9, 9, $X);
459 $this->ROUND3($C,$D,$A,$B, 5, 11, $X); $this->ROUND3($B,$C,$D,$A, 13, 15, $X);
460 $this->ROUND3($A,$B,$C,$D, 3, 3, $X); $this->ROUND3($D,$A,$B,$C, 11, 9, $X);
461 $this->ROUND3($C,$D,$A,$B, 7, 11, $X); $this->ROUND3($B,$C,$D,$A, 15, 15, $X);
463 $A = $this->add32(array($A, $AA)); $B = $this->add32(array($B, $BB));
464 $C = $this->add32(array($C, $CC)); $D = $this->add32(array($D, $DD));
467 # Needed? because perl seems to choke on overflowing when doing bitwise
468 # operations on numbers larger than 32 bits. Well, it did on my machine =)
471 for ($i = 0; $i < sizeof($v); $i++) {
472 $v[$i] = array($this->unsigned_shift_r(($v[$i]&0xffff0000), 16), ($v[$i]&0xffff));
474 for ($i = 0; $i < sizeof($v); $i++) {
475 @$sum[0] += $v[$i][0];
476 @$sum[1] += $v[$i][1];
478 $sum[0] += ($sum[1]&0xffff0000)>>16;
481 $ret = ($sum[0]<<16) | $sum[1];
482 if ($this->x($ret) > 4294967296) {
483 $ret = (2*4294967296) - $this->x($ret);
488 # Ported from SAMBA/source/lib/md4.c:ROUND1
489 function ROUND1(&$a,$b,$c,$d,$k,$s,$X) {
490 $a = $this->md4lshift($this->add32(array($a, $this->F($b,$c,$d), $X[$k])), $s);
494 # Ported from SAMBA/source/lib/md4.c:ROUND2
495 function ROUND2(&$a,$b,$c,$d,$k,$s,$X) {
496 $a = $this->md4lshift($this->add32(array($a, $this->G($b,$c,$d), $X[$k] + 0x5A827999)), $s);
500 # Ported from SAMBA/source/lib/md4.c:ROUND3
501 function ROUND3(&$a,$b,$c,$d,$k,$s,$X) {
502 $a = $this->md4lshift($this->add32(array($a + $this->H($b,$c,$d) + $X[$k] + 0x6ED9EBA1)), $s);
506 # Ported from SAMBA/source/lib/md4.c:lshift
507 # Renamed to prevent clash with SAMBA/source/libsmb/smbdes.c:lshift
508 function md4lshift($x, $s) {
510 if ($this->x($x) > 4294967296) {
511 $x = (2*4294967296) - $this->x($x);
513 $ret = ((($x<<$s)&0xFFFFFFFF) | $this->unsigned_shift_r($x, (32-$s)));
514 if ($this->x($ret) > 4294967296) {
515 $ret = (2*4294967296) - $this->x($ret);
521 * Unsigned shift operation for 32bit values.
523 * PHP 4 only supports signed shifts by default.
525 function unsigned_shift_r($a, $b) {
531 $a = ($a >> ($b - 1));