2017.W26 - 雜湊函數 以數位貨幣為例 > 供給來自於需求 ## 前言 ## 最近數位(虛擬)貨幣正夯 根據 Bitcoin[0] 的論文中提到 BTC 的若干要求中提到的 PoW (Proof-of-Word) 正是例計算一個 SHA 256 得到的 Hash 中 開頭若干為 0 所需要花費的勞力 但是有辦法不(那麼)勞而獲嗎？ ## 內容 ## 雜湊函數 (Hash Function) 是一種數學函數 用來將一個大群集對應到小群集的方式 通常 Hash Function 會將輸入對應到一個固定長度的雜湊值 (Hash) 例如廣為人知的 MD5 就是將任意值雜湊為一個固定 128-bit 的 Hash 一個好的 Hash Function 需要滿足以下條件： 1. 防止碰撞 (collision) 2. 均勻 (uniformity) 3. 不可逆轉 4. 雪崩效應 (avalanche effect)[1] 這分別代表著給予一個 Hash 值 你很困難的找到他的原始輸入值 稍微改變輸入值也會得到差異很大的結果 舉一個不好的 Hash Function - H(x) = (x + 3) % 13 當做例子 假設給予一個 Hash 值 - 5 可以很快的反推出來原始的輸入值為 2 (違反 3.) 或者是輸入 4、5 會得到相似的結果 7、8 (違反 4.) 在 BTC 的例子中[2] 可以看到利用區塊[3]的開頭當作是 SHA 256 輸入值的一部分 (nonce) 接著從 0 到 MAX_NONCE 開始暴力嘗試 直到找到滿足的條件 (condition hash) 我們已經知道 MD5 可以有效的找到一個碰撞[4] 因此如果有一個虛擬貨幣 使用 MD5 來當作是主要的雜湊演算法 這樣忠厚老實的礦工就會用暴力搜尋的方式找到下一個區塊 而讀過演算法奸巧礦工 就可以用各種優化的演算法來找到下一個區塊 因此目前的虛擬貨幣 都選用沒有已知問題的雜湊演算法 另一種現代遇到的 Hash 問題就是不希望算出 hash 算得太快 在一開始 hash 設計的初衷 只需要逆轉很困難即可 但是在虛擬貨幣或資訊安全的情境下 算 hash 算得太快反而不是一個優點 原因在於如果暴力計算 hash 成本低廉 (運算速度快) 那暴力破解就不會是問題了 假設使用 RC4-40 當作例子 - 在暴力破解的狀況下需要嘗試 2 的 40 次方 ~= 10^12 如果用 一秒算出 1 個 hash 值 則需要花費 34865 年 一秒算出 1G 個 hash 值 則需要花費 17 分鐘 但如果用硬體的方式加速運算的 可能就會有更加顯著的成長 像這邊文章提到用硬體實作的 SHA 256 會有 4200% 的加速 [6] [0]: https://bitcoin.org/bitcoin.pdf [1]: https://en.wikipedia.org/wiki/Avalanche_effect [2]: https://github.com/jgarzik/pyminer/blob/master/pyminer.py [3]: https://en.wikipedia.org/wiki/Blockchain [4]: http://www.mscs.dal.ca/~selinger/md5collision/ [5]: https://github.com/secworks/sha256 [6]: http://www.electronicsfaq.com/2014/01/sha256-on-tiva-c-series-of-cotex-m4.html --

※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 123.193.122.171 ※ 文章網址: https://webptt.com/m.aspx?n=bbs/NetSecurity/M.1498575971.A.244.html