Hash collision using the leading 40-bits of SHA-1

Question

I am trying to implement Floyd's cycle finding algorithm for finding a leading 40-bit hash collision in the SHA-1 algorithm. However, my code will not find a repetition even with 800,000,000 hashes. Can I get some help on this issue?

Here is my code for reference.

REMOVED

Note: I want to understand Floyd's cycle finding algorithm, can someone explain the theory and implementation?

EDIT: Finished Solution Thanks everyone for the help, It now finds collisions in ~3,000,000 hashes!

#include "sha.h"
#include "cryptlib.h"
#include <cstdlib>
#include <iostream>
#include <string>
#include <iterator>
#include <algorithm>
#include <random>
#include <bitset>
#include <time.h>

#pragma comment(lib, "cryptlib.lib")

using namespace std;

CryptoPP::SHA1 SHA;

// takes the reference to a char array and fills it
// with random hex values
void randStr(byte(&src)[5]){
    const char *hex_digits = "0123456789abcdef";
    srand(time(NULL));
    for (int i = 0; i < 5; i++) {
        src[i] = hex_digits[(rand() % 16)];
    }
}

void hash_40(byte (&src)[5], byte (&hash)[5]){
    // Temp hash Storage
    byte k[CryptoPP::SHA1::DIGESTSIZE];
    // SHA Calculation
    SHA.CalculateDigest(k, src, 5);
    // Copy to hash destination
    for (int i = 0; i < 5; i++){
        hash[i] = k[i];
    }
}

// compares 2 strings to length len
// faster than C: strncmp with compiler
// optimizations and works as unsigned 
bool cmp_hash(byte(&a)[5], byte(&b)[5], int len){
    for (int i = 0; i < len; ++i){
        if (a[i] != b[i]){
            return false;
        }
    }
    return true;
}

int main(){
    byte 
        t[5],
        h[5],
        xT[5],
        xH[5];
    randStr(t);
    copy(begin(t), end(t), begin(h));
    hash_40(t, t);
    hash_40(h, h);
    hash_40(h, h);
    copy(begin(t), end(t), begin(xT));
    copy(begin(h), end(h), begin(xH));
    unsigned long ctr = 0;
    while (true){
        hash_40(t, t);
        hash_40(h, h);
        hash_40(h, h);
        ctr += 3;
        if (cmp_hash(t, h, 5)){
            break;
        }
        if (ctr % 10000 == 0){
            cout << ctr << "\r\n";
        }
        copy(begin(t), end(t), begin(xT));
        copy(begin(h), end(h), begin(xH));
    }

    cout << "\r\n" << xH << "\r\n" << xT << "\r\nHash to the same leading 40 bits\r\n";
    system("pause");
    return 0;
}

Answer 1

Ok, here's how it is supposed to work: we take the function (which maps a string of $n$ bits to a string of $n$ bits), and iterate it repeatedly. After some amount of time, we'll run into a loop (that is, we'll evaluate to a value that we visited before, and there after, we'll repeatedly run through the loop). And, we'll run the function iteration twice, with one of iterations running twice as fast as the other; what will happen eventually is that they'll both fall into the loop, and that the fast one will catch up with the slow one, and give us the collision (using somewhat more computation than other methods would, but using hardly any memory at all).

This is all well and good; the question is: how much computation do we expect. Well, if the function acts like a random function (and SHA1 is believed to), we'll expect to hit a collision somewhere around $c2^{n/2}$ (for a value of $c$ not drastically larger than 1).

Ok, and so what's the value of $n$? Well, you're feeding 160 bits into SHA, and using all 160 bits of SHA output in the next iteration, and so $n=160$ (and so this logic is unlikely to fall into a loop drastically earlier than $2^{80}$ iterations).

Now, during your comparison, you're comparing only 40 bits; however because it is unlikely you've fallen into a loop, you are effectively comparing random values; you might run into a collision, but with only probability $2^{-40}$ per comparison. Hence, it's not at all surprising that you haven't found anything yet.

And, given all this, what is the correct fix? Well, the obvious thing to do is to actually use $n=40$; that is, when you do your SHA1 computation, feed in only 40 bits (and not all 160). That should fix your problem.