增加发现散列冲突的概率
增加发现散列冲突的概率
提问于 2019-05-23 03:33:25
我正在尝试查找修改后的散列函数的散列冲突。假设我修改后的散列只输出SHA-1的前36位。我们知道，SHA-1是一个160位的哈希值，因此，我们只需要输出40个字符中的9个字符进行比较。
我如何开始我的程序是通过散列一个字符串(我有一个运行的SHA-1算法，我将它命名为sha1。我还确保了SHA-1算法的输出是正确的。)
首先，我会硬编码2个字符串，并从40个字符中提取出9个字符，因为我只需要SHA-1的前36位。如果发现冲突，则下面的函数基本上返回true，如果未找到冲突，则返回false
public static boolean findCollision(int x1, int x2) {
String message1 = "I tried " + x1 + " iteration to find a collision";
String message2 = "I tried " + x2 + " iteration to find a collision";
//hashing my string and extracting 9 characters
String message_hash1 = sha1(message1);
String message_hash2 = sha1(message2);
String modified_hash1 = message_hash1.substring(0, 9);
String modified_hash2 = message_hash2.substring(0, 9);
if (modified_hash1.equals(modified_hash2))
return true;
else
return false;
}最后，我将有一个主函数，它将在无限循环中随机直到MAX_VALUE的整数，并且当且仅当找到散列时才会中断。
public static void main(String[] args) {
Random random = new Random();
int x1 = 0;
int x2 = 0;
int counter = 0;
while (true) {
while(true){
x1 = random.nextInt(Integer.MAX_VALUE);
x2 = random.nextInt(Integer.MAX_VALUE);
if (x1 != x2)
break;
}
if (findCollision(x1, x2) == true) {
break;
}
counter++;
}
System.out.println("\nNumber of trials: " + counter);
}如果我尝试只取SHA-1的前24位，我可以很容易地找到冲突。然而，尽管运行了几个小时，我还是无法找到36位的冲突。因此，我想知道还有什么替代方法可以让我找到只有36位SHA-1的冲突。
回答 1
Stack Overflow用户
发布于 2019-05-24 09:59:00
https://stackoverflow.com/users/1081110/dawood-ibn-kareem是正确的，最好的方法是记住以前的散列并对它们进行检查，只要这是实际的，即适合内存，36位冲突所需的大约2^18个值确实适合内存，尽管只有一点点(大约50位)不适合。
这段代码在大约一秒钟内发现了8个低于2^20的冲突(第一个如预期的略低于2^18 )：
static void SO56263762TruncCollision (String[] args) throws Exception {
int[][] known = new int[1<<24][];
MessageDigest sha1 = MessageDigest.getInstance("SHA1");
for( int i = 0; i < (1<<20); i++ ){
byte[] raw = sha1.digest(("I tried "+i+" iterations to find a collision").getBytes());
int key = 0; for( int j = 0; j < 3; j++ ) key = key<<8 | (raw[j]&0xFF);
char[] val = new char[9]; for( int j = 0; j < 9; j++ ) val[j] = Character.forDigit(j%2==0? (raw[j/2]>>4)&0xF: raw[j/2]&0xF, 16);
int[] test = known[key];
if( test == null ){ (known[key] = new int[1])[0] = i; }
else{
for( int k = 0; k < test.length; k++ ){
byte[] raw2 = sha1.digest(("I tried "+test[k]+" iterations to find a collision").getBytes());
char[] val2 = new char[9]; for( int j = 0; j < 9; j++ ) val2[j] = Character.forDigit(j%2==0? (raw2[j/2]>>4)&0xF: raw2[j/2]&0xF, 16);
if( Arrays.equals(val, val2)) System.out.println ("found "+i+" and "+test[k]);
}
(known[key] = Arrays.copyOf(test, test.length+1))[test.length] = i;
}
}
System.out.println ("Memory="+(Runtime.getRuntime().totalMemory()-Runtime.getRuntime().freeMemory()) );
}页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/56263762
复制相关文章
相似问题
腾讯云开发者
