Channels ▼


Testing the Final SHA-3 Hashing Algorithms

The Run-Bit Test

A good hash function must also distribute its output bits uniformly. That means the first half of the hash output must have the same number of 1s and 0s as the second half. So for an ideal 256-bit hash, each of its halves should have exactly 64 1s and 0s. Too many 1s or 0s on one half of the hash means the hash is severely skewed. This could be a sign of poor statistical randomness, making the function open to pre-image attacks.

Listing Five: The testbed for the run-bit test.

- (void)testRunsWith:(NSString *)aMsg forType:(NSInteger)aTyp
	NSMutableString *tStr, *tSub;
	NSData *tTst;
	NSInteger tIdx, tRun, tLen, tALf, tARt;
	NSInteger tHln, tHdx, tBdx, tBon, tLft, tRgt;
	NSRange tPos;
	unichar tChr;
	char *tBuf, tSmp;
	// perform the test
	tLen = [aMsg length];
	tLft = 0;
	tRgt = 0;
	for (tRun = 0; tRun	< tLen; tRun++)
		// create a copy of the message text
		tStr = [NSMutableString	stringWithString:aMsg];
		for (tIdx = 0; tIdx < 255; tIdx++)
			// read a character byte
			tChr = [tStr characterAtIndex:tRun];
			tChr = tChr + tIdx + 1;
			tChr %= 255;
			// update the string
			tSub = [NSMutableString stringWithCharacters:&tChr length:1];
			tPos = NSMakeRange(tRun, 1);
			[tStr replaceCharactersInRange:tPos withString:tSub];
			// generate a test hash
			tTst = [tStr sha3Hash:aTyp];
			// analyse the hash stream
			tHln = [tTst length];
			tBuf = (char *)[tTst bytes];
			// counting ones on the left half
			for (tHdx = 0; tHdx < (tHln / 2); tHdx++)
				// extract a hash byte
				tSmp = tBuf[tHdx];
				for (tBdx = 0; tBdx < 8; tBdx++)
					// check the hash bit
					tBon = (tSmp & 0x1);
					if (tBon == 1)
					tSmp >>= 1;
			// counting ones on the right half
			for (tHdx = (tHln / 2); tHdx < tHln ; tHdx++)
				// extract a hash byte
				tSmp = tBuf[tHdx];
				for (tBdx = 0; tBdx < 8; tBdx++)
					// check the hash bit
					tBon = (tSmp & 0x1);
					if (tBon == 1)
					tSmp >>= 1;
	// calculate the average run-bit count
	tALf = tLft / (tLen * 255);
	tARt = tRgt / (tLen * 255);
	// store the test results

Listing Five shows the routine that does a run-bit test. This routine, testRuns:forType:, uses the same two arguments as testTiming:forType:. And it uses the same two nested loops to copy and modify the message data (lines 13-34).

After the routine hashed the modified message, it extracts the raw bytes from the NSData object (lines 37-38). It counts the number of 1s present in the first half (lines 41-53), then the number of 1s in the second half (lines 56-68). Finally, the routine calculates the average bit count per change in message byte (lines 73-74).

In Table 3 are the results of the run-bit test. All the hashes showed a slight skew in bit distribution, but the skew never exceeds a dozen bits. MD-5, for instance, was off its ideal by just two bits. And both halves of its hash output have the same average number of 1s. SHA-2 is a bit more interesting. Both its halves are no more than two 1s less than its ideal. Plus, its left half has one more 1 than its right. This implies a slight big-endian skew in the SHA-2 function.

Table 3: Results from the run-bit test.

The five SHA-3 hashes are even more interesting. All but one showed a slight big-endian skew. Keccak and BLAKE have the largest skew, their left half having 9 more 1s than their right. Grøstl, on the other hand, has only two 1s more on its right half, implying a slight little-endian skew. Moreover, its skew is the smallest of the five.

All five SHA-3 hashes deviate slightly from the ideal distribution of 64 1s and 0s. BLAKE has the largest deviation on its left half having six 1s more than ideal. Keccak has the largest for its right half, six 1s less than ideal. Both Grøstl and JH were spot on with their right halves, while their left halves were off by two to three 1s.

Related Reading

More Insights

Currently we allow the following HTML tags in comments:

Single tags

These tags can be used alone and don't need an ending tag.

<br> Defines a single line break

<hr> Defines a horizontal line

Matching tags

These require an ending tag - e.g. <i>italic text</i>

<a> Defines an anchor

<b> Defines bold text

<big> Defines big text

<blockquote> Defines a long quotation

<caption> Defines a table caption

<cite> Defines a citation

<code> Defines computer code text

<em> Defines emphasized text

<fieldset> Defines a border around elements in a form

<h1> This is heading 1

<h2> This is heading 2

<h3> This is heading 3

<h4> This is heading 4

<h5> This is heading 5

<h6> This is heading 6

<i> Defines italic text

<p> Defines a paragraph

<pre> Defines preformatted text

<q> Defines a short quotation

<samp> Defines sample computer code text

<small> Defines small text

<span> Defines a section in a document

<s> Defines strikethrough text

<strike> Defines strikethrough text

<strong> Defines strong text

<sub> Defines subscripted text

<sup> Defines superscripted text

<u> Defines underlined text

Dr. Dobb's encourages readers to engage in spirited, healthy debate, including taking us to task. However, Dr. Dobb's moderates all comments posted to our site, and reserves the right to modify or remove any content that it determines to be derogatory, offensive, inflammatory, vulgar, irrelevant/off-topic, racist or obvious marketing or spam. Dr. Dobb's further reserves the right to disable the profile of any commenter participating in said activities.

Disqus Tips To upload an avatar photo, first complete your Disqus profile. | View the list of supported HTML tags you can use to style comments. | Please read our commenting policy.