【密碼學】你以為你要的．雜湊演算法

方格子的付費功能管制比較嚴格所以我還不能選付費功能。或許在穩定獲得訂閱用戶前站方認為內容的品管很重要。就好像Youtube也是經營了數年才開放付費訂閱。Spotify的podcast功能甚至上線一、兩年了也還沒有付費或是donate之類的功能。

好吧。想收費的那幾篇我先押著，讓內容更充實點。先繼續閒聊系列。首先就來聊聊雜湊演算法吧。

如果您是電腦相關科系的學生，或許你會懷疑這門單純的技術真得撐得起一些閒聊的文章嗎？我想三千字絕對不是問題。比較麻煩的是去年年底方格子好像上了一些新功能。在那之後，只要我輸入的內容太多，可能二、三千字，編輯框就會發生很大的延遲。使得我準備用來收費的其中一篇寫到後面寫的很辛苦。

Hash Function，中文翻「雜湊函式」或是「哈希函數」，兩個譯名用的都大有人在。我喜歡前者，稱它雜湊演算法；後者是音譯，而且譯得不夠有技巧，與這個函式的行為完全沒有關聯（至少我想不到）。不過實際上還有一個更合適的名稱，那就是「摘要演算法」，看倌們慢慢往下看就會了解其中緣由。

雜湊函式是電腦科學裡面一種常見的演算法，使用的場景十分多元，到處都看得到。它的觀念很簡單，非常容易上手。我甚至以為正統電腦科學的第一門課《計算機概論》裡面就有介紹，不過我調查的結果是否定的。但我還是感覺要在高中或大學的學程裡面碰到；若是在研究所才碰也太慢。

雜湊函式是一個包裏了一堆運算的黑盒子函式，裡面通常是一堆位元運算的組合。它接受任意長度的輸入值，然後吐出對應的（固定內容的）並且固定長度的輸出值。它可以用底下的公式表示。H為雜湊函式，a、b為輸入的值，而a'與b'則分別是a或b輸入H後得到的輸出值。

上面提到輸入與輸出是對應是（固定的），指得是假如輸入a時輸出a'，則你每次輸入a都一定會輸出a'，不會發生輸出值不一致的情形。由於輸入與輸出有對應關係而且輸出值的長度固定，我們也經常會稱輸出的值是輸入值的『特徵值』（亦稱摘要值（digest）），尤其是運用在輸入值的長度經常大於輸出值的時候。原因是當我們看到兩個輸出值，比如a'與b'，我們就能分辨得出來兩者的『特徵』不同，所以原先的輸入值也是不同的。反之，若看到a'和a'兩個相同的輸出值，就該知道他們的輸入值也該相同。當你要進行確認的時候，只要把原先的輸入值（比如a）丟到H裡面算一下，看看是否與某個輸出值（比如a'）相同就好。

上面已經提到幾個雜湊函式的硬要求，在此整理如下：

除了硬要求外，還有幾個軟要求（或特性）：

若是a'等於b'則稱為碰撞（collision）。碰撞是一定會發生的，因為輸入值的樣本空間無限，而輸出值的樣本空間有限（固定長度的關係），所以不可能確保不會碰撞。但是雜湊函式要盡量確保碰撞的機會低，或是確保某個輸出被碰撞的機會是固定的，而不是特別容易撞到某個輸出。前面提到，雜湊函式的輸出值也被稱為是特徵值。若是太容易發生碰撞，或是碰撞的情形太偏跛就無法確保『特徵』的義意，也會讓該雜湊函式失去某些場景下的應用。

比如我們在檢查某個巨大的檔案有沒有被異動時，我們就會用雜湊函式算出特徵值，並將這個特徵值安置在某個比較小的空間備查就好，而不需要準備一個巨大的空間來安置巨大檔案。若是特徵值容易碰撞，則這個異動檢查就變得沒有義意，可能發生檔案遭到異動卻無法檢查出來。

