1
$\begingroup$

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;
}
$\endgroup$
  • $\begingroup$ will find a collision -> won't find a collision? $\endgroup$ – Maarten Bodewes Nov 21 '14 at 0:58
  • $\begingroup$ yup, changed make sense $\endgroup$ – miiiiiitchko Nov 21 '14 at 1:40
  • $\begingroup$ Your problem seems to be that only the cmp_hashhash step is reduced to 40 bits; assuming hash.CalculateDigest is SHA-1, the function that you iterate is 160-bit, and does not enter a cycle in a reasonable time. Change steps involving hash.CalculateDigest to truncate to 40 bit (perhaps just by changing 20 to 5), and see the magic of the birthday bound. $\endgroup$ – fgrieu Nov 21 '14 at 8:36
3
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ But shouldn't a leading-bit collision happen within 2^20 iterations? $\endgroup$ – miiiiiitchko Nov 20 '14 at 23:47
  • $\begingroup$ @user1813580 A quick test confirms this. $\endgroup$ – Maarten Bodewes Nov 21 '14 at 1:37
  • $\begingroup$ @user1813580: why should you expect this logic to find a leading-bit collision within $2^{20}$ iterations; until it falls into a loop, it is effectively doing a random walk through bit patterns; and if you test $2^{20}$ random pairs for 40 bit collisions, you have probability about $2^{-20}$ of finding one. Once you run into a loop, then the bit patterns stop acting randomly (actually, independently), however (as above) you are quite unlikely to run into a loop that early. $\endgroup$ – poncho Nov 21 '14 at 5:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.