Cryptographic Hardware and Embedded Systems - CHES 2002: 4th International Workshop, Redwood Shores, CA, USA, August 13-15, 2002, Revised Papers (Lecture Notes in Computer Science, 2523)

✍ Scribed by Burton S. Jr. Kaliski (editor), Cetin K. Koc (editor), Christof Paar (editor)

• Publisher: Springer
• Year: 2003
• Tongue: English
• Leaves: 625
• Category: Library

✦ Synopsis

ThesearetheproceedingsofCHES2002,theFourthWorkshoponCryptographic Hardware and Embedded Systems. After the ?rst two CHES Workshops held in Massachusetts, and the third held in Europe, this is the ?rst Workshop on the West Coast of the United States. There was a record number of submissions this year and in response the technical program was extended to 3 days. As is evident by the papers in these proceedings, there have been again many excellent submissions. Selecting the papers for this year’s CHES was not an easy task, and we regret that we could not accept many contributions due to the limited availability of time. There were 101 submissions this year, of which 39 were selected for presentation. We continue to observe a steady increase over previous years: 42 submissions at CHES ’99, 51 at CHES 2000, and 66 at CHES 2001. We interpret this as a continuing need for a workshop series that c- bines theory and practice for integrating strong security features into modern communicationsandcomputerapplications. Inadditiontothesubmittedcont- butions, Jean-Jacques Quisquater (UCL, Belgium), Sanjay Sarma (MIT, USA) and a panel of experts on hardware random number generation gave invited talks. As in the previous years, the focus of the Workshop is on all aspects of cr- tographic hardware and embedded system security. Of special interest were c- tributionsthatdescribenewmethodsfore?cienthardwareimplementationsand high-speed software for embedded systems, e. g. , smart cards, microprocessors, DSPs, etc. CHES also continues to be an important forum for new theoretical and practical ?ndings in the important and growing ?eld of side-channel attacks.

✦ Table of Contents

