Channels ▼


Testing the Final SHA-3 Hashing Algorithms

The Cascade Test

Next, we want a hash function with good avalanche properties. If two message data differ by a single byte, their respective hashes must change by at least half the total bytes, but no more than two-thirds of those same bytes. In an ideal 256-bit hash, that means a change of at least 16 bytes per message byte and no more than 21 bytes. Anything less or more could mean a susceptibility to collisions.

In Listing Four is the routine testCascade:against:forType:, which runs a cascade test. Like the previous routine, it gets the message data as an NSString, the hash type as an NSInteger. But it gets a third argument: the message's original hash (aHsh) as an NSData.

Listing Four: The cascade testbed

- (void)testCascadeWith:(NSString *)aMsg against:(NSData *)aHsh forType:(NSInteger)aTyp;
	NSMutableString *tStr, *tSub;
	NSInteger tIdx, tRun, tLen, tCnt, tAve;
	NSInteger tHln;
	NSNumber *tNum;
	NSData *tTst;
	NSRange tPos;
	char *tOrg, *tNew, tOch, tNch;
	unichar tChr;

	// perform the test
	tLen = [aMsg length];
	tCnt = 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];
	         // analyze the hash stream
		   tOrg = (char *)[aHsh bytes];
		   tNew = (char *)[tTst bytes];
  	         tHln = ([tTst length] < [aHsh length]) ?  
                            [tTst length] : [aHsh length];
		   while (tHln > 0)
			// read a hash byte
			tOch = *tOrg;
			tNch = *tNew;
			// compare the bytes
			if (tOch != tNch)
			// go to the next pair of bytes
	// calculate the average cascade
	tAve = tCnt / (tLen * 255);
	tNum = [NSNumber numberWithInteger:tAve];

	// store the results

The first half of the routine is similar to that of testTiming:forType: (lines 14-34). After a call to sha3hash:, the routine compares the generated hash with the original (lines 37-54). It counts the bytes that differ between the two. Then, after the nested loop, the routine calculates the average change in bytes (lines 58-59), again storing the result in an NSNumber.

Table 2 shows the test results for both the SHA-3 candidates and their OpenSSL cousins. The first two OpenSSL hashes showed decent avalanche rates. The MD-5 hash changes at an average of 9 bytes per message byte, just one byte more than the minimum ideal of 8 (for a 128-bit hash). The SHA-2 hash, however, changes about 29 bytes per message byte. This is clearly more than the ideal maximum of 21 bytes.

Table 2: The results of the cascade test.

As for the SHA-3 hashes, they all showed an average change of 17 bytes per message byte, a byte more than the minimum of 16.

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.