SHA256 version 2.0 alpha 3 - updated

Coding Critique is the place to post source code for peer review by other members of DevNetwork. Any kind of code can be posted. Code posted does not have to be limited to PHP. All members are invited to contribute constructive criticism with the goal of improving the code. Posted code should include some background information about it and what areas you specifically would like help with.

Popular code excerpts may be moved to "Code Snippets" by the moderators.

Moderator: General Moderators

User avatar
feyd
Neighborhood Spidermoddy
Posts: 31559
Joined: Mon Mar 29, 2004 3:24 pm
Location: Bothell, Washington, USA

SHA256 version 2.0 alpha 3 - updated

Post by feyd »

Updated 2007-06-03: Alterations in green. Code posted below has been updated to the latest.
Updated 2007-06-05: Alterations in purple. Code posted below has not changed.

So for whatever reason I finally got around to getting close to finishing version 2.0 of my SHA256 class structure. The current builds of which can be downloaded from here: http://code.google.com/p/redwidow-dna/downloads/list

Changes this run are
  • No more static calls. Shifted to objects in favor of more object oriented and easier to switch to another algorithm
  • PHP 4 and 5 versions included in the archive.
  • PHP 5 version is aware of, and will use if possible, the hashing extension
  • It should yield a smaller memory requirement for all inputs, especially files. It no longer requires to load the entire file into memory.
  • More of a plug-in style design for class structure, with interfaces defined in PHP 5 (they're base classes in PHP 4) to make adding more inputs or algorithms simple.
  • Added UrlInput
  • SimpleTest Unit Tests for PHP 4 and PHP 5 builds.
  • Compatibility adapter now in for both PHP 4 and PHP 5 builds.
This in the pipe:
  • [s]Compatibility adapter for users of the older version wishing to update[/s]
  • [s]Adding UrlInput[/s]
Future additions:
  • Other hashing algorithms SHA384, SHA512, SHA768 and SHA1024 are top-most priorities.
  • Other inputs. I'm open to suggestions.
I'd like to hear anything you all think about it, good or bad. I'm already expecting a "it's about time" comment or ten, so no real need, but if you must, go ahead and rib me. :)

The main meat of the PHP 5 library follows for review:

Code: Select all

<?php


/*******************************************************************************
 *
 *	SHA256 object oriented class for PHP 5
 *	implemented by feyd _at_ devnetwork .dot. net
 *	specification from http://csrc.nist.gov/cryptval/shs/sha256-384-512.pdf
 *
 *	(C) Copyright 2007 PHP Developer's Network. All rights reserved.
 *
 *	This library is free software; you can redistribute it and/or modify it
 *	under the terms of the GNU Lesser General Public License as published by the
 *	Free Software Foundation; either version 2.1 of the License, or (at your
 *	option) any later version.
 *
 *	This library is distributed in the hope that it will be useful, but WITHOUT
 *	ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
 *	FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public License
 *	for more details.
 *
 *	You should have received a copy of the GNU Lesser General Public License
 *	along with this library; if not, write to the
 *		Free Software Foundation, Inc.
 *		59 Temple Place, Suite 330,
 *		Boston, MA 02111-1307 USA 
 *	
 *	Thanks to CertainKey Inc. for providing some example outputs in Javascript
 *
 *----- Version 2.0.0 ----------------------------------------------------------
 *
 *	These classes generate PHP level errors when an error, warning, or notice of
 *	some kind happens during execution. This allows you to "hide" any of these
 *	like you would any other function's error output using error_reporting().
 * 
 *  It should be noted that this version is completely incompatible with
 *  previous versions. An adapter for older versions will be forthcoming.
 * 
 *  At this time, this library requires the BCMath Arbitrary Precision
 *  Mathematics Functions library installed.
 *
 *  ---------------------------------
 *
 *  Sha256 is an implementation of HashAlgorithm which performs all the
 *  computations required to generate a SHA256 hash result of a given input.
 *
 *  ---------------------------------
 *
 *  NOTE: If you receive a parse error, you probably aren't running PHP 5.
 *
 *  ---------------------------------
 *
 *	Method:
 *		Sha256v2::hash()
 *
 *	Syntax:
 *		string $sha256->hash( HashInput in[, boolean raw ] )
 *
 *	Description:
 *      Attempt to hash a given input. The return value is either a hex string
 *      or binary string. A lowercase hex string is the default. Passing true 
 *      as the second parameter will result in the binary string.
 * 
 *		Failures return FALSE.
 *
 *	Usage:
 *      $sha256 = new Sha256v2();
 *      $hash = $sha256->hash(new StringInput('string to hash'));
 *
 *----- History ----------------------------------------------------------------
 *      2.0.0   Completely redone adding compatibility for PHP 5 along with
 *              redesigning the original form to be more modular. The PHP 5
 *              version will use the hash extension if possible.
 *
 *		1.1.0	Split out generic 'hash' class to a seperate include, for future
 *					hashes to use.
 *				Changed handling around to allow for very large message chunks
 *					for files and URL handling (does not affect string hashes).
 *				Added file hashing support. see notes above for details.
 *				Added url hashing support. see notes above for details.
 *				Split testing to a seperate file.
 *				Initial check-in to source control
 *				Removed octal output as a future option, due to incomplete usage
 *				Added bit and upper case hex output
 *
 *		1.0.1	Potential integer truncation bug fix for various operating
 *					systems and processor combinations.
 *
 *		1.0.0	First version made available.
 *
 *----- Source Control Information ---------------------------------------------
 *
 *	$Workfile: Sha256.class.php $
 *	$Author: feyd $
 *	$JustDate: 2007-06-03 $
 *	$Revision: 11 $
 *
 *	$Header: /inc/php5/Sha256.class.php 11     2007-06-03 9:30p feyd $
 *
 ******************************************************************************/


