口令安全研究進展

王 平 汪 定 黃欣沂

1(北京大學(xué)信息科學(xué)技術(shù)學(xué)院 北京 100871)2(福建師范大學(xué)數(shù)學(xué)與計算機科學(xué)學(xué)院 福州 350117)3(北京大學(xué)軟件與微電子學(xué)院 北京 102600) (wangdingg@pku.edu.cn)

?

口令安全研究進展

王 平1,3汪 定1黃欣沂2

1(北京大學(xué)信息科學(xué)技術(shù)學(xué)院 北京 100871)2(福建師范大學(xué)數(shù)學(xué)與計算機科學(xué)學(xué)院 福州 350117)3(北京大學(xué)軟件與微電子學(xué)院 北京 102600) (wangdingg@pku.edu.cn)

身份認證是確保信息系統(tǒng)安全的第一道防線，口令是應(yīng)用最為廣泛的身份認證方法.盡管口令存在眾多的安全性和可用性缺陷，大量的新型認證技術(shù)陸續(xù)被提出，但由于口令具有簡單易用、成本低廉、容易更改等特性，在可預(yù)見的未來仍將是最主要的認證方法.因此，口令近年來引起了國內(nèi)外學(xué)者的廣泛關(guān)注，涌現(xiàn)出了一大批關(guān)于口令安全性的研究成果.從用戶生成口令時的脆弱行為入手，介紹了中英文用戶口令的特征、分布和重用程度；總結(jié)了近30年來提出的幾個主流口令猜測算法，并根據(jù)它們所依賴的攻擊對象的信息不同進行了分類；然后，回顧了當(dāng)前廣泛使用的基于統(tǒng)計學(xué)的口令策略強度評價標準；此外，對比了當(dāng)前主流的幾個口令強度評價器.最后，對當(dāng)前研究現(xiàn)狀進行了總結(jié)，并對未來研究方向進行了展望.

身份認證；口令安全；脆弱行為；猜測攻擊；強度評價

隨著信息化進程的不斷推進，人們的日常生活不斷網(wǎng)絡(luò)化，資產(chǎn)不斷數(shù)字化，身份認證逐漸成為保障用戶信息安全的基本手段.基于口令的認證伴隨著大型機的問世而誕生，在20世紀60年代起被廣泛用于大型機的訪問控制[1]，避免分時操作系統(tǒng)的時間片被濫用.20世紀90年代互聯(lián)網(wǎng)進入千家萬戶以來，互聯(lián)網(wǎng)服務(wù)(如郵件、電子商務(wù)、社交網(wǎng)絡(luò))蓬勃發(fā)展，口令成為互聯(lián)網(wǎng)世界里保護用戶信息安全的最主要手段之一[2].

隨著互聯(lián)網(wǎng)的發(fā)展，一方面越來越多的服務(wù)需要口令保護，另一方面人類大腦能力有限，只能記憶5～7個口令[3]，導(dǎo)致用戶不可避免地使用低信息熵的弱口令[4]，在多個網(wǎng)站中重用同一口令[5]，在紙上記口令[6]，帶來嚴重的安全危脅.2004年，比爾·蓋茨對外宣告口令將消亡，微軟公司將使用多因子認證替代純口令認證[7].后續(xù)一系列學(xué)術(shù)研究也分別從口令無法抵抗離線猜測攻擊[8-9]、口令過期策略(password expiration policy)無法保證更新后的口令的不可預(yù)測性[10]等方面論證了口令認證技術(shù)的不可持續(xù)性.與時同時，大量的替代口令的認證方案不斷被提出,比如多因子認證[11]、圖形口令[12]、生物認證[13]、行為認證[14]等.相比之下，研究口令的相關(guān)工作卻較少.

出乎意料的是，時至今日，口令的地位在工業(yè)界不僅絲毫沒有被撼動，反而在越來越多的信息系統(tǒng)應(yīng)用中得到加強.這一現(xiàn)象吸引了越來越多的學(xué)者關(guān)注，開始引起學(xué)術(shù)界的反思.研究發(fā)現(xiàn)，雖然這些替代型方案有的在安全性方面優(yōu)于口令，有的在可用性方面勝過口令，但幾乎都在可部署性(deployability)方面劣于口令，并且各自存在一些固有的缺陷[15].比如，基于硬件(如智能卡、USB key)的認證技術(shù)成本高昂，使用不方便；基于生物(如指紋、虹膜)的認證技術(shù)不具有可撤銷性，且存在隱私泄露問題.因此，學(xué)術(shù)界逐漸開始形成一個共識[2,16-18]：在可預(yù)見的未來，口令仍將是最主要的身份認證方式.

既然口令不可替代，只有深入理解口令的安全性和可用性，人類才能更好地與之共存(living with passwords)[16-17].自2012年以來，口令研究逐漸成為一個熱點，涌現(xiàn)出了一大批關(guān)于口令的研究成果，本文主要關(guān)注安全性方面的研究進展.關(guān)于口令的可用性，讀者可關(guān)注人機交互方面的刊物，它已成為該領(lǐng)域一個重要研究分支[19].需要指出的是，與口令強度無關(guān)的攻擊(如社會工程學(xué)[20]、惡意口令捕獲軟件[21])也不是本文關(guān)注點.

口令安全性研究的難點在于，口令是人生成的，與人的行為直接相關(guān)，而每個人的行為因內(nèi)在或外在環(huán)境的不同而千差萬別.比如說，同樣是注冊一個163郵箱帳戶，有的人覺得這個帳戶不重要，會使用“123456”作口令.有的人后面會經(jīng)常使用這一郵箱，因此采用精心構(gòu)造的一個字符串(比如“brysjhhrhl”，一句詩的首字母)作口令.眾所周知，“123456”是弱口令；但是，如果很多用戶也使用詩詞的首字母作口令，那么攻擊者A很可能了解這一用戶行為，進而“brysjhhrhl”也可能是弱口令.至于這2個口令誰更安全，需要具體考察它們針對4種口令猜測攻擊(見第2節(jié))的抵抗能力.再比如，給定一個口令“Wang.123”，該口令如果是由“Li”姓用戶產(chǎn)生，那么該口令可很好抵御定向在線口令猜測攻擊(targeted online password guessing attack).如果該口令如果是由“Wang”姓用戶產(chǎn)生，顯然它是一個弱口令[22]，無法抵御定向在線口令猜測攻擊；無論對于任何用戶，這一口令都無法抵抗離線口令猜測攻擊[22-23].在用戶脆弱口令行為研究方面，焦點主要集中在用戶的傾向性構(gòu)造模式選擇[24-26]、口令重用[27-28]、基于個人信息構(gòu)造口令[22,29]3個方面.

基于對用戶脆弱口令行為的更深入理解，一方面攻擊者會不斷改進其口令猜測算法,另一方面系統(tǒng)管理員也可以阻止弱口令的使用.近年來一個突出變化是，口令攻擊算法逐漸擺脫了依靠“奇思妙想”啟發(fā)式方法，進入了依賴可靠的概率模型科學(xué)化算法的新階段，如基于概率上下文無關(guān)方法(probabilistic context-free grammars, PCFG)[30]，基于馬爾可夫鏈(Markov-Chain)的方法[23]，基于自然語言處理技術(shù)(natural language processing, NLP)的方法[31].與此同時，管理員也可以：1)設(shè)計更準確的口令強度評測器(password strength meter, PSM)[28,32-33]，以便用戶注冊、更新口令時對用戶提交的口令的強度進行及時反饋；2)設(shè)計更安全可用的口令生成策略，比如研究發(fā)現(xiàn)策略“口令長度12位以上，包含2類字符”要比策略“必須8位以上，包括字母、數(shù)字和特殊字符”更可用、更安全[34].

口令安全研究根據(jù)其研究方法大致可分為3個階段.第1階段為1999年以前，主要采用啟發(fā)式方式，沒有理論體系，口令安全研究更多是一門藝術(shù)，歐美少數(shù)幾個研究機構(gòu)零星地發(fā)表一些成果(如文獻[35-37])；第2階段為2000年到2008年，口令理論體系初現(xiàn)端倪，但主基調(diào)與微軟的“口令替代計劃”類似，這一階段研究大多集中于揭示口令的弱點，表明口令在身份認證領(lǐng)域?qū)o法擔(dān)當(dāng)主要角色(如文獻[8,38-39]);第3階段為2009年以來，口令安全理論體系逐漸完善，形成了以Markov[23]、PCFG[30]為代表的概率攻擊理論模型，以Zipf原理為基礎(chǔ)的口令分布理論模型[25]，以α-guesswork為代表的口令分布強度評價理論模型[40]，使口令安全研究擺脫了傳統(tǒng)的依賴簡單統(tǒng)計方法和啟發(fā)式“奇思妙想”，進入了以嚴密理論體系為支撐的科學(xué)軌道.值得一提的是，口令的Zipf分布[25]由我國學(xué)者發(fā)現(xiàn).

