---
tags: Network Security, Password Cracking, DL, FLA, PassGAN
---
<style>
img{
width:70%;
height: auto;
display: block;
margin-left: auto;
margin-right: auto;
}
</style>

# 深度學習與密碼猜測之結合：FLA與PassGAN
###### 名字：謝旻恩 學號：N26100668
## 1. Introduction
密碼可說是最常見的權限認證手段，因為他容易被實現，不需要特別的硬軟體設備即可設定達成。於是密碼破解亦成為網路攻擊手段的一大主題。

根據passcape.com統計，根據常見password list : rockyou.txt，目前網路上流傳常見的密碼長度分布於6~10字元之間，雖然包含大小寫數字的排列組合來說，組合可能非常巨大。然而為了方便記憶密碼，通常人類設置的密碼恐帶有類似的規律性存在。並且相同密碼組合可能會被同時應用在不同的裝置系統上，故駭客便可透過以上人性弱點來試圖猜測密碼，並進一步取得裝置間的機敏資訊。

隨著深度學習的蓬勃發展，許多深度學習的演算法也被應用到密碼猜測的領域進行實作，也獲得了不錯的成果。FLA [1] 使用RNN的技術設計一套有效率、輕量化的密碼猜測演算法，並應用在密碼強度確認的領域中。PassGAN [2] 使用深層對抗網路（Generative Adverserial Network），不再依賴Rulebase的學習，而讓模型自行學習並生成密碼組合。

以下報告我將針對常見的Password Guessing工具與方法進行介紹。並分別針對FLA與PassGAN的模型介紹其原理和貢獻。

## 2. Background

### 2.1 Password Cracking and Guessing
Password Cracking透過不斷嘗試密碼已取得帳戶對應的密碼資訊，是一種十分基礎的資安攻擊模式。目前常見的進行模式為：

**Brute force暴力破解法**：對字元進行窮舉輸入以測試密碼。這樣的方式在毫無限制下雖保證一定能取得密碼，但所耗費的時間過長也浪費運算資源，若只考慮大小寫字母與數字共62個字元，嘗試六到十個字元的暴力破解，則有62^6^+62^7^+62^8^+62^9^+62^10^種可能性，通常會希望利用特定的規則來降低猜測的數量。

**Dictionary attack字典攻擊**：建立一份可能性高的密碼組合表單，以此降低測試的數量。這份字典的組合可能來自過去曾被破解過的密碼、或是依照人類常見設定密碼的規則，組合成的新的密碼，比如語詞組合（iloveyou123）、字母混和（iLoVeyOu）或火星文（ilov3you）。

雖然這些Password Cracking的攻擊，只要系統限定密碼登入的次數、設定認證碼或圖片認證、設定防火牆，即無法攻擊。然而仍可能出現以下情境，使密碼破解成為威脅。

1. 若系統開發並未妥當做好安全設定，線上密碼破解即為可能的事。其中例如2014年發生名人私密照從Apple iCloud流出，即是透過Find My Phone service API並未針對brute force施行保護而產生的資安漏洞事件。[3]
2. 若password hashing的資料庫被偷取，駭客即能透過offline的方式進行密碼破解。駭客將密碼dictionary經過加密的hashing，生成出一張hashing list，並將這份名單與用戶的密碼hashing進行配對。

駭客透過以上兩種狀況破解密碼後，可再憑藉人類傾向重複使用同一份密碼的習慣，對該用戶的不同系統帳戶進行Password Reuse Attack。在2016便發生一起案例，駭客取得一份網頁上9900萬個用戶名帳密資料庫，隨後對同時註冊中國淘寶的用戶進行Password Reuse攻擊，影響高達2000萬名用戶。[4]

3. 密碼存管系統雖協助使用者存取密碼、建議高強度密碼並自動填入密碼，然而其系統仍是透過使用者設定的密碼，而人類設定的密碼即有可能透過Password guessing的方式進一步的破解。

### 2.2 Probabilistic method
以下我將介紹Probabilistic的password guessing方法，這些方法不依賴神經網路，先針對輸入password set進行處理，經過機率模型後，依機率大小輸出新的password combinations。

**Probabilistic Context-Free Grammars**：PCFG試圖以數學機率模型找出文本後設的語法規則。曾被應用在RNA序列的研究中。一個PCFG的G可被定義為[5]：

$$ G = (M,T,R,S,P) $$

- M is the set of non-terminal symbols
- T is the set of terminal symbols
- R is the set of production rules
- S is the start symbol
- P is the set of probabilities on production rules

PCFG認為密碼是由特定的結構字元組成，如六個英文字母與兩個數字。並由Terminal決定密碼延續的結束字元機率。

**Markov Models**：Markov models利用前面已排列的字元，去預測下一個字元的可能機率。比如在一個5-gram Markov model要對"ilovey"的下一個字元做預測，便會以"lovey"對下一個字元可能機率預測，而"o"是最大可能機率的字元。

Markov model容易預測出語意性字串，這雖然是人類慣用性密碼的表現，但也容易導致overfitting，近年來有許多針對Markov model Password guessing的研究。

**Mangled Wordlist Methods**：針對特定字語進行隨意雜湊規則，比如將其打亂，或是做字元更換如'a'與'@'、'e'與'3'。這樣的密碼生成規則雖然並非基於機率模型，但對密碼猜測十分有幫助，故被廣泛使用，包含John the Ripper和Hashcat。

