Testing the Final SHA-3 Hashing Algorithms

The Collision Test

Finally, we want a hash function that rarely produces colliding hashes. If two messages differ by a mere byte, the function should still assign each one a unique hash.

In Listing Six is the routine testCollisions:against:forType:. This one shares the same input arguments as the routine testCascade:against:forType:. It even uses the same nested loop to copy and modify the message data (lines 13-33).

Listing Six: The testbed for the collision test.

- (void)testCollideWith:(NSString *)aMsg against:(NSData *)aHsh forType:(NSInteger)aTyp
{
	NSMutableString *tStr, *tSub;
	NSInteger tIdx, tRun, tLen, tHit, tCor, tRte;
	NSData *tTst;
	NSNumber *tNum;
	NSRange tPos;
	
	BOOL tChk;
	unichar tChr, tNew;
	
	// perform the test
	tLen = [aMsg length];
	tHit = 0;
	tCor = 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];
			tNew = tChr + 1;
			if (tNew > 255)
				tNew -= 255;
			
			// update the string
			tSub = [NSMutableString 
				stringWithCharacters:&tNew length:1];
			tPos = NSMakeRange(tRun, 1);
			[tStr replaceCharactersInRange:tPos withString:tSub];
			
			// recheck string
			if ([tStr isEqualToString:aMsg])
				tCor++;
			else 
			{
				// generate a test hash
				tTst = [tStr sha3Hash:aTyp];
				
				// compare the hash values
				tChk = [tTst isEqualToData:aHsh];
				if (tChk)
					tHit++;
			}
			
		}
	}
	
	// store the results
	if (tHit > 0)
	{
		tRte = (tLen * 255 - tCor) / tHit;
	}
	else
		tRte = tHit;
	//....
}

But this time, the test routine checks if the modified message (tStr) matches the one in the argument aMsg (line 36). If the check proved false, the routine hashes the modified message with the correct SHA-3 function (line 41). Afterwards, it uses the NSData method isEqualToData: to check the resulting hash (tHsh) against the original (aHsh). A positive match means a collision and the routine updates the local tHit (lines 44-45). Then once the nested loop ends, the test routine calculates the collision rate in terms of the number of unique hashes per collision (lines 53-58).

Table 4 shows the results of the collision test. At first, it appears none of the algorithms have experienced any collisions. This is a bit misleading, however, considering the number of variations involved.

The sample message used has 41 characters (assuming ASCII encoding). The routine then produces 10,668 unique variations of that same message. But that number of variations is too small to induce collisions. To properly test a 256-bit hash function, we need at least 65,536 variations. One way perhaps to achieve this is to alter the test routine so that it modifies the message at the bit level.

Furthermore, both BLAKE and Grøstl did produce collisions (marked here in red). BLAKE had an average rate of 3556 unique hashes per collision, Grøstl about 2667 unique hashes per collision. These collisions, however, could not be replicated reliably. This implies some sort of instability in the test routine itself.

Conclusion

The final five SHA-3 candidates show much promise in terms of performance and security. In this article, we learned how each candidate converts a given message into a unique hash. Then we examined how to incorporate these candidates into the NSString class with the use of a category. And we subjected them to four basic tests and saw how they compare against their OpenSSL cousins.

It will some time before NIST finally decides on which candidate will be the SHA-3 standard. But when they do, be assured Dr. Dobb's will cover the new standard in detail.

José is a freelance engineering writer living in North Vancouver, British Columbia. He frequently contributes articles to MacTech and REALStudio Developer.

Click here to read Part 1 of this series.