綜上，本文主要從用戶脆弱口令行為、口令攻擊算法、口令分布強度評價指標和口令強度評價方法4個方面，對國內(nèi)外最新研究進展進行綜述.

1 用戶的脆弱口令行為

用戶的不安全口令行為是造成口令無法達到理想強度的直接原因[41]，因此理解用戶的脆弱口令行為成為研究口令安全性的基礎(chǔ)前提.一方面用戶往往需要管理幾十上百個口令帳戶[24]，并且這一數(shù)字在不斷增長，此外各個網(wǎng)站的口令設(shè)置要求往往差異很大[22,42]；另一方面，用戶用于處理信息安全事務(wù)的精力十分有限且保持穩(wěn)定[43]，并不會隨著時間的推移而有較大幅度提高.這一根本矛盾導(dǎo)致了用戶的一系列脆弱行為.近期研究表明，現(xiàn)實中用戶的口令行為往往是理智的[44]，并且只有這樣，普通用戶才能可持續(xù)地管理不斷增多的口令帳戶[45].

當(dāng)前，廣泛采用的口令脆弱行為挖掘方法既有實證分析(如文獻[23-26])，也有用戶調(diào)查(如文獻[27-28])；實證分析的數(shù)據(jù)既有來自于黑客泄露(如文獻[23-25,46])，也有來自于企業(yè)合作(如文獻[40,47])；用戶調(diào)查既有小規(guī)模的傳統(tǒng)調(diào)查(如文獻[27-28])，也有基于外包服務(wù)的新型大規(guī)模網(wǎng)絡(luò)調(diào)查(如文獻[34]).為更好顯示實證分析結(jié)果，本文使用了8個知名真實口令集，如表1所示.總的來說，已發(fā)現(xiàn)用戶的脆弱口令行為主要可以歸為以下3類.

Table 1 Basic Information about the Password Datasets Used

Notes:*The 12306 dataset includes five types of personal information: name, birthday, email, phone number and national identity card number.

**The Rootkit dataset includes four types of personal information: name, birthday, user name and email.

1.1 口令構(gòu)造的偏好性選擇

1.1.1 國民口令

1979年，Morris和Thompson在他們的開創(chuàng)性論文里分析了3 289個真實用戶口令，發(fā)現(xiàn)86%落入普通字典，33%可以在5 min內(nèi)搜索出來.后續(xù)大量研究(如文獻[23-28])表明，除了選擇單詞作口令，用戶常常將單詞進行簡單變換，以滿足網(wǎng)站口令設(shè)置策略的要求.

比如“123456a”可以滿足“字母+數(shù)字”的策略要求.這些最流行的單詞及其變換就形成了國民口令，如表2所示.中文國民口令多為純數(shù)字，而英文國民口令多含字母，這體現(xiàn)了語言對口令行為的影響.有趣的是，愛情這一主題在國民口令中占據(jù)了重要地位.高達1.01%～10.44%的用戶選擇最流行的10個口令，這意味著攻擊者A只要嘗試10個最流行的口令，其成功率就會達到1.01%～10.44%.同時，這也預(yù)示著人類生成的口令遠不是均勻分布，那到底是什么分布呢？

Table 2 Top-10 Most Popular Passwords of Each Service

1.1.2 Zipf分布

在2012年以前，學(xué)術(shù)界普遍假設(shè)口令滿足均勻分布(如文獻[48-49])，這有2方面的原因：1)缺少大規(guī)模真實口令數(shù)據(jù)，口令具體是什么分布難以實證；2)在均勻分布的假設(shè)下，分析問題最為方便簡單.自2009年第1個千萬級口令集Rockyou泄露以來，如表1所示，數(shù)以百計的知名網(wǎng)站被攻陷[50]，這為研究口令分布提供了充足原始數(shù)據(jù).關(guān)于口令Zipf分布的發(fā)現(xiàn)經(jīng)歷了一個“否定—肯定”的曲折過程.因為人類自然語言滿足Zipf分布[51]，很自然的一個想法是，人類生成的口令也可能滿足Zipf分布.2012年，Malone和Maher[52]分析了3 200萬條Rockyou數(shù)據(jù)和另外3個小于10萬條的數(shù)據(jù)集，將整個口令集輸入Zipf模型，發(fā)現(xiàn)擬合出來的參數(shù)通不過Kolmogorov-Smirnov(KS)檢驗.因此，他們得到結(jié)論：口令不服從Zipf分布.同年，Bonneau[40]使用類似方法分析了7 000萬條Yahoo口令，也否定了口令服從Zipf分布的可能性.

2014年，Wang等人[25]根據(jù)大數(shù)定律，指出那些低頻次口令天然無法反映其真實頻率，因此只有將那些高頻次口令(如出現(xiàn)頻次不小于4的口令)輸入Zipf模型才有意義.基于這一新方法，Wang等發(fā)現(xiàn)在10萬抽樣樣本下，通過Zipf模型擬合的參數(shù)可通過KS檢驗.這意味著，Zipf模型能夠很好地刻畫口令分布(雙對數(shù)坐標下為直線，如圖1所示)：

其中，r表示排名，fr表示排名為r的口令的頻率，C和s為常數(shù)，由具體的分布(即數(shù)據(jù)集)決定.

當(dāng)前,這一發(fā)現(xiàn)已被廣泛應(yīng)用于多個場合，如精確刻畫可證明安全協(xié)議中攻擊者優(yōu)勢[53-54]、評估基因保護系統(tǒng)的抗攻擊能力[55]、評估口令Hash函數(shù)的強健性[56].同時，這一規(guī)律表明，口令頻次呈多項式下降，高頻的口令和低頻的口令都會占據(jù)整個口令集的重要部分.這也從根本上說明了為什么漫步猜測攻擊(見2.1節(jié))會如此有效.

Fig. 1 Human-chosen passwords follow Zipf’s law.圖1 人類生成的口令服從Zipf分布

1.1.3 字符組成結(jié)構(gòu)

當(dāng)網(wǎng)站設(shè)置了口令生成策略時，口令的字符組成很大程度上由口令策略所決定.當(dāng)網(wǎng)站未設(shè)置口令構(gòu)成策略時，用戶口令的結(jié)構(gòu)直接體現(xiàn)了用戶的偏好[22-24].

表3中最突出的現(xiàn)象是，絕大多數(shù)中文口令包含數(shù)字，并且27%～45%僅由數(shù)字構(gòu)成；英文口令喜歡包含字母，低于16%的口令僅由數(shù)字構(gòu)成，有相當(dāng)一部分由一串小寫字母后面跟1組成.由于高達99.57%的000webhost口令由字母和數(shù)字共同構(gòu)成，這意味著該網(wǎng)站在運行不久后就執(zhí)行了“字母+數(shù)字”的口令策略.在這種情況下，用戶也顯示了偏好：54.42%的000webhost口令符合“一串小寫字母+一串?dāng)?shù)字”的結(jié)構(gòu).用戶的這些偏好正是攻擊者A所努力挖掘的對象.

1.1.4 口令長度

用戶口令長度也直接受網(wǎng)站策略影響.當(dāng)網(wǎng)站未設(shè)置長度限制時，口令的長度分布由受網(wǎng)站服務(wù)類型(重要程度)的影響.比如，000webhost提供建站服務(wù)，口令具有管理員權(quán)限，該網(wǎng)站34.7%的口令長度不低于11，這一比例是其他任意網(wǎng)站的2倍以上.表4顯示，對于普通網(wǎng)站來說，90%以上口令的長度介于6-11之間，這一信息對攻擊者A減少猜測空間具有重要作用.

Table 3 Composition Structures of Passwords Chosen by Chinese and English Users

Note: The first line of the table are presented in regular expressions.For instance, ^[a-z]+$ stands for the passwords that are only composed of lower-case letters, [a-z] stands for the passwords that include lower-case letters, and ^[a-z]+[0-9]+$ stands for the passwords that are beginning with lower-case letters and ending up with digits.

Table 4 Length Distribution of Passwords Chosen by Chinese and English Users

1.2 口令重用

一直以來，用戶的口令重用行為被認為是不安全的，所以用戶應(yīng)當(dāng)避免重用[57-59].但是，近期研究發(fā)現(xiàn)，面對如此多的需要管理的帳號，重用口令是用戶理智的做法[44,60]，關(guān)鍵在于如何重用[45].只有跨不同安全級(或重要程度)帳戶重用口令，才是應(yīng)努力避免的[61].表5中總結(jié)了用戶口令直接重用和間接(修改后)重用的一些數(shù)據(jù).

