hcstatgen 篇: per-position Markov chain attack – 深入 hashcat 系列文章

hashcat 是一套開源 (MIT License) 的離線密碼破解軟體，還能利用顯示卡 GPU 加快破解速度。其官網宣稱是「世界上最快的密碼破解工具」，廣泛支援許多常用的雜湊值演算法，以及破解攻擊模式。

「深入 hashcat 系列」是針對想要深耕資安領域的你，所撰寫的一系列文章。每篇文章針對 hashcat 其中一個參數、參數值或功能，進行說明，並搭配實做指令範例，幫助你快速掌握 hashcat 。

在上一篇文章中，我們談到 hashcat 進階功能：「 per-position Markov chain attack」，介紹了 hashcat 如何應用馬可夫鏈、什麼是 per-position，以及 hashcat 的馬可夫鏈(Markov chain) 相關參數。Markov chain (馬可夫鏈) 是一種隨機過程的統計機率模型，如果讀者還不熟悉馬可夫鏈，可以點選上一篇文章溫習。

這篇要延續上篇，繼續來談「hashcat 與 馬可夫鏈 (Markov chain) 相關的工具程式 」。hashcat 為了能夠讓使用者自行產生馬可夫鏈 (Markov chain) 的統計檔案 (stat 檔)，專案亦一併釋出了 hcstatgen、hcstat2bin、sp64 工具程式。

這篇文章會先來講解 hcstagen 的原理。接下來，請你一起來探尋 hcstatgen 工具程式的原理奧秘吧！

＊請留意文章中提到的工具軟體，請在授權環境下執行測試與使用，禁止在非授權環境下執行！

Photo by Ian Livesey on StockSnap

hcstatgen 工具程式簡介

hcstatgen 是 hashcat 第一代的馬可夫鏈統計資料模型的儲存格式產生程式，最長支援匯入的密碼長度到 64 個字元。但最新的 hashcat 程式 (v6.2.6) 已不支援此格式。hcstatgen 需搭配 statsprocessor 工具程式一起使用。

雖然 hashcat 已不再支援此格式，但因 hcstagen 程式碼十分簡潔，容易理解。要了解 hashcat 馬可夫鏈 (Markov chain) 實做程式碼，從這支程式原始碼 (hcstatgen.c) 下手會較容易。

Kali Linux 使用者，請安裝 hashcat-utils 套件，來使用 hcstatgen 。安裝路徑在 /usr/lib/hashcat-utils/hcstatgen.bin，後續的程式摘要，為了縮短篇幅，統一使用 hcstatgen代替。

Kali Linux 的安裝方式如下：

$ sudo apt install hashcat-utils

讀者可使用 alias 設定 hcstatgen，方便執行文章後面提到的指令。

$ alias hcstatgen="/usr/lib/hashcat-utils/hcstatgen.bin"

hcstatgen 使用方式

1. 先準備一個文字檔，比方說是 hello.txt，內容如下：

$ cat hello.txt
hello
world

2. 使用 hcstatgen 產生馬可夫鏈的機率模型檔案 (hello.stat)，指令如下：

$ hcstatgen hello.stat < hello.txt

3. 使用 hexdump 讀取 hello.stat ，可以看到大部分的資料為 0 ，僅有少部份的行數裡面有填值 1、2。為什麼填 0 、1、2 ，我們會在後面篇幅 「hello.stat 的資料結構」中解釋。

