深入 hashcat 系列：per-position Markov chain attack (上篇)

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

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

這篇我們來談 hashcat 進階功能：「 per-position Markov chain attack」。Markov chain (馬可夫鏈) 是一種隨機過程的統計機率模型。hashcat 進行 Mask attack mode (-a 3) 時，會根據字元的馬可夫鏈機率模型，進行候選密碼字元的排列組合，能更有效率地暴力破解密碼。 並且，預設執行時，就內建開啟此功能。

接下來，請你一起跟我來探詢 hashcat 馬可夫鏈的奧秘吧。

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

Photo by Ian Livesey on StockSnap

什麼是馬可夫鏈 (Markov Chain) ？

馬可夫鏈 (Markov Chain)是一種隨機過程的統計機率模型，定義是下一動的值取決於目前值，並計算所有可能下一動值的機率。下一動的值與前面幾動的值無關。

維基百科的定義是，

What happens next depends only on the state of affairs now.

出處： https://en.wikipedia.org/wiki/Markov_chain

舉個例子。

比方說，你已經猜了 3 次拳，第一次出「剪刀」，第二次出「布」，第三次出「石頭」。經過統計後，接下來要出第 4 次拳，出「石頭」的機率是 0.2、出「布」的機率是 0.3 ，出「剪刀」機率是 0.5 (所有機率加總要等於 1 )，第 4 次出拳的結果跟第 1 次、第 2 次出拳無關。這就是馬可夫鏈機率模型 (Markov chain)。

hashcat 如何應用馬可夫鏈？

當現成字典檔無法成功破解 Hash 時，就得選擇 Mask mode 暴力破解模式 (Attack mode = 3) 。但以往的暴力破解方式，是從 0~9, a~z, A~z, 等一路排列組合，進行列舉破解。

而 hashcat 有更聰明的做法。事先計算常見密碼的馬可夫鏈機率模型，並儲存成 .hcstat2 格式，讓執行時匯入。現在hashcat 執行時，預設即載入已計算好的馬可夫鏈機率模型 (/usr/share/hashcat/hashcat.hcstat2)。

比方說，一般人會選用大小寫字母、數字與特殊符號來組成密碼。「s」字母後面常常是接 「t」字母，「q」字母後面常常是接「u」字母。事先計算字母的馬可夫機率統計模型，並運用在暴力破解中。將比較有可能出現的字母列舉組合，放在候選密碼的前面，有機會讓密碼更快被破解出來。

總而言之，在密碼破解上，應用馬可夫鏈無法減少列舉破解的密碼數量(keyspace)與時間複雜度，但是可以讓密碼更快被破解出來。

舉例來說， 傳統暴力破解，按字母順序列舉印出結果，如下。順序是 a -> b ->c … -> z。

$ hashcat -a 3 --stdout --markov-disable ?l
a
b
c
d
e
f
g
h
i
j
k
l
m
n
o
p
q
r
s
t
u
v
w
x
y
z

使用馬可夫鏈印出的結果，如下。順序是 s -> m -> c -> b …-> x，將使用者取密碼常使用的字母，排在前面。

$ hashcat -a 3  --stdout ?l
s
m
c
b
a
p
l
j
d
t
r
k
h
g
f
n
i
e
w
v
o
y
z
q
u
x

什麼是 per-position？

傳統的 Markov chain( hashcat 參數：--markov-classic) 做法是加總每個位置出現字元的 Markov chain 機率，無論字元是出現在哪一個位置。

但自 2012年起， hashcat 加入了 「per-position」到實做 Markov chain 的程式碼中。做法是針對每個字母位置(最長支援密碼長度 256) ，都單獨計算 Markov chain 機率。

例如第 1 個位置的字母是「s」，後面通常會接「t」。但是，如果「s」是出現在第 7 個位置，後面有可能接的是「e」。

參考資料：

• https://hashcat.net/forum/thread-1285.html
• https://www.trustwave.com/en-us/resources/blogs/spiderlabs-blog/hashcat-per-position-markov-chains/

hashcat 的馬可夫鏈(Markov chain) 相關參數

hashcat 與馬可夫鏈(Markov chain) 有關的參數，摘錄如下：

    --markov-hcstat2           | File | Specify hcstat2 file to use                          | --markov-hcstat2=my.hcstat2
    --markov-disable           |      | Disables markov-chains, emulates classic brute-force |
    --markov-classic           |      | Enables classic markov-chains, no per-position       |
    --markov-inverse           |      | Enables inverse markov-chains, no per-position       |
-t, --markov-threshold         | Num  | Threshold X when to stop accepting new markov-chains | -t 50

markov-hcstat2 <hcstat2 file>

說明：匯入 hcstat2gen 產出的 Markov chain 統計檔 (.hcstat2)(需經過 lzma 壓縮)，不指定參數時，預設載入 /usr/share/hashcat/hashcat.hcstat2。

--markov-disable

說明：關閉馬可夫鏈功能，改為傳統暴力破解列舉。
附註：root_stats_buf, markov_stats_buf 通通填 0

--markov-classic

說明：Markov chain 統計模型不管字母所在位置(no per-position), 把所有字母位置(第1 ~ 第256) 的機率資料加總計算。

--markov-inverse

說明： 2021 年 7 月 7 日加入的新功能。加入了 --markov-inverse 參數新功能。能讓原本的 Markov chain 機率統計模型資料反轉。優先將較使用一般人取密碼時較少使用的字母，放在候選密碼的前面。

ref: https://github.com/hashcat/hashcat/issues/1058

– Added option –markov-inverse to inverse markov statistics, with the idea of reversing the order of the password candidates

原先未使用 --markov-inverse 參數印出的結果，如下。順序是 s -> m -> c -> b …-> x

$ $ hashcat -a 3  --stdout ?l
s
m
c
b
a
p
l
j
d
t
r
k
h
g
f
n
i
e
w
v
o
y
z
q
u
x

使用 --markov-inverse 參數印出的結果，順序是 x -> u -> q -> z … -> s，可以發現字母產出的順序完全顛倒了。

$ hashcat -a 3 --markov-inverse --stdout ?l
x
u
q
z
y
o
v
w
e
i
n
f
g
h
k
r
t
d
j
l
p
a
b
c
m
s

--markov-threshold=NUM

說明：印出前面 <NUM> 字元就結束。不指定參數時，預設是全印。

例如 --markov-threshold=2， 在 hello.hcstat2 機率模型中，「h」與 「w」是第 1 位置出現機率排名前 2 名的字母，排名第 3 名以後的字母就不印了。「e」與「o」是第 2 位置出現機率排名前 2 名的字母，排名第 3 名以後的字母就不印了。

$ hashcat -a 3 --markov-hcstat2 hello.hcstat2 --markov-threshold=2 --stdout ?l?l?l
hel
wel
hor
wor
hea
wea
hoa

小結

hashcat 預設內建的「per-position markov chain attack」功能，並提供了 5 個與馬可夫鏈 (Markov chain) 相關的參數，讓我們微調，並針對一般人取密碼的習慣，加快破解速度。

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