雖然我查的資料沒有直接提到這個特性。但我認為雜湊函式的結果是要不可逆的，也就是可以用雜湊函式將a算出a'。但是只給你a'時，你無法通過算式算回a。這應該不難理解。雜湊函式的黑盒子裡有破壞性的運算，將輸入值又拆又摺的，讓最終的輸出沒有足夠的資訊可以推導回去。這種特性又導致雜湊函式被稱為one-way hash function，也就是能從a一條路算到a'，但是a'回不了a。其實也就是在名稱上說了它是單行道，不可以逆行。

有one-way function，當然也有two-way function，但不是指雜湊函式。two-way function是加密演算法的別稱，一條路是做加密，另一條路則是解密。

雖然我這裡稱它的結果不可逆，但是嘿嘿嘿嘿...我們後面說。

這也不是硬規矩，但一個雜湊函式做不到這點，其應用將會大受侷限，可能立馬會被丟棄。雜湊函式經常與加密演算法一起用來保護資料。有些加密演算法已經夠慢了，雜湊函式當然不可以跟著拖抬錢。除此之外，如果雜湊函式的計算時間或運算量有明顯差距的話，可能被拿來分析並猜出原本的輸入值。雖然很難完全做到毫無差距，但是縮短差距能增解分析的難度，降低被破解的機會。

雖然這個沒有在定義上直接被列為特性。但是做不到這點的雜湊函式恐怕沒人敢用。前面提到，碰撞的機會要愈低愈好。如果你執行雜湊前就能預測結果的話，那你也一定能知道哪些輸入會有某個固定的輸出，也就是說，你可以很容易的發生碰撞。這會讓大部份雜湊函式的應用變得無效。

打個比方。有間商店使用雜湊函式來計算特徵值作為交易金額比對時的依據。假如金額10和1000的雜湊結果一樣，那花費1000元進行購買的消費者就可以和商店抱怨，聲稱自己只有花費10元，甚至請商店退款990元。Google在2017年有對SHA1雜湊算法實作碰撞攻擊。有興趣的可以去看一看。

前面已經提到一些使用場景，在進入下一個章節的轉折前，我在這裡依照實務上的運用做更詳細的整理吧！

這個前面就有提到一些。因為雜湊演算法的輸入與輸出成對，因此輸出可以代表它是來自某個輸入，可以說是該輸入的『特徵』。當我們的輸入非常巨大時，因為輸出的長度固定，使得我們可以很有效率的把某個巨大的輸入的『特徵』保留下來做為訊息驗證碼使用。訊息驗證碼用來檢查原始的文檔是否有遭到異動，比如作業系統在開機後可以檢查自己的設定或是可執行檔是否遭到非預期的修改（像是中了電腦病毒，或被駭客/盜版者變更）。當然，也可以反過來為電腦病毒與惡意程式做MAC，然後製作成病毒特徵庫，早期的防毒軟體就相當依賴這個技術。現在的防毒軟體如果只用病毒特徵庫已遠遠不足，因為病毒種類太多，變種太快。好比現時的covid-19變種太多太快，很難製作有效的疫苗。

訊息驗證碼又分成帶key和不帶key的。帶key的表示計算訊息驗證碼的過程中會用到加密演算法。除了確保某個輸出是來自某來輸入之外，更確保訊息驗證碼是持有金鑰的人計算出來的，比如HMAC。HMAC的key屬於單一金鑰，因此也常常與單一金鑰搭配使用。我稍微查了一下有沒有人搞雙金鑰的MAC，看起來大家寧願用隨機產生的單金鑰做HMAC再外面再用雙金鑰包裏。

數位簽章是訊息驗證的加強版。除了確保內容有沒有更動，更要求內容來自特定來源。詳細我在付費的密碼學實務應用課程裡介紹，在此不贅述。簡單的說，現今要達成數位簽章必須結合雜湊函式+加密+解密。

