基于屬性拆分與數(shù)據(jù)挖掘的真實(shí)口令分析

郭奕東，邱衛(wèi)東，劉伯仲

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

1 概述

在計(jì)算機(jī)與互聯(lián)網(wǎng)技術(shù)高度發(fā)展的今天，口令目前仍然是身份驗(yàn)證的主要手段。除軍事、金融等對(duì)安全性要求極高的領(lǐng)域之外，無(wú)論是主流的文件加密應(yīng)用，還是流行的網(wǎng)絡(luò)應(yīng)用，如電子郵件、即時(shí)通訊工具、論壇等，都依靠口令進(jìn)行用戶身份或者使用權(quán)限的認(rèn)證?？诹钚孤痘蜻z失，將導(dǎo)致機(jī)密數(shù)據(jù)泄露、用戶隱私遭竊取、經(jīng)濟(jì)財(cái)產(chǎn)損失等一系列嚴(yán)重后果。目前研究主要集中在基于口令的密鑰交換協(xié)議上。文獻(xiàn)[1]提出形式化分析協(xié)議安全性的方法；文獻(xiàn)[2]分析一個(gè)協(xié)議的安全性缺陷并提出改進(jìn)；文獻(xiàn)[3-4]分別關(guān)注基于口令三方密鑰交換協(xié)議的安全性與高效性；文獻(xiàn)[5]提出在不經(jīng)意傳輸下有效的基于口令的密鑰交換方法；文獻(xiàn)[6]提出基于口令的秘密交換概念以及有效的協(xié)議。

然而，對(duì)于口令本身的研究卻相當(dāng)少見。出于方便記憶的原因，用戶設(shè)置的口令通常不是完全隨機(jī)的，而會(huì)選擇姓名、生日、電話、英文單詞等或其組合。這為字典、社交工程或其他手段的攻擊提供了可能。目前研究口令設(shè)置的文獻(xiàn)比較少見，文獻(xiàn)[7]通過Windows Live Toolbar得以記錄用戶登錄不同網(wǎng)站的口令，發(fā)現(xiàn)用戶平均擁有6.5個(gè)口令，每3.9個(gè)網(wǎng)站共享一個(gè)口令；口令平均長(zhǎng)度40.54 bit；并且簡(jiǎn)單統(tǒng)計(jì)純數(shù)字、小寫字母、數(shù)字小寫、強(qiáng)口令4類占總口令數(shù)量的百分比。文獻(xiàn)[8]提出了口令因子的概念并基于此實(shí)現(xiàn)字典，取得良好的恢復(fù)效果。2011年末眾多大型網(wǎng)站口令泄露的事件，突顯此類信息安全事件的嚴(yán)重影響，然而也為分析真實(shí)口令提供了數(shù)據(jù)來(lái)源。

本文提出一種新的基于屬性的口令分析方法，通過對(duì)口令屬性進(jìn)行分析、歸類獲得數(shù)據(jù)源；使用Apriori算法[9]挖掘口令屬性之間的內(nèi)在聯(lián)系，挖掘用戶設(shè)置口令的習(xí)慣。

2 口令屬性

直接對(duì)口令進(jìn)行分析是困難的。雖然可以通過編輯距離等方法量化分析字符串之間的相似度，然而這對(duì)于口令分析并不合理，不能揭示口令設(shè)置特征。因此，必須對(duì)原始口令進(jìn)行一些預(yù)處理。

定義 口令屬性是口令字符串的特點(diǎn)、性質(zhì)或特征。

口令屬性體現(xiàn)的是口令之間內(nèi)在的性質(zhì)，是本文分析的主要數(shù)據(jù)?？诹顚傩杂稍伎诹畈鸱肢@得，可以設(shè)置不同的口令屬性，本文中所分析的屬性如表1所示。表中所有屬性皆為布爾值，是名詞性屬性，便于之后的數(shù)據(jù)挖掘。

表1 口令屬性

