这篇是对于论文的总结和个人的一些观点，关于代码部分请看下一篇：

有什么问题和疑惑欢迎讨论，一起研究口令破解的技术。

文章主要讲了两个技术，基于模板的破解（PCFG这个在上篇中有讲）和基于字符串的破解（就是本篇重点markov）。

使用的口令集有6个，3个来自美国，3个来自中国，总共6kw。

markov 模型：

首先介绍markov链，一个d阶markov链（即d+1 ngram模型）对应概率公式：

可以看到每个字符由前面d个字符决定。
例如1阶markov模型：

C0可以视为起始字符

概率由统计次数来获取。

标准化

1直接标准化

假设口令长度分布均匀，文中描述的是训练使用的口令长度在L到U之间，所以所有值除以(U-L+1)
但是口令长度分布肯定是不同的，这个方法效果不好。

2按照长度分布标准化

但是不同口令集长度分布不同，这个方法效果应该也不好。

3结束字符标准化

对训练口令和测试口令都添加一个结束字符。之所以使用这个标准化是由于部分片段口令的概率反而比完整口令大，例如passwor概率比password大，因为d的概率<=1。添加结束字符之后，片段化口令对应结束字符的概率就会非常小。

模型细节

1 模型的阶数

阶数越大的模型越能探索更多的信息，但是容易过拟合和稀疏。
这里的稀疏指计算概率时使用的次数可能会非常小，会变得noisy？？这里没懂。

2 平滑方法

由于高阶模型计算的情况，一些口令可能会被赋值概率为0，因此需要使用平滑技术来避免。

（1）Additive smoothing（拉普拉斯平滑）

即在计算概率时，分子上加一个值，文中是0.01（因为总字符有95个，1/95就是接近0.01）
同理分母要加上总值，保证概率和为1.

（2） Good-Turing smoothing（图灵平滑）

这里论文中写了该平滑的用处，具体使用没有详细介绍。不过依然可以在网上找到：
常用的平滑技术

3 分组

grouping也是用于处理稀疏性的一种方法，主要目的是减小字符集大小，将大写字符和特殊字符用两个符号分别代替，这样对于2阶模型的概率公式，举个例子。
P[“aF?b”] ：

但是如果仔细想一下会发现，大写字符也是要区分考虑的，例如swor后D的概率会大于Q，因此公式需要进行变化：

a代表所有大写字符 w代表所有特殊字符。

4 backoff技术

在预测下一个字符时，如何使用之前的片段也是有讲究的。例如对于片段passwor，用全部的片段预测或许不如用wor来预测。
这里的backoff技术就是找到一个最短的片段来预测下一个字符。
backoff会设置一个阈值，用于过滤那些出现次数较低的片段。
对于序列c0c1…cl-1，预测下一个字符cl。不会直接使用c0c1…cl-1来预测，而是选择cici+1…cl-1来预测，这里i要求尽可能的小，当cici+1…cl-1的count大于阈值即可。
但是还有可能cici+1…cl的次数为0，这样新生成的片段概率就为0了，这样就要继续增大i的值，直到找到满足要求的前缀片段。
bakcoff会远远慢与markov。

5 口令生成

方法1：优先队列保存

将口令片段和对应概率封装到一个结构（文中是node）然后放入优先队列中，每次弹出概率最高的一项，判断是否生成结束，如果没结束就添加所有可能的下一个字符再次放入队列（需要满足要求的项，例如概率和长度等），否则直接输出。
这个好处是保证生成的口令完全是按照概率降序的，缺点是占据大量内存，论文中说如果生成口令数目在50w一下可以考虑。

方法2：概率阈值搜索

作者的思路大致是先设置一个阈值，进行一次DFS将大于阈值的生成，如果生成数目不够就减小阈值，然后再次DFS，依次往复，最后生成足够数目的口令，再排序。
个人观点是不如先开始就把概率阈值设置稍微小一点，生成超出预期的口令再排序剔除，这样全程也只用遍历一次，同时避免了重复口令生成。

PCFG模型

这个模型我已经在之前的博客讲解了，论文是09年weir的，具体可以看：
2009PCFG
这里就对PCFG简单的介绍。

这篇论文里面作者对PCFG进行了改进，但是大体思想没变，都是按照片段划分后，分片段记录概率值：

这里作者改进的一点就是将大小写区分开来，设置为两种片段。改进的第二点就是增加了一个模型，字母片段也从训练中获取的字典来填充。

实验部分

使用了6个数据集 rockyou phpbb yahoo 178 csdn duduniu
将这6个数据集合并为整体大数据集，进行清洗，清洗掉包含不可打印字符的口令，长度小于4或者大于40的口令。
作者还统计了一下unique的口令，总体为40%，并且发现越小的口令集，含有unique的口令占比越高。
作者将不同口令集进行搭配，用于训练和测试：

下面是一些比较重要的实验结果图片：
首选是在如下搭配的结果：

注意ws-mc5-end表示5阶markov，添加起始和结束字符。
ws-mc5-b10-end表示5阶markov使用backoff，对应阈值为10，添加起始和结束字符。

关于markov的代码实现将在另一个博客中展示：