### The Run-Bit Test

A good hash function must also distribute its output bits uniformly. That means the first half of the hash output must have the same number of 1s and 0s as the second half. So for an ideal 256-bit hash, each of its halves should have exactly 64 1s and 0s. Too many 1s or 0s on one half of the hash means the hash is severely skewed. This could be a sign of poor statistical randomness, making the function open to pre-image attacks.

**Listing Five: The testbed for the run-bit test.**

- (void)testRunsWith:(NSString *)aMsg forType:(NSInteger)aTyp { NSMutableString *tStr, *tSub; NSData *tTst; NSInteger tIdx, tRun, tLen, tALf, tARt; NSInteger tHln, tHdx, tBdx, tBon, tLft, tRgt; NSRange tPos; unichar tChr; char *tBuf, tSmp; // perform the test tLen = [aMsg length]; tLft = 0; tRgt = 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]; // analyse the hash stream tHln = [tTst length]; tBuf = (char *)[tTst bytes]; // counting ones on the left half for (tHdx = 0; tHdx < (tHln / 2); tHdx++) { // extract a hash byte tSmp = tBuf[tHdx]; for (tBdx = 0; tBdx < 8; tBdx++) { // check the hash bit tBon = (tSmp & 0x1); if (tBon == 1) tLft++; tSmp >>= 1; } } // counting ones on the right half for (tHdx = (tHln / 2); tHdx < tHln ; tHdx++) { // extract a hash byte tSmp = tBuf[tHdx]; for (tBdx = 0; tBdx < 8; tBdx++) { // check the hash bit tBon = (tSmp & 0x1); if (tBon == 1) tRgt++; tSmp >>= 1; } } } } // calculate the average run-bit count tALf = tLft / (tLen * 255); tARt = tRgt / (tLen * 255); // store the test results //.... }

Listing Five shows the routine that does a run-bit test. This routine, `testRuns:forType:`

, uses the same two arguments as `testTiming:forType:`

. And it uses the same two nested loops to copy and modify the message data (lines 13-34).

After the routine hashed the modified message, it extracts the raw bytes from the `NSData`

object (lines 37-38). It counts the number of 1s present in the first half (lines 41-53), then the number of 1s in the second half (lines 56-68). Finally, the routine calculates the average bit count per change in message byte (lines 73-74).

In Table 3 are the results of the run-bit test. All the hashes showed a slight skew in bit distribution, but the skew never exceeds a dozen bits. MD-5, for instance, was off its ideal by just two bits. And both halves of its hash output have the same average number of 1s. SHA-2 is a bit more interesting. Both its halves are no more than two 1s less than its ideal. Plus, its left half has one more 1 than its right. This implies a slight big-endian skew in the SHA-2 function.

The five SHA-3 hashes are even more interesting. All but one showed a slight big-endian skew. Keccak and BLAKE have the largest skew, their left half having 9 more 1s than their right. Grøstl, on the other hand, has only two 1s more on its right half, implying a slight little-endian skew. Moreover, its skew is the smallest of the five.

All five SHA-3 hashes deviate slightly from the ideal distribution of 64 1s and 0s. BLAKE has the largest deviation on its left half having six 1s more than ideal. Keccak has the largest for its right half, six 1s less than ideal. Both Grøstl and JH were spot on with their right halves, while their left halves were off by two to three 1s.