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.


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";
    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(){
    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)){
        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";
    return 0;
  • $\begingroup$ will find a collision -> won't find a collision? $\endgroup$
    – Maarten Bodewes
    Nov 21, 2014 at 0:58
  • $\begingroup$ yup, changed make sense $\endgroup$ Nov 21, 2014 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, 2014 at 8:36

1 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.

  • 1
    $\begingroup$ But shouldn't a leading-bit collision happen within 2^20 iterations? $\endgroup$ Nov 20, 2014 at 23:47
  • $\begingroup$ @user1813580 A quick test confirms this. $\endgroup$
    – Maarten Bodewes
    Nov 21, 2014 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, 2014 at 5:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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