求解 烏雲白帽子大會 直播的第三道題是怎麼解的呢？

鏈接地址：烏雲白帽子大會

第三道題應該怎麼去解決呢？

哈希碰撞？並沒有思路。

暴力破解了一晚上。。。。

求大神幫助。

題目的意思是：一個手機號（你的手機號碼，比如：000000000A1）根據這段函數生成的哈希值為380045697574565917，找出一個字元串使得它的哈希值也為這個數。

字元串可以由大小寫字元，數字組成

---

看了其他答案才明白問的是啥，其實這個沒有窮舉的必要啦……這個hash純用異或，構造的實在是太差了，最差的地方就在於它是線性的。下面我來演示怎麼迅速用手寫的方法找到一個碰撞。

我們首先稍微改變一下這個Hash函數，我們可以看到它將字元串長度作為第一個元素參與Hash，我們改寫一下這個形式，把字元串的長度編碼成一個字元，比如說這個字元串長度是11，就編碼為

"x0b000000000A1"。

經過編碼之後的字元串計算Hash值是完全線性的，這源於布爾代數中異或操作其實相當於加法，具有許多加法的性質。如果我們有兩個字元串，首先我們將兩個字元串左邊補0（注意是補x00，而不是補"0"字元，顯然補0不影響Hash值計算）補到一樣長，然後把對應的字元的ASCII碼進行異或，很容易證明，原來的兩個字元串的Hash值的異或，就等於異或後的字元串的Hash值，這就是異或的線性性質。證明我就不寫了，不相信的話可以計算一下"x0fx0fx0fx0f"和"xf0xf0xf0xf0"的Hash值（不包含長度的），然後看是不是"xffxffxffxff"的Hash值。

接下來我們要考慮這個字元串的特性，它由數字、大小寫字母組成，我們來複習一下這些字母的ASCII碼的特性，數字從0x30 - 0x39, 大寫字母從0x41到0x5a，小寫字母從0x61到0x7a。不難發現，與0x20異或，恰好可以將一個大寫字母與小寫字母互換。

接下來我們利用線性性，構造一個Hash值為0的字元串，然後與原始字元串進行異或，來製造一個碰撞。由於Hash每次移位5位，而字元串每次移位8位，中間相差了3位，我們可以構造一個包含兩個bit的字元串，讓這相差的3位撞在一起然後消除掉，比如說"x01x20"，它的Hash值恰好是0。那麼在這個字元串右邊補上若干個x00，Hash值仍然是0。我們就利用這個最簡單的0值Hash字元串來製造碰撞。

我們前面已經看到了，一個大寫字母與0x20異或會變成小寫字母，而數字0與0x1異或會變成數字1，所以我們把0x20與A對齊，這樣0x1會對齊到A前面的數字0，於是我們就得到一個異或的結果：

000000001a1

這個字元串就滿足條件。

這當然不是唯一的答案，比如說"x02x40"也是合法的碰撞字元串，而0x40與數字0異或的結果是0x70，"p"，與數字1異或的結果是0x71, "q"，所以

000000000Cq

00000002pA1

2p0000000A1

也是符合條件的答案

當然把這些碰撞字元串組合起來用也是可以的，這樣我們可以生成出一大堆一大堆的碰撞。

---

答案其實特別特別多，因為11位字元串至少有127^11之多（只考慮ascii為正的字元），而long在java中不過也才2^64範圍，所以肯定有大量重複。

首先把代碼敲進來，輸出一下運算過程中hash的結果，發現依次是

ok，前兩個字元的hash結果是10800，所以只需要找一個字元串，長度也是11，後面是0000000A1，前面hash的結果是10800就可以了，所以暴力枚舉一下

然後發現四組解

1後面估計是個沒圖案的字元，或者是空格，懶得搞出來，所以2p0000000A1顯然就是一組答案了，或者3P0000000A1。

驗證後無誤，不知道所問是否是這個。

---

熊貓tv烏雲白帽子大會的網頁下面的題目？ - 白帽黑客 (White Hat)

---

推薦閱讀：