如何找到简单哈希算法的冲突

逆向工程 C++ C 静态分析 补丁反转 散列函数
2021-06-24 21:59:47

我有以下哈希算法：

    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;

bitXor 只是执行 Xor 操作：

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

现在我想找到一个算法，当给定outputVal时可以生成“inputVal”。（生成的 inputVal 可能不一定与原始 inputVal 相同。这就是我想找到碰撞的原因）。这意味着我需要找到一个算法来生成一个解决方案，当输入上述算法时，结果与指定的“outputVal”相同。要生成的解决方案的长度应小于或等于 32。

1个回答

使用您提供的代码具有任意种子值的 Lame 暴力破解器在一个小时内发现了一些碰撞

#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();
}

结果 

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

编辑

改进但仍然跛脚的暴力破解器在 80 秒内发现第一次碰撞 

#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';
 }
}

结果

>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
其它你可能感兴趣的问题
上一篇向 IDA 添加异常范围 下一篇打包的 PE 文件，从哪里开始？