Lecture Notes in Computer Science 4047 CommencedPublicationin1973 FoundingandFormerSeriesEditors: GerhardGoos,JurisHartmanis,andJanvanLeeuwen EditorialBoard DavidHutchison LancasterUniversity,UK TakeoKanade CarnegieMellonUniversity,Pittsburgh,PA,USA JosefKittler UniversityofSurrey,Guildford,UK JonM.Kleinberg CornellUniversity,Ithaca,NY,USA FriedemannMattern ETHZurich,Switzerland JohnC.Mitchell StanfordUniversity,CA,USA MoniNaor WeizmannInstituteofScience,Rehovot,Israel OscarNierstrasz UniversityofBern,Switzerland C.PanduRangan IndianInstituteofTechnology,Madras,India BernhardSteffen UniversityofDortmund,Germany MadhuSudan MassachusettsInstituteofTechnology,MA,USA DemetriTerzopoulos UniversityofCalifornia,LosAngeles,CA,USA DougTygar UniversityofCalifornia,Berkeley,CA,USA MosheY.Vardi RiceUniversity,Houston,TX,USA GerhardWeikum Max-PlanckInstituteofComputerScience,Saarbruecken,Germany Matthew Robshaw (Ed.) Fast Software Encryption 13th International Workshop, FSE 2006 Graz, Austria, March 15-17, 2006 Revised Selected Papers 1 3 VolumeEditor MatthewRobshaw TelecomResearchandDevelopment 38-40rueduGeneralLeclerc,92794IssylesMoulineaux,Cedex9,France E-mail:[email protected] LibraryofCongressControlNumber:2006928940 CRSubjectClassification(1998):E.3,F.2.1,E.4,G.2,G.4 LNCSSublibrary:SL4–SecurityandCryptology ISSN 0302-9743 ISBN-10 3-540-36597-4SpringerBerlinHeidelbergNewYork ISBN-13 978-3-540-36597-6SpringerBerlinHeidelbergNewYork Thisworkissubjecttocopyright.Allrightsarereserved,whetherthewholeorpartofthematerialis concerned,specificallytherightsoftranslation,reprinting,re-useofillustrations,recitation,broadcasting, reproductiononmicrofilmsorinanyotherway,andstorageindatabanks.Duplicationofthispublication orpartsthereofispermittedonlyundertheprovisionsoftheGermanCopyrightLawofSeptember9,1965, initscurrentversion,andpermissionforusemustalwaysbeobtainedfromSpringer.Violationsareliable toprosecutionundertheGermanCopyrightLaw. SpringerisapartofSpringerScience+BusinessMedia springer.com ©Springer-VerlagBerlinHeidelberg2006 PrintedinGermany Typesetting:Camera-readybyauthor,dataconversionbyScientificPublishingServices,Chennai,India Printedonacid-freepaper SPIN:11799313 06/3142 543210 Preface Fast Software Encryption (FSE) 2006 is the 13th in a series of workshops on symmetric cryptography. It has been sponsored for the last five years by the International Association for Cryptologic Research (IACR), and previous FSE workshops have been held around the world: 1993 Cambridge, UK 1994 Leuven, Belgium 1996 Cambridge, UK 1997 Haifa, Israel 1998 Paris,France 1999 Rome, Italy 2000 New York, USA 2001 Yokohama,Japan 2002 Leuven, Belgium 2003 Lund, Sweden 2004 New Delhi, India 2005 Paris,France The FSE workshop is devoted to research on fast and secure primitives for symmetric cryptography, including the design and analysis of block ciphers, stream ciphers, encryption schemes, analysis and evaluation tools, hash func- tions, and message authentication codes. This year more than 100 papers were submitted to FSE for the first time. After anextensivereviewbythe ProgramCommittee,27paperswerepresented atthe workshop.Ofcourse,the programwouldnothavebeencompletewithout the invited speaker, and the presentation by Eli Biham on the early history of differential cryptanalysis was particularly appreciated by workshopattendees. We are very grateful to the Program Committee and to all the external reviewers for their hard work. Each paper was refereed by at least three re- viewers, with papers from Program Committee members receiving at least five reviews.ThelocalOrganizingCommitteeatGrazworkedveryhardandwepar- ticularlythank Melanie Blauensteiner,ChristopheDe Canni`ere,SharifIbrahim, Florian Mendel, Norbert Pramstaller, Christian Rechberger, and Michaela Tretter-Dragovic for their generous efforts and strong support. In Paris we are indebted to Henri Gilbert and Helena Handschuh, who shared their valuable experience from FSE 2005, and to Coˆme Berbain and Olivier Billet for proof- reading and preparing the FSE pre-proceedings. Toclose,wethanktheIACRsecretariat,KevinMcCurley,andShaiHalevifor theirhelpwiththeregistrationprocessandwethanktheIACRfortheirsupport ofFSE.We aregratefultoK.U.Leuvenfortheirweb-basedreviewsoftwareand we thank both France Telecom and Siemens, Munich for their financial support of FSE 2006. Matt Robshaw France Telecom R&D FSE 2006 ProgramChair Vincent Rijmen Graz University of Technology FSE 2006 General Chair FSE 2006 March 15-17, 2006, Graz, Austria Sponsored by the International Association for Cryptologic Research (IACR) Program and General Chairs Matt Robshaw ..........France Telecom R&D ProgramChair Vincent Rijmen .........Graz University of Technology General Chair Program Committee Kazumaro Aoki .........NTT, Japan Steve Babbage ..........Vodafone, UK Anne Canteaut .........INRIA, France Carlos Cid ..............Royal Holloway,University of London, UK Joan Daemen ...........STMicroelectronics, Belgium Orr Dunkelman .........Technion–IsraelInstituteofTechnology,Israel Helena Handschuh ......Spansion, France Thomas Johansson ......Lund University, Sweden Antoine Joux ...........DGA and University of Versailles, France Charanjit Jutla .........IBM Watson Research Center, USA Xuejia Lai ..............Shanghai Jiaotong University, China Stefan Lucks ............University of Mannheim, Germany Mitsuru Matsui .........Mitsubishi Electric, Japan Willi Meier .............FH Aargau, Switzerland Kaisa Nyberg ...........HelsinkiUniversityofTechnologyandNokia,Finland Elisabeth Oswald .......Graz University of Technology, Austria Bart Preneel ............K.U.Leuven, Belgium H˚avard Raddum ........University of Bergen, Norway Matt Robshaw ..........France Telecom R&D, France Phillip Rogaway ........U.C.Davis,USAandMahFahLuangUniv.,Thailand Moti Yung ..............RSASecurityandColumbiaUniversity,USA Sponsors France Telecom R&D Siemens, Munich VIII Organization External Reviewers Frederik Armknecht Daniel Augot Elad Barkan Mihir Bellare Coˆme Berbain Dan Bernstein Eli Biham Alex Biryukov John Black Nick Bone Christophe de Canni`ere Pascale Charpin Fr´ed´ericDidier Claus Diem Martin Feldhofer Henri Gilbert Louis Granboulan Johann Groszschaedl Shai Halevi Philip Hawkes Martin Hell Christoph Herbst Tetsu Iwata Nathan Keller John Kelsey Alexander Kholosha Lars Knudsen Ted Krovetz Ulrich Ku¨hn Simon Ku¨nzli Joe Lano C´edric Lauradoux Stefan Mangard Florian Mendel Marine Minier Sean Murphy Anderson Nascimento Philippe Oechslin Matthew Parker Ludovic Perret Raphael C.-W. Phan Norbert Pramstaller Christian Rechberger Vincent Rijmen Greg Rose Markku-JuhaniO. Saarinen Tsuneo Sato Eric Schost Tom Shrimpton Herv´e Sibert Dirk Stegemann John Steinberger Michael Steiner Stefan Tillich Jean-PierreTillich Hiroki Ueda Charlotte Vikkelso Johan Wall´en Dai Watanabe Ralf-Philipp Weinmann Doug Whiting Go Yamamoto Kan Yasuda Table of Contents Stream Ciphers I Cryptanalysis of Achterbahn Thomas Johansson, Willi Meier, Fr´ed´eric Muller .................. 1 Cryptanalysis of Grain Coˆme Berbain, Henri Gilbert, Alexander Maximov ................. 15 Cryptanalysis of the Stream Cipher DECIM Hongjun Wu, Bart Preneel ...................................... 30 Block Ciphers On Feistel Structures Using a Diffusion Switching Mechanism Taizo Shirai, Kyoji Shibutani .................................... 41 PseudorandomPermutation Families over Abelian Groups Louis Granboulan, E´ric Levieil, Gilles Piret ....................... 57 A Zero-Dimensional Gro¨bner Basis for AES-128 Johannes Buchmann, Andrei Pyshkin, Ralf-Philipp Weinmann ...... 78 Hash Functions I Cryptanalysis of the Full HAVAL with 4 and 5 Passes Hongbo Yu, Xiaoyun Wang, Aaram Yun, Sangwoo Park ............ 89 Collisions and Near-Collisions for Reduced-Round Tiger John Kelsey, Stefan Lucks ...................................... 111 Analysis of Step-Reduced SHA-256 Florian Mendel, Norbert Pramstaller, Christian Rechberger, Vincent Rijmen................................................ 126 Analysis Improved Linear Distinguishers for SNOW 2.0 Kaisa Nyberg, Johan Wall´en .................................... 144 X Table of Contents Reducing the Space Complexity of BDD-Based Attacks on Keystream Generators Matthias Krause, Dirk Stegemann................................ 163 Breaking the ICE - Finding Multicollisions in Iterated Concatenated and Expanded (ICE) Hash Functions Jonathan J. Hoch, Adi Shamir .................................. 179 Proposals A New Dedicated 256-Bit Hash Function: FORK-256 Deukjo Hong, Donghoon Chang, Jaechul Sung, Sangjin Lee, Seokhie Hong, Jaesang Lee, Dukjae Moon, Sungtaek Chee ........... 195 Some Plausible Constructions of Double-Block-Length Hash Functions Shoichi Hirose................................................. 210 Provably Secure MACs from Differentially-Uniform Permutations and AES-Based Implementations Kazuhiko Minematsu, Yukiyasu Tsunoo........................... 226 Hash Functions II Searching for Differential Paths in MD4 Martin Schla¨ffer, Elisabeth Oswald ............................... 242 A Study of the MD5 Attacks: Insights and Improvements John Black, Martin Cochran, Trevor Highland ..................... 262 The Impact of Carries on the Complexity of Collision Attacks on SHA-1 Florian Mendel, Norbert Pramstaller, Christian Rechberger, Vincent Rijmen................................................ 278 Modes and Models A New Mode of Encryption Providing a Tweakable Strong Pseudo-randomPermutation Debrup Chakraborty, Palash Sarkar .............................. 293 New BlockcipherModes of Operationwith Beyondthe BirthdayBound Security Tetsu Iwata ................................................... 310 Table of Contents XI The Ideal-Cipher Model, Revisited: An Uninstantiable Blockcipher-BasedHash Function John Black.................................................... 328 Implementation and Bounds How Far Can We Go on the x64 Processors? Mitsuru Matsui ................................................ 341 Computing the Algebraic Immunity Efficiently Fr´ed´eric Didier, Jean-Pierre Tillich .............................. 359 Upper Bounds on Algebraic Immunity of Boolean Power Functions Yassir Nawaz, Guang Gong, Kishan Chand Gupta ................. 375 Stream Ciphers II Chosen-Ciphertext Attacks Against MOSQUITO Antoine Joux, Fr´ed´eric Muller................................... 390 Distinguishing Attacks on the Stream Cipher Py Souradyuti Paul, Bart Preneel, Gautham Sekar .................... 405 Resynchronization Attacks on WG and LEX Hongjun Wu, Bart Preneel ...................................... 422 Author Index................................................... 433 Cryptanalysis of Achterbahn Thomas Johansson1, Willi Meier2,(cid:2), and Fr´ed´eric Muller3 1 Department of Information Technology, LundUniversity P.O.Box 118, 221 00 Lund,Sweden [email protected] 2 FH Aargau, 5210 Windisch, Switzerland [email protected] 3 HSBC-France [email protected] Abstract. We present several attacks against the Achterbahn stream cipher,whichwasproposedtotheeSTREAMcompetition.Wecanbreak thereduced and thefull version with complexity of 255 and 261 steps. Extensionsofourattacksarealsodescribedtobreakmodifiedversions of the Achterbahn stream cipher, which were proposed following the publication of preliminary cryptanalysis results. These attacks highlight some problems in the design principle of Achterbahn,i.e.,combiningtheoutputsofseveralnonlinear(butsmall) shift registers using a nonlinear (butrather sparse) output function. 1 Introduction The European project ECRYPT recently decided to launch a competition to identify new stream ciphers that might be suitable for widespread adoption. This projectis calledeSTREAM[3]andreceived35submissions,someofwhich have already been broken. Among these new algorithms, a challenging new design is Achterbahn [5]. It is a relatively simple, hardware-oriented stream cipher, using a secret key of 80 bits. In this paper, we present several attacks which break the cipher faster than a brute force attack. Our results provide new directions to break stream ciphers built by combination of several small, but nonlinear shift registers, like Achterbahn. 2 Description of Achterbahn 2.1 General Structure Achterbahn uses 8 small non-linear registers, denoted by R ,...,R . Their size 1 8 ranges from 22 to 31 bits (see Table 1). The total size of the internal state is (cid:2) The second author is supported by Hasler Foundation www.haslerfoundation.ch underproject number2005. M.J.B.Robshaw(Ed.):FSE2006,LNCS4047,pp.1–14,2006. (cid:2)c InternationalAssociationforCryptologicResearch2006