c++ - 反转哈希，查找冲突(与总和和左/右移位进行异或)

Question

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

如果 B 是常量而 C 是变量，如何找到 A？ (如果没有解决方案，可以更改C)

A 是 DWORD，B 是 DWORD，C 是 BYTE!= 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 生成随机值的循环搜索 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 ) == B

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 是您的常量(在本例中为 0x00000001)，那么 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);
    }
}

运行上面的代码在一两分钟后发生了以下碰撞:

cê cë1 côÌ cõí cö c÷¦ cøG cùh dÌ1 dÍ dÒí dÓÌ dÖh d×G dئ dÙ e¬ e­1 e²Ì e³í e¶G e·h e¸ e¹¦ f1 f f¦ f fh fG fí fÌ gm gn1 gq gr¦ gsG gth gwÌ gxí hO1 hP hQh hRG hS¦ hT hUí 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, }