include_once 'HashAlgorithm.class.php';
include_once 'StringInput.class.php';


/**
 * This is version 2 of the SHA256 hashing algorithm. The algorithm itself
 * hasn't changed much, certainly not the output, but the design approach has. 
 * This is now much more object oriented and flexible as a result. It is now
 * much easier to switch algorithms than previously possible with older 
 * versions of this library.
 */
class Sha256v2 implements HashAlgorithm
{
	/**
	 * Used as a flag to force the internal routine to run instead of 
	 * attempting to use the hashing extension if it exists.
	 */
	private $noExt;
	
	
	/**
	 * Constructor sets the $noExt flag.
	 * @param $noExt
	 * Set the no extension flag.
	 */
	public function __construct($noExt = false)
	{
		$this->noExt = is_bool($noExt) && $noExt === true;
	}
	
	
	/**
	 * Hash the data represented by the HashInput object (or string) given.
	 * @param in
	 * An object that implements HashInput or a string.
	 * @param raw
	 * Request that the result be returned in binary instead of hex when
	 * true.
	 * @return The resulting hash or false on error.
	 */
	public function hash( $in, $raw = false )
	{
		if (is_object($in) and $in instanceof HashInput)
		{
			// bypass the error
		}
		elseif(is_scalar($in))
		{
			$in = new StringInput(strval($in));
		}
		else
		{
			trigger_error(__METHOD__ . 
				'(): First parameter is not a subclass of HashInput.',
				E_USER_ERROR);
		}
		
		$raw = is_bool($raw) && $raw === true;
		
		// Check for the existance of the hashing extenion (and verification
		// that it supports sha256)
		if( !$this->noExt and
			extension_loaded( 'hash' ) and
		    function_exists( 'hash_algos' ) and
		    in_array( 'sha256', hash_algos() ) and
		    function_exists( 'hash_init' ) and
		    function_exists( 'hash_update' ) and
		    function_exists( 'hash_final' ))
		{
			$hash = hash_init( 'sha256' );
			while(($buf = $in->read(64)) !== false)
			{
				hash_update($hash, $buf);
			}
			return hash_final($hash, $raw);
		}
		else
		{
			//	H(0) registers
			$hash = array (
				 1779033703,	-1150833019,	 1013904242,	-1521486534,
				 1359893119,	-1694144372,	  528734635,	 1541459225,
			);
			
			// reset the pointer
			$in->rewind();
			
			// the byte counter
			$counter = '0';
			
			// local buffer used to wait for the chunk size to be reached.
			$buffer = '';
			
			// loop until we can't read anymore.
			while( ($buf = $in->read(64)) !== false )
			{
				// concatenate to the actual buffer
				$buffer .= $buf;
				
				// add to the byte counter
				$counter = bcadd($counter, strlen($buf), 0);
				
				// do we have enough in the buffer to compress it?
				if( strlen($buffer) >= 64 )
				{
					$hash = $this->compress(substr($buffer, 0, 64), $hash);
					$buffer = substr($buffer, 64);
				}
			}
			
			// close the input
			$in->close();
			
			// tack on the footer
			$buffer .= $this->calculateFooter( $counter );
			
			// perform remaining compressions
			while( strlen($buffer) >= 64 )
			{
				$hash = $this->compress(substr($buffer, 0, 64), $hash);
				$buffer = substr($buffer, 64);
			}
			
			// make sure the buffer is empty
			assert('strlen($buffer) == 0');
			
			// pack the result into either a hex string or binary string
			$str = '';
			reset($hash);
			if( $raw )
			{
				do
				{
					$str .= pack('N', current($hash));
				}
				while(next($hash));
			}
			else
			{
				do
				{
					$str .= sprintf('%08x', current($hash));
				}
				while(next($hash));
			}
			
			return $str;
		}
	}
	
	
	/**
	 * Compress a given chunk using the given registers.
	 * @param chunk
	 * The chunk of data to process (must be 64 bytes)
	 * @param hash
	 * The current registers for the hash result
	 * @return The compression results
	 */
	private function compress($chunk, array $hash)
	{
		static $K = null;
		
		if($K === null)
		{
			$K = array (
				 1116352408,	 1899447441,	-1245643825,	 -373957723,
				  961987163,	 1508970993,	-1841331548,	-1424204075,
				 -670586216,	  310598401,	  607225278,	 1426881987,
				 1925078388,	-2132889090,	-1680079193,	-1046744716,
				 -459576895,	 -272742522,	  264347078,	  604807628,
				  770255983,	 1249150122,	 1555081692,	 1996064986,
				-1740746414,	-1473132947,	-1341970488,	-1084653625,
				 -958395405,	 -710438585,	  113926993,	  338241895,
				  666307205,	  773529912,	 1294757372,	 1396182291,
				 1695183700,	 1986661051,	-2117940946,	-1838011259,
				-1564481375,	-1474664885,	-1035236496,	 -949202525,
				 -778901479,	 -694614492,	 -200395387,	  275423344,
				  430227734,	  506948616,	  659060556,	  883997877,
				  958139571,	 1322822218,	 1537002063,	 1747873779,
				 1955562222,	 2024104815,	-2067236844,	-1933114872,
				-1866530822,	-1538233109,	-1090935817,	 -965641998,
			);
		}
		
		$W = array();
		$vars = 'abcdefgh';
		list($a, $b, $c, $d, $e, $f, $g, $h) = $hash;
		for($j = 0; $j < 64; ++$j)
		{
			if($j < 16)
			{
				$T1  = ord($chunk{$j*4  }) & 0xFF; $T1 <<= 8;
				$T1 |= ord($chunk{$j*4+1}) & 0xFF; $T1 <<= 8;
				$T1 |= ord($chunk{$j*4+2}) & 0xFF; $T1 <<= 8;
				$T1 |= ord($chunk{$j*4+3}) & 0xFF;
				$W[$j] = $T1;
			}
			else
			{
				$W[$j] = $this->sum(
					((($W[$j-2] >> 17) & 0x00007FFF) | 
						($W[$j-2] << 15)) ^ ((($W[$j-2] >> 19) & 0x00001FFF) |
						($W[$j-2] << 13)) ^ (($W[$j-2] >> 10) & 0x003FFFFF), 
					$W[$j-7],
					((($W[$j-15] >> 7) & 0x01FFFFFF) | ($W[$j-15] << 25)) ^
						((($W[$j-15] >> 18) & 0x00003FFF) | ($W[$j-15] << 14))
						^ (($W[$j-15] >> 3) & 0x1FFFFFFF), $W[$j-16]);
			}

			$T1 = $this->sum(
				$h,
				((($e >> 6) & 0x03FFFFFF) | ($e << 26)) ^ 
					((($e >> 11) & 0x001FFFFF) | ($e << 21)) ^ 
					((($e >> 25) & 0x0000007F) | ($e << 7)),
				($e & $f) ^ (~$e & $g),
				$K[$j],
				$W[$j]);
			$T2 = $this->sum(
				((($a >> 2) & 0x3FFFFFFF) | ($a << 30)) ^ 
					((($a >> 13) & 0x0007FFFF) | ($a << 19)) ^ 
					((($a >> 22) & 0x000003FF) | ($a << 10)),
				($a & $b) ^ ($a & $c) ^ ($b & $c));
			$h = $g;
			$g = $f;
			$f = $e;
			$e = $this->sum($d, $T1);
			$d = $c;
			$c = $b;
			$b = $a;
			$a = $this->sum($T1, $T2);
		}
		
		//	compute the next hash set
		for($j = 0; $j < 8; $j++)
			$hash[$j] = $this->sum(${$vars{$j}}, $hash[$j]);
		
		return $hash;
	}
	
	
	/**
	 * Perform a 32-bit summation the way SHA256 expects. This method is
	 * used by the digest method extensively. This method accepts a
	 * variable number of arguments which is why none are listed.
	 * @return The sum calculated
	 */
	private function sum()
	{
		$T = 0;
		for($x = 0, $y = func_num_args(); $x < $y; ++$x)
		{
			//	force argument to integer
			$a = intval(func_get_arg($x));
			
			//	carry storage
			$c = 0;
			
			for($i = 0; $i < 32; ++$i)
			{
				//	sum of the bits at $i
				$j = (($T >> $i) & 1) + (($a >> $i) & 1) + $c;
				//	carry of the bits at $i
				$c = ($j >> 1) & 1;
				//	strip the carry
				$j &= 1;
				//	clear the bit
				$T &= ~(1 << $i);
				//	set the bit
				$T |= $j << $i;
			}
		}
		
		return $T;
	}
	
	
	/**
	 * Calculate the footer required for the hash given the length of the 
	 * message.
	 * @param numbytes
	 * The quantity of bytes in the message.
	 * @return The calculated footer binary data
	 */
	private function calculateFooter( $numbytes )
	{
		$M = bcmod( $numbytes, '4294967296' );           // clip to 32 bits
		$L1 = bcmod(bcdiv($M, '268435456', 0), '16');	 // top order bits
		$L2 = bcmod( bcmul($M, '8', 0), '4294967296' );  // number of bits
		$l = pack('N*', intval($L1), intval($L2));
		
		//	64 = 64 bits needed for the size mark. 1 = the 1 bit added to the
		//	end. 511 = 511 bits to get the number to be at least large enough
		//	to require one block. 512 is the block size.
		$k = $L2 + 64 + 1 + 511;
		$k -= $k % 512 + $L2 + 64 + 1;
		$k >>= 3;	//	convert to byte count
		
		$footer = chr(128) . str_repeat(chr(0), $k) . $l;
		
		assert('($M + strlen($footer)) % 64 == 0');
		
		return $footer;
	}
}