2014年，Das 等人[27]進一步研究了口令間接重用時新口令和原口令間的相似度，并使用了一系列文本相似度算法(如最大共同長度LCS、文氏距離Levenshtien、曼哈頓距離Manhattan、重合度Overlap)進行測量.結(jié)果表明，只有約30%的用戶重用口令時簡單修改(即新舊口令相似度在[0.8,1])，絕大多數(shù)用戶的新舊口令相似度小于0.8，表明修改幅度較大.圖2基于4種相似度算法，對12306與CSDN間接口令重用相似度進行了測量，結(jié)果與Das等人[27]的發(fā)現(xiàn)基本一致.

Table 5 Statistics About Password Reuse

Fig. 2 Similarity scores of PW reuse between 12306 and CSDN.圖2 12306與CSDN間接口令重用相似度

為更好理解不同網(wǎng)站間用戶口令間接重用的程度，圖3基于Levenshtien相似度算法，對表1中口令集進行了測量.結(jié)果表明，中文用戶口令重用的問題要更嚴重：約有40%以上間接重用的中文口令相似度在[0.7,1],而英文口令僅有20%.

Fig. 3 Levenshtien similarity scores of indirect password reuse.圖3 不同網(wǎng)站口令間接重用的文氏相似度

1.3 基于個人信息構(gòu)造口令

早在1979年，Morris和Thompson[35]就發(fā)現(xiàn)用戶構(gòu)造口令時喜歡使用姓名等個人信息，在猜測字典中加入姓名庫可以顯著提高口令猜測成功率.除了姓名、生日、用戶名、Email前綴、身份證號、電話號碼[24,26,35]，甚至地名這些個人相關(guān)信息都可能被用戶使用[62].表6給出了6類常用個人信息在中英文口令中的含有率.其中，生日的含有率最高，其次為用戶名、姓名、Email前綴，也有少量用戶使用身份證號和手機號作口令.Wang等人[24]發(fā)現(xiàn)，在4.36%含有長為11位數(shù)字串的中文用戶口令中，66.74%包含手機號.

Table 6 Personal Information Usages in 12306

表7給出了4種不同類型姓名在口令中的構(gòu)成比例.其中“Abbr.full name”表示“名的縮寫+姓氏”，如“wang ping”的縮寫為“pwang”.可以看出，相當(dāng)比例的用戶使用姓氏或“名的縮寫+姓氏”作為口令的構(gòu)成部分.需要注意的是，英文網(wǎng)站Rootkit用戶使用個人信息相較中文網(wǎng)站12306較少，但這并不能得到“中文用戶更傾向于在口令中使用個人信息”的結(jié)論，這是因為Rootkit網(wǎng)站是黑客論壇，其中的用戶具有比普通用戶更高的安全意識和更豐富的安全技術(shù)知識.總的來說，正如第2節(jié)中所證實的，用戶使用個人信息構(gòu)造口令的習(xí)慣嚴重降低了口令強度，定向攻擊者可依此大大增強其效率.

Table 7 Various Name Usages in Passwords

2 口令猜測攻擊

一般來說，口令的安全性可分為2類[23-24]：1)整個口令集的安全性(即口令分布的安全性)；2)單個口令的安全性.第1類安全性的評價既可以采用攻擊算法進行實際攻擊，也可以采用基于統(tǒng)計學(xué)的評價指標；第2類安全性的評價只能采用攻擊算法進行實際攻擊，然后根據(jù)攻擊結(jié)果來衡量，當(dāng)前廣泛采用的衡量指標是成功攻擊該口令所需要的猜測次數(shù)[63-64].本節(jié)關(guān)注攻擊算法，基于統(tǒng)計學(xué)的評價指標見第3節(jié).如表8所示，根據(jù)攻擊過程中是否利用用戶個人信息，口令猜測算法可分為漫步攻擊和定向攻擊；依據(jù)攻擊是否需要與服務(wù)器交互,可分為在線攻擊和離線攻擊.基于PCFG的算法[30]和Markov算法[23]是當(dāng)前主流的2個漫步攻擊算法，也是其他算法的基礎(chǔ)，因此本節(jié)詳細介紹這2個算法，其他算法簡要概述.

Table 8 A Taxonomy of Password (PW) Guessing Attacks

2.1 漫步攻擊算法

所謂漫步攻擊(trawling attacking)是指攻擊者A不關(guān)心具體的攻擊對象是誰，其唯一目標是在允許的猜測次數(shù)下，猜測出越多的口令越好.這意味著，最優(yōu)的攻擊者會首先猜測排名r=1的口令，接著猜測排名r=2的口令，依次類推.

Fig. 4 Effectiveness of various heuristic guessing algorithms[40].圖4 基于啟發(fā)式方法的攻擊效果[40]

2.1.1 啟發(fā)式算法

早期的口令猜測算法基本都是漫步攻擊算法，且沒有嚴密的理論體系，很大程度上依靠零散的“奇思妙想”.比如，構(gòu)造獨特的猜測字典[35,37]，采用“精心設(shè)計”的猜測順序[65]，基于開源軟件(如John the Ripper)[65-66].如Bonneau[40]所指出的，這些啟發(fā)式算法難以重現(xiàn)，難以相互公平對比.因此，這里我們僅概述它們的攻擊效果.如圖4所示，絕大多數(shù)(如文獻[35,65])啟發(fā)式算法的攻破率在30%以下，猜測字典大小為212～220.雖然少數(shù)算法(如文獻[35,68])能夠達到60%以上，但其測試集都較小，都小于10萬，并且往往僅在一個測試集上進行評估.

2.1.2 PCFG

2009年，Weir等人[30]提出了第1個完全自動化的、建立在嚴密的概率上下文無關(guān)文法(PCFG)基礎(chǔ)之上的漫步口令猜測算法.該算法的核心假設(shè)是口令的字母段L、數(shù)字段D和特殊字符段S是相互獨立的.它首先將口令根據(jù)前述3種字符類型進行切分，比如“wang123!”被切分為L4:wang，D3:123和S1:!，L4D3S1被稱為該口令的結(jié)構(gòu)(模式).該算法主要分為訓(xùn)練和猜測集生成2個階段.

Fig. 5 Illustration of the training phase of PCFG[30].圖5 PCFG算法[30]的訓(xùn)練過程

在訓(xùn)練階段，最關(guān)鍵的是統(tǒng)計出口令模式頻率表Σ1和字符組件(語義)頻率表Σ2.基于CFG方法，對泄漏口令進行統(tǒng)計，得到各種模式的頻率和模式中數(shù)字組件、特殊字符組件的頻率，獲得Σ1和表Σ2.比如針對L4D3S1，統(tǒng)計在全部口令中以L4D3S1為模式的口令頻率，以及“wang”在長為4的字母段的頻率，“123”在長為3的數(shù)字串中的頻率和“!”在長為1的特殊字符串中的頻率.整個過程如圖5所示：

在猜測集生成階段，依據(jù)上面獲得的模式頻率表Σ1和語義頻率表Σ2，生成一個帶頻率猜測的集合，以模擬現(xiàn)實中口令的概率分布.比如，猜測“wang123!”的概率計算為P(wang123!)=P(S→L4D3S1)×P(L4→wang)×P(D3→123)×P(S1→!)=0.15×0.3×0.6×0.3=0.008 1.這表明，“wang123!”的可猜測度為0.008 1.整個過程如圖6所示：

Fig. 6 Illustration of the guess generation phase of PCFG[30].圖6 PCFG算法[30]的猜測集生成過程

這樣，就能獲得每個字符串(猜測)的概率，按照概率遞減排序即可獲得一個猜測集.

2.1.3 Markov

2005年，Narayanan和Shmatikov[38]首次將Markov鏈技術(shù)引入到口令猜測中來.該算法的核心假設(shè)是：用戶構(gòu)造口令從前向后依次進行.它不像PCFG那樣對口令進行分割，而是對整個口令進行訓(xùn)練，通過從左到右的字符之間的聯(lián)系來計算口令的概率.類似PCFG模型，Markov模型也分為訓(xùn)練和猜測集生成2個階段.

在訓(xùn)練階段，統(tǒng)計口令中每個子串后面跟的一個字符的頻數(shù).Markov模型有階的概念，n階Markov模型就需要記錄長度為n的字符串后面跟的一個字母頻數(shù).例如，在4階Markov中，口令abc123需要記錄的有：開頭是a的頻數(shù)，a后面是b的頻數(shù)，ab后面是c的頻數(shù)，abc后面是1的頻數(shù)，abc1后面是2的頻數(shù)，bc12后面是3的頻數(shù).這樣，每個字符串在訓(xùn)練之后都能得到一個概率，即從左到右，將長度為n的子串在訓(xùn)練結(jié)果中進行查詢，將所有的概率相乘得到該字符串的概率.在4階Markov模型下，口令abc123的概率計算如下：

