Fast Software Encryption: 7th International Workshop, FSE 2000, New York, NY, USA, April 10-12, 2000. Proceedings (Lecture Notes in Computer Science, 1978)

Since 1993, Cryptographic Algorithm Research Has Centered Around The Fast So- Ware Encryption (fse) Workshop. First Held At Cambridge University With 30 Attendees, It Has Grown Over The Years And Has Achieved Worldwide Recognition As A Premiere Conference. It Has Been Held In Belgium, Israel, France, Italy, And, Most Recently, New York. Fse 2000 Was The 7th International Workshop, Held In The United States For The Rst Time. Two Hundred Attendees Gathered At The Hilton New York On Sixth Avenue, To Hear 21 Papers Presented Over The Course Of Three Days: 10{12 April 2000. These Proceedings Constitute A Collection Of The Papers Presented During Those Days. Fse Concerns Itself With Research On Classical Encryption Algorithms And - Lated Primitives, Such As Hash Functions. This Branch Of Cryptography Has Never Been More In The Public Eye. Since 1997, Nist Has Been Shepherding The Adv- Ced Encryption Standard (aes) Process, Trying To Select A Replacement Algorithm For Des. The Rst Aes Conference, Held In California The Week Before Crypto 98, Had Over 250 Attendees. The Second Conference, Held In Rome Two Days Before Fse 99, Had Just Under 200 Attendees. The Third Aes Conference Was Held In Conjunction With Fse 2000, During The Two Days Following It, At The Same Hotel. Specific Stream-cipher Cryptanalysis -- New Ciphers -- Aes Cryptanalysis 1 -- Block-cipher Cryptanalysis 1 -- Power Analysis -- General Stream-cipher Crytanalysis -- Aes Cryptanalysis 2 -- Block-cipher Cryptanalysis 2 -- Theoretical Work. Bruce Schneier (ed.) Includes Bibliographical References And Index. Lecture Notes in Computer Science Preface Table of Contents Real Time Cryptanalysis of A5/1 on a PC Introduction Description of the A5/1 Stream Cipher Previous Attacks Informal Description of the New Attacks Detailed Description of the Attacks Efficient Sampling of Special States Efficient Disk Probing Efficient Disk Storage Efficient Tree Exploration The Biased Birthday Attack Efficient Determination of Initial States Reducing the Preprocessing Time of the Biased Birthday Attack Extracting the Key from a Single Red State Statistical Analysis of the Alleged RC4 Keystream Generator Introduction Description of the Alleged RC4 Cipher and Other Work Previous Analysis of RC4 Analysis of Digraph Probabilities Anomalous RC4 Outputs Extrapolating to Higher Values of $n$ Understanding the Statistical Anomalies Analysis of Fortuitous States Directions for Future Work Conclusions The Software-Oriented Stream Cipher SSC2 Introduction Specification of SSC2 The Word-Oriented Linear Feedback Shift Register The Nonlinear Filter The Lagged-Fibonacci Generator Cryptographic Properties of SSC2 Correlation Analysis of SSC2 Scalability of SSC2 Key Scheduling Scheme Performance Conclusion Mercy: A Fast Large Block Cipher for Disk Sector Encryption Introduction Avalanche and Certificational Weaknesses Mercy Design Goals Description of Mercy T Box Operation M Q State Machine F Function Round Structure Key Schedule Design of Mercy Balanced Feistel Network Key Schedule and S-Boxes $ d_{0ldots 7} $ Operation M Q State Machine F Function Avalanche Whitening Linear and Differential Cryptanalysis Conclusions A Statistical Attack on RC6 Introduction RC6 Outlines A Probabilistic Event on RC6 Encryption On Distinguishing RC6 from a Random Permutation On Recovering the Secret Key A Simplified Approach for Recovering $S_0$ and $S_1$ Improved Approach Without Filtering On the Existence of Similar RC5 Statistics Conclusion Amplified Boomerang Attacks Against Reduced-Round Mars and Serpent Introduction Impact of the Results Boomerangs, Inside-Out Attacks, and the Boomerang-Amplifier Preliminaries The Inside-Out Attack Boomerangs Turning the Boomerang into a Chosen-Plaintext Attack Comparing Boomerangs and Boomerang Amplifiers Boomerang-Amplifiers with 3-Tuples Detecting the Effects of the Boomerang-Amplifiers Amplified Boomerangs and the MARS Core The MARS Core Attacking MARS with a Simple Amplified Boomerang A Boomerang-Amplified Differential-Linear Attack on Eleven Rounds Boomerang-Amplifiers and Serpent Description of Serpent Distinguishing Seven Rounds of Serpent Eight-Round Serpent Key Recovery Attack Conclusions Related Attacks Applying the Attack to Other Algorithms Correlations in RC6 with a Reduced Number of Rounds Introduction $chi ^2$ Tests Correlations in RC6 Small Rotation Amounts $chi ^2$ Statistic of RC6 A Possible Analytical Explanation Weak Keys Attacks on RC6 Distinguishing Attacks Key-Recovery Conclusion On the Interpolation Attacks on Block Ciphers 1 Introduction 2 Mathematical background and definitions 3 Lagrange coefficients, Galois Field Fourier Transform and Boolean functions 3.1 Relation between the Galois Field Fourier Transform and the Lagrange coefficients 3.2 Relation between Boolean functions and its Galois filed polynomial representation 4 Checking algebraic expressions for trap doors 4.1 Undoing the effect of a linear transformation on the output coordinates 4.2 Undoing the effect of a linear transformation on the input coordinates References Stochastic Cryptanalysis of Crypton Introduction An Outline of Crypton Statistical Properties of the Round Function Property (1) Property(2) Stochastic Attack Using Differential Properties Computing Transition Probabilities Attack Procedure Stochastic Cryptanalysis of Crypton Using a Partition of Blocks in 16 Classes Computation of Transition Probabilities Attack Procedure Results Concerning Crypton v1.0 Conclusion Bitslice Ciphers and Power Analysis Attacks Introduction Implementation Attacks Timing Attacks and Simple Power Analysis Differential Power Analysis Higher-Order DPA On Correlation and Decorrelation The Duplication Method Bitslice Ciphers BaseKing Cryptanalysis Protecting Bitslice Ciphers against DPA Key Addition Full State Splitting The Bias Vector Method Coding Results Applicability to 3-Way and Serpent Conclusions First Order vs. Second Order DPA Securing the AES Finalists Against Power Analysis Attacks 1 Introduction 1.1 Research Motivation 1.2 Previous Work 1.3 Paper Overview 2 Fundamental Operations in the AES Algorithms 2.1 Table Lookup Operations 2.2 Bitwise Boolean Functions 2.3 Shift and Rotate Operations 2.4 Addition and Multiplication Modulo 2 32 2.5 Bitwise Permutations 2.6 Polynomial Multiplications over GF(2 8 ) 2.7 Linear Transformations 3 Review of Power Analysis Attacks and Countermeasures 4 Secure Implementations of the AES Fundamental Operations 4.1 Table Lookup Operations 4.2 Bitwise Boolean Functions 4.3 Shift and Rotate Operations 4.4 Addition and Multiplication Modulo 2 32 4.5 Bitwise Permutations 4.6 Polynomial Multiplications over GF(2 8 ) 4.7 Linear Transformations 5 Implementation Details 5.1 Implementations for a Specific Processor 5.2 Algorithm Specific Issues 6 Performance Measurements 7 Conclusions Acknowledgments References Ciphertext only Reconstruction of Stream Ciphers Based on Combination Generators Introduction Theoretical Background Linear Feedback Shift Register Sequences Boolean Functions for Stream Ciphers Recovering the LFSRs Statistical Model Complexity Analysis Simulation Results Recovering of the Combining Function A Simple Algorithm for Fast Correlation Attacks on Stream Ciphers Introduction The Cryptanalyst's Problem and Definitions ML-Decoding of Linear Codes Description of a New Fast Correlation Attack A Theoretical Analysis of the Proposed Algorithm Simulations Results Conclusions A Low-Complexity and High-Performance Algorithm for the Fast Correlation Attacks* Introduction Decoding Concept for the Fast Correlation Attack Novel Appropriate Parity-Check Sets Preliminaries Methods for Construction and Specification of the Parity-Check Sets Expected Cardinalities of the Parity-Check Sets Novel Algorithm for Fast Correlation Attack One-Step Decoding Algorithm - OSDA Iterative Decoding Algorithm - IDA Performance and Complexity Performance Complexity Comparison of the Novel Algorithm with Recently Proposed Improved Fast Correlation Attacks Comparison of the Underlying Principles Comparison of the Performance and Complexity Conclusions Improved Cryptanalysis of Rijndael Introduction The Square Attack The Original 6-round Attack A 7-round Extension An Improvement Extension to 7 Rounds A Second Improvement Extension to 8 Rounds Summary The Key Schedule Partial Key Guessing Key Splitting Summary A 9-Round Related-Key Attack The Key Difference Pattern The Encryptions An Improvement Further Work Summary Conclusions Notation On the Pseudorandomness of the AES Finalists - RC6 and Serpent Introduction Preliminaries Security Model Pseudorandomness of Idealized Twofish Pseudorandomness of Idealized MARS Pseudorandomness of Primitive-Wise Idealized RC6 Primitive-Wise Idealization of RC6 Pseudorandomness of Primitive-Wise Idealized RC6 Pseudorandomness of Primitive-Wise Idealized Serpent Primitive-Wise Idealization of Serpent Pseudorandomness of Primitive-Wise Idealized Serpent Linear Cryptanalysis of Reduced-Round Versions of the SAFER Block Cipher Family Introduction Description of SAFER-K64 The Round Structure The Key Schedule A Mini-Version of SAFER-K64 Linear Cryptanalysis of SAFER Linear Cryptanalysis Homomorphic Linear Relations Non-homomorphic Linear Relations Key-Dependent Linear Relations Search Results Fractional Linear Attacks Methodology Conclusion A Ciphertext-Only Attack A Chosen-Plaintext Linear Attack on DES Introduction Linear Cryptanalysis on DES Chosen-Plaintext Attacks First Attack Second Attack Third Attack Conclusion Provable Security against Differential and Linear Cryptanalysis for the SPN Structure Introduction and Motivation Preliminaries Provable Security against DC Provable Security against LC Provable Security against DC and LC with a Semi-maximal Diffusion Layer Conclusion Unforgeable Encryption and Chosen Ciphertext Secure Modes of Operation Introduction Motivation Applicability Importance of a Single-Key Solution Previous Work Summary of Results Notation Unforgeability Definitions Unforgeability and Chosen Ciphertext Security The Forgeability of Previous Modes Unforgeable Modes of Operation A Stateful Mode A Probabilistic Mode Forthcoming: An Incremental Mode Discussion Efficient Methods for Generating MARS-Like S-Boxes Introduction S-Box Fundamentals MARS Property Requirements MARS Differential Requirements MARS Linear Requirements Satisfaction of MARS Properties S-Box Generation Techniques Summary of MARS S-Box Generation Techniques Summary of our Techniques for Generating MARS-like S-Boxes Experimental Results Property Relationships and Technique Variation Property Relationships Possible Variations on our Techniques Conclusions and Future Research Author Index Fast Software Encryption: 7th International Workshop, FSE 2000 New York, NY, USA, April 10–12, 2000 Proceedings Author: Gerhard Goos, Juris Hartmanis, Jan van Leeuwen, Bruce Schneier Published by Springer Berlin Heidelberg ISBN: 978-3-540-41728-6 DOI: 10.1007/3-540-44706-7 Table of Contents: Real Time Cryptanalysis of A5/1 on a PC Statistical Analysis of the Alleged RC4 Keystream Generator The Software-Oriented Stream Cipher SSC2 Mercy: A Fast Large Block Cipher for Disk Sector Encryption A Statistical Attack on RC6 Amplified Boomerang Attacks Against Reduced-Round MARS and Serpent Correlations in RC6 with a Reduced Number of Rounds On the Interpolation Attacks on Block Ciphers Stochastic Cryptanalysis of Crypton Bitslice Ciphers and Power Analysis Attacks Securing the AES Finalists Against Power Analysis Attacks Ciphertext only Reconstruction of Stream Ciphers Based on Combination Generators A Simple Algorithm for Fast Correlation Attacks on Stream Ciphers A Low-Complexity and High-Performance Algorithm for the Fast Correlation Attack Improved Cryptanalysis of Rijndael On the Pseudorandomness of the AES Finalists - RC6 and Serpent Linear Cryptanalysis of Reduced-Round Versions of the SAFER Block Cipher Family A Chosen-Plaintext Linear Attack on DES Provable Security against Differential and Linear Cryptanalysis for the SPN Structure Unforgeable Encryption and Chosen Ciphertext Secure Modes of Operation This book constitutes the thoroughly refereed post-proceedings of the 7th International Workshop on Fast Software Encryption, FSE 2000, held in New York City, USA in April 2000. The 21 revised full papers presented were carefully reviewed and selected from a total of 53 submissions. The volume presents topical sections on stream-cipher cryptanalysis, new ciphers, AES cryptanalysis, block-cipher cryptanalysis, and theoretical work The papers are organized in topical sections on block ciphers, lightweight block ciphers, tweakable block ciphers, stream ciphers, hash functions, message authentication codes, provable security, implementation aspects, lightweight authenticated encryption, automated cryptanalysis, Boolean functions.