顛倒散列，查找衝突（與總和和左/右位移異或）

Question

A^((A >> 2) + (A << 5) + C) == B 

如何查找A如果B是常量而C是變量？

A爲DWORD（C可如果它沒有辦法來改變），B爲DWORD，C是字節= 0

EDIT1：GalacticJello的回答後，我收到了另一個問題：有沒有辦法做到沒有循環（簡化表達式）？

爲什麼我需要這樣的： 我試圖做一個反向功能（碰撞搜索）爲

unsigned int X(const char* const in) { //strlen(in) is always < 127 

    unsigned int result = 0x12345678; //just for an example 
    for(int i = 0; in[i] != 0; ++i) 
    result ^= (result >> 2) + (result << 5) + in[i]; 

    return result; 
} 

目前我有一個生成隨機C，然後循環搜索A. （我搜索一個使用產生的隨機值[對於A]，並檢查是否上述表達式爲真環路）

EDIT2：這是我的當前搜索的碰撞，即我現在測試代碼..

#include <stdio.h> 
#include <conio.h> 

using namespace std; 


unsigned int originalHash(const char* const in) { 

    unsigned int result = 0x12345678; 
    for(int i = 0; in[i] != 0; ++i) { 
     result = result^((result >> 2) + (result << 5) + in[i]); 
    } 

    return result; 

} 


//A^((A >> 2) + (A << 5) + C) == B 
bool findSolutions(unsigned int inHash, char* _C, unsigned int* _A) { //Starts searching from *A and *C and writes there values on success. 

    unsigned int C = *_C; 
    if(C == 0) ++C; 

    unsigned int A = *_A; 

    for(C; C < 256; ++C) { 

     for(A; A < 0xFFFFFFFF; ++A) { 

      if((A^((A >> 2) + (A << 5) + C)) == inHash) { 

       *_C = C; 
       *_A = A; 
       return true; 

      } 

     } 

     A = 0; 

    } 

    return false; 

} 


bool findCollisions(unsigned int inHash, char* szOutStr) { 

    const unsigned int REQ_HASH = 0x12345678; 
    unsigned int prevHash = 0; 
    int curChar = 0; 

    do { 

     printf("Loop Begin:\tI = %i | H = %08x | rH = %08x\n", curChar, inHash, REQ_HASH); 

     if(!findSolutions(inHash, &szOutStr[curChar], &prevHash)) { 

      printf("Unable to find solutions for %08x\n", inHash); 

      if(curChar == 0) return false; 
      --curChar; 
      continue; 

     } 

     if(prevHash == REQ_HASH) { 

      szOutStr[curChar] = 0; 
      return true; 

     } 

     printf("Found solution:\tC = %02x (%c) | A = %08x\n", szOutStr[curChar], szOutStr[curChar], prevHash); 

     char firstSolutionC = szOutStr[curChar]; 
     unsigned int firstSolutionA = prevHash; 

     printf("Trying to find alternative solutions..\n"); 
     do { 

      if(!findSolutions(inHash, &szOutStr[curChar], &prevHash)) { 

       printf("Alternative solution not found!\n"); 
       break; 

      } 

      printf("Alternative solution found [%s valid]:\tC = %02x (%c) | A = %08x\n", prevHash == REQ_HASH ? "" : "not", szOutStr[curChar], szOutStr[curChar], prevHash); 

      if(prevHash == REQ_HASH) { 

       szOutStr[curChar] = 0; 
       return true; 

      } 

      ++prevHash; 

     } while(true); 

     szOutStr[curChar] = firstSolutionC; 
     prevHash = firstSolutionA; 
     printf("Using first solution:\tC = %02x (%c) | A = %08x\n", szOutStr[curChar], szOutStr[curChar], prevHash); 

     ++curChar; 
     inHash = prevHash; 

    } while(curChar < 127); 

    return false; 

} 

int main(void) { 

    char mask[] = "hQh"; 

    DWORD original = originalHash(mask); 

    printf("%s == %08x\n", mask, original); 

    char out[128]; 
    memset(out, 0, sizeof out); 
    if(findCollisions(original, out)) 
     printf("%08x == %s\n", original, out); 
    else 
     printf("Unable to find collisions\n"); 

    getch(); 

    return 0; 

} 

Answer 1

我只是要帶刺的問題（對不起，C＃代碼，但你應該能夠得到要點）：

a ^（（A >> 2）+（A < < 5）+ C）==乙

static List<Tuple<uint, uint>> FindSolutions(uint B) 
{ 
    var solutions = new List<Tuple<uint, uint>>(); 
    for (uint C = 0; C < uint.MaxValue; C++) 
    { 
     for (uint A = 0; A < uint.MaxValue; A++) 
     { 
      uint guess = A^((A >> 2) + (A << 5) + C); 
      if (guess == B) 
       solutions.Add(new Tuple<uint,uint>(A, C)); 
     } 
    } 

    return solutions; 
} 

