亂玩雜湊函數

當你學密碼學的雜湊函數時，你爸爸媽媽爺爺奶奶叔叔嬸嬸舅舅阿姨，就連你男朋友女朋友啊不對我沒有女朋友全部都會跟你說：好的Hash 帶你上天堂，不好的Hash 帶你住套房不要用安全性不足的Hash，可是說到不好的Hash 到底會怎麼樣，卻也沒人說個準。

我決定來做個試驗，來玩一下安全性不足的Hash 究竟會發生什麼事情？

首先是實作iSHA1，名稱來自 In-Secure Hash Algorithm，i之所以要小寫是為了潮偽裝成蘋果公司最新的產品，輸出長度為32 bits ，因此利用生日攻擊法尋找這個Hash 的碰撞只需要2^16 的計算複雜度。
實作就懶得實作了，自己設計hash function 有夠麻煩，拿個SHA1 然後只取前32 bits 就好了啦XD

大概就像這樣：

iSHA1.hexdigest():
    sha1.hexdigest()[:8]

現在有了這個就可以玩很多亂七八糟的東西啦，例如破密碼，我們選用一個最簡化的保存密碼方式：把輸入的密碼經過iSHA1 之後保存，因為iSHA1 的size 不夠，因此比較容易找到碰撞，即便如此應該還是比明文保存好一點，至少不會一眼看出密碼是啥XD

我們選一個強式密碼：

Y@kum0Yuk@r!G@D@!Suk!

經過iSHA1，它會變成：

0e14c36a

超短的對不對，為了這個我寫了個網頁
http://isha1-1338.appspot.com/attack1
大家可以在上面找碰撞，我還懶得找，但相信不會有SHA1 這麼困難…個屁

我用了以下的 python code，為了可以輸入還是用string.printable，而非跑全部的可能性：

for length in range(10):
  print("test string with length %d" % (length))
  for s in itertools.combinations(string.printable, length):
    h = iSHA1.iSHA1().update("".join(s).encode('utf-8')).hexdigest()
    if h == answer:
      print("Collision found: %s" % "".join(s))

跑了至少1 hr 才跑出一個7 characters length 的collision

well 我這是用Python ，如果用C 來試驗也許就先快100 倍，再加上類似Hashcat 這樣的專用軟體，還能擴增128 張GPGPU lolololol，可以衝到37336 Mh/s：
https://hashcat.net/oclhashcat/
至少這是個例子，無論用了多強的密碼，Hash 爆了還是沒用，噗滋一下密碼照樣給人試出來，現在SHA1 已經出現可行的攻擊，意即它的強度已經達不到理論上2^80 的安全強度，雖然這不表示SHA1 變得多不安全，不過實務上一般都建議改用SHA2 家族的雜湊函數以保證更高的安全強度。