//----------------------------------------------------------------------------- | |
// Differential collision & distribution tests - generate a bunch of random keys, | |
// see what happens to the hash value when we flip a few bits of the key. | |
#pragma once | |
#include "Types.h" | |
#include "Stats.h" // for chooseUpToK | |
#include "KeysetTest.h" // for SparseKeygenRecurse | |
#include "Random.h" | |
#include <vector> | |
#include <algorithm> | |
#include <stdio.h> | |
//----------------------------------------------------------------------------- | |
// Sort through the differentials, ignoring collisions that only occured once | |
// (these could be false positives). If we find collisions of 3 or more, the | |
// differential test fails. | |
template < class keytype > | |
bool ProcessDifferentials ( std::vector<keytype> & diffs, int reps, bool dumpCollisions ) | |
{ | |
std::sort(diffs.begin(), diffs.end()); | |
int count = 1; | |
int ignore = 0; | |
bool result = true; | |
if(diffs.size()) | |
{ | |
keytype kp = diffs[0]; | |
for(int i = 1; i < (int)diffs.size(); i++) | |
{ | |
if(diffs[i] == kp) | |
{ | |
count++; | |
continue; | |
} | |
else | |
{ | |
if(count > 1) | |
{ | |
result = false; | |
double pct = 100 * (double(count) / double(reps)); | |
if(dumpCollisions) | |
{ | |
printbits((unsigned char*)&kp,sizeof(kp)); | |
printf(" - %4.2f%%\n", pct ); | |
} | |
} | |
else | |
{ | |
ignore++; | |
} | |
kp = diffs[i]; | |
count = 1; | |
} | |
} | |
if(count > 1) | |
{ | |
double pct = 100 * (double(count) / double(reps)); | |
if(dumpCollisions) | |
{ | |
printbits((unsigned char*)&kp,sizeof(kp)); | |
printf(" - %4.2f%%\n", pct ); | |
} | |
} | |
else | |
{ | |
ignore++; | |
} | |
} | |
printf("%d total collisions, of which %d single collisions were ignored",(int)diffs.size(),ignore); | |
if(result == false) | |
{ | |
printf(" !!!!! "); | |
} | |
printf("\n"); | |
printf("\n"); | |
return result; | |
} | |
//----------------------------------------------------------------------------- | |
// Check all possible keybits-choose-N differentials for collisions, report | |
// ones that occur significantly more often than expected. | |
// Random collisions can happen with probability 1 in 2^32 - if we do more than | |
// 2^32 tests, we'll probably see some spurious random collisions, so don't report | |
// them. | |
template < typename keytype, typename hashtype > | |
void DiffTestRecurse ( pfHash hash, keytype & k1, keytype & k2, hashtype & h1, hashtype & h2, int start, int bitsleft, std::vector<keytype> & diffs ) | |
{ | |
const int bits = sizeof(keytype)*8; | |
for(int i = start; i < bits; i++) | |
{ | |
flipbit(&k2,sizeof(k2),i); | |
bitsleft--; | |
hash(&k2,sizeof(k2),0,&h2); | |
if(h1 == h2) | |
{ | |
diffs.push_back(k1 ^ k2); | |
} | |
if(bitsleft) | |
{ | |
DiffTestRecurse(hash,k1,k2,h1,h2,i+1,bitsleft,diffs); | |
} | |
flipbit(&k2,sizeof(k2),i); | |
bitsleft++; | |
} | |
} | |
//---------- | |
template < typename keytype, typename hashtype > | |
bool DiffTest ( pfHash hash, int diffbits, int reps, bool dumpCollisions ) | |
{ | |
const int keybits = sizeof(keytype) * 8; | |
const int hashbits = sizeof(hashtype) * 8; | |
double diffcount = chooseUpToK(keybits,diffbits); | |
double testcount = (diffcount * double(reps)); | |
double expected = testcount / pow(2.0,double(hashbits)); | |
Rand r(100); | |
std::vector<keytype> diffs; | |
keytype k1,k2; | |
hashtype h1,h2; | |
printf("Testing %0.f up-to-%d-bit differentials in %d-bit keys -> %d bit hashes.\n",diffcount,diffbits,keybits,hashbits); | |
printf("%d reps, %0.f total tests, expecting %2.2f random collisions",reps,testcount,expected); | |
for(int i = 0; i < reps; i++) | |
{ | |
if(i % (reps/10) == 0) printf("."); | |
r.rand_p(&k1,sizeof(keytype)); | |
k2 = k1; | |
hash(&k1,sizeof(k1),0,(uint32_t*)&h1); | |
DiffTestRecurse<keytype,hashtype>(hash,k1,k2,h1,h2,0,diffbits,diffs); | |
} | |
printf("\n"); | |
bool result = true; | |
result &= ProcessDifferentials(diffs,reps,dumpCollisions); | |
return result; | |
} | |
//----------------------------------------------------------------------------- | |
// Differential distribution test - for each N-bit input differential, generate | |
// a large set of differential key pairs, hash them, and test the output | |
// differentials using our distribution test code. | |
// This is a very hard test to pass - even if the hash values are well-distributed, | |
// the differences between hash values may not be. It's also not entirely relevant | |
// for testing hash functions, but it's still interesting. | |
// This test is a _lot_ of work, as it's essentially a full keyset test for | |
// each of a potentially huge number of input differentials. To speed things | |
// along, we do only a few distribution tests per keyset instead of the full | |
// grid. | |
// #TODO - put diagram drawing back on | |
template < typename keytype, typename hashtype > | |
void DiffDistTest ( pfHash hash, const int diffbits, int trials, double & worst, double & avg ) | |
{ | |
std::vector<keytype> keys(trials); | |
std::vector<hashtype> A(trials),B(trials); | |
for(int i = 0; i < trials; i++) | |
{ | |
rand_p(&keys[i],sizeof(keytype)); | |
hash(&keys[i],sizeof(keytype),0,(uint32_t*)&A[i]); | |
} | |
//---------- | |
std::vector<keytype> diffs; | |
keytype temp(0); | |
SparseKeygenRecurse<keytype>(0,diffbits,true,temp,diffs); | |
//---------- | |
worst = 0; | |
avg = 0; | |
hashtype h2; | |
for(size_t j = 0; j < diffs.size(); j++) | |
{ | |
keytype & d = diffs[j]; | |
for(int i = 0; i < trials; i++) | |
{ | |
keytype k2 = keys[i] ^ d; | |
hash(&k2,sizeof(k2),0,&h2); | |
B[i] = A[i] ^ h2; | |
} | |
double dworst,davg; | |
TestDistributionFast(B,dworst,davg); | |
avg += davg; | |
worst = (dworst > worst) ? dworst : worst; | |
} | |
avg /= double(diffs.size()); | |
} | |
//----------------------------------------------------------------------------- | |
// Simpler differential-distribution test - for all 1-bit differentials, | |
// generate random key pairs and run full distribution/collision tests on the | |
// hash differentials | |
template < typename keytype, typename hashtype > | |
bool DiffDistTest2 ( pfHash hash ) | |
{ | |
Rand r(857374); | |
int keybits = sizeof(keytype) * 8; | |
const int keycount = 256*256*32; | |
keytype k; | |
std::vector<hashtype> hashes(keycount); | |
hashtype h1,h2; | |
bool result = true; | |
for(int keybit = 0; keybit < keybits; keybit++) | |
{ | |
printf("Testing bit %d\n",keybit); | |
for(int i = 0; i < keycount; i++) | |
{ | |
r.rand_p(&k,sizeof(keytype)); | |
hash(&k,sizeof(keytype),0,&h1); | |
flipbit(&k,sizeof(keytype),keybit); | |
hash(&k,sizeof(keytype),0,&h2); | |
hashes[i] = h1 ^ h2; | |
} | |
result &= TestHashList<hashtype>(hashes,true,true,true); | |
printf("\n"); | |
} | |
return result; | |
} | |
//---------------------------------------------------------------------------- |