基於鍵盤及公開密碼特徵所學習知識之密碼猜測方法

Password Cracking Based on Knowledge Learned from Keyboard and Disclosed Password Patterns

周憲政(Hsien-Cheng Chou)

指導教授 ： 賴飛羆

國立臺灣大學/電機資訊學院/資訊工程學研究所/博士(2012年)

https://doi.org/10.6342/NTU.2012.10299

摘要

目前用來保護敏感資訊的加密機制，多數仍以密碼為基礎的身分驗證系統最常被使用，儘管這些驗證方法會遭遇到字典攻擊法之攻擊。為了避免這些攻擊，很多部門或單位會強迫使用者必須使用較複雜之密碼，並且要求密碼中必須包括數字及特殊符號等字元。本論文提出一個論點，祇要使用者所選用的密碼不會過於難記憶，則這些密碼仍有可能會遭遇到經過特別訓練所產生字典之攻擊。一種最常看到的手段就是使用鍵盤上的態樣(Patterns)作為密碼，也就是依照鍵盤上的鍵盤位置，來產生較複雜之密碼。針對以鍵盤規則所產生的密碼，本篇論文站在一個攻擊者的立場，提出一個實質有效的攻擊方法。我們設計一個工作平台，先針對鍵盤上最常被使用之相鄰及平行關係產生相對應之鍵盤規則，稱之為AP patterns，再根據這些規則產生攻研用之密碼資料庫。經實驗證實，利用我們方法所產生的密碼空間比起窮舉法(Brute-Force Attack)，可大幅縮小244.47倍。同時，我們也設計一個混合式密碼猜測系統來證明其運算效能。實驗結果顯示，加入我們之AP patterns，可使平均攻研效能提升114%。
除了對鍵盤攻擊法之研究外，我們也開發出一個密碼分析平台，用來有系統地分析使用者所使用密碼之特性，並且辨識分類及計算這些密碼的規則及對應的機率值。以這些密碼規則為基礎，我們建立一個由訓練集、字典集及測試集等3個集合所組成的模組，稱為TDT-Model，利用此模組來生成機率值從大到小的密碼資料庫。利用此模組可大幅降低所蒐尋的密碼空間，提升攻研效能。經實驗證實，運用TDT-Model方法所產生的密碼，所攻獲的密碼為John-the-Ripper的1.58倍，為Brute-Force Attack的2.82倍。同時，將本方法結合所設計的混合式密碼猜測系統，實際應用於攻研UNIX系統的通行密碼，發現其攻研效能可提升297%。

關鍵字

密碼破解 ； 字典攻擊法 ； 窮舉法 ； 鍵盤攻擊法 ； TDT-Model攻擊法 ； John-the-Ripper 攻擊法 ； 混合式密碼猜測系統

並列摘要

Password-based authentication systems are still the most commonly used mechanism for protecting sensitive information despite being vulnerable to dictionary- based attacks. Against such attacks, many organizations enforce complicated password-creation rules and require that passwords include numeric and special characters. This study demonstrates that as long as passwords are not difficult to remember, they remain vulnerable to “smart dictionary” attacks. One commonly used “trick” is to use keyboard patterns, i.e., key patterns on a keyboard, to create passwords that conform to the complex rules. This thesis proposes an efficient and effective method to attack passwords generated from some special keyboard patterns. We create a framework to formally describe the commonly used keyboard patterns of adjacent keys and parallel keys, called AP patterns, to generate password databases. Our simulation results show that the password space generated using AP patterns is about 244.47 times smaller than that generated for a Brute-Force attack. We also design a hybrid password cracking system consisting of different attacking methods to verify the effectiveness. Our results show that the number of passwords cracked increases by up to 114% on average than those without applying AP patterns.
In addition to the study of keyboard attack, we also develop a password analysis platform to formally analyze commonly used passwords and to identify frequently used password patterns and their associated probabilities. Based on these patterns, a model with a Training set, a Dictionary set and a Testing set (TDT-Model), is used to generate probabilistic passwords sorted in decreasing order. The model can be used to dramatically reduce the size of the password space to be searched. The simulation results show that the number of passwords cracked using the TDT-Model is 1.58 and 2.82 times higher compared to the John-the-Ripper attack and Brute-Force attack, respectively. We also apply the hybrid password cracking system combining different attacks to verify the effectiveness of the proposed method. After applying the TDT-Model, the number of passwords cracked increased by up to 297%.

並列關鍵字

Password cracking ； Dictionary attack ； Brute-Force attack ； Keyboard attack ； TDT-Model attack ； John-the-Ripper attack ； Hybrid password cracking system

參考文獻

[1] H. Gao, X. Liu, S. Wang, H. Liu, R. Dai, Design and Analysis of a Graphical Password Scheme, International Conference of Innovative Computing, Information and Control, pp. 675-678, 2009.

[2] D. Davis, F. Monrose, and M. K. Reiter, On User Choice in Graphical Password Schemes, Proceedings of the 13th USENIX Security Symposium, 2004.

[3] M. Bellare, D. Pointcheval, P. Rogaway, Authenticated Key Exchange Against Dictionary Attack, Advances in Cryptology - EUROCRYPT’00, Lecture in Computer Science, Springer-Verlag, 2000.

[4] S. Delaune, F. Jacquemard, A Theory of Dictionary Attacks and its Complexity, 17th IEEE Computer Security Foundations Workshop, 2004.

[5] S. Bellovin, M. Merritt, Encrypted Key Exchange: Password-based Protocols Secure against Dictionary Attacks, Proceedings of the Symposium on Security and Privacy, pp. 72-84, IEEE, 1992.