Published at:   |   Reading: 1453 words ~3min   |   PV/UV: /

今天在熊猫 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 前面几位开头的值，查找有没有匹配的结果，如果有，反复人肉，就能够一步步得到所需的串头了。

自动碰撞程序

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

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

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

0%