P(abc123)=P(a)×P(b|a)×P(c|ab)×

P(1|abc)×P(2|abc1)×P(3|bc12),

在2014年，Ma等人[23]首次將平滑技術(shù)和正規(guī)化技術(shù)運用到Markov模型中.平滑技術(shù)是為了消除數(shù)據(jù)集中過擬合(overfitting)問題，主要有Laplace平滑和Simple Good-Turing平滑2種；正規(guī)化技術(shù)是為了使得攻擊算法所生成的猜測的概率總和始終為1，形成一個概率模型，主要有End-Symbol正規(guī)化和長度分布正規(guī)化2種.下面以Laplace平滑技術(shù)和End-Symbol正規(guī)化技術(shù)為例說明.

Laplace平滑是在訓(xùn)練完畢之后，對于每個字符串的頻數(shù)都加0.01，再去計算字符串的概率.例如，對于字符串a(chǎn)bc123，其中的概率計算如下：

P(3|bc12)=

其中字符總數(shù)一般是在95個可打印ASCII字符0x20～0x7E中增加一個結(jié)尾符號，共96個字符.

End-Symbol正規(guī)化在每個口令的最后加了一個結(jié)尾符號(假設(shè)記為⊥)，把⊥當(dāng)作一個字符，訓(xùn)練時將⊥一起加入頻數(shù)統(tǒng)計，除了口令開頭不能出現(xiàn)⊥以外，在口令其他地方都當(dāng)作正常字符.生成猜測集時，只有以⊥結(jié)尾的符串才能夠作為猜測，其他字符串都不能作為猜測輸出.

2.1.4 NLP

2014年，Veras等人[69]指出口令中包含大量深層次語義信息，比如一個口令以“ilove…”起始，它后面接男女姓名的可能性遠大于“123”或“asd”.但是，當(dāng)前的PCFG算法和和Markov算法都沒有利用這些深層次語義信息.于是，Veras等人在PCFG算法將口令進行L,D，S分段的框架內(nèi)，進一步對L段進行語義挖掘，提出了融合語義的NLP算法.該算法2個核心點：1)分詞(segmentation)，因為口令的詞段間沒有明確的分割符；2)詞性標注(part-of-speech tagging或POS tagging)，即對詞語標注一個合適的詞性，也就是確定這個詞是名詞、動詞、形容詞或其他詞性.為了有效分詞和詞性標注，Veras等人收集整理了一個英語語料庫集合，主體為當(dāng)代美國英語語料庫(COCA)，另加英文人名、城市地點名等語料庫.基于這些該語料庫，他們使用自然語言處理的方法對口令進行切詞、詞性標注，并在此基礎(chǔ)上對英文用戶口令所具有的語義含義進行分析、抽象和實例化.NLP算法的猜測集生成階段與PCFG算法相同.

根據(jù)圖7和文獻[23-24]的結(jié)果，PCFG算法在小猜測次數(shù)下(即在線猜測攻擊)最優(yōu)，Markov算法在大猜測次數(shù)下(即離線猜測攻擊)開始顯示優(yōu)勢，NLP攻擊效果介于PCFG和Markov之間.NLP算法為口令猜測提供了一個新的思路，尚有繼續(xù)改進的空間.比如利用隱語義模型(latent Dirichlet allocation, LDA)[70]來更好地控制語義標注和抽象化的粒度.

Fig. 7 Comparison of trawling guessing algorithms.圖7 漫步猜測攻擊算法對比

2.2 定向攻擊算法

定向口令猜測攻擊的目標是盡可能以最快速度猜測出所給定用戶在給定服務(wù)(如網(wǎng)站、個人電腦)的口令[22,29].因此，攻擊者會利用與攻擊對象相關(guān)的個人信息(personal information, PI)，以增強猜測的針對性.用戶的個人信息有很多種，比如人口學(xué)相關(guān)信息(姓名、生日、年齡、職業(yè)、學(xué)歷、性別等)，用戶在該網(wǎng)站的過期口令(舊口令)，用戶在其他網(wǎng)站(泄露)的口令.當(dāng)前定向口令猜測研究尚在起步階段，主要集中在如何利用人口學(xué)相關(guān)信息方面.

2.2.1 Targeted-Markov

2016年，Wang等人[71]首次提出了基于Markov鏈的定向攻擊猜測算法.該算法基于漫步Markov攻擊模型[23]，其基本思想是：人群中有多少比例使用某種PI，那么攻擊對象也將有同樣可能性(比例)使用該PI.為實現(xiàn)這一思想，文獻[71]首先將PI分為6大類(即用戶名A、郵箱前綴E、姓名N、生日B、手機號P和身份證G)，并且對每一大類根據(jù)需要的粒度進一步細分.比如，N可分為N1(姓名全稱)，N2(姓氏)，N3(名),…,N7(首字母大寫的姓氏)共7小類.接著，假設(shè)集合{N1，N2，N3…，N7；B1，B2，…;…；G1，G2…}中共有k個元素，將每一個元素視為與95個ASCII可打印字符同等地位的基本字符，這樣Markov模型中將有95+k個基本字符.然后，將訓(xùn)練集每個口令中所有的PI信息替換成對應(yīng)的PI類型基本字符，訓(xùn)練階段的剩余步驟與漫步Markov模型[23]相同.

猜測集生成階段分2步:1)運行漫步Markov模型[23]的猜測集生成過程，產(chǎn)生中間猜測集，該猜測集既包含“123456”這樣的可以直接使用的猜測，也會包含帶PI類型基本字符的“中間猜測”(如N1，N2123)；2)將“中間猜測”里的PI基本字符替換為攻擊對象的相應(yīng)PI信息，如將N2123替換為wang123(假設(shè)攻擊對象姓名為“wang ping”)①文獻[29]只考慮長度大于等于3的PI信息..

2.2.2 Personal-PCFG

2016年，Li等人[29]首次提出了基于概率上下文無關(guān)文法(PCFG)的定向攻擊猜測算法，稱為Personal-PCFG.該算法基于漫步PCFG攻擊模型[30]，基本思想與PCFG攻擊模型完全相同：將口令按字符類型按長度進行切分.為實現(xiàn)這一思想，文獻[29]首先將PI分為6大類(即用戶名A、郵箱前綴E、姓名N、生日B、手機號P和身份證G)，并將這6種PI字符類型視為與漫步PCFG模型里的L,D,S同等地位，這樣Personal-PCFG中有9種類型字符；接著，在訓(xùn)練過程中，將訓(xùn)練集中每個口令如同漫步PCFG攻擊模型[30]那樣，按相應(yīng)字符類型及其長度進行分段，比如“wang123!”被切分為N4D3S1分段，因為“wang”屬于姓名N這一大類，長度為4.剩余訓(xùn)練過程與漫步PCFG模型[30]類似.

猜測集生成階段分2步：1)運行漫步PCFG模型[30]的猜測集生成過程，產(chǎn)生中間猜測集，該猜測集既包含“123456”這樣的可以直接使用的猜測，也會包含帶PI類型字符的“中間猜測”(如N1，N2123)；2)將“中間猜測”里的PI類型字符替換為攻擊對象的相應(yīng)長度的PI信息，如將N4123替換為wang123(假設(shè)攻擊對象姓名為“wang ping”)①.

Fig. 8 Comparison of targeted guessing algorithms.圖8 定向猜測攻擊算法對比

圖8對Targeted-Markov[71]和Personal-PCFG[29]這2個定向口令猜測攻擊算法進行了對比.同時，為了更好顯示定向攻擊算法在在線猜測方面的優(yōu)勢，我們將定向攻擊算法與漫步攻擊算法(Markov[23]、PCFG[30]和Trawling-optimal[40])也進行了對比.結(jié)果顯示，在猜測數(shù)為10～1 000時，Targeted-Markov[71]的攻擊效率比Personal-PCFG[29]高出37.18%～73.29%,比理想漫步算法(Trawling-optimal[40])高出412%～740%.

需要指出的是，除了用戶的人口學(xué)相關(guān)信息(姓名、生日等)，用戶在其他網(wǎng)站的泄露的口令也可以被攻擊者利用來進行定向攻擊.可以預(yù)見，這種利用用戶口令重用脆弱行為的定向攻擊，其危害可能要比基于人口學(xué)相關(guān)信息的攻擊更為嚴重.但除了文獻[27]給出的一個簡單的啟發(fā)式的攻擊方法外，當(dāng)前尚未見基于嚴格理論模型的公開成果.

3 口令分布安全性評價指標

