基于属性拆分与数据挖掘的真实口令分析

郭奕东，邱卫东，刘伯仲

(上海交通大学信息安全工程学院，上海 200240)

1 概述

在计算机与互联网技术高度发展的今天，口令目前仍然是身份验证的主要手段。除军事、金融等对安全性要求极高的领域之外，无论是主流的文件加密应用，还是流行的网络应用，如电子邮件、即时通讯工具、论坛等，都依靠口令进行用户身份或者使用权限的认证。口令泄露或遗失，将导致机密数据泄露、用户隐私遭窃取、经济财产损失等一系列严重后果。目前研究主要集中在基于口令的密钥交换协议上。文献[1]提出形式化分析协议安全性的方法；文献[2]分析一个协议的安全性缺陷并提出改进；文献[3-4]分别关注基于口令三方密钥交换协议的安全性与高效性；文献[5]提出在不经意传输下有效的基于口令的密钥交换方法；文献[6]提出基于口令的秘密交换概念以及有效的协议。

然而，对于口令本身的研究却相当少见。出于方便记忆的原因，用户设置的口令通常不是完全随机的，而会选择姓名、生日、电话、英文单词等或其组合。这为字典、社交工程或其他手段的攻击提供了可能。目前研究口令设置的文献比较少见，文献[7]通过Windows Live Toolbar得以记录用户登录不同网站的口令，发现用户平均拥有6.5个口令，每3.9个网站共享一个口令；口令平均长度40.54 bit；并且简单统计纯数字、小写字母、数字小写、强口令4类占总口令数量的百分比。文献[8]提出了口令因子的概念并基于此实现字典，取得良好的恢复效果。2011年末众多大型网站口令泄露的事件，突显此类信息安全事件的严重影响，然而也为分析真实口令提供了数据来源。

本文提出一种新的基于属性的口令分析方法，通过对口令属性进行分析、归类获得数据源；使用Apriori算法[9]挖掘口令属性之间的内在联系，挖掘用户设置口令的习惯。

2 口令属性

直接对口令进行分析是困难的。虽然可以通过编辑距离等方法量化分析字符串之间的相似度，然而这对于口令分析并不合理，不能揭示口令设置特征。因此，必须对原始口令进行一些预处理。

定义 口令属性是口令字符串的特点、性质或特征。

口令属性体现的是口令之间内在的性质，是本文分析的主要数据。口令属性由原始口令拆分获得，可以设置不同的口令属性，本文中所分析的属性如表1所示。表中所有属性皆为布尔值，是名词性属性，便于之后的数据挖掘。

表1 口令属性

姓氏匹配的是百家姓中444个单姓的拼音，忽略大小写。例如：“赵”姓拼音为zhao，那么口令zhao1989、JackieZhao都可匹配为包含姓氏。生日匹配的是形如yyyymmdd,yyyymdd,yyyymd,yyyy-mm-dd,yyyy-m-dd,yyyy-m-d,yyyy.mm.dd,yyyy.m.dd,yyyy.m.d的字符串。其中，yyyy匹配1900年-2020年，m或mm匹配月份，d或dd匹配日期。例如若包含19800703,1980703,189073,1980-7-13等字符串，均可视为包含生日。手机号匹配的是形如13,15,18起始的连续11位数字字符串，例如13999999999,15000000000或18111111111等。存在一些重叠的情况，例如英语单词yesterday中起始ye也可被认为是百家姓中的“叶”姓，此时匹配的规则是长度优先。弱口令目前没有广泛接受的明确定义，因此，在互联网上搜录一些黑客常用的口令破解字典，将出现在字典中的口令视为弱口令。

3 口令属性分析

口令属性分析的总体流程如图1所示。

图1 口令分析流程

对输入的口令依次进行口令属性拆分、属性分类、数据挖掘。每一个步骤不仅是下一步的前提，也可以获得不少有价值的信息。数据挖掘算法采用经典Apriori关联算法。

3.1 口令属性拆分

口令的属性拆分是从原始口令中分析获得量化数据的关键步骤，为之后的所有过程提供原始数据。