姓氏匹配的是百家姓中444個(gè)單姓的拼音，忽略大小寫。例如：“趙”姓拼音為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等字符串，均可視為包含生日。手機(jī)號(hào)匹配的是形如13,15,18起始的連續(xù)11位數(shù)字字符串，例如13999999999,15000000000或18111111111等。存在一些重疊的情況，例如英語(yǔ)單詞yesterday中起始ye也可被認(rèn)為是百家姓中的“葉”姓，此時(shí)匹配的規(guī)則是長(zhǎng)度優(yōu)先。弱口令目前沒有廣泛接受的明確定義，因此，在互聯(lián)網(wǎng)上搜錄一些黑客常用的口令破解字典，將出現(xiàn)在字典中的口令視為弱口令。

3 口令屬性分析

口令屬性分析的總體流程如圖1所示。

圖1 口令分析流程

對(duì)輸入的口令依次進(jìn)行口令屬性拆分、屬性分類、數(shù)據(jù)挖掘。每一個(gè)步驟不僅是下一步的前提，也可以獲得不少有價(jià)值的信息。數(shù)據(jù)挖掘算法采用經(jīng)典Apriori關(guān)聯(lián)算法。

3.1 口令屬性拆分

口令的屬性拆分是從原始口令中分析獲得量化數(shù)據(jù)的關(guān)鍵步驟，為之后的所有過程提供原始數(shù)據(jù)。

口令屬性拆分的形式化定義如下：輸入屬性集合A={a1,a2,…,an}，是需要分析的所有口令屬性，輸入口令集合P={p1,p2,…,pm}為所有待分析的口令。對(duì)于P中的每一個(gè)口令pi，分析其構(gòu)造，得到pi擁有的屬性集合PAi={ai1,ai2,…,aij}，其中屬性aij∈A?？诹顚傩圆鸱值妮敵鰹樗锌诹罴捌鋵?duì)應(yīng)屬性集合，即PASet={{p1,PA1},{p2,PA2},…,{pm,PAm}}。

對(duì)口令屬性拆分后得到的口令屬性集合進(jìn)行統(tǒng)計(jì)，可以獲得各個(gè)屬性ai∈A出現(xiàn)的百分比信息。

3.2 口令屬性歸類

口令屬性歸類是在口令屬性拆分結(jié)果PASet中，將完全一致的PA合并為一類，并統(tǒng)計(jì)其出現(xiàn)的次數(shù)。

口令屬性歸類的形式化定義如下：輸入PASet={{p1,PA1},{p2,PA2},…,{pm,PAm}}，統(tǒng)計(jì)合并相同的PA，輸出集合ASet={{Countn1,PAn1},{Countn2,PAn2},…,{Countnk,PAnk}}， 其中，Countn1≥1,nk≤m。

歸類之后可以得到每一分類的數(shù)量信息，并且該數(shù)據(jù)集已經(jīng)忽略了原始的口令。通過對(duì)Countni進(jìn)行排序，可以獲得數(shù)量最多的屬性類別信息。

歸類更重要的意義在于減少之后數(shù)據(jù)挖掘的計(jì)算量。雖然目前已經(jīng)有不少針對(duì)規(guī)則關(guān)聯(lián)算法快速實(shí)現(xiàn)[10]的研究，例如通過矩陣算法[11]或者十字鏈表[12]優(yōu)化，然而性能依舊難以滿足千萬(wàn)級(jí)數(shù)據(jù)量的要求?？紤]到用戶設(shè)置口令的非完全隨機(jī)性，以及各個(gè)屬性之間可能存在的互斥、包含關(guān)系，|ASet|<<<|PASet|。因此，對(duì)歸類后的ASet進(jìn)行挖掘數(shù)據(jù)量遠(yuǎn)小于直接對(duì)PASet進(jìn)行數(shù)據(jù)挖掘。

3.3 口令數(shù)據(jù)挖掘