2012年，Bonneau[40]指出，采用攻擊算法來評估口令分布的安全性可能帶來不確定性，因為攻擊算法的效率嚴重依賴于攻擊模型以及模型參數(shù)(如訓(xùn)練集、平滑方法、歸一化方法)的選擇.相比之下，基于統(tǒng)計學(xué)的評價指標則避免了這一難題.當(dāng)前，廣泛采用的統(tǒng)計學(xué)指標主要有6類，下面分別介紹，最后利用它們來測量本文所使用的真實口令集.

不失一般性，設(shè)分布為X ,樣本空間大小為N，事件概率從大到小依次為p1,p2,…,pN，滿足p1≥p2≥…≥pN.

3.1 信息熵

Shannon信息熵(Shannon entropy)[72]被廣泛用來測量一個分布的不確定性：

3.2 最小熵

最小熵(min entropy)[72]被用來測量一個分布中概率最大事件出現(xiàn)的不確定性：

H∞(X)=-logp1.

3.3 猜測熵

猜測熵(guessing entropy)[73]被用來測量當(dāng)一個漫步攻擊者按最優(yōu)方式攻擊時，猜測出X中任一元素需要的平均猜測次數(shù)：

3.4β-success-rate

β-success-rate[74]被用來測量當(dāng)一個漫步攻擊者被限制至多猜測β次時，其平均成功率：

3.5α-work-factor

α-work-factor[74]被用來測量當(dāng)一個漫步攻擊者想要達到至少α的成功率時，它需要對每個帳戶至少發(fā)起的猜測次數(shù)為：

3.6α-guesswork

2012年，Bonneau[40]指出，雖然對每個帳戶發(fā)起μα(X)次猜測確實能夠保證α的成功率，但對于有些帳戶，攻擊者并不需要μα(X)次猜測就能攻破.α-work-factor指標不能刻畫這一情形，這是α-work-factor的一個固有缺陷.于是，Bonneau指出了α-guesswork[40]這一指標.它用來測量當(dāng)一個漫步攻擊者想要達到α的成功率時，它需要對每個帳戶平均發(fā)起的猜測次數(shù)：

其等價的比特表現(xiàn)形式為

3.7 指標的應(yīng)用示例

上述6個指標中，信息熵和最小熵天然以bit為單位，而其他指標有的是百分比，有的是猜測次數(shù).Bonneau[40]巧妙地使用“有效密鑰長度”的思想，將它們都等價轉(zhuǎn)換為以bit單位，以便進行對比.如表9所示，最小熵、β-success-rate[74]和小成功率的α-guesswork適于用來衡量一個口令分布抵抗在線猜測攻擊的能力，而信息熵和大成功率的α-guesswork適于用來衡量一個口令分布抵抗離線猜測攻擊的能力.

表9所示為在8個口令分布中，CSDN抵抗在線猜測攻擊能力最差，000webhost最優(yōu)；Rookit抵抗離線猜測攻擊能力最差，Dodonew最優(yōu).如第2節(jié)所言，在這個8個網(wǎng)站中，000webhost提供的是建站服務(wù)，其上口令具有管理員權(quán)限，并且執(zhí)行了最嚴格的口令生成策略(即“字母+數(shù)字”)，因此不難理解000webhost抵抗在線猜測攻擊能力最優(yōu).出乎意料的是，CSDN執(zhí)行了最長的口令長度要求(即“口令長度不小于8”)，但其抵抗在線猜測攻擊能力最差，這可能因其僅是一個技術(shù)交流論壇.這再一次證實：網(wǎng)站服務(wù)類型是影響口令強度的第一因素[24]，其次為口令生成策略[28].

值得注意的是，本文的6個指標，都只能用來衡量口令分布在漫步攻擊者模型下的安全強度，無法衡量口令分布在定向猜測模型下的安全強度.如何設(shè)計在定向猜測模型下的、多維度的口令分布安全指標，是值得研究的一個課題.

Table 9 Evaluation Results of Various Statistical Strength Metrics for Each Password Distribution

4 口令強度評測

造成當(dāng)前弱口令頻繁出現(xiàn)的一個直接原因在于普通用戶口令安全意識不足，甚至是不正確的[75]，不知道如何正確構(gòu)造(設(shè)置)與給定網(wǎng)絡(luò)服務(wù)重要程度相匹配的口令.造成用戶安全意識缺陷的原因有2個：1)口令是私密數(shù)據(jù)，普通用戶往往不知道其他用戶的口令是什么樣，當(dāng)選擇大眾化的口令或口令構(gòu)造模式時卻并不知情，甚至自認為是“獨特的”，“巧妙的”[76]；2)絕大多數(shù)主流網(wǎng)站的口令強度評測器(password strength meter, PSM)設(shè)計是啟發(fā)式的，沒有投入足夠的努力(“bear no indication of any serious efforts”[77])，向用戶反饋的口令強度結(jié)果不準確，且常常與其他網(wǎng)站相互沖突，不可避免造成用戶的困惑、挫敗感和誤解[22].這2條原因都突出了在用戶生成口令時，網(wǎng)站向用戶提供及時、準確、一致的口令強度反饋結(jié)果的必要性.并且，近期研究表明，表現(xiàn)形式醒目、反饋結(jié)果準確的PSM確實能夠顯著提高口令的安全性[78-79].

鑒于此，近年來學(xué)術(shù)界、工業(yè)界和標準組織在PSM設(shè)計方面投入了大量的努力，提出了一系列PSM.根據(jù)文獻[2,80],標準組織界影響力最大的PSM當(dāng)屬NIST entropy[81];文獻[77]調(diào)研了當(dāng)前工業(yè)界22個主流PSM，表現(xiàn)最突出的為Zxcvbn[82]和KeePSM[83];學(xué)術(shù)界最先進的3個算法為fuzzyPSM[28]、PCFG-based PSM[32]和Markov-based PSM[33].根據(jù)底層設(shè)計思想的不同，可以將上述這些PSM分為3類：基于規(guī)則(如文獻[80])、基于模式檢測(如文獻[82-83])和基于攻擊算法(如文獻[28,32-33]).

4.1 基于規(guī)則的口令強度評價方法

影響最大的基于規(guī)則的方法當(dāng)屬NIST PSM[80].當(dāng)前在主流網(wǎng)站上應(yīng)用的口令強度評價方法絕大多數(shù)為基于規(guī)則的方法，沿用了NIST PSM的思想：口令強度依據(jù)長度和所包含的字符類型而定.典型的代表就是騰訊網(wǎng)站[84]：1)當(dāng)口令長度len<6或len≤8且僅由數(shù)字組成時，只進行警告，不輸出強度值；2)當(dāng)口令長度len≥6，且僅由一種字符組成時，評價為“弱”；3)當(dāng)口令長度len≥8，包含2類字符為“中”，包含3類或4類字符為“強”.

這類方法的最大優(yōu)點是簡單，比如騰訊涉及PSM的代碼只有12行；缺陷也是非常明顯的：評價結(jié)果不準確，容易誤判——低估強口令和高估弱口令都會發(fā)生.

4.2 基于模式檢測的口令強度評價方法

此類方法(如文獻[82,84])主要目標是檢測口令的各個子段(sub-parts of a password)所屬的構(gòu)造模式(如鍵盤模式、順序字符模式、首字母大寫等等).接著，對發(fā)現(xiàn)的各個模式賦予相應(yīng)的分數(shù)(score).然后，將口令的所有模式的分數(shù)加和，得到該口令的總得分，即為口令強度值.比如，Zxcvbn[82]主要考慮了3類模式：1)鍵盤模式，如qwert,asd,zxcvbn;2)常見語義模式,如日期、姓名；3)順序字符模式,如123456,gfedcba.這些模式被視為弱口令的標志，會給一個較低的分數(shù).此外,Zxcvbn[82]還考慮了字典模式：將口令的子段與構(gòu)造的一系列字典(如top 10000口令,1 003個男性姓名，3 814個女性姓名)進行匹配，根據(jù)查找比對的次數(shù)進行相應(yīng)賦值.如果口令的一個子段不屬于上述4類模式，則被視為隨機字符段，該子段被賦予一個較高的分數(shù).

這類方法比基于規(guī)則的方法更科學(xué)，但仍屬于啟發(fā)式方法，沒有自適應(yīng)性；一些弱模式(比如字符跳變Leet:password→p@ssword)如果沒有被考慮到，就會漏檢，造成弱口令被高估為強口令.

4.3 基于攻擊算法的口令強度評價方法

安全永遠是相對的.相對于某種攻擊者模型而言，一個口令可能是安全的；相對于另外一種攻擊者模型而言，可能是非常脆弱的.比如，“Wangping.123”可以很好抵抗漫步在線猜測攻擊(如Markov[23],PCFG[30])，但相對定向在線猜測攻擊(如Targeted Markov[71],Personal-PCFG[29])而言，卻明顯是弱口令.

