安亞巍,羅 順,朱智慧

(上海通用識別技術研究所,上海 201112)

0 概述

隨著計算機技術和現(xiàn)代密碼學的發(fā)展,加密算法越來越成熟,加密工具越來越普遍,并且隨著人們信息安全意識的普遍提高,口令密碼作為一種應用方便、成本低廉的安全手段被越來越多用戶所接受[1],這給電子取證工作帶來挑戰(zhàn)[2]。越來越多的科研人員關注如何確保加密數(shù)據取證結果的準確性和時效性,而口令破解是電子取證領域主要的研究內容之一。

口令破解的主要方法包括弱口令掃描法、字典破解法、暴力破解法等。其中:弱口令掃描法是指遍歷低位數(shù)或簡單字符空間的口令集;字典破解法是指用英文字典、互聯(lián)網側漏暴庫密碼表等預置密碼口令進行破解嘗試;暴力破解法是指依次試遍所有可能位數(shù)長度的口令字符組合。弱口令掃描法和字典破解法都存在需要進行優(yōu)化以提高口令覆蓋率的問題,暴力破解法受時間和存儲空間限制,對具有一定長度的目標口令往往無能為力。

為提高口令破解效率,現(xiàn)有的研究已提出多種破解加速方法。一類方法是利用GPU[3-6]、FGPA[7]等硬件設備或采用分布式計算環(huán)境[8]提高破解運算速度;另一類是尋找口令空間分布的規(guī)律[9-11],在小幅降低命中率條件下大幅縮小窮舉空間,實現(xiàn)破解效率的提升。

多數(shù)口令的設置都包含了很多人為因素和潛在規(guī)律。如在國內某知名網站泄露的口令中,頻率前五的口令是純數(shù)字口令,頻率前100的口令全部由小寫字符和數(shù)字組成;又如在另一份互聯(lián)網上泄露的密碼表中,其33%的密碼由8個字符組成,19%的密碼由9個字符組成,16%的密碼由6個字符組成,62%的密碼由小寫字母和數(shù)字組成等[12-13]。本文通過一步狀態(tài)轉移概率矩陣迭代得到的馬爾可夫鏈,本質上即為從已破解口令中挖掘出的人們在進行口令設置過程中的某些行為習慣或語言使用特性[14]。

本文從字典和已破解口令中挖掘規(guī)律,提出一種基于馬爾可夫鏈的口令破解算法。通過對字典或已破解口令的統(tǒng)計分析,實現(xiàn)口令字符一步狀態(tài)轉移概率的動態(tài)估計,并得到下一位口令字符的遍歷空間和遍歷順序。

1 馬爾可夫模型

假設一個狀態(tài)離散的隨機變量{Xn|n=0,1,…}有m種狀態(tài)值{s0,s1,…,sm|m≤n},若變量X在某一時刻Xi處于狀態(tài)sji(0≤ji≤m)的概率只與其在前一時刻Xi-1的狀態(tài)sji-1有關,即:

P(Xi=sji|Xi-1=sji-1,Xi-2=sji-2,…,X0=sj0)=

P(Xi=sji|Xi-1=sji-1)

則稱變量X具有馬爾可夫性,變量X的隨機過程{Xn|n=0,1,…}為馬爾可夫鏈[15]。相應地,在系統(tǒng)變量中具有馬爾可夫性的模型被稱為馬爾可夫模型(Markov Model,MM)。

馬爾可夫性的直觀含義是在已知現(xiàn)在狀態(tài)條件下,過去與將來相互獨立。即如果用已知的、到現(xiàn)在為止的所有信息來預測將來,則將來只與現(xiàn)在有關,而與過去無關[16-17]。

若令具有馬爾可夫性的變量X在時刻k處于狀態(tài)si,在時刻k+1處于狀態(tài)sj的概率為pij,則一步狀態(tài)轉移概率矩陣表示為:

(pk+1(s0),pk+1(s1),…,pk+1(sm))=

(pk(s0),pk(s1),…,pk(sm))P

其中,pk(si)表示變量X在時刻k處于狀態(tài)si的概率。若令v(k)=(pk(s0),pk(s1),…,pk(sm))為時刻k的狀態(tài)概率分布,即有:

v(k+1)=v(k)P

從而可以得到變量X在任意時刻k的狀態(tài)概率分布為:

v(k)=v(0)Pk

