2017年2月21日 星期二

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

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

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

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

冰城傳奇人物資料裡面的最後那個 byte 稱為 checksum, 就是檢查碼的概念。 這跟銀行帳號或 身份證字號規則 一樣, 多出一位看似無用的數字, 目的是避免不小心抄錯一個字錢就進了錯誤的人的帳號。

假設因為某種原因我無法更改那個檢查碼, 那麼我還能夠改出超人嗎? 其實還是可以的, 如果我改 A 欄位時, 根據 XOR 的規則同時修改不重要的 B 欄位, 檢查碼就不會改變了。

更普遍地說, 計算檢查碼 Z 不一定要用 XOR 函數, 也可以改用其他更複雜的函數 Z=f(x)。 這裡簡單用一個 x 來代表前面 n-1 個有意義的 bytes 全部。 (假設人物資料共有 n 個 bytes。) 因為 XOR 要逆回去計算很容易。 所以小屁孩很容易 "刻" (找到) 一個裡想的 y, 它的值跟 x 不一樣, 但卻能滿足 f(x)=f(y) 、 通過遊戲公司的測試。 顯然, 如果把 f 改成加法或乘法也一樣無效, 因為減法跟除法都很容易算, 小屁孩很容易反過來求出 B 欄位應該填什麼值才能矇混過關。

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

滿足 「正著算很簡單、 逆著算很煩」 的函數通稱為 one-way function; 符合這個特性的雜湊函數就稱為 單向雜湊函數 one-way hash function: 餵一個任意字串 (可以是一個很大的檔案) 給它吃, 它會算出一個短短的數字; 但是想要找到其他 「可以產生同一個短短數字」 的字串 (以便以假亂真) 非常困難。 你可以說這個數字就像是這個檔案的 (看似亂碼的) 摘要一樣: 不同內容的檔案 (即使內容只差一個 bit) 算出來的摘要也會不一樣。 好吧, 應該說, 兩者相同的機率趨近於零。 高中資訊學科中心 的 「雜湊函數」 那一節的白話解釋寫得很讚。

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

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

現在你可以約略理解了: 比特幣裡面的 「挖礦」 跟 「避免作弊」 這兩件事, 都是靠著單向雜湊函數的特性來實現的。 因為逆著算某些東西需要窮舉, 所以想要找出適當的雜湊值來獲得新的比特幣需要花很多算力, 也就是俗稱的挖礦。 因為逆著算某些東西需要窮舉, 而且全球比特幣的交易歷史紀錄被分批整理成一個個的區塊, 這些區塊再串成一長串的區塊鏈 (blockchain), 前後區塊以 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 裡面的值相同; 而存這個值比較安全, 因為那個函數是單向的、 不可逆的。

在 /etc/shadow 裡面, 密碼欄位用 $ 切成三段。 第一段是函數代號, 也就是說這個密碼到底被哪一個單向雜湊函數處理過。 根據 這一篇, $1 表示 MD5、 $5 表示 SHA-256、 $6 表示 SHA-512。 (我沒看過 blowfish 的實例。) 中間那一串稱為鹽巴 (salt)。 對, 效果類似調味用的 -- 最後面那一長串其實不是 f(密碼), 而是 f(密碼加鹽巴) 鹽巴通常是系統要存密碼之前用亂數產生的。 這樣一來, 你從密碼檔裡甚至無從判斷兩個人是否使用相同的密碼; 想要反推密碼的難度就更提高了。

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

