2

I have the following hash algorithm:

    unsigned long specialNum=0x4E67C6A7;
    unsigned int ch;
    char inputVal[]="                        AAPB2GXG";


    for(int i=0;i<strlen(inputVal);i++)
    {
        ch=inputVal[i];

        ch=ch+(specialNum*32);
        ch=ch+(specialNum/4);

        specialNum=bitXor(specialNum,ch);
    }

    int outputVal=specialNum;

The bitXor simply does the Xor operation:

int bitXor(int a,int b)
{
    return (a & ~b) | (~a & b);
}

Now I want to find an Algorithm that can generate an "inputVal" when the outputVal is given.(The generated inputVal may not be necessarily be same as the original inputVal.That's why I want to find collision). This means that I need to find an algorithm that generates a solution that when fed into the above algorithm results same as specified "outputVal". The length of solution to be generated should be less than or equal to 32.

4
  • 1
    You should try the Z3 Solver. It's ideal in such cases.
    – 0xec
    Jun 2, 2015 at 12:36
  • What is Z3?What does it do? How can I use it in my situation?
    – ASHUTOSH
    Jun 2, 2015 at 12:56
  • 3
    Z3 is a SMT Solver. You can check out this article.
    – 0xec
    Jun 2, 2015 at 13:07
  • 1
    Another link (similar technique than the one suggested by Extreme Coders): HackingWeek 2015 – Reverse 4.
    – perror
    Jun 3, 2015 at 7:33

1 Answer 1

3

A Lame brute forcer with an arbitrary seed value using the code you provided finds a few collisions under an hour

#include <stdio.h>
#include <windows.h>
int bitXor(int a,int b) { return (a & ~b) | (~a & b); }
void hashit( void) {  
    SYSTEMTIME st;  
    unsigned long specialNum=0x4E67C6A7,savedspecialNum=0x4E67C6A7;
    unsigned int ch;
    char inputVal[32]={0};
    GetSystemTime(&st);
    printf("System time is : %02d:%02d:%02d:%02d\nBruteforce seed = 0xfffffff0\n", 
    st.wHour, st.wMinute,st.wSecond,st.wMilliseconds);
    for (unsigned __int64 in = 0xfffffff0; in < 0xffffffffffffffff; in++) {     
        _i64toa_s( in,inputVal,sizeof(inputVal),10);        
        for(unsigned int i=0;i<strlen(inputVal);i++){
            ch=inputVal[i];
            ch=ch+(specialNum*32);
            ch=ch+(specialNum/4);
            specialNum=bitXor(specialNum,ch);
        }
        if(specialNum == savedspecialNum) {
            GetSystemTime(&st);
            printf("The system time is: %02d:%02d:%02d:%02d\n", 
            st.wHour, st.wMinute,st.wSecond,st.wMilliseconds);
            printf("%I64x\t%x\n",in,specialNum);
        }
        specialNum = savedspecialNum;
    }
}
void main (void) {
    hashit();
}

result

System time is : 06:17:40:328
Bruteforce seed = 0xfffffff0
The system time is: 06:51:23:343
198172e4a       4e67c6a7

Edit

An improved but still Lame bruteforcer finds the first collision in 80 odd seconds

#include <stdio.h>
#include <windows.h>
char in[33] = {"4294967280"};
unsigned long specialNum=0x4E67C6A7,savedspecialNum=0x4E67C6A7;
SYSTEMTIME lt;
void main (void ){ unsigned int ch; GetLocalTime(&lt);
 printf("BruteForce Started At %02d:%02d:%02d:%02d Seed used 0n%s 0x%I64x\n",
 lt.wHour, lt.wMinute,lt.wSecond,lt.wMilliseconds,in,_strtoui64(in,0,10));
 while(in[0] <= 57) { while(in[1] <= 57) { while(in[2] <= 57) {
    while(in[3] <= 57) { while(in[4] <= 57) { while(in[5] <= 57) {
       while(in[6] <= 57) { while(in[7] <= 57) { while(in[8] <= 57) {
          while(in[9] <= 57 ) { for(unsigned int i=0;i<10;i++) {
            ch=in[i]; ch=ch+(specialNum*32); ch=ch+(specialNum/4);
            specialNum=specialNum^ch;
           } if(specialNum == savedspecialNum) { GetLocalTime(&lt);
            printf("First Collision Found 0n%s 0x%I64x\nBruteForce Ended "
            "At %02d:%02d:%02d:%02d\n",in,_strtoui64(in,0,10),lt.wHour,
            lt.wMinute,lt.wSecond,lt.wMilliseconds);return;
           }specialNum = savedspecialNum; in[9]++;
          }in[8]++;in[9]='0';
         }in[7]++;in[8]='0','0';
        }in[6]++;in[7]='0','0','0';
       }in[5]++;in[6]='0','0','0','0';
      }in[4]++;in[5]='0','0','0','0','0';
     }in[3]++;in[4]='0','0','0','0','0','0';
    }in[2]++;in[3]='0','0','0','0','0','0','0';
   }in[1]++;in[2]='0','0','0','0','0','0','0','0';
  }in[0]++;in[1]='0','0','0','0','0','0','0','0','0';
 }
}

Result

>strarray.exe
BruteForce Started At 19:26:45:437 Seed used 0n4294967280 0xfffffff0
First Collision Found 0n6846623306 0x198172e4a
BruteForce Ended At 19:28:01:921
3
  • So the 1147ee384 and 115da3233 are solutions.But when I input them in my hash algorithm, the hash calculated does not match with savedspecialNum.Why is this happening ?Dont you think specialNum should be initialized back to 4e67c6a7 after each iteration of outer loop?
    – ASHUTOSH
    Jun 3, 2015 at 5:08
  • Yeah you missed to initialize the specialNum back to 4e67c6a7.It works. But is there any way to improve the efficiency?
    – ASHUTOSH
    Jun 3, 2015 at 6:03
  • yeah i saved the original but it seems i posted some stale code thanks for noticing it i have edited the init part
    – blabb
    Jun 3, 2015 at 6:33

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.