Black Hat Europe 2025 | Slashing QUIC's Performance With A Hash DoS
三句話摘要
利用 QUIC 協議中的連接 ID 和弱雜湊函數進行拒絕服務攻擊，可完全癱瘓後端伺服器。 ## QUIC 協議中由用戶端完全控制的連接 ID 與多個實作的弱雜湊函數結合，形成了可完全癱瘓後端伺服器的 Hash DoS 漏洞，啟示是協議設計需防止攻擊者輸入控制雜湊表，實作者須依賴現代語言的內建防護而絕不自行實現雜湊函數。 Hash DoS 攻擊的核心原理：雜湊表在無碰撞時查詢為 O(1)，但碰撞發生時退化為 O(n)。若使用鏈表法解決碰撞，n 個元素的插入與查詢摊銷複雜度變為 O(n²)。攻擊者透過生成大量特意製造的碰撞鍵值，觸發演算法最壞情況，導致服務端 CPU 滿載。
重點整理
重點- 1
Hash DoS 攻擊的核心原理：雜湊表在無碰撞時查詢為 O(1)，但碰撞發生時退化為 O(n)。若使用鏈表法解決碰撞，n 個元素的插入與查詢摊銷複雜度變為 O(n²)。攻擊者透過生成大量特意製造的碰撞鍵值，觸發演算法最壞情況，導致服務端 CPU 滿載。
- 2
QUIC 協議的攻擊表面：QUIC 採用 UDP+TLS 1.3 加速連線建立，無需 TCP 三路握手。為支援用戶裝置在 Wi-Fi 與行動網路間無縫切換，QUIC 引入連接 ID 機制，用戶端自主生成並可任意選擇值。RFC 明確規定連接 ID 由「實作特定方法」決定，完全攻擊者可控。服務器將其作為雜湊表鍵儲存連線，直接滿足 Hash DoS 的第一個必要條件。
- 3
實作中的弱雜湊函數：Alibaba x-quic 使用乘法雜湊（hash = hash × 31 + byte），2 字節輸入有 9 個值都雜湊到 255。連接 ID 需 8-20 字節，攻擊者可排列組合這 9 個子串，產生 9^6 = 50 多萬個碰撞，耗時僅 0.1 秒。LiteSpeed lsquic 的 xx-h32 聲稱防碰撞，但簡化實作（8-12 字節）仍可用微分密碼分析產生數十萬碰撞對。
- 4
防護策略與責任劃分：協議設計者應防止攻擊者控制雜湊輸入；實作者必須採用 Python/Go/Rust 等內建 SipHash 防護的語言，勿自行實現雜湊函數（Ericsson Rask 即使用 Rust 也因重新實現而遭殃）；漏洞研究人員應持續追蹤新實作中的類似問題。
- 5
##
實用技巧與重點
乾貨- 受影響實作（8 個，已修復）：
- Alibaba x-quic（乘法雜湊）
- LiteSpeed lsquic（xx-h32）
- Apache Traffic Server
- nghttp2
- 多個已停維護專案
- Ericsson Rask
- Chromium（2019 年已主動修復）
- 碰撞生成與性能數據：
- 連接 ID 長度 12 字節：9^6 = 501,529 個碰撞 ID
- 生成 50+ 萬碰撞 ID 耗時：0.1 秒
- 插入查詢 10 萬碰撞 ID：12 秒（隨機 ID 僅 0.33 秒）
- 插入查詢 20 萬碰撞 ID：48 秒（隨機 ID 僅 1 秒）
- 插入查詢 50+ 萬碰撞 ID：超 7 分鐘
- 防護機制：
- SipHash（JP Aumasson 與 Dan Bernstein 設計的密鑰偽隨機函數）
- Python、Go、Rust 預設使用 SipHash
- 標準規範：
- QUIC 連接 ID 長度：8-20 字節
- RFC：客戶端選擇源連接 ID 採「實作特定方法」
- 協調披露時間表：
- 逐項目披露 → 聯繫 QUIC 工作組 → 設定統一披露日期（該年 2 月）
- 披露時所有受影響實作均已完成修復
- ##
結論
結論“QUIC 協議中由用戶端完全控制的連接 ID 與多個實作的弱雜湊函數結合，形成了可完全癱瘓後端伺服器的 Hash DoS 漏洞，啟示是協議設計需防止攻擊者輸入控制雜湊表，實作者須依賴現代語言的內建防護而絕不自行實現雜湊函數。”
完整解析
詳細Hash 拒絕服務攻擊是針對資料結構演算法複雜度的經典攻擊手法，歷史超過 20 年。演講者 Paul Botinelli 是 Trail of Bits 的密碼學顧問，15 年前在研究生密碼學研討課接觸相關論文後，一直關注此類攻擊在各種協議和實作中的蹤跡。實施 Hash DoS 需兩個必要條件：攻擊者能控制輸入值，且系統使用弱雜湊函數。
要理解攻擊機制，須先掌握雜湊表原理。雜湊表是鍵值儲存結構，透過雜湊函數將鍵映射到陣列索引。理想情況下查詢和插入都是常數時間 O(1)。然而當不同鍵雜湊到同一位置時產生碰撞。常見的碰撞解決方案包括開放定址法（順序掃瞄尋找空槽）和鏈表法（在該索引位置建立鏈結串列）。一旦發生碰撞，鏈表中的查詢時間變為線性 O(n)。若攻擊者能向雜湊表注入 n 個碰撞的鍵，隨後 n 次查詢的總耗時會呈二次方級 O(n²) 增長——第一個元素查詢很快，但每增加一個元素就變慢，因為必須遍歷整個鏈表。
QUIC 協議恰好提供了理想的攻擊目標。QUIC 由 Google 於 2012 年設計，後被 RFC 標準化並成為 HTTP/3 的基礎。相較於傳統 TCP 需三次握手再進行 TLS 握手的冗長過程，QUIC 使用 UDP 直接發送攜帶 TLS 握手訊息的封包，大幅降低連線建立延遲。更重要的是，為了支援行動裝置在家中 Wi-Fi 和戶外行動網路間無縫切換時保持連線（不需重新握手），QUIC 引入了連接 ID 概念。連接 ID 由用戶端自主生成，用於標識特定連線。當裝置切換網路導致 IP 位址改變時，伺服器只需根據收到的連接 ID 即可恢復連線狀態，無須重新進行耗時的 TCP 和 TLS 握手。
RFC 標準明確規定客戶端使用「實作特定方法」選擇源連接 ID，這意味著攻擊者擁有完全的生成自由度。伺服器通常將這些用戶端選擇的連接 ID 作為鍵儲存在雜湊表中管理所有連線，這正好滿足 Hash DoS 的第一個必要條件：攻擊者可控的輸入。
演講者在審計 QUIC 實作時發現多個專案使用了易於碰撞的弱雜湊函數。Alibaba x-quic 採用簡單乘法雜湊演算法：初始化雜湊值為 0，逐字節迭代，每次將雜湊值乘以質數 31 後加上當前字節值。這種函數容易被破解。以 2 字節輸入為例，有 9 個不同的 2 字節組合都雜湊到同一值 255（例如 00ff、01e0、02c1 等）。由於 QUIC 允許連接 ID 長度為 8-20 字節，攻擊者可將這 9 個 2 字節碰撞子串任意排列組合，例如長度 12 字節時可排列 6 個子串，產生 9^6 超過 50 萬個碰撞連接 ID。演講者的 Python 演示腳本顯示，生成這 50 多萬個碰撞 ID 耗時僅 0.1 秒。
LiteSpeed lsquic 使用 xx-h32 雜湊函數，該函數聲稱具有良好的碰撞分散性和隨機性特徵。雖然實作相對複雜，涵蓋旋轉和非線性運算，但演講者發現當限制輸入長度為 8 或 12 字節時（QUIC 標準允許的範圍），可繞過複雜的後續處理步驟。使用微分密碼分析技術，演講者成功找到能生成數十萬碰撞對的差分值，且這些差分獨立於伺服器生成的隨機密鑰，即便伺服器使用密碼學安全的虛擬隨機數產生器也無法防禦。
將這些碰撞連接 ID 插入伺服器雜湊表後，效能急劇下降。演講中的性能測試清晰展示了二次方複雜度的危害。插入並查詢 10 萬個碰撞 ID 耗時 12 秒（隨機 ID 僅需 0.33 秒），翻倍至 20 萬個時耗時變為 48 秒而非線性的 2 倍。考慮到 Cloudflare 每秒處理 5500 萬請求，50 萬碰撞 ID 相對微不足道，但已足以讓伺服器 CPU 持續滿負荷運轉數分鐘至數十分鐘。
協調披露涉及對 24 個公開 QUIC 實作的審計。演講者最終發現其中 8 個存在該漏洞，約占 1/3，包括前述的 Alibaba x-quic 和 LiteSpeed lsquic，以及 Apache Traffic Server、nghttp2 等。有趣的是 Ericsson 的 Rask 實作雖使用通常提供 DoS 防護的 Rust 語言，但開發者為追求效能自行重新實現了雜湊函數，再次違反了「不要自己實現雜湊」的黃金法則。Chromium 早在 2019 年已主動發現並修復了該漏洞。最終在該年 2 月的協調披露日期時，所有受影響實作都完成了修復。
防護措施相對明確。Python、Go 和 Rust 等現代語言的雜湊表實現預設使用 SipHash 等密鑰偽隨機函數，能有效提供 Hash DoS 抵抗性。協議設計者應在規範中避免讓攻擊者控制重要資料結構的輸入；實作者應依賴語言內建的防護機制而非自行實現；漏洞研究人員需持續追蹤並發現新專案中的類似問題。
##
關鍵時刻
Pipeline v2帶時間戳的重點，會在逐字稿層級分析上線後產生。目前請先透過原始影片觀看。
事實查核
Pipeline v2說法查證是下一次管線升級的一部分。KeyFrame 只會顯示它真正能驗證的內容。
