Last active
October 1, 2018 05:21
-
-
Save masonticehurst/ae6514d79e73bad369281aae95f29a72 to your computer and use it in GitHub Desktop.
Primitive SHA-256 Hash Function Implementation without External Libraries
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
<?php | |
/* | |
======================= Author ======================= | |
Mason Ticehurst - September 28th, 2018 | |
======================= Notice ======================= | |
!!! DO NOT USE THIS AS A REPLACEMENT FOR THE DEFAULT HASH | |
FUNCTIONS, THIS IS LIKELY SUSCEPTIBLE TO EXPLOITATION | |
NOR IS IT AS OPTIMIZED AS THE BUILT-IN ALTERNATIVES !!! | |
================= Documentation Used ================= | |
https://nvlpubs.nist.gov/nistpubs/FIPS/NIST.FIPS.180-4.pdf | |
https://en.wikipedia.org/wiki/SHA-2#Pseudocode | |
*/ | |
const INPUT = "meme_xd_aa$%9-02_##$(%()$%()aaaaa!!!!aaaa3789a7897aaaaaaaaa3543455435345345"; | |
// Reasoning: | |
// 1 (zero seperator bit) | |
// + length of input (multiplied by 8 because each character is 8 bits) | |
// + 16 bits | |
// + 64 bits (padded input length appended) | |
$NUM_BLOCKS = floor( 1 + ( ( ( 8 * strlen( INPUT ) ) + 16 + 64 ) / 512 ) ); | |
/* | |
genConstants( $aConstants ) | |
Description: Used to generate the prime numbers defined by the Department of Commerce | |
Inputs: | |
- 8 assumes query for H constants (fractional portions of the SQUARE root of the first 8 prime numbers) | |
- 64 assumes query K constants (fractional portions of the CUBE root of the first 64 prime numbers) | |
Output: | |
- Constant array (fail if input not valid in SHA256's context (8 or 64)) | |
*/ | |
function genConstants( $aConstants ){ | |
$newConstants = array(); | |
if( sizeof( $aConstants ) != 8 && sizeof( $aConstants ) != 64 ){ | |
// Invalid constant generation | |
// H0-H7 ( 8 Constants ) | |
// K0-K63 ( 64 Constants ) | |
return; | |
} | |
if( sizeof( $aConstants ) == 8 ){ | |
foreach( $aConstants as $val ){ | |
$v = floor( fmod( sqrt( $val ), 1 ) * pow( 2, 32 ) ); | |
$newConstants[] = $v; | |
} | |
} | |
if( sizeof( $aConstants ) == 64 ){ | |
foreach( $aConstants as $val ){ | |
$v = floor( fmod( pow( $val, 1/3 ), 1 ) * pow( 2, 32 ) ); | |
$newConstants[] = $v; | |
} | |
} | |
return $newConstants; | |
} | |
/* | |
genPrimes( $iPrimes ) | |
Description: Generates array of iPrimes primes | |
*/ | |
function genPrimes( $iPrimes ){ | |
$totalPrimes = 0; | |
$pArray = array(); | |
for( $i = 0; $totalPrimes < $iPrimes; ){ | |
$curPrime = gmp_nextprime( $i ); | |
$pArray[] = gmp_strval( $curPrime ); | |
$i = $curPrime; | |
$totalPrimes++; | |
} | |
return $pArray; | |
} | |
/* | |
Ch( $x, $y, $z ) | |
Description: Choose function defined by NSA/Department of Commerce ( x AND y ) XOR ( ( NOT x ) AND z ) | |
*/ | |
function Ch( $x, $y, $z ){ | |
$x = $x; | |
$y = $y; | |
$z = $z; | |
return ( ( $x & $y ) ^ ( ( ~$x ) & $z ) ); | |
} | |
/* | |
Maj( $x, $y, $z ) | |
Description: Majority function defined by NSA/Department of Commerce ( x AND y ) XOR ( x AND z ) XOR ( y AND z ) | |
*/ | |
function Maj( $x, $y, $z ){ | |
$x = $x; | |
$y = $y; | |
$z = $z; | |
return ( ( $x & $y ) ^ ( $x & $z ) ^ ( $y & $z ) ); | |
} | |
/* | |
ROTL( $x, $t ) | |
Description: Rotate-left function defined by NSA/Department of Commerce (circular bitshift left T times) | |
!!! THIS IS NOT USED IN SHA256 !!! | |
*/ | |
function ROTL( $x, $t ){ | |
return( $x << $t ) | ( $x >> ( 32 - $t ) ) & ( ( 1 << 32 ) - 1 ); | |
} | |
/* | |
ROTR( $x, $t ) | |
Description: Rotate-right function defined by NSA/Department of Commerce (circular bitshift right T times) | |
*/ | |
function ROTR( $x, $t ){ | |
return( ($x >> $t ) | ( $x << ( 32 - $t ) ) ) & ( ( 1 << 32 ) - 1 ); | |
} | |
/* | |
SHR( $x, $t ) | |
Description: Rotate-right function defined by Department of Commerce (right shift T times) | |
*/ | |
function SHR( $x, $t ){ | |
return ( $x >> $t ); | |
} | |
/* | |
Σ0( $x ) | |
Description: Σ0 (Big-Sigma0) function defined by Department of Commerce ( ROTR( x, 2 ) XOR ROTR( x, 13 ) XOR ROTR( x, 22 ) ) | |
*/ | |
function Σ0( $x ){ | |
$s0 = ROTR( $x, 2 ); | |
$s1 = ROTR( $x, 13 ); | |
$s2 = ROTR( $x, 22 ); | |
return ( $s0^ $s1 ^ $s2 ); | |
} | |
/* | |
Σ1( $x ) | |
Description: Σ1 (Big-Sigma1) function defined by Department of Commerce ( ROTR( x, 6 ) XOR ROTR( x, 11 ) XOR ROTR( x, 25 ) ) | |
*/ | |
function Σ1( $x ){ | |
return ( ROTR( $x, 6 ) ^ ROTR( $x, 11 ) ^ ROTR( $x, 25 ) ); | |
} | |
/* | |
σ0( $x ) | |
Description: σ0 (little-sigma0) function defined by Department of Commerce ( ROTR( x, 7 ) XOR ROTR( x, 18 ) XOR SHR( x, 3 ) ) | |
*/ | |
function σ0( $x ){ | |
return ( ROTR( $x, 7 ) ^ ROTR( $x, 18 ) ^ SHR( $x, 3 ) ); | |
} | |
/* | |
σ1( $x ) | |
Description: σ1 (little-sigma1) function defined by Department of Commerce ( ROTR( x, 17 ) XOR ROTR( x, 19 ) XOR SHR( x, 10 ) ) | |
*/ | |
function σ1( $x ){ | |
return ( ROTR( $x, 17 ) ^ ROTR( $x, 19 ) ^ SHR( $x, 10 ) ); | |
} | |
/* | |
padLength( $x ) | |
Description: Returns number of zeros required to make string a length in a multiple of 512 | |
*/ | |
function padLength( $x ){ | |
global $NUM_BLOCKS; | |
$k = ( 512 * ( $NUM_BLOCKS - 1 ) + 447 - ( 8 * strlen( $x ) ) ); | |
return $k; | |
} | |
/* | |
messageBinary( $str ) | |
Description: Returns the binary representation of our string input | |
*/ | |
function messageBinary( $str ){ | |
$msg = ""; | |
for( $i = 0; $i < strlen( $str ); $i++ ){ | |
$bin = unpack( 'H*', $str[$i] ); | |
$msg .= str_pad( base_convert( $bin[1], 16, 2 ), 8, 0, STR_PAD_LEFT ); | |
} | |
return $msg; | |
} | |
// Initialize our constants | |
$hConstants = genConstants( genPrimes( 8 ) ); | |
$kConstants = genConstants( genPrimes( 64 ) ); | |
/* | |
messageStruct( $str ) | |
Description: Returns the padded out binary (string in binary + 1 seperator + padding zeros + 64 bit length of binary before seperator) | |
*/ | |
function messageStruct( $str ){ | |
$m = messageBinary( $str ); | |
$l = strlen( $m ); | |
$m .= "1"; | |
for( $i = 0; $i < padLength( $str ); $i++ ){ | |
$m .= "0"; | |
} | |
$m .= str_pad( decbin( $l ), 64, 0, STR_PAD_LEFT ); | |
return $m; | |
} | |
/* | |
messageScheduler( $str, &$x, &$h, &$K ) | |
((1 << 32) - 1) is used several times to prevent integer overflow on systems higher than 32 bits (allows them to wrap around) | |
*/ | |
function messageScheduler( $str, &$h, &$K ){ | |
$hash = 0x00000000; | |
$x = messageStruct( $str ); | |
global $NUM_BLOCKS; | |
// Iterate for X amount of chunks (for each time our binary input meets 512 bits) | |
for( $chunk = 0; $chunk < $NUM_BLOCKS; $chunk++ ){ | |
$M = array(); | |
// Define our 64-entry message schedule array (32 bit words) | |
for( $i = ( 512 * $chunk ); $i < ( 512 * ( $chunk + 1 ) ); $i += 32 ){ | |
$M[] = substr( $x, $i, 32 ); | |
} | |
// Create a fixed length array for our working values | |
$W = new SplFixedArray( 64 ); | |
// Initialize our working values | |
for( $i = 0; $i < 64; $i++ ){ | |
$W[ $i ] = 0x00000000; | |
} | |
// Copy chunk into first 16 words [0..15] of the message scheduler array | |
for( $i = 0; $i < 16; $i++ ){ | |
$n = base_convert( $M[ $i ], 2, 10 ); | |
$W[ $i ] = $n; | |
} | |
// Remaining [16..63] all defined on page 22 of FIPS 180-4 | |
for( $i = 16; $i < 64; $i++ ){ | |
// run littleSigma0 on word 15 before current | |
$s0 = σ0( $W[ $i - 15 ] ); | |
$s0 &= (1 << 32) - 1; | |
// run littleSigma1 on word 2 before current | |
$s1 = σ1( $W[ $i - 2 ] ); | |
$s1 &= (1 << 32) - 1; | |
// Sum word from 16 before current, littleSigma0, word from 7 before current, and littleSigma1 | |
$W[ $i ] = $W[ $i - 16 ] + $s0 + $W[ $i - 7 ] + $s1; | |
$W[ $i ] &= (1 << 32) - 1; | |
} | |
// initialize 8 working variables with constants | |
$A = $h[0]; | |
$A &= (1 << 32) - 1; | |
$B = $h[1]; | |
$B &= (1 << 32) - 1; | |
$C = $h[2]; | |
$C &= (1 << 32) - 1; | |
$D = $h[3]; | |
$D &= (1 << 32) - 1; | |
$E = $h[4]; | |
$E &= (1 << 32) - 1; | |
$F = $h[5]; | |
$F &= (1 << 32) - 1; | |
$G = $h[6]; | |
$G &= (1 << 32) - 1; | |
$H = $h[7]; | |
$H &= (1 << 32) - 1; | |
for( $t = 0; $t < 64; $t++ ){ | |
$S1 = Σ1( $E ); | |
$ch = Ch( $E, $F, $G ); | |
$temp1 = $H; | |
$temp1 += $S1; | |
$temp1 += $ch; | |
$temp1 += $K[ $t ]; | |
$temp1 += $W[ $t ]; | |
$S0 = Σ0( $A ); | |
$maj = Maj( $A, $B, $C ); | |
$temp2 = $S0 + $maj; | |
$H = $G; | |
$H &= (1 << 32) - 1; | |
$G = $F; | |
$G &= (1 << 32) - 1; | |
$F = $E; | |
$F &= (1 << 32) - 1; | |
$E = $D + $temp1; | |
$E &= (1 << 32) - 1; | |
$D = $C; | |
$D &= (1 << 32) - 1; | |
$C = $B; | |
$C &= (1 << 32) - 1; | |
$B = $A; | |
$B &= (1 << 32) - 1; | |
$A = $temp1 + $temp2; | |
$A &= (1 << 32) - 1; | |
} | |
// Redefine constants for next chunk loop | |
$h[0] += $A; | |
$h[0] &= (1 << 32) - 1; | |
$h[1] += $B; | |
$h[1] &= (1 << 32) - 1; | |
$h[2] += $C; | |
$h[2] &= (1 << 32) - 1; | |
$h[3] += $D; | |
$h[3] &= (1 << 32) - 1; | |
$h[4] += $E; | |
$h[4] &= (1 << 32) - 1; | |
$h[5] += $F; | |
$h[5] &= (1 << 32) - 1; | |
$h[6] += $G; | |
$h[6] &= (1 << 32) - 1; | |
$h[7] += $H; | |
$h[7] &= (1 << 32) - 1; | |
// concatenate our 8 hash pieces into final hash (make always 4 capital bytes) | |
$d = sprintf( "%08X%08X%08X%08X%08X%08X%08X%08X", $h[0], $h[1], $h[2], $h[3], $h[4], $h[5], $h[6], $h[7] ); | |
// Final hash assignment | |
$hash = $d; | |
} | |
// last hash/final iteration is the input's hash | |
return $hash; | |
} | |
// Constants are generated and therefore cannot be defined as "constant", though they always will return the same results | |
// pass by reference for performance purposes | |
echo( messageScheduler( INPUT, $hConstants, $kConstants ) ); | |
?> |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment