口令安全研究進展

王 平 汪 定 黃欣沂

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

?

口令安全研究進展

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

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

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

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

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

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

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

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

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

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

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

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

1 用戶的脆弱口令行為

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

當前，廣泛采用的口令脆弱行為挖掘方法既有實證分析(如文獻[23-26])，也有用戶調查(如文獻[27-28])；實證分析的數據既有來自于黑客泄露(如文獻[23-25,46])，也有來自于企業合作(如文獻[40,47])；用戶調查既有小規模的傳統調查(如文獻[27-28])，也有基于外包服務的新型大規模網絡調查(如文獻[34]).為更好顯示實證分析結果，本文使用了8個知名真實口令集，如表1所示.總的來說，已發現用戶的脆弱口令行為主要可以歸為以下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 口令構造的偏好性選擇

1.1.1 國民口令

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

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

Table 2 Top-10 Most Popular Passwords of Each Service

1.1.2 Zipf分布

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

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

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

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

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

1.1.3 字符組成結構

當網站設置了口令生成策略時，口令的字符組成很大程度上由口令策略所決定.當網站未設置口令構成策略時，用戶口令的結構直接體現了用戶的偏好[22-24].

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

1.1.4 口令長度

用戶口令長度也直接受網站策略影響.當網站未設置長度限制時，口令的長度分布由受網站服務類型(重要程度)的影響.比如，000webhost提供建站服務，口令具有管理員權限，該網站34.7%的口令長度不低于11，這一比例是其他任意網站的2倍以上.表4顯示，對于普通網站來說，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 口令重用

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

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

Table 5 Statistics About Password Reuse

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

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

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

1.3 基于個人信息構造口令

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

Table 6 Personal Information Usages in 12306

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

Table 7 Various Name Usages in Passwords

2 口令猜測攻擊

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

Table 8 A Taxonomy of Password (PW) Guessing Attacks

2.1 漫步攻擊算法

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

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

2.1.1 啟發式算法

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

2.1.2 PCFG

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

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

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

在猜測集生成階段，依據上面獲得的模式頻率表Σ1和語義頻率表Σ2，生成一個帶頻率猜測的集合，以模擬現實中口令的概率分布.比如，猜測“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鏈技術引入到口令猜測中來.該算法的核心假設是：用戶構造口令從前向后依次進行.它不像PCFG那樣對口令進行分割，而是對整個口令進行訓練，通過從左到右的字符之間的聯系來計算口令的概率.類似PCFG模型，Markov模型也分為訓練和猜測集生成2個階段.

在訓練階段，統計口令中每個子串后面跟的一個字符的頻數.Markov模型有階的概念，n階Markov模型就需要記錄長度為n的字符串后面跟的一個字母頻數.例如，在4階Markov中，口令abc123需要記錄的有：開頭是a的頻數，a后面是b的頻數，ab后面是c的頻數，abc后面是1的頻數，abc1后面是2的頻數，bc12后面是3的頻數.這樣，每個字符串在訓練之后都能得到一個概率，即從左到右，將長度為n的子串在訓練結果中進行查詢，將所有的概率相乘得到該字符串的概率.在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]首次將平滑技術和正規化技術運用到Markov模型中.平滑技術是為了消除數據集中過擬合(overfitting)問題，主要有Laplace平滑和Simple Good-Turing平滑2種；正規化技術是為了使得攻擊算法所生成的猜測的概率總和始終為1，形成一個概率模型，主要有End-Symbol正規化和長度分布正規化2種.下面以Laplace平滑技術和End-Symbol正規化技術為例說明.

Laplace平滑是在訓練完畢之后，對于每個字符串的頻數都加0.01，再去計算字符串的概率.例如，對于字符串abc123，其中的概率計算如下：

P(3|bc12)=

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

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

2.1.4 NLP

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

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

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

2.2 定向攻擊算法

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

2.2.1 Targeted-Markov

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

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

2.2.2 Personal-PCFG

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

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

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

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

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

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

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

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

3.1 信息熵

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

3.2 最小熵

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

H∞(X)=-logp1.

3.3 猜測熵

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

3.4β-success-rate

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

3.5α-work-factor

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

3.6α-guesswork

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

其等價的比特表現形式為

3.7 指標的應用示例

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

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

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

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

4 口令強度評測

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

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

4.1 基于規則的口令強度評價方法

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

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

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

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

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

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

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

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

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

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

圖9采用Spearman系數對上述6個主流PSM進行了對比.對于一個給定的測試口令集，PSM會對其中每個口令輸出一個強度值(概率值)；如果將這些口令將其強度值排序，會產生一個口令強度序列.Spearman系數用以衡量一個PSM輸出的強度序列與理想PSM輸出的強度序列間的相關關系：2個序列完全相同則Spearman系數為1，倒序則Spearman系數為-1，Spearman系數越大表明2個序列越接近.因此，Spearman系數越大表明其越接近理想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最核心功能是防止用戶選擇弱口令：準確向用戶反饋口令的強度，當發現用戶選擇了弱口令時，進行重點提示或阻止.因此，總體來說，fuzzyPSM表現最優，學術界的PSM要優于工業界PSM，標準組織NIST的PSM的評價結果準確性最低.

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

5 總結與展望

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

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

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

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

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

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

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

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

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

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

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

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

[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)(劉功申, 邱衛東, 孟魁, 等. 基于真實數據挖掘的口令脆弱性評估及恢復[J]. 計算機學報, 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

國家重點研發計劃項目(2016YFB0800603)；國家自然科學基金項目(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).