基于概率上下文無關文法的口令強度評估方法

陳穎+狄宏+柳亞男

摘 要：口令作為當前互聯(lián)網(wǎng)應用最主要的安全認證方式之一，口令的強弱決定著用戶賬戶和系統(tǒng)的安全。文中針對目前常用的口令強度評估工具Passwordmeter等存在口令強度評估簡單、參數(shù)較少等口令易遭受字典攻擊等問題，利用信息熵進行口令強度的方法研究，提出一種新的口令強度評估方法。該方法采用概率上下文無關文法建模，對網(wǎng)絡泄露的真實口令明文進行特征分析，通過口令的結構劃分來計算其出現(xiàn)的概率，從而計算信息熵得出口令強度值，該方法計算代價較小，能夠有效抵抗字典攻擊。

關鍵詞：安全認證；口令規(guī)則；口令強度；信息熵；概率上下文無關文法

中圖分類號：TP391 文獻標識碼：A 文章編號：2095-1302（2017）04-00-03

0 引 言

據(jù)統(tǒng)計，現(xiàn)今互聯(lián)網(wǎng)用戶平均每天訪問25個需要登入口令的網(wǎng)站[1]?？诹钭鳛楫斍盎ヂ?lián)網(wǎng)登錄最常用的安全機制，時刻影響著人們的日常生活，盡管其他認證手段如生物特征信息認證等認證方式在技術上已取得了較快進展，但是口令以其成本較低、使用快捷的特點一直作為安全認證的最主要方式。對于用戶和網(wǎng)站的管理者而言，口令的安全性就顯得至關重要。所謂安全，是指口令在一定時間和代價下黑客無法破解[2]。

用戶往往會選擇一個便于記憶的口令，這就導致口令強度較低，很容易被人破解[3]。近日國外賬號密碼安全管理軟件Keeper發(fā)布了2016年25大最常見密碼，指出到2016年為止，還有17%的用戶使用“123456”作為密碼；最受歡迎的密碼前五位分別是：“123456”、“123456789”、“qwerty”、“12345678”和“111111”，這也說明人們對口令強度的重視程度還不夠。用戶的口令設置習慣還與其所處地區(qū)、文化背景有很大的關系，有研究表明不同國家的用戶在進行口令長度和字符類型的選擇時存在差異，比如中國大陸人偏好用純數(shù)字口令[4]。為了使用戶選擇強度更高的口令，很多網(wǎng)站都會采用口令強度檢驗器來實現(xiàn)，大多數(shù)檢驗器都通過規(guī)定口令長度、字符類型來讓用戶選擇口令，但用戶依然能夠設置出符合這些檢驗器規(guī)則但強度卻很低的口令。

當前有很多口令強度的評估工具，以Passwordmeter和Password Check Online為例，將需要評估強度的口令明文輸入這些工具，工具就會給出一個分數(shù)介于0到100之間的強度值。這些口令強度評估工具看似有用，但使用的規(guī)則過于簡單，導致得出的口令強度值不夠準確。

關于口令強度評估的研究有很多，國內(nèi)的劉公申等基于數(shù)據(jù)挖掘提出一種方法[3]，通過制定多個口令強度因素并賦予一定的權重來進行口令強度的評估。

2006年，美國國家標準與技術研究院提出利用信息熵來計算口令強度的方法[5]，通過計算口令在字典中出現(xiàn)的概率來評估口令強度。Claude Castelluccia等人則在此基礎上利用馬爾可夫模型計算口令的概率[6]，該方法強調(diào)的是口令相鄰字符之間的聯(lián)系。但在實際中，多數(shù)口令以分段式結構出現(xiàn)，類似于“ABC23456”、“791346qwer”、“！@#QWE123”，這種情況與馬爾可夫模型強調(diào)的相鄰字符之間的聯(lián)系存在差別。

本文針對口令存在結構劃分的特點，通過對網(wǎng)站泄露的真實口令進行分析，采用概率上下文無關文法（Probabilistic Context Free Grammar，PCFG）建模，提出一種自適應的口令強度評估方法。

1 相關研究

關于口令強度評估的研究是信息安全領域內(nèi)的一個重要研究方向，近年來國內(nèi)外研究人員在該領域也提出了一些新的口令強度評估方法。

1.1 現(xiàn)有的口令強度評估工具

當前網(wǎng)上存在很多口令強度評估工具，但其原理和操作方法都大同小異，以Passwordmeter為例，口令強度值的影響因素分為正向加分和負向減分兩種，加分項有長度、數(shù)字、大小寫字母、特殊符號等，每種因素賦予不同的權重；減分項有是否純數(shù)字、是否純字母、是否有重復字符等，且為每種因素賦予不同的權重；最后把兩種因素的分數(shù)值進行簡單加減運算得出口令的強度值，大小介于0到100之間，數(shù)值越大表示其強度越高。以2016年最常見的25大密碼中排名第17的“1q2w3e4r”為例，通過Passwordmeter工具評估得出該口令得分62，強度級別屬于“strong”，顯然與事實不符。

