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

by iok
發佈日期: 更新日期: 1K 人次瀏覽

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)。

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」。

參考資料:

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) 相關的參數,讓我們微調,並針對一般人取密碼的習慣,加快破解速度。

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

相關文章

留言