 |
| 圖片來源 |
- Bucket(桶)：雜湊表儲存資料的位置，每一個位置具有唯一識別索引。
- Slot(槽)： 每一個Bucket裡面都會存放不同的資料，而假設一筆資料由兩個欄位組成，每一個欄位就是一個Slot(槽)。
- Hash Function(雜湊演算法)：計算出雜湊值的一套數學公式，諸如： MD5、SHA…皆是著名的雜湊演算法。
上一篇我們介紹了「【開發智能合約 - 密碼學系列】編碼(Encode)、雜湊(Hash)、加密(Encrypt)傻傻分不清楚？」， 相信大家對於編碼、雜湊、加密已經具備基礎的知識了， 那這次就來深入聊聊雜湊(Hash)的內容、相關的演算法、應用場景…。
我們在聊區塊鏈的時候常常會聽到Hash、Hash Function、Hash…， 常常我們都認為Hash就是保障區塊鏈安全的重要算法， 但嚴格來說Hash並不是一一種加密算法， 而是一種資訊檢索， 透過演算法將內容取摘要之後產生的一串不可逆推的雜湊值，也就是這組「雜湊值」被允許公開流傳與網路上， 這也是為什麼我們常常在下載檔案的時候， 會看到MD5值的原因， 因為MD5也是雜湊的一種演算應用， 下載過後透過雜湊值的比對， 就可以確保檔案傳送的過程是沒有被「任意竄改」的， 因為一旦內容遭到竄改， 通常雜湊值的比對就會失敗， 假若不匹配， 我們就可以初步將該檔案判定為異常。
上面那段描述相信大家也看到了一個重點， 就是「不可竄改」的特性，因此也被呼應到區塊鏈的特性。
具有哪些特點？
- 產生出來的雜湊值長度固定， 可以用於系統優化， 將大量資料取雜湊又不需要逆推資料的情境。
- 搜尋速度快， 基本上時間複雜度為O(1)。
- 難以偽造， 只要資料一改變， 雜湊值勢必截然不同。
如何運作？
1. 我們都知道計算機的運算基本單元皆為0與1， 因此第一步先將資料化為數值。
2. 接著透過Hash Function取餘數、平均法…等， 得出雜湊位址。
3. 接著在雜湊表的特定位址存放資料。
關於Hash Function
取餘數(Mod)
相除取餘數，Hash Function最基本的演算方式就是相除取餘數的方式，假設有5個Buckets，現有1個值為4的資料，則運算邏輯為：
5 % 4 = 1
中間平方法(Mid-Square)
公式主要為pow(N, 2)取中間幾位數， 舉例來說， 現有一個值為16的資料， 取平方之後如下
pow(16, 2) = 256
假設我們取1個位數， 則會是「2 [5] 6」之中的5。
什麼是碰撞(Collision)？
簡單來說就是「Hash(X) = Hash(Y)」， 來源值經過Hash Function之後得出的結果相同，此為碰撞狀況， 我們都知道Hash是一種類似取摘要的過程， 因此會有雜湊後相同的狀況發生。
碰撞的攻擊手法
假設有個數學公式是「Hash(X) = Hash(Y)」， 那麼我們常常下載檔案時是不是會帶有MD5的驗證碼讓我們檢核， 關鍵來了， 我們得到MD5驗證碼也就是Hash(X)的結果， 此時只要根據這樣的公式進行暴力運算得出Hash(Y)的Y值， 駭客就能夠替換掉有攻擊性的檔案，讓我們下載後也能檢核通過， 此時的我們將不疑有他的將檔案打開， 這時候就讓我們的裝置暴露在風險之中了， 這樣的過程稱為「碰撞攻擊(Collision Attack)」。
如何避免這種攻擊？ 當然就是選用較安全一點的演算法，但是相對的運算量也會提高， 這就是取捨的過程， 不過世界上也沒有一種演算法能夠完全不被破解的， 隨著硬體效能的演進， 既有的雜湊演算法被破解只是時間早晚的問題， 因此我們再進行軟體開發的過程中也要注意雜湊的演算法選用是否過時， 讓系統暴露於弱點之中。
如何解決碰撞(Collision)？
線性探測法(Linear Probing)
這種方式非常容易， 假設有一數值經過Hash Function運算之後得出位置(Slot)已經被佔用了， 那麼就繼續往下一個Slot找， 直到有空位為止， 但這種方式也是有其缺點， 因為碰撞之後的挪移也會產生下一個Slot碰撞的狀況， 造成擁擠碰撞的狀況。
平方探測法(Quadratic Probing)
此方法主要改善線性探測法的缺陷， 避免擁擠碰撞的現象， 並非每次都線性增加1的方式， 而是每次碰撞就以平方跳躍的方式， 讓下一次的位置更加分散。
hash(key) + probe^2
什麼是溢位(Overflow)？
Bucket並不是無限大， 因此一旦桶子滿了之後， 又要塞資料時就會造成溢位的狀況， 而Collision並不等於 Overflow因此這點要特別注意。
更安全就要加點鹽(Salt)
一般的Hash Function通常每次運算結果都相同(Hash(X) = 相同值)， 固定的狀況下就有被破解的風險存在， 因此可以加點隨機值， 讓破解的難度提高， 就如同「食物」加點「鹽」味道就不太一樣了， 此時駭客如果想要用「Hash(X) = Hash(Y)」的公式難度就更高了，因為以公式來說會變成「Hash(X + 隨機值) = Hash(Y + ???)」， 以此來避免被攻擊的風險。
常見的雜湊演算法
- Message Digest (MD) Algorithm: 常見的MD5就是這種演算法。
- Secure Hash Algorithm (SHA): SHA-128、SHA-256…。
雜湊絕對安全嗎？
早期的SHA-1已經被Google攻破了「九百萬兆次演算實現碰撞！Google 攻破了最重要的加密技術」， 隨著硬體設備的提升， 早期的演算法也逐漸不堪負荷， 因此才會有SHA-256、SHA-512…的演算法出現， 隨著時代的演進我們的密碼學也需要跟著演進才能夠達到安全的保護。
結語
當我們深入認識雜湊之後才知道原來「取摘要」的過程這麼複雜，不同的演算法具有不同的特性，取完摘要後還要避免碰撞、溢位，果然一套好的軟體背後的技術真的不容易，希望軟體能夠逐漸被重視，而不再只是免費廉價的第一印象，一套具有品質的軟體能夠避免許多不必要的問題發生，進而導致商業損失，因此我們身為開發者也要擔起技術的責任，不斷的學習技術的原理，並靈活運用，搭建出值得信賴的商業軟體。
留言
張貼留言