Security of Block Ciphers

Kazuo Sakiyama: Associate Professor, The University of Electro-Communications, Tokyo, Japan.Dr Sakiyama’s area of expertise includes digital circuit design, cryptographic embedded systems, and secure computing. He has been working on digital circuit design since 1996. Since 2001 he has focused on cryptographic embedded systems, and has been teaching hardware security in several lectures of advanced cryptography and PBL (project-based learning) courses.Yu Sasaki: Researcher, NTT Secure Platform Laboratories, NTT Corporation, Tokyo, Japan.He has been working on the cryptography since 2004. His research interest has focused on security evaluation of cryptographic protocols and cryptanalysis on symmetric-key primitives.Yang Li: Research Assistant, The University of Electro-Communications, Japan.

• Preface xiAbout the Authors xiii1 Introduction to Block Ciphers 11.1 Block Cipher in Cryptology 11.1.1 Introduction 11.1.2 Symmetric-Key Ciphers 11.1.3 Efficient Block Cipher Design 21.2 Boolean Function and Galois Field 31.2.1 INV, OR, AND, and XOR Operators 31.2.2 Galois Field 31.2.3 Extended Binary Field and Representation of Elements 41.3 Linear and Nonlinear Functions in Boolean Algebra 71.3.1 Linear Functions 71.3.2 Nonlinear Functions 71.4 Linear and Nonlinear Functions in Block Cipher 81.4.1 Nonlinear Layer 81.4.2 Linear Layer 111.4.3 Substitution-Permutation Network (SPN) 121.5 Advanced Encryption Standard (AES) 121.5.1 Specification of AES-128 Encryption 121.5.2 AES-128 Decryption 191.5.3 Specification of AES-192 and AES-256 201.5.4 Notations to Describe AES-128 23Further Reading 252 Introduction to Digital Circuits 272.1 Basics of Modern Digital Circuits 272.1.1 Digital Circuit Design Method 272.1.2 Synchronous-Style Design Flow 272.1.3 Hierarchy in Digital Circuit Design 292.2 Classification of Signals in Digital Circuits 292.2.1 Clock Signal 292.2.2 Reset Signal 302.2.3 Data Signal 312.3 Basics of Digital Logics and Functional Modules 312.3.1 Combinatorial Logics 312.3.2 Sequential Logics 322.3.3 Controller and Datapath Modules 362.4 Memory Modules 402.4.1 Single-Port SRAM 402.4.2 Register File 412.5 Signal Delay and Timing Analysis 422.5.1 Signal Delay 422.5.2 Static Timing Analysis and Dynamic Timing Analysis 452.6 Cost and Performance of Digital Circuits 472.6.1 Area Cost 472.6.2 Latency and Throughput 47Further Reading 483 Hardware Implementations for Block Ciphers 493.1 Parallel Architecture 493.1.1 Comparison between Serial and Parallel Architectures 493.1.2 Algorithm Optimization for Parallel Architectures 503.2 Loop Architecture 513.2.1 Straightforward (Loop-Unrolled) Architecture 513.2.2 Basic Loop Architecture 533.3 Pipeline Architecture 553.3.1 Pipeline Architecture for Block Ciphers 553.3.2 Advanced Pipeline Architecture for Block Ciphers 563.4 AES Hardware Implementations 583.4.1 Straightforward Implementation for AES-128 583.4.2 Loop Architecture for AES-128 613.4.3 Pipeline Architecture for AES-128 653.4.4 Compact Architecture for AES-128 66Further Reading 674 Cryptanalysis on Block Ciphers 694.1 Basics of Cryptanalysis 694.1.1 Block Ciphers 694.1.2 Security of Block Ciphers 704.1.3 Attack Models 714.1.4 Complexity of Cryptanalysis 734.1.5 Generic Attacks 744.1.6 Goal of Shortcut Attacks (Cryptanalysis) 774.2 Differential Cryptanalysis 784.2.1 Basic Concept and Definition 784.2.2 Motivation of Differential Cryptanalysis 794.2.3 Probability of Differential Propagation 804.2.4 Deterministic Differential Propagation in Linear Computations 834.2.5 Probabilistic Differential Propagation in Nonlinear Computations 864.2.6 Probability of Differential Propagation for Multiple Rounds 894.2.7 Differential Characteristic for AES Reduced to Three Rounds 914.2.8 Distinguishing Attack with Differential Characteristic 934.2.9 Key Recovery Attack after Differential Characteristic 954.2.10 Basic Differential Cryptanalysis for Four-Round AES † 964.2.11 Advanced Differential Cryptanalysis for Four-Round AES † 1034.2.12 Preventing Differential Cryptanalysis † 1064.3 Impossible Differential Cryptanalysis 1104.3.1 Basic Concept and Definition 1104.3.2 Impossible Differential Characteristic for 3.5-round AES 1114.3.3 Key Recovery Attacks for Five-Round AES 1144.3.4 Key Recovery Attacks for Seven-Round AES † 1234.4 Integral Cryptanalysis 1314.4.1 Basic Concept 1314.4.2 Processing P through Subkey XOR 1324.4.3 Processing P through SubBytes Operation 1334.4.4 Processing P through ShiftRows Operation 1344.4.5 Processing P through MixColumns Operation 1344.4.6 Integral Property of AES Reduced to 2.5 Rounds 1354.4.7 Balanced Property 1364.4.8 Integral Property of AES Reduced to Three Rounds and Distinguishing Attack 1374.4.9 Key Recovery Attack with Integral Cryptanalysis for Five Rounds 1394.4.10 Higher-Order Integral Property † 1414.4.11 Key Recovery Attack with Integral Cryptanalysis for Six Rounds † 143Further Reading 1475 Side-Channel Analysis and Fault Analysis on Block Ciphers 1495.1 Introduction 1495.1.1 Intrusion Degree of Physical Attacks 1495.1.2 Passive and Active Noninvasive Physical Attacks 1515.1.3 Cryptanalysis Compared to Side-Channel Analysis and Fault Analysis 1515.2 Basics of Side-Channel Analysis 1525.2.1 Side Channels of Digital Circuits 1525.2.2 Goal of Side-Channel Analysis 1545.2.3 General Procedures of Side-Channel Analysis 1555.2.4 Profiling versus Non-profiling Side-Channel Analysis 1565.2.5 Divide-and-Conquer Algorithm 1575.3 Side-Channel Analysis on Block Ciphers 1595.3.1 Power Consumption Measurement in Power Analysis 1605.3.2 Simple Power Analysis and Differential Power Analysis 1635.3.3 General Key Recovery Algorithm for DPA 1645.3.4 Overview of Attack Targets 1695.3.5 Single-Bit DPA Attack on AES-128 Hardware Implementations 1815.3.6 Attacks Using HW Model on AES-128 Hardware Implementations 1865.3.7 Attacks Using HD Model on AES-128 Hardware Implementations 1925.3.8 Attacks with Collision Model † 1995.4 Basics of Fault Analysis 2035.4.1 Faults Caused by Setup-Time Violations 2055.4.2 Faults Caused by Data Alternation 2085.5 Fault Analysis on Block Ciphers 2085.5.1 Differential Fault Analysis 2085.5.2 Fault Sensitivity Analysis † 215Acknowledgment 223Bibliography 2236 Advanced Fault Analysis with Techniques from Cryptanalysis 2256.1 Optimized Differential Fault Analysis 2266.1.1 Relaxing Fault Model 2266.1.2 Four Classes of Faulty Byte Positions 2276.1.3 Recovering Subkey Candidates of sk10 2286.1.4 Attack Procedure 2306.1.5 Probabilistic Fault Injection 2316.1.6 Optimized DFA with the MixColumns Operation in the Last Round † 2326.1.7 Countermeasures against DFA and Motivation of Advanced DFA 2366.2 Impossible Differential Fault Analysis 2376.2.1 Fault Model 2386.2.2 Impossible DFA with Unknown Faulty Byte Positions 2386.2.3 Impossible DFA with Fixed Faulty Byte Position 2446.3 Integral Differential Fault Analysis 2456.3.1 Fault Model 2466.3.2 Integral DFA with Bit-Fault Model 2476.3.3 Integral DFA with Random Byte-Fault Model 2516.3.4 Integral DFA with Noisy Random Byte-Fault Model † 2546.4 Meet-in-the-Middle Fault Analysis 2606.4.1 Meet-in-the-Middle Attack on Block Ciphers 2606.4.2 Meet-in-the-Middle Attack for Differential Fault Analysis 263Further Reading 2687 Countermeasures against Side-Channel Analysis and Fault Analysis 2697.1 Logic-Level Hiding Countermeasures 2697.1.1 Overview of Hiding Countermeasure with WDDL Technique 2707.1.2 WDDL-NAND Gate 2727.1.3 WDDL-NOR and WDDL-INV Gates 2737.1.4 Precharge Logic for WDDL Technique 2737.1.5 Intrinsic Fault Detection Mechanism of WDDL 2767.2 Logic-Level Masking Countermeasures 2777.2.1 Overview of Masking Countermeasure 2777.2.2 Operations on Values with Boolean Masking 2787.2.3 Re-masking and Unmasking 2787.2.4 Masked AND Gate 2797.2.5 Random Switching Logic 2817.2.6 Threshold Implementation 2837.3 Higher Level Countermeasures 2857.3.1 Algorithm-Level Countermeasures 2867.3.2 Architecture-Level Countermeasures 2897.3.3 Protocol-Level Countermeasure 290Bibliography 291Index 293