?>
Last edited by feyd on Tue Jun 05, 2007 9:37 am, edited 2 times in total.
User avatar
infolock
DevNet Resident
Posts: 1708
Joined: Wed Sep 25, 2002 7:47 pm

Post by infolock »

Very elegant implimentation.
User avatar
Chris Corbyn
Breakbeat Nuttzer
Posts: 13098
Joined: Wed Mar 24, 2004 7:57 am
Location: Melbourne, Australia

Post by Chris Corbyn »

8O If I could understand how it all works I'd critique it at a code level... but I'm not quite the mathematical genius you are 8)

Producing a PHP5 specific version was definitely a good move. I'm going to download your code for a closer look at your plugin-style layout :)
User avatar
feyd
Neighborhood Spidermoddy
Posts: 31559
Joined: Mon Mar 29, 2004 3:24 pm
Location: Bothell, Washington, USA

Post by feyd »

d11wtq wrote:Producing a PHP5 specific version was definitely a good move. I'm going to download your code for a closer look at your plugin-style layout :)
At this point, it's quite basic. In reality, it's more composition than plug-in since there's only two points where you'd want to tweak (algorithm and input mechanism.)

Hopefully this time, I can produce SHA384 and higher quite easily.

On the subject of PHP 5, I had been meaning to get one out there at some point, but wanted to push it to the 2.0 release. Unfortunately, my brain didn't want to program (PHP) for 18 months.

