# How do I find a collision for a simple hash algorithm

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.

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

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
``````
• 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 '15 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 '15 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 '15 at 6:33