3 則留言:

  1. 以下是我在
    [編程隨想的博客 - 如何構造安全的口令/密碼]
    https://program-think.blogspot.com/2010/06/howto-prevent-hacker-attack-3.html
    的留言.

    我們可以利用 [單向密碼雜湊函式] 算出密碼, 這樣每次登入網站需要輸入密碼時, 可以 "算" 出來, 不需要 "背密碼". 我把下面 python script 也放到手機裡, 萬一哪天出門需要輸入密碼, 拿出手機算一下就知道了, 不用背.


    ------------- 以下是我的留言 ----------------


    分享一下我個人產生 Hash 的方式, 跟編成隨想的最後一個方式大同小異.
    好的演算法不怕攤在陽光下, 這邊給大家參考.


    ## Shell script (把這隻 script 存進 ~/.bashrc 或 ~/.bash_profile, 用類 Unix 的人都懂的) :

    ##################################################
    #asKansweR script in ~/.bashrc 或 ~/.bash_profile.
    asKansweR () {
    read answeR
    echo -n "$answeR" | sha512sum | sed -n 's/^\(.*\) -$/\1/p' | tr -d '\n' | xxd -r -p | base64 | tr -d '\n' | sed -n 's/^\(.*\)/\1\n/p'
    }
    ##################################################

    這個 script 我相信 windows 10 以上也可以跑, 因為 windows 10 現在好像可以支援 Ubuntu 的 bash 的樣子, 不須安裝額外東西, 大家可以玩玩看.

    sha512 計算出來的 hash 值會再用 base64 編碼轉換一次, 這樣訊息密度比較大 (相同長度產生的組合可能性比較高, 因為 base64 的合法字元從 a ~ z, A ~ Z, 還有少數幾個符號).
    你要把以上存在 shell script 也可以, 那就把 asKansweR 函式名稱拿掉.


    ## Python :

    ##################################################
    #asKansweR.py
    import base64
    import hashlib

    w = None

    while w != "exit":
    w = input("")
    if w == "exit" or w == "quit":
    break
    ## Generate sha512 hash (message digest) (in binary format?) from original message.
    x = hashlib.sha512(str.encode(w)).digest()
    y = base64.b64encode(x)
    print(y.decode("utf-8"))
    ##################################################

    Python 版的執行方式像這樣 : "python3 asKansweR.py", 然後一樣開始打字, 打完按 Enter, 輸入 "exit" 或 "quit" 再 Enter 跳出.

    這個 script我自己也是有放在手機上, 外出時如果需要輸入密碼我可以把手機掏出來當場 "算" 出密碼, 不過 andriod 的系統會不會側錄我是另外一回事 ...


    ## 或是使用線上免費網站轉換器 :

    可搜尋 "sha512 online converter", "base64 online converter" ... 之類的, 很好找, 比如這 2 個 :
    http://hash.online-convert.com/sha512-generator
    http://en.1mu.info/tools/hexbase64.html

    這邊注意一下, 這裡的目的只是要實驗或證明這些函式的算法得到的結果是可靠和一致的, 因為把明文資料送給這些網頁工具沒有安全性可言, 你在計算之前已經把明文送給這些伺服器了.
    而且也是要證明這些密碼雜湊函式是開放標準, 隨隨便便都可以取得, 你不用擔心找不到或算不出來.


    ## 密碼產生實際過程 :

    舉例來說, 我的 Message 如果是 :
    apple
    會產生 Message Digest :
    hE2HeRA7lMGPSqTMDDtEdAWFgKmR+6hdPKaYoLyeUsWUD+t6ZaOikOF+ayPulD7MT3PnSQMnJFtP5dXvtZD+sg==

    我的 Message 如果是 :
    apple2
    會產生 Message Digest :
    30dgOP4El5SqOpr+WdmEjIFZppXby4Ul3wG9nCZNrERPynMqDBUFYH4ZWypuXGennNkH34ESa+mmxDC9Xa86Gw==

    Message 你要打多長都隨你, 要打什麼符號也可.
    但最後的密碼長度我通常只會取大概 15 位數, 不含 / 和 + 符號, 如果我的祕密字串 (Message) 是 "apple2", 那我對應的密碼 (Message Digest) 就是 "30dgOP4El5SqOpr".
    (Base 64 的目地只是要讓相同長度的密碼產生的組合可能性比較高, 除此之外沒有其他意義. Base64 的合法字元除了 a ~ z, A ~ Z, 還有 / 和 + 2 個符號, 但這 2 個符號我個人習慣是不會用的.)

    只不過沒有試過編成隨想說的不斷遞迴幾千次的計算, 我曾經考慮過 pbkdf2 而不是 sha512 做遞迴計算, 但想想我其實不需要用到這麼安全, 因為安全的瓶頸其實是在網站資料庫本身.

    回覆刪除
    回覆
    1. 哎呀, 每行開頭的空白縮排被 Blogspot 去掉了.
      Shell Script 沒關係, Python 代碼裡面的 "while" 和 "if" 內沒有縮排會沒辦法跑的. 捕上去就 ok.

      刪除
  2. 大幅改寫: 改從 「打 game 改超人」 切入、 加入一段略談 bitcoin、 請臺大資工薛智文教授 校閱指正

    回覆刪除