密碼目前仍是各系統中用來作認證最常用的機制，然而這種機制很容易受到字典攻擊法攻擊。為了防止這種攻擊，使用者會使用複雜的知識建構規則來創建其密碼。本文利用資料探勘的方法，試圖找出這樣的密碼知識建構規則，並利用其所發現之規則，建構出對於破解密碼的模型。
在密碼知識建構規則探勘中，我們利用已公布的一個大型社交網站用戶密碼進行正規化、結構分類與統計分析，發現使用者在創建密碼時，有80%以上是由英文小寫文字與數字交錯使用而成，其中在英文小寫字串後附加數字的密碼結構規則佔了33.02%。然而，在「英文小寫字串」、「英文小寫字串後附加數字」與「數字後附加英文小寫字串」之間，經過與dic-0294比對之後，有意義的英文小寫字串比例卻有明顯的差異。在上述的三大類之間，將英文小寫字串抽離互相比對後，以長度為6的英文小寫字串來說，有意義的字串比例為6.78%、43.39%、59.76%；若長度縮減為4，有意義的字串比例提高為64.14%、69.58%、79.73%。
之後我們利用Context-Free Grammar來表示密碼知識建構規則且分析這些知識規則所建構之所有密碼之空間複雜度。發現對於密碼知識建構規則的分析，低於280有99.94%，低於240有77.04%。為了實驗有效的攻擊辦法，我們設計了一種模式，利用訓練時所產生的密碼知識規則以及規則下的元素集合(Knowledge Set)、搭配廣泛的字典(Dictionary)用於測試集(Testing Set)來進行密碼破解效果的測試，稱為KDT模型，生成密碼的資料庫。並利用此密碼資料庫對測試集做破解的動作。將之前已公布的大型社交網站用戶密碼等份，任取一份利用KTD模型作為訓練集來訓練，之後任取一份做為測試集測試。

Passwords are still the most commonly used mechanism for user authentication. However, they are vulnerable to dictionary attacks. In order to guard against such attacks, users will use complicated knowledge construction rules to create their passwords. This paper proposes a method by using data mining to find out these knowledge construction rules, and uses these rules to create a model to cracking passwords.
To mining these rules, we analyze an already announced large social network websites users’ password. After these data are normalized, structural classification and statistics, we found that more than 80 percent passwords are created by English lowercase and digital. And additional digital string after English lowercase string’s case is 33.02 percent. However, after comparing with dic-0294, there is obvious difference in meaningful English lowercase string’s ratio between “English lowercase string”, “additional digital string after English lowercase string” and “additional English lowercase string after digital string”. Dic-0294 should contain most common American words, abbreviations, hyphenations, and even incorrect spellings. To the length is six of English lowercase string, the meaningful string’s rate are 6.78 percent, 43.39 percent and 59.76 percent. This represent when users create their password only use English lowercase string, they wont use one word to be password so that the repeat strings are very small. If the length is four, the rate are raising 64.14 percent, 69.58 percent and 79.73 percent. It means the shorter English lowercase string they use, the higher rate of meaningful string.
	Then we use a complete grammar type to represent password knowledge construction rules and analyze these password’s space complexity. We found that there are 99.04 percent lower than 280, and 77.04 percent lower than 240. We propose a high efficient and effective way by these data to cracking those users’ password. And we create a model include knowledge construction rules and elements’ set, and also use widespread dictionary in training set to do cracking password. The model called KTD model. Then we generate a database of password and use this database for cracking those password. We separate the websites users’ password, and then use one of them to do Knowledge set and one of them for Testing set. In 1/10000000, the success rate of password cracking is 10%.

