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)
				tCnt++;
				
			// go to the next pair of bytes
			tOrg++;
			tNew++;
			tHln--;
		   }
	     }
	}
	// 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.

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.