PG-RNN: 一種基于遞歸神經網絡的密碼猜測模型

滕南君，魯華祥，金敏，葉俊彬，李志遠

（1. 中國科學院 半導體研究所，北京 100083; 2. 中國科學院大學，北京 100089; 3. 中國科學院 腦科學與智能技術卓越創新中心，上海 200031; 4. 半導體神經網絡智能感知與計算技術北京市重點實驗室，北京 100083）

在網絡時代普及的今天，密碼是一種被廣泛使用的用戶驗證方法。主要原因在于，一方面密碼方便理解、使用，另一方面較容易實現。然而，讓人擔憂的是，密碼的使用者總是傾向于設置一些強度低、易猜測的弱密碼，例如：abcdefg，1234567等。實際上，密碼的安全性和方便性之間，總是存在某種程度上的折中：即強密碼不容易被攻擊破解，但是對于用戶來說，很難記憶；而弱密碼雖然方便記憶和使用，但卻容易被猜到。現階段大部分網站在用戶設定密碼時，都會加入密碼強度測試機制(一般分為“弱、中等、強”3個級別)這樣的預防措施能夠在一定程度上提醒用戶避免設定過于簡單的密碼。這些機制通常都是基于規則的，比如：要求密碼必須包含一個數字、一個小寫字母或者一個特殊字符[1]，密碼長度在6～18位之間等。

如何更快、更有效地找到有效的用戶密碼，一直以來都是一個活躍的研究領域。目前流行的基于規則的密碼猜測工具hash-cat，John the ripper(JTR)[2-3], 主要通過原有的密碼字典或泄露的密碼數據集，加上密碼規則的模糊化和變形來生成新的大量近似的密碼。文獻[4]開發了一種基于模板結構的密碼模型PCFGs，采用了上下文無關法,這種方法背后的思想是將密碼切分成不同的模板結構(e.g.，5個小寫字母加3個數字)，讓終端產生的密碼符合這樣的密碼結構。每個生成的密碼P概率等于該密碼結構類型的概率PT與各子結構的概率乘積，例如，如果一個密碼由兩部分組成：字母+數字，那么該密碼的生成概率則為P=PletterPdigitPT，值得一提的是，PCFGs模型在針對長密碼時有著較好的效果。文獻[1]采用一種基于馬爾可夫的模型，該模型通過評估n元概率的原理，在衡量密碼強度上性能要優于基于規則的方法。文獻[6]系統地比較和實現了目前流行的幾種密碼猜測的技術來評估密碼強度，發現字典攻擊在發現弱密碼時最有效，它們能夠快速地以哈希校驗的方法快速檢驗大量規則相似的密碼，而馬爾可夫鏈模型則在強密碼時表現更加突出。所有的這些攻擊方法隨著搜索空間的不斷擴大，有效性會出現指數型的下降[7]。

盡管上述的這些方法，都能夠在一定程度上彌補人為設定密碼規則的一些不足，但是這些方法往往也包含大量非真實用戶設置密碼[5]；此外，密碼規則的確立和啟發式探索依然需要大量密碼專家的參與。對于人為設定的密碼，在一定程度上，可以將其看成語言的延伸，因此，明文密碼的設置習慣依然符合人類的表達習慣；在本文中我們希望能夠直接、有效地挖掘出密碼的一些內在的規律或特征。文獻[8-9]中，展示了遞歸神經網絡能夠很好地學習到文本數據特征，并且生成一些之前從未出現過的新字符組合。這表明，遞歸神經網絡并不僅僅只是簡單的復刻、重現訓練數據，而是通過內部的特征表示不同的訓練樣本，在高維度中綜合重構出新的數據。我們的PGRNN模型很大程度上是基于之前的這些方法，旨在通過小規模泄露密碼樣本數據，生成更多符合真實用戶密碼樣本分布空間特征的密碼，提高密碼猜測算法效率；同時，通過端到端的小模型生成方式，能夠有效地擴充密碼攻擊字典，縮小密碼猜測空間。

