Primitive SHA-256 Hash Function Implementation without External Libraries

sha256.php

<?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 ) );
?>