簡易檢索 / 詳目顯示

回結果列表
研究生： 吳彥慧
Wu, Yen-Hui
論文名稱： 基於差分路徑之降回 Keccak 碰撞攻擊
Collision Attacks on Round-Reduced Keccak based on Differential Trails
指導教授： 黃柏嶧
Huang, Po-Yi
學位類別： 碩士
Master
系所名稱： 理學院 - 數學系應用數學碩博士班
Department of Mathematics
論文出版年： 2026
畢業學年度： 114
語文別： 英文
論文頁數： 91
中文關鍵詞： 雜湊函數 、SHA-3 、Keccak 、差分攻擊 、碰撞攻擊 、縮減輪數攻擊
外文關鍵詞： Hash Function, SHA-3, Keccak, Differential Cryptanalysis, Collision Attack, Round-Reduced Attack
相關次數： 點閱：4  下載：0 
分享至:
查詢本校圖書館目錄 查詢臺灣博碩士論文知識加值系統 勘誤回報

    • Keccak 雜湊函數已被 NIST 選定為 SHA-3 標準，其演算法包含 24 輪運算。然而，目前學界針對完整 24 輪 Keccak 的攻擊尚未有具體突破，現有的研究主要集中於縮減輪數（Round-Reduced）的安全性分析。目前針對 5 輪 Keccak 最有效的碰撞攻擊，主要採用差分分析法。
    本論文旨在探討針對縮減輪數 Keccak 的碰撞攻擊。文中首先介紹差分攻擊的基礎理論，涵蓋一般差分與內部差分（Internal Differential）之概念。由於攻擊的執行仰賴於特定的差分路徑（Differential Trail），本研究前段將詳述如何推導出適用於攻擊的三輪差分路徑。隨後，本研究利用目標差分演算法（Target Difference Algorithm, TDA）與目標內部差分演算法（Target Internal Difference Algorithm, TIDA）等技術，成功實現針對 5 輪 Keccak 的碰撞攻擊。相關的演算法實作程式碼亦收錄於本論文附錄中，以供參考驗證。

    Keccak has been selected by NIST as the SHA-3 hash standard. While the algorithm consists of 24 rounds, practical attacks against the full 24-round Keccak remain infeasible. Consequently, current research focuses on analyzing the security of round-reduced variants. The most effective collision attacks on 5-round Keccak are currently achieved using differential cryptanalysis.
    This thesis investigates collision attacks on round-reduced Keccak. We introduce the fundamentals of differential attacks, including both standard differential and internal differential methods. Since the execution of the attack relies on specific differential trails, the initial chapters describe the derivation of a 3-round trail suitable for our attack. Subsequently, we utilize the Target Difference Algorithm (TDA) and Target Internal Difference Algorithm (TIDA) to mount a collision attack on 5-round Keccak. The relevant implementation code is provided in the appendix.

    Abstract i 摘要 ii 1 Introduction 1 2 Preliminaries 4 2.1 Sponge Construction and the SHA-3 Family 4 2.2 The Keccak-f Permutation 5 2.2.1 Inverse of χ 7 3 Differential Trail Search 10 3.1 Differential Cryptanalysis Basics 11 3.1.1 Properties of the θ Mapping 11 3.1.2 Propagation Weight 12 3.1.3 Parity-Bare States 12 3.1.4 The Column-Parity Kernel and Orbitals 13 3.2 Generating the 3-Round Trail 13 3.2.1 Generating the 2-Round Core 14 3.2.2 Trail Extension 17 3.3 Theoretical Lower Bounds for Multi-Round Trails 20 3.4 Trail Search with SAT Solver 21 3.4.1 Input Format of SAT Solvers: Conjunctive Normal Form (CNF) 22 3.4.2 Restricting the Propagation Weight of S-boxes Using Auxiliary Variables 22 4 Collision Attack on Round-Reduced Keccak 23 4.1 Differential Analysis of the Nonlinear Layer 23 4.1.1 Differential Distribution Table (DDT) 24 4.1.2 Values of Difference Conditions Table (VDCT) 24 4.1.3 Probabilistic Linearization and Maximum Difference Density Subspace (MDST) 25 4.2 The Target Difference Algorithm Framework 27 4.2.1 Trail Discovery with SAT Solver 27 4.2.2 Construction of the 2-Round Connector 29 4.2.3 Optimizing Degrees of Freedom: S-box Linearization 31 4.2.4 Extension to the Adaptive 3-Round Connector 33 4.2.5 Collision Search and Two-Block Extension Strategy 33 4.3 The Target Internal Difference Algorithm Framework 34 4.3.1 The Squeeze Attack: A Variant of Birthday Attack 35 4.3.2 Subspace Mapping and Complexity Analysis 36 4.3.3 Theoretical Framework: Internal Symmetry and Overlapping Constraints 37 4.3.4 Message Selection and Free Variable Extraction 39 4.3.5 Message Collection and Subspace Collision Search 40 4.4 Comparative Analysis of TDA and TIDA 41 References 44 A Inverse of the Linear Layer 47 A.1 Constructing EM 50 B DDT Analysis via SAT Solving 52 B.1 Keccak S-box SAT Solver Modeling 52 B.2 DDT Generation for Keccak χ S-box 52 B.3 Logical Representation of Differential Constraints 56 B.3.1 Analysis of the attack.cnf File 56 B.3.2 Encoding Format and Notation 57 B.4 Solver Execution 58 C Target Difference Algorithm (TDA) Implementation 59 C.1 C++ Implementation of Matrix Inverse and State Generation 59 C.2 Preparation for Finding the 2-Round Connector 64 C.3 2-Round Connector 72 D Target Internal Difference Algorithm (TIDA) 78 D.1 Finding the Internal Differential Trail via SAT 78 D.2 Implementation of the Message Selection Phase 81

    [1] National Institute of Standards and Technology, SHA-3 Standard: Permutation-Based Hash and Extendable-Output Functions, Federal Information Processing Standards Publication (FIPS PUB) 202, U.S. Department of Commerce, 2015.
    [2] T. Li and Y. Sun, “Preimage attacks on round-reduced Keccak-224/256 via an allocating approach,” in Advances in Cryptology – EUROCRYPT 2019, pp. 556–584, 2019. [3] Z. Zhang, C. Hou, and M. Liu, “Preimage attacks on up to 5 rounds of SHA-3 using internal differentials,” in Advances in Cryptology – EUROCRYPT 2025, pp. 333–363, 2025.
    [4] T. Li, Y. Sun, M. Liao, and D. Wang, “Preimage attacks on the round-reduced Keccak with cross-linear structures,” IACR Transactions on Symmetric Cryptology, vol. 2017, no. 4, pp. 39–57, 2017.
    [5] Z. Zhang, C. Hou, and M. Liu, “Probabilistic Linearization: Internal Differential Collisions in up to 6 Rounds of SHA-3,” Cryptology ePrint Archive, Report 2024/1136, 2024.
    [6] Z. Zhang, C. Hou, and M. Liu, “Collision Attacks on Round-Reduced SHA-3 Using Conditional Internal Differentials,” in EUROCRYPT 2023, LNCS 14007, pp. 220–251, 2023.
    [7] S. Huang, O. A. Ben-Yehuda, O. Dunkelman, and A. Maximov, “Finding Collisions against 4-Round SHA-3-384 in Practical Time,” IACR Trans. Symmetric Cryptol., vol. 2022, no. 3, pp. 239–270, 2022.
    [8] J. Guo, G. Liao, G. Liu, M. Liu, K. Qiao, and L. Song, “Practical Collision Attacks against Round-Reduced SHA-3,” Journal of Cryptology, vol. 33, no. 1, pp. 148–185, 2020.
    [9] F. de Lima Marquezino, R. Portugal, and C. Lavor, A Primer on Quantum Computing, SpringerBriefs in Computer Science, Springer, 2019.
    [10] K. Qiao, L. Song, M. Liu, and J. Guo, “New Collision Attacks on Round-Reduced Keccak,” in EUROCRYPT 2017, LNCS 10211, pp. 216–243, 2017.
    [11] S. Huang, X. Wang, G. Xu, M. Wang, and J. Zhao, “Conditional Cube Attack on Reduced-Round Keccak Sponge Function,” in EUROCRYPT 2017, LNCS 10211, pp. 492–521, 2017.
    [12] L. Song, G. Liao, and J. Guo, “Non-full Sbox Linearization: Applications to Collision Attacks on Round-Reduced KECCAK,” in CRYPTO 2017, LNCS 10402, pp. 428–451, 2017.
    [13] S. Moriai (Ed.), Fast Software Encryption - FSE 2013, LNCS 8424, Springer, 2014.
    [14] I. Dinur, O. Dunkelman, and A. Shamir, “New Attacks on Keccak-224 and Keccak256,” in FSE 2012, LNCS 7549, pp. 442–461, 2012.
    [15] I. Dinur, O. Dunkelman, and A. Shamir, “Collision Attacks on Up to 5 Rounds of SHA-3 Using Generalized Internal Differentials,” Cryptology ePrint Archive, Report 2012/672, 2012.
    [16] M. Soos, K. Nohl, and C. Castelluccia, “Extending SAT Solvers to Cryptographic Problems,” in SAT 2009, LNCS 5584, pp. 244–257, 2009.
    [17] C. Sinz, “Towards an Optimal CNF Encoding of Boolean Cardinality Constraints,” in CP 2005, LNCS 3709, pp. 827–831, 2005.
    [18] J. Guo, M. Liu, and L. Song, “Linear Structures: Applications to Cryptanalysis of Round-Reduced KECCAK,” in ASIACRYPT 2016, LNCS 10031, pp. 249–274, 2016.
    [19] J. Daemen and G. Van Assche, “Differential Propagation Analysis of Keccak,” in FSE 2012, LNCS 7549, pp. 422–441, 2012
    [20] A. Duc, J. Guo, T. Peyrin, and L. Wei, “Unaligned Rebound Attack: Application to Keccak,” in FSE 2012, LNCS 7549, pp. 407–426, 2012.
    [21] S. Mella, J. Daemen, and G. Van Assche, “New techniques for trail bounds and application to differential trails in Keccak,” IACR Transactions on Symmetric Cryptology, vol. 2017, no. 1, pp. 329–357, 2017.
    [22] G. Liu, W. Qiu, and Y. Tu, “New Techniques for Searching Differential Trails in Keccak,” in IACR Transactions on Symmetric Cryptology, Vol. 2019, No. 4, pp. 407–437, 2020.

    QR CODE