滕南君,魯華祥,金敏,葉俊彬,李志遠
(1. 中國科學院 半導體研究所,北京 100083; 2. 中國科學院大學,北京 100089; 3. 中國科學院 腦科學與智能技術(shù)卓越創(chuàng)新中心,上海 200031; 4. 半導體神經(jīng)網(wǎng)絡智能感知與計算技術(shù)北京市重點實驗室,北京 100083)
在網(wǎng)絡時代普及的今天,密碼是一種被廣泛使用的用戶驗證方法。主要原因在于,一方面密碼方便理解、使用,另一方面較容易實現(xiàn)。然而,讓人擔憂的是,密碼的使用者總是傾向于設置一些強度低、易猜測的弱密碼,例如:abcdefg,1234567等。實際上,密碼的安全性和方便性之間,總是存在某種程度上的折中:即強密碼不容易被攻擊破解,但是對于用戶來說,很難記憶;而弱密碼雖然方便記憶和使用,但卻容易被猜到?,F(xiàn)階段大部分網(wǎng)站在用戶設定密碼時,都會加入密碼強度測試機制(一般分為“弱、中等、強”3個級別)這樣的預防措施能夠在一定程度上提醒用戶避免設定過于簡單的密碼。這些機制通常都是基于規(guī)則的,比如:要求密碼必須包含一個數(shù)字、一個小寫字母或者一個特殊字符[1],密碼長度在6~18位之間等。
如何更快、更有效地找到有效的用戶密碼,一直以來都是一個活躍的研究領(lǐng)域。目前流行的基于規(guī)則的密碼猜測工具hash-cat,John the ripper(JTR)[2-3], 主要通過原有的密碼字典或泄露的密碼數(shù)據(jù)集,加上密碼規(guī)則的模糊化和變形來生成新的大量近似的密碼。文獻[4]開發(fā)了一種基于模板結(jié)構(gòu)的密碼模型PCFGs,采用了上下文無關(guān)法,這種方法背后的思想是將密碼切分成不同的模板結(jié)構(gòu)(e.g.,5個小寫字母加3個數(shù)字),讓終端產(chǎn)生的密碼符合這樣的密碼結(jié)構(gòu)。每個生成的密碼P概率等于該密碼結(jié)構(gòu)類型的概率PT與各子結(jié)構(gòu)的概率乘積,例如,如果一個密碼由兩部分組成:字母+數(shù)字,那么該密碼的生成概率則為P=PletterPdigitPT,值得一提的是,PCFGs模型在針對長密碼時有著較好的效果。文獻[1]采用一種基于馬爾可夫的模型,該模型通過評估n元概率的原理,在衡量密碼強度上性能要優(yōu)于基于規(guī)則的方法。文獻[6]系統(tǒng)地比較和實現(xiàn)了目前流行的幾種密碼猜測的技術(shù)來評估密碼強度,發(fā)現(xiàn)字典攻擊在發(fā)現(xiàn)弱密碼時最有效,它們能夠快速地以哈希校驗的方法快速檢驗大量規(guī)則相似的密碼,而馬爾可夫鏈模型則在強密碼時表現(xiàn)更加突出。所有的這些攻擊方法隨著搜索空間的不斷擴大,有效性會出現(xiàn)指數(shù)型的下降[7]。
盡管上述的這些方法,都能夠在一定程度上彌補人為設定密碼規(guī)則的一些不足,但是這些方法往往也包含大量非真實用戶設置密碼[5];此外,密碼規(guī)則的確立和啟發(fā)式探索依然需要大量密碼專家的參與。對于人為設定的密碼,在一定程度上,可以將其看成語言的延伸,因此,明文密碼的設置習慣依然符合人類的表達習慣;在本文中我們希望能夠直接、有效地挖掘出密碼的一些內(nèi)在的規(guī)律或特征。文獻[8-9]中,展示了遞歸神經(jīng)網(wǎng)絡能夠很好地學習到文本數(shù)據(jù)特征,并且生成一些之前從未出現(xiàn)過的新字符組合。這表明,遞歸神經(jīng)網(wǎng)絡并不僅僅只是簡單的復刻、重現(xiàn)訓練數(shù)據(jù),而是通過內(nèi)部的特征表示不同的訓練樣本,在高維度中綜合重構(gòu)出新的數(shù)據(jù)。我們的PGRNN模型很大程度上是基于之前的這些方法,旨在通過小規(guī)模泄露密碼樣本數(shù)據(jù),生成更多符合真實用戶密碼樣本分布空間特征的密碼,提高密碼猜測算法效率;同時,通過端到端的小模型生成方式,能夠有效地擴充密碼攻擊字典,縮小密碼猜測空間。
預測是一個概率問題,對于一個訓練好的RNN網(wǎng)絡,給定一串輸入字符序列,然后計算出下一個字符的概率分布并且根據(jù)概率生成下一個出現(xiàn)的字符,并將當前時刻的字符作為下一步網(wǎng)絡的輸入。由于密碼本身就是一串字符串,因此,密碼的生成和文本生成之間有著非常相似的特點。最早嘗試使用遞歸神經(jīng)網(wǎng)絡來做密碼猜測攻擊的是一篇博客[10],它的想法是通過一大堆已經(jīng)被破解的密碼,產(chǎn)生新的、有效的密碼,來預測那些還沒有被破解的密碼。但是遺憾的是,作者只是簡單地搭建了個RNN模型,并沒有對模型進行調(diào)整和修改,每個模型只生成了很少的密碼數(shù)量,而且匹配上的密碼數(shù)量也非常有限,以至于作者對這種方法可行性表示懷疑。最近,文獻[11]第1次嘗試了使用生成對抗網(wǎng)絡[12](generative adversarial networks, GAN)來進行密碼猜測攻擊。在生成對抗網(wǎng)絡PassGAN中,生成網(wǎng)絡G和對抗網(wǎng)絡D采用的都是卷積神經(jīng)網(wǎng)絡,生成網(wǎng)絡G接受輸入作為噪聲向量,前向傳播經(jīng)過卷積層后輸出一個長度為10的one-hot編碼的字符序列。這些字符序列經(jīng)過Softmax非線性函數(shù)之后,進入對抗網(wǎng)絡D中進行判別。在測試中,文獻[11]通過兩個網(wǎng)站公開泄露的密碼數(shù)據(jù)集來訓練PassGAN模型,然后生成不同數(shù)量級別的密碼數(shù)量,結(jié)果顯示他們的模型能夠在測試密碼數(shù)據(jù)中匹配上一定數(shù)量的密碼。Melicher等[13]提出了一種快速的密碼猜測方法,他們采用了復雜的3層長短時記憶(long-short term memory, LSTM)遞歸層和兩層全連接層的網(wǎng)絡來產(chǎn)生新的密碼字符序列。在測評中,文獻[13]基于蒙特卡羅仿真的方法:在一個非常大的數(shù)量范圍內(nèi)(1010~1025),對模型在5組密碼長度、字符類型都不同的測試數(shù)據(jù)上進行測試,結(jié)果表明他們的方法性能要優(yōu)于基于字典和規(guī)則的Hash-cat與JTR,以及基于概率的PCFGs、Markov模型。
遞歸神經(jīng)網(wǎng)絡(RNN)是一種基于時間序列的網(wǎng)絡結(jié)構(gòu),因而能夠?qū)哂袝r間順序特性的數(shù)據(jù)進行建模。對于字符級別的RNN網(wǎng)絡,在每個時間步上,輸入值為one-hot編碼的一維向量(其中,向量維度由數(shù)據(jù)集包含的字符種類數(shù)決定),輸入數(shù)據(jù)信息傳遞到隱層,并更新隱層狀態(tài),經(jīng)過非線性函數(shù)后最后達到輸出層,輸出一個預測概率分布,并通過概率分布的值,確定輸出字符的種類。RNN網(wǎng)絡可以具有多層隱含層,并且每一層包含若干個神經(jīng)元,加上非線性激活函數(shù);因而整個網(wǎng)絡具有非常強大的特征表達能力。在連續(xù)多個時間步上,RNN網(wǎng)絡能夠組合、記錄大量的信息,從而能夠用來進行準確地預測工作。對于某一個特定時間步T的輸出,它不僅僅依賴于當前的輸入值,還與T之前的若干步輸入有關(guān)。舉個例子,一個RNN網(wǎng)絡要輸出“Beijing”這個字符串,我們可能會給該網(wǎng)絡輸入Beijin,而對于接下來網(wǎng)絡要輸出的這個字符,根據(jù)輸出概率分布,輸出字符“g”的概率要顯著高于其他候選字符。另外,在輸出一串字符之后,我們依賴一個特殊的換行符作為單個密碼結(jié)束的標志。
遞歸神經(jīng)網(wǎng)絡的誤差通過反向梯度傳播算法按照時間步從后往前傳遞。但是,由于梯度在傳遞過程中需要經(jīng)過連續(xù)地相乘,因此這樣的參數(shù)關(guān)系使得RNN的梯度傳播會存在一定的難度。Bengio等[16-17]證明了梯度在反向傳播中,會隨著時間步的推移呈指數(shù)級的衰減或者爆炸問題,給遞歸神經(jīng)網(wǎng)絡的訓練增加難度。梯度爆炸會帶來RNN網(wǎng)絡訓練的不穩(wěn)定性,在實際訓練中,梯度爆炸的情況可以通過對梯度進行裁剪(將梯度限制在一定數(shù)值范圍內(nèi))來有效地控制。后來出現(xiàn)的 long short term memory (LSTM)[14],GRU[15]則是解決了RNN梯度衰減問題。通過改變神經(jīng)元內(nèi)部的結(jié)構(gòu)方式,并且加入中間信息的存儲單元,使得梯度可以在很長的時間步上傳播,輸出與輸入之間依賴的時間跨度變大。對于密碼猜測任務來說,單個密碼的長度是有限的(絕大部分)。因此,長時間序列上的可依賴性或許并不是我們所需要的,因為對于一個長度有限的密碼來說,當前字符可能僅僅取決于之前的幾個字符,而不是很多個。出于這樣的考慮,本文中的PG-RNN模型采用的是之前沒有人嘗試過的RNN網(wǎng)絡結(jié)構(gòu),從而能夠搭建一個輕量化但非常有效地密碼猜測模型(整個網(wǎng)絡模型參數(shù)約0.12 M)。
本文提出的PG-RNN模型,參數(shù)設置如下:出于對訓練數(shù)據(jù)中絕大部分的密碼長度的考慮,時間序列長度為20;模型采用單層遞歸神經(jīng)網(wǎng)絡,隱層神經(jīng)元數(shù)量為256,兩個全連接層;學習率初始化為0.01,采用了Adagrad梯度更新算法。
本文采用的是從公開互聯(lián)網(wǎng)上收集到的一些網(wǎng)站泄露的真實密碼數(shù)據(jù)集合, 這些公開的密碼集合都是以純文本txt或者sql格式存在。我們僅僅使用這些數(shù)據(jù)集中的密碼部分,而濾除掉其他非相關(guān)信息(包括用戶注冊郵箱或者用戶名等)。我們在實驗中使用了如下的密碼數(shù)據(jù)集,它們分別是 Rockyou、Yahoo、CSDN、RenRen 和 Myspace[18-20]。Rockyou密碼集包含了2009年12月由于SQL漏洞遭到了黑客攻擊,導致約3 200萬用戶密碼, 我們收集到大約1 400萬無重復的密碼;2012年,Yahoo公司的Voices泄露了大約40萬個賬號信息,CSDN(Chinese software developer network)是目前國內(nèi)最大的IT開發(fā)者社區(qū),它在2011年發(fā)生的數(shù)據(jù)庫泄露事件,有大約600萬用戶賬號和明文密碼被公開。同樣是在2011年,國內(nèi)著名的社交平臺人人網(wǎng)也被曝遭到黑客攻擊,將近500萬用戶賬號和密碼泄露. 此外,還有Myspace網(wǎng)站泄露的部分數(shù)據(jù),大約37 000個存在于txt的明文密碼。
我們對這些數(shù)據(jù)進行了以下清洗工作。1)剔除掉了除密碼之外的其他信息;2)考慮到編碼問題,只保留了那些只包含95個可打印ASCII字符的密碼(出于用戶使用習慣考慮),這一步濾除掉了少量的密碼;3)我們對這些密碼進行了長度的統(tǒng)計分析,如圖1所示。對于以上提到的密碼數(shù)據(jù)集,我們發(fā)現(xiàn)任何一個密碼數(shù)據(jù)集來說,大部分的密碼長度都集中在[5, 15]的范圍內(nèi)(對于本文中采用到的密碼數(shù)據(jù)集來說,密碼長度分布在[5, 15]區(qū)段內(nèi)的數(shù)量都占據(jù)了總數(shù)的95%以上)。這是因為一方面大部分網(wǎng)站在要求用戶輸入密碼時,都有最短長度限制,另一方面,對于大多數(shù)用戶在設定密碼時,為了方便自己記憶和輸入,也不會選擇長的密碼。因此我們進一步只選取了長度(不包括換行符)在[5, 15]的密碼作為我們的實驗數(shù)據(jù)。最終的密碼集細節(jié)情況如表1所示。
圖1 5個公開泄露的密碼數(shù)據(jù)集的密碼長度分布情況Fig. 1 The password length distribution of the five leaked passwords dataset
表 1 密碼數(shù)據(jù)集的統(tǒng)計以及數(shù)據(jù)清理情況Table 1 Statistic of password datasets and data clean
為評估PG-RNN模型效果,我們對密碼數(shù)據(jù)集進行了隨機切分:70%密碼用于訓練,30%用于測試。以Rockyou密碼數(shù)據(jù)集為例,70%的訓練數(shù)據(jù)(一共有9 804 818個無重復密碼),30%的測試數(shù)據(jù)(一共4 201 550個無重復密碼),對于其他數(shù)據(jù)集,我們也做了同樣的處理。
神經(jīng)網(wǎng)絡通過在訓練過程中不斷地迭代,逐步學習到數(shù)據(jù)特征??紤]到我們收集到的數(shù)據(jù)集之間大小差異巨大,而數(shù)據(jù)集的大小對于網(wǎng)絡的訓練次數(shù)是有著至關(guān)重要的影響。在實際訓練過程中,發(fā)現(xiàn)PG-RNN網(wǎng)絡迭代到約1.5個Epoch之后,誤差就不再下降了,網(wǎng)絡性能也達到了相對穩(wěn)定階段。因此根據(jù)每個數(shù)據(jù)集的大小,我們選擇設置不同的迭代次數(shù)。
密碼長度和密碼字符結(jié)構(gòu)類型一直是衡量密碼特性的重要指標。在該小節(jié)中,我們參考了文獻[5]的方法。對 Rockyou、CSDN、RenRen、Yahoo、Myspace原始數(shù)據(jù)集以及各自新生成的密碼數(shù)據(jù)集從密碼長度和密碼字符結(jié)構(gòu)類型進行了統(tǒng)計分析。圖 2(a) ~ (e)分別表示 Rockyou、CSDN、Ren-Ren、Yahoo、Myspace的訓練數(shù)據(jù)集和生成的不同量級的新密碼集合在不同密碼長度(5~15)上的數(shù)量分布情況。
圖2 新生成的不同規(guī)模密碼集的長度分布情況Fig. 2 Length distribution of new password dataset with multiple scales
可以明顯地看出,通過我們的PG-RNN模型生成的新密碼數(shù)據(jù),在長度分布上非常接近原始的訓練數(shù)據(jù),當生成數(shù)量與原始訓練集相當時,二者幾乎達到了重合的程度。對比PG-RNN與其他方法在CSDN密碼集上的表現(xiàn)(生成規(guī)模約為原始密碼1倍),原始數(shù)據(jù)集中數(shù)目最多的是長度為8的密碼,比例為36.37%,PG_RNN長度為8密碼比例為36.86%;文獻[5]中列出的方法在長度最多的密碼數(shù)量上出現(xiàn)了不同程度的偏差,其中PCFG和4階Markov,分別達到了6.2%和18.9%。
長度分布的衡量通常并不能很好地體現(xiàn)出密碼之間的差異性。文獻[2]中通過將密碼切分為不同的模板,反映出即使長度相同的密碼,也可能是由完全不同的字符類型組成??紤]此,按照如下的幾種字符結(jié)構(gòu)類型對原始訓練數(shù)據(jù)集和新生成的密碼集 (~x1, ~x10),進行了分類,包括純數(shù)字、純字母(大小寫)、數(shù)字+字母(大小寫)、特殊字符共4類,具體統(tǒng)計結(jié)果見表1。對于CSDN、RenRen來說,密碼訓練集都是以“純數(shù)字”和“數(shù)字+字母”的形式為主,比例分別占了各自對的45.4%和38.8%、52.4%和25%;而在Rockyou和Yahoo密碼數(shù)據(jù)集中,“數(shù)字+字母”和“純字母”占的比重最大,這也反映了國內(nèi)外用戶在密碼設置習慣上的一些差異。從表1中,可以很容易看出,無論是大約1倍的規(guī)模,還是約10倍的規(guī)模,我們的PG-RNN模型生成的新密碼數(shù)據(jù)與原始的訓練密碼集的字符類型結(jié)構(gòu)分布比例都非常地接近,即便是對于占比重非常小的包含特殊字符的類型。
參照文獻[11]中的對比方法,在這一小節(jié)中,我們對PG-RNN模型生成的新密碼數(shù)據(jù)進行了匹配度的評估,也就是新生成密碼與訓練集和測試集的密碼重合個數(shù)。重點對比了我們的方法與文獻[11中的PassGAN模型在Rockyou數(shù)據(jù)集上的效果;同時針對其他幾個數(shù)據(jù)集,我們也給出了PGRNN在測試集上的匹配度結(jié)果以及分析如表2所示。
表 2 CSDN原始密碼集和不同方法生成的新密碼集(x1規(guī)模)在密碼數(shù)最多的長度(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
密碼生成工具都是通過學習現(xiàn)有數(shù)據(jù)集中的數(shù)據(jù)特征來產(chǎn)生新的密碼數(shù)據(jù)集,而新密碼數(shù)據(jù)集與訓練集的匹配度也能夠反映出模型的學習能力。因此,有必要將新生成的密碼數(shù)據(jù)集與訓練數(shù)據(jù)進行對比分析。文中重點對比了PG-RNN模型與文獻[11]在Rockyou密碼數(shù)據(jù)集上的表現(xiàn),具體結(jié)果如表3所示。從表格中可以直觀地看出,隨著生成密碼數(shù)量的增加,新生成密碼能夠與訓練集匹配上的密碼個數(shù)也在增加,這在PGRNN和PassGAN兩個模型上都能夠很好地得到體現(xiàn),這也說明了PG-RNN模型和PassGAN都有著非常強的學習數(shù)據(jù)特征的能力。在匹配度上,隨著生成密碼數(shù)量的增加,本文提出的PGRNN方法與PassGAN相比,在匹配度的優(yōu)勢愈發(fā)明顯;當生成密碼數(shù)量在108時,PG-RNN模型達到了x2.24倍以上的匹配度(由于數(shù)據(jù)切分比例不同,我們的訓練集包含的密碼個數(shù)為9 804 818(無重復),文獻[11]為 9 926 278(無重復))。由于與訓練集匹配上的密碼是已知的,因此這部分密碼完全可以通過基于訓練集的字典攻擊方式而得到。但是,與訓練集的匹配度可以較好地表現(xiàn)出模型的學習能力的。值得一提的是,我們的RNN模型生成密碼的重復率要遠遠小于PassGAN,而在PassGAN模型生成的密碼中,密碼的重復率非常的高,達到80%以上(隨著生成密碼數(shù)增加,甚至大于90%),事實上大量輸出重復的密碼并沒有多大意義,反而會增加密碼生成的時間。
表 3 不同訓練密碼集和規(guī)模約為訓練集1倍、10倍的新生成密碼集在密碼字符結(jié)構(gòu)類型的統(tǒng)計情況Table 3 Character structure categories on training dataset and new generated passwords at the scale of x1, x10 respectively on different datasets
此外,對PG-RNN和PassGAN兩個模型生成的新密碼,在測試集上進行了對比測試。詳細的對比結(jié)果如表4所示。
表 4 PG-RNN與PassGAN各自的生成密碼在Rockyou訓練集上的評估結(jié)果Table 4 The evaluation results between PG-RNN and PassGAN on Rockyou training dataset
其中,第3列和第5列分別表示的是在測試集中匹配上但是沒有出現(xiàn)在訓練集中的密碼個數(shù)(有重復)、在測試集中但不在訓練集中的密碼個數(shù)(無重復)。對比兩個模型的前兩行數(shù)據(jù),可以看出,我們的模型在生成的密碼數(shù)多于PassGAN的情況下,能夠在測試集上匹配上的比例大于后者,這是理所當然的(由于切分比例不同,我們的測試集包含無重復密碼個數(shù)是4 201 550,文獻[11]中是3 094 199,計算比例時是相對于各自的測試集密碼數(shù)而言,這樣比較起來相對公平)。對比兩個模型的第3、4行數(shù)據(jù)結(jié)果,PGRNN在生成密碼數(shù)量上與PassGAN相同的情況下,依然能夠獲得比PassGAN大的在測試集的覆蓋率,甚至超過了1.2%,這進一步說明本文提出的PG-RNN模型是非常具有競爭力的。 需要指出的是,PassGAN使用了復雜的多層殘差卷積神經(jīng)網(wǎng)絡,在網(wǎng)絡模型復雜度和訓練難度上都要遠遠高于PG-RNN模型。
除了Rockyou數(shù)據(jù)集,我們也在表5~6中,列出了我們的模型在其他數(shù)據(jù)集上的測試結(jié)果。從表格中看出,我們的PG-RNN模型針對不同的數(shù)據(jù)集都有較好的效果。此外,可以預見的是隨著生成數(shù)量的進一步增大,能夠匹配上的數(shù)目會進一步增加。而針對PG-RNN模型在Myspace數(shù)據(jù)集上的表現(xiàn)相對于在其他數(shù)據(jù)集表現(xiàn)較差的原因,我們分析主要在于神經(jīng)網(wǎng)絡的訓練是高度依賴于數(shù)據(jù)的,因而對于數(shù)據(jù)量較多的情況能夠?qū)W習到更多的特征,而我們收集到的Myspace數(shù)據(jù)集太小,因此數(shù)據(jù)集體現(xiàn)的統(tǒng)計特征并不明顯,如表6。但是,總的來說,基于遞歸神經(jīng)網(wǎng)絡的模型相對于人為設定規(guī)則和Markov等方法,具備更強的發(fā)掘密碼特征能力。
表 5 對比PG-RNN和PassGAN的生成密碼在Rockyou測試集上的評估結(jié)果Table 5 The evaluation results between PG-RNN and PassGAN on Rockyou test dataset
表 6 PG-RNN在其他密碼數(shù)據(jù)集上的評估結(jié)果Table 6 The evaluation results of PG-RNN on other datasets
本文提出了一種基于遞歸神經(jīng)網(wǎng)絡的密碼猜測模型。在網(wǎng)上公開的泄露密碼數(shù)據(jù)集(包括Rockyou、CSDN、RenRen、Yahoo、Myspace)上對模型進行了一系列的訓練、測試;實驗結(jié)果表明,當在泄露密碼數(shù)據(jù)上訓練后,針對字符級別建模的遞歸神經(jīng)網(wǎng)絡模型提供了一種端到端的密碼生成解決方法,能夠很好地用來生成大量密碼,從而方便破譯出更多潛在密碼。
我們的模型針對不同的數(shù)據(jù)集,以及生成不同密碼規(guī)模情況下,都能夠較好地在密碼結(jié)構(gòu)字符類型,密碼長度分布等特征上接近原始訓練數(shù)據(jù)的。此外,在Rockyou數(shù)據(jù)集上,我們的PG-RNN模型在生成數(shù)據(jù)規(guī)模相當?shù)那闆r下,在測試集中匹配超過11%的密碼個數(shù),相對于PassGAN模型,超過了1.2%。我們的下一步工作主要分為以下兩個方面:1)嘗試其他的RNN網(wǎng)絡結(jié)構(gòu),并分析其在不同的結(jié)構(gòu)在密碼猜測上的效果;2)進一步觀察RNN模型在生成密碼時的內(nèi)部數(shù)據(jù)表示狀態(tài)。