摘 要

作为身份认证的重要手段，文本口令因为其方便部署、使用简单等特点一直是互联网中被广泛使用的认证方式。近年来，由于知名互联网应用程序数据泄露的频繁发生，文本口令显得极为不安全。与此同时，用户薄弱的口令安全意识和不断完善的口令攻击模型使得保障口令安全面临着巨大的挑战。基于保护互联网口令认证系统的安全，本文调研了国内外众多知名网站的口令生成策略，发现这些策略已经难以应对趋于自动化的口令猜测攻击。所谓“知己知彼，百战不殆”，本文试图从研究口令攻击模型来减少弱口令的出现，从而使口令认证系统的安全性提高。

针对以上问题，本文在研究和总结前人工作的基础上，完成如下工作：

1. 大规模口令脆弱性分析。本文分析大规模真实数据集，提出了群组的概念，根据服务网站的用户语言将大规模口令数据集进行群组划分：中文组和英文组，统计了两组网站的口令数据集特征，包括流行口令，口令字符组成结构、口令长度分布以及口令中字母和数字的频率分布，发现两组数据集在这些特征方面具有较大差异；
2. 提出一种改进的基于PCFG和Markov模型的口令猜测算法。该算法通过综合两类模型（PCFG和Markov）优点，从子结构组成层面和字符前后依赖层面对口令进行训练猜测，使得口令破解效率得到提高，最后实验验证了该算法的有效性；
3. 设计并进行了各模型的破解效率实验。该实验分析比较了PCFG算法、Markov算法及改进算法的优缺点，并通过对真实数据集的训练与测试提供了各算法的破解效率曲线图，从原理本质层面揭示了各模型的缺陷原因，同时分析了一些可能的优化方向；

关键词：口令安全；口令破解；口令分析；PCFG模型；Markov模型；

Abstract

As an important means of identity authentication, text passwords have been widely used as an authentication method on the Internet because of their convenient deployment and simple use. In recent years, due to the frequent occurrence of data leakage of well-known Internet applications, text passwords have become extremely insecure. At the same time, users' weak password security awareness and the continuous improvement of password attack models make it a huge challenge to ensure password security. Based on protecting the security of the Internet password authentication system, this article investigate the password generation strategies of many well-known websites at home and abroad, and find that these strategies have been difficult to respond to automated password attacks. The so-called "Know Yourself, Know Your Others, Fight forever", this article try to improve the strength of weak passwords by studying the password attack model, thereby improving the security of the password authentication system.

To solve these problems, this paper summarizes the basic research and previous work on the completion of the following work:

1. Large-scale password vulnerability analysis. This paper analyzes large-scale real data sets, and proposes the concept of grouping. According to the user language of the service website, the large-scale password data set is divided into groups: Chinese group and English group. Popular passwords, the structure of password characters, the distribution of password length, and the frequency distribution of letters and numbers in passwords have found that the two sets of data sets have significant differences in these characteristics;
2. An improved password guessing algorithm based on PCFG and Markov model is proposed. The algorithm combines the advantages of two types of models (PCFG and Markov) to train and guess the password from the substructure composition level and the character dependency level, so that the password cracking efficiency is improved. Finally, the experiment verifies the effectiveness of the algorithm;
3. The cracking efficiency experiment of each model is designed and carried out. This experiment analyzes and compares the advantages and disadvantages of the PCFG algorithm, Markov algorithm and improved algorithm, and provides the cracking efficiency curve of each algorithm through training and testing of real data sets, revealing the causes of defects of each model from the level of principle essence. Some possible optimization directions are analyzed;

Keywords: Password security; password cracking; password analysis; PCFG model; Markov model;

目 录

摘 要 I

Abstract II

第1章 绪论 1

1.1研究背景与意义 1

1.2国内外研究现状 1

1.2.1口令破解研究现状 2

1.2.2口令强度评估研究现状 2

1.3本文研究内容 3

1.4本文组织结构 3

1.5本章小结 4

第2章 大规模口令数据分析 5

2.1 口令生成策略 5

2.2群组的定义 6

2.3口令数据集 6

2.4基于群组的口令集特征分析 6

2.4.1流行口令 6

2.4.2长度分布 8

2.4.3口令结构 9

2.4.4 字母和数字频率 10

2.5本章小结 11