因此，評價口令強弱的一個自然途徑就是，使用攻擊算法對給定口令進行攻擊，依據(jù)攻擊的難易程度進行強弱判定.基于這一思想，近期提出了幾個基于漫步攻擊算法的PSM.一個廣泛被接受的直觀感覺是，攻擊算法越高效，基于其上的PSM將更準確(見文獻[32]).文獻[28]指出事實并非如此：雖然Markov算法[23]攻擊效率要比PCFG算法[30]好，但大規(guī)模真實口令集對比實驗顯示，PCFG-based PSM[32]卻比Markov-based PSM[33]更準確.一個可能的原因是，Markov算法[23]使用了平滑技術(shù)(如Laplace和Good-Turning)，導(dǎo)致其可以破解出更多口令，但同時也帶來了數(shù)據(jù)稀疏性問題.

2016年，Wang等人[28]通過用戶調(diào)查證實，用戶在向一個新網(wǎng)站注冊口令時，往往是重用(44.8%)一個現(xiàn)有的口令，或者修改(32.6%)一個現(xiàn)有口令，而僅有14.5%的用戶從無到有構(gòu)造一個全新的口令.基于這一發(fā)現(xiàn)，他們設(shè)計了一個基于模糊概率上下文無關(guān)文法的口令強度評價算法.該算法使用一個弱口令集A(如來自社交網(wǎng)站)作為基礎(chǔ)口令集，使用另外一個強口令集B(如來自電子商務(wù)網(wǎng)站)作為修改口令集，然后學(xué)習(xí)(Learn)用戶從口令集A取口令然后修改為口令集B中相似口令的方法和相應(yīng)頻率，得到一個概率模型fuzzy PCFG.在口令評價階段，基于fuzzy PCFG對給定口令計算一個概率值，該概率值作為此口令的強度.

Fig. 9 Comparison of six leading password strength meters.圖9 當(dāng)前6種主流口令強度評價算法對比

圖9采用Spearman系數(shù)對上述6個主流PSM進行了對比.對于一個給定的測試口令集，PSM會對其中每個口令輸出一個強度值(概率值)；如果將這些口令將其強度值排序，會產(chǎn)生一個口令強度序列.Spearman系數(shù)用以衡量一個PSM輸出的強度序列與理想PSM輸出的強度序列間的相關(guān)關(guān)系：2個序列完全相同則Spearman系數(shù)為1，倒序則Spearman系數(shù)為-1，Spearman系數(shù)越大表明2個序列越接近.因此，Spearman系數(shù)越大表明其越接近理想PSM.圖9顯示，在識別弱口令方面，fuzzyPSM>PCFG-based PSM>Markov-based PSM>Zxcvbn>KeePSM>NIST PSM；在識別強口令方面，PCFG-based PSM>Markov-based PSM>fuzzyPSM>Zxcvbn>KeePSM>NIST PSM.由于PSM最核心功能是防止用戶選擇弱口令：準確向用戶反饋口令的強度，當(dāng)發(fā)現(xiàn)用戶選擇了弱口令時，進行重點提示或阻止.因此，總體來說，fuzzyPSM表現(xiàn)最優(yōu)，學(xué)術(shù)界的PSM要優(yōu)于工業(yè)界PSM，標準組織NIST的PSM的評價結(jié)果準確性最低.

需要指出的是，本文所討論的6個主流PSM都基于漫步猜測攻擊，未考慮用戶個人信息對口令安全性的影響.盡作者所知，當(dāng)前尚無基于定向猜測攻擊PSM的公開研究成果出現(xiàn).隨著用戶越來越多的個人相關(guān)信息開始上網(wǎng)，越來越多的網(wǎng)站被攻破、口令被泄露，設(shè)計基于定向攻擊者模型的PSM是一個具有重要現(xiàn)實意義的研究方向.

5 總結(jié)與展望

口令由于使用簡單、成本低廉、容易修改，克服了基于物理硬件的認證技術(shù)和生物特征認證技術(shù)的缺陷，學(xué)術(shù)界逐漸認識到：在可預(yù)見的未來，口令仍無可替代.因此，理解口令的安全性顯得十分必要，近年來也涌現(xiàn)出了一大批相關(guān)研究成果.本文系統(tǒng)性地總結(jié)了當(dāng)前國內(nèi)外在用戶脆弱口令行為、口令猜測算法、口令分布強度評價、口令強度評價4個領(lǐng)域的研究進展，概述了研究思路和主要研究方法，并指出了存在的不足和值得進一步研究的方向.當(dāng)前，關(guān)于口令安全的研究整體尚處于起步階段，國內(nèi)外的相關(guān)研究力量匱乏，在很多重要方向上亟待深入研究，存在大量機遇.下面探討口令安全未來的研究需求：

1)口令的Zipf分布模型帶來的啟示

當(dāng)前,幾乎所有的基于口令的安全協(xié)議(如文獻[85-87])都假設(shè)“口令滿足均勻”.但事實上，口令是嚴重偏態(tài)的Zipf分布，意味著這些安全協(xié)議不可避免低估了攻擊者的優(yōu)勢，亦即低估了協(xié)議存在的安全風(fēng)險.因此，在更符合實際的Zipf口令分布假設(shè)下，如何精確刻畫攻擊者優(yōu)勢是值得進一步探討的問題.

2)基于隱語義LDA模型的漫步猜測攻擊

基于NLP的漫步猜測攻擊算法效果不佳的一個重要原因是，NLP方法在語義標注和抽象化的粒度難以調(diào)控，而隱語義LDA模型[70]正好可以彌補這一不足.如何將LDA模型引入口令猜測，以實現(xiàn)細粒度的語義標注和抽象是一個有前景的研究方向.

3)基于泄露口令的定向猜測攻擊

一方面，用戶重用口令的趨勢越來越嚴重，另一方面被攻陷的網(wǎng)站越來越多，相當(dāng)比例的用戶口令曾被泄露.攻擊者必然會利用用戶曾經(jīng)泄露的口令來攻擊用戶當(dāng)前的口令.如何使用概率模型準確模擬這一攻擊行為？除了泄露的口令，如果再利用個人信息(如姓名、生日)，攻擊者的定向猜測攻擊成功率會有多高？各類個人信息對安全性的影響有何不同？文獻[71]首次對這些問題進行了一些探討，提出了一系列攻擊算法，期待更多相關(guān)研究.

4)基于定向攻擊模型的口令強度評測

當(dāng)前口令強度評測研究主要集中在，如何基于漫步猜測攻擊模型，設(shè)計更逼近理想漫步猜測攻擊者的PSM.隨著用戶越來越多的個人相關(guān)信息被公開，在其他網(wǎng)站使用的口令被泄露，設(shè)計基于定向攻擊者模型的PSM是一個具有重要現(xiàn)實意義的研究方向.

5)服務(wù)器端口令集泄露的檢測

當(dāng)前很多網(wǎng)站(如Myspace,Dropbox,Last.fr[88])都是口令泄露多年后才覺察到，然后通知用戶更新口令，往往為時已晚.如何在服務(wù)器端及時檢測到口令集的泄露，是一項亟待解決的課題.2013年，Juels和Revist提出了honeywords的思想，并給出了幾個啟發(fā)式生成honeywords的方法[89].作者將“如何對這些honeywords的生成方法進行實證評估”遺留為公開問題.實際上，這一問題的解決有賴于對另一更基本問題的深刻認識：攻擊者如何進行最優(yōu)攻擊.這可能涉及到復(fù)雜的統(tǒng)計學(xué)模型.

總之,口令安全是一個理論性與實踐性都很強的多學(xué)科交叉(如密碼學(xué)、統(tǒng)計學(xué)、自然語言處理、機器學(xué)習(xí))研究課題，充滿機遇與挑戰(zhàn),相信必定會吸引更多的學(xué)者的關(guān)注和研究.

[1]Axel B, Boudhayan C, Lennie D, et al. Security on the IBM Mainframe[EB/OL]. [2014-12-01]. http://ibm.co/1UMpdH7

[2]Bonneau J, Herley C, Van Oorschot P C, et al. Passwords and the evolution of imperfect authentication[J]. Communications of the ACM, 2015, 58(7): 78-87

[3]Keith M, Shao B, Steinbart P. The usability of passphrases for authentication: An empirical field study[J]. International Journal of Human-Computer Studies, 2007, 65(1): 17-28

[4]Yan J, Blackwell A, Anderson R, et al. Password memorability and security: Empirical results[J]. IEEE Security & Privacy, 2004, 2(5): 25-31

[5]Florencio D, Herley C. A large-scale study of web password Habits[C] //Proc of WWW 2007. New York: ACM, 2007: 657-666

[6]Adams A, Sasse M A. Users are not the enemy[J]. Communications of the ACM, 1999, 42(12): 40-46

