白話「單向雜湊函數」 & 如何手動修改密碼檔

[2017/12/10 改寫/新增內容。 感謝臺大資工 薛智文教授 校閱指正。]

我們小時候的 RPG 沒有連線， 都是在自己的電腦上存檔而已， 所以很容易研究、 竄改人物的各種屬性跟裝備的數值。 例如我玩 「創世紀」 (Ultima III) 的時候， 就曾經： (1) 存檔， 並備份到別處。 (2) 讓一群弱弱的怪獸打幾拳， 再把牠幹掉、 取得金幣 (3) 再存檔。 檢查先後兩次存檔內容的差別， 就可以知道改哪幾個地方可以讓人物的生命點數跟金錢爆表 :-)

後來對另一款遊戲 「冰城傳奇」 (Bard's Tale) 也如法泡製， 結果改過的人物都壞掉了， 無法載入遊戲 :-( 研究了很久， 才發現最後面有一個看不懂的 byte 沒有改到 -- 它是這個人物屬性值的前面所有 n-1 個 bytes 的 XOR。 於是改完屬性之後， 又重算新的 XOR， 再把它填進去， 就又成功地創造出超人 :-)

假設因為某種原因我無法更改那個 檢查碼 (checksum) 那麼我還能夠改出超人嗎? 其實還是可以的， 如果我改 A 欄位時， 根據 XOR 的規則同時修改某個不重要的 B 欄位， 讓兩者的 XOR 值維持不變， 那麼程式碼就不會發現我修改過人物了。

其實銀行帳號或 身份證字號規則 的最後一位數也都是檢查碼。 不過銀行與身份證字號的檢查碼的主要效用是避免 不小心 抄錯一個字匯款或中獎發票獎金就進了錯誤的人的帳號； 如果要避免小屁孩 刻意 修改資料， XOR 或是身份證檢查碼公式顯然是不夠強大的。

更普遍地說， 計算檢查碼 Z 不一定要用 XOR 函數， 也可以改用其他更複雜的函數 Z=f(x)。 假設人物資料共有 n 個 bytes， 這裡簡單用一個 x 來代表前面 n-1 個 bytes 全部， 包含上述的 A 欄位與 B 欄位， 而 Z 則是最後一個 byte 的值 (檢查碼)。 因為 XOR 要逆回去計算很容易。 所以小屁孩很容易 "刻" (找到) 一個理想的 y 它的值跟 x 不一樣， 但卻能滿足 f(y)=f(x) 、 通過遊戲公司的測試。 顯然， 如果把 f 改成加法或乘法也一樣無效， 因為它們的逆運算 (減法跟除法) 都很容易算， 小屁孩在修改過 A 欄位之後， 很容易反過來求出 B 欄位到底應該填什麼值才能讓 f(y) 的值維持跟原先的 f(x) 一樣。

所以站在遊戲公司的立場， 他們要問的是： 什麼樣的 f 正著算很簡單； 但反過來算卻很煩， 除了窮舉之外別無他法? 暫時撇開整數與浮點數的不同， 就算是 sin 或 cos 也沒多厲害， 因為它們的反函數也可以用泰勒展開式很快地算出來。

[2021/10/24] 那我們就來看一個例子： 請到 sha256 online 測試， 在上半任意貼一些中英文數字標點符號， 長短不拘， 並且注意下半視窗看似亂碼的那個 64 位數的十六進位數字如何變化。 (除了長度固定之外， 基本上就是沒有規則可言。) 也請搜尋 「sha256 online」， 在其他類似網站輸入一模一樣的文字 (連空格幾個都不能有差)， 觀察是否輸出相同的十六進位數字。

密碼學家很喜歡這一類的函數， 稱為 cryptographic hash function 密碼雜湊函數 或 one-way function 單向雜湊函數。 (我查不到兩者精確的差異) 一個好的密碼雜湊函數 f 應該具有有以下特性：

1. 不論輸入資料多長多短， 它的輸出 (稱為 message digest 或 hash value) 的長度都是固定的。
2. pre-image resistance： 給你一個 hash value y， 想要找出一個 x 使得 f(x) = y 需要花很長很長， 長到不切實際的運算時間。
3. second pre-image resistance： 給你一個輸入值 x1， 想要找出一個 x2 使得 f(x1) = f(x2) 需要花很長很長， 長到不切實際的運算時間。
4. collision resistance： 想要找出任何一組 x1 與 x2 使得 f(x1) = f(x2) 都需要花很長很長， 長到不切實際的運算時間。
5. avalanche effect： 即使輸入資料 x1 與 x2 只差一個 bit， 算出來的結果也會亂得完全看不出關係。 (一顆小石頭就能造成雪崩的概念。)

大推 高中資訊學科中心 的 「雜湊函數」 那一節的白話解釋。 也請參考英文文章： 1、 2、 3、 4； 動畫描述 sha256sum 運算步驟。

補充： second pre-image resistance 和 collision resistance 有什麼差別？ 它們的主要著眼點是從黑帽駭客攻擊的難易度出發， 所以要從這個視角去看比較容易理解。 簡單地說， 對一個 hash 函數的 collision 攻擊 通常比較早成功， 因為對攻擊者而言， 可以任選 x1 與 x2。 至於 second preimage 攻擊則比較困難。 我覺得 這個答案 最專業； 這個應用角度的說明 也很不錯。 從純數學的角度去看， 比較容易錯過重點。

一二十年前， md5sum 還算是一個蠻實用的單向雜湊函數。 從網路下載大檔時， 通常網站會提供一個 md5sum 的十六進位數字讓你驗證下載是否成功。 意思就是說： 如果你下載完之後對檔案下 md5sum 指令， 出來的結果跟網站提供的數字相同， 那麼你的檔案 "應該" (機率趨近於 1) 跟原始檔案一模一樣。 這種應用場合比較沒有暴力破解或惡意篡改的疑慮， 只有 (機率趨近於 0) 超級倒楣的可能性， 所以大家還是持續用 md5sum。

但是隨著電腦的 「算力」 (computing power) 越來越強， 尤其是隨著 GPU 的出現， 用 「窮舉」 的方式來破解 md5sum (尋找可以魚目混珠、 產生相同摘要的另一個字串) 變得越來越可行， 也就是說 md5sum 的保護力變得越來越弱了。 根據楊中皇老師所著的 網路安全， 就連 SHA-1 也不夠安全； 目前常用函數當中最理想的是 SHA-512。

現在你可以約略理解比特幣裡面的 「避免作弊」 跟「挖礦」 兩件事了 -- 兩者都是靠著單向雜湊函數的特性來實現的。 全球比特幣的交易歷史紀錄被分批整理成一個個的區塊， 這些區塊再串成一長串的區塊鏈 (blockchain)， 每個區塊裡面， 還有前後區塊都以 hash 環環相扣， 牽一髮動全身。 如果想要竄改交易歷史紀錄， 必須倒著算太多 hash 函數， 簡直比登天還難。 相對來說， 當循規蹈矩的挖礦工人簡單多了。 比特幣的一個區塊裡面， 有一個專門讓礦工嘗試填寫各種數值的 4-byte 欄位， 稱為 nonce 。 在適當的時間點， 如果可以找到一個適當的值填入這個 nonce， 讓這一整個區塊的 sha256 hash 落於某個公定的範圍之內， 並廣播通知所有礦友加以驗證， 那就表示你挖到礦了。 隨著時間的推移， 人類的電腦越來越進步， 為了保持挖礦的一定難度， 每隔幾年， 這個 「公定的範圍」 就會更新一次， 變得越來越小越嚴格。 順便一提， crypto-currency 裡面的 crypto 是密碼學 (cryptography) 的字根， 指的是這類新型貨幣採用了密碼學裡面的單向雜湊函數以及 非對稱式加密/解密演算法 當中的數位簽章認證功能 (但並沒有用到它的加解密功能)， 所以 「加密貨幣」 這個名字其實有點誤導。

* * * * *

單向雜湊函數還有另一個應用： 密碼檔。 Linux 的 帳號管理有一個很好的特性： 在必要的時候， 管理員要能夠進入你的帳號做事； 但理想上， 系統最好設計成讓他可以讓他不需要知道你的密碼。 (試想： 如果你在其他地方的帳號採用跟這裡相同的密碼...?) 如果你曾忘記密碼、 跑去找管理員， 可能就會發現： 管理員只能幫你改； 但他不能幫你找出舊密碼。 如果管理員竟然可以幫你查出遺忘的密碼， 那你... 乾脆直接去裸奔算了...

為什麼這麼說呢? 原來密碼檔裡永遠都不應該儲存密碼本身， 而是密碼再經過單向雜湊函數運算過後的結果。 不論是 ssh 登入密碼檔 /etc/shadow 或是 dokuwiki 的 /etc/dokuwiki/users.auth.php 或是其他許多服務的密碼檔， 裡面所包含的字串長這樣： $1$d0lzo8J3$W0gy.g4Y 或這樣： $5$hp19NKFwbuqQKsut$jezzRQn5... 或這樣： $6$8cnmW1GxONptsR$aNdHG8Dj... 它並不是你當初設定的密碼， 而是 f(密碼)， 也就是密碼經過單向雜湊函數運算過後的結果。 系統不需要記住原始的密碼， 只需要判斷你輸入的密碼經過單向雜湊函數之後， 出來的結果是否與存在 /etc/shadow 裡面的值相同； 而存這個值比較安全， 因為那個函數是單向的、 不可逆的， 所以就連偉大的系統管理員或是成功入侵的黑帽駭客也無法得知你的密碼。

那如果預先把 常見密碼 的 message digest 預先算出來變成一個表格， 再反過來查詢， 不就可以破解較弱的密碼了嗎？ 這種表格稱為 rainbow table 彩虹表， 而這種攻擊方式則稱為字典攻擊。

在 /etc/shadow 裡面， 密碼欄位用 $ 切成三段。 第一段是函數代號， 也就是說這個密碼到底被哪一個單向雜湊函數處理過。 根據 這一篇， $1 表示 MD5、 $5 表示 SHA-256、 $6 表示 SHA-512。 (我沒看過 blowfish 的實例。) 中間那一串稱為鹽巴 (salt)。 對， 效果類似調味用的 -- 最後面那一長串其實不是 f(密碼)， 而是 f(密碼加鹽巴) 鹽巴通常是系統要存密碼之前用亂數產生的。 這樣一來， 你從密碼檔裡甚至無從判斷兩個人是否使用相同的密碼， 而且這也讓彩虹表/字典攻擊失去效力， 卻又不需要增加使用者的記憶負擔。

如果你的系統有安裝 whois 套件， 就可以從命令列上用 mkpasswd 指令產生這三段字串： mkpasswd -m sha-512 或 mkpasswd -m sha-256 或 mkpasswd -m md5。 輸入密碼之後， 直接把印出來的那一串貼到密碼檔的密碼欄位， 密碼就改好了。

如果在命令列上用 -S 指定 salt ， 像這樣： mkpasswd -m sha-512 -S 'abcdefgh'， 那麼印出來的結果， 第二與第三個 $ 之間就會是你所指定的 salt (以上例而言就是 abcdefgh)。 相同的 salt、 相同的密碼， 才會產生相同的結果； 相同的密碼， 只要 salt 不同， 最後的結果也會不同。