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.