Cryptographic Hardware and Embedded Systems -- CHES 2010: 12th International Workshop, Santa Barbara, USA, August 17-20,2010, Proceedings (Lecture Notes in Computer Science, 6225)

✍ Scribed by Stefan Mangard (editor), Francois-Xavier Standaert (editor)

• Publisher: Springer
• Year: 2010
• Tongue: English
• Leaves: 469
• Category: Library

✦ Synopsis

Since 1999, the workshop on Cryptographic Hardware and Embedded Systems (CHES) is the foremost international scienti?c event dedicated to all aspects of cryptographic hardware and security in embedded systems. Its 12th edition was held in Santa Barbara, California, USA, August 17–20, 2010. Exceptionally this year, it was co-located with the 30th International Cryptology Conference (CRYPTO). This co-location provided unique interaction opportunities for the communities of both events. As in previous years, CHES was sponsored by the International Association for Cryptologic Research (IACR). The workshopreceived 108 submissions, from 28 di?erent countries,of which the Program Committee selected 30 for presentation. Each submission was - viewed by at least 4 committee members, for a total of 468 reviews. Two invited talks completed the technical program. The ?rst one, given by Ivan Damg? ard and Markus Kuhn, was entitled “Is Theoretical Cryptography Any Good in Practice?”, and presented jointly to the CRYPTO and CHES audiences, on Wednesday, August 18, 2010. The second one, given by Hovav Shacham, was entitled “Cars and Voting Machines: Embedded Systems in the Field. ” The Program Committee agreed on giving a best paper award to Alexandre Berzati, C´ ecile Canovas-Dumas and Louis Goubin, for their work “Public Key Perturbation of Randomized RSA Implementations. ” These authors will also be invitedtosubmitanextendedversionoftheirpapertotheJournalofCryptology, together with the authors of two other contributions. First, Jean-Philippe - masson,LucaHenzen,WilliMeierandMar´ ?aNaya-Plasencia,authorsof“Quark: aLightweightHash. ”Second,LucaHenzen,PietroGendotti,PatriceGuillet,- rico Pargaetzi, Martin Zoller and Frank K.

✦ Table of Contents

