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/cn.aspx?n=bbs/NetSecurity/M.1498575971.A.244.html