$ hexdump hello.stat
0000000 0000 0000 0000 0000 0000 0000 0000 0000
*
0000340 0001 0000 0000 0000 0000 0000 0000 0000
0000350 0000 0000 0000 0000 0000 0000 0000 0000
*
00003b0 0000 0000 0000 0000 0001 0000 0000 0000
00003c0 0000 0000 0000 0000 0000 0000 0000 0000
*
0000b20 0000 0000 0000 0000 0001 0000 0000 0000
0000b30 0000 0000 0000 0000 0000 0000 0000 0000
*
0000b70 0000 0000 0000 0000 0001 0000 0000 0000
0000b80 0000 0000 0000 0000 0000 0000 0000 0000
*
0001360 0001 0000 0000 0000 0000 0000 0000 0000
0001370 0000 0000 0000 0000 0000 0000 0000 0000
*
0001390 0001 0000 0000 0000 0000 0000 0000 0000
00013a0 0000 0000 0000 0000 0000 0000 0000 0000
*
0001b60 0002 0000 0000 0000 0000 0000 0000 0000
0001b70 0000 0000 0000 0000 0000 0000 0000 0000
*
0002320 0001 0000 0000 0000 0000 0000 0000 0000
0002330 0000 0000 0000 0000 0000 0000 0000 0000
*
0002370 0000 0000 0000 0000 0001 0000 0000 0000
0002380 0000 0000 0000 0000 0000 0000 0000 0000
*
0054320 0000 0000 0000 0000 0001 0000 0000 0000
0054330 0000 0000 0000 0000 0000 0000 0000 0000
*
005bb70 0000 0000 0000 0000 0001 0000 0000 0000
005bb80 0000 0000 0000 0000 0000 0000 0000 0000
*
00d2b60 0001 0000 0000 0000 0000 0000 0000 0000
00d2b70 0000 0000 0000 0000 0000 0000 0000 0000
*
00d7b90 0001 0000 0000 0000 0000 0000 0000 0000
00d7ba0 0000 0000 0000 0000 0000 0000 0000 0000
*
0156360 0001 0000 0000 0000 0000 0000 0000 0000
0156370 0000 0000 0000 0000 0000 0000 0000 0000
*
0159360 0001 0000 0000 0000 0000 0000 0000 0000
0159370 0000 0000 0000 0000 0000 0000 0000 0000
*
01d6320 0001 0000 0000 0000 0000 0000 0000 0000
01d6330 0000 0000 0000 0000 0000 0000 0000 0000
*
01d6370 0000 0000 0000 0000 0001 0000 0000 0000
01d6380 0000 0000 0000 0000 0000 0000 0000 0000
*
2020000

hello.stat 的資料結構

hcstatgen.c 程式裡有 2 個關鍵的變數，一是 root_stats_buf，另一個是 markov_stats_buf ，分別對應到作業系統某個記憶體空間(呼叫 calloc() 取得)。程式讀取文字檔後，會填入馬卡夫鏈統計機率模型資料至 root_stats_buf 與 markov_stats_buf 變數中，並將root_stats_buf 與 markov_stats_buf 的記憶體內容依序寫入 (fwrite) 至 hello.stat 檔案中。hello.stat 檔案即產生完成。

root_stats_buf

root_stats_buf 是 uint64_t 指標，指向 1 塊 size 為 131,072 bytes (約 128 Kb) 的記憶體空間，131,072 bytes = 64 (最長密碼長度) x 256(CHARSIZ) x 8 bytes (uint64_t size)。負責儲存馬可夫鏈統計機率模型中，代表每個位置 (per-position) 的每個字母出現次數 。

root_stats_buf_by_pos 

root_stats_buf_by_pos 是  root_stats_buf 相關的指標變數 ，是 2 維稀疏矩陣root_stats_buf_by_pos[0] ~ root_stats_by_pos[64] 循序對應到 root_stats_buf 的記憶體位址，每 1 個 root_stats_buf_by_pos[] 的 size 是 256 (CHARSIZE)。

比方說，hello.txt 裡面有 單字1: hello， 單字2: world

$ cat hello.txt
hello
world 

要填寫馬可夫鏈統計機率模型資料中，每個位置 (per-position) 的每個字母出現次數 ，在 root_stats_buf_by_pos 儲存寫法，如下：

root_stats_buf_by_pos[0]['h'] += 1
root_stats_buf_by_pos[1]['e'] += 1
root_stats_buf_by_pos[2]['l'] += 1
root_stats_buf_by_pos[3]['l'] += 1
root_stats_buf_by_pos[4]['o'] += 1

