登入微信需要密碼，打開郵箱需要密碼，手機支付需要密碼?，現代人生活離不開密碼，但你的密碼安全嗎？你知道使用你知道使用和很多人一樣的密碼，不僅僅損害使用者個人的安全性，甚至還會被用于攻擊其他用戶嗎？

即便一般網站會設計規則禁止用戶設置諸如 123456 或 qwerty 之類非常容易識別的弱密碼，但是對于更“時尚”的弱密碼就無能為力了。比如隨著《神奇女俠》的熱映，流行的密碼可能也隨之從 superman 變成 wonderwoman。

一群以色列研究人員 ，近日在一場密碼學大咖云集的研討會RWC 2019 上，提出一種創新方案，使用一種增強了抗干擾能力的多方計算協議，可以在不損害用戶密碼隱私性的前提下，系統地發現并統計出現的頻率很高的弱密碼，且統計結果不會被攻擊者輕易操縱和篡改。這種方案可用于幫助用戶更好地選擇自己的密碼，降低受到攻擊的風險。

如何統計哪些密碼最常用？

在這篇論文How to (not) Share a Password: Privacy preserving protocols for finding heavy hitters with adversarial behavior中，Moni Naor、Benny Pinkas、Eyal Ronen 等人指出，自從1961年麻省理工學院（ MIT ）在 CTSS 共享操作系統中使用密碼以來，現代意義上的密碼已經有了半個多世紀的歷史。如今隨著移動互聯網和物聯網的蓬勃發展，密碼已經滲透到了我們生活中的各個角落。但是很多現實中的例子反復向我們證明：密碼并不意味著絕對安全，即使密碼是由用戶自己選取的。

一方面，密碼保證安全的一個前提條件是密碼本身必須是隨機選取的，即密碼含有比較高的信息熵。但是這樣的強密碼在提供很好的安全性也為記憶帶來了很大負擔，特別是在現代人需要記住很多個不同賬戶的密碼的情況下。

于是對于那些隔幾個月才登錄一次的賬號，常常會出現登錄前必須先重置已經忘記的密碼的情況。為了方便起見，很多人實際上會選擇比較容易記憶、同時信息熵也較低的密碼。

另一方面，由生日或者連續數字/字母構成的弱密碼往往非常容易被猜到，并不能起到應有的保護作用。而且流行的弱密碼不僅僅損害使用者個人的安全性，甚至還會被用于攻擊其他用戶。

比如某個網站泄露出明文存儲的用戶密碼以后，黑客就可以選擇里面出現頻率比較高的密碼組成字典，用于攻擊其他網站的用戶。因為不同網站用戶選擇密碼的分布一般是大致相似的，于是一個網站的用戶中流行的密碼被另一個網站用戶使用的概率也是顯著高于隨機選取的密碼的，黑客便可借此極大地提高攻擊的效率。

為了避免弱密碼帶來的安全性隱患，很多系統會選擇禁止使用弱密碼，為此需要維護一個常用弱密碼的黑名單。這個黑名單包括一些常見的模式和通過以往的密碼泄露事件已知的流行密碼。

那么問題來了——流行密碼往往是隨著時代不斷變化的，應該如何去系統地統計并發現哪些密碼是出現頻率很高的弱密碼呢？直接統計密碼明文顯然不是一個好主意，在安全性上有很大的漏洞；即使是統計密碼的（未加鹽的）哈希值的頻率也會帶來很多安全上的隱患。Eyal Ronen 所做的報告中就提出了一個解決上述問題的方案。

一位信息泄漏與The Password Game

要統計常見密碼必須滿足的第一條要求，就是不要對用戶造成傷害，或者盡可能減少對用戶的傷害。

從攻擊者的角度來看，一個公開的常用密碼黑名單，實際上就是一個攻擊者夢寐以求的字典，可以用來幫助其猜測用戶的密碼。此外公開的密碼黑名單也可能成為系統被攻擊的漏洞。

另一方面，從用戶的角度來說，雖然統計用戶的密碼必然要求記錄有關用戶密碼的信息，但是如果只泄漏密碼中的一位的話，其實對于安全性的影響是微乎其微的——因為攻擊者只需要多花一點時間就可以猜到這一位信息。

我們可以通過如下猜測密碼的博弈游戲來說明：攻擊者 A 希望攻擊一個設備 D，為此 A 需要選定一個長度為 L 的猜測密碼列表，若 D 的密碼在列表 L 里，則 A 獲得勝利。