雜湊演算法經常被用來保護和驗證輸入值。它的核心概念先以使用者的密碼為例說明。首先，我們想要驗證使用者的密碼。但是，我們又不希望真的接觸到使用者的密碼（因為我們只要能驗證就好，拿在手上不是必須，畢盡保管也是一種負擔）。此時，我們就可以用雜湊演算法把密碼轉換成另一個值存起來。這樣我們不知道密碼是什麼，也不用存密碼；而驗證的時候只要對方先把密碼拿去雜湊一下，再將算好的結果送來比對。注意，這個技術有它的撇步，真正安全的作法我們另作介紹。

科學家們設計的加密演算法在經過充份討論後顯得十分強大。這點我在付費的文章中會多做討論。總的來說，一般攻擊者不會以破解演算法為目標，只有密碼學家才可能這樣搞。一般的攻擊者的目標都是想辦法繞過加密演算法，比如設法偷金鑰。因此，金鑰的保管是非常重要的議題，也是一般開發人員真正要面對的棘手難題。對於這個問題，我也一樣在付費的文章裡多做討論。這裡先把PBK拿出來說嘴。所謂的PBK就是將使用者輸入的密碼轉成金鑰的一種技術。這門技術中，雜湊函數就扮演了重要的角色。其實做這個轉換的原理也很單純，最「手工」的做法就是把password拿去hash然後將hash後的結果作為金鑰（警告：這個做法不安全，詳細請看我的實務教學文章），這把金鑰不存放在任何地方，用完就丟。下次使用者要解密，只要請使用者再輸入一次password就好。如此，攻擊者就算成功入侵你的系統也沒辦法找到金鑰，而那些加密了的密文當然也就不會被解開。

區塊鍊是火紅的題目，我會另開專題介紹，這裡也只粗略的說明一下。在提及區塊鍊之前，先說明雜湊鍊（hashchain）的概念。所謂hashchain就是把某個輸入，比如a，拿去做多次雜湊運算。第一次的hash由a算出了a'，而第二次則是將a'作為輸入值，算出a''，以此類推做多次。如果攻擊者要從a'破解到a很難的話，那麼理論上攻擊者要從a''破解到a就更難了。區塊鍊裡面就用上了這個技術，然後再加上一些其他的技倆，使區塊鍊變得更堅不可催。

上面提到的各種運用簡直都超完美。不難看出來，反碰撞與不可逆的特性被用得淋漓盡致。雖然雜湊演算法有碰撞的隱憂，但是機會很低，幾乎可以乎略不計。然而道高一尺魔高一丈。問題竟然發生在演算法的外面。也可以說，雜湊函數有什麼樣的特性就有什麼樣的原罪。底下介紹的Rainbow table就是雜湊函數使用者必須想到的威脅。

前面提到，雜湊函數有不可逆的特性。然而，雜湊函數的輸入與輸出是成對的，我們可以輕易得知輸入a會得到a'，那我們看到a'時猜想輸入值是a，不就達到了逆轉的效果(*註1)？更進一步的猜想，我把所有可能的輸入-輸出做成一張表，那麼不就可以透過「查表法」將各種可能的輸出值「解回」輸入值？是的，這個是有可能的，而那張表就叫做rainbow table。前面提到，我們可以用雜湊函數保護密碼。當你以為one-way function能保護密碼時，攻擊者就可以透過rainbow table把密碼「查」回來。

你可能會想：「誰會這麼無聊去做rainbow table？一個有效的表可以預見的會非常非常的大」。然而這種無聊人士到處都是，甚至還能請Google參一角。舉一個實際例子。我用SHA-1雜湊函數算出底下的特徵值：

你猜得到原始的輸入值是什麼嗎？想知道答案就直接把上面那串值丟進Google Search吧！

如果你查到了答案，想必會非常驚訝。然而，如果正確的使用雜湊函數，就能有效的達到它原有的效果。至於什麼是正確的使用方式？我們在付費的文章裡繼續滿足各位的願望。

註1：輸出是a'時，輸出可能是a也可以是某個未知的值，因為有可能發生碰撞；但碰撞機會低，所以我們仍能接受這個逆轉的效果。