預測是一個概率問題，對于一個訓練好的RNN網絡，給定一串輸入字符序列，然后計算出下一個字符的概率分布并且根據概率生成下一個出現的字符，并將當前時刻的字符作為下一步網絡的輸入。由于密碼本身就是一串字符串，因此，密碼的生成和文本生成之間有著非常相似的特點。最早嘗試使用遞歸神經網絡來做密碼猜測攻擊的是一篇博客[10]，它的想法是通過一大堆已經被破解的密碼，產生新的、有效的密碼，來預測那些還沒有被破解的密碼。但是遺憾的是，作者只是簡單地搭建了個RNN模型，并沒有對模型進行調整和修改，每個模型只生成了很少的密碼數量，而且匹配上的密碼數量也非常有限，以至于作者對這種方法可行性表示懷疑。最近，文獻[11]第1次嘗試了使用生成對抗網絡[12](generative adversarial networks, GAN)來進行密碼猜測攻擊。在生成對抗網絡PassGAN中，生成網絡G和對抗網絡D采用的都是卷積神經網絡，生成網絡G接受輸入作為噪聲向量，前向傳播經過卷積層后輸出一個長度為10的one-hot編碼的字符序列。這些字符序列經過Softmax非線性函數之后，進入對抗網絡D中進行判別。在測試中，文獻[11]通過兩個網站公開泄露的密碼數據集來訓練PassGAN模型，然后生成不同數量級別的密碼數量，結果顯示他們的模型能夠在測試密碼數據中匹配上一定數量的密碼。Melicher等[13]提出了一種快速的密碼猜測方法，他們采用了復雜的3層長短時記憶(long-short term memory, LSTM)遞歸層和兩層全連接層的網絡來產生新的密碼字符序列。在測評中，文獻[13]基于蒙特卡羅仿真的方法：在一個非常大的數量范圍內(1010～1025)，對模型在5組密碼長度、字符類型都不同的測試數據上進行測試，結果表明他們的方法性能要優于基于字典和規則的Hash-cat與JTR，以及基于概率的PCFGs、Markov模型。

1 遞歸神經網絡和PG-RNN模型參數設置

1.1 遞歸神經網絡

遞歸神經網絡(RNN)是一種基于時間序列的網絡結構，因而能夠對具有時間順序特性的數據進行建模。對于字符級別的RNN網絡，在每個時間步上，輸入值為one-hot編碼的一維向量(其中，向量維度由數據集包含的字符種類數決定)，輸入數據信息傳遞到隱層，并更新隱層狀態，經過非線性函數后最后達到輸出層，輸出一個預測概率分布，并通過概率分布的值，確定輸出字符的種類。RNN網絡可以具有多層隱含層，并且每一層包含若干個神經元，加上非線性激活函數；因而整個網絡具有非常強大的特征表達能力。在連續多個時間步上，RNN網絡能夠組合、記錄大量的信息，從而能夠用來進行準確地預測工作。對于某一個特定時間步T的輸出，它不僅僅依賴于當前的輸入值，還與T之前的若干步輸入有關。舉個例子，一個RNN網絡要輸出“Beijing”這個字符串，我們可能會給該網絡輸入Beijin，而對于接下來網絡要輸出的這個字符，根據輸出概率分布，輸出字符“g”的概率要顯著高于其他候選字符。另外，在輸出一串字符之后，我們依賴一個特殊的換行符作為單個密碼結束的標志。

遞歸神經網絡的誤差通過反向梯度傳播算法按照時間步從后往前傳遞。但是，由于梯度在傳遞過程中需要經過連續地相乘，因此這樣的參數關系使得RNN的梯度傳播會存在一定的難度。Bengio等[16-17]證明了梯度在反向傳播中，會隨著時間步的推移呈指數級的衰減或者爆炸問題，給遞歸神經網絡的訓練增加難度。梯度爆炸會帶來RNN網絡訓練的不穩定性，在實際訓練中，梯度爆炸的情況可以通過對梯度進行裁剪(將梯度限制在一定數值范圍內)來有效地控制。后來出現的 long short term memory (LSTM)[14]，GRU[15]則是解決了RNN梯度衰減問題。通過改變神經元內部的結構方式，并且加入中間信息的存儲單元，使得梯度可以在很長的時間步上傳播，輸出與輸入之間依賴的時間跨度變大。對于密碼猜測任務來說，單個密碼的長度是有限的(絕大部分)。因此，長時間序列上的可依賴性或許并不是我們所需要的，因為對于一個長度有限的密碼來說，當前字符可能僅僅取決于之前的幾個字符，而不是很多個。出于這樣的考慮，本文中的PG-RNN模型采用的是之前沒有人嘗試過的RNN網絡結構，從而能夠搭建一個輕量化但非常有效地密碼猜測模型(整個網絡模型參數約0.12 M)。