在這個博弈中，如果A 在有一位信息泄漏的情況下可以用一個長度為 L 的列表以概率 delta獲勝，則另一個攻擊者 A’ 只需要選擇一個長度為 2L的列表即可在沒有泄漏的條件下實現以相同的概率 delta獲勝。更進一步，如果使用了具有差分隱私保護的算法，則 A’ 不需將列表長度加倍也可以保持相似的勝率（對于實現了 eps-DP 的差分隱私方案，A’ 使用長度為 L 的列表即可達到不小于 的成功率）。

在計算理論中，尋找常見密碼實際上就是解決一個尋找重元素（heavy hitter）的問題，即從一列輸入元素中發現出現頻率大于一定比例的元素。在這個過程中，我們希望每個用戶的密碼泄漏的信息不能超過一個比特，以保證用戶的隱私性和安全性。另外我們還希望false negative 的概率是可忽略的，即幾乎不可能錯過任何一個弱密碼；對于false positive可以適當放松，但是也希望其概率盡可能小，以減少正常的密碼被錯誤拒絕的概率。

類似的問題之前已經被研究過，不過通常需要一個一定程度上可信的第三方，或者是若干個沒有串通的第三方。但是在現實中這些假設都過于理想化了。現實中除了缺乏一個可信的第三方去進行統計以外，還可能出現攻擊者試圖阻止統計者找到一個弱密碼黑名單的情況。為此我們也需要考慮如何避免統計結果被操縱或篡改。

使用傳統的多方計算技術可以部分地解決上述問題，即實現對于用戶的隱私的保護，但是抵抗惡意干擾的能力比較弱。所以 Eyal Ronen 等人在這個報告里講到的方案，實際上使用了一種增強了抗干擾能力的兩方計算協議。該協議實現的正確性如下：

一個半誠實的方案

這個方案源自于 【BNSTS17】 這篇論文的工作。實現的方式是選擇一個輸出長度為l 比特的哈希函數，可以把任意長度的密碼給映射到長度為 l 的二進制串上，且出現碰撞的概率較低。

然后向每個用戶發送一個隨機數 r，要求用戶返回 r 和 H（password）的內積 v（如下圖所示）。收到 v 以后，統計者（服務器）再對所有可能的 x 依次更新 T[x] 的值（T是一個長度為 2^l 的向量）。

通過簡單的計算可以驗證，如果 x 作為密碼的哈希值出現的頻率高，則相應的T[x]的值也會很大。因為T[x] 本質上是所有的 x 加上一個隨機的噪音。因此只需統計出現頻率超過一定閾值的 T[x] 即可得到一個關于常見密碼的哈希值的列表。如下圖所示。

但是這種方案需要用戶一側比較誠實地配合才行。否則如果用戶刻意選擇相反的結果，則可以減少相應的密碼被統計到的次數，即變相地實現了隱藏一個常見密碼的目的。

一個基于平方剩余的方案

對于兩個大素數的乘積 N=pq，很難判斷 Jacobi Symbol 為 1 的那些數是否是關于 N 的平方剩余。利用這個性質，我們可以對于每個 v 計算如下的 e，并以此為依據更新 T[v]。 此后的步驟與上一個方案相似。

需要指出的是，上述方案在攻擊者知道一個非平方剩余的時候并不安全。但是好在攻擊者很難以比隨機猜測更好的方法找到一個非平方剩余，且上述方案的安全性可以歸約到這個難以找到 nQR 的假設。

作為一個完整的方案，我們還需要用戶一方提供一個零知識證明，證明內積運算的結果是正確的。這個零知識證明可以通過 Fiat-Shamir heuristic 改造成非交互式的（參考 Bulletproof，zk-STARK 等）。

關于何時把一個密碼識別為“常用密碼”的閾值，可以參考下圖。

基于平方剩余的方案在實現的性能方面：用戶側的計算需要15秒，且可以在后臺運算；服務器側需要為每個用戶花 0.5 秒左右的時間進行驗證。

同樣的方案還可以用于統計其他場景中的 heavy hitter 問題，例如洋蔥網絡、設備的 PIN 和 pattern、大規模服務提供商的動態密碼分布等。

總結

通過這篇研究可以思考的一個問題是，對于這個統計常用密碼的問題，我們是否真的需要（基于計算復雜性的）密碼學？

如果用戶都是善意的，實際上密碼學的構造并不是必須的。但是如果有惡意用戶試圖操縱統計結果，則不可避免地要用到一些密碼學構造。

另外，關于攻擊者是否可以利用以哈希值存儲的密碼黑名單列表，仍是一個有待研究的問題——盡管現在看來這似乎并不可行。