口令属性拆分的形式化定义如下：输入属性集合A={a1,a2,…,an}，是需要分析的所有口令属性，输入口令集合P={p1,p2,…,pm}为所有待分析的口令。对于P中的每一个口令pi，分析其构造，得到pi拥有的属性集合PAi={ai1,ai2,…,aij}，其中属性aij∈A。口令属性拆分的输出为所有口令及其对应属性集合，即PASet={{p1,PA1},{p2,PA2},…,{pm,PAm}}。

对口令属性拆分后得到的口令属性集合进行统计，可以获得各个属性ai∈A出现的百分比信息。

3.2 口令属性归类

口令属性归类是在口令属性拆分结果PASet中，将完全一致的PA合并为一类，并统计其出现的次数。

口令属性归类的形式化定义如下：输入PASet={{p1,PA1},{p2,PA2},…,{pm,PAm}}，统计合并相同的PA，输出集合ASet={{Countn1,PAn1},{Countn2,PAn2},…,{Countnk,PAnk}}， 其中，Countn1≥1,nk≤m。

归类之后可以得到每一分类的数量信息，并且该数据集已经忽略了原始的口令。通过对Countni进行排序，可以获得数量最多的属性类别信息。

归类更重要的意义在于减少之后数据挖掘的计算量。虽然目前已经有不少针对规则关联算法快速实现[10]的研究，例如通过矩阵算法[11]或者十字链表[12]优化，然而性能依旧难以满足千万级数据量的要求。考虑到用户设置口令的非完全随机性，以及各个属性之间可能存在的互斥、包含关系，|ASet|<<<|PASet|。因此，对归类后的ASet进行挖掘数据量远小于直接对PASet进行数据挖掘。

3.3 口令数据挖掘

采用Apriori算法对ASet进行数据挖掘。Apriori是一项基本的关联规则算法，在数据集中找出项与项之间的关系。该算法的一些基本概念如下：

(1)资料库：存储二维结构的记录集。定义为D；

(2)所有项集：所有项目的集合，定义为I；

(3)记录：资料库中的一笔记录，定义为T；

(4)k-项集：同时出现的k个项的集合，定义为k-itemset；

(5)支持度：定义为support(X)=occur(X)/count(D)=P(X)；

(6)置信度：定义为confidence(X->Y)=support(XUY)/support(X)=P(Y|X)。

算法挖掘的目标是形如X->Y的规则，其中，X,Y均为k-项集。以支持度和置信度来刻画一条规则的好坏，输出所有满足预设的最小支持度、最小置信度的规则。

Apriori算法的一个经典应用是购物篮分析，分析顾客购买不同商品之间的关系。该算法也十分适合口令属性分析。在口令属性分析中，PASet口令属性集合对应于资料库D，A对应于所有项集，一个口令的属性PAi对应于一条记录。因此，可以将Apriori直接应用于PASet以获得口令属性ai之间的关联规则。在实际使用中，如3.2节所述，考虑到性能，将该算法应用到ASet上，在更短时间内得到相同的结果。

4 实验结果与分析

4.1 实验环境

使用Java开发实现了整个口令分析系统，进行相关实验，实验环境数据如表2所示。分析的对象是CSDN泄露的642万条真实口令。原始口令数据如图2所示。

表2 实验环境

图2 原始口令数据

4.2 实验性能

将640万条真实口令输入系统，运行时间如表3所示。

表3 性能测试

4.3 口令属性拆分

在拆分进行属性拆分之后，首先得到了各个属性的统计信息，如表4所示。

表4 口令属性统计

由表4可见，用户设置口令长度集中分布在7位～11位，占据总量的85.02%；超过12位的口令也有近13%。在口令的字符组成上，大部分的口令包含数字与小写字母，发现一个重要的特征是纯数字的口令竟然有45.03%之多。纯数字口令安全性极差，会给攻击者带来极大的方便。口令内容组成上百家姓、生日与简单数字是大部分用户构建口令的选择。

4.4 口令属性归类

通过口令属性归类，根据属性的不同总共获得884类口令，该数字远小于输入的口令总数642万。表5列举了所有百分比超过3%的口令类别。

表5 口令属性分类