1.2 PG-RNN模型參數設置

本文提出的PG-RNN模型，參數設置如下：出于對訓練數據中絕大部分的密碼長度的考慮，時間序列長度為20；模型采用單層遞歸神經網絡，隱層神經元數量為256，兩個全連接層；學習率初始化為0.01，采用了Adagrad梯度更新算法。

2 密碼數據集分析

本文采用的是從公開互聯網上收集到的一些網站泄露的真實密碼數據集合, 這些公開的密碼集合都是以純文本txt或者sql格式存在。我們僅僅使用這些數據集中的密碼部分，而濾除掉其他非相關信息(包括用戶注冊郵箱或者用戶名等)。我們在實驗中使用了如下的密碼數據集，它們分別是 Rockyou、Yahoo、CSDN、RenRen 和 Myspace[18-20]。Rockyou密碼集包含了2009年12月由于SQL漏洞遭到了黑客攻擊，導致約3 200萬用戶密碼， 我們收集到大約1 400萬無重復的密碼；2012年，Yahoo公司的Voices泄露了大約40萬個賬號信息，CSDN(Chinese software developer network)是目前國內最大的IT開發者社區，它在2011年發生的數據庫泄露事件，有大約600萬用戶賬號和明文密碼被公開。同樣是在2011年，國內著名的社交平臺人人網也被曝遭到黑客攻擊，將近500萬用戶賬號和密碼泄露. 此外，還有Myspace網站泄露的部分數據，大約37 000個存在于txt的明文密碼。

我們對這些數據進行了以下清洗工作。1)剔除掉了除密碼之外的其他信息；2)考慮到編碼問題，只保留了那些只包含95個可打印ASCII字符的密碼(出于用戶使用習慣考慮)，這一步濾除掉了少量的密碼；3)我們對這些密碼進行了長度的統計分析，如圖1所示。對于以上提到的密碼數據集，我們發現任何一個密碼數據集來說，大部分的密碼長度都集中在[5, 15]的范圍內(對于本文中采用到的密碼數據集來說，密碼長度分布在[5, 15]區段內的數量都占據了總數的95%以上)。這是因為一方面大部分網站在要求用戶輸入密碼時，都有最短長度限制，另一方面，對于大多數用戶在設定密碼時，為了方便自己記憶和輸入，也不會選擇長的密碼。因此我們進一步只選取了長度(不包括換行符)在[5, 15]的密碼作為我們的實驗數據。最終的密碼集細節情況如表1所示。

圖1 5個公開泄露的密碼數據集的密碼長度分布情況Fig. 1 The password length distribution of the five leaked passwords dataset

表 1 密碼數據集的統計以及數據清理情況Table 1 Statistic of password datasets and data clean

3 實驗及結果分析

3.1 PG-RNN的訓練與數據切分

為評估PG-RNN模型效果，我們對密碼數據集進行了隨機切分：70%密碼用于訓練，30%用于測試。以Rockyou密碼數據集為例，70%的訓練數據(一共有9 804 818個無重復密碼)，30%的測試數據(一共4 201 550個無重復密碼)，對于其他數據集，我們也做了同樣的處理。

神經網絡通過在訓練過程中不斷地迭代，逐步學習到數據特征。考慮到我們收集到的數據集之間大小差異巨大，而數據集的大小對于網絡的訓練次數是有著至關重要的影響。在實際訓練過程中，發現PG-RNN網絡迭代到約1.5個Epoch之后，誤差就不再下降了，網絡性能也達到了相對穩定階段。因此根據每個數據集的大小，我們選擇設置不同的迭代次數。

3.2 新生成密碼長度分布和字符結構評估