第3章 基于概率语言模型的口令猜测算法设计 13

3.1 经典口令概率模型 13

3.1.1 概率上下文无关文法（PCFG）模型 13

3.1.2 马尔科夫（Markov）模型 13

3.2基于PCFG和Markov模型的口令猜测算法 14

3.2.1 口令集训练阶段算法设计 15

3.2.2 口令集猜测阶段算法设计 17

3.3 本章小结 18

第4章 基于概率语言模型的口令攻击实验 20

4.1 实验准备 20

4.1.1实验环境 20

4.1.2数据来源 20

4.1.3模型和数据集 20

4.1.4评价指标 20

4.2 基于概率语言模型的口令攻击 21

4.3模型分析 25

4.4本章小结 26

第5章 总结与展望 27

5.1全文总结 27

5.2下一步工作 27

参考文献 28

致 谢 30

第1章 绪论

1.1研究背景与意义

随着信息技术的快速发展与变革，互联网应用的广泛普及为人类的学习、工作和生活带来了极大的便利。近年来以移动互联网和电子商务等为代表的信息技术的发展，使人们的资产变得越来越数字化、信息化。比如支付宝、微信、铁路12306等涉及到用户的个人信息安全及财产安全。因此，身份认证也是互联网世界中保障用户信息安全的最主要方式之一。

由于时代的发展，身份认证的形式也是截然不同。例如：基于硬件的认证技术，包括U盾和密码器等；基于人类生物特征的认证技术，包括指纹和虹膜等；以及目前熟悉的文本口令、图形口令等。然而，由于基于硬件和生物特征的认证方式通常存在高成本、使用不便及隐私泄露等问题，低成本、简单、易实现的文本口令则被广泛应用在互联网身份认证中。而且在可预见的未来，口令认证仍将作为主要的身份认证方式并被应用于互联网中的各大主流服务商。由于口令存在的必需性，人类需要深入理解并研究口令的安全性和可用性^[1]。口令被人类所创造，也就代表口令的研究结果会直接受人的行为所影响，而不同人的行为因其自身或所处外界环境的不同而迥然相异。例如，同样是注册一个网页游戏账户，有的人只是抱着体验的心态随便注册一个账户，会使用简单的“123123”作为口令。而有的人则是被该类型的游戏所吸引，就会悉心构造一个字符串（比如“g2a0m0e0”，出生年份插入单词game中）作为口令。

在近十年中，国内外知名网站的口令泄露事件不断发生，非法攻击者从中获取到了丰厚的资源，并将其用于优化口令攻击的算法。如：在2011年，国内知名IT技术CSDN网站经历黑客攻击，大约600万条用户数据被泄露，此后天涯，嘟嘟牛等国内多家网站陆续出现用户明文口令泄露事件；在2013到2016年间，国外知名社交网站Yahoo遭遇严重的黑客攻击，近10亿条用户数据包括邮箱，口令，电话号码等被泄露；在2017年，数据服务公司Dun ＆Bradstreet（D＆B）于3月份泄露了一个数据量高达52GB的数据库，约3370万个电子邮件地址和联系信息被泄露；在2018年，华住旗下多个连锁酒店开房信息数据正在暗网出售，包括姓名、手机号、邮箱、身份证号、登录密码等，泄密数量达到5亿条；在2019年，IT 安全和云数据管理巨头 Rubrik 的数据库遭到泄露，泄露包含姓名和联系方式在内的客户数据约10GB。

1.2国内外研究现状

安全研究往往包括两方面，即攻击和防守。在口令安全中，口令破解即代表着攻击，口令强度评估即代表着防守，所以本节将对口令破解和口令强度评估两方面进行研究现状分析。

1.2.1口令破解研究现状

对于口令的破解，暴力破解方法往往是最直接也是最易理解的。暴力破解主要指用穷举法列举出所有可能的密码。利用这种方法来将字符进行逐个组合，理论上可以破解任何一个密码，仅仅只是一个时间问题。然而，组合方法可能有几千万亿种，可能会耗费几个月的时间甚至更多，这样长的时间显然是不被接受的。其解决办法就是利用字典，即攻击者按照不同的规则将可能的密码组合缩小到某个范围，比如英文单词以及生日的数字组合等，这在很大程度上缩短了破解时间。