Skip to content

Instantly share code, notes, and snippets.

@natmchugh
Last active October 9, 2015 14:54
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save natmchugh/179912c6cdba552bd70b to your computer and use it in GitHub Desktop.
Save natmchugh/179912c6cdba552bd70b to your computer and use it in GitHub Desktop.
Check that the Freestart collision published here https://sites.google.com/site/itstheshappening/ probably only works on 64 bit machine / OS
<?php
/*
Note 1: All variables are unsigned 32 bits and wrap modulo 232 when calculating, except
ml the message length which is 64 bits, and
hh the message digest which is 160 bits.
Note 2: All constants in this pseudo code are in big endian.
Within each word, the most significant byte is stored in the leftmost byte position
*/
// Initialize variables:
function preProcess($message){
/*
Pre-processing:
append the bit '1' to the message i.e. by adding 0x80 if characters are 8 bits.
append 0 ≤ k < 512 bits '0', thus the resulting message length (in bits)
is congruent to 448 (mod 512)
append ml, in a 64-bit big-endian integer. So now the message length is a multiple of 512 bits.
*/
$originalSize = strlen($message) * 8;
$message .= chr(128);
while (((strlen($message) + 8) % 64) !== 0) {
$message .= chr(0);
}
foreach (str_split(sprintf('%064b', $originalSize), 8) as $bin) {
$message .= chr(bindec($bin));
}
return $message;
}
function rotl($x, $n) {
return ($x << $n) | ($x >> (32 - $n));
}
function SHAfunction($step, $b, $c, $d)
{
switch ($step) {
case 0;
return ($b & $c) ^ (~$b & $d);
case 1;
case 3;
return $b ^ $c ^ $d;
case 2;
return ($b & $c) ^ ($b & $d) ^ ($c & $d);
}
}
function hash_sha1(array $IV, $input, $raw = false) {
list($h0, $h1, $h2, $h3, $h4) = $IV;
$K = [0x5a827999, 0x6ed9eba1, 0x8f1bbcdc, 0xca62c1d6];
$message = preProcess($input);
// Process the message in successive 512-bit chunks:
// break message into 512-bit chunks
$chunks = str_split($message, 64);
foreach ($chunks as $chunk) {
// break chunk into sixteen 32-bit big-endian words w[i], 0 ≤ i ≤ 15
$words = str_split($chunk, 4);
foreach ($words as $i => $chrs) {
$chrs = str_split($chrs);
$word = '';
foreach ($chrs as $chr) {
$word .= sprintf('%08b', ord($chr));
}
$words[$i] = bindec($word);
}
// Extend the sixteen 32-bit words into eighty 32-bit words:
for ($i = 16; $i < 80; $i++) {
// w[i] = (w[i-3] xor w[i-8] xor w[i-14] xor w[i-16]) leftrotate 1
$words[$i] = rotl($words[$i-3] ^ $words[$i-8] ^ $words[$i-14] ^ $words[$i-16], 1) & 0xffffffff;
}
// Initialize hash value for this chunk:
$a = $h0; $b = $h1; $c = $h2; $d = $h3; $e = $h4;
// Main loop:[39]
foreach ($words as $i => $word) {
$s = floor($i / 20);
$f = SHAfunction($s, $b, $c, $d);
$temp = rotl($a, 5) + $f + $e + $K[$s] + $word & 0xffffffff;
$e = $d;
$d = $c;
$c = rotl($b, 30);
$b = $a;
$a = $temp;
}
// Add this chunk's hash to result so far:
$h0 = ($h0 + $a) & 0xffffffff;
$h1 = ($h1 + $b) & 0xffffffff;
$h2 = ($h2 + $c) & 0xffffffff;
$h3 = ($h3 + $d) & 0xffffffff;
$h4 = ($h4 + $e) & 0xffffffff;
}
if ($raw) {
return pack('N5', $h0, $h1, $h2, $h3, $h4);
}
return sprintf('%08x%08x%08x%08x%08x', $h0, $h1, $h2, $h3, $h4);
}
$IV1 = [0x506b0178, 0xff6d1890, 0x202291fd, 0x3ade3871, 0xb2c665ea];
$M1 = hex2bin('9d443828a5ea3df086eaa0fa7783a7363324484daf702aaaa3dab679d8a69e2d543820eda7fffb52d3ff493fc3ff551efbffd97f55feeef2085af312088688a9');
$hash1 = hash_sha1($IV1, $M1);
$IV2 = [0x506b0178, 0xff6d1891, 0xa02291fd, 0x3ade3871, 0xb2c665ea];
$M2 = hex2bin('3f44383881ea3deca0eaa0ee5183a72c3324485dab702ab66fdab66dd4a69e2f943820fd13fffb4eefff493b7fff5504dbffd96f71feeeeee45af306048688ab');
$hash2 = hash_sha1($IV2, $M2);
var_dump($hash1);
var_dump($hash2);
var_dump(hash_equals($hash1,$hash2));
@natmchugh
Copy link
Author

The SHA1 implementation is based on pseudo code found here https://en.wikipedia.org/wiki/SHA-1#SHA-1_pseudocode

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment