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

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

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

如何統(tǒng)計(jì)哪些密碼最常用？

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

一方面，密碼保證安全的一個(gè)前提條件是密碼本身必須是隨機(jī)選取的，即密碼含有比較高的信息熵。但是這樣的強(qiáng)密碼在提供很好的安全性也為記憶帶來(lái)了很大負(fù)擔(dān)，特別是在現(xiàn)代人需要記住很多個(gè)不同賬戶的密碼的情況下。

于是對(duì)于那些隔幾個(gè)月才登錄一次的賬號(hào)，常常會(huì)出現(xiàn)登錄前必須先重置已經(jīng)忘記的密碼的情況。為了方便起見，很多人實(shí)際上會(huì)選擇比較容易記憶、同時(shí)信息熵也較低的密碼。

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

比如某個(gè)網(wǎng)站泄露出明文存儲(chǔ)的用戶密碼以后，黑客就可以選擇里面出現(xiàn)頻率比較高的密碼組成字典，用于攻擊其他網(wǎng)站的用戶。因?yàn)椴煌W(wǎng)站用戶選擇密碼的分布一般是大致相似的，于是一個(gè)網(wǎng)站的用戶中流行的密碼被另一個(gè)網(wǎng)站用戶使用的概率也是顯著高于隨機(jī)選取的密碼的，黑客便可借此極大地提高攻擊的效率。

為了避免弱密碼帶來(lái)的安全性隱患，很多系統(tǒng)會(huì)選擇禁止使用弱密碼，為此需要維護(hù)一個(gè)常用弱密碼的黑名單。這個(gè)黑名單包括一些常見的模式和通過(guò)以往的密碼泄露事件已知的流行密碼。

那么問(wèn)題來(lái)了——流行密碼往往是隨著時(shí)代不斷變化的，應(yīng)該如何去系統(tǒng)地統(tǒng)計(jì)并發(fā)現(xiàn)哪些密碼是出現(xiàn)頻率很高的弱密碼呢？直接統(tǒng)計(jì)密碼明文顯然不是一個(gè)好主意，在安全性上有很大的漏洞；即使是統(tǒng)計(jì)密碼的（未加鹽的）哈希值的頻率也會(huì)帶來(lái)很多安全上的隱患。Eyal Ronen 所做的報(bào)告中就提出了一個(gè)解決上述問(wèn)題的方案。

一位信息泄漏與The Password Game

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

從攻擊者的角度來(lái)看，一個(gè)公開的常用密碼黑名單，實(shí)際上就是一個(gè)攻擊者夢(mèng)寐以求的字典，可以用來(lái)幫助其猜測(cè)用戶的密碼。此外公開的密碼黑名單也可能成為系統(tǒng)被攻擊的漏洞。

另一方面，從用戶的角度來(lái)說(shuō)，雖然統(tǒng)計(jì)用戶的密碼必然要求記錄有關(guān)用戶密碼的信息，但是如果只泄漏密碼中的一位的話，其實(shí)對(duì)于安全性的影響是微乎其微的——因?yàn)楣粽咧恍枰嗷ㄒ稽c(diǎn)時(shí)間就可以猜到這一位信息。

我們可以通過(guò)如下猜測(cè)密碼的博弈游戲來(lái)說(shuō)明：攻擊者 A 希望攻擊一個(gè)設(shè)備 D，為此 A 需要選定一個(gè)長(zhǎng)度為 L 的猜測(cè)密碼列表，若 D 的密碼在列表 L 里，則 A 獲得勝利。

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

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

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

使用傳統(tǒng)的多方計(jì)算技術(shù)可以部分地解決上述問(wèn)題，即實(shí)現(xiàn)對(duì)于用戶的隱私的保護(hù)，但是抵抗惡意干擾的能力比較弱。所以 Eyal Ronen 等人在這個(gè)報(bào)告里講到的方案，實(shí)際上使用了一種增強(qiáng)了抗干擾能力的兩方計(jì)算協(xié)議。該協(xié)議實(shí)現(xiàn)的正確性如下：

一個(gè)半誠(chéng)實(shí)的方案

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

然后向每個(gè)用戶發(fā)送一個(gè)隨機(jī)數(shù) r，要求用戶返回 r 和 H（password）的內(nèi)積 v（如下圖所示）。收到 v 以后，統(tǒng)計(jì)者（服務(wù)器）再對(duì)所有可能的 x 依次更新 T[x] 的值（T是一個(gè)長(zhǎng)度為 2^l 的向量）。

通過(guò)簡(jiǎn)單的計(jì)算可以驗(yàn)證，如果 x 作為密碼的哈希值出現(xiàn)的頻率高，則相應(yīng)的T[x]的值也會(huì)很大。因?yàn)門[x] 本質(zhì)上是所有的 x 加上一個(gè)隨機(jī)的噪音。因此只需統(tǒng)計(jì)出現(xiàn)頻率超過(guò)一定閾值的 T[x] 即可得到一個(gè)關(guān)于常見密碼的哈希值的列表。如下圖所示。

但是這種方案需要用戶一側(cè)比較誠(chéng)實(shí)地配合才行。否則如果用戶刻意選擇相反的結(jié)果，則可以減少相應(yīng)的密碼被統(tǒng)計(jì)到的次數(shù)，即變相地實(shí)現(xiàn)了隱藏一個(gè)常見密碼的目的。

一個(gè)基于平方剩余的方案

對(duì)于兩個(gè)大素?cái)?shù)的乘積 N=pq，很難判斷 Jacobi Symbol 為 1 的那些數(shù)是否是關(guān)于 N 的平方剩余。利用這個(gè)性質(zhì)，我們可以對(duì)于每個(gè) v 計(jì)算如下的 e，并以此為依據(jù)更新 T[v]。 此后的步驟與上一個(gè)方案相似。

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

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

關(guān)于何時(shí)把一個(gè)密碼識(shí)別為“常用密碼”的閾值，可以參考下圖。

基于平方剩余的方案在實(shí)現(xiàn)的性能方面：用戶側(cè)的計(jì)算需要15秒，且可以在后臺(tái)運(yùn)算；服務(wù)器側(cè)需要為每個(gè)用戶花 0.5 秒左右的時(shí)間進(jìn)行驗(yàn)證。

同樣的方案還可以用于統(tǒng)計(jì)其他場(chǎng)景中的 heavy hitter 問(wèn)題，例如洋蔥網(wǎng)絡(luò)、設(shè)備的 PIN 和 pattern、大規(guī)模服務(wù)提供商的動(dòng)態(tài)密碼分布等。

總結(jié)

通過(guò)這篇研究可以思考的一個(gè)問(wèn)題是，對(duì)于這個(gè)統(tǒng)計(jì)常用密碼的問(wèn)題，我們是否真的需要（基于計(jì)算復(fù)雜性的）密碼學(xué)？

如果用戶都是善意的，實(shí)際上密碼學(xué)的構(gòu)造并不是必須的。但是如果有惡意用戶試圖操縱統(tǒng)計(jì)結(jié)果，則不可避免地要用到一些密碼學(xué)構(gòu)造。

另外，關(guān)于攻擊者是否可以利用以哈希值存儲(chǔ)的密碼黑名單列表，仍是一個(gè)有待研究的問(wèn)題——盡管現(xiàn)在看來(lái)這似乎并不可行。