I'll probably have UrlInput ready Sunday (since the rest of today and all of tomorrow is fairly shot.)
User avatar
Ollie Saunders
DevNet Master
Posts: 3179
Joined: Tue May 24, 2005 6:01 pm
Location: UK

Post by Ollie Saunders »

Well, it is certainly nice to see you writing some code feyd.

I would criticise you on the readability of some of this but as I don't any knowledge of SHA256 this might not be so applicable. Could you not make a bit more use of a few extract method refactors?
Oh and where's the unit test?
Last edited by Ollie Saunders on Fri Jun 01, 2007 5:51 pm, edited 1 time in total.
User avatar
Ambush Commander
DevNet Master
Posts: 3698
Joined: Mon Oct 25, 2004 9:29 pm
Location: New Jersey, US

Post by Ambush Commander »

I would criticise you on the readability of some of this but as I don't any knowledge of SHA256 this might be so applicable. Could you not make a bit more use of a few extract method refactors?
Because SHA-256 has a very strong mathematical foundation, the pushing around of bits needed is well documented and Feyd does not necessarily need to reiterate the theory behind the algorithm in his code. He has, however, properly commented PHP implementation specific steps.
User avatar
feyd
Neighborhood Spidermoddy
Posts: 31559
Joined: Mon Mar 29, 2004 3:24 pm
Location: Bothell, Washington, USA

