Fault Diagnosis and Tolerance in Cryptography: Third International Workshop, FDTC 2006, Yokohama, Japan, October 10, 2006, Proceedings (Lecture Notes in Computer Science, 4236)

In recent years applied cryptography has developed considerably to satisfy the - creasing security requirements of various information technology disciplines, such as telecommunications, networking, database systems, mobile applications and others. Cryptosystems are inherently computationally complex and in order to satisfy the high throughput requirements of many applications, they are often implemented by means of either VLSI devices (cryptographic accelerators) or highly optimized software routines (cryptographic libraries) and are used via suitable (network) protocols. The sophistication of the underlying cryptographic algorithms, the high complexity of the implementations, and the easy access and low cost of cryptographic devices resulted in increased concerns regarding the reliability and security of crypto-devices. The effectiveness of side channel attacks on cryptographic devices, like timing and power-based attacks, has been known for some time. Several recent investigations have demonstrated the need to develop methodologies and techniques for designing robust cryptographic systems (both hardware and software) to protect them against both accidental faults and maliciously injected faults with the purpose of extracting the secret key. This trend has been particularly motivated by the fact that the equipment needed to carry out a successful side channel attack based on fault injection is easily accessible at a relatively low cost (for example, laser beam technology), and that the skills needed to use it are quite common. The identification of side channel attacks based on fault injections and the development of appropriate counter-measures have therefore become an active field of scientific and industrial research. Fault Diagnosis and Tolerance in Cryptography front-matter 1 fulltext 12 Introduction 12 Definitions and Preliminaries 14 The Physical Fault Model or Recalling Seifert's Attack 15 Novel Fault Attacks Against RSA Authentication 17 Bypass Fault Attacks 17 Permanent Fault Attacks 18 Mitigating Fault Attacks Against RSA Authentication 20 Mitigating Seifert-Like Attacks 20 Mitigating Bypass Fault Attacks 20 Mitigating Permanent Fault --- A Mission Impossible? 22 fulltext_001 24 Introduction 24 Fault Models 25 The BOS Scheme 27 Obvious Security Considerations 28 Wagner's Attacks Against the BOS Scheme 28 Bit and Byte Faults 29 Wagner's Attack 32 Conclusion 33 fulltext_002 35 Introduction 35 Preliminary Notions 37 The Model 37 The Basic Attack 39 Randomized Time 42 Countermeasures 44 Conclusions 45 Proofs 46 fulltext_003 47 Introduction 47 Elliptic Curve Cryptography 49 The Sign Change Attack on Elliptic Curve Repeated Doubling 50 Sign Change Attack on $Q^'_i$ in Line 4. 51 Countermeasures 54 Analysis of the Countermeasure 55 Realization of Sign Change Attacks 57 Conclusions and Open Problems 59 Proofs of Lemma 5, Lemma 6, and Theorem 7 61 fulltext_004 64 Introduction 65 Preliminary Background of CRT-Based Cryptanalysis 66 Chinese Remainder Theorem 66 The CRT-Based Cryptanalysis 66 Shamir's Countermeasure 67 Review of Two Protocols for RSA with CRT Based on Fault Infection 67 The First Protocol -- CRT-1 Protocol 67 The Second Protocol -- CRT-2 Protocol 68 Hardware Fault Cryptanalysis on Fault Infective RSA with CRT 68 Hardware Fault Cryptanalysis on CRT-1 Protocol 69 Hardware Fault Cryptanalysis on CRT-2 Protocol 70 Concluding Remarks 70 fulltext_005 73 Introduction 73 A Review of Previous Work 74 Our Algorithm 76 Security Analysis 76 Efficiency Analysis 79 Conclusion 79 Proof of Theorem 1 80 fulltext_006 82 Introduction 82 The RSA Cryptosystem 83 Online Detection 85 Implementation 86 Conclusions 89 fulltext_007 91 Introduction 91 Data-and-Compute Error Detection Method 92 The Arithmetic Stamp 94 Computing the Arithmetic Step of a Non-reduced Montgomery Multiplications 95 Protecting the Full Modular Exponentiation Procedure 96 Conclusion 96 fulltext_008 99 Introduction 99 Quasi Delay Insensitive Logic 100 The Asynchronous DES Architecture 101 Fault Injection Process 102 Results Interpretation 103 Rounds Sequences Modification 103 Exploitation 104 Reference DES Results 105 Hardened DES Results 106 Theoretical Analysis of the Weaknesses 106 Counter-Measures 107 Conclusion 107 References 108 fulltext_009 109 Introduction 109 The FOX Cipher Family 110 The Attack 112 Conclusions 115 fulltext_010 117 Introduction 117 Model 119 New Fault Attacks 121 Notation 121 Scenarios 121 First Attack 122 Second Attack 123 Third Attack 126 Fourth Attack 128 Fifth Attack 128 Concluding Remarks 130 fulltext_011 132 Introduction 132 Testable and Reconfigurable Pipeline for Block Ciphers 133 Scheduling for Error Detection and Reconfiguration 136 Performance 139 Conclusions 141 fulltext_012 142 Introduction 142 Related Work 144 Model of Low-Cost Cryptographic Devices 145 Adversarial Models 146 Classification of Faults 147 Objectives of the Adversary 147 Means of the Adversary 149 Applications 150 Conclusion 152 fulltext_013 155 Introduction 155 The Model 157 Key Points 157 Environmental Conditions and Passive Fault Attacks 158 Cryptographic Key Failure Tolerance 159 Accepted Error-Bound to the Risk of Key Exposure 159 Failure Rates 159 Cryptographic Key Reliable Lifetimes 160 Estimation Methodology 160 Single Cryptographic Modules Implementing a Generic Cryptographic Scheme 161 Highly Available Cryptographic Infrastructures 162 Using This Framework 163 Estimating Upper Bounds for Cryptographic Key Lifetimes 163 Selecting Dependable Cryptographic Infrastructures 164 Scaling-Out Cryptographic Infrastructures 164 Consequences of the Presented Estimates 165 On the Importance of Good CKFT Values 166 Conclusions 166 fulltext_014 170 Introduction 170 Error Detection Techniques Using Space Redundancies 171 Description of a First Scheme 171 Security of the Presented Scheme 173 Description of Improved Schemes 174 Summary of the Results 176 Error Detection Using Repetition and Duplication 176 Description of a First Scheme 177 Another Proposal Equivalent to Repetition/Duplication 180 Discussion and Conclusions 181 fulltext_015 184 Introduction 184 Adversarial Fault Model 186 Robust Arithmetic Codes 186 Robust Arithmetic Operations 189 Robust Montgomery Multiplication 192 Conclusion 194 fulltext_016 196 Introduction 196 Current Protection Methods for Symmetric Ciphers 197 Attack Model 197 Limitations of Methods Based on Linear Error-Detecting Codes 198 Systematic Robust Codes 199 General Architecture 202 Architectural Optimizations 203 Conclusions 205 References 206 fulltext_017 207 Introduction 207 Related Work 209 Redundancy Through Ring and Field Homomorphisms 210 Homomorphic Embedding in Rings and Extension Fields 211 Basic Scaled Embedding 213 Idempotent Scaled Embedding 214 Error Correction Using Algorithm-Based Fault Tolerance 217 Relation to Cyclic Codes 218 Conclusion 219 fulltext_018 222 Introduction 222 Vulnerabilities of Existing Balanced Gates 223 Effects of Failures on Imbalance and Power Analysis Attacks 226 Countermeasure Strategies 229 Conclusions 232 References 232 fulltext_019 234 Introduction 234 Another Trivial Case 235 Secure Algorithm Implementations 237 Attacking the First XOR 237 Attacking the Key Masking 240 Modifying Known S-Box Values 241 Modifying Unknown S-Box Values 243 Countermeasures 245 Conclusion 246 fulltext_020 248 Introduction 248 Types of Attacks 249 Basic Type Confusion Attacks 250 Glitching 252 Combined Attacks 253 Execution of Java Bytecode 256 Counter-Measures 259 Discussion and Further Work 260 back-matter 263 Front Matter....Pages - Is It Wise to Publish Your Public RSA Keys?....Pages 1-12 Wagner’s Attack on a Secure CRT-RSA Algorithm Reconsidered....Pages 13-23 Attacking Right-to-Left Modular Exponentiation with Timely Random Faults....Pages 24-35 Sign Change Fault Attacks on Elliptic Curve Cryptosystems....Pages 36-52 Cryptanalysis of Two Protocols for RSA with CRT Based on Fault Infection....Pages 53-61 Blinded Fault Resistant Exponentiation....Pages 62-70 Incorporating Error Detection in an RSA Architecture....Pages 71-79 Data and Computational Fault Detection Mechanism for Devices That Perform Modular Exponentiation....Pages 80-87 Case Study of a Fault Attack on Asynchronous DES Crypto-Processors....Pages 88-97 A Fault Attack Against the FOX Cipher Family....Pages 98-105 Fault Based Collision Attacks on AES....Pages 106-120 An Easily Testable and Reconfigurable Pipeline for Symmetric Block Ciphers....Pages 121-130 An Adversarial Model for Fault Analysis Against Low-Cost Cryptographic Devices....Pages 131-143 Cryptographic Key Reliable Lifetimes: Bounding the Risk of Key Exposure in the Presence of Faults....Pages 144-158 A Comparative Cost/Security Analysis of Fault Attack Countermeasures....Pages 159-172 Non-linear Residue Codes for Robust Public-Key Arithmetic....Pages 173-184 Fault Attack Resistant Cryptographic Hardware with Uniform Error Detection....Pages 185-195 Robust Finite Field Arithmetic for Fault-Tolerant Public-Key Cryptography....Pages 196-210 DPA on Faulty Cryptographic Hardware and Countermeasures....Pages 211-222 Fault Analysis of DPA-Resistant Algorithms....Pages 223-236 Java Type Confusion and Fault Attacks....Pages 237-251 Back Matter....Pages - This book constitutes the refereed proceedings of the Third International Workshop on Fault Diagnosis and Tolerance in Cryptography, FDTC 2006, held in Yokohama, Japan in October 2006. The 12 revised papers of FDTC 2006 are presented together with 9 papers from FDTC 2004 and FDTC 2005 that passed a second round of reviewing. They all provide a comprehensive introduction to the issues faced by designers of robust cryptographic devices and to the currently available methodologies and techniques for protecting these devices against fault injection attacks. The papers are organized in topical sections on attacks on public key systems, protection of public key systems, attacks on and protection of symmetric key systems, models for fault attacks on cryptographic devices, fault-resistant arithmetic for cryptography, as well as fault attacks and other security threats This book constitutes the refereed proceedings of the Third International Workshop on Fault Diagnosis and Tolerance in Cryptography, FDTC 2006, held in Yokohama, Japan in October 2006. The 12 revised papers of FDTC 2006 are presented together with nine papers from FDTC 2004 and FDTC 2005 that passed a second round of reviewing. They all provide a comprehensive introduction to the issues faced by designers of robust cryptographic devices.