Fast Software Encryption: 14th International Workshop, FSE 2007, Luxembourg, Luxembourg, March 26-28, 2007, Revised Selected Papers (Lecture Notes in Computer Science, 4593)

Annotation This book contains the thoroughly refereed post-proceedings of the 14th International Workshop on Fast Software Encryption, FSE 2007, held in Luxembourg, Luxembourg, March 2007. It addresses all current aspects of fast and secure primitives for symmetric cryptology, covering hash function cryptanalysis and design, stream ciphers cryptanalysis, theory, block cipher cryptanalysis, block cipher design, theory of stream ciphers, side channel attacks, and macs and small block ciphers Title Page Preface FSE 2007 Table of Contents Producing Collisions for Panama, Instantaneously Introduction Description of $\panama$ Structure of the Attack Collision in the Buffer Collision in the State Difference Propagation Through $\gamma$ Specifying the Trail Symmetric Patterns Techniques for Equation Transfer Immediate Satisfaction in W Bridge from W to T Side Bridge Dependency Removal The Conditions Due to Differential (dT, dU Solving the Equations by Correction TheChosenTrail Equation Transfer in the Chosen Trail Subcollisions I and V Subcollision II Subcollision III Subcollision IV Example of Collision and Workload References Cryptanalysis of FORK-256 Introduction Description of FORK-256 Preliminary Observations on FORK-256 Micro-collisions in $Q_L$ and $Q_R$ Necessary and Sufficient Condition for Micro-collisions A First Attempt with a Simple Differential Path Near-Collision at the Seventh Round Choosing the Difference Near-Collisions for FORK-256’s Compression Function Finding High-Level Differential Paths in FORK-256 More General Variant of Path Finding Collisions for the Full Compression Function Finding Collisions with Low Memory Requirements Finding Collisions Faster with Precomputed Tables Compression Function’s Collisions Turned into Hash Ones References The Grindahl Hash Functions Introduction The Grindahl Design General Strategy Invertibility Design Approach for the Permutation Birthday Attacks Design Parameters for the Permutation Design Parameters for the Output Transformation Proposals for Hash Functions Grindahl-256 Grindahl-512 Padding Rule Security Analysis Designing Secure Compression Functions Implementation Software Performance On Hardware Implementations On Hashing Small Messages Memory Requirements Conclusion References Overtaking VEST Introduction Description of VEST Counter Linear Counter Diffusor Accumulator Output Combiner Key Setup Mode IV Setup Mode Basic Weaknesses of VEST Components Differential Characteristics of the Registers Collision in the Counter Diffusor Partial Keyed State Recovery Attack with Long IVs Attack with Short IVs KeyRecovery Backtracking the Key Setup Second Phase Meet-in-the-Middle Attack Key Recovery Through Related-Key Attack Security Discussion Existential Forgeries for VEST Hash MAC Mode Conclusion References Cryptanalysis of Achterbahn-128/80 Introduction Main Specifications of Achterbahn-128/80 Main Specifications of Achterbahn-128 Main Specifications of Achterbahn-80 The Key-Loading Algorithm Attack Against Achterbahn Version 2 in 2 in $\boldsymbol{2^{53}}$ Principle of Hell and Johansson Attack Complexity Example with Achterbahn Version 2 Improvement of the Attack Against Achterbahn Version 2 Distinguishing Attacks Against Achterbahn-128/80 Distinguishing Attack Against Achterbahn-80 Distinguishing Attack Against Achterbahn-128 Attack with a New Keystream Limitation Recovering the Key References Differential-Linear AttacksAgainst the Stream Cipher Phelix* Introduction The Stream Cipher Phelix The Differential Propagation of Addition A Basic Key Recovery Attack on Phelix The Bias in the Differential Distribution of the Keystream Recovering the Key Improving the Attack on Phelix Recovering $Z^{(i)$ Recovering $X_{i+1,0}$ An Approach to Strengthen Helix and Phelix Conclusion References How to Enrich the Message Space of a Cipher Introduction Preliminaries TheXLSConstruction The Mixing Function The Bit Flips SecurityofXLS Supporting Tweaks XLS with Ordinary PRPs References Security Analysis of Constructions Combining FIL Random Oracles Introduction Definitions and Notations Security Analysis for Preimage Resistance Security Analysis for Collision Resistance Application to Previously Proposed Schemes Concluding Remarks References Bad and Good Ways of Post-processing Biased Physical Random Numbers Introduction An Ineffective Post-processing Method for Biased Random Numbers The E-Transform True and Claimed Properties of the E-Transform What Is Really Going on in the E-Transform Attacking the Post-processed Output of the E-Transform Attacking Unknown Quasigroups and Leaders Two Classes of Random Number Post-processing Functions Improved Random Number Post-processing Functions with a Fixed Number of Input Bits The Concrete Problem Considered A Solution for Low Area Hardware Implementation Analysis of H Improving An Even Better Solution What About Going Further? The Entropy of S On the Implementation of S Conclusion and Further Research Topics References Improved Slide Attacks Introduction Related-Key Attacks and Slide Attacks Related-Key Attacks Slide Attacks Our New Technique Studying the Cycle Structure Using the Cycles in the Slide Attack Several Attacks on Reduced Round GOST A Short Description of GOST Description of the Attack Analysis of the Attack Other Results on GOST Summary and Conclusions References A New Class of Weak Keys for Blowfish Introduction Our Contributions and Organization of the Paper Notation High Level Descriptions of Blowfish New Models for Description Reflection Properties of Blowfish Two Reflection Attacks First Attack Second Attack Improvement of Vaudenay’s Cryptanalysis on a Subset of Keys Discussion of Attacks References The 128-Bit Blockcipher CLEFIA (Extended Abstract) Introduction Notations Specification Definition of $\textit{GFN}_{d,r}$ Data Processing Part Key Scheduling Part F-Functions Constant Values Design Rationale Evaluations Security Performance Conclusion References New Lightweight DES Variants Introduction Design Considerations for Lightweight Block Ciphers DESL and DESXL: Design Ideas and Security Consideration Design Criteria of DESL Improved Resistance Against Differential Cryptanalysis and Davis Murphy Attack Improved Resistance Against Linear Cryptanalysis 4R Iterative Linear Approximation 5R Iterative Linear Approximation nR Iterative Linear Approximation Resistance Against Algebraic Attacks Improved S-Box Lightweight Implementation of DESL Results and Conclusion References A New Attack on 6-Round IDEA Introduction Description of IDEA and the Notations Used in the Paper A New Attack on 5.5-Round IDEA The First Component — A Linear Equation Involving the LSBs of the Intermediate Encryption Values The Second Component — A Square-Like Structure The Third Component — Exploiting the Weak Key Schedule Analysis and Improvement of the Basic Attack The 6-Round Attack An Improved 5-Round Attack A 5-Round Attack Using Only 16 Known Plaintexts Summary and Conclusions References Related-Key Rectangle Attacks on Reduced AES-192 and AES-256* Introduction Description of AES The Related-Key Rectangle Attack Related-Key Rectangle Attack on 10-Round AES-192 8-Round Related-Key Rectangle Distinguisher Key Recovery Attack on 10-Round AES-192 with 256 Related Keys Reducing the Number of Related Keys from 256 to 64 Related-Key Rectangle Attacks on 8-Round AES-192 and 9-Round AES-256 Comments on the 9-Round AES-192 Attack Presentedat Eurocrypt 2005 Conclusion References An Analysis of XSL Applied to BES Introduction The XSL Attack on BES A Summary of the XSL Attack A Summary of the BES Cipher An Analysis of This Attack Analysing the Extended S-Box Equations Adding the Extended Linear Equations Further Analysis Conclusion References On the Security of IV Dependent Stream Ciphers* Introduction Outline of Our Results Security Model Basic Security Notions Security Requirements for an IV-Dependent Stream Ciphers Security of the Generic Construction A Simple Composition Theorem A Tree Based Stream Cipher Construction The Tree Based Construction Resulting Stream Cipher Construction Efficiency Considerations Application to the quad Stream Cipher Conclusion References Two General Attacks on Pomaranch-Like Keystream Generators Introduction Description of Pomaranch Pomaranch Version 1 Pomaranch Version 2 Pomaranch Version 3 Previous Attacks on the Pomaranch Stream Ciphers Distinguishing Attacks on Pomaranch-Like Ciphers Period of Registers Filter Function Linear Approximations of Jump Registers Attacking Different Versions of Pomaranch Attack Complexities for the Existing Versions of the Pomaranch Family Square Root IV Attack Attack Complexities on Pomaranch Conclusions References Analysis of $\qq$ Introduction Questions Conclusions Previous Work Future Work The $\qq$ Family of Stream Ciphers Definition of $\qq$ Parameter Restrictions Example: $\qq$(256, 20, 20) Nonces How to Solve Multivariate Systems History of Lazard-Faug`ere Solvers:$\mathbf{F_4}$, $\mathbf{F_5}$ , XL, XL2, FXL Algorithm XL (eXtended Linearization) at Degree D XL2, F4 and F5 Practicalities: XL with Wiedemann, and Ramifications Broken Parameters for $\qq$ Overview: Using Algebraic Attacks Against $\qq$ Example: Breaking $\qq$(256, 20, 20) Asymptotics for Attacking $\qq$(q,n, n) Directly (q large) Asymptotics for Attacking $\qq$(2, n, n) Directly Which Field Is Best? The State of System-Solving Cryptanalysis Unprovable Parameters for $\qq$ Overview: Attacking the Underlying Hard Problem Example: $\qq$(256, 20, 20) Example: $\qq$(16, 40, 40) Examples: $\qq$(2, 160, 160), (2, 256, 256), (2, 350, 350) Proven and Unproven Parameters for $\qq$ References Message Freedom in MD4 and MD5 Collisions:Application to APOP Introduction Background and Notation APOP MD4 and MD5 Wang’s Attack Against MD4 and MD5 A New Approach to Collision Finding Previous Works Our Method Choosing a Part of the Message MD4 Message Freedom MD5 Message Freedom Applications The APOP Attack in Practice References New Message Difference for MD4 Introduction Preliminaries Specification of MD4 [5] Related Work 1: Collision Attack by Wang et al. and ItsImprovement by Previous Works Related Work 2: Differential Path Search by Schl ̈affer and Oswald [6] New Local Collision Importance of Selecting $\delta$M Problem of Wang et al.’s Local Collision and Constructing New Local Collision Construction of New Local Collision New Message Difference Differential Path Search Algorithm Definition of Good DPC Overview of Problems of Previous Work [6] and Our Improvement Details of Our New Proposed Algorithm for the First Round Attack Implementation Message Modification Attack Procedure and Complexity Estimation Comparison with Previous Attacks Conclusion References Algebraic Cryptanalysis of 58-Round SHA-1 Introduction Preliminaries Description of SHA-1 Definition and Notation An Improved Message Modification Technique How to Calculate Sufficient Conditions on the $a_i$ ? Gaussian Elimination and Controlled Relations Conventional/Advanced Message Modification Techniques An Algebraic Description of the Improved Message Modification Analysis of the 58-Round SHA-1 Using the Improved Message Modification A Concluding Note References Algebraic Immunity of S-Boxes and Augmented Functions Introduction Algebraic Properties of S-Boxes Implicit Equations Conditional Equations Algorithmic Methods Algebraic Attacks Based on the Augmented Function Generic Scenarios for Filter Generators Equations Induced by Annihilators Sampling Basic Scenario Refined Basic Scenario Substitution of Equations First Application: Some Specific Filter Generators Existence of Equations Probabilistic Equations Discussion of Attacks Second Application: Trivium Sampling Potential Attacks Conclusions References Generalized Correlation Analysis of Vectorial Boolean Functions Introduction Generalized Correlation Analysis of Vector Output Stream Ciphers Efficient Computation of the Generalized Nonlinearity Reduction in Complexity Experimental Results Upper Bound on Generalized Nonlinearity Spectral Characterization and Generalized Correlation Immunity Equivalence of Generalized Correlation Immunity and Usual Correlation Immunity Generalized Nonlinearity of Secondary Constructions References An Analytical Model for Time-Driven Cache Attacks Introduction Time-Driven Cache Attacks Last Round Correlation Attack AnalyticalModel Experimental Results References Improving the Security of MACs Via Randomized Message Preprocessing Introduction Notation and Basic Definitions Salted Hashing and MACs A Generic Construction poly: Hashing by Polynomial Evaluation Cascade Construction A Generic Construction from -$\epsilon$-$\Delta$ Universal HashFunctions Numerical Example Related Work and Open Problems References New Bounds for PMAC, TMAC, and XCBC Introduction Preliminaries PMAC Description and Previous Security Proof New Security Bound for PMAC TMACandXCBC New Security Bounds for TMAC and XCBC Proof of Theorem 3 Conclusion and Future Work References Perfect Block Ciphers with Small Blocks* Introduction Notations Random Permutation Selection Repartitor Splitter InvSplitter Permutator InvPermutator Sampling Following the Hypergeometric Distribution Acceptance-Rejection Method Aka. Rejection Sampling Upper-Bounding Distributions Cauchy-Lorentz Distribution by Inverse Method Description of Repartitor Security Model Conclusion References Author Index