ctf-wiki 哈希攻擊實戰指南：暴力破解、長度擴展攻擊與可逆哈希逆向

文档网络安全教程【免费下载链接】ctf-wikiCome and join us, we need you!项目地址https://gitcode.com/gh_mirrors/ct/ctf-wiki点击查看免费下载本篇技術指南以 ctf-wiki 的哈希攻擊章節為主體系統梳理 CTF 密碼學中針對哈希函數的兩大攻擊思路——依賴摘要長度的暴力攻擊生日攻擊、中點交會攻擊與依賴算法設計缺點的密碼分析哈希長度擴展攻擊、可逆自定義哈希。讀完後你將掌握哈希長度擴展攻擊的完整原理推導、HashPump 工具的使用方式以及如何識別並逆向一類輪內使用異或XOR組合的可逆自定義哈希並能直接在 CTF 中復用本文給出的完整解密腳本。哈希攻擊的兩大分類常見的哈希函數攻擊方法主要分為兩大類暴力攻擊不依賴於任何算法細節僅與 Hash 值長度有關。其下又有兩種代表性方法生日攻擊法Birthday Attack沒有利用哈希函數的結構和任何代數弱性質只依賴於消息摘要的長度即 Hash 值的長度。其理論基礎是生日悖論——當樣本數量達到摘要空間大小的平方根量級時發生碰撞的概率就足夠高。中點交會攻擊法Meet-In-The-Middle生日攻擊的一種變形不直接比較 Hash 值而是比較中間變量。這種攻擊主要適用於攻擊具有分組鏈結構的哈希方案。密碼分析依賴於具體算法的設計缺點例如下文要講解的哈希長度擴展攻擊以及針對自定義可逆哈希的逆向。在深入攻擊手段之前先回顧哈希函數本身需要滿足的基本性質。倉庫中的 哈希函數基礎 一文給出了完整的需求表輸入長度可變、輸出長度固定、計算高效、單向性給定H(x)h求x計算上不可行、抗弱碰撞性、抗強碰撞性以及偽隨機性。攻擊的本質就是在某個性質上找到破壞點——暴力攻擊破壞的是「碰撞困難」長度擴展攻擊破壞的則是「偽隨機性」與「單向性」在特定構造下的失效。暴力破解實戰HashCat 工具對於基於字典的暴力破解場景原文檔將HashCat描述為目前基於 CPU 和 GPU 破解 Hash 的主流工具它支持幾乎所有常見哈希算法MD5、SHA 系列、NTLM、bcrypt 等的字典攻擊、規則攻擊、掩碼攻擊與組合攻擊並能充分利用 GPU 的並行計算能力。CTF 中常見的用法是拿到一個未知明文哈希後先用內置字典如 rockyou跑一遍字典攻擊再配合規則變形處理常見的密碼變體。值得注意的是HashCat 的適用前提是「目標明文存在於字典或可窮舉的空間內」一旦哈希的構造刻意破壞了這一前提例如下文 Hashinator 題目中salt password的長度被強制拉長到 128 字節字典與彩虹表思路就會失效此時需要轉向算法本身的結構分析。哈希長度擴展攻擊Hash Length Extension Attack什麼是哈希長度擴展攻擊哈希長度擴展攻擊是指針對某些允許包含額外信息的加密散列函數的攻擊手段。該攻擊適用於在消息與密鑰的長度已知的情形下所有採取了H(key ∥ message)此類構造的散列函數。MD5 和 SHA-1 等基於 Merkle–Damgård 構造的算法均對此類攻擊顯示出脆弱性。這類哈希函數有以下特點消息填充方式都比較類似首先在消息後面添加一個1然後填充若干個0直至總長度與 448 同餘最後在其後附上 64 位的消息長度填充前的長度。以 SHA-1 為例倉庫 SHA1 基礎 中明確說明其分組長度為512 比特先在消息右側補比特 1再補若干個比特 0直到消息的比特長度對 512 取模後餘數是 448。每一塊得到的鏈接變量都會被作為下一次執行 hash 函數的初始向量 IV。在最後一塊的時候才會將其對應的鏈接變量轉換為 hash 值。攻擊適用條件一般攻擊時應滿足如下條件我們已知key的長度如果不知道的話需要爆破出來我們可以控制message的內容我們已經知道了包含key的一個消息的 hash 值。滿足這些條件後我們就可以得到一對(message, x)滿足x H(key ∥ message)雖然我們並不清楚key的內容。攻擊原理推導不妨假設我們知道了hash(key s)的 hash 值其中s是已知的。那麼這個值在計算的時候必然會進行填充。我們首先可以得到key s擴展後的字符串now即now key | s | padding那麼如果我們在now的後面再次附加上一部分信息extra即key | s | padding | extra這樣再去計算 hash 值的時候會對extra進行填充直到滿足條件先計算now對應的鏈接變量IV1而我們已經知道這部分的 hash 值並且鏈接變量產生 hash 值的算法是可逆的所以我們可以得到鏈接變量下面會根據得到的鏈接變量IV1對extra部分進行哈希算法並返回 hash 值。那麼既然我們已經知道了第一部分的 hash 值並且還知道extra的值我們便可以得到最後的 hash 值。而之前我們也說了我們可以控制message的值那麼其實s、padding、extra我們都是可以控制的。所以我們自然可以找到對應的(message, x)滿足x hash(key | message)。攻擊的本質在於Merkle–Damgård 結構的輸出就是最後一個分組的鏈接變量而鏈接變量本身就是下一輪計算的 IV。因此知道H(key ∥ s)的輸出等價於知道「以該輸出為 IV 繼續哈希任意後綴」的計算起點——攻擊者無需知道key就能偽造出任意key ∥ s ∥ padding ∥ extra的合法哈希。這在 Web 場景中典型的危害是當後端用H(secret ∥ message)作為簽名或 MAC 時攻擊者可以偽造message之後任意附加數據的簽名。實戰工具HashPump原文檔推薦的實戰工具是HashPump其作用正是將上述原理自動化輸入已知的哈希值、已知數據、要附加的數據以及猜測的密鑰長度工具即可計算出填充位元組與附加數據後的完整偽造消息及其新哈希。具體使用方式編譯、命令行參數格式請參考該工具發布頁面的 README 說明。相關背景從初始化 IV 識別 MD5 與 SHA-1在逆向遇到未知哈希函數時可以通過函數初始化常量來快速識別算法族。倉庫 MD5 基礎 指出如果一個函數包含如下四個初始化變量基本可以斷定是 MD5 函數的初始化 IV0x674523010xEFCDAB890x98BADCFE0x10325476而 SHA1 基礎 指出 SHA-1 在上述四個變量之外新增了第五個常量0x67452301 0xEFCDAB89 0x98BADCFE 0x10325476 0xC3D2E1F0這四個/五個常量是 MD5 與 SHA-1 壓縮函數的公開設計參數也是逆向分析時判斷算法類型的快捷標誌。哈希算法設計缺陷可逆哈希與 Hashinator 題目一些自定義的哈希算法可能是可逆的。原文檔以Hashinator這道題為例完整演示了如何識別並利用這一設計缺陷。該題目同時對應簡體中文版本 attack.md。題目邏輯題目的邏輯很簡單從一個知名的密碼字典rockyou中挑選出一個password並且使用多種哈希算法隨機哈希 32 輪。我們需要從最後的哈希結果中破解出原始的password。題目採用的哈希算法有md5、sha1、blake、scrypt。關鍵的代碼如下password self.generate_password() # from rock_you.txt salt self.generate_salt(password) # 與password的長度有關 hash_rounds self.generate_rounds() # 生成進行hash算法的順序 password_hash self.calculate_hash(salt password, hash_rounds)程序首先從rockyou.txt中隨機抽取一個password作為加密的明文然後根據抽取的password的長度生成一個長度為128 - len(password)的salt從之前列舉的 4 種哈希算法中抽取組成 32 輪的哈希運算根據之前得到的password、salt計算出最後給我們的password_hash。思路分析為何不能窮舉很明顯我們不可能通過逆向哈希算法本身來完成題目。我們知道所有可能的明文首先考慮能否通過構造彩虹表來完成窮舉。但是注意到generate_salt()函數中salt和password的長度組合超過了 128 byte 的長度並且代碼中特意註釋了msize 128 # f-you hashcat :D這行註釋說明出題人刻意用鹽把總長度固定在 128 字節使字典攻擊與彩虹表攻擊完全失效——salt是隨機生成且與password綁定的無法預先離線構造彩虹表。那這樣的話只存在一種可能算法可逆。查看calculate_hash()函數的具體實現可以發現如下可疑的代碼for i in range(len(hash_rounds)): interim_salt xor(interim_salt, hash_rounds-1-i) interim_hash xor(interim_hash, hash_roundsi) final_hash interim_salt interim_hash重新梳理一下我們知道的信息hash_rounds中保存了 32 輪即每輪要使用的哈希函數句柄final_hash是最後給我們的哈希結果hash_rounds中的內容也會在生成之後打印給我們我們希望得到interim_salt和interim_hash在第一輪的值interim_salt和interim_hash的長度均為 64 byte。可逆性推導仔細觀察interim_salt和interim_hash的計算方法可以發現它是可逆的。核心等式如下$$ interim_hash_1 interim_hash_2 \oplus hash_roundsi $$這行代碼裡我們已知interim_hash_1和interim_salt_3由此可以推出interim_hash_2的值而interim_hash_2則是上一輪的interim_hash。之所以可逆關鍵在於整個循環裡每一輪的輸入輸出都是公開可推導的正向計算時interim_salt的更新只依賴於上一輪的interim_hash而interim_hash的更新只依賴於更新後的interim_salt由於異或是自反運算a b ⊕ c可推出b a ⊕ c且哈希函數句柄md5、sha1、blake、scrypt與每輪順序都公開因此可以嚴格按相反順序逐輪逆推。以此方法逆推 32 次則可以得到最初的password和salt。解密腳本原文檔給出的完整解密腳本如下使用 pwntools 的remote與服務端交互先讀取挑戰數據再按逆序還原import os import hashlib import socket import threading import socketserver import struct import time import threading # import pyscrypt from base64 import b64encode, b64decode from pwn import * def md5(bytestring): return hashlib.md5(bytestring).digest() def sha(bytestring): return hashlib.sha1(bytestring).digest() def blake(bytestring): return hashlib.blake2b(bytestring).digest() def scrypt(bytestring): l int(len(bytestring) / 2) salt bytestring[:l] p bytestring[l:] return hashlib.scrypt(p, saltsalt, n2**16, r8, p1, maxmem67111936) # return pyscrypt.hash(p, salt, 2**16, 8, 1, dkLen64) def xor(s1, s2): return b.join([bytes([s1[i] ^ s2[i % len(s2)]]) for i in range(len(s1))]) def main(): # io socket.socket(familysocket.AF_INET) # io.connect((47.88.216.38, 20013)) io remote(47.88.216.38, 20013) print(io.recv(1000)) ans_array bytearray() while True: buf io.recv(1) if buf: ans_array.extend(buf) if buf b!: break password_hash_base64 ans_array[ans_array.find(bb) 2: ans_array.find(b\n)] password_hash b64decode(password_hash_base64) print(password:, password_hash) method_bytes ans_array[ ans_array.find(bused:\n) 6 : ans_array.find(b\nYour) ] methods method_bytes.split(b\n) methods [bytes(x.strip(b- )).decode() for x in methods] print(methods) in_salt password_hash[:64] in_hash password_hash[64:] for pos, neg in zip(methods, methods[::-1]): interim_salt xor(interim_salt, hash_rounds-1-i) interim_hash xor(interim_hash, hash_roundsi) in_hash xor(in_hash, eval({}(in_salt).format(neg))) in_salt xor(in_salt, eval({}(in_hash).format(pos))) print(in_hash, in_salt) print(in_hash[-20:]) io.interactive() main()腳本的關鍵在於for pos, neg in zip(methods, methods[::-1])正向 32 輪中第i輪用hash_rounds[i]更新interim_hash、用hash_rounds[-1-i]更新interim_salt因此逆向時必須用正序與逆序配對的方式逐輪還原neg對應正向最後一輪使用的函數pos對應正向第一輪使用的函數。逆向完成後in_hash[-20:]即為原始password的末尾 20 字節可直接提交給服務端驗證。原始哈希算法為完整理解逆向過程原文檔同時給出了服務端的原始實現HashHandler繼承自socketserver.BaseRequestHandlerThreadedTCPServer啟用allow_reuse_address True監聽在0.0.0.0:1337import os import hashlib import socket import threading import socketserver import struct import time # import pyscrypt from base64 import b64encode def md5(bytestring): return hashlib.md5(bytestring).digest() def sha(bytestring): return hashlib.sha1(bytestring).digest() def blake(bytestring): return hashlib.blake2b(bytestring).digest() def scrypt(bytestring): l int(len(bytestring) / 2) salt bytestring[:l] p bytestring[l:] return hashlib.scrypt(p, saltsalt, n2**16, r8, p1, maxmem67111936) # return pyscrypt.hash(p, salt, 2**16, 8, 1) def xor(s1, s2): return b.join([bytes([s1[i] ^ s2[i % len(s2)]]) for i in range(len(s1))]) class HashHandler(socketserver.BaseRequestHandler): welcome_message Welcome, young wanna-be Cracker, to the Hashinator. To prove your worthiness, you must display the power of your cracking skills. The test is easy: 1. We send you a password from the rockyou list, hashed using multiple randomly chosen algorithms. 2. You crack the hash and send back the original password. As you already know the dictionary and wont need any fancy password rules, {} seconds should be plenty, right? Please wait while we generate your hash... hashes [md5, sha, blake, scrypt] timeout 10 total_rounds 32 def handle(self): self.request.sendall(self.welcome_message.format(self.timeout).encode()) password self.generate_password() # from rock_you.txt salt self.generate_salt(password) # 與password的長度有關 hash_rounds self.generate_rounds() # 生成進行hash算法的順序 password_hash self.calculate_hash(salt password, hash_rounds) self.generate_delay() self.request.sendall(Challenge password hash: {}\n.format(b64encode(password_hash)).encode()) self.request.sendall(Rounds used:\n.encode()) test_rounds [] for r in hash_rounds: test_rounds.append(r) for r in hash_rounds: self.request.sendall(- {}\n.format(r.__name__).encode()) self.request.sendall(Your time starts now!\n.encode()) self.request.settimeout(self.timeout) try: response self.request.recv(1024) if response.strip() password: self.request.sendall(Congratulations! You are a true cracking master!\n.encode()) self.request.sendall(Welcome to the club: {}\n.format(flag).encode()) return except socket.timeout: pass self.request.sendall(Your cracking skills are bad, and you should feel bad!.encode()) def generate_password(self): rand struct.unpack(I, os.urandom(4))[0] lines 14344391 # size of rockyou line rand % lines password f open(rockyou.txt, rb) for i in range(line): password f.readline() return password.strip() def generate_salt(self, p): msize 128 # f-you hashcat :D salt_size msize - len(p) return os.urandom(salt_size) def generate_rounds(self): rand struct.unpack(Q, os.urandom(8))[0] rounds [] for i in range(self.total_rounds): rounds.append(self.hashes[rand % len(self.hashes)]) rand rand 2 return rounds def calculate_hash(self, payload, hash_rounds): interim_salt payload[:64] interim_hash payload[64:] for i in range(len(hash_rounds)): interim_salt xor(interim_salt, hash_rounds-1-i) interim_hash xor(interim_hash, hash_roundsi) interim_hash xor( interim_hash, hash_roundsi) ) ) final_hash interim_salt interim_hash return final_hash def generate_delay(self): rand struct.unpack(I, os.urandom(4))[0] time.sleep(rand / 1000000000.0) class ThreadedTCPServer(socketserver.ThreadingMixIn, socketserver.TCPServer): allow_reuse_address True PORT 1337 HOST 0.0.0.0 flag with open(flag.txt) as f: flag f.read() def main(): server ThreadedTCPServer((HOST, PORT), HashHandler) server_thread threading.Thread(targetserver.serve_forever) server_thread.start() server_thread.join() if __name__ __main__: main()從源碼結構看該題目的「陷阱」設計十分清晰generate_password()用 4 字節隨機數對14344391rockyou 字典行數取模選取密碼保證明文來源可窮舉、但具體是哪一行不可預知generate_salt()用msize 128固定總長度直接封死字典/彩虹表路線代碼註釋f-you hashcat :D是出題人的明示generate_rounds()用 8 字節隨機數按rand % 4與rand 2逐位生成 32 輪算法順序並在握手階段全部打印——這正是逆向的前提算法順序必須公開calculate_hash()中每個 64 字節的interim_salt/interim_hash都只做「異或 哈希」兩種可逆運算且註釋掉的備選實現先算 salt 再算 hash 的合併寫法進一步佐證了作者對可逆性的考量。原代碼中被註釋掉的那段「等價但不可逆」的實現非常值得注意如果把兩步異或合併為一步先對interim_salt求哈希後整體異或進interim_hash攻擊者就無法從最終輸出分離出兩個中間值逆向將不再可行。換句話說可逆性並非哈希輪數堆疊帶來的而是「兩路中間值交叉異或」這種結構造成的——兩路狀態各自只被對方的新值異或形成了一條可回溯的鏈。倉庫中的其他哈希攻擊案例原文檔所屬的 哈希章節 還收錄了多道與哈希攻擊相關的題目可作為上述攻擊思路的延伸印證2017 34c3 Software_update見 綜合題目服務端將目錄下每個文件的 SHA-256 哈希異或起來作為 RSA 簽名輸入。攻擊思路是利用異或的線性性質構造一組文件使修改pre-copy.py前後的哈希異或值相互抵消本質是把問題化為在GF(2)^256向量空間中求解線性組合用 sage 構造 256 維基底並求解目標向量delta。這與 Hashinator 一樣攻擊點同樣是「異或運算破壞了哈希作為簽名的完整性保證」。2018 網鼎杯 hashcoll見 FNV 哈希自定義的 FNV 型迭代哈希h (h i) * g mod 2^256本質是關於消息字節的多項式要求構造兩個消息哈希相等即可化為求解z_1 g^{n-1} ... z_n k * 2^256的整數關係問題最終用 LLL 格基約簡算法求解碰撞。這是「自定義哈希不具備抗碰撞性」的典型格攻擊案例。2017 SECCON SHA1 is dead見 SHA1 基礎利用公開的 SHA-1 碰撞對shattered PDF 前 320 字節構造滿足SHA1(file1) SHA1(file2)且SHA256不同的兩個文件並利用「碰撞前綴後接相同數據哈希仍相同」的性質把文件填充到指定大小區間。總結與防禦建議綜上CTF 中哈希攻擊的核心思路可以歸納為三條主線長度攻擊針對H(key ∥ message)構造的 Merkle–Damgård 哈希只要知道密鑰長度就能無需密鑰地偽造任意後綴——防禦方式是改用H(message ∥ key)HMAC 的內外雙哈希結構更佳或直接使用 HMAC、HKDF 等密鑰化構造結構攻擊任何把哈希輸出與異或、加法等可逆運算混用的自定義「哈希」都可能因兩路中間值可回溯而完全可逆且混合異或的簽名方案如 34c3 Software_update會被向量空間線性組合攻破代數攻擊形如h (h x) * g mod 2^n的迭代哈希可化為格問題用 LLL 求解碰撞自定義哈希必須經過標準審計如採用 SHA-3 等海綿結構才能用於安全場景。對應的防禦實踐包括簽名/MAC 一律採用 HMAC 或標準密鑰派生自定義哈希僅允許用於非安全場景如哈希表以及為哈希輸入引入足夠長且不可預測的隨機鹽從源頭封死字典與彩虹表路線——正如 Hashinator 題目所演示的那樣。赞分享文档网络安全教程【免费下载链接】ctf-wikiCome and join us, we need you!项目地址https://gitcode.com/gh_mirrors/ct/ctf-wiki点击查看免费下载相关推荐Docs 部署时如何根据场景估算服务器内存与 vCPU 需求Docs 部署时如何根据场景估算服务器内存与 vCPU 需求 在部署 DocsLa Suite Docs基于 Django React 的开源协作文档编文档网络安全教程imagededup 哈希算法详解感知哈希、差异哈希、小波哈希深度解析imagededup 哈希算法详解感知哈希、差异哈希、小波哈希深度解析 在数字图像管理领域imagededup 项目提供了一套简单高效的图像去重解决方案。这计算机视觉图像处理人工智能OI-wiki 字符串哈希String Hash全解原理、冲突攻防、子串哈希与实战应用OI wiki 字符串哈希String Hash全解原理、冲突攻防、子串哈希与实战应用 字符串哈希String Hashing / Hash 函数是文档知识库教育教程上一篇Rust实战教程深入理解HashMap集合类型下一篇MacOS文本区域交互快捷键大全基于jbranchaud/til项目创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考