Cryptographic Hardware and Embedded Systems –CHES 2002
Preface
Organization
Table of Contents
CHES: Past, Present, and Future
Optical Fault Induction Attacks
Introduction
Background
Experimental Method
Results
Implications and Further Work
Countermeasures
Conclusion
Template Attacks
Introduction
Theory
The Multivariate Gaussian Model Approach
The Pruning Process
Case Study: RC4
Template Attack on RC4
Other Case Studies
Implications and Countermeasures
The EM Side–Channel(s)
Introduction
EM Emanations and Acquisition
Origin of EM Emanations
Types of EM Emanations
Propagation and Capture of EM Signals
Experimental Results
Information Leakage across EM Spectrum
The Power of the EM Side--Channel(s)
Bad Instructions Defeat Power Analysis Countermeasures
Conclusion and Further Work
Countermeasures
Enhanced Montgomery Multiplication
Introduction
Preliminaries and Definitions
The Appropriate Choice of $s$ in the $NRMM^{s}$ Algorithm
Choosing $s$ for a Chain of Operations in $@mathbb {Z}N$
Discussion
New Algorithm for Classical Modular Inverse
Introduction
The Classical Modular Inverse in Previous Works
The Right-Shift Algorithm for the Classical Modular Inverse
The Montgomery Algorithm for the Classical Modular Inverse
New Left-Shift Algorithm for the Classical Modular Inverse
Results and Discussion
HW Implementation
Conclusion
Appendix: The Mathematical Proof of Proposed Algorithm
Increasing the Bitlength of a Crypto-Coprocessor
Introduction
Preliminaries
The Instructions {tt MultMod} and {tt MultModInit}$_n$
The Instructions {tt MultModDiv} and {tt MultModDivInit}$_n$
The Doubling Algorithm
Modular Multiplication without Initialization
Modular Multiplication with Initialization
Optimized Special Purpose Variants
Software Realization of the text {tt MultModDiv} and text {tt MultModDivInit}$_n$ Instructions
Hardware Realization of the text {tt MultModDiv} and text {tt MultModDivInit}$_n$ Instructions
Conclusion
Enhancing Simple Power-Analysis Attacks on Elliptic Curve Cryptosystems
Introduction
Related Work
Previous Results
An Attack Based on a Markov Model for the Elliptic-Curve Scalar Point-Multiplication Algorithm
Elliptic-Curve Scalar Point-Multiplication Algorithms
The Attacker's Task
Markov Models
Results
Analysis of a Double-Add and Subtract Algorithm
Application to the NAF-Method
A General Comment on the Key Testing Phase
A Note on the Application to Randomized Algorithms
Conclusion
Implementation of Elliptic Curve Cryptography with Built-In Counter Measures against Side Channel Attacks
Introduction
Preliminaries and Notation
Taxonomy of Software Counter Measures
Indistinguishability
Splitting Variables
Randomization of the Execution Sequence
Homogeneous Group Operations
Non-deterministic Right-to-Left Method with Precomputations
A Point of a Small Order as a Perturbation Point
Computer Experiments
Conclusion
Secure Elliptic Curve Implementations: An Analysis of Resistance to Power-Attacks in a DSP Processor
1 Introduction
2 Elliptic Curves and Software Implementation
3 Analysis of Uncertainty in Power-Attack Resistance
4 Discussions and Conclusions
References
Appendix: A
Appendix: B
Address-Bit Differential Power Analysis of Cryptographic Schemes OK-ECDH and OK-ECDSA
Introduction
Preliminaries
Elliptic Curve
Side Channel Attack
OK-ECDH and OK-ECDSA
Address-Bit DPA
Outline
Experimental Results
Proposed Address-Bit DPA
SE Attack
ZE Attack
Concluding Remarks
2Gbit/s Hardware Realizations of RIJNDAEL and SERPENT: A Comparative Analysis
Introduction
Common Design Issues
The Rijndael and Serpent Algorithms
A Fair Comparison
Overall Architectural Choices
The Rijndael Implementation
Sharing Look-Up Tables between En- and Decryption
Reorganizing a Cipher Round for Pipelining
Precomputing Subkeys
The Serpent Implementation
Separating Decryption from Encryption
Systematic Allocation of Hardware Resources
Generating Subkeys on the Fly
The Two Integrated Circuits Compared
Conclusions
Efficient Software Implementation of AES on 32-Bit Platforms
Introduction
Description of the Rijndael Algorithm
A New Technique for Computing the Rijndael Algorithm
The Transposed State Matrix Primitives
The Transposed State Matrix Key Scheduling
Implementation and Time Performance Figures
Conclusions
An Optimized S-Box Circuit Architecture for Low Power AES Design
Introduction
AES Algorithm and Its Circuit Implementations
2.1 AES Algorithm
2.2 Various S-Box Circuit Implementations
2.3 A S-Box Implementation Based on Composite Field Technique
Analysis of Power Consumption in AES Circuits
3.1 Power Analysis Method
3.2 Power Consumption of Various S-Box Architectures
3.3 Analysis
The Proposed Low Power S-Box Architecture and Its
Evaluation Results
4.1 The Proposed Multi-stage PPRM Architecture
4.2 Circuit Sharing between S-Box and S-Box-1
Conclusion
References
A-1. Stage 1 of S-Box
A-2. Stage 2 of S-Box
A-3. Stage 3 of S-Box
B-1. Stage 1 of S-Box-1
B-2. Stage 2 of S-Box-1
B-3. Stage 3 of S-Box-1
C-1. Stage 1 of Inverter over the AES Field
C-2. Stage 2 of Inverter over the AES Field
C-3. Stage 3 of Inverter over the AES Field
Simplified Adaptive Multiplicative Masking for AES
Introduction
Adaptive Masking Method for AES
The Rijndael Round
Adaptive Multiplicative Masking
Simplified Multiplicative Masking
Securized Implementation of the Simplified Multiplicative Masking
Conclusion
Multiplicative Masking and Power Analysis of AES
Introduction
Differential Power Analysis of AES
Multiplicative Masking of AES
Differential Power Analysis of Masked AES
Embedded Multiplicative Masking
Overview of Countermeasure
Efficient Implementation
Security Analysis
Conclusions
Keeping Secrets in Hardware: The Microsoft XboxTM Case Study
Introduction and Background
Xbox Hardware Cryptosystem Overview
Breaking the Physical Security
Lessons Learned
Future Work
Addendum
A DPA Attack against the Modular Reduction within a CRT Implementation of RSA
Introduction
RSA and the CRT Implementation
DPA against a Non-CRT Implementation
Key Hypotheses
Selection Functions
Correlation
DPA Attack against a CRT Implementation
Basic Idea:Hypotheses on the Remainder
The General DPA Attack:MRED
Results
First Case:8-Bit Architecture
Second Case:32-Bit Architecture
Efficiency of MRED
Limitations and Countermeasures
Conclusion
References
Further Results and Considerations on Side Channel Attacks on RSA
1 Introduction
2 Side Channel Attack on RSAES-OAEP Plaintext
2.1 Attack Description
2.2 Obtaining the Least Significant Bit of a Plaintext (Building an lsb-Oracle)
3 Note on Converting the Deciphering Oracle to a Signing Oracle
4 Side Channel Attack on RSA-KEM
Confirmation Oracle
4.2 Fault Side Channel Attacks
4.2.1 Faults in the Bits of the Private Exponent d
4.2.2 The Usage of Trojan Modulus
Algorithm A1: Computation of the Private Exponent Using the Access to a RSA Confirmation Oracle
Other Computational Faults
4.2.5 Comparison of Attacks on RSA Schemes
4.3. General Countermeasures
5 Conclusion
References
Fault Attacks on RSA with CRT: Concrete Results and Practical Countermeasures
Introduction
Preliminaries
The RSA System
The Fault-Based Cryptanalysis of RSA Using CRT
Simple Software Countermeasure to Defeat the Fault Attack
Shamir's Software Countermeasure
General Remarks on Methods to Overcome Fault Attacks
Physical Fault Attacks Realization
Spikes
Laboratory Setting
Results on Unprotected Hardware and Software
Practical Fault Attacks Countermeasures for Unprotected Hardware
Model to Understand Resulting/Possible Faults
Software Countermeasures Derived According to the Model
Measurement Results for Enhanced Software Countermeasures
Conclusion
Some Security Aspects of the MIST Randomized Exponentiation Algorithm
Introduction
The M{relax fontsize {9}{11}selectfont abovedisplayskip 8.5p @ plus3p @ minus4p @ abovedisplayshortskip z @ plus2p @ belowdisplayshortskip 4p @ plus2p @ minus2p @ def leftmargin leftmargini parsep 0p @ plus1p @ minusp @ topsep 8p @ plus2p @ minus4p @ itemsep 0p @ {leftmargin leftmargini parsep 0p @ plus1p @ minusp @ topsep 8p @ plus2p @ minus4p @ itemsep 0p @ }belowdisplayskip abovedisplayskip IST} Algorithm
The Base Choice and Addition Sub-chains
The Sequence of Addition Chain Values
Re-use of Summands
Identifying the Digit Sub-chains
The Operand Sharing Search Space
S&M Chains
Conclusion
The Montgomery Powering Ladder
Introduction
Montgomery Ladder
Efficiency Analysis
Lucas Chains
Parallel Computing
Common-Multiplicand Multiplication
Security Analysis
Side-Channel Attacks
Fault Attacks
Conclusion
DPA Countermeasures by Improving the Window Method
Introduction
Data Randomizing Techniques
Our Method
Overview
Overlapping Window Method (O-WM)
Randomized Table Window Method (RT-WM)
Hybrid Randomizing Window Method (HR-WM)
Security Evaluation against DPA
Basic Idea
O-WM
RT-WM
HR-WM
DPA Attack Experiment
Performance Comparison
Countermeasure Choice for an Encryption Algorithm
Conclusion
Efficient Subgroup Exponentiation in Quadratic and Sixth Degree Extensions
Introduction
Preliminaries
Computational Model
Discrete Logarithm Problem
Finite Field Representation
Key Generation
LUC and XTR
Quadratic Extensions
Field Representation for $pequiv 2mskip -medmuskip mkern 5mumathbin {mathgroup symoperators mod}penalty 900 mkern 5mumskip -medmuskip 3$
Field Representation for $pequiv 3mskip -medmuskip mkern 5mumathbin {mathgroup symoperators mod}penalty 900 mkern 5mumskip -medmuskip 4$
Subgroup Exponentiation
Sixth Degree Extension
Multiplication of Fifth Degree Polynomials
Field Representation for $pequiv 2mskip -medmuskip mkern 5mumathbin {mathgroup symoperators mod}penalty 900 mkern 5mumskip -medmuskip 9$
Subgroup Exponentiation
Key Selection
Timings
Solinas' Trick
On the Efficient Generation of Elliptic Curves over Prime Fields
Introduction
Preliminaries of Elliptic Curve Theory
The Complex Multiplication Method and Our Variant
Construction of Hilbert and Weber Polynomials
Implementation
Experimental Results
Conclusions
An End-to-End Systems Approach to Elliptic Curve Cryptography
Introduction
Related Work
System Overview
Secure Sockets Layer
Public-Key Cryptography in SSL
ECC Hardware Acceleration
Architectural Overview
ALU
Multiplier
Divider
Point Multiplication Algorithms
Implementation and Performance
Conclusions
A Low-Power Design for an Elliptic Curve Digital Signature Chip
Introduction
The `Optimal El Gamal' Authentication Algorithm
Optimal El Gamal Scheme
Algorithmic Optimizations
Finite Field Arithmetic and Field Towers
Finite Field Algorithms
Point Halving Algorithm
Sliding Window Multiplication with Precomputation
Hardware Architecture and Design
Hardware Implementation
Command, Configuration, and Control
Random Number Generation
Message Input
Signature Algorithm
Hardware Optimizations
Hardware Design Results
Conclusions
A Reconfigurable System on Chip Implementation for Elliptic Curve Cryptography over GF(2n)
Introduction
Mathematical Background
Elliptic Curve Arithmetic
Finite Field Arithmetic
Hardware Architecture
Combinational Karatsuba Multiplier (CKM)
Finite Field Coprocessor (FFCP)
Atmel FPSLIC Hardware Platform
Implementation
Pure Software without HW Acceleration
Hardware Acceleration
Performance Comparison
Conclusion
Genus Two Hyperelliptic Curve Coprocessor
Introduction
Basic Algorithms
Finite Fields
Polynomial Rings
Hyperelliptic Curves
HEC Cryptosystems
Coprocessor Implementation
Field Calculation Blocks
Polynomial Calculation Blocks
Control Implementation
Performance
Conclusion
True Random Number Generator Embedded in Reconfigurable Hardware
Introduction
PLL -- Source of Randomness in Recent FPLDs
Analog PLL in Altera FPLD
Jitter Characteristics of Altera PLL Circuitry
Randomness Extraction from an Intrinsic Jitter
Timing Analysis of the Logic Cell in Altera FPLD
Basic Principle of Randomness Extraction
TRNG Realization
Experimental Hardware Implementation
Statistical Evaluation of TRNG
Testing of Basic Statistical Assumption
The NIST Statistical Tests
Conclusions
Evaluation Criteria for True (Physical) Random Number Generators Used in Cryptographic Applications
Introduction
True, Deterministic, and Hybrid Random Number Generators: Main Differences
General Objectives on a TRNG Evaluation
Assessing the Random Number Generation I (Standard Case)
Assessing the Random Number Generation II (Alternative Criteria)
Startup Test, Online Test, Tot Tests
Vulnerability Analysis
Conclusions
A Hardware Random Number Generator
RFID Systems and Security and Privacy Implications
Introduction
A Brief Introduction to RFID Systems
Basic System Components
Transceiver-Transponder Coupling and Communication
Data Coding
Modulation
Tag Anti-collision
Reader Anti-collision
Frequencies and Regulations
The EPC System: A Minimalist Approach
RFID Security Benefits and Threats
Previous Work
Security Goals
Low-Cost RFID Issues
Some Approaches to RFID Protection
Future Research Directions
Conclusions
A New Class of Invertible Mappings
Introduction
Notations and Definitions
Previous Constructions of Invertible Mappings
The New Construction
Testing the Invertibility of Parametric Functions
Cryptographic Applications
Concluding Remarks
Scalable and Unified Hardware to Compute Montgomery Inverse in GF(p) and GF(2n)
1 Introduction
2 Scalable Architecture
3 Montgomery Inverse Procedures for GF(p) and GF(2n)
3.1 Representation and Manipulation of Elements in GF(2n)
3.2 Montgomery Inverse in GF(2n)
3.3 Multi-bit Shifting
4 The Unified and Scalable Inverter Architecture
5 Modeling and Analysis
5.1 Area Comparison
5.2 Speed Comparison
6 Conclusion
Acknowledgments. The authors would like to thank KFUPM-Saudi Arabia and NSF under the CAREER grant CCR-0093434-fiComputer Arithmetic Algorithms and Scalable Hardware Designs for Cryptographic Applicationsfl for providing financial support toward this research.
References
Appendix
Dual-Field Arithmetic Unit for GF(p) and GF(2m)
Introduction
Related Work
Mathematical Background
Addition and Modular Reduction in $GF(p)$
Multiplication and Squaring in $GF(p)$
Inversion in $GF(p)$
Addition in $GF(2^m)$
Multiplication in $GF(2^m)$
Squaring in $GF(2^m)$
Inversion in $GF(2^m)$
Architecture
Results
Conclusion
Error Detection in Polynomial Basis Multipliers over Binary Extension Fields
Introduction
Preliminaries
Multiplication Using Polynomial Basis
Error Detection Strategy
Parity Predictions of Individual Module
Parity Prediction in ( alpha ) Module
Parity Predictions of Sum and Pass-Thru Modules
Error Detections in Polynomial Basis Multipliers
Bit-Parallel PB Multiplier
Bit-Serial PB Multiplier
Conclusions and Future Work
Hardware Implementation of Finite Fields of Characteristic Three
Introduction
Supersingular Elliptic Curves and the Tate Pairing
Polynomial Arithmetic Modulo Three
Addition
Multiplication
Implementation of Arithmetic in ${@mathbb F}{3^{6 p}}$
Timing of Field Operations
Conclusion
Preventing Differential Analysis in GLV Elliptic Curve Scalar Multiplication
Introduction
Differential Analysis and Previous Work on Randomised Endomorphisms
The Gallant-Lambert-Vanstone Computation Method
Elliptic Scalar Multiplication Using Sub-lattices and the GLV Method
Retrieving New $v_1$ and $v_2$
Decomposition of $k$
The Case of Small Determinant
On the Protection Offered by the Randomised GLV Method against DPA
On the Additional Computation Cost of the Randomised GLV Method
An Affine Generalisation
Conclusion
Algorithm for Elliptic Scalar Multiplication Using Sub-lattices
Algorithm for Affine Generalisation
Randomized Signed-Scalar Multiplication of ECC to Resist Power Attacks
Introduction
Elliptic Curve Cryptosystems and Power Attacks
Binary Scalar Multiplication
Power Attacks
Non-adjacent Form(NAF) Recoding Algorithm
The New Countermeasure Based on Randomized Signed-Scalar Representation
Randomized Signed-Scalar Representation
Analysis and Comparisons
Experimental Result
Conclusion
Fast Multi-scalar Multiplication Methods on Elliptic Curves with Precomputation Strategy Using Montgomery Trick
Introduction
Elliptic Curve Operations
Our Contributions
Multi-scalar Multiplication
Simultaneous Scalar Multiplication
Proposed Precomputation Stage
Montgomery Trick
Simultaneous Sliding Window NAF Method
Further Improvement: Reducing the Number of Points in Precomputation
Computational Cost and Comparison
Precomputation Stage
Evaluation Stage
Comparison
Experience Using a Low-Cost FPGA Design to Crack DES Keys
Introduction
Attacks on the IBM 4758 CCA
Banking Security
Optimisation of the Attack Code
The Original Attack
The Optimised Attack
Optimising the Key Search with an FPGA
Cracking Performance
How the DES Cracker Works
Implementation Overview
Implementation of the DES S-Boxes
Pipelining vs. Looping Designs
Results
Conclusions
A Time-Memory Tradeoff Using Distinguished Points: New Analysis & FPGA Results
Introduction
Basic Scheme
Definitions
Algorithms
Overlap Situations
Efficient Mask Functions
Theoretical Analysis
Probability to Reach a Distinguished Point
Compute the Average Chain Length $beta $
Previous Proposals for the Success Rate
A Prediction of the Mergers
A Prediction of the Average Chain Length after Sort
Prediction of Collisions and Final Probability of Success
Memory Complexity
Precomputation Complexity
Processing Complexity
Practical Experiments
DES-40
DES-56
Conclusion
Author Index