Title Page
Preface
Organizations
Table of Contents
Low Cost Cryptography
Quark: A Lightweight Hash
Introduction
Description of the Quark Hash Family
Sponge Construction
Permutation
Proposed Instances
Design Rationale
Single Security Level
Sponge Construction
Permutation Algorithm
Preliminary Security Analysis
The Hermetic Sponge Strategy
Generic Second Preimage Attack
Resistance to Cube Attacks and Cube Testers
Resistance to Differential Attacks
Resistance to Slide Distinguishers
Hardware Implementation
Architectures
Methodology
Discussion and Comparison with Present-Based Designs
References
PRINTcipher: A Block Cipher for IC-Printing
Introduction
Design Approach to PRINTcipher
PRINTcipher-48 and PRINTcipher-96
Deriving the Permutations from the User Key
Security Goals
Some Features of the Design
Security Analysis
Differential and Linear Characteristics
High Order Differentials and Algebraic Attacks
Related-Key Attacks
Statistical Saturation Attacks
Implementation Results
Conclusions
References
Appendix
Sponge-Based Pseudo-Random Number Generators
Introduction
Advantages and Limitations of Our Construction
Using a Hash Function for Pseudo-Random Number Generation
Modeling a Reseedable Pseudo-Random Number Generator
Constructing a PRNG Using a Sponge Function
The Sponge Construction
Reusing the State for Multiple Feed and Fetch Phases
Constructing a Reseedable Pseudo-Random Number Generator
Security
Indifferentiability
Resistance against State Recovery
Forward Security
A Concrete Example with Keccak
Conclusions
References
Efficient Implementations I
A High Speed Coprocessor for Elliptic CurveScalar Multiplications over $F_p$
Introduction
Mathematical Background
RNS
Elliptic Curves
Base Choice
Hardware Architecture
Architecture Overview
Pipeline Architecture
Memory
Radix-RNS Transformation
Side Channel Attacks
Result and Comparison
Results
Comparison
Conclusion
References
Co-Z Addition Formulæ and Binary Ladders on Elliptic Curves
Introduction
Preliminaries
Jacobian Coordinates
Co-Z Point Addition
Binary Scalar Multiplication Algorithms
New Implementations
Left-to-Right Scalar Multiplication
Right-to-Left Scalar Multiplication Algorithm
Point Doubling and Tripling
Combined Double-Add Operation
Discussion
Performance Analysis
Security Considerations
Conclusion
References
Efficient Techniques for High-Speed Elliptic Curve Cryptography
Introduction
Preliminaries
The x86-64 Based Processor Family
Optimizations at the Field Arithmetic Level
Field Multiplication
Other ``Cheaper'' Operations
Optimizations at the Point Arithmetic Level
Our Choice of Explicit Formulas
Minimizing the Cost of Point Operations
Minimizing the Effect of Data Dependencies
Optimizations at the Scalar Arithmetic Level
Implementation Using GLS
Implementation Results
References
Side-Channel Attacks and Countermeasures I
Analysis and Improvement of the Random Delay Countermeasure of CHES 2009
Introduction
The Floating Mean Method
The Real Behavior of Floating Mean
Explaining the Cogs
Choosing Correct Parameters
Improved Floating Mean
Analysis
Illustration
Full Algorithm
The Optimal Criterion of Efficiency
Drawbacks of the Coefficient of Variation
The New Criterion
Comparing Efficiency
Conclusion
References
Distribution of Delay's Length d
Efficient Implementation of Improved Floating Mean
New Results on Instruction Cache Attacks
Introduction
I-Cache Attack Concept
Improved Attack Techniques
Spying on the Instruction Cache
Realizing the DSA
The Attack
Closing the Instruction Cache Side-Channel
Performance Evaluation
Conclusions
References
Correlation-Enhanced Power Analysis Collision Attack
Introduction
Hardware Implementation of the AES
Our Implementation
Details on the Masked AES S-Box
Analysis of the AES Implementation
Analysis of the Unprotected Architecture
Analysis of the Masked Architecture
Correlation-Enhanced Collision Attack
Conclusion
References
Side-Channel Analysis of Six SHA-3 Candidates
Introduction
How to Perform Side-Channel Attacks on Hash Functions
Message Authentication Codes with Hash Functions
Side-Channel Attacks
AES-Based SHA-3 Candidates
ECHO
Grøstl
SHAvite-3
Other SHA-3 Candidates
BLAKE
CubeHash
HAMSI
Conclusion and Discussions
References
Tamper Resistance and Hardware Trojans
Flash Memory ‘Bumping’ Attacks
Introduction
Background
Experimental Method
Results
Implications and Further Improvements
Conclusion
References
Self-referencing: A Scalable Side-Channel Approach for Hardware Trojan Detection
Introduction
Motivation of Self-referencing Approach
Methodology
Results
Simulation Results
Experimental Results
Conclusion
References
Appendix
When Failure Analysis Meets Side-Channel Attacks
Introduction
Light Emission as a Side-Channel Signal
Background
Experimental Method
Results
Laser Stimulation to Improve Side-Channel Attacks
Background
Experimental Method
Results
Conclusion
References
Efficient Implementations II
Fast Exhaustive Search for Polynomial Systems in $F_2$
Introduction
Generalities
Known Techniques for Quadratic Polynomials
A Faster Recursive Algorithm for Any Degree
Common Zeroes of Several Multivariate Polynomials
A Brief Description of the Hardware Platforms
Vector Units on x86-64
G2xx-Series Graphics Processing Units from NVIDIA
Implementations
CPU Enumeration Kernel
GPU Enumeration Kernel
Checking Candidates
Partial Evaluation
More Test Data and Discussion
References
256 Bit Standardized Crypto for 650 GE – GOST Revisited
Introduction
Previous Work
Outline
Description of the GOST Encryption Algorithm
The Choice of a Set of S-Boxes
Hardware Implementations
Conclusions
References
Appendix
Mixed Bases for Efficient Inversion in $F((2^2)^2)^2$ and Conversion Matrices of SubBytes of AES
Introduction
Preliminaries
Extension Field $F_2^8$ and Its Tower Construction $F((2^2)^2)^2$
Morioka's Construction Morioka
Canright's Construction [2]
Another Efficient Construction
Conversion Matrices with the Viewpoint of Conjugates
Main Proposal
Mixed Bases for $I_4$ of Fig. 14
Mixed Bases for the Inversion in $F((2^2)^2)^2$
Evaluation
Conclusion and Future Work
Architectures of the Construction Shown in Sec. 2.43
SHA-3
Developing a Hardware Evaluation Method for SHA-3 Candidates
Introduction
Evaluation Methodology
Performance Metrics
SHA-3 Parameters
Defining Specifications
ASIC Realizations
Implementation
Design Flow
Algorithms
Results
High Throughput Scenario
Medium Throughput Scenario
Sources of Error
Conclusions
Hardware Architectures
Fair and Comprehensive Methodology for Comparing Hardware Performance of Fourteen Round Two SHA-3 Candidates Using FPGAs
Introduction and Motivation
Choice of a Language, FPGA Devices, and Tools
Performance Metrics for FPGAs
Speed.
Resource Utilization/Area.
Uniform Interface
Optimization Target and Design Methodology
Results
Conclusions and Future Work
References
Performance Analysis of the SHA-3 Candidates on Exotic Multi-core Architectures
Introduction
Target Platforms
Porting the SHA-3 Candidates to the Cell and GPU
AES-Inspired SHA-3 Candidates
Other SHA-3 Candidates
Conclusion
References
XBX: eXternal Benchmarking eXtension for the SUPERCOP Crypto Benchmarking Framework
Introduction
Judging Security
Judging Performance
Additional Criteria
Motivation for the eXternal Benchmarking eXtension
Design Goals
Hardware
Overview
Microcontroller Family
eXternal Benchmarking Harness XBH
eXternal Benchmarking Device XBD
Software
XBS: Benchmark Control
Algorithms to Benchmark
Hardware Abstraction
Application Framework
Bootloader
Benchmarking Harness
Benchmarking Results
Different Implementations of Skein512 on Atmel ATmega1281
SHA-3 Candidates on an ARM Cortex-M3 32-Bit CPU Using Two Compilers
Conclusion
References
Fault Attacks and Countermeasures
Public Key Perturbation of Randomized RSA Implementations
Introduction
Background
Notations
Modular Exponentiation Algorithms
Exponent Randomization
Description of Our Attack
Bit Analysis of a Randomized Exponent
Fault Model
Result of a Faulty Computation
Analysis
Attack Algorithm
Summary of Our Attack
Performance
Conclusion
Proof of the Theorem 1
Fault Sensitivity Analysis
Introduction
Preliminaries
Common Fault Injection Techniques
DFA and Attack Requirements
FSA Proposal
General Principle of FSA
Data-Dependency of Fault Sensitivity
General FSA Attacks Scenarios
FSA Attack Scenarios against PPRM1-AES
Attack Requirements and Countermeasures for FSA
FSA Attacks against WDDL-AES
WDDL "Protected" against Setup-Time Violation Attacks
Data-Dependency of Fault Sensitivity for WDDL-AES
Practical FSA Attack against WDDL-AES
Conclusions
References
PUFs and RNGs
An Alternative to Error Correction for SRAM-Like PUFs
Introduction
Idea
Modeling and Statistical Aspects
Implementation
Conclusion
Calculations
Numerical Examples
New High Entropy Element for FPGA Based True Random Number Generators
Introduction
New Entropy Element Design Goals
Transition Effect Ring Oscillator
Transistor Level SPICE Simulation
TERO Mathematical Model Based on Effects of Intrinsic Noise
Analytical Comparison of the TERO and RO Modes
TERO and RO Response under External Perturbations
Hardware Implementation
Experimental Results
Conclusion and Future Work
References
The Glitch PUF: A New Delay-PUF Architecture Exploiting Glitch Shapes
Introduction
Background
Our Contributions
Simulating Behavior of Delay-PUFs
Glitch PUFs
Basic Idea
Overall Sequence
Acquisition of Glitch Waveforms
Conversion to Response
Reliability Enhancement
The Architecture
Adjustment of the Design Parameter
Experimental Results
Inter-chip Variation
Intra-chip Variation
Secrecy Rate
Conclusions
References
New Designs
Garbled Circuits for Leakage-Resilience: Hardware Implementation and Evaluation of One-Time Programs
Introduction
Our Contributions and Outline
Related Work
Preliminaries
Extending and Using One-Time Programs
Extending One-Time Programs
Using One-Time Programs for Leakage Protection
Efficient Evaluation of Garbled Circuits in Hardware
Architecture for Evaluating Garbled Circuits in Hardware
Compile-Time Optimizations for Memory-Constrained Devices
Implementation
References
ARMADILLO: A Multi-purpose Cryptographic Primitive Dedicated to Hardware
Introduction
The ARMADILLO Function
Dedicated Attacks
Permutation-Dependent Attacks
Parameter Vectors
ARMADILLO2
Hardware Implementation and Performance
Comparison
Conclusions
References
Side-Channel Attacks and Countermeasures II
Provably Secure Higher-Order Masking of AES
Introduction
Preliminaries on Higher-Order Masking
Basic Principle
Soundness of Higher-Order Masking
Higher-Order Masking Schemes
The Ishai-Sahai-Wagner Scheme
Higher-Order Masking of AES
Higher-Order Masking of the AES S-Box
Higher-Order Masking of the Whole Cipher
Security Analysis
Implementation Results
Conclusion
References
Algebraic Side-Channel Analysis in the Presence of Errors
Introduction
Background
Causes of Errors in Side-Channel Information
Contributions
Algebraic Side-Channel Attacks
General Structure of an Algebraic Attack
Naïve Methods of Dealing with Errors
Handling Errors by Pseudo-Boolean Representation
Side-Channel Analysis as a Pseudo-Boolean Problem
An Introduction to Pseudo-Boolean Optimizers
Elements of a TASCA Equation Set
An Attack on Keeloq
The Keeloq Algorithm
An Equation Set for Keeloq
Attack Results
Preliminary Results on AES
The AES Algorithm
An Equation Set for AES
Initial Results
Open Issues
Full Attack against AES and Other Ciphers
Better PB Solvers
TASCA as Part of the Design Tool Chain
Conclusion
References
Coordinate Blinding over Large Prime Fields
Introduction
Preliminaries
Elliptic Curves
Side-Channel Resistant Scalar Multiplication
Implementing Elliptic Curve Arithmetic
Homogeneous Projective Coordinates
Jacobian Projective Coordinates
Choosing μ and ν
Implementation Considerations
Using Montgomery Multiplication
Generating $f$
Performance
Further Security Considerations
Conclusion
References
Author Index