TED Break

execution

michaeli@lxhalle ~/coding
$ g++ -std=c++0x -O3 sha1m.cpp

michaeli@lxhalle ~/coding
$ time ./a.out
6e5a2b6d164557be546a0f17e441dcfafe7938a9 collides with test which is 2C000001
004272ba8922de44bceef49f01dccd6f81f9b997 collides with c1 which is 2CDEC8A7

real    0m28.644s
user    0m28.330s
sys     0m0.060s

julius@v220100453772998 ~/coding/tests
$ # Just received new data from friends. Their IDs were 0DF31D63 and 0FDE6CF6. Since it's not too expensive, I'll be checking 0A.. to 10..

julius@v220100453772998 ~/coding/tests
$ time nice -n 19 ./a.out
6b447cb40f2b677afbb07fa4f6541065172365d2 collides with c4 which is 0DF316E7
8bd1f58cdab015d5b82ec6c42b51ef5a595d4d4a collides with c3 which is 0FDE68FA

real    1m6.657s
user    1m6.148s
sys     0m0.332s

julius@v220100453772998 ~/coding/tests
$ # Grah, typo in the checking mask for c2...

julius@v220100453772998 ~/coding/grnvsbreak
$ time nice -n 19 ./a.out
be3ebc22f05f3e8461b78decfeaf610ca5bd7710 collides with c2 which is 0DF3169B
6b447cb40f2b677afbb07fa4f6541065172365d2 collides with c4 which is 0DF316E7
8bd1f58cdab015d5b82ec6c42b51ef5a595d4d4a collides with c3 which is 0FDE68FA

real    0m33.248s
user    0m32.794s
sys     0m0.360s

sha1m.cpp

#include <string.h>
#include <stdio.h>
#include <time.h>
#include <iostream>
#include <cassert>

using namespace std;

char stri [128];
unsigned int h0,h1,h2,h3,h4;

inline void SHA1m()
{
        h0 = 0x67452301,
        h1 = 0xEFCDAB89,
        h2 = 0x98BADCFE,
        h3 = 0x10325476,
        h4 = 0xC3D2E1F0;

        unsigned int sal = ((/*strlen(stri)=*/9+8)/64+1)*16;
        static unsigned int * sa = new unsigned int[sal];
        bzero(sa,sal);
        static unsigned int sat [80];

        int i=0,j=0,k=0,l=/*strlen(stri)=*/9,a=0,b=0,c=0,d=0,e=0,f=0,g=0;

        for (i=0; i<l; ++i) sa[i/4] |= (stri[i] << (8*(3-i%4)));
        sa[i/4] |= (0x80 << (8*(3-i%4)));
        sa[sal-1]=l*8;

        i=0;
        while (i<sal)
        {
                for (j=0;j<16;++j) sat[j]=sa[i+j];
                for (;j<80;++j)
                {
                        k = sat[j-3]^sat[j-8]^sat[j-14]^sat[j-16];
                        sat[j]=((k&0x7fffffff)<<1)|(k<0);
                }
                a=h0; b=h1; c=h2; d=h3; e=h4;
                for (j=0;j<80;++j)
                {
                        if (j<20)
                        {
                                f = (b&c)|((~b)&d);
                                k = 0x5A827999;
                        }
                        else if (j<40)
                        {
                                f = b^c^d;
                                k = 0x6ED9EBA1;
                        }
                        else if (j<60)
                        {
                                f = (b&c)|(b&d)|(c&d);
                                k = 0x8F1BBCDC;
                        }
                        else
                        {
                                f = b^c^d;
                                k = 0xCA62C1D6;
                        }
                        g = ((a&0x7fffffff)<<5)|((a<0)*0x10)|((a&0x78000000)>>27);
                        g += e+f+k+sat[j];
                        e = d;
                        d = c;
                        c = ((b&0x7fffffff)<<30)|((b<0)*0x20000000)|((b&0x7ffffffc)>>2);
                        b = a;
                        a = g;
                }
                h0+=a; h1+=b; h2+=c; h3+=d; h4+=e;
                i+=16;
        }
}

int main()
{
        int i = 0x2B500000; // Kind of arbitrary but based on my own ID 2CDEC8F3
        sprintf(stri, "%08X\n", i);
        for(; i < 0x2F000003; ++i) {
                SHA1m();
                #define hashcol(hv0,hv1,hv2,hv3,hv4, v) \
                        if(hv0 == h0 && hv1 == h1 && hv2 == h2 && hv3 == h3 && hv4 == h4)\
                                printf("%08x%08x%08x%08x%08x collides with %s which is %.8s\n",h0,h1,h2,h3,h4,v,stri)
                hashcol(0x6e5a2b6d,0x164557be,0x546a0f17,0xe441dcfa,0xfe7938a9,"test");
                //hashcol(0xb61e9920,0xe2556629,0xbf192606,0xd56c52d1,0xf4770a38,"own");
                //004272ba8922de44bceef49f01dccd6f81f9b997
                hashcol(0x004272ba,0x8922de44,0xbceef49f,0x01dccd6f,0x81f9b997,"c1");
                //be3ebc22f05f3e8461b78decfeaf610ca5bd7710
                hashcol(0xbe3ebc22,0xf05f3e84,0x61b78dec,0xfeaf610c,0xa5bd7710,"c2");
                //8bd1f58cdab015d5b82ec6c42b51ef5a595d4d4a
                hashcol(0x8bd1f58c,0xdab015d5,0xb82ec6c4,0x2b51ef5a,0x595d4d4a,"c3");
                //6b447cb40f2b677afbb07fa4f6541065172365d2
                hashcol(0x6b447cb4,0x0f2b677a,0xfbb07fa4,0xf6541065,0x172365d2,"c4");
                int c = 7;
                do
                        switch(stri[c]) {
                                case 'F':
                                        stri[c] = '0';
                                        break;
                                case '9':
                                        stri[c] = 'A';
                                        break;
                                default:
                                        ++stri[c];
                        }
                while(stri[c--] == '0');
                static_assert('1' == '0'+1 && '2' == '1'+1 && '3' == '2'+1 &&
                              '4' == '3'+1 && '5' == '4'+1 && '6' == '5'+1 &&
                                          '7' == '6'+1 && '8' == '7'+1 && '9' == '8'+1 &&
                                          'B' == 'A'+1 && 'C' == 'B'+1 && 'D' == 'C'+1 &&
                                          'E' == 'D'+1 && 'F' == 'E'+1, "assert an asciiish code");
        }
        return 0;
}