可以看出這類評估工具的方法十分簡單，僅通過口令字符的簡單規(guī)則就得出口令強度值為“strong”的口令是無法抵抗字典攻擊的。

1.2 基于真實數(shù)據(jù)挖掘的口令脆弱性評估

劉功申等提出一種基于真實數(shù)據(jù)挖掘的口令脆弱性評估方法[3]。該方法通過對真實數(shù)據(jù)的挖掘得到真實口令的規(guī)則，依據(jù)口令長度、采用的字符種類、不同字符的拼接方法、是否包含特殊信息、是否包含私人信息、是否為常用口令或常用口令的一部分、是否包含英文單詞、是否包含中文詞匯的拼音及變體、字符是否按順序排列、字符是否重復和是否符合鍵盤分布共11個規(guī)則因素，對每個因素進行分數(shù)和權重的分配以進行加權求和計算，最終得出口令強度值。

該方法制定了更為復雜、更為科學的強度影響因子，也考慮到了字典攻擊的影響因素，在效果上比Passwordmeter等工具好很多。這種方法依然采用口令規(guī)則的方式進行口令強度評估，目前還有一種比較流行的方式，即通過計算信息熵進行口令強度的評估。

1.3 基于信息熵的口令強度評估

2006年美國國家標準與技術研究院提出利用信息熵來計算口令強度的方法[5]。利用信息熵計算公式計算口令強度，將評估口令強度的問題轉(zhuǎn)化到計算待評估口令的概率問題。同時在文獻中提出了猜測熵、最小熵等計算方法，以此為依據(jù)，大量研究人員展開了以信息熵計算為基礎的口令強度評估方法的研究。

Claude Castelluccia等人提出了一種基于馬爾可夫模型的自適應口令強度評估方法[6]，該方法通過馬爾可夫模型獲得口令的概率，采用計算信息熵的方法進行口令強度的計算。馬爾可夫模型此前在口令字典生成領域有比較成功的應用[7]。

基于馬爾可夫模型的口令強度評估方法，字符與字符之間存在聯(lián)系，通常知道一條口令的前幾位，可以預測出下一位字符。文獻[6]提出n-gram的馬爾可夫模型通過n-1長度的前綴字符串來確定下一個字符的概率。

（1）n-gram數(shù)據(jù)庫的建立

在建立n-gram數(shù)據(jù)庫之前，采用的口令字符集為大寫字母、小寫字符、阿拉伯數(shù)字以及特殊符號，為方便計算，將其中的特殊符號統(tǒng)一采用一個符號來代替，這樣不僅可以避免轉(zhuǎn)移概率矩陣過于稀疏，還能夠完整保留口令的規(guī)律。依據(jù)已有的口令數(shù)據(jù)庫，先統(tǒng)計口令中n元組字符串的頻次，為避免存在某n元組數(shù)目為0的情況，采用數(shù)量加1平滑策略，至此，n-gram數(shù)據(jù)庫建立完成。

（2）口令強度評估方法

采用信息熵的方式進行口令強度評估，計算口令C=c1，c2，…，cm的強度。

其中，S表示字符集。

文獻[6]通過實驗說明該模型在口令強度評估方面確實有不錯的效果。文獻[2]針對此模型提出了改進方案，結合口令三元組的乘積、口令長度與口令首字符的出現(xiàn)概率等設計了新的強度評估函數(shù)，并將其運用到口令字典分級當中。但該方法的準確程度依賴于馬爾可夫建模時階數(shù)的選擇，當階數(shù)較大時，計算量很大。

本文采用計算信息熵的方法進行口令強度的評估，但與馬爾可夫模型不同的是，本文采取統(tǒng)計口令分段式結構特征的方法來獲取口令的概率。

2 基于概率上下文無關文法的口令強度評估

針對口令存在的分段式結構特點，采用概率上下文無關文法建模，先統(tǒng)計大量真實口令的結構特點，計算出待測口令的概率，用得到的概率值計算信息熵以獲得口令強度。

2.1 概率上下文無關文法

概率上下文無關文法是上下文無關文法的擴展。一個概率上下文無關文法（PCFG）是一個五元組（N，∑，S，R，P），即一個非終結符集N，一個終結符集∑，一個開始非終結符S∈N，一個產(chǎn)生式集R，對于任意產(chǎn)生式r∈R，其概率為P（r）。

PCFG的規(guī)則表示形式為：A→αp，其中A為非終結符，p為A推導出α的概率，即p=P（A→α），該概率分布必須滿足條件：∑P（A→α）=1，即相同左部的產(chǎn)生式概率分布滿足歸一化條件。

2009 年，Matt Weir 和 Sudhir Aggarwal 等人提出基于概率的上下文無關文法模型用于生成口令字典[8]，實驗證明，該模型用于口令字典生成效果很好。

2.2 基于概率上下文無關文法的口令強度評估方法

基于概率上下文無關文法的口令強度評估方法分為兩部分，第一部分為真實口令數(shù)據(jù)的結構特征統(tǒng)計，對收集到的大量真實口令數(shù)據(jù)進行處理；第二部分為口令強度的計算。