其中,v(0)為變量X的初始狀態(tài)概率分布,v(0)經過與一步狀態(tài)轉移概率矩陣P的k次迭代得到v(0)Pk,其即為變量X轉移k步后的狀態(tài)概率分布預測。

2 基于樣本估計的馬爾可夫鏈

2.1 口令字符的空間截斷

根據Shannon信息理論,熵是用來度量隨機變量的不確定性。一個離散隨機變量X,其值域記為Sx,對Sx中狀態(tài)值s∈Sx,其概率分布函數(shù)為ps(x),則變量X的熵為:

對每一個口令字符進行基于樣本的統(tǒng)計,并用頻率f(α)給出概率p(α)的近似估計。其中,α表示口令字符,f(α)表示在樣本字典或已破解口令中字符α的出現(xiàn)頻率,p(α)表示在設置口令時用到字符α的概率。由此得到字典或已破解口令中口令的信息熵為:

Algoritmy網站列出英文字母的出現(xiàn)頻率如表1所示。

表1 Algoritmy網站英文字母出現(xiàn)頻率 %

計算得出英文語言的信息熵為4.176,即英文所傳達的信息大概只使用了24.176≈18個字符。在英文字母中出現(xiàn)頻率最高的18位字母,占全部小寫字母的69.23%,覆蓋了94.36%的字母出現(xiàn)頻率。

對暴力破解來說,將口令字符在高頻的18位字符處作截斷,意味著若暴力的口令空間為8位小寫字符,運算量即從268減少到188,僅相當于原運算量的5.28%。

在實際破解工作中,口令字符的狀態(tài)空間為95個可打印字符,包括大小寫英文字母、數(shù)字、標點符號。通過信息熵的計算來進行口令字符的空間截斷,其運算縮減量比單純英文小寫字母效果更顯著。若仍以8位長度口令為例,對某密碼表的統(tǒng)計計算得到其信息熵為5.70,則其有效字符為52位,截斷后其計算量僅相當于原運算量的0.81%。

2.2 一步狀態(tài)轉移概率估計

使用馬爾可夫鏈進行口令破解的關鍵是對口令字符一步狀態(tài)轉移概率的估計。本文通過統(tǒng)計字典或已破解口令中,口令字符在當前各種狀態(tài)值的情況下向下一刻各種狀態(tài)值轉移的頻率,來對一步狀態(tài)轉移概率進行估計。

對統(tǒng)計字典或已破解口令中所有二元字符進行組合,將其前一位字符看成是當前字符狀態(tài)值,后一位字符看成是下一刻字符轉移狀態(tài)值,即可通過統(tǒng)計所有二元字符組合的字符間跟隨關系得到一步狀態(tài)轉移概率矩陣的估計,表示如下:

其中,fαβ為字典或已破解口令中二元字符組合αβ的頻率,即是口令字符從狀態(tài)值α一步轉移到β的頻率,α、β為可打印字符。

2.3 馬爾可夫鏈的生成

采用第2.1節(jié)方法對口令字符空間進行截斷。設經過截斷后口令字符的狀態(tài)空間從95個可打印字符縮減到m+1位,記為{α0,α1,…,αm}。然后得到口令字符一步狀態(tài)轉移概率矩陣的估計P=(pij)(m+1)×(m+1)。

對矩陣P中每一個行向量(pi0,pi1,…,pim),i=0,1,…,m進行降序排列,記排序結果為(pij0,pij1,…,pijm),pij0≥pij1≥…≥pijm,其中,{j0,j1,…,jm}為{0,1,…,m}的一個排列。即在根據口令字符一步狀態(tài)轉移概率矩陣得到當前口令字符為αi的情況下,下一位口令字符按可能性從高至低依次為αj0,αj1,…,αjm。

針對字典或已破解口令的馬爾可夫鏈如圖1所示。

圖1 字典或已破解口令的馬爾可夫鏈

從而得到下一位口令字符的遍歷空間{αj0,αj1,…,αjm}和遍歷順序{j0,j1,…,jm}。

2.4 轉移矩陣計算

轉移矩陣P有實時和延時2種計算方式。實時計算是指每獲得一條口令即進行一次口令空間字符截斷計算,同時更新轉移矩陣P。實時計算轉移矩陣增加了大量的計算開銷,而帶來的破解性能提升卻有限,特別是當口令庫規(guī)模較大時,入庫一條或兩條新口令,對口令空間和轉移矩陣P的影響是非常微弱的。

