《2014 A Study of Probabilistic Password Models- --IEEE S&P 2014 Ma jery 》
根据论文可知,该算法的实现流程大致如下:
所有步骤均使用C++实现
将数据集分为训练集和测试集,并且去除其中含有空格和一些特殊符号(不可显示的)的密码 又因为字典字符全为小写,故依据论文不考虑大小写,将训练集和测试集中的字符部分全部化为小写
首先将训练集中的密码处理为Base结构(例如:@password1 -> S1L8D1)并计算每种Base结构出现的概率(通过stl中的map实现) 然后统计出特殊符号和数字的概率(如D1可以是0,1,2,3,4,5,6,7,8,9,通过训练集计算分别出他们的概率),这同样可以通过map实现。 从而可以得到口令猜测中的变量替换规则:PCFG
采用了优先队列,结构体包含如下三个项目:1.index value(即这个预终端结构处理到哪个部分如L3D2S1,L3索引为0,D2,索引为1,S1索引为2)2.pivot value(用于指示预终端结构生成中的替换范围,比如若pivot值为2,则只能替换这个预终端结构中索引值大于2的部分)3.该预终端结构/基础结构的概率 每次取优先队列队首,然后将可替换部分依据PCFG进行替换,再将替换后的预终端结构存入优先队列
优先队列排序依据:概率 > pivot value
由预终端结构到终端结构为填充单词部分,有两种方法:
先选择概率最高的预终端结构,然后根据预终端结构的字符部分的长度替换单词(例如:!L3123,字典中长度为3的单词有hat cat、则终端结构为!hat123、!cat123),然后再选择概率第二高的预终端结构(直接排序处理即可)3.该预终端结构出现的概率。4.预终端结构 这个要通过dfs实现!
根据字典中各长度的单词数量分配概率,从而计算终端结构的概率
实验中用于训练和测试的数据下载自网站,选用myspace。
在网站上下载的文件为带有各个密码出现次数的密码文件,所以我通过c++程序将其变成单一密码形式。 如: 2 password -> password password 然后再将得到的密码随机分为Train set 和 Test set
目前问题: 1.如何将生成的文法 在猜测时用代码实现变量替换(解决,类似链表的思路) 2.如何最后导入词典并利用词典生成终端结构即破解密码(2014的论文中似乎不导入外部词典,要使用 n-gram markov 来进行L部分的变量替换)(解决) 3.2014的方法对2009方法中的具体改进之处(似乎是L部分采用markov) 4.最后猜测生成后如何与测试集比对(采用set) 5.如何将结果展示(先生成大约3e7个guess然后由于先生成的口令概率最大,故可以从头至尾与test集比对统计成功率即可,然后将结果导入Excel生成图像)
实验中的问题: 1.论文中说删去非ASCLL以及含空格的口令后剩余口令数目为60k+,但是我本地操作后剩余为41260(但是训练样本和实验样本数目比例仍然设置为3:2),也因此base struct 数目与论文中不一致 2.论文中的实验集与测试集均比我使用的大,所以导致其破解能力下降