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.
