Algorithmic cryptAnAlysis © 2009 by Taylor and Francis Group, LLC C7002_FM.indd 1 5/11/09 1:11:54 PM CHAPMAN & HALL/CRC CRYPTOGRAPHY AND NETWORK SECURITY Series Editor Douglas R. Stinson Published Titles Jonathan Katz and Yehuda Lindell, Introduction to Modern Cryptography Antoine Joux, Algorithmic Cryptanalysis Forthcoming Titles Burton Rosenberg, Handbook of Financial Cryptography Maria Isabel Vasco, Spyros Magliveras, and Rainer Steinwandt, Group Theoretic Cryptography Shiu-Kai Chin and Susan Beth Older, Access Control, Security and Trust: A Logical Approach © 2009 by Taylor and Francis Group, LLC C7002_FM.indd 2 5/11/09 1:11:54 PM Chapman & Hall/CRC CRYPTOGRAPHY AND NETWORK SECURITY Algorithmic cryptAnAlysis Antoine Joux © 2009 by Taylor and Francis Group, LLC C7002_FM.indd 3 5/11/09 1:11:54 PM Chapman & Hall/CRC Taylor & Francis Group 6000 Broken Sound Parkway NW, Suite 300 Boca Raton, FL 33487-2742 © 2009 by Taylor and Francis Group, LLC Chapman & Hall/CRC is an imprint of Taylor & Francis Group, an Informa business No claim to original U.S. Government works Printed in the United States of America on acid-free paper 10 9 8 7 6 5 4 3 2 1 International Standard Book Number: 978-1-4200-7002-6 (Hardback) This book contains information obtained from authentic and highly regarded sources. Reasonable efforts have been made to publish reliable data and information, but the author and publisher cannot assume responsibility for the validity of all materials or the consequences of their use. The authors and publishers have attempted to trace the copyright holders of all material reproduced in this publication and apologize to copyright holders if permission to publish in this form has not been obtained. If any copyright material has not been acknowledged please write and let us know so we may rectify in any future reprint. Except as permitted under U.S. Copyright Law, no part of this book may be reprinted, reproduced, transmit- ted, or utilized in any form by any electronic, mechanical, or other means, now known or hereafter invented, including photocopying, microfilming, and recording, or in any information storage or retrieval system, without written permission from the publishers. For permission to photocopy or use material electronically from this work, please access www.copyright. com (http://www.copyright.com/) or contact the Copyright Clearance Center, Inc. (CCC), 222 Rosewood Drive, Danvers, MA 01923, 978-750-8400. CCC is a not-for-profit organization that provides licenses and registration for a variety of users. For organizations that have been granted a photocopy license by the CCC, a separate system of payment has been arranged. Trademark Notice: Product or corporate names may be trademarks or registered trademarks, and are used only for identification and explanation without intent to infringe. Library of Congress Cataloging‑in‑Publication Data Joux, Antoine. Algorithmic cryptanalysis / Antoine Joux. p. cm. -- (Chapman & Hall/CRC cryptography and network security) Includes bibliographical references and index. ISBN 978-1-4200-7002-6 (hardcover : alk. paper) 1. Computer algorithms. 2. Cryptography. I. Title. III. Series. QA76.9.A43J693 2009 005.8’2--dc22 2009016989 Visit the Taylor & Francis Web site at http://www.taylorandfrancis.com and the CRC Press Web site at http://www.crcpress.com © 2009 by Taylor and Francis Group, LLC C7002_FM.indd 4 5/11/09 1:11:54 PM A` Katia, Anne et Louis © 2009 by Taylor and Francis Group, LLC Contents Preface I Background 1 A bird’s-eye view of modern cryptography 3 1.1 Preliminaries . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.1.1 Typical cryptographic needs . . . . . . . . . . . . . . . 6 1.2 Defining security in cryptography . . . . . . . . . . . . . . . 10 1.2.1 Distinguishers. . . . . . . . . . . . . . . . . . . . . . . 11 1.2.2 Integrity and signatures . . . . . . . . . . . . . . . . . 16 1.2.3 Authenticated encryption . . . . . . . . . . . . . . . . 17 1.2.4 Abstracting cryptographic primitives . . . . . . . . . . 21 2 Elementary number theory and algebra background 23 2.1 Integers and rational numbers . . . . . . . . . . . . . . . . . 23 2.2 Greatest common divisors in Z . . . . . . . . . . . . . . . . . 26 2.2.1 Binary GCD algorithm . . . . . . . . . . . . . . . . . 30 2.2.2 Approximations using partial GCD computations . . . 31 2.3 Modular arithmetic . . . . . . . . . . . . . . . . . . . . . . . 33 2.3.1 Basic algorithms for modular arithmetic . . . . . . . . 34 2.3.2 Primality testing . . . . . . . . . . . . . . . . . . . . . 38 2.3.3 Specific aspects of the composite case . . . . . . . . . 41 2.4 Univariate polynomials and rational fractions . . . . . . . . . 44 2.4.1 Greatest common divisors and modular arithmetic . . 45 2.4.2 Derivative of polynomials . . . . . . . . . . . . . . . . 47 2.5 Finite fields . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47 2.5.1 The general case . . . . . . . . . . . . . . . . . . . . . 48 2.5.2 The special case of F . . . . . . . . . . . . . . . . . 49 2n 2.5.3 Solving univariate polynomial equations . . . . . . . . 55 2.6 Vector spaces and linear maps . . . . . . . . . . . . . . . . . 61 2.7 The RSA and Diffie-Hellman cryptosystems . . . . . . . . . . 63 2.7.1 RSA . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63 2.7.2 Diffie-Hellman key exchange . . . . . . . . . . . . . . . 65 © 2009 by Taylor and Francis Group, LLC II Algorithms 3 Linear algebra 71 3.1 Introductory example: Multiplication of small matrices over F 71 2 3.2 Dense matrix multiplication . . . . . . . . . . . . . . . . . . 77 3.2.1 Strassen’s algorithm . . . . . . . . . . . . . . . . . . . 80 3.2.2 Asymptotically fast matrix multiplication . . . . . . . 89 3.2.3 Relation to other linear algebra problems . . . . . . . 93 3.3 Gaussian elimination algorithms . . . . . . . . . . . . . . . . 94 3.3.1 Matrix inversion . . . . . . . . . . . . . . . . . . . . . 98 3.3.2 Non-invertible matrices . . . . . . . . . . . . . . . . . 98 3.3.3 Hermite normal forms . . . . . . . . . . . . . . . . . . 103 3.4 Sparse linear algebra . . . . . . . . . . . . . . . . . . . . . . 105 3.4.1 Iterative algorithms . . . . . . . . . . . . . . . . . . . 106 3.4.2 Structured Gaussian elimination . . . . . . . . . . . . 113 4 Sieve algorithms 123 4.1 Introductory example: Eratosthenes’s sieve . . . . . . . . . . 123 4.1.1 Overview of Eratosthenes’s sieve . . . . . . . . . . . . 123 4.1.2 Improvements to Eratosthenes’s sieve . . . . . . . . . 125 4.1.3 Finding primes faster: Atkin and Bernstein’s sieve . . 133 4.2 Sieving for smooth composites . . . . . . . . . . . . . . . . . 135 4.2.1 General setting . . . . . . . . . . . . . . . . . . . . . . 136 4.2.2 Advanced sieving approaches . . . . . . . . . . . . . . 148 4.2.3 Sieving without sieving . . . . . . . . . . . . . . . . . 152 5 Brute force cryptanalysis 155 5.1 Introductory example: Dictionary attacks . . . . . . . . . . . 155 5.2 Brute force and the DES algorithm . . . . . . . . . . . . . . 157 5.2.1 The DES algorithm . . . . . . . . . . . . . . . . . . . 157 5.2.2 Brute force on DES . . . . . . . . . . . . . . . . . . . 161 5.3 Brute force as a security mechanism . . . . . . . . . . . . . . 163 5.4 Brute force steps in advanced cryptanalysis . . . . . . . . . . 164 5.4.1 Description of the SHA hash function family . . . . . . 165 5.4.2 A linear model of SHA-0 . . . . . . . . . . . . . . . . . 168 5.4.3 Adding non-linearity . . . . . . . . . . . . . . . . . . . 171 5.4.4 Searching for collision instances . . . . . . . . . . . . . 179 © 2009 by Taylor and Francis Group, LLC 5.5 Brute force and parallel computers . . . . . . . . . . . . . . . 182 6 The birthday paradox: Sorting or not? 185 6.1 Introductory example: Birthday attacks on modes of operation 186 6.1.1 Security of CBC encryption and CBC-MAC . . . . . . 186 6.2 Analysis of birthday paradox bounds . . . . . . . . . . . . . 189 6.2.1 Generalizations . . . . . . . . . . . . . . . . . . . . . . 190 6.3 Finding collisions . . . . . . . . . . . . . . . . . . . . . . . . 192 6.3.1 Sort algorithms . . . . . . . . . . . . . . . . . . . . . . 196 6.3.2 Hash tables . . . . . . . . . . . . . . . . . . . . . . . . 207 6.3.3 Binary trees . . . . . . . . . . . . . . . . . . . . . . . . 210 6.4 Application to discrete logarithms in generic groups . . . . . 216 6.4.1 Pohlig-Hellman algorithm . . . . . . . . . . . . . . . . 216 6.4.2 Baby-step, giant-step algorithm . . . . . . . . . . . . . 218 7 Birthday-based algorithms for functions 223 7.1 Algorithmic aspects . . . . . . . . . . . . . . . . . . . . . . . 224 7.1.1 Floyd’s cycle finding algorithm . . . . . . . . . . . . . 225 7.1.2 Brent’s cycle finding algorithm . . . . . . . . . . . . . 226 7.1.3 Finding the cycle’s start . . . . . . . . . . . . . . . . . 227 7.1.4 Value-dependent cycle finding . . . . . . . . . . . . . . 228 7.2 Analysis of random functions . . . . . . . . . . . . . . . . . . 231 7.2.1 Global properties . . . . . . . . . . . . . . . . . . . . . 231 7.2.2 Local properties . . . . . . . . . . . . . . . . . . . . . 232 7.2.3 Extremal properties . . . . . . . . . . . . . . . . . . . 232 7.3 Number-theoretic applications . . . . . . . . . . . . . . . . . 233 7.3.1 Pollard’s Rho factoring algorithm . . . . . . . . . . . . 233 7.3.2 Pollard’s Rho discrete logarithm algorithm . . . . . . 236 7.3.3 Pollard’s kangaroos . . . . . . . . . . . . . . . . . . . . 237 7.4 A direct cryptographic application in the context of blockwise security . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 238 7.4.1 Blockwise security of CBC encryption . . . . . . . . . 239 7.4.2 CBC encryption beyond the birthday bound . . . . . 239 7.4.3 Delayed CBC beyond the birthday bound . . . . . . . 240 7.5 Collisions in hash functions . . . . . . . . . . . . . . . . . . . 242 7.5.1 Collisions between meaningful messages . . . . . . . . 243 7.5.2 Parallelizable collision search . . . . . . . . . . . . . . 244 © 2009 by Taylor and Francis Group, LLC 7.6 Hellman’s time memory tradeoff . . . . . . . . . . . . . . . . 246 7.6.1 Simplified case . . . . . . . . . . . . . . . . . . . . . . 247 7.6.2 General case . . . . . . . . . . . . . . . . . . . . . . . 248 8 Birthday attacks through quadrisection 251 8.1 Introductory example: Subset sum problems . . . . . . . . . 251 8.1.1 Preliminaries . . . . . . . . . . . . . . . . . . . . . . . 252 8.1.2 The algorithm of Shamir and Schroeppel . . . . . . . 253 8.2 General setting for reduced memory birthday attacks . . . . 256 8.2.1 Xoring bit strings. . . . . . . . . . . . . . . . . . . . . 257 8.2.2 Generalization to different groups. . . . . . . . . . . . 258 8.2.3 Working with more lists . . . . . . . . . . . . . . . . . 262 8.3 Extensions of the technique . . . . . . . . . . . . . . . . . . . 263 8.3.1 Multiple targets . . . . . . . . . . . . . . . . . . . . . 263 8.3.2 Wagner’s extension . . . . . . . . . . . . . . . . . . . . 264 8.3.3 Related open problems . . . . . . . . . . . . . . . . . . 265 8.4 Some direct applications . . . . . . . . . . . . . . . . . . . . 267 8.4.1 Noisy Chinese remainder reconstruction . . . . . . . . 267 8.4.2 Plain RSA and plain ElGamal encryptions . . . . . . 269 8.4.3 Birthday attack on plain RSA. . . . . . . . . . . . . . 269 8.4.4 Birthday attack on plain ElGamal . . . . . . . . . . . 270 9 Fourier and Hadamard-Walsh transforms 273 9.1 Introductory example: Studying S-boxes . . . . . . . . . . . 273 9.1.1 Definitions, notations and basic algorithms . . . . . . 273 9.1.2 Fast linear characteristics using the Walsh transform . 275 9.1.3 LinkbetweenWalshtransformsanddifferentialcharac- teristics . . . . . . . . . . . . . . . . . . . . . . . . . . 279 9.1.4 Truncated differential characteristics . . . . . . . . . . 282 9.2 Algebraic normal forms of Boolean functions . . . . . . . . . 285 9.3 Goldreich-Levin theorem . . . . . . . . . . . . . . . . . . . . 286 9.4 Generalization of the Walsh transform to F . . . . . . . . . 288 p 9.4.1 Complexity analysis . . . . . . . . . . . . . . . . . . . 291 9.4.2 Generalization of the Moebius transform to F . . . . 293 p 9.5 Fast Fourier transforms . . . . . . . . . . . . . . . . . . . . . 294 9.5.1 Cooley-Tukey algorithm . . . . . . . . . . . . . . . . . 296 9.5.2 Rader’s algorithm . . . . . . . . . . . . . . . . . . . . 300 © 2009 by Taylor and Francis Group, LLC