安亚巍,罗 顺,朱智慧

(上海通用识别技术研究所,上海 201112)

0 概述

随着计算机技术和现代密码学的发展,加密算法越来越成熟,加密工具越来越普遍,并且随着人们信息安全意识的普遍提高,口令密码作为一种应用方便、成本低廉的安全手段被越来越多用户所接受[1],这给电子取证工作带来挑战[2]。越来越多的科研人员关注如何确保加密数据取证结果的准确性和时效性,而口令破解是电子取证领域主要的研究内容之一。

口令破解的主要方法包括弱口令扫描法、字典破解法、暴力破解法等。其中:弱口令扫描法是指遍历低位数或简单字符空间的口令集;字典破解法是指用英文字典、互联网侧漏暴库密码表等预置密码口令进行破解尝试;暴力破解法是指依次试遍所有可能位数长度的口令字符组合。弱口令扫描法和字典破解法都存在需要进行优化以提高口令覆盖率的问题,暴力破解法受时间和存储空间限制,对具有一定长度的目标口令往往无能为力。

为提高口令破解效率,现有的研究已提出多种破解加速方法。一类方法是利用GPU[3-6]、FGPA[7]等硬件设备或采用分布式计算环境[8]提高破解运算速度;另一类是寻找口令空间分布的规律[9-11],在小幅降低命中率条件下大幅缩小穷举空间,实现破解效率的提升。

多数口令的设置都包含了很多人为因素和潜在规律。如在国内某知名网站泄露的口令中,频率前五的口令是纯数字口令,频率前100的口令全部由小写字符和数字组成;又如在另一份互联网上泄露的密码表中,其33%的密码由8个字符组成,19%的密码由9个字符组成,16%的密码由6个字符组成,62%的密码由小写字母和数字组成等[12-13]。本文通过一步状态转移概率矩阵迭代得到的马尔可夫链,本质上即为从已破解口令中挖掘出的人们在进行口令设置过程中的某些行为习惯或语言使用特性[14]。

本文从字典和已破解口令中挖掘规律,提出一种基于马尔可夫链的口令破解算法。通过对字典或已破解口令的统计分析,实现口令字符一步状态转移概率的动态估计,并得到下一位口令字符的遍历空间和遍历顺序。

1 马尔可夫模型

假设一个状态离散的随机变量{Xn|n=0,1,…}有m种状态值{s0,s1,…,sm|m≤n},若变量X在某一时刻Xi处于状态sji(0≤ji≤m)的概率只与其在前一时刻Xi-1的状态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]。相应地,在系统变量中具有马尔可夫性的模型被称为马尔可夫模型(Markov Model,MM)。

马尔可夫性的直观含义是在已知现在状态条件下,过去与将来相互独立。即如果用已知的、到现在为止的所有信息来预测将来,则将来只与现在有关,而与过去无关[16-17]。

若令具有马尔可夫性的变量X在时刻k处于状态si,在时刻k+1处于状态sj的概率为pij,则一步状态转移概率矩阵表示为:

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

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

其中,pk(si)表示变量X在时刻k处于状态si的概率。若令v(k)=(pk(s0),pk(s1),…,pk(sm))为时刻k的状态概率分布,即有:

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

从而可以得到变量X在任意时刻k的状态概率分布为:

v(k)=v(0)Pk

其中,v(0)为变量X的初始状态概率分布,v(0)经过与一步状态转移概率矩阵P的k次迭代得到v(0)Pk,其即为变量X转移k步后的状态概率分布预测。

2 基于样本估计的马尔可夫链

2.1 口令字符的空间截断

根据Shannon信息理论,熵是用来度量随机变量的不确定性。一个离散随机变量X,其值域记为Sx,对Sx中状态值s∈Sx,其概率分布函数为ps(x),则变量X的熵为:

对每一个口令字符进行基于样本的统计,并用频率f(α)给出概率p(α)的近似估计。其中,α表示口令字符,f(α)表示在样本字典或已破解口令中字符α的出现频率,p(α)表示在设置口令时用到字符α的概率。由此得到字典或已破解口令中口令的信息熵为:

Algoritmy网站列出英文字母的出现频率如表1所示。

表1 Algoritmy网站英文字母出现频率 %

计算得出英文语言的信息熵为4.176,即英文所传达的信息大概只使用了24.176≈18个字符。在英文字母中出现频率最高的18位字母,占全部小写字母的69.23%,覆盖了94.36%的字母出现频率。

对暴力破解来说,将口令字符在高频的18位字符处作截断,意味着若暴力的口令空间为8位小写字符,运算量即从268减少到188,仅相当于原运算量的5.28%。