var solutions = FindSolutions(0x00000001); 

如果B是您的常數（00000001在這種情況下），則第一少數對於A溶液和C是：

A = 0x8b439581, B= 0x00000001, C = 0x00000000 
(0x8b439581^((22d0e560) + (6872B020) + 0)) == 0x00000001 
0x8b439581^(0x8b439580) == 0x00000001 
0x00000001 == 0x00000001 

人：

A = 0x9ba5e354, B= 0x00000001, C = 0x00000000 
A = 0x00000000, B= 0x00000001, C = 0x00000000 
A = 0x6a7ef9db, B= 0x00000001, C = 0x00000004 

...等

編輯：

要查找的碰撞，你可以簡單地通過密鑰空間進行蠻力。

再次，比較遺憾的是C＃代碼：

static uint originalHash(string input) 
{ 
    unt result = 0x12345678; 
    for (int i = 0; i < input.Length; i++)    
     result ^= (result >> 2) + (result << 5) + input[i]; 

    return result; 
} 


var charset = new string(Enumerable.Range(1, 255).Select(i => (char)i).ToArray()); 

var hits = new List<string>(); 
var hashToFind = originalHash("hQh"); 

for (int wordNum = 1; wordNum < int.MaxValue; wordNum++) 
{ 
    var word = Utils.NumberToString(wordNum, charset); 
    var guess = originalHash(word); 
    if (guess == hashToFind) 
    { 
     Console.WriteLine("Found: " + word); 
     hits.Add(word); 
    } 
} 

運行上面的代碼給我下面的碰撞一兩分鐘後：

CE CE1 COI COI有限公司ç÷| COG CUH dÌ1dÍdÒídÓÌdÖhd×GdØ|dÙe¬ e1e²Ìe³e e g e he he e ei f1 ff f f f f f f f g gn1 gq gr gsg gthgwÌgxíhO1 hP hQh hRG hS| hThUíhVÌi/i01 i1G i2h i3 i4|i5Ìi6í

那些並不好解釋，這裏的字節值：

{ 0x63, 0xEA, 0x10, } 
{ 0x63, 0xEB, 0x31, } 
{ 0x63, 0xF4, 0xCC, } 
{ 0x63, 0xF5, 0xED, } 
{ 0x63, 0xF6, 0x85, } 
{ 0x63, 0xF7, 0xA6, } 
{ 0x63, 0xF8, 0x47, } 
{ 0x63, 0xF9, 0x68, } 
{ 0x64, 0xCC, 0x31, } 
{ 0x64, 0xCD, 0x10, } 
{ 0x64, 0xD2, 0xED, } 
{ 0x64, 0xD3, 0xCC, } 
{ 0x64, 0xD6, 0x68, } 
{ 0x64, 0xD7, 0x47, } 
{ 0x64, 0xD8, 0xA6, } 
{ 0x64, 0xD9, 0x85, } 
{ 0x65, 0xAC, 0x10, } 
{ 0x65, 0xAD, 0x31, } 
{ 0x65, 0xB2, 0xCC, } 
{ 0x65, 0xB3, 0xED, } 
{ 0x65, 0xB6, 0x47, } 
{ 0x65, 0xB7, 0x68, } 
{ 0x65, 0xB8, 0x85, } 
{ 0x65, 0xB9, 0xA6, } 
{ 0x66, 0x8D, 0x31, } 
{ 0x66, 0x8E, 0x10, } 
{ 0x66, 0x91, 0xA6, } 
{ 0x66, 0x92, 0x85, } 
{ 0x66, 0x93, 0x68, } 
{ 0x66, 0x94, 0x47, } 
{ 0x66, 0x97, 0xED, } 
{ 0x66, 0x98, 0xCC, } 
{ 0x67, 0x6D, 0x10, } 
{ 0x67, 0x6E, 0x31, } 
{ 0x67, 0x71, 0x85, } 
{ 0x67, 0x72, 0xA6, } 
{ 0x67, 0x73, 0x47, } 
{ 0x67, 0x74, 0x68, } 
{ 0x67, 0x77, 0xCC, } 
{ 0x67, 0x78, 0xED, } 
{ 0x68, 0x4F, 0x31, } 
{ 0x68, 0x50, 0x10, } 
{ 0x68, 0x51, 0x68, } 
{ 0x68, 0x52, 0x47, } 
{ 0x68, 0x53, 0xA6, } 
{ 0x68, 0x54, 0x85, } 
{ 0x68, 0x55, 0xED, } 
{ 0x68, 0x56, 0xCC, } 
{ 0x69, 0x2F, 0x10, } 
{ 0x69, 0x30, 0x31, } 
{ 0x69, 0x31, 0x47, } 
{ 0x69, 0x32, 0x68, } 
{ 0x69, 0x33, 0x85, } 
{ 0x69, 0x34, 0xA6, } 
{ 0x69, 0x35, 0xCC, } 
{ 0x69, 0x36, 0xED, }