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

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

1 概述

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

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

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

2 口令屬性

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

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

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

表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起始的連續(xù)11位數(shù)字字符串，例如13999999999,15000000000或18111111111等。存在一些重疊的情況，例如英語單詞yesterday中起始ye也可被認(rèn)為是百家姓中的“葉”姓，此時匹配的規(guī)則是長度優(yōu)先。弱口令目前沒有廣泛接受的明確定義，因此，在互聯(lián)網(wǎng)上搜錄一些黑客常用的口令破解字典，將出現(xiàn)在字典中的口令視為弱口令。

3 口令屬性分析

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

圖1 口令分析流程

對輸入的口令依次進行口令屬性拆分、屬性分類、數(shù)據(jù)挖掘。每一個步驟不僅是下一步的前提，也可以獲得不少有價值的信息。數(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}為所有待分析的口令。對于P中的每一個口令pi，分析其構(gòu)造，得到pi擁有的屬性集合PAi={ai1,ai2,…,aij}，其中屬性aij∈A?？诹顚傩圆鸱值妮敵鰹樗锌诹罴捌鋵?yīng)屬性集合，即PASet={{p1,PA1},{p2,PA2},…,{pm,PAm}}。

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

3.2 口令屬性歸類

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

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

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

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

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

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

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

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

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

(4)k-項集：同時出現(xiàn)的k個項的集合，定義為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-項集。以支持度和置信度來刻畫一條規(guī)則的好壞，輸出所有滿足預(yù)設(shè)的最小支持度、最小置信度的規(guī)則。

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

4 實驗結(jié)果與分析

4.1 實驗環(huán)境

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

表2 實驗環(huán)境

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

4.2 實驗性能

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

表3 性能測試

4.3 口令屬性拆分

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

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

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

4.4 口令屬性歸類

通過口令屬性歸類，根據(jù)屬性的不同總共獲得884類口令，該數(shù)字遠(yuǎn)小于輸入的口令總數(shù)642萬。表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算法進行規(guī)則關(guān)聯(lián)時，設(shè)置的最小支持度為10%，最小置信度為10%，最大置信度為99%。設(shè)置最大置信度是為了屏蔽置信度100%，即存在必然關(guān)系的規(guī)則，這些規(guī)則都是無實際意義的。

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

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

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

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

5 結(jié)束語

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

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

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

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

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

[4]許春香,何小虎.高效的基于口令的三方密鑰交換協(xié)議[J].電子科技大學(xué)學(xué)報,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]曾萬聰,周緒波,戴 勃,等.關(guān)聯(lián)規(guī)則挖掘的矩陣算法[J].計算機工程,2006,32(2):45-47.

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