[閒聊] 2017.W26 - 雜湊函數用數位貨幣為例

看板NetSecurity (資安資訊安全)作者CMJ0121 (不要偷 Q)時間7年前 (2017/06/27 23:06)推噓0(0推 0噓 1→)

留言1則, 1人參與討論串1/1

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://www.ptt.cc/bbs/NetSecurity/M.1498575971.A.244.html

[閒聊] 2017.W26 - 雜湊函數 用數位貨幣為例

[閒聊] 2017.W26 - 雜湊函數用數位貨幣為例