基于屬性拆分與數據挖掘的真實口令分析

郭奕東，邱衛東，劉伯仲

(上海交通大學信息安全工程學院，上海 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.