Channels ▼
RSS

Security

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.

Table 4: The results of the collision test. The numbers in red indicate the number of hashes per collision.

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.


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.
 

Video