2.2.1 真實口令數(shù)據(jù)的結構特征統(tǒng)計

口令中的字符分為三類，分別是數(shù)字、字母和特殊符號，在進行數(shù)據(jù)處理的過程中，將數(shù)字、字母、特殊符號分別用D、L、S來表示。比如口令“123456！@#$password”，將其表示為“DDDDDDSSSSLLLLLLLL”，我們稱所有的“DSL”結構為數(shù)據(jù)的結構類型。

數(shù)據(jù)的預處理首先通過劃分口令數(shù)據(jù)的結構類型將訓練集中的所有口令數(shù)據(jù)進行分類，并計算每種結構類型出現(xiàn)的概率，將所有結構按照概率值降序排列存儲。通過對網(wǎng)易游戲泄露的四百多萬條口令明文進行處理，選取一部分結果進行展示，見表1所列。

統(tǒng)計每種字符類型，以字母為例。統(tǒng)計口令中連續(xù)出現(xiàn)的所有字母串，以口令“chen1laughing2wen”為例，截取“chen”、“l(fā)aughing”、“wen”三個字母串，對所有口令都進行相同處理，分別計算相同字符串出現(xiàn)的次數(shù)，然后統(tǒng)計相同長度下不同字符串各自出現(xiàn)的概率，對數(shù)字、特殊字符進行相同的處理。對網(wǎng)易泄露的四百多萬條口令進行統(tǒng)計，選取部分結果展示，見表2、表3和表4所列。

2.2.2 口令強度的計算

進行口令強度計算時先將口令轉(zhuǎn)化為結構類型，查詢結構類型的概率記為P1；查詢口令結構每個字結構的概率，記為P2、P3……；計算查詢得到的所有概率的乘積記為P；計算口令強度值：

這里以評估口令“password123@@”的強度為例，其結構類型為“LLLLLLLLDDDSS”，查詢其概率記為P1，查詢其子結構“password”、“123”和“@@”的概率分別記作P2、P3和P4，然后求各概率的乘積P=P1×P2×P3×P4，按公式（3）計算出F值，即為口令強度值。

2.3 強度評估測試

測試數(shù)據(jù)來自網(wǎng)易游戲泄露的四百多萬條口令明文，用本文的方法通過該口令集測試出口令的信息熵值介于6到59之間。統(tǒng)計該口令集的口令明文，對口令出現(xiàn)的次數(shù)按序排列，以排名第14位的“woaini1314”為例，通過Passwordmeter進行檢測，其強度為53，級別為“good”；而通過本文提出的強度評估方法得出強度值為15.20，可以看出該值更加符合該口令的實際強度。

2.4 關于模型的說明

本文提出的口令強度評估方法依賴收集到的大量真實的口令數(shù)據(jù)，收集到的口令數(shù)據(jù)量的大小將影響最終的結果，所以前期需要進行大量的口令收集工作。

由于不同地區(qū)的口令設置習慣不同，在進行一次口令強度評估時要采用同一地區(qū)的口令數(shù)據(jù)進行預處理；同樣對于同一待評估強度的口令選取不同地區(qū)的真實口令數(shù)據(jù)進行分析時得到的結果會有所差別，這也能體現(xiàn)該模型具有很強的自適應性。

3 結 語

本文提出了基于概率上下文無關文法的口令強度評估模型，該模型依賴于大量的真實口令數(shù)據(jù)。針對此情況未來的工作要著眼于真實數(shù)據(jù)的收集，進行大量的實驗來驗證算法的實際效果，提出更為完善的算法說明。

參考文獻

[1]張建明，林亞平，周四望，等.傳感器網(wǎng)絡中誤有界的小波數(shù)據(jù)壓縮算法[J].軟件學報，2010，21（6）：1364-1377.

[2]沈瑛，廖劉承，董天陽.口令強度評估的分級先驗模型研究[J].計算機科學，2015， 42（11）：222-227.

[3]劉功申，邱衛(wèi)東，孟魁，等.基于真實數(shù)據(jù)挖掘的口令脆弱性評估及恢復[J].計算機學報，2016，39（3）：454-467.

[4]黃萍，張許杰，劉剛.小世界網(wǎng)絡的研究現(xiàn)狀與展望[J].情報雜志，2007，26（4）：66-68.

[5] W.E.Burr，D.F.Dodson，W.T.Polk. Electronic authentication guideline[Z].NIST special publication，2006.

[6] C Castelluccia，M Dürmuth，D Perito.Adaptive Password-Strength Meters from Markov Models[Z].

[7] Chris D，Ravi G. BApasswd：A new proactive passwordchecker[C].Proceedings of the 16th National Computer Security Conference，Baltimore，USA，1993：1-5.

[8] M.Weir，S.Aggarwal，B.de Medeiros，et al.Password Cracking Using Probabilistic Contest-Free Grammars[Z].in Proc. 30th IEEE Symp.Secur.Privacy，2009：391-405.

[9] Tsourakakis C E.Fast counting of treangles in large real networks without counting：Algorithms and laws[C].The Eighth IEEE International Conference on Data Mining，IEEE，2008：608-617.