[7]Munir K. Gates predicts death of the password[EB/OL]. [2004-02-25]. http://www.cnet.com/news/gates-predicts-death-of-the-password/

[8]Clair L, Johansen L, Enck W, et al. Password exhaustion: Predicting the end of password usefulness[G] //LNCS 4332: Proc of ICISS 2006. Berlin: Springer, 2006: 37-55

[9]Brumen B, Taneski V. Moore’s curse on textual passwords[C] //Proc of MIPRO 2015. Piscataway, NJ: IEEE, 2015: 1360-1365

[10]Zhang Y, Monrose F, Reiter M. The security of modern password expiration: An algorithmic framework and empirical analysis[C] //Proc of ACM CCS 2010. New York: ACM, 2010: 176-186

[11]Wang D, Wang N, Wang P, et al. Preserving privacy for free: Efficient and provably secure two-factor authentication scheme with user anonymity[J]. Information Sciences, 2015, 321: 162-178

[12]Biddle R, Chiasson S, Van Oorschot P C. Graphical passwords: Learning from the first twelve years[J]. ACM Computing Surveys, 2012, 44(4): No.19

[13]Yang Y, Lu H, Liu J K, et al. Credential wrapping: From anonymous password authentication to anonymous biometric authentication[C] //Proc of ASIACCS 2016. New York: ACM, 2016: 141-151

[14]Zheng N, Paloski A, Wang H. An efficient user verification system using angle-based mouse movement biometrics[J]. ACM Trans on Information and System Security, 2016, 18(3): 1-27

[15]Bonneau J, Herley C, Oorschot P, et al. The quest to replace passwords: A framework for comparative evaluation of web authentication schemes[C] //Proc of IEEE S&P 2012. Piscataway, NJ: IEEE, 2012: 553-567

[16]Herley C, Van Oorschot P. A research agenda acknowledging the persistence of passwords[J]. IEEE Security & Privacy, 2012, 10(1): 28-36

[17]Lindell Y. A Post-Password World?[EB/OL]. [2016-04-06]. https://www.dyadicsec.com/post-password_world/

[18]Freeman D, Dürmuth M, Biggio B. Who are you? A statistical approach to measuring user authenticity[C] //Proc of NDSS 2016. San Diego, CA: Internet Society, 2016: 1-15

[19]Garfinkel S, Lipford H R. Usable security: History, themes, and challenges[J]. Synthesis Lectures on Information Security, Privacy, and Trust, 2014, 5(2): 1-124

[20]Song Y, Yang C, Gu G. Who is peeping at your passwords at starbucks? to catch an evil twin access point[C] //Proc of IEEE/IFIP DSN 2010. Piscataway, NJ: IEEE, 2010: 323-332

[21]Zhang F, Leach K, Wang H, et al. Trustlogin: Securing password-login on commodity operating systems[C] //Proc of ASIACCS 2015. New York: ACM, 2015: 333-344

[22]Wang D, Wang P. The emperor’s new password creation policies[G] //LNCS 9327: Proc of ESORICS 2015. Berlin: Springer, 2015: 456-477

[23]Ma J, Yang W, Luo M, et al. A study of probabilistic password models[C] //Proc of IEEE S&P 2014. Piscataway, NJ: IEEE, 2014: 689-704

[24]Wang D, Cheng H, Wang P, et al. Understanding passwords of Chinese users: Characteristics, security and implications, CACR Report[EB/OL]. ChinaCrypt 2015, [2004-02-25]. http://t.cn/RG8RacH

[25]Wang, D, Jian G, Huang X, et al. Zipf’s law in passwords[J/OL]. IEEE Trans on Information Forensics and Security, 2016. [2016-06-15]. http://eprint.iacr.org/2014/631.pdf

[26]Liu Gongshen, Qiu Weidong, Meng Kui, et al. Password vulnerability assessment and recovery based on rules mined from large-scale real data[J]. Chinese Journal of Computers, 39(3): 454-467 (in Chinese)(劉功申, 邱衛(wèi)東, 孟魁, 等. 基于真實數(shù)據(jù)挖掘的口令脆弱性評估及恢復(fù)[J]. 計算機學(xué)報, 2016, 39(3): 454-467)

[27]Das A, Bonneau J, Caesar M, et al. The tangled web of password reuse[C] //Proc of NDSS 2014. San Diego, CA: Internet Society, 2014: 1-15

[28]Wang D, He D, Cheng H, et al. fuzzyPSM: A new password strength meter using fuzzy probabilistic context-free grammars[C] //Proc of IEEE/IFIP DSN 2016. Piscataway, NJ: IEEE, 2016: 595-606

[29]Li Y, Wang H, Sun K. A study of personal information in human-chosen passwords and its security implications[C] //Proc of INFOCOM 2016. Piscataway, NJ: IEEE, 2016: 1-9

[30]Weir W, Aggarwal S, Medeiros B, et al. Password cracking using probabilistic context-free grammars[C] //Proc of IEEE S&P 2009. Piscataway, NJ: IEEE, 2009: 391-405

[31]Veras R, Collins C, Thorpe J on the semantic patterns of passwords and their security impact[C] //Proc of NDSS 2014. San Diego, CA: Internet Society, 2014: 1-15

[32]Castelluccia C, Dürmuth M, Perito D. Adaptive password strength meters from markov models[C] //Proc of NDSS 2012. San Diego, CA: Internet Society, 2012: 1-15

[33]Houshmand S, Aggarwal S. Building better passwords using probabilistic techniques[C] //Proc of ACSAC 2012. New York: ACM, 2012: 109-118

[34]Shay R, Komanduri S, Durity A L, et al. Designing Password Policies for Strength and Usability[J]. ACM Trans on Information and System Security, 2016, 18(4): No.13

[35]Morris R, Thompson K. Password security: A case history[J]. Communications of the ACM, 1979, 22(11): 594-597

[36]Riddle B, Miron M, Semo J. Passwords in use in a university timesharing environment[J]. Computer & Security, 1989, 8(7): 569-579

[37]Wu T. A real-world analysis of kerberos password security[C] //Proc of NDSS 1999. San Diego, CA: Internet Society, 1999: 1-10

[38]Narayanan A, Shmatikov V. Fast dictionary attacks on passwords using time-space tradeoff[C] //Proc of CCS 2005. New York: ACM, 2005: 364-372

[39]Ives B, Walsh K R, Schneider H. The domino effect of password reuse[J]. Communications of the ACM, 2004, 47(4): 75-78

[40]Bonneau J. The science of guessing: Analyzing an anonymized corpus of 70 million passwords[C] //Proc of IEEE S&P 2012. Piscataway, NJ: IEEE, 2012: 538-552

[41]Adams A, Sasse M A. Users are not the enemy[J]. Communications of the ACM, 1999, 42(12): 40-46

[42]Florêncio D, Herley C. Where do security policies come from?[C] //Proc of SOUPS 2010. New York: ACM, 2010: 1-14

[43]Beautement A, Sasse M A, Wonham M. The compliance budget: Managing security behaviour in organizations[C] //Proc of NSPW 2009. New York: ACM, 2009: 47-58

[44]Stobert E, Biddle R. The password life cycle: User behaviour in managing passwords[C] //Proc of SOUPS 2014. New York: ACM, 2014: 243-255

[45]Florêncio D, Herley C, Van Oorschot P C. Password portfolios and the finite-effort user: Sustainably managing large numbers of accounts[C] //Proc of SEC 2014. Berkeley, CA: USENIX Association, 2014: 575-590

[46]Ji S, Yang S, Hu X, et al. Zero-sum password cracking game: A large-scale empirical study on the crackability, correlation, and security of passwords[J]. IEEE Trans on Dependable and Secure Computing, 2016, Doi:10.1109/TDSC.2015.2481884

[47]Bailey D, Dürmuth M, Paar C. Statistics on password re-use and adaptive strength for financial accounts[C] //Proc of SCN 2014. Berlin: Springer, 2014: 218-235

[48]Halevi S, Krawczyk H. Public-key cryptography and password protocols[J]. ACM Trans on Information System Security, 1999, 2(3), 230-268

[49]Katz J, Ostrovsky R, Yung M. Efficient and secure authenticated key exchange using weak passwords[J]. Journal of the ACM, 2009, 57(1): 1-41

[50]Troy Hunt. Pwned websites[EB/OL]. [2016-06-15]. https://haveibeenpwned.com/PwnedWebsites

[51]Zipf G. Human behavior and the principle of least effort[M]. Reading, MA: Addison-Wesley, 1949

[52]Malone D, Maher K. Investigating the distribution of password choices[C] //Proc of WWW 2012. New York: ACM, 2012: 301-310

[53]Zhang L, Zhang Z, Hu X. UC-secure two-server password-based authentication protocol and its applications[C] //Proc of ASIACCS 2016. New York: ACM, 2016: 153-164

