前言

網站被拖庫后，一些弱口令的 hash 很容易被破解還原。本文講解一種新的存儲方式，使攻擊者跑 hash 變得更麻煩。

傳統儲存

對于大多數系統，用戶名和密碼都是這樣存儲的：

一個賬號對應一個密碼，這是很自然的想法，實現起來也很方便；而且密碼在存儲前經過 hash，也是比較安全的。

不過，盡管密碼 不是明文 的，但它和賬號的對應關系卻是 明確的。攻擊者可針對某個有價值的用戶，單獨針對其 hash 進行暴力破解。

那么是否有方案，既能實現用戶名、密碼的認證，同時又不透露它們之間的對應關系？

合并儲存

既然不能透露對應關系，那顯然需要一個單獨的表來存放它們 —— 事實上這個表只需一個字段就可以，只儲存 二元組的 hash：

key = hash(user, password)

這樣，唯一的 對應唯一的 key；而通過 key 既看不出用戶名，也看不出密碼！

table_key_set

其他和密碼無關的資料，則儲存在 資料表 里：

table_userinfo

（資料表里的用戶名雖然是明文的，但它不屬于認證需要的數據，因此不在本文討論的保護范圍內）

認證步驟

用戶注冊時，后端先通過 資料表 查詢用戶名是否已注冊，保證用戶名是唯一的。然后將 的 hash 值（即 key）添加到 key_set 表里；其他信息則寫入資料表。

登錄時，服務器根據提交上來的 ，使用同樣的算法算出 key，并檢索是否存在于 key_set 表中 —— 若存在，則認證成功；反之，則認證失敗。

認證成功后，即可根據 用戶名 訪問 資料表 中相應的記錄，進行具體的業務操作。

修改密碼很簡單，只需刪除舊 key，添加新 key 就可以；注銷用戶也同理，直接刪除 key 即可。

這樣，認證相關的數據中，就不會出現任何有意義的信息了，甚至連用戶名都沒有！

FAQ

A：將所有賬號的認證信息混在一起，會相互干擾嗎？比如用戶 A 和用戶 C 使用相同的密碼，會不會有影響？

Q：顯然不會。因為 key 并不僅僅代表密碼，同時還蘊含了用戶名。只有當 用戶名、密碼同時符合時，才能匹配到數據庫中的 key。只要有一項不符合，仍然查無此 key。

A：key 之間會存在沖突嗎？

Q：盡管用戶名是唯一的，但 key 還結合了密碼因素，因此不能保證所有 key 絕對唯一，理論上仍有沖突的可能。

不過無需擔心，只要 key 足夠長就能有效避免。例如選擇 32 字節，那么空間就有 256^32 ≈ 10^77。即使網站有 10 億用戶，沖突的幾率仍小得忽略不計。

A：賬號 <"jack", "123456"> 和賬號 <"jack1", "23456"> 的 key 會不會一樣？

Q：當然不會。二元組的 hash 值，顯然不能先合并，再計算。而必須先單獨計算，合并后再計算。現實中我們可以用 HMAC 函數，例如：

key = hmac_sha256(user, password)

一般需要同時 hash 兩個參數的場合，用 HMAC 是最方便的，并且更權威。

A：雖然 key_set 表的數據是無意義的，但其他表仍會泄露用戶名等信息，這樣還有意義嗎？

Q：我們的目的并不是防止 用戶名 等信息的泄露，而是抹掉 用戶名 與 密碼 之間的關聯，讓破解更麻煩（有多麻煩下面會講解）。

A：如果有人忘記了密碼，那么這個用戶的 key 是不是永遠不知道了？

Q：確實~ 不知道密碼就無法算出 key。不過重置密碼的功能還是可以實現的，等會我們會討論。

優勢

用了該方案之后，即使 key_set 表泄露，用戶名及密碼都不會暴露。攻擊者還得設法獲得其他表，或從網站上爬取數據，才能獲得實際的用戶名。

事實上，即使知道某個用戶名，也無法找到對應的 key —— 因為計算 key 不僅需要用戶名，還要密碼！光知道用戶名是不夠的。

當然，即使不知道某個用戶對應的 key，但想破解其明文口令，仍然是可行的。假設攻擊者確定有個叫 alice 的用戶，則可通過如下邏輯跑字典：

for each word in dict
    key = hash('alice', word)

    # 查詢該 key 是否存在
    if table_key_set.exist(key)
        print '破解成功，密碼是', word

和傳統破解不同的是，現在每猜一個口令就得查表一次，成本就大幅增加了！并且現有的絕大多數破解工具，都沒有提供基于查表的解決方案，因此給攻擊者增加了不少復雜度。