采用Apriori算法對(duì)ASet進(jìn)行數(shù)據(jù)挖掘。Apriori是一項(xiàng)基本的關(guān)聯(lián)規(guī)則算法，在數(shù)據(jù)集中找出項(xiàng)與項(xiàng)之間的關(guān)系。該算法的一些基本概念如下：

(1)資料庫(kù)：存儲(chǔ)二維結(jié)構(gòu)的記錄集。定義為D；

(2)所有項(xiàng)集：所有項(xiàng)目的集合，定義為I；

(3)記錄：資料庫(kù)中的一筆記錄，定義為T；

(4)k-項(xiàng)集：同時(shí)出現(xiàn)的k個(gè)項(xiàng)的集合，定義為k-itemset；

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

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

算法挖掘的目標(biāo)是形如X->Y的規(guī)則，其中，X,Y均為k-項(xiàng)集。以支持度和置信度來(lái)刻畫一條規(guī)則的好壞，輸出所有滿足預(yù)設(shè)的最小支持度、最小置信度的規(guī)則。

Apriori算法的一個(gè)經(jīng)典應(yīng)用是購(gòu)物籃分析，分析顧客購(gòu)買不同商品之間的關(guān)系。該算法也十分適合口令屬性分析。在口令屬性分析中，PASet口令屬性集合對(duì)應(yīng)于資料庫(kù)D，A對(duì)應(yīng)于所有項(xiàng)集，一個(gè)口令的屬性PAi對(duì)應(yīng)于一條記錄。因此，可以將Apriori直接應(yīng)用于PASet以獲得口令屬性ai之間的關(guān)聯(lián)規(guī)則。在實(shí)際使用中，如3.2節(jié)所述，考慮到性能，將該算法應(yīng)用到ASet上，在更短時(shí)間內(nèi)得到相同的結(jié)果。

4 實(shí)驗(yàn)結(jié)果與分析

4.1 實(shí)驗(yàn)環(huán)境

使用Java開發(fā)實(shí)現(xiàn)了整個(gè)口令分析系統(tǒng)，進(jìn)行相關(guān)實(shí)驗(yàn)，實(shí)驗(yàn)環(huán)境數(shù)據(jù)如表2所示。分析的對(duì)象是CSDN泄露的642萬(wàn)條真實(shí)口令。原始口令數(shù)據(jù)如圖2所示。

表2 實(shí)驗(yàn)環(huán)境

圖2 原始口令數(shù)據(jù)

4.2 實(shí)驗(yàn)性能

將640萬(wàn)條真實(shí)口令輸入系統(tǒng)，運(yùn)行時(shí)間如表3所示。

表3 性能測(cè)試

4.3 口令屬性拆分

在拆分進(jìn)行屬性拆分之后，首先得到了各個(gè)屬性的統(tǒng)計(jì)信息，如表4所示。

表4 口令屬性統(tǒng)計(jì)

由表4可見，用戶設(shè)置口令長(zhǎng)度集中分布在7位～11位，占據(jù)總量的85.02%；超過12位的口令也有近13%。在口令的字符組成上，大部分的口令包含數(shù)字與小寫字母，發(fā)現(xiàn)一個(gè)重要的特征是純數(shù)字的口令竟然有45.03%之多。純數(shù)字口令安全性極差，會(huì)給攻擊者帶來(lái)極大的方便。口令內(nèi)容組成上百家姓、生日與簡(jiǎn)單數(shù)字是大部分用戶構(gòu)建口令的選擇。

4.4 口令屬性歸類

通過口令屬性歸類，根據(jù)屬性的不同總共獲得884類口令，該數(shù)字遠(yuǎn)小于輸入的口令總數(shù)642萬(wàn)。表5列舉了所有百分比超過3%的口令類別。

表5 口令屬性分類

在表5的8類口令中，類別1、類別2是7位～11位的全數(shù)字口令，占16.21%；類別4～類別6是7位～11位全數(shù)字的弱口令；類別3、類別8是7位～11位包含數(shù)字與小寫字母的口令。從最多的口令類別中依舊可以看出，數(shù)字在口令的組成里處于支配性地位。