一、	緒論...............................................1
1.1	研究背景、動機...............................................1
1.2	論文架構....................................................1
二、	文獻探討...........................................2
2.1	Context-Free Grammar.........................................2
2.2	John The Ripper..............................................3
2.3	圖形密碼....................................................4
2.4	字典攻擊法..................................................4
2.5	暴力攻擊法..................................................4
三、	分析用戶密碼.......................................5
3.1	用戶密碼之元素與結構........................................5
3.2	用戶創建密碼之數字組合......................................8
3.3	用戶創建密碼之文字.........................................10
四、	生成密碼策略......................................13
4.1	密碼產生文法規則...........................................13
4.2	複雜度分析.................................................14
4.3	KDT模型..................................................15
4.4	與測試集比對...............................................17
4.5	破解成功率.................................................19
五、	結論..............................................20
5.1	密碼知識規則...............................................20
5.2	密碼複雜度.................................................20
3.3	破解密碼...................................................21
參考文獻.................................................22
附錄1	Rockyou前100名密碼結構規則.......................23

表目錄
表3-1	94種可列印文字...........................................................................................5
表3-2	用戶密碼之結構............................................................................................6
表3-3	前十名密碼結構規則....................................................................................7
表3-4	前五名之原始結構........................................................................................7
表3-5	L+D+數字字數前十名之結構........................................................................7
表3-6	前五名L+D2與相對應D2L+統計之結構......................................................8
表3-7	L+D2與D2L+之數字組合相關係數...............................................................8
表3-8	前五名L+D4與相對應D4L+統計之結構......................................................9
表3-9	L+D4與D4L+之數字組合相關係數...............................................................9
表3-10	前五名L+D3與相對應D3L+統計之結構....................................................10
表3-11	L+D3與D3L+之數字組合相關係數.............................................................10
表3-12	L+之前五名結構..........................................................................................11
表3-13	L2 – L13之有意義字串數量與百分比.......................................................11
表3-14	L2D2 – L13D2之有意義字串數量與百分比...............................................12
表3-15	D2L2 – D2L13之有意義字串數量與百分比..............................................12
表4-1	Rockyou密碼結構前十名之複雜度...........................................................14
表4-2	密碼強度與所佔比例..................................................................................14
表4-3	20等份時，未使用字典訓練集與測試集比對後之機率與數量...............17
表4-4	10等份時，未使用字典訓練集與測試集比對後之機率與數量...............18
表4-5	4等份時，未使用字典訓練集與測試集比對後之機率與數量.................18
表4-6	20等份使用字典訓練集與測試集比對後之機率與數量.........................18

圖目錄
圖1	KDT模型流程圖.....................................17
圖2	相同機率下，使用與不使用字典之成功率曲線...........19

[1] 	H. Gao, X. Liu, S. Wang, H.g Liu, R. Dai, Design and Analysis of a Graphical Password Scheme, International Conference of Innovative Computing, Information and Control, pp.675-678, 2009.
[2] 	S. Delaune, F. Jacquemard, A Theory of Dictionary Attacks and its Complexity, 17th IEEE Computer Security Foundations Workshop, 2004.
[3] 	J. Yan, A. Blackwell, R. Anderson, and A. Grant. Password Memorability and Security: Empirical Results. IEEE Security and Privacy Magazine, Volume 2, Number 5, pages 25-31, 2004.
[4] 	R. V. Yampolskiy. Analyzing User Password Selection Behavior for Reduction of Password Space. Proceedings of the IEEE International Carnahan Conferences on Security Technology, pp.109-115, 2006.
[5] 	M. Bakker, R. Jagt, GPU-based password cracking, February 5, 2010.
[6] 	M. Weir, S. Aggarwal, B. de Medeiros, B. Glodek, Password Cracking Using Probabilistic Context-Free Grammars, 30th IEEE Symposium on Security and Privacy, 2009.
[7] 	HTTP http://www.openwall.com [cited 2-19-2010] 
[8] 	C. Kuo, S. Romanosky, L. Cranor, “Human Selection of Mnemonic Phrase-based Passwords” Symposium on User Privacy and Security, July 2006, Pittsburg, PA 
[9] 	J. Yan, “A Note on Proactive Password Cracking”, Proceedings of the 2001 workshop on New security paradigms, Pages 127-135, 2001, Cloudcroft, New Mexico 
[10] 	A. Forget, S. Chiasson, P.C. van Oorschot, R. Biddle, “Improving Text Passwords Through Persuasion.” Symposium on Usable Privacy and Security (SOUPS) 2008, July 23–25, 2008, Pittsburgh, PA USA