提升成本

作為防守方，也可以人為提高查表門檻 —— 我們往 key_set 表里填充大量無用數據，故意將表撐大。而攻擊者并不知道哪些是真實的，哪些是無用的，只能都將它們進行索引等處理，這樣就增加了破解所需的資源！

如果攻擊者直接用現成數據庫查表的話，那效率顯然會非常低，密碼破解速度將被限制在數據庫查詢速度上。對于數據庫來說，幾萬的 query/s 已經很快了，通常也足夠用了；但對于跑字典，幾萬的 hash/s 就太慢了。例如經典的破解工具 hashcat，簡單的算法能達到上億的 hash/s，如果 GPU 夠好，甚至還可以再提高幾個量級！

這個速度，對于查表來說是很難達到的 —— 即使攻擊者自己實現一套更優化的算法。因為查表需要大量的內存占用和訪問，使得很難利用硬件加速。（可參考 對硬件有抵抗效果的 Hash 算法）

同時，數據庫體積被人為撐大后，也極大增加了拖庫時的下載成本！

記錄填充

對于無用的填充數據，我們也不是完全隨機生成的，而是通過一定的規律去產生。例如基于一個口令進行推導：

for i = 0 ... 10000
    key = hmac(PWD, i)
    table_key_set.add(key)

這樣管理者只需提供 PWD 這個值，就能產生 10000 條無用記錄。由于攻擊者并不知道其中的規律，因此也就無法進行區分了。

當未來數據庫記錄太多時，我們可以用同類似的辦法，刪除一些無用記錄；另外，即使忘了無用記錄的條數，只需通過二分法，用少量的次數就可以試出。

加鹽

前面為了簡單描述，我們省略了和 鹽 相關的東西，現在將其補回來。

由于 鹽 需要和 用戶名 關聯，因此無法存儲在 key_set 表中，只能存放其他表中，例如存在 資料表 里。

用戶注冊時，生成一個隨機串作為鹽，并保存。接著用 三元組的 hash 值作為 key：

key = hash(username, password, salt)

其他的步驟則保持不變。

登錄時，先根據用戶名查詢出相應的鹽，然后使用同樣的方式計算 key。這樣，就把鹽融入到 key 里面了。

加鹽還是很有必要的。因為用戶名和密碼大多是有規律的，如果不加鹽，那么 key 也是防不住彩虹表的。

忘記密碼

現在來講解本方案的唯一缺陷 —— 密碼重置。

由于用戶名和密碼不再有關聯，因此一旦有用戶忘了密碼，想對其進行重置，這就非常棘手了 —— 因為不知道密碼，就無法知道對應的 key！

但不用擔心，解決方案還是有的。首先可通過其他手段，證明這個帳號的擁有權，比如短信、郵箱等。

通過認證后，用戶就可以設置新密碼了 —— 系統生成新 key，添加到 key_set 表里，舊 key 則仍保持殘留。

但是，殘留會有問題嗎？顯然有！如果舊密碼以后想起來了，那還是可以登錄的。這樣一個帳號就可以有多個密碼登錄，顯然不安全！因此得改進。

事實上，只要在重置密碼時，將 鹽 也進行重置，就可以避免這個問題了。因為用新鹽算出的新 key，和舊 key 完全不搭邊了：

new_key = hash(username, password, new_salt)

同時，舊鹽一旦被覆蓋，也就永遠消失了，沒有任何人知道。不知道舊鹽，當然就無法計算舊 key。所以那些殘留的 key，是不會出賣曾經用過的密碼的！

當然唯一的缺陷，就是殘留的 key 會白白占用一條記錄。不過我們本來就有意將 key_set 表撐大，因此也就不在乎這些殘留數據了。如果真擔心用戶不斷重置密碼，產生大量無用的 key 將數據庫撐爆的話，倒是可以限制重置密碼的頻率。

這里的巧妙之處，在于一鹽兩用：最新的鹽，則是防止拖庫后的彩虹表攻擊；曾經用過的鹽，則起到 密鑰 的作用。并且這個密鑰已從世上消失了，因此殘留的 key 是不會有安全隱患的。

總結

和傳統存儲方案相比，該方案將敏感信息獨立存儲，并且不再顯式透露 用戶名 和 密碼 的關系。

雖然從算法上看，該方案并沒有提升暴力破解的難度，但從工程化角度來看，倒是增加了暴力破解的復雜度 —— 只要攻擊者的對超大數據的查詢算法實現的不夠好，那么 跑字典 的速度就難以提升，從而成為密碼破解的瓶頸。