[54]Wang D, Wang P. Two birds with one stone: Two-factor authentication with security beyond conventional bound[J]. IEEE Trans on Depend Security Computer, 2016, Doi: 10.1109/TDSC.2016.2605087

[55]Huang Z, Ayday E, Hubaux J, et al. Genoguard: Protecting genomic data against brute-force attacks[C] //Proc of IEEE S&P 2015. Piscataway, NJ: IEEE, 2015: 447-462

[56]Blocki J, Datta A. CASH: A cost asymmetric secure hash algorithm for optimal password protection[C/OL] //Proc of IEEE CSF 2016. Piscataway, NJ: IEEE, 2016 [2016-06-15]. http://arxiv.org/pdf/1509.00239v1.pdf

[57]McDowell M, Hernan S, Rafail J. Choosing and protecting passwords[EB/OL]. [2013-02-06]. https://www.us-cert.gov/ncas/tips/ST04-002

[58]Jacoby D. False Perceptions of IT Security: Passwords[EB/OL]. [2014-12-16]. https://blog.kaspersky.com/false-perception-of-it-security-passwords/7036/

[59]Singer A, Anderson W, Farrow R. Rethinking password policies[J]. Usenix Login, 2013, 38(4): 14-19

[60]Blocki J, Blum M, Datta A. Naturally rehearsing passwords[C] //Proc of ASIACRYPT 2013. Berlin: Springer, 2013: 361-380

[61]Centre for the Protection of National Infrastructure. Password guidance: Executive summary[EB/OL]. [2015-09-08]. https://www.gov.uk/government/publications/password-policy-simplifyig-your-approach/password-policy-executive-summary

[62]Yampolskiy R V. Analyzing user password selection behavior for reduction of password space[C] //Proc of IEEE CCST 2006. Piscataway, NJ: IEEE, 2006: 109-115

[63]Dell’Amico M, Michiardi P, Roudier Y. Password strength: An empirical analysis[C] //Proc of INFOCOM 2010. Piscataway, NJ: IEEE, 2010: 1-9

[64]Dell’Amico M, Filippone M. Monte carlo strength evaluation: Fast and reliable password checking[C] //Proc of ACM CCS 2015. New York: ACM, 2015: 158-169

[65]Klein D. Foiling the cracker: A survey of, and improvements to, password security[C] //Proc of USENIX SEC 1990. Berkeley, CA: USENIX Association, 1990: 5-14

[66]Spafford E. Observations on reusable password choices[C] //Proc of USENIX SEC 1992. Berkeley, CA: USENIX Association, 1992: 1-16

[67]Kuo C, Romanosky S, Cranor L F. Human selection of mnemonic phrase-based passwords[C] //Proc of SOUPS 2006. New York: ACM, 2006: 67-78

[68]Schneier B. Real-World Passwords[EB/OL]. [2006-12-14]. https://www.schneier.com/blog/archives/2006/12/realworld_passw.html

[69]Veras R, Collins C, Thorpe J. On semantic patterns of passwords and their security impact[C] //Proc of NDSS 2014. San Diego, CA: Internet Society, 2014: 1-16

[70]Blei D M, Ng A Y, Jordan M I. Latent dirichlet allocation[J]. Journal of Machine Learning Research, 2003, 3: 993-1022

[71]Wang D, Zhang Z, Wang P, et al. Targeted online password guessing: An underestimated threat[C] //Proc of ACM CCS 2016. New York: ACM, 2016: 1-13

[72]Cachin C. Entropy measures and unconditional security in cryptography[D]. Z¨urich: ETH, 1997

[73]Pliam J. On the incomparability of entropy and marginal guesswork in brute-force attacks[G] //LNCS 1977: Proc of INDOCRYPT 2000. Berlin: Springer, 2000: 67-79

[74]Boztas S. Entropies, guessing, and cryptography, 6[R]. Melbourne: Department of Mathematics, Royal Melbourne Institute of Technology, 1999

[75]Ur B, Noma F, Bees J, et al. I added ‘!’ at the end to make it secure: Observing password creation in the lab[C] //Proc of SOUPS 2015. New York: ACM, 2015: 123-140

[76]Ur B, Bees J, Segreti S, et al. Do users’ perceptions of password security match reality[C] //Proc of ACM CHI 2016. New York: ACM, 2016: 3748-3760

[77]Carnavalet X, Mannan M. A large-scale evaluation of high-impact password strength meters[J]. ACM Trans on Information and System Security, 2015, 18(1): 1-32

[78]Ur B, Kelley P, Komanduri S, et al. How does your password measure up? The effect of strength meters on password creation[C] //Proc of SEC 2012. Berkeley, CA: USENIX Association, 2012: 65-80

[79]Egelman S, Sotirakopoulos A, Beznosov K, et al. Does my password go up to eleven? the impact of password meters on password selection[C] //Proc of CHI 2013. New York: ACM, 2013: 2379-2388

[80]Weir M, Aggarwal S, Collins M, et al. Testing metrics for password creation policies by attacking large sets of revealed passwords[C] //Proc of ACM CCS 2010. New York: ACM, 2010: 162-175

[81]Burr W, Dodson D, Perlner R, et al. Electronic authentication guideline, NIST SP800-63-2[R]. Reston, VA: National Institute of Standards and Technology, 2013

[82]Wheeler D. Zxcvbn: Realistic password strength estimation[EB/OL]. [2012-04-10]. https://blogs.dropbox.com/tech/2012/04/zxcvbn-realistic-password-strength-estimation/

[83]Reichl D. Details on the quality/strength estimations in KeePass[EB/OL]. [2012-04-10]. http://keepass.info/help/kb/pw quality est.html

[84]Tencent. Password strength meter of Tecent[EB/OL]. [2016-06-10]. http://zc.qq.com/chs/v2/

[85]Halevi S, Krawczyk H. Public-key cryptography and password protocols[J]. ACM Trans on Information and System Security, 1999, 2(3): 230-268

[86]Yi X, Rao F, Tari Z, et al. ID2S password-authenticated key exchange protocols[J]. IEEE Trans on Computers, 2016, doi:10.1109/TC.2016.2553031

[87]Jarecki S, Krawczyk H, Shirvanian M, et al. Device-enhanced password protocols with optimal online-offline protection.[C] //Proc of ASIACCS 2016. New York: ACM, 2016: 177-188

[88]Wilson M. 43 million Last.fm account details leaked after 2012 hack[EB/OL]. [2016-09-04]. http://betanews.com/2016/09/04/last-fm-password-leak/

[89]Juels A, Rivest R. Honeywords: Making password-cracking detectable[C] //Proc of ACM CCS 2013. New York: ACM, 2013: 145-160

Wang Ping, born in 1961. PhD, professor in Peking University. His main research interests include system security and distributed computing.

Wang Ding, born in 1985. PhD candidate in the School of Electrical Engineering and Computer Science, Peking University. His main research interests include password cryptography, cryptographic protocols and provable security (wangdingg@pku.edu.cn).

Huang Xinyi, born in 1981. PhD, professor at Fujian Normal University and the Co-Director of Fujian Provincial Key Laboratory of Network Security and Cryptology. His main research interests include applied cryptography and network security (xyhuang81@gmail.com).

Advances in Password Security

Wang Ping1,3, Wang Ding1, and Huang Xinyi2

1(SchoolofElectronicsEngineeringandComputerScience,PekingUniversity,Beijing100871)2(SchoolofMathematicsandComputerScience,FujianNormalUniversity,Fuzhou350117)3(SchoolofSoftwareandMicroelectronics,PekingUniversity,Beijing102600)

Identity authentication is the first line of defense for information systems, and passwords are the most widely used authentication method. Though there are a number of issues in passwords regarding security and usability, and various alternative authentication methods have also been successively proposed, password-based authentication will remain the dominant method in the foreseeable future due to its simplicity, low cost and easiness to change. Thus, this topic has attracted extensive interests from worldwide researchers, and many important results have been revealed. This work begins with the introduction of users’ vulnerable behaviors and details the password characteristics, distribution and reuse rate. Next we summarize the primary cracking algorithms that have appeared in the past 30 years, and classify them into groups in terms of the difference in dependence on what information is exploited by the attacker. Then, we revisit the various statistical-based evaluation metrics for measuring the strength of password distributions. Further, we compare the state-of-the-art password strength meters. Finally, we summarize our results and outline some future research trends.

identity authentication; password security; vulnerable behavior; guessing attack; strength evaluation

2016-06-15；

2016-09-07

國家重點研發(fā)計劃項目(2016YFB0800603)；國家自然科學(xué)基金項目(61472016,61472083)

TP391

This work was supported by the National Key Research Program of China (2016YFB0800603) and the National Natural Science Foundation of China (61472016,61472083).