在表5的8类口令中，类别1、类别2是7位～11位的全数字口令，占16.21%；类别4～类别6是7位～11位全数字的弱口令；类别3、类别8是7位～11位包含数字与小写字母的口令。从最多的口令类别中依旧可以看出，数字在口令的组成里处于支配性地位。

4.5 口令数据挖掘

在使用Apriori算法进行规则关联时，设置的最小支持度为10%，最小置信度为10%，最大置信度为99%。设置最大置信度是为了屏蔽置信度100%，即存在必然关系的规则，这些规则都是无实际意义的。

算法最终挖掘出的规则数目是107条，考虑到属性间的一些包含关系，如：包含百家姓->包含小写字母(支持度=20.85%，置信度=95.26%)，进行了人工筛选，去除了显而易见的规则。表6列选了一些挖掘出的规则。

表6 口令属性规则

对表6中列举的10条规则，按照置信度排序。规则1～规则4、规则7、规则9突显数字在口令组成中的重要地位，这与属性拆分后的统计结果一致。规则5、规则6显示了百家姓、小写字母与数字的组合构成一大部分的口令。规则8表明包含百家姓的口令中长度在9位～11位的占总数一半以上。规则10显示了用户在使用小写字母构造口令时，相当一部分选用百家姓，可以做出合理推断就是用户本身的姓。

通过这些实验数据表明，本文提出的方法能够有效分析出用户这是口令的内在特征，并且能够处理百万甚至千万级的口令数据。

5 结束语

本文提出了一种基于口令属性的口令分析方法。首先定义了口令属性的概念，并提出一些可以分析的属性，然后依次通过属性拆分、属性归类以及口令属性的数据挖掘，得到用户设置口令的特征。在实验中使用该方法分析640多万条真实口令，得到现实世界中用户设置口令的一些习惯特征。

本文中涉及的20条口令属性是根据经验提出的，并没有数据分析的基础。下一步工作可以通过模式识别等方法，从原始口令数据中挖掘出口令的属性，并应用本文方法更精确地获得口令特征。

[1]李 莉,薛 锐,张焕国,等.基于口令认证的密钥交换协议的安全性分析[J].电子学报,2005,33(1):166-170.

[2]张利华,章丽萍,张有光,等.基于口令的远程身份认证及密钥协商协议[J].计算机应用,2009,29(4):924-927.

[3]丁晓飞,马传贵.具有强安全性的三方口令认证密钥交换协议[J].计算机学报,2010,33(1):111-118.

[4]许春香,何小虎.高效的基于口令的三方密钥交换协议[J].电子科技大学学报,2012,41(4):596-598.

[5]Canetti R,Dachman S D,Vaikuntanathan V,et al.Efficient Password Authenticated Key Exchange via Oblivious Transfer[EB/OL].(2013-07-31).http://link.springer.comcontent/pdf/10.1007/978-3-642-30057-8_27.pdf.

[6]Bagherzandi A,Jarecki S,Saxena N,et al.Password-protected Secret Sharing[C]//Proc.of the 18th ACM Conference on Computer and Communications Security.[S.l.]:ACM Press,2011:433-444.

[7]Florencio D,Herley C.A Large-scale Study of Web Password Habits[C]//Proc.of the 16th International Conference on World Wide Web.[S.l.]:ACM Press,2007:657-666.

[8]卢致旭,邱卫东,廖 凌.基于数据挖掘技术的字典生成方法[J].信息安全与通信保密,2011,9(11):63-65.

[9]Wang Ke,Tang Liu,Han Jiawei,et al.Top Down FP-growth for Association Rule Mining[EB/OL].[2013-07-31].http://link.springer.com/chapter/10.1007/3-540-47887-6_34.

[10]Agrawal R,Srikant R.Fast Algorithms for Mining Association Rules[C]//Proc.of the 20th International Conference on Very Large Data Bases.[S.l.]:ACM Press,1994:487-499.

[11]曾万聪,周绪波,戴 勃,等.关联规则挖掘的矩阵算法[J].计算机工程,2006,32(2):45-47.

[12]黄建明,赵文静,王星星.基于十字链表的Apriori改进算法[J].计算机工程,2009,35(2):37-38,41.