#201 Hash 碰撞的一种思路

今天在熊猫 TV 上看乌云白帽子大会,下面有三道互动的题目挺有意思的。

前面两题都很简单,第一题是解一个莫斯电码、第二题答案很简单,但是要提交答案需要在网页源码上懂点手脚。

第三题是重头戏,不过难度也不高,题目如下:

第三题每个人的答案都不一样,图片里被我划掉的这部分是我的用户名(手机号) K。

红色部分的一串数字就是经过上面的 DEKHash 算出的结果,所以题意就很明显了,找到 K' 使得 DEKHash(K') == DEKHash(K)

题目中给出的是 Java 代码,我作为 Java 黑,显然是不能忍受的,所以弄成了 C++的版本:

1
2
3
4
5
6
7
long DEKHash(string str) {
long hash = str.length();
for(int i = 0; i < str.length(); i++) {
hash = ((hash<<5)^(hash>>27))^str.at(i);
}
return hash;
}

下面来看我是怎么寻找这样的 K'

思路

本科的时候对安全相关的技术很有兴趣,但是由于各种忙从来没接触过,今天刚好又是周六看起了直播,所以也算是第一次尝试。

首先,这个 DEKHash 的计算方法显然是跟字符串的长度有关的,所以我们寻找的碰撞 K' 的长度应该和我们原来的 K 的长度相同。

验证纯数字

因为用户名是手机号码,所以一开始我会想要穷举11位的所有手机号是否有重复的 Hash:

1
2
3
4
5
6
7
8
9
10
11
12
13
void find() {
long i = 15900000000;
while(true) {
string str = to_string(i);
long value = DEKHash(str);
if(value == 379207836497504850) {
cout << "find:" << i << endl;
break;
}
cout << "current: " << i << " value: " << value << endl;
i++;
}
}

不过跑了一段一小会儿就放弃了,但是从观察到的输出来看,发现了一个规律:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
current: 15900270751 value: 379033047429333661
current: 15900270752 value: 379033047429333662
current: 15900270753 value: 379033047429333663
current: 15900270754 value: 379033047429333656
current: 15900270755 value: 379033047429333657
current: 15900270756 value: 379033047429333658
current: 15900270757 value: 379033047429333659
current: 15900270758 value: 379033047429333652
current: 15900270759 value: 379033047429333653

current: 15900270760 value: 379033047429333756
current: 15900270761 value: 379033047429333757
current: 15900270762 value: 379033047429333758
current: 15900270763 value: 379033047429333759
current: 15900270764 value: 379033047429333752
current: 15900270765 value: 379033047429333753
current: 15900270766 value: 379033047429333754
current: 15900270767 value: 379033047429333755
current: 15900270768 value: 379033047429333748
current: 15900270769 value: 379033047429333749

在这个结果下,只有末尾号码发生变化,最后算出来的值只有最后两位才会发生变化。

所以很明显,如果只是纯数字的号码,找到Hash 值相同的 K' 只能够在最后一位不同的情况下寻找,一共才十个号码,很容易验证没有这样的 K'

所以纯数字的结果马上就可以放弃了。

随机搜索

最开始的时候我们已经分析过K'的串场要与K相同,既然纯数字不可能,那么只能从字符串中搜索了。

下面这个函数是一个生成长度为 len 的随机字符串,字符串会包含数字、大小写字母。

1
2
3
4
5
6
7
8
9
10
void gen_random(char *s, const int len) {
static const char alphanum[] =
"0123456789"
"ABCDEFGHIJKLMNOPQRSTUVWXYZ"
"abcdefghijklmnopqrstuvwxyz";
for (int i = 0; i < len; ++i) {
s[i] = alphanum[rand() % (sizeof(alphanum) - 1)];
}
s[len] = 0;
}

这样的话,我们重新编写搜索函数:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
void random_find() {
while(true) {
int search_length = 5;

char *str = new char[search_length];
str[search_length-1] = '\0';
gen_random(str, search_length-1);

string first = "3x63qqR";

string sec(str);

string real = first+sec;
long value = DEKHash(real);
if(value == 379207836497504850) {
cout << "find:" << real << endl;
break;
}
cout << "current: " << real << " value: " << value << endl;
delete [] str;
}
}

这样的话,跑一跑马上就能找到了:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
current: 3x63qqRzvgF value: 379207836495569058
current: 3x63qqRFa6M value: 379207836493854345
current: 3x63qqRrPWN value: 379207836495281834
current: 3x63qqRQBTF value: 379207836494313154
current: 3x63qqRQor5 value: 379207836494268017
current: 3x63qqR4sVH value: 379207836497605260
current: 3x63qqRtJzX value: 379207836495450908
current: 3x63qqRgQUH value: 379207836494920428
current: 3x63qqRoSaC value: 379207836495180903
current: 3x63qqR217I value: 379207836497475245
current: 3x63qqRE7KR value: 379207836493832502
current: 3x63qqRz5Ts value: 379207836495637239
current: 3x63qqRFLPJ value: 379207836493811278
find:3x63qqR7ts6

你可能会问,string first = "3x63qqR" 这段是怎么来的?

首先这段字符串并不知道,是一步步迭代来的。

string first 首先应该设置为 "",而 search_length 的值设置为 12(留一个单元保存 \0),然后开始跑结果,当然不太可能马上就能获得结果,但是我们至少能够获得一部分结果,然后在输出的结果中用我们已知的 hash 值的一部分在 value 中搜索以 379207836497504850 前面几位开头的值,查找有没有匹配的结果,如果有,反复人肉,就能够一步步得到所需的串头了。

自动碰撞程序

人肉方案做出来显然有点低效率,我们不如编写一个自动化搜索的函数,这稍微需要一点精力,思路是,可以先随机跑出来一定大小的样本,然后在样本中进行搜索,确定一小部分串头,如此反复。

但是从另一方面看,其实我是第一个解出这道题的人,用的就是人肉的方法,如果还要花精力编写一个自动碰撞的程序,可能就不会是第一个解出的人了。

所以,既然思路已经有了,这个程序就留给有意者写吧。

打赏催更