| //----------------------------------------------------------------------------- |
| // 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; |
| } |
| |
| //---------------------------------------------------------------------------- |