PCFG口令猜测算法实现

  PCFG是一种完全自动的、建立在严密的概率上下文无关法基础之上的漫步口令猜测算法，该算法的核心思想是将每一条口令看作是由字母段L、数字段D、特殊字符段S根据一定的模式互相组合而成的。我们可以通过对大量的口令数据进行分析，统计出这些口令可能的组合模式，从而利用该模式生成更多的口令，进行口令猜测。

实现细节

  该算法的实现主要包括三个部分：口令集预处理、口令集训练、口令猜测，使用的编程语言为python3.7，具体细节如下所示：

• 口令集预处理：实验中所使用的口令集为MySpace，去掉了包含非ASCLL或者空格的口令，剩余口令总数为41251。然后将这些口令随机拆分为训练集和测试集，分别存放在trainword.txt和testword.txt文件中。代码中设置了参数eps可以对训练集和测试集的分配比例进行调节，本文将eps设置为0.4，即测试集占口令总数的40%（16500）。除此之外，在随机拆分训练集和测试集时，设置了随机种子seed，方便实验结果的复现。
• 口令集训练：口令集训练的目的是统计出口令模式频率和字符组件频率。对于字符组件频率的统计，论文中提到的方法只统计了数字段和D和特殊S。在实现过程中，我也统计了字母段L的频率，同时字母段L将作为字典参与口令猜测过程。（根据测试集生成的口令模式一共有1134种）
• 口令猜测：口令猜测的过程类似于树的遍历，这里采用类似于深度优先遍历的方法。分别对所有的口令模式频率表和字符组件频率表由大到小进行排序，从频率最高的口令模式开始进行口令猜测，根据字符组件频率表依次生成该模式下所有可能的口令，然后在进行下一个口令模式的猜测。对于每个生成的口令，需要计算其可能出现的概率，如果该概率值大于预设的阈值（比如0.000000001），则可以将其输出并与测试集中的口令进行比对。反之，则将该口令丢弃。实验中所有的猜测口令都存放在guess文件夹下对应的口令模式文件中。

  按照上述实验设置进行了实验，具体代码参考我的GitHub。在代码刚开始运行阶段，正确猜解口令的速度很快。两分钟的时间内大概能够正确猜解6000多个口令，之后正确猜解的速度逐渐降低。由于⽣成口令时我们设置了阈值，只有超过该阈值的口令才会进⾏匹配，所以真正参与口令猜测的 口令数量要远远小于实际⽣成的口令数量，上图横坐标展⽰的就是参与口令猜测的口令数量。这⾥展⽰ 的结果是利⽤口令模式表中前400种左右的模式⽣成的口令，正确猜解的口令数量为6529（总共 16500）

Markov口令猜测算法实现

  ⼀般情况下，⽤⼾构造口令的顺序是从前向后依次进⾏的。根据这⼀特点，Narayanan等⼈在 2005年⾸次将Markov链技术引⼊口令猜测中来。与PCFG算法不同，基于Markov模型的口令猜测算法 对整个口令进⾏训练，通过从左到右的字符之间的联系来计算口令的概率。该算法也分为训练和猜测集 ⽣成两个阶段，以下介绍实现细节。（针对此前代码存在的问题，本次代码进⾏了相应的修改。对于 start symbol问题，已经充分理解并实现；对于阈值问题，优化了阈值的分配⽅式。综合来看，实验效果得到了很⼤的提升）

实现细节

  该算法的实现主要包括三个部分：口令集预处理、口令集训练、口令猜测，使⽤的编程语⾔为 python3.7，具体细节如下所⽰：

• 口令集预处理：实验中所使⽤的口令集为Rockyou，去掉了包含⾮ASCLL或者空格的口令，剩余口 令总数为32460357。由于口令总数很⼤，这⾥我没有使⽤全部的口令进⾏训练和测试。我从数据 集中随机选择了2000000条口令，然后将这些口令拆分为训练集和测试集（各占50%）。代码中设 置了number参数，可以选择使⽤数据的量。除此之外，在随机选择数据时，设置了随机种⼦seed，⽅便实验结果的复现。
• 口令集训练：口令集训练的⽬的是统计出各个字串在训练集中出现的频数。统计频数时，对于口令 开头字⺟出现的频率单独进⾏统计，其余字串的频数均存放在⼀个字典中。我使⽤了End-Symbol 正规化技术，频数统计时也会对口令结束标志符号进⾏统计。频数统计完成之后，利⽤Laplace平 滑技术来计算概率，然后对每个字串后⾯出现的字⺟依据概率值⼤小进⾏排序。
• 口令集猜测：这⾥使⽤优先队列的思想来对猜测口令进⾏存储和遍历，如果当前队列前端的字符串 最后⼀个字符为口令结束标识符，则将其输出进⾏口令猜解，否则根据其字串在概率表中的统计情 况，在该字符串后继续添加字符并计算概率，然后插⼊队列。为了减少队列对内存的损耗，再将每 ⼀个字符串插⼊队列之前，要对其概率值进⾏判断。只有当其概率值⼤于预设阈值时，才准许插⼊队列。

  按照上述实验设置进⾏了实验，具体代码参考我的GitHub。由于实验机器性能有限，这⾥使⽤的测试集口令总数为 1000000，猜测次数为1000000，order=3,4,5。order=3时，猜测出的口令数⽬为279517；order=4时，猜测出的口令数⽬为378980；order=5时，猜测出的口令数 ⽬为414806。