在实际破解工作中,口令字符的状态空间为95个可打印字符,包括大小写英文字母、数字、标点符号。通过信息熵的计算来进行口令字符的空间截断,其运算缩减量比单纯英文小写字母效果更显著。若仍以8位长度口令为例,对某密码表的统计计算得到其信息熵为5.70,则其有效字符为52位,截断后其计算量仅相当于原运算量的0.81%。

2.2 一步状态转移概率估计

使用马尔可夫链进行口令破解的关键是对口令字符一步状态转移概率的估计。本文通过统计字典或已破解口令中,口令字符在当前各种状态值的情况下向下一刻各种状态值转移的频率,来对一步状态转移概率进行估计。

对统计字典或已破解口令中所有二元字符进行组合,将其前一位字符看成是当前字符状态值,后一位字符看成是下一刻字符转移状态值,即可通过统计所有二元字符组合的字符间跟随关系得到一步状态转移概率矩阵的估计,表示如下:

其中,fαβ为字典或已破解口令中二元字符组合αβ的频率,即是口令字符从状态值α一步转移到β的频率,α、β为可打印字符。

2.3 马尔可夫链的生成

采用第2.1节方法对口令字符空间进行截断。设经过截断后口令字符的状态空间从95个可打印字符缩减到m+1位,记为{α0,α1,…,αm}。然后得到口令字符一步状态转移概率矩阵的估计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}的一个排列。即在根据口令字符一步状态转移概率矩阵得到当前口令字符为αi的情况下,下一位口令字符按可能性从高至低依次为αj0,αj1,…,αjm。

针对字典或已破解口令的马尔可夫链如图1所示。

图1 字典或已破解口令的马尔可夫链

从而得到下一位口令字符的遍历空间{αj0,αj1,…,αjm}和遍历顺序{j0,j1,…,jm}。

2.4 转移矩阵计算

转移矩阵P有实时和延时2种计算方式。实时计算是指每获得一条口令即进行一次口令空间字符截断计算,同时更新转移矩阵P。实时计算转移矩阵增加了大量的计算开销,而带来的破解性能提升却有限,特别是当口令库规模较大时,入库一条或两条新口令,对口令空间和转移矩阵P的影响是非常微弱的。

延时计算是指当入库的新口令达到一定量时(如原口令库的5%),或者口令字符的频次出现较大变化时(如某一字符新增频次超过5%),再进行一次口令空间字符截断计算和转移矩阵更新计算。由于延时计算是一次性计算,并且只有当口令库出现较大增量的情况下才会触发,因此,相比于大量的解密运算,延时计算新增加的工作量微乎其微,并极大地保留了算法对破解性能的提升。

3 算法描述

基于马尔可夫链的口令破解算法步骤如下:

步骤1统计字典或已破解口令中口令字符的分布。

步骤2根据信息熵方法,确定口令空间的截断,得到口令空间的近似。

步骤3统计字典或已破解口令中所有二元字符组合,根据二元字符的跟随分布,得到口令字符一步状态转移概率矩阵P的估计。

步骤4根据口令字符一步状态转移概率矩阵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作为计算设备,对比基于马尔可夫链的破解方式和普通暴力破解方式的破解效率。

以某开源口令破解工具附带密码表为字典,计算口令字符一步状态转移概率矩阵P。该密码表共有3 399 474条口令,长度从1位到35位,其中长度8位的口令有446 739条。以长度8位的口令为样本,统计得到字符分布如表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},其口令字符一步状态转移概率矩阵P为:

设定猜测长度为7位～8位,按前30位字符截断,计算得口令猜测空间为6 779亿条。采用基于马尔可夫链算法破解,记录实际耗时118 s,成功破解246 238条口令。采用普通暴力破解方式,记录实际耗时117 s,成功破解31条口令。破解测试结果如表3所示。

表3 2种破解方式的测试结果

从表3可以看出,两者比较效果明显,基于马尔可夫链的破解方式能优先遍历更高可能性的字符组合,对口令破解尤其是需要超长破解时间的长口令破解有显著的效果提升。

5 结束语

人们在设置口令过程中的某些行为习惯或语言特性可以用马尔可夫链进行描述。本文提出的基于马尔可夫链的口令破解算法,能够充分利用字典或已破解口令中字符分布、组合分布等特征来提升破解性能。相比暴力破解等传统方法,本文算法具有以下优势:将口令设置的潜在社会工程学特征(人们在设置口令时的某些行为习惯或语言使用特性)量化为口令空间截断和状态转移矩阵,使破解过程指向更有可能性的口令并使计算资源使用更高效;马尔可夫链的使用有效缩小了破解空间,并加速了符合社会工程学规律的口令破解,在同等计算资源条件下,能使口令尽可能快和集中地被破解出来。下一步将继续研究口令中某一字符和与其关联紧密的前两位字符之间关联规律的二阶马尔可夫模型,挖掘实际口令设置规律,以提高口令破解的准确性。