密碼長度和密碼字符結構類型一直是衡量密碼特性的重要指標。在該小節中，我們參考了文獻[5]的方法。對 Rockyou、CSDN、RenRen、Yahoo、Myspace原始數據集以及各自新生成的密碼數據集從密碼長度和密碼字符結構類型進行了統計分析。圖 2(a) ～ (e)分別表示 Rockyou、CSDN、Ren-Ren、Yahoo、Myspace的訓練數據集和生成的不同量級的新密碼集合在不同密碼長度(5～15)上的數量分布情況。

圖2 新生成的不同規模密碼集的長度分布情況Fig. 2 Length distribution of new password dataset with multiple scales

可以明顯地看出，通過我們的PG-RNN模型生成的新密碼數據，在長度分布上非常接近原始的訓練數據，當生成數量與原始訓練集相當時，二者幾乎達到了重合的程度。對比PG-RNN與其他方法在CSDN密碼集上的表現(生成規模約為原始密碼1倍)，原始數據集中數目最多的是長度為8的密碼，比例為36.37%，PG_RNN長度為8密碼比例為36.86%；文獻[5]中列出的方法在長度最多的密碼數量上出現了不同程度的偏差，其中PCFG和4階Markov，分別達到了6.2%和18.9%。

長度分布的衡量通常并不能很好地體現出密碼之間的差異性。文獻[2]中通過將密碼切分為不同的模板，反映出即使長度相同的密碼，也可能是由完全不同的字符類型組成。考慮此，按照如下的幾種字符結構類型對原始訓練數據集和新生成的密碼集 (～x1, ～x10)，進行了分類，包括純數字、純字母(大小寫)、數字+字母(大小寫)、特殊字符共4類，具體統計結果見表1。對于CSDN、RenRen來說，密碼訓練集都是以“純數字”和“數字+字母”的形式為主，比例分別占了各自對的45.4%和38.8%、52.4%和25%；而在Rockyou和Yahoo密碼數據集中，“數字+字母”和“純字母”占的比重最大，這也反映了國內外用戶在密碼設置習慣上的一些差異。從表1中，可以很容易看出，無論是大約1倍的規模，還是約10倍的規模，我們的PG-RNN模型生成的新密碼數據與原始的訓練密碼集的字符類型結構分布比例都非常地接近，即便是對于占比重非常小的包含特殊字符的類型。

3.3 在訓練集和測試集上的匹配度評估

