我如何找到一个简单的哈希算法的碰撞 [英] how do i find collision for a simple hash algorithm

问题描述

我有以下散列算法：

  unsigned long specialNum = 0x4E67C6A7; 
 unsigned int ch; 
 char inputVal [] =AAPB2GXG; 
 
 $ b for（int i = 0; i  {
 ch = inputVal [i]; 
 
 ch = ch +（specialNum * 32）; 
 ch = ch +（specialNum / 4）; 
 
 specialNum = bitXor（specialNum，ch）; 
} 
 
 unsigned int outputVal = specialNum; 
  

bitXor只是执行XOR操作：

  int bitXor（int a，int b）
 {
 return（a&〜b）| （〜a& b）; 
} 
  

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

。

解决方案

<方法1：蛮力。没什么大不了的，因为你的specialNum总是在int的范围内，所以在平均尝试了几十亿个输入值之后，你找到了正确的值。应该在几秒钟内完成。方法2：蛮力，但聪明。

考虑处理最后一个ch之前的specialNum值。你先计算（specialNum * 32）+（specialNum / 4）+ ch。由于-128 <= ch < 128或0 <= ch <取决于char的符号性，您知道结果的最高23位，与ch无关。在用specialNum异或之后，你也知道最高23位（如果ch是带符号的，则最高23位有两个可能的值）。您检查这23位是否匹配所需的输出，如果不匹配，则一次性排除ch的所有256个值。所以暴力方法将在1600万步之后平均结束。

现在考虑处理最后两个ch之前的specialNum值。再次，您可以根据最后两个字符来确定结果的最高14位（如果ch用四个备选符号签名）。如果最高14位不匹配，则表示完成。

方法3：这是您如何做到的。再考虑所有长度为0,1,2等的字符串s（但是，您的算法很可能会更快地找到解决方案）。处理字符串s后计算specialNum。按照你的算法，并且允许char被签名，找到最多4个不同的值，即specialNum的最高14位在处理另外两个字符之后可能有的值。如果其中任何一个匹配了所需的输出，则在处理下一个字符的256个可能值之后检查specialNum的值，并查找最多2个不同的值，即specialNum的最高23位在检查另一个char后可能具有的值。如果其中一个匹配所需输出的最高23位，那么在处理256个可能的下一个字符中的每一个并查找匹配之后，检查什么是specialNum。

应该在毫秒以下工作。如果char未经签名，则速度更快。

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

    unsigned 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.

解决方案

Method 1: Brute force. Not a big deal, because your "specialNum" is always in the range of an int, so after trying on average a few billion input values, you find the right one. Should be done in a few seconds.

Method 2: Brute force, but clever.

Consider the specialNum value before the last ch is processed. You first calculate (specialNum * 32) + (specialNum / 4) + ch. Since -128 <= ch < 128 or 0 <= ch < 256 depending on the signedness of char, you know the highest 23 bits of the result, independent of ch. After xor'ing ch with specialNum, you also know the highest 23 bits (if ch is signed, there are two possible values for the highest 23 bits). You check whether those 23 bits match the desired output, and if they don't, you have excluded all 256 values of ch in one go. So the brute force method will end on average after 16 million steps.

Now consider the specialNum value before the last two ch are processed. Again, you can determine the highest possible 14 bits of the result (if ch is signed with four alternatives) without examining the last two characters at all. If the highest 14 bits don't match, you are done.

Method 3: This is how you do it. Consider in turn all strings s of length 0, 1, 2, etc. (however, your algorithm will most likely find a solution much quicker). Calculate specialNum after processing the string s. Following your algorithm, and allowing for char to be signed, find the up to 4 different values that the highest 14 bits of specialNum might have after processing two further characters. If any of those matches the desired output, then examine the value of specialNum after processing each of the 256 possible values of the next character, and find the up to 2 different values that the highest 23 bits of specialNum might have after examining another char. If one of those matches the highest 23 bits of the desired output then examine what specialNum would be after processing each of the 256 possible next characters and look for a match.

This should work below a millisecond. If char is unsigned, it is faster.

这篇关于我如何找到一个简单的哈希算法的碰撞的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！