延時計算是指當入庫的新口令達到一定量時(如原口令庫的5%),或者口令字符的頻次出現(xiàn)較大變化時(如某一字符新增頻次超過5%),再進行一次口令空間字符截斷計算和轉移矩陣更新計算。由于延時計算是一次性計算,并且只有當口令庫出現(xiàn)較大增量的情況下才會觸發(fā),因此,相比于大量的解密運算,延時計算新增加的工作量微乎其微,并極大地保留了算法對破解性能的提升。

3 算法描述

基于馬爾可夫鏈的口令破解算法步驟如下:

步驟1統(tǒng)計字典或已破解口令中口令字符的分布。

步驟2根據信息熵方法,確定口令空間的截斷,得到口令空間的近似。

步驟3統(tǒng)計字典或已破解口令中所有二元字符組合,根據二元字符的跟隨分布,得到口令字符一步狀態(tài)轉移概率矩陣P的估計。

步驟4根據口令字符一步狀態(tài)轉移概率矩陣P構建馬爾可夫鏈。

步驟5根據馬爾可夫鏈,對當前口令字符αi的下一位口令字符,做出遍歷空間{αj0,αj1,…,αjm}和遍歷順序{j0,j1,…,jm}的估計。

步驟6根據當前口令長度設置,對初始口令字符α0,按步驟5中方法逐位估計口令空間和順序,并對口令字符進行遍歷。

步驟7若步驟6中得到正確口令,則退出,否則更改初始口令字符α0為α1。

步驟8若步驟7中得到正確口令,則退出,否則更改當前口令長度設置,并回到步驟6,若口令長度超限,則退出。

4 測試算例

為驗證基于馬爾可夫鏈的口令破解算法的有效性,從網上泄漏的真實用戶口令中隨機抽取100萬條作為破解目標設計測試算例。算例以MD5算法為例,采用2塊AMD Radeon R9 GPU作為計算設備,對比基于馬爾可夫鏈的破解方式和普通暴力破解方式的破解效率。

以某開源口令破解工具附帶密碼表為字典,計算口令字符一步狀態(tài)轉移概率矩陣P。該密碼表共有3 399 474條口令,長度從1位到35位,其中長度8位的口令有446 739條。以長度8位的口令為樣本,統(tǒng)計得到字符分布如表2所示。

表2 某密碼表8位口令樣本字符分布 %

計算得密碼表中口令的信息熵為4.75,從而將口令空間截斷為24.75≈29位。也可以根據破解需求進一步放寬對口令空間的截斷,如在前30位口令字符處進行截斷,即{e,a,i,s,o,n,r,t,u,l,k,d,m,c,h,g,p,b,y,v,f,,-,.,′,z,w,j,A,S},其口令字符一步狀態(tài)轉移概率矩陣P為:

設定猜測長度為7位～8位,按前30位字符截斷,計算得口令猜測空間為6 779億條。采用基于馬爾可夫鏈算法破解,記錄實際耗時118 s,成功破解246 238條口令。采用普通暴力破解方式,記錄實際耗時117 s,成功破解31條口令。破解測試結果如表3所示。

表3 2種破解方式的測試結果

從表3可以看出,兩者比較效果明顯,基于馬爾可夫鏈的破解方式能優(yōu)先遍歷更高可能性的字符組合,對口令破解尤其是需要超長破解時間的長口令破解有顯著的效果提升。

5 結束語

人們在設置口令過程中的某些行為習慣或語言特性可以用馬爾可夫鏈進行描述。本文提出的基于馬爾可夫鏈的口令破解算法,能夠充分利用字典或已破解口令中字符分布、組合分布等特征來提升破解性能。相比暴力破解等傳統(tǒng)方法,本文算法具有以下優(yōu)勢:將口令設置的潛在社會工程學特征(人們在設置口令時的某些行為習慣或語言使用特性)量化為口令空間截斷和狀態(tài)轉移矩陣,使破解過程指向更有可能性的口令并使計算資源使用更高效;馬爾可夫鏈的使用有效縮小了破解空間,并加速了符合社會工程學規(guī)律的口令破解,在同等計算資源條件下,能使口令盡可能快和集中地被破解出來。下一步將繼續(xù)研究口令中某一字符和與其關聯(lián)緊密的前兩位字符之間關聯(lián)規(guī)律的二階馬爾可夫模型,挖掘實際口令設置規(guī)律,以提高口令破解的準確性。