root_stats_buf_by_pos[0]['w'] += 1
root_stats_buf_by_pos[1]['o'] += 1
root_stats_buf_by_pos[2]['r'] += 1
root_stats_buf_by_pos[3]['l'] += 1
root_stats_buf_by_pos[4]['d'] += 1

root_stats_buf_by_pos 足標[0]、[1] … [4] 代表是字母的位置，像 h 是第 1 個位置的字母，統計方式就是 root_stats_buf_by_pos[0]['h'] += 1 。e 是第 2 個位置的字母，統計方式就是 root_stats_buf_by_pos[1]['e'] += 1 。

其餘沒有在單字裡面的字母，數值填 0。儲存寫法如下：

root_stats_buf_by_pos[0]['a'] = 0
root_stats_buf_by_pos[0]['b'] = 0
root_stats_buf_by_pos[0]['c'] = 0
...
root_stats_buf_by_pos[4]['x'] = 0
root_stats_buf_by_pos[4]['y'] = 0
root_stats_buf_by_pos[4]['z'] = 0

在這邊是方便舉例，假設最後一個字元為 z，實際上應該是某一個特殊符號

markov_stats_buf

markov_stats_buf是 uint64_t 指標，指向 1 塊 size 為 33,554,432 bytes (約 32768 KB, 32 MB) 的記憶體空間，33,554,432 bytes = 64 (最長密碼長度) x 256(CHARSIZ) x 256 (CHARSIZE) x 8 bytes (uint64_t size)。負責儲存馬可夫鏈統計機率模型中，每個位置 (per-position) 的字母跟相鄰字母 出現次數。

markov_stats_buf_by_key 

 markov_stats_buf_by_key是與 markov_stats_buf 相關的指標變數 ，是 3 維稀疏矩陣。markov_stats_buf_by_key[0][0] ~ markov_stats_by_key[64][256] 循序對應到 markov_stats_buf 的記憶體位址，每 1 個 markov_stats_buf_by_key[][] 的 size 是 256 (CHARSIZE)。比方說, 單字1: hello, 單字2: world，要填寫馬可夫鏈統計機率模型資料中，每個位置 (per-position) 的字母跟相鄰字母出現次數，在 markov_stats_buf_by_key 儲存寫法，如下：

markov_stats_buf_by_pos[0]['h']['e'] += 1
markov_stats_buf_by_pos[1]['e']['l'] += 1
markov_stats_buf_by_pos[2]['l']['l'] += 1
markov_stats_buf_by_pos[3]['l']['o'] += 1

markov_stats_buf_by_pos[0]['w']['o'] += 1
markov_stats_buf_by_pos[1]['o']['r'] += 1
markov_stats_buf_by_pos[2]['r']['l'] += 1
markov_stats_buf_by_pos[3]['l']['d'] += 1

其餘沒有在單字裡面的字母，數值填 0，儲存寫法如下：

markov_stats_buf_by_pos[0]['a']['a'] = 0
markov_stats_buf_by_pos[0]['a']['b'] = 0
markov_stats_buf_by_pos[0]['a']['c'] = 0
...
markov_stats_buf_by_pos[4]['z']['x'] = 0
markov_stats_buf_by_pos[4]['z']['y'] = 0
markov_stats_buf_by_pos[4]['z']['z'] = 0

在此是方便舉例，假設最後一個字元為 z，實際上應該是某一個特殊符號。

之後一行一行讀完 hello.txt 檔案內全部的單字後，填入馬卡夫鏈統計資料後，再依序把 root_stats_buf 與 markov_stats_buf 的資料寫入檔案中，便完成 hello.stat 檔案。

小結

我花了幾個禮拜爬疏了 hcstatgen 的原始碼，把追 code 過程 Memo 下來並撰寫這篇文章。在這邊文章中介紹 hcstatgen 簡介 、使用方式與 stat 檔案的資料結構，希望對讀者有幫助。

若你喜歡這篇文章，請幫我分享給你的好朋友，並且在底下留言鼓勵我。期待在下篇，再與你見面。