2016年6月10日 星期五

亂玩雜湊函數

當你學密碼學的雜湊函數時,你爸爸媽媽爺爺奶奶叔叔嬸嬸舅舅阿姨,就連你男朋友女朋友啊不對我沒有女朋友全部都會跟你說:好的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 家族的雜湊函數以保證更高的安全強度。
Related Posts Plugin for WordPress, Blogger...