4.5 口令數(shù)據(jù)挖掘

在使用Apriori算法進(jìn)行規(guī)則關(guān)聯(lián)時(shí)，設(shè)置的最小支持度為10%，最小置信度為10%，最大置信度為99%。設(shè)置最大置信度是為了屏蔽置信度100%，即存在必然關(guān)系的規(guī)則，這些規(guī)則都是無(wú)實(shí)際意義的。

算法最終挖掘出的規(guī)則數(shù)目是107條，考慮到屬性間的一些包含關(guān)系，如：包含百家姓->包含小寫字母(支持度=20.85%，置信度=95.26%)，進(jìn)行了人工篩選，去除了顯而易見的規(guī)則。表6列選了一些挖掘出的規(guī)則。

表6 口令屬性規(guī)則

對(duì)表6中列舉的10條規(guī)則，按照置信度排序。規(guī)則1～規(guī)則4、規(guī)則7、規(guī)則9突顯數(shù)字在口令組成中的重要地位，這與屬性拆分后的統(tǒng)計(jì)結(jié)果一致。規(guī)則5、規(guī)則6顯示了百家姓、小寫字母與數(shù)字的組合構(gòu)成一大部分的口令。規(guī)則8表明包含百家姓的口令中長(zhǎng)度在9位～11位的占總數(shù)一半以上。規(guī)則10顯示了用戶在使用小寫字母構(gòu)造口令時(shí)，相當(dāng)一部分選用百家姓，可以做出合理推斷就是用戶本身的姓。

通過這些實(shí)驗(yàn)數(shù)據(jù)表明，本文提出的方法能夠有效分析出用戶這是口令的內(nèi)在特征，并且能夠處理百萬(wàn)甚至千萬(wàn)級(jí)的口令數(shù)據(jù)。

5 結(jié)束語(yǔ)

本文提出了一種基于口令屬性的口令分析方法。首先定義了口令屬性的概念，并提出一些可以分析的屬性，然后依次通過屬性拆分、屬性歸類以及口令屬性的數(shù)據(jù)挖掘，得到用戶設(shè)置口令的特征。在實(shí)驗(yàn)中使用該方法分析640多萬(wàn)條真實(shí)口令，得到現(xiàn)實(shí)世界中用戶設(shè)置口令的一些習(xí)慣特征。

本文中涉及的20條口令屬性是根據(jù)經(jīng)驗(yàn)提出的，并沒有數(shù)據(jù)分析的基礎(chǔ)。下一步工作可以通過模式識(shí)別等方法，從原始口令數(shù)據(jù)中挖掘出口令的屬性，并應(yīng)用本文方法更精確地獲得口令特征。

[1]李 莉,薛 銳,張煥國(guó),等.基于口令認(rèn)證的密鑰交換協(xié)議的安全性分析[J].電子學(xué)報(bào),2005,33(1):166-170.

[2]張利華,章麗萍,張有光,等.基于口令的遠(yuǎn)程身份認(rèn)證及密鑰協(xié)商協(xié)議[J].計(jì)算機(jī)應(yīng)用,2009,29(4):924-927.

[3]丁曉飛,馬傳貴.具有強(qiáng)安全性的三方口令認(rèn)證密鑰交換協(xié)議[J].計(jì)算機(jī)學(xué)報(bào),2010,33(1):111-118.

[4]許春香,何小虎.高效的基于口令的三方密鑰交換協(xié)議[J].電子科技大學(xué)學(xué)報(bào),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]盧致旭,邱衛(wèi)東,廖 凌.基于數(shù)據(jù)挖掘技術(shù)的字典生成方法[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]曾萬(wàn)聰,周緒波,戴 勃,等.關(guān)聯(lián)規(guī)則挖掘的矩陣算法[J].計(jì)算機(jī)工程,2006,32(2):45-47.

[12]黃建明,趙文靜,王星星.基于十字鏈表的Apriori改進(jìn)算法[J].計(jì)算機(jī)工程,2009,35(2):37-38,41.