今天在熊猫 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
23
|
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 前面几位开头的值，查找有没有匹配的结果，如果有，反复人肉，就能够一步步得到所需的串头了。
自动碰撞程序
人肉方案做出来显然有点低效率，我们不如编写一个自动化搜索的函数，这稍微需要一点精力，思路是，可以先随机跑出来一定大小的样本，然后在样本中进行搜索，确定一小部分串头，如此反复。
但是从另一方面看，其实我是第一个解出这道题的人，用的就是人肉的方法，如果还要花精力编写一个自动碰撞的程序，可能就不会是第一个解出的人了。
所以，既然思路已经有了，这个程序就留给有意者写吧。