## 3. Fast, lean, and accurate: Modeling password guessability using neural networks.
2016發布於25^th^Usenix Security Symposium，提出使用RNN model的神經網路模型。關於neural network應用在password guessing的論文不算多，而這篇算是近年來最早的一篇論文。

而FLA的模型為了讓password guessing能應用在password strength checking的應用上，於是模型秉持的輕量化與預測效率的原則，模型控制在數百kb內，提供client-side model javascript的pasword strength checking的介面。

**Model Design**：password guessing型式類似markov chain的做法。使用RNN模型基於目前的密碼字串對下一個字元的預測（大小寫、英文、END）。而如何表示一組密碼的強度，即透過把此系列預測序列的機率相乘即可表示。



依此方式，FLA模型可依據字串序列建成一棵機率樹，透過beam-search演算法（a hybrid of depth/breadth search）將機率順位高並符合規則的密碼組成序列。此列表即能成為password guessing的破解dictionary順序，也可提供成為password strength checking的依據。

**Guessing Effectiveness**：論文比較PCFG, Markov chain, JtR, Hashcat與輕量化FLA模型間的使用資源與預測效率。以下可見FLA使用的資源容量極低，而在預測表現上隨著資料集難度增加，PCFG, JtR, Hashcat的表現遠遠不如Markov chain和FLA的機率模型。

並且FLA的表現幾乎與透過MinGuess策略（將每種策略搭配進行猜測）表現相差不遠。可見FLA模型優秀的表現。

>FLA effective model：60mb
PCFGs：4.7gb
Markov chain：1.1gb
JtR, Hashcat：756mb


## 4. PassGAN: A deep learning approach for password guessing.
2017年首先提出，並在2019年發布於International Conference on Applied Cryptography and Network Security。提出使用深層對抗網路（Gernerative Adverserial Network）的方式生成密碼。

透過GAN模型訓練的好處，是過去的訓練模型都是基於讓模型去學習現有資料集的潛在規律，但透過Generative model讓模型從0開始去臨摹人類密碼設計的規則，這樣不受限於現有資料集的束縛，並也更能生成獨特且大量的密碼組合。

**Model Design**：模型參考IWGAN，使用RESNET的Residual block特性作為Backbone的設計基礎。而因應文字序列使用1D-conv，在Gernerator和Discriminator各使用了五層residual block。

**Evaluation**：雖說本論文宣稱達到state of the art，然而依照PassGAN的實驗結果來看，PassGAN需要比起前述方式（PSFG,FLA,Markov,JtR,Hashcat）更多的猜測步數，才能達到於testing data中相同的猜中率。顯然此篇論文更著重於密碼可生成的多樣性，而非FLA論文注重的猜測效率與模型資源大小。

作者於論文中建議可把JtR或Hashcat工具用做第一步的guessing tool，並以PassGAN做為前者密碼集用盡的輔助。然而我個人認為基於機率模型（FLA, Markov chain）的機率降序猜測更符合實務，這些模型可對密碼出現機率進行排名以做猜測，這大大提升了猜測的命中效率和準確度。

## 5. Conclusion
在深度學習技術迅速發展的時代，雖讓資安保護（如封包檢測）提供強大策略，但也使攻擊手段有所受益，在Password Guessing的領域中我們看到FLA更強大的Guessing效能，與PassGAN對人類密碼模式的臨摹。Password Guessing雖然是相對基礎且容易防範的策略，但若在系統開發過程中忽略了資安防護，仍可能讓這樣的攻擊趁虛而入，且密碼外洩所造成的後續傷害可能可以十分可觀。

## 6. Reference
[1] [Melicher, W., Ur, B., Segreti, S. M., Komanduri, S., Bauer, L., Christin, N., & Cranor, L. F. (2016). Fast, lean, and accurate: Modeling password guessability using neural networks. In 25th {USENIX} Security Symposium ({USENIX} Security 16) (pp. 175-191).](https://www.usenix.org/conference/usenixsecurity16/technical-sessions/presentation/melicher)

[2] [Hitaj, B., Gasti, P., Ateniese, G., & Perez-Cruz, F. (2019, June). Passgan: A deep learning approach for password guessing. In International Conference on Applied Cryptography and Network Security (pp. 217-237). Springer, Cham.](https://link.springer.com/chapter/10.1007/978-3-030-21568-2_11)

[3] [iCloud password hack published, blocked as celebrity photo theft confirmed [Updated: Apple comment]](https://www.engadget.com/2014-09-01-icloud-password-hacking-tool-published-blocked-amidst-celebrity.html)

[4] [Hackers attack 20 million accounts on Alibaba's Taobao shopping site](https://news.yahoo.com/hackers-attack-20-million-accounts-alibabas-taobao-shopping-102144632--finance.html)

[5] [Probabilistic context-free grammar - Wikipedia](https://en.wikipedia.org/wiki/Probabilistic_context-free_grammar)

[6] [USENIX Security '16 - Fast, Lean, and Accurate: Modeling Password Guessability Using Neural Networks](https://www.youtube.com/watch?v=GgaZ_LxsL_8&t=349s)