參照文獻[11]中的對比方法，在這一小節中，我們對PG-RNN模型生成的新密碼數據進行了匹配度的評估，也就是新生成密碼與訓練集和測試集的密碼重合個數。重點對比了我們的方法與文獻[11中的PassGAN模型在Rockyou數據集上的效果；同時針對其他幾個數據集，我們也給出了PGRNN在測試集上的匹配度結果以及分析如表2所示。

表 2 CSDN原始密碼集和不同方法生成的新密碼集(x1規模)在密碼數最多的長度(L=8)上的比較Table 2 Comparison on CSDN primitive dataset and new datasets(x1 scale) generated by different methods on length (L=8) with the most passwords

密碼生成工具都是通過學習現有數據集中的數據特征來產生新的密碼數據集，而新密碼數據集與訓練集的匹配度也能夠反映出模型的學習能力。因此，有必要將新生成的密碼數據集與訓練數據進行對比分析。文中重點對比了PG-RNN模型與文獻[11]在Rockyou密碼數據集上的表現，具體結果如表3所示。從表格中可以直觀地看出，隨著生成密碼數量的增加，新生成密碼能夠與訓練集匹配上的密碼個數也在增加，這在PGRNN和PassGAN兩個模型上都能夠很好地得到體現，這也說明了PG-RNN模型和PassGAN都有著非常強的學習數據特征的能力。在匹配度上,隨著生成密碼數量的增加，本文提出的PGRNN方法與PassGAN相比，在匹配度的優勢愈發明顯；當生成密碼數量在108時，PG-RNN模型達到了x2.24倍以上的匹配度(由于數據切分比例不同，我們的訓練集包含的密碼個數為9 804 818(無重復)，文獻[11]為 9 926 278(無重復))。由于與訓練集匹配上的密碼是已知的，因此這部分密碼完全可以通過基于訓練集的字典攻擊方式而得到。但是，與訓練集的匹配度可以較好地表現出模型的學習能力的。值得一提的是，我們的RNN模型生成密碼的重復率要遠遠小于PassGAN，而在PassGAN模型生成的密碼中，密碼的重復率非常的高，達到80%以上(隨著生成密碼數增加，甚至大于90%)，事實上大量輸出重復的密碼并沒有多大意義，反而會增加密碼生成的時間。

表 3 不同訓練密碼集和規模約為訓練集1倍、10倍的新生成密碼集在密碼字符結構類型的統計情況Table 3 Character structure categories on training dataset and new generated passwords at the scale of x1, x10 respectively on different datasets

3.4 在測試集上的評估效果

此外，對PG-RNN和PassGAN兩個模型生成的新密碼，在測試集上進行了對比測試。詳細的對比結果如表4所示。

表 4 PG-RNN與PassGAN各自的生成密碼在Rockyou訓練集上的評估結果Table 4 The evaluation results between PG-RNN and PassGAN on Rockyou training dataset

其中，第3列和第5列分別表示的是在測試集中匹配上但是沒有出現在訓練集中的密碼個數(有重復)、在測試集中但不在訓練集中的密碼個數(無重復)。對比兩個模型的前兩行數據，可以看出，我們的模型在生成的密碼數多于PassGAN的情況下，能夠在測試集上匹配上的比例大于后者，這是理所當然的(由于切分比例不同，我們的測試集包含無重復密碼個數是4 201 550，文獻[11]中是3 094 199，計算比例時是相對于各自的測試集密碼數而言，這樣比較起來相對公平)。對比兩個模型的第3、4行數據結果，PGRNN在生成密碼數量上與PassGAN相同的情況下，依然能夠獲得比PassGAN大的在測試集的覆蓋率，甚至超過了1.2%，這進一步說明本文提出的PG-RNN模型是非常具有競爭力的。 需要指出的是，PassGAN使用了復雜的多層殘差卷積神經網絡，在網絡模型復雜度和訓練難度上都要遠遠高于PG-RNN模型。

除了Rockyou數據集，我們也在表5～6中，列出了我們的模型在其他數據集上的測試結果。從表格中看出，我們的PG-RNN模型針對不同的數據集都有較好的效果。此外，可以預見的是隨著生成數量的進一步增大，能夠匹配上的數目會進一步增加。而針對PG-RNN模型在Myspace數據集上的表現相對于在其他數據集表現較差的原因，我們分析主要在于神經網絡的訓練是高度依賴于數據的，因而對于數據量較多的情況能夠學習到更多的特征，而我們收集到的Myspace數據集太小，因此數據集體現的統計特征并不明顯，如表6。但是，總的來說，基于遞歸神經網絡的模型相對于人為設定規則和Markov等方法，具備更強的發掘密碼特征能力。

表 5 對比PG-RNN和PassGAN的生成密碼在Rockyou測試集上的評估結果Table 5 The evaluation results between PG-RNN and PassGAN on Rockyou test dataset

表 6 PG-RNN在其他密碼數據集上的評估結果Table 6 The evaluation results of PG-RNN on other datasets

4 結束語

本文提出了一種基于遞歸神經網絡的密碼猜測模型。在網上公開的泄露密碼數據集(包括Rockyou、CSDN、RenRen、Yahoo、Myspace)上對模型進行了一系列的訓練、測試；實驗結果表明，當在泄露密碼數據上訓練后，針對字符級別建模的遞歸神經網絡模型提供了一種端到端的密碼生成解決方法，能夠很好地用來生成大量密碼，從而方便破譯出更多潛在密碼。

我們的模型針對不同的數據集，以及生成不同密碼規模情況下，都能夠較好地在密碼結構字符類型，密碼長度分布等特征上接近原始訓練數據的。此外，在Rockyou數據集上，我們的PG-RNN模型在生成數據規模相當的情況下，在測試集中匹配超過11%的密碼個數，相對于PassGAN模型，超過了1.2%。我們的下一步工作主要分為以下兩個方面：1)嘗試其他的RNN網絡結構，并分析其在不同的結構在密碼猜測上的效果；2)進一步觀察RNN模型在生成密碼時的內部數據表示狀態。