Post by feyd »

ole wrote:Well, it is certainly nice to see you writing some code feyd.

I would criticise you on the readability of some of this but as I don't any knowledge of SHA256 this might be so applicable. Could you not make a bit more use of a few extract method refactors?
Oh and where's the unit test?
Unit tests will follow Sunday with the UrlInput update.
User avatar
feyd
Neighborhood Spidermoddy
Posts: 31559
Joined: Mon Mar 29, 2004 3:24 pm
Location: Bothell, Washington, USA

Post by feyd »

Code posted on Google updated. Initial post of this thread has been updated as well.

For those that will be running the now included unit tests, make sure to adjust the define() placed at the top of the code in Sha256.test.php to reflect your path to SimpleTest.
User avatar
John Cartwright
Site Admin
Posts: 11470
Joined: Tue Dec 23, 2003 2:10 am
Location: Toronto
Contact:

Post by John Cartwright »

Great job feyd, updating my libraries now

Thanks :)
User avatar
feyd
Neighborhood Spidermoddy
Posts: 31559
Joined: Mon Mar 29, 2004 3:24 pm
Location: Bothell, Washington, USA

Post by feyd »

Just so everyone's aware, I plan to have the compatibility adapter in the build sometime tomorrow (June 4th) afternoon.
matthijs
DevNet Master
Posts: 3360
Joined: Thu Oct 06, 2005 3:57 pm

Post by matthijs »

Looks great feyd.
User avatar
feyd
Neighborhood Spidermoddy
Posts: 31559
Joined: Mon Mar 29, 2004 3:24 pm
Location: Bothell, Washington, USA

Post by feyd »

Sorry for the delay, alpha 3 is up. This go 'round: the compatibility adapter is in and the old test file is included to test that it's working. Hopefully no one gets errors and I can shift it to final. :)

I'll let this sit for, say a week for people to test out on various servers.
User avatar
Oren
DevNet Resident
Posts: 1640
Joined: Fri Apr 07, 2006 5:13 am
Location: Israel

Post by Oren »

Code: Select all

$this->noExt = is_bool($noExt) && $noExt === true;
What's the is_bool() for? Do you think/know this is faster?
User avatar
feyd
Neighborhood Spidermoddy
Posts: 31559
Joined: Mon Mar 29, 2004 3:24 pm
Location: Bothell, Washington, USA

Post by feyd »

No, but it is more explicit and does what I want it to: if it's not boolean, assume false.
User avatar
Oren
DevNet Resident
Posts: 1640
Joined: Fri Apr 07, 2006 5:13 am
Location: Israel

Post by Oren »

feyd wrote:if it's not boolean, assume false.
Well, $noExt === true; does that too.
Post Reply