cryptAnAlysis

© 2009 by Taylor and Francis Group, LLC

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

Chapman & Hall/CRC

CRYPTOGRAPHY AND NETWORK SECURITY

Algorithmic

cryptAnAlysis

Antoine Joux

© 2009 by Taylor and Francis Group, LLC

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

`

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 De¬ning 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 Speci¬c 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 ¬elds . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47

2.5.1 The general case . . . . . . . . . . . . . . . . . . . . . 48

2.5.2 The special case of F2n ................. 49

2.5.3 Solving univariate polynomial equations . . . . . . . . 55

2.6 Vector spaces and linear maps ................. 61

2.7 The RSA and Di¬e-Hellman cryptosystems . . . . . . . . . . 63

2.7.1 RSA . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63

2.7.2 Di¬e-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 F2 71

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 ¬nding algorithm . . . . . . . . . . . . . 225

7.1.2 Brent™s cycle ¬nding algorithm . . . . . . . . . . . . . 226

7.1.3 Finding the cycle™s start . . . . . . . . . . . . . . . . . 227

7.1.4 Value-dependent cycle ¬nding . . . . . . . . . . . . . . 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 tradeo¬ . . . . . . . . . . . . . . . . 246

7.6.1 Simpli¬ed 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 di¬erent 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 De¬nitions, notations and basic algorithms . . . . . . 273

9.1.2 Fast linear characteristics using the Walsh transform . 275

9.1.3 Link between Walsh transforms and di¬erential charac-

teristics . . . . . . . . . . . . . . . . . . . . . . . . . . 279

9.1.4 Truncated di¬erential 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 Fp ......... 288

9.4.1 Complexity analysis . . . . . . . . . . . . . . . . . . . 291

9.4.2 Generalization of the Moebius transform to Fp . . . . 293

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

9.5.3 Arbitrary ¬nite abelian groups . . . . . . . . . . . . . 303

10 Lattice reduction 309

10.1 De¬nitions ............................ 309

10.2 Introductory example: Gauss reduction . . . . . . . . . . . . 311

10.2.1 Complexity analysis . . . . . . . . . . . . . . . . . . . 315

10.3 Higher dimensions . . . . . . . . . . . . . . . . . . . . . . . . 318

10.3.1 Gram-Schmidt orthogonalization . . . . . . . . . . . . 319

10.3.2 Lenstra-Lenstra-Lov´sz algorithm

a ........... 320

10.4 Shortest vectors and improved lattice reduction ....... 327

10.4.1 Enumeration algorithms for the shortest vector . . . . 327

10.4.2 Using shortest vectors to improve lattice reduction . . 330

10.5 Dual and orthogonal lattices .................. 331

10.5.1 Dual of a lattice . . . . . . . . . . . . . . . . . . . . . 332

10.5.2 Orthogonal of a lattice . . . . . . . . . . . . . . . . . . 333

11 Polynomial systems and Gr¨bner base computations

o 337

11.1 General framework ....................... 338

11.2 Bivariate systems of equations ................. 340

11.2.1 Resultants of univariate polynomials . . . . . . . . . . 341

11.2.2 Application of resultants to bivariate systems . . . . . 343

11.3 De¬nitions: Multivariate ideals, monomial orderings and Gr¨bnero

bases . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 345

11.3.1 A simple example: Monomial ideals . . . . . . . . . . 346

11.3.2 General case: Gr¨bner bases . . . . . . . . . . . . . .

o 346

11.3.3 Computing roots with Gr¨bner bases . . . . . . . . . .

o 349

11.3.4 Homogeneous versus a¬ne algebraic systems . . . . . 351

11.4 Buchberger algorithm . . . . . . . . . . . . . . . . . . . . . . 352

11.5 Macaulay™s matrices . . . . . . . . . . . . . . . . . . . . . . . 354

11.6 Faug`re™s algorithms . . . . . . . . . . . . . . . . . . . . . . .

e 355

11.6.1 The F4 approach . . . . . . . . . . . . . . . . . . . . . 356

11.6.2 The F5 approach . . . . . . . . . . . . . . . . . . . . . 359

11.6.3 The speci¬c case of F2 . . . . . . . . . . . . . . . . . . 360

11.6.4 Choosing and changing monomial ordering for Gr¨bner o

bases . . . . . . . . . . . . . . . . . . . . . . . . . . . . 361

11.7 Algebraic attacks on multivariate cryptography . . . . . . . . 362

11.7.1 The HFE cryptosystem . . . . . . . . . . . . . . . . . 363

© 2009 by Taylor and Francis Group, LLC

11.7.2 Experimental Gr¨bner basis attack . . . . . . . . . . .

o 364

11.7.3 Theoretical explanation . . . . . . . . . . . . . . . . . 365

11.7.4 Direct sparse approach on Macaulay™s matrix . . . . . 366

11.8 On the complexity of Gr¨bner bases computation

o ...... 367

III Applications

12 Attacks on stream ciphers 373

12.1 LFSR-based keystream generators . . . . . . . . . . . . . . . 374

12.2 Correlation attacks ....................... 376

12.2.1 Noisy LFSR model . . . . . . . . . . . . . . . . . . . . 376

12.2.2 Maximum likelihood decoding . . . . . . . . . . . . . . 377

12.2.3 Fast correlation attacks . . . . . . . . . . . . . . . . . 380

12.2.4 Algorithmic aspects of fast correlation attacks . . . . . 383

12.3 Algebraic attacks ........................ 387

12.3.1 Predicting an annihilator polynomial . . . . . . . . . . 388

12.4 Extension to some non-linear shift registers . . . . . . . . . . 389

12.5 The cube attack . . . . . . . . . . . . . . . . . . . . . . . . . 390

12.5.1 Basic scenario for the cube method . . . . . . . . . . . 392

12.6 Time memory data tradeo¬s .................. 393

13 Lattice-based cryptanalysis 397

13.1 Direct attacks using lattice reduction ............. 397

13.1.1 Dependence relations with small coe¬cients . . . . . . 397

13.1.2 Some applications of short dependence relations ... 402

13.2 Coppersmith™s small roots attacks . . . . . . . . . . . . . . . 407

13.2.1 Univariate modular polynomials . . . . . . . . . . . . 407

13.2.2 Bivariate polynomials . . . . . . . . . . . . . . . . . . 410

13.2.3 Extension to rational roots . . . . . . . . . . . . . . . 413

13.2.4 Security of RSA with small decryption exponent . . . 414

14 Elliptic curves and pairings 417

14.1 Introduction to elliptic curves ................. 417

14.1.1 The group structure of elliptic curves . . . . . . . . . . 418

14.1.2 Double and add method on elliptic curves . . . . . . . 423

14.1.3 Number of points on elliptic curves . . . . . . . . . . . 423

14.2 The Weil pairing . . . . . . . . . . . . . . . . . . . . . . . . . 424

14.2.1 Weil™s reciprocity law . . . . . . . . . . . . . . . . . . 424

© 2009 by Taylor and Francis Group, LLC

14.2.2 The Weil pairing on -torsion points . . . . . . . . . . 429

14.3 The elliptic curve factoring method .............. 432

14.3.1 Pollard™s p ’ 1 factoring . . . . . . . . . . . . . . . . . 432

14.3.2 Elliptic curve factoring . . . . . . . . . . . . . . . . . . 433

15 Index calculus algorithms 439

15.1 Introduction to index calculus ................. 439

15.2 A simple ¬nite ¬eld example .................. 441

15.2.1 Overview . . . . . . . . . . . . . . . . . . . . . . . . . 441

15.2.2 A toy example . . . . . . . . . . . . . . . . . . . . . . 448

15.3 Generalization to ¬nite ¬elds with small enough characteristic 449

15.3.1 Overview of the regular function ¬eld sieve . . . . . . 453

15.4 Introduction to the number ¬eld sieve . . . . . . . . . . . . . 455

15.4.1 Factoring with the quadratic sieve . . . . . . . . . . . 456

15.4.2 Discrete logarithms with the Gaussian integer method 457

15.4.3 Constructing number ¬eld sieve polynomials . . . . . . 461

15.5 Smoothness probabilities .................... 463

15.5.1 Computing smoothness probabilities for polynomials . 463

15.5.2 Asymptotic lower bound on the smoothness probability 467

15.5.3 Smoothness probabilities for integers . . . . . . . . . . 467

References 471

Lists 491

© 2009 by Taylor and Francis Group, LLC

Preface

The idea of this book stemmed from a master™s degree course given at the

University of Versailles. Since most students in this course come from a math-

ematical background, its goal is both to prime them on algorithmic methods

and to motivate these algorithmic methods by cryptographically relevant ex-

amples. Discussing this course with colleagues, I realized that its content

could be of interest to a much larger audience. Then, at Eurocrypt 2007 in

Barcelona, I had the opportunity to speak to Sunil Nair from Taylor & Fran-

cis. This discussion encouraged me to turn my course into a book, which you

are now holding.

This book is intended to serve several purposes. First, it can be a basis for

courses, both at the undergraduate and at the graduate levels. I also hope

that it can serve as a handbook of algorithmic methods for cryptographers.

It is structured in three parts: background, algorithms and applications. The

background part contains two chapters, a short introduction to cryptography

mostly from a cryptanalytic perspective and a background chapter on ele-

mentary number theory and algebra. The algorithms part has nine chapters,

each chapter regroups algorithms dedicated to a single topic, often illustrated

by simple cryptographic applications. Its topics cover linear algebra, sieving,

brute force, algorithms based on the birthday paradox, Hadamard-Fourier-

Walsh transforms, lattice reduction and Gr¨bner bases. The applications part

o

takes a di¬erent point-of-view and uses recipes from several chapters in the

algorithms part to address more advanced cryptographic applications. This

¬nal part contains four chapters dealing with linear feedback shift register

based stream ciphers, lattice methods for cryptanalysis, elliptic curves and

index calculus methods.

All chapters in the algorithms and applications parts have an exercise sec-

tion. For all exercises whose number is marked with an “h” exponent, e.g.,

exercise 1h , hints and solutions are given on the book™s website whose ad-

dress is http://www.joux.biz/algcrypt. To allow the book to serve as a

textbook, about half of the exercises have neither hints nor solutions.

The content of this book should not necessarily be read or taught in linear

order. For a ¬rst reading or an introductory course, the content of Chapters 2,

3 and 6 covering basic number theory, linear algebra and birthday paradox al-

gorithms should su¬ce. For a longer course, the choice of chapters depends on

the background of the reader or students. With a mathematical background,

I would recommend choosing among Chapters 4, 7, 10 and 11. Indeed, these

chapters are based on mathematical premises and develop algorithms on this

basis. With a computer science background, Chapters 5, 8 and 9 are more

suited. Finally, the applications presented in the last part can be used for

dedicated graduate courses. Alternatively, they can serve as a basis for course

© 2009 by Taylor and Francis Group, LLC

end projects.

Throughout this book, we discuss many algorithms. Depending on the spe-

ci¬c aspect that needs to be emphasized, this is done using either a textual

description, an algorithm in pseudo-code or a C code program. The idea is

to use pseudo-code to emphasize high-level description of algorithms and C

code to focus on lower-level implementation details. Despite some drawbacks,

the C programming language is well suited for programming cryptanalytic

applications. One essential advantage is that it is a relatively low-level pro-

gramming language that allows to tightly control the behavior of the code

that is executed by the target processor. Of course, assembly language would

give an even tighter control. However, it would be much harder to read and

would only be usable on a single microprocessor or family of microprocessors.

Note that for lack of space, it was not possible to present here C programs

for all algorithms that are discussed in this book. Several additional codes

are available for downloading on the book™s website. All these codes were

developed and tested using the widely available Gnu GCC compiler. Note

that these codes are not optimally tuned, indeed, ¬ne tuning C code is usually

speci¬c to a single compiler version and often hurt the code™s legibility. Where

timings are given, they were measured on an Intel Core 2 Duo at 2.4 Ghz.

Writing this book was a long and challenging undertaking. It would not

have been possible without the help of many people. First, I would like to

thank my Ph.D. advisor, Jacques Stern, without his guidance, I would not

have taken the path of research and cryptography. I also wish to thank all

my colleagues and co-authors, for discussing fascinating research problems. It

was a great source of inspiration while writing this book. All my students and

former students deserve special thanks, especially for forcing me to reconsider

previous knowledge again and again. Through sheer coincidence, I happened

to be the program chair of Eurocrypt 2009 while writing this book, it was a

very nice experience and I am extremely grateful to the wonderful people who

accepted to serve on my committee. During the ¬nalization of the manuscript,

I attended a seminar on “Symmetric Cryptography” at the “Leibniz-Zentrum

f¨r Informatik” in Schloss Dagstuhl, Germany. Attending this seminar and

u

discussing with all the participants was extremely helpful at that time, I

would like to give due credit to the organizers and to the wonderful sta¬ at

Schloss Dagstuhl. A few of my colleagues helped me during proofreading,

thanks to Johannes Buchmann, Pierre-Alain Fouque, Steven Galbraith, Louis

Goubin, Reynald Lercier, Michael Quisquater, Michael Schneider and Nicolas

Sendrier, this book contains much fewer typos than it would have. Thanks

to Michel Abdalla for putting together a large bibliography of cryptography-

related articles and for letting me use it. Last but not least, I would like to

express all my gratitude to my family for supporting me all these years and

for coping with my occasional absentmindedness.

Finally, I wish to acknowledge institutional support from the D´l´gation

ee

G´n´rale pour l™Armement and the University of Versailles and Saint-Quentin-

ee

en-Yvelines.

© 2009 by Taylor and Francis Group, LLC

Existing programs or libraries

Many of the algorithms presented here have been programmed, in very ef-

¬cient ways, into existing computer packages. In many cases, reprogramming

the methods might not be needed or might even be counter-productive when

the available programs are very e¬cient.

We give here a short discussion of available programs and libraries which

contain algorithmic methods discussed in this book. This discussion does not

pretend to exhaustivity. We regroup the stand-alone tools on one side and

libraries that need to be used in conjunction with a user written program on

the other. Note that stand-alone tools usually incorporate a programming

language to allow the development of user™s applications. Some of the pro-

grams o¬er both options, a stand-alone tool and a library; we list them in the

stand-alone category. The various programs are listed in alphabetical order.

We recommend using them for benchmarking and before considering to write

user™s speci¬c code.

Stand-alone tools

• GAP This computer algebra system is developed by the GAP group, its

home page is http://www.gap-system.org/. It includes many features

and o¬ers very useful group theoretic algorithms. In particular, it is able

to manipulate group characters and group representation.

• MAGMA Magma is a computer algebra system that can be bought

online at http://magma.maths.usyd.edu.au/. An online calculator,

with limited computing power, is also available. The Magma language

is mathematically oriented and every object belongs to a rigourously

de¬ned structure. Magma includes a large number of features. In par-

ticular, it o¬ers algebraic geometry tools and knows how to compute

with elliptic curves and divisors. Magma also contains a fast implemen-

tation of F4 Gr¨bner basis algorithm and lattice reduction tools.

o

• Maple Maple computer algebra is a very well-known and versatile sys-

tem, used in a large variety of applications. The current version contains

a very e¬cient implementation of the F5 Gr¨bner basis algorithm.

o

• PARI/GP This computer algebra system was initiated by Henri Cohen

and is currently maintained by Karim Belabas under the GPL license.

It o¬ers both a stand-alone tool and a C library. In addition to classical

features such as modular computation, linear algebra, polynomials, it

o¬ers some speci¬c functionalities to compute information about general

number ¬elds and elliptic curves over the complex ¬eld. For more infor-

mation, look up the webpage at http://pari.math.u-bordeaux.fr/.

© 2009 by Taylor and Francis Group, LLC

• SAGE Sage is an open-source mathematics software system http:

//www.sagemath.org/ based on the Python language. It incorporates

many e¬cient implementations of algorithms for algebra. One speci-

¬city of Sage is that it o¬ers the option of interfacing with other com-

puter algebra systems and of incorporating functionalities from existing

libraries.

Libraries

• FFTW This library developed at MIT by Matteo Frigo and Steven G.

Johnson is dedicated to high-performance computation of Fourier trans-

forms. The home page of the library is located at http://www.fftw.

org/.

• NTL This library written by Victor Shoup and available at http:

//www.shoup.net/ntl/ is based on the C++ language. It implements

¬nite ¬elds, routines for univariate polynomials, linear algebra and sev-

eral lattice reduction algorithms.

© 2009 by Taylor and Francis Group, LLC

Part I

Background

© 2009 by Taylor and Francis Group, LLC

Chapter 1

A bird™s-eye view of modern

cryptography

Since cryptanalysis cannot exist without cryptography, this background chap-

ter aims at making a brief, necessarily incomplete survey of modern cryptog-

raphy, recalling some essential de¬nitions and facts for the perusal of this

book and laying down the notational ground. In particular, it presents vari-

ous security notions, corresponding to several classes of adversaries. Modern

cryptanalysis is the counterpart to these security notions. The fundamental

goal of a cryptanalyst is to violate one or several of these security notions for

algorithms that claim, implicitly or explicitly, to satisfy these security notions.

This can be achieved in two main ways, either by overcoming an underlying

security hypothesis or by exhibiting a speci¬c ¬‚aw in the considered algorithm

or protocol.

This chapter only intends to serve as an introduction to the topic and

certainly to give a complete description of modern cryptography. The reader

may wish to consult a reference book on cryptography. There are many such

books, a few examples are [Buc04, MvOV97, Sch96, Sti02].

1.1 Preliminaries

Cryptography is a ubiquitous tool in the world of information security. It

is required when trying to keep the secrecy of communications over open

channels or to prove the authenticity of an incoming message. It can be used

to create many multiparty protocols in a way that makes cheating di¬cult

and expensive. In fact, its range of applicability is very wide and it would

not be possible to give a complete list of functionalities that can be achieved

through the use of cryptography. Instead, we are going to focus on a small set

of fundamental goals and see how they can be formalized into precise security

notions. From an historical perspective, the oldest and foremost cryptographic

goal is con¬dentiality.

Con¬dentiality appeared quite early in human history. At that time, mes-

sengers were regularly sent between troops or traders to carry important mes-

sages. They were also regularly captured by enemies and they sometimes

3

© 2009 by Taylor and Francis Group, LLC

4 Algorithmic Cryptanalysis

turned out to be spies or traitors. In this context, the basic idea was to be

able to write messages in a way that would preserve the secrecy of the mes-

sage meaning against these events. Later, with the invention of postal services,

telegraphs, radio communications and computer networks, it became easier to

send messages and at the same time easier to intercept or copy these messages.

Thus, the basic question remains: how can we make sure that messages will

not be read by the wrong person? One option is to hide the very existence

of the message through various means, this is called steganography. We will

not consider this option any further. Another option does not try to hide

the message but simply to make sure that it cannot be understood except by

the intended recipient, using something akin to a scrambling process, called

encryption.

This notion of con¬dentiality is trickier than it may ¬rst appear. What

precisely can we hide about a message? Is it possible to be sure that nothing

can be learned about it? A ¬rst limit is that it is not possible to hide every-

thing about a given message, looking at the encrypted message, an attacker

can always learn or at least estimate the length of the message. The only

way to avoid this would be to output ciphertexts of the maximum accepted

input length for all messages. This would, of course, yield utterly impractical

cryptosystems. Moreover, the attacker may have some prior information and

seeing the message is not going to make him forget it. As a consequence, it is

convenient to assume that the length of the message is not hidden by the en-

cryption and to measure the amount of new knowledge that can be extracted

by the attacker from the message. Similarly, the attacker may obtain prior

information about the encryption system. As a consequence, to make cryp-

tography useful in a wide variety of contexts, it is necessary to assume that

the speci¬cations of the cryptosystem are public, or could be leaked to the ad-

versary. The security of the system should only rely on a short secret: the key

of the system. This essential principle was proposed by Auguste Kerckho¬s

in 1883 and published in [Ker83].

This approach and its limits were further studied by Shannon in 1945 in a

con¬dential report titled A Mathematical Theory of Cryptography. This report

was declassi¬ed after World War II and the results published in [Sha49]. In

order to study the security of cryptographic systems, this paper introduced

a new mathematical theory: information theory. In a nutshell, information

theory contained good news and bad news about cryptography. The good

news is that perfect con¬dentiality is possible and can be achieved using a

simple encryption algorithm called the One Time Pad. The bad news is that

the One Time Pad is impractical for most applications and that according

to information theory nothing more practical can be secure. Indeed, the

One Time Pad views messages as sequences of symbols (bits or characters)

and encrypts them by a simple mixing of each symbol with a corresponding

symbol extracted from the key. However, it is crucial for the security of this

scheme to use a random key of the same length as the message to encrypt.

With any shorter key, the One Time Pad degenerates into a variation of the

© 2009 by Taylor and Francis Group, LLC

A bird™s-eye view of modern cryptography 5

Vigenere cipher and becomes very weak. Of course, transmitting very long

keys securely is rarely easier than directly transmitting messages securely.

Moreover, this system is error prone and any key reuse dooms the security

of the corresponding messages. In practice, a user would expect to use a

relatively short key for the transmission of long messages. Using information

theory, Shannon showed that this not possible. Indeed, a powerful enough

cryptanalyst can always try to decrypt the transmitted message using all

possible keys. The only key that yields a meaningful message is the correct

one.

In order to bypass this impossibility result, modern cryptography takes into

account the amount of work required from the cryptanalyst and assumes that,

even for relatively short key lengths, trying all keys costs too much and is not

an option. This idea is at the core of computationally based cryptography. An

asymptotically oriented approach to this idea can be obtained by using com-

plexity theory. In this approach, easy tasks such as encryption or decryption

are modeled by polynomial time computations and hard tasks are assumed

to be in harder classes of complexity1 . This approach has an essential draw-

back, complexity classes are too coarse and they do not always ¬nely re¬‚ect

the hardness of real computation. For example, a polynomial time algorithm

of complexity n100 is usually totally impractical, while an exponential time

algorithm of complexity 2n/100 is often useful. A more concrete approach was

proposed by Bellare, Kilian and Rogaway in [BKR00] and aims at giving a

more precise information about the cost of attacks for real life parameters of

cryptographic schemes. However, even this concrete approach is not complete

and comparing the practicality and the full cost [Wie04] of attacks is a di¬cult

art.

Pushing the idea of computationally based cryptography a bit further, in

1976, Di¬e and Hellman invented public key cryptography [DH76]. The basic

idea is to use trapdoor one-way functions, i.e., functions which are easy to

compute, hard to invert and which become easy to invert once a secret value,

the trapdoor, is known.

Note that, in spite of achieving perfect con¬dentiality, the One Time Pad

is not perfectly secure. Indeed security is more than simply con¬dentiality, it

also covers the concept that an attacker should not be able to tamper with

messages without being detected. Clearly, this is not true with the One Time

Pad, since changing any bit of the ciphertext has a simple e¬ect: changing

the same bit in the corresponding plaintext. This property allows an attacker

to perform any change of his choice on the transmitted message. To prevent

this, it is necessary to invoke another cryptographic functionality: integrity.

1 Atmost, one can hope for N P -complete cryptanalysis, since guessing the correct key

su¬ces to break any cryptographic scheme.

© 2009 by Taylor and Francis Group, LLC

6 Algorithmic Cryptanalysis

1.1.1 Typical cryptographic needs

These two basic functionalities, con¬dentiality and integrity, give a ¬rst

criteria to classify cryptographic algorithms. Another essential criterion is

the distinction between secret key and public key algorithms. Secret key

algorithms use the same key, or sometimes distinct but equivalent keys, to

encrypt and decrypt, to authenticate or verify authentication. Public key

algorithms use di¬erent keys, the public key to encrypt or verify signatures,

the private key to decrypt or sign.

Using these two criteria, we obtain four classes of cryptographic systems.

1.1.1.1 Secret key encryption

Typical secret key algorithms encrypt messages using a short secret key

common to the sender and the recipient of the secret message. Typically,

secret keys of recent algorithm are often between 128 and 256 bits. Secret key

encryption algorithms are further divided into two main categories: stream

ciphers based and block ciphers based.

Stream ciphers combine a pseudo-random generator of cryptographic qual-

ity, also called a keystream generator, together with One Time Pad encryption.

Block ciphers are keyed permutations which act on blocks of bits; blocks of

128 bits are a frequent choice. In order to encrypt messages, they are combined

with a mode of operation which describes how to parse the messages into

blocks and decompose the encryption of a message into encryption of blocks.

Some of the basic mode of operations have been known for a long time and

were already standardized for use with the DES algorithm. More recently, the

NIST2 encouraged research for new modes of operation in order to propose

them as standards for use together with the AES block cipher. To illustrate

modes of operation and their importance in secret key encryption, let us de-

scribe three well-known modes (see Figure 1.1): Electronic Code Book (ECB),

Cipher Block Chaining (CBC) and Counter mode (CTR).

The ECB mode works as follows: ¬rst it pads the plaintext message P to

ensure that its length becomes a multiple of the block length, some care should

be taken to make sure that the padding can be reversed after decryption to

recover the original message. A standard solution is to add a single 1 after

the original message, followed by the number of zeros needed to ¬ll the last

message block. Note that with this padding, messages whose original length

is already an entire number of blocks are enlarged by one full block. After

padding, the ECB mode parses the padded message in n-bit blocks, where n

is the length of the cipher™s blocks. Let the i-th block be denoted by P (i) . To

encrypt P , each block P (i) is encrypted separately.

Another very common encryption mode is the Cipher Block Chaining (CBC)

mode. To add security, this encryption mode is randomized. The randomiza-

2 National Institute of Standards and Technology

© 2009 by Taylor and Francis Group, LLC

A bird™s-eye view of modern cryptography 7

P

P1 P2 P

’1

···

C

C1 C2 C

’1

(a) ECB encryption

P

P1 P2 P

’1

IV

···

C

C1 C2 C

’1

(b) CBC encryption

R+ ’2

R+1 R+

R

···

P

P1 P2 P

’1

C

C1 C2 C

’1

(c) CTR encryption

Figure 1.1: Some classical encryption modes

© 2009 by Taylor and Francis Group, LLC

8 Algorithmic Cryptanalysis

tion is added at the very beginning of the encryption process by simply adding

one block of random initial value (IV ) at the beginning of the message. There

are two options when using this initial value, it can be considered either as

an additional plaintext message block, say P (0) or as an additional ciphertext

block, then denoted by C (0) . When the IV is considered as an extra plaintext

block, the ¬rst ciphertext block is set to C (0) = Π(P (0) ) where Π denotes the

underlying block cipher or random permutation. From the ¬rst ciphertext

block, we then proceed iteratively, letting C (i) = Π(P (i) • C (i’1) ). When the

IV is considered as a ciphertext block, the ¬rst encryption is simply omit-

ted. An important fact about CBC encryption is that the encryption of any

block of plaintext is a function not only of the block value, but also of all the

previous blocks and of the IV .

As modes of encryption go, we also consider the Counter (CTR) mode. In

this mode, the block cipher is used to generate a pseudo-random sequence

which is then used similarly to a one-time pad in order to encrypt the plain-

text message. Thus, CTR mode is a simple way to make a stream cipher

algorithm out of a block cipher. More precisely, the CTR mode is given as

input a starting counter value. The ¬rst block of pseudo-random material

is obtained by encrypting this input value. Then the value is incremented

in order to obtain the next block of pseudo-randomness, incremented again

for the following one and so on. . . Depending on the precise implementation

choice, the incrementation can be done in several di¬erent ways. On a general

purpose processor, the most e¬cient method is to increment by arithmetically

adding 1 to the counter value, modulo 2b , where b is the block size in bits.

In hardware, either on ASICs or FPGAs, it is faster to consider the counter

as the state of a linear feedback shift register (see Chapter 2) and to incre-

ment it by advancing the linear feedback shift register by one step. Thus,

the exact speci¬cations of the CTR mode may vary depending on the target

architecture.

1.1.1.2 Secret key authentication

In [Sim82, Sim85, Sim86], Simmons developed a theory for perfect authen-

tication systems, which can be seen as an equivalent of Shannon™s perfect

encryption. The secret key authentication algorithms used in practice are

known as Message Authentication Codes (MACs). There are two main cate-

gories of MACs, MAC based on a block cipher and MAC based on a universal

hash function. To construct a MAC based on a block cipher, it su¬ces to

devise a speci¬c mode of operation. MAC based on universal hash functions

work on a very di¬erent principle; they were initially proposed by Wegman

and Carter in [WC81]. The idea is to compute the universal hash of the

message to authenticate and then to encrypt this value. This method yields

very fast MAC algorithms. Indeed, there exist some very fast universal hash-

ing algorithms that only cost a few processor operations per message block,

see [NP99].

© 2009 by Taylor and Francis Group, LLC

A bird™s-eye view of modern cryptography 9

To illustrate MACs based on a block cipher, let us consider the CBC en-

cryption mode once more. Another interesting feature of this mode is that a

very simlar variation can be used as a Message Authentication Code (MAC).

In this alternative mode called CBC-MAC, we very closely follow the CBC

encryption process with a couple of simple changes. The ¬rst change is that

CBC-MAC does not need an IV . Moreover, adding an IV would make CBC-

MAC insecure if the IV is processed as a ciphertext block. The second change

is that in CBC-MAC, we do not output any intermediate block encryption

but only the value of the last block. The third and ¬nal change concerns the

output of the ¬nal block. If this block is directly given as MAC value, then the

resulting authentication mode is only secure for messages of ¬xed length. In

practice, it is usually required to have the ability to process messages of arbi-

trary length. In that case, the last encrypted block should be post-processed

before being used as a MAC. The most common post-processing simply reen-

crypts this value with the block cipher keyed with another independent key.

1.1.1.3 Public key encryption

Public key encryption algorithms mostly rely on number theoretic hard

problems. One approach to public key encryption, ¬rst proposed in [DH76],

is to directly rely on a trapdoor one-way permutation. In that case, the

one-way permutation is made public and used for encryption. The trapdoor

is kept private and used for decryption. The typical example is the famous

cryptosystem of Rivest, Shamir and Adleman (RSA). Another approach is

the key exchange algorithm of Di¬e and Hellman, also introduced in [DH76],

which does not encrypt messages but lets two users agree on a common secret

key. Once a common secret key has been agreed upon, the users can en-

crypt messages using a secret key algorithm. As a consequence, key exchange

algorithms su¬ce to o¬er the public key encryption functionality.

Moreover, note that for performance reasons, even trapdoor one-way per-

mutations are rarely used to directly encrypt messages or message blocks. It

is more practical to build a hybrid cryptosystem that encrypts a random key

with the trapdoor one-way permutation and encrypts the message using a

secret key encryption scheme.

In addition, when using the RSA public key cryptosystem, special care

should be taken not to simply encrypt small keys. Indeed, such a direct

approach opens the way to multiplicative attacks. This is further developed

in Chapter 8.

1.1.1.4 Public key signature

The most frequently encountered public key signatures algorithms are coun-

terparts of the public key encryption algorithms stated above. The RSA sig-

nature algorithm follows the approach proposed in [DH76] and inverses the

one-way permutation, thanks to the trapdoor in order to sign. Veri¬cation

is achieved by computing the one-way permutation in the forward direction.

© 2009 by Taylor and Francis Group, LLC

10 Algorithmic Cryptanalysis

Note that in the case of RSA, this approach needs to be applied with care

in order to avoid multiplicative attacks. Before going through the inverse

one-way permutation, the information to be signed needs to be carefully pre-

pared using a padding algorithm. Typical approaches are the full domain hash

(FDH) and the probabilistic signature scheme (PSS) described in [BR96].

The Di¬e-Hellman key exchange algorithm also has corresponding signa-

ture algorithms. These algorithms are based on a modi¬ed zero-knowledge

proof of knowledge of a discrete logarithm. The algorithm of Schnorr [Sch91]

and the NIST standard Digital Signature Algorithm are two examples. Zero-

knowledge proofs of knowledge are not further discussed in this book.

This idea of using modi¬ed zero-knowledge proofs to build a signature

scheme can be applied with a very large variety of hard computational prob-

lems. It was introduced by Fiat and Shamir in [FS87]. Using this approach

signature algorithms have been based on many hard computational problems.

For the same reason that public encryption is rarely used to directly en-

crypt messages, public key signature schemes are rarely3 applied directly to

messages. Instead, the message to be signed is ¬rst transformed using a cryp-

tographic hash function. Here, the goal of the hash function is to produce a

short unique identi¬er for the message. In order to yield such an identi¬er,

the hash function should be constructed in a way that prevents a cryptanalyst

to e¬ciently build two messages hashing to the same value. In other words,

the hash function should be collision resistant.

1.2 De¬ning security in cryptography

In the framework of computationally based cryptography, an important

task is to de¬ne what kinds of actions can be considered as attacks. Clearly,

recovering the key from one or several encrypted messages is an attack. How-

ever, some tasks may be easier and remain useful for an adversary. Along

the years, a complex classi¬cation of attacks appeared. This classi¬cation

describes attacks by the type of information they require: there are cipher-

text only attacks, known plaintext attacks, chosen plaintext attacks and even

chosen ciphertext attacks. Also, by the amount of e¬ort the adversary uses to

intercept messages or temper with the cryptosystem: this yields the notions of

passive, lunchtime and active attacks. Finally, by the type of information that

the attack outputs: there are key recovery attacks, message recovery attacks

and distinguishers. A key recovery allows the adversary to compute the key

or some equivalent information which can afterwards be used to decrypt any

3 One notable exception to this general rule is signature with message recovery, which embeds

a (short) message within the signature, thus avoiding separate transmission.

© 2009 by Taylor and Francis Group, LLC

A bird™s-eye view of modern cryptography 11

message. A message recovery attack aims at deciphering a single message.

The goal of a distinguisher is to learn a small amount of information about

the encryption process.

Modern cryptographers have learned that, as illustrated by many historical

examples [Kah67], where cryptography is concerned it is preferable to err on

the side of caution. Indeed, the state-of-the-art of attacks against a given cryp-

tographic scheme can only move forward yielding better and better attacks.

Often, when faced with an incomplete attack which could easily be dismissed

as practically irrelevant, cryptographers prefer to consider it as an advanced

warning signal that indicates that further attacks may be forthcoming. As

a consequence of this cautiousness, a very strong de¬nition of con¬dentiality

is used in cryptography. When a cryptographic scheme fails to achieve this

de¬nition, it calls for a reaction. In the early stages, the best reaction is to

patch or dump the system, depending on the exact nature of the attack. After

the system has been widely deployed, unless it is utterly broken and calls for

immediate replacement, the best reaction is to start preparing a replacement

and a phase-out strategy.

Another reason for choosing a strong de¬nition of con¬dentiality is that it

facilitates the work of cryptanalysts. Indeed, it takes much less work to simply

point out an intrinsic weakness of a cryptographic scheme with a so-called

certi¬cation attack than to turn this weakness into a full-¬‚edged key recovery

attack. As a consequence, when several algorithms need to be compared, it

is very useful to use certi¬cation attacks as criteria to prune out the least

plausible candidates. For example, this approach was followed by NIST for

the selection of the AES encryption standard.

1.2.1 Distinguishers

The strongest de¬nitions of con¬dentiality which are currently available rely

on the notion of distinguishers. Depending on the exact characteristics of the

system being considered, the precise de¬nition of distinguishers possibly needs

to be adapted. However, the basic style of the de¬nitions is always preserved.

All distinguishers share some basic properties:

• A distinguisher, also called a distinguishing adversary, is a computa-

tional process, often modeled by a Turing machine.

• A distinguisher A interacts in a black box manner with an environ-

ment E that encapsulates the cryptographic scheme under attack and

in particular chooses random keys for this cryptographic scheme.

• The behavior of the environment depends on the value of a control bit

c, chosen uniformly at random upon the ¬rst call to the environment.

• The adversary outputs a single bit, 0 or 1, and the goal of the adversary

is to determine the value of c with a probability of success greater than

1/2, i.e., to achieve a better success rate than by blindly guessing c.

© 2009 by Taylor and Francis Group, LLC

12 Algorithmic Cryptanalysis

• The advantage of the adversary adv(A) is de¬ned as:

adv(A) = |2 Pr(A outputs c) ’ 1|. (1.1)

These basic properties already call for some comments. A ¬rst remark

concerns the presence of an absolute value in the de¬nition of the advantage.

This is useful because it ensures that the advantage is always non-negative.

Moreover, it makes sense because when 2Pr(A outputs c) ’ 1 < 0, we can

construct a new adversary A by reversing the output of A. This adversary

succeeds when A fails and vice versa. As a consequence:

2 Pr(A outputs c) ’ 1 = 1 ’ 2 Pr(A outputs c) > 0. (1.2)

Another important remark is that:

adv(A) = |Pr(A outputs 0 | c = 0) ’ Pr(A outputs 0 | c = 1)|. (1.3)

In this equation, the notation Pr(|) denotes a conditional probability, condi-

tioned by the event written at the right of |. It is a simple consequence of the

two following facts:

Pr(A outputs c) = Pr(A outputs 0 | c = 0)/2 + Pr(A outputs 1 | c = 1)/2,

1 = Pr(A outputs 0 | c = 1) + Pr(A outputs 1 | c = 1). (1.4)

Also, when using distinguishers, we should remember that in addition to the

trivial adversary that simply guesses c, we can devise a generic adversary that

models exhaustive key search. This adversary simply guesses the key material

that has been chosen by the environment for the underlying cryptographic

scheme. Using this key, it tries to determine whether c equal 0 or 1. If the

key is correct, this is usually easy. Note, however, that the details depend on

the exact ¬‚avor of distinguisher we are considering. Moreover, it is also easy

to determine that the guessed key is incorrect. In that case, the adversary

reverses to the trivial strategy of guessing c. This key guessing adversary

obtains an advantage of the order of 2’k , where k is the bit length of the key.

This shows that in the de¬nition of con¬dentiality we should not consider

adversaries with an exponentially small advantage. Two di¬erent kinds of

advantages are usually considered: advantages above a constant larger than

1/2, such as 2/3 for example, and advantages exponentially close to one, such

as 1 ’ 2’k . In fact, these two kinds of advantages yield the same security

notion and an adversary with a constant advantage can be converted into an

adversary with advantage exponentially close to one by repeating it enough

times using di¬erent random coins.

Distinguishing attacks against ECB encryption

To illustrate distinguishing attacks, let us consider distinguishers against

the ECB. These attacks rely on the fact that encryption with a block cipher

© 2009 by Taylor and Francis Group, LLC

A bird™s-eye view of modern cryptography 13

cannot hide equalities between blocks. As a consequence, an adversary can

often gain some information about the encrypted messages. A very classical

example of this weakness consists in encrypting a bitmap picture in ECB

mode and remarking that the general shape of the picture remains visible.

In particular, large zones of uniform color remain uniform. To formalize this

weakness into a distinguishing attack, let us consider an adversary that does

not query the encryption mode and directly proposes two messages M0 and

M1 consisting of 2 blocks each after padding. M0 is chosen to ensure that

its two blocks are equal, and M1 to ensure that they are di¬erent. When

the adversary is given back the encryption of one message, he simply checks

whether the two ciphertext blocks are equal. In case of equality, he announces

that M0 was encrypted and otherwise that M1 was. The adversary succeeds

with probability 1 and, thus, has advantage 1. Since the total number of

blocks involved in the attack is very small, this shows that ECB encryption

is generically insecure.

ECB encryption can also be shown insecure by using a di¬erent chosen

message attack. In this attack, the adversary ¬rst queries the encryption

mode for the encryption of any message of his choice M . Then, he sends two

messages M0 and M1 , where M0 is equal to M and M1 is any other message

of the same length. When he receives the encryption of one among M0 and

M1 , he compares this encryption to the encryption of M he already had. If

both are equal, he announces that M0 was encrypted and otherwise that it

was M1 . This attack also succeeds with probability one. The main interest

of this second attack is that it can be generalized to any deterministic mode.

To thwart this attack, it is important to make sure that encrypting twice the

same message does not usually output twice the same ciphertext. This can be

achieved by adding randomness to the message during the encryption process.

A typical way of adding randomness is the use of an IV as in CBC encryption.

This simple randomization prevents the above attacks against the ECB mode

to work against CBC encryption.

1.2.1.1 Allowed queries for distinguishers

In cryptography, two di¬erent types of distinguishers are alternatively en-

countered, chosen plaintext adversaries (CPA) and chosen ciphertext adver-

saries (CCA). These distinguishers di¬er by the type of queries they are al-

lowed to perform. Chosen plaintext adversary can query an encryption oracle

and obtain encryptions of arbitrary messages they construct. In addition,

chosen ciphertext adversaries can also ask for decryption of arbitrary strings

they construct. After considering chosen ciphertext adversaries, designers of

cryptographic systems have introduced the idea of authenticating correctly

constructed ciphertexts, this allows their systems to answer invalid when

asked to decrypt arbitrary strings. This is a key idea to design CCA-secure

cryptographic schemes.

© 2009 by Taylor and Francis Group, LLC

14 Algorithmic Cryptanalysis

1.2.1.2 Three ¬‚avors of distinguishers

We now informally describe three frequent ¬‚avors of distinguishers.

1.2.1.2.1 Find then guess distinguishers The simplest ¬‚avor of distin-

guishers is called “¬nd-then-guess” or FTG distinguishers. After initialisation

of the environment, the distinguishing adversary interacts with the environ-

ment in three consecutive phases.

1. The adversary sends messages of his choice to the environment and

receives the corresponding ciphertexts, encrypted by the cryptographic

scheme using the key chosen during initialization. This phase behaves

independently of the bit c chosen by the environment. It is also possible

to allow the adversary to ask for decryption of arbitrary ciphertexts of

his choice when considering chosen ciphertext attacks. Each message can

be chosen interactively after receiving the encryption for the previous

message.

2. The adversary produces two test messages M0 and M1 of the same

length. It sends the messages to the environment and receives a cipher-

text C corresponding to an encryption of Mc .

3. The adversary may once again ask for encryption and/or decryption

of messages of his choice, with a single, essential, exception: it is not

allowed to ask for the decryption of the message C itself. Note that for

chosen ciphertext attacks, requesting the decryption of messages derived

from C is acceptable, as long as they di¬er from C. Typically, truncated,

padded or slightly di¬erent copies of C are allowed in that case.

After the three phases, the adversary outputs his guess for c.

1.2.1.2.2 Left or right distinguishers A (polynomially) more powerful

¬‚avor of distinguishers than FTG distinguishers are “left-or-right” or LOR

distinguishers. It consists of a single phase, where the adversary sends pairs

of messages (M0 , M1 ) of the same length and receives the encryption of Mc .

Pairs of messages are chosen interactively after receiving previous encryption.

In the case of chosen ciphertext attacks, the adversary may also send pairs of

ciphertexts (C0 , C1 ) and learn the decryption of Cc . To avoid trivial attacks,

redundant queries are forbidden, i.e., an adversary is not allowed to request

the decryption of a ciphertext returned by a previous query as part of a pair

of ciphertexts.

At the end of the interaction the adversary produces a guess for c, i.e.,

tries to determine whether the left-hand side or the right-hand side of queries

was processed by the environment. This explains the name of “left-or-right”

distinguishers.

To show that LOR adversaries are more powerful than FTG adversaries, it

su¬ces to prove that any FTG adversary can be transformed into an LOR

© 2009 by Taylor and Francis Group, LLC

A bird™s-eye view of modern cryptography 15

adversary which is as powerful. The proof is very simple, it su¬ces to em-

bed the FTG adversary in a LOR-wrapper which runs it in a black box way.

In the ¬rst and ¬nal phase, when the FTG adversary requests an encryp-

tion of M , the wrapper forwards the pair (M, M ) to the environment and

returns the answer. In the middle phase, the FTG adversary produces a pair

of messages (M0 , M1 ). The wrapper simply forwards this pair and the en-

vironment™s answer. At the end, the wrapper copies the output of the FTG

adversary. Clearly, the wrapper in the LOR context is as successful as the

original adversary in the FTG context. Moreover, the number and length of

queries and the running times are essentially identical.

1.2.1.2.3 Real or random distinguishers The FTG and LOR distin-

guishers both test the ability of an adversary to extract information from ci-

phertexts when a very small amount of information remains unknown. “Real-

or-Random” or ROR distinguishers are based on a di¬erent paradigm and try

to distinguish between real encrypted messages and purely random encrypted

messages. As usual, during initialization, the environment chooses a random

bit c and random keys for its embedded cryptographic scheme. During in-

teraction, the adversary sends messages of his choice to the environment. If

c = 0, the environment is in real mode and returns the encryption of each

message it receives. If c = 1, the environment is in random mode, in that

case, it returns the encryption of a uniformly distributed random string of the

same length.

In fact, it was shown in [BDJR97] that ROR security is equivalent to LOR

security. In [RBBK01], a variation of the ROR security is proposed, it is

called indistinguishability from random strings and often denoted by IND$.

In this variation, depending on the value of its inner bit, the environment

either returns the encryption of the message it received or a purely random

string of the same length as the encrypted message.

This style of distinguisher is very useful for some security proofs, because

there are more tools for showing that a string is indistinguishable from a

random string than for addressing environment with two sides, where each

side has its own speci¬c description. However, IND$ security is stronger than

LOR security or, equivalently, than ROR security.

Indeed, assuming that LOR secure cryptosystems exist, it is possible to

construct examples of schemes which are LOR secure but not IND$ secure.

The basic idea is very simple. Starting from any LOR secure encryption

scheme S, we construct a new scheme S , which encrypts a message M under

key k as 0 Sk (M ), i.e., it simply prepends a 0 to the encryption of M using S.

It is clear that the LOR security of S is the same as the LOR security of S.

However, S is not IND$ secure because any output of the ROR environment

that starts with 1 is necessarily coming from the random mode. This example

shows that requiring IND$ security is in some sense too much.

© 2009 by Taylor and Francis Group, LLC

16 Algorithmic Cryptanalysis

1.2.2 Integrity and signatures

In modern times, cryptography deals with more than con¬dentiality. It is

also used to protect messages or ¬les against tempering. This protection can

be based either on secret key or on public key algorithms. In secret key cryp-

tography, we saw that this protection is o¬ered by message authentication

codes. With public key cryptography, the protection is based on a stronger

mechanism called signature. The essential di¬erence between MACs and sig-

natures is that message authentication codes protect their users against at-

tacks by third parties but o¬er no protection against dishonest insiders, while

signatures o¬er this additional protection. This di¬erence is re¬‚ected when

de¬ning the security notions for integrity. Integrity mechanisms of both types

rely on two algorithms. The ¬rst algorithm takes as input a message and

outputs an authentication tag. It also uses some key material, either the

common key in the secret key framework or the private key of the signer in

the public key framework. The second algorithm takes as input a message

and an authentication tag and returns either valid or invalid. It uses either

the common secret key or the public key of the signer. In both frameworks,

the goal of an attacker is to construct a forgery, i.e., a valid authentication

on a message, without knowledge of the secret or private keys. As with con¬-

dentiality, the attacker is also allowed to ¬rst make queries, more precisely, he

can obtain authentication tags for any message of his choice. For the security

notion to make sense, the produced forgery should not simply be a copy of

one of these tags but should be new. This can be made precise in two di¬erent

ways. One option is to ask the attacker to output a valid authentication tag

for a new message, which has not been given during the queries. The alter-

native is to also allow additional tags for messages which have already been

authenticated, as long as the forged tag has never been produced as answer to

a query on this message. For example, in this alternative, if a tag σ has been

produced for M and a tag σ for M (with σ = σ and M = M ), assuming

that σ is also a valid authentication tag for M , it counts as a valid forgery,

despite the fact that M was already authenticated and that σ was already

produced, because the pair (M, σ ) is new.

To measure the e¬ciency of an attacker in the case of forgeries, we de¬ne

its advantage as the probability that its output (M, σ) is a valid forgery. Note

that, here, there is no need to subtract 1/2 because the output no longer

consists of a single bit and is thus much harder to guess. For example, guessing

a valid authentication tag on t-bits at random succeeds with low probability

1/2t . A forgery attack is considered successful when its complexity is low

enough and when its probability of success is non-negligible, for example larger

than a ¬xed constant > 0.

© 2009 by Taylor and Francis Group, LLC

A bird™s-eye view of modern cryptography 17

1.2.3 Authenticated encryption

After seeing the de¬nitions of con¬dentiality and integrity/signatures, a

natural question is to consider authenticated encryption. Is it possible to

construct cryptographic systems that meet both the requirements of con¬den-

tiality and integrity/signature? In particular, is there a generic approach to

compose secure cryptographic methods that individually ensure con¬dential-

ity and integrity/signature and construct a new cryptosystem which ensures

both?

In the context of authenticated encryption, it is interesting to consider some

natural methods to compose an encryption scheme and an authentication

scheme and see why these methods are not generically secure. We start in

the context of secret key cryptography, i.e., with secret key encryption and

MACs. We discuss the case of public key primitives afterwards.

1.2.3.1 Authenticated encryption in the secret key setting

The goal of authenticated encryption is to perform encryption and au-

thentication of messages, while guaranteeing the security of both primitives

simultaneously. This can be done by composing two preexisting crypto-

graphic primitives or by devising a new speci¬c algorithm (for some examples,

see [Jut01, KVW04, Luc05, RBBK01]). The generic composition approach,

i.e., for arbitrary preexisting primitives, was studied in detail by Bellare and

Namprempre in [BN00] and raises some deep questions about the relations

between con¬dentiality and integrity.

1.2.3.1.1 Encrypt and MAC Given a secret key encryption scheme and

a MAC, the ¬rst idea that comes to mind in order to encrypt and protect the

integrity of a message M at the same time is simply to concatenate an encryp-

tion of M and a MAC of M . The reason that makes this simple idea insecure

is that a MAC algorithm does not necessarily hide the complete content of

the message. For example, if we are given a secure MAC algorithm, we can

easily construct another secure MAC based on it in a way that completely

destroys con¬dentiality. It su¬ces to form an extended MAC by concatenat-

ing the original one with the ¬rst few bits of the message. The reader may

check that this yields another secure MAC and that it cannot preserve con-

¬dentiality. Moreover, MAC algorithms are usually deterministic algorithms

that compute a short tag from the input message and verify the correctness of

the received tag by recomputing it and comparing values. With determinis-

tic MAC algorithms, the simple concatenation construction always fails to be

secure. Indeed, it is clear that the following adversary is always a successful

¬nd-the-guess distinguisher:

• The adversary asks for authenticated encryption of random messages

of the same length until two messages with a di¬erent MAC are found.

Let M0 and M1 be these two messages and (C0 , m0 ) and (C1 , m1 ) be

© 2009 by Taylor and Francis Group, LLC

18 Algorithmic Cryptanalysis

the corresponding authenticated encryptions. In these encryptions, Ci

is the regular ciphertext and mi the MAC tag. We have m1 = m2 with

high probability.

• The adversary sends (M0 , M1 ) to the environment and receives an en-

crypted message (Cc , mc ). Since the encryption algorithm is secure, Cc

does not permit to distinguish which message is encrypted. However,

since the MAC algorithm is deterministic, the MAC tag mc is either m0

or m1 . If mc = m0 , the adversary announces that M0 is the encrypted

message. If mc = m1 , it announces M1 . Clearly, this guess is always

correct.

1.2.3.1.2 MAC then Encrypt The reason why the previous approach

fails is that MACs are not intended to protect the con¬dentiality of messages.

To avoid this issue, one possible approach is the MAC then Encrypt paradigm

where we concatenate the MAC tag m to the message M and encrypt (M m)

into a ciphertext C. This clearly prevents the MAC tag from leaking informa-

tion about the encrypted message. However, this composition is not secure

either. To understand why, given a secure encryption scheme Enc, we can

construct a new encryption scheme Enc that encrypts M into (Enc(M ) 1),

simply adding an additional bit after the message encrypted by Enc. The

corresponding decryption Dec strips the last bit, without checking its value,

and applies the regular decryption Dec.

When Enc is used together with any MAC scheme in a MAC then encrypt

construction, the resulting scheme does not ensure authenticity. Indeed, an

adversary can forge a valid encryption message in the following way:

• Send an arbitrary message M and obtain a ciphertext C = Enc (M m).

• Replace the ¬nal bit of C by a zero, thus forming a message C .

• Give C as forgery.

Clearly, Dec decrypts C into (M m) since the last bit is discarded anyway.

As a consequence, the MAC tag is accepted as valid. Thus, C is a legitimate

forgery.

It is important to remark that the above attack is quite arti¬cial. However,

other reasons why this order of composition is not generically secure are dis-

cussed in [Kra01]. Another interesting property shown in this paper is that in

the context of secure channels, the MAC then Encrypt composition is secure

for some speci¬c encryption algorithms, including CBC encryption.

1.2.3.1.3 Encrypt then MAC After MAC then Encrypt, we can try the

other direction of composition, ¬rst encrypt the message M into a ciphertext

C, then compute a MAC m of the ciphertext. Bellare and Namprempre

showed in [BN00] that the Encrypt then MAC approach allows to construct a

© 2009 by Taylor and Francis Group, LLC

A bird™s-eye view of modern cryptography 19

secure authenticated encryption given any secure encryption and any secure

MAC, under the condition that independent keys are used for the two schemes.

To sketch the proof, let us start with integrity. We claim that an adversary

cannot form a new valid ciphertext by himself, unless he forges a valid MAC

for some string (the corresponding unauthenticated ciphertext). Concerning

con¬dentiality, it is clear that the MAC cannot help. Otherwise, it would

be possible to attack the con¬dentiality of the encryption scheme simply by

adding a MAC tag to it. Since this operation could easily be performed by

an adversary, we see that the Encrypt then MAC composition is also secure

from the con¬dentiality point-of-view.

1.2.3.2 Authenticated encryption in the public key setting

In the public key setting, the adversary is granted more power, since he has

access to the public keys and can encrypt and verify signatures by himself.

Thus, any generic composition insecure in the secret key setting is also insecure

in the public key setting. However, additional attacks exist in the public key

setting. We now explain why neither “Encrypt then Sign” nor “Sign then

Encrypt” are secure and discuss secure methods.

1.2.3.2.1 Sign then Encrypt Of course, the Sign then Encrypt composi-

tion inherits the weakness of MAC then Encrypt. However, other weaknesses

appear in the public key setting. In particular, the Sign then Encrypt com-

position su¬ers from a forwarding attack. Indeed, the legitimate recipient of

a message can after decryption decide to reencrypt the same message for a

third party, whose public key is known to him. For the third party, since

the signature is valid, the message seems to come from the initial sender and

the forwarding leaves no tracks. It is easy to come with contexts where this

forwarding attack can be considered an attack. Anyway, it is clearly an un-

desirable property for a secure cryptographic scheme.

1.2.3.2.2 Encrypt then Sign The Encrypt then Sign composition fails

to be secure for another reason. Indeed, this composition is subject to a cipher-

text stealing attack. The ciphertext stealing works as follows: the attacker

intercepts a message from a sender to a receiver and prevents this message

from reaching the receiver. After interception, the attacker strips the signa-

ture from the original encrypted message and replaces it by his own signature.

After that, he resends the modi¬ed message to its intended recipient. Since

the signature is valid and since the message can be correctly decrypted, the

recipient logically assumes that this is a legitimate message from the attacker.

Depending on the application, this ciphertext stealing attack can be used

to break con¬dentiality or for other malicious purposes. A breach of con¬-

dentiality may occur when the recipient answers the message, especially if he

quotes it. In a di¬erent context, if the recipient is a timestamping or regis-

© 2009 by Taylor and Francis Group, LLC

20 Algorithmic Cryptanalysis

tering authority, the attacker could falsely claim ownership of the encrypted

information that the original sender wanted to register.

Since Encrypt then Sign is a straightforward adaptation of Encrypt then

MAC to the public key context, it is interesting to precisely identify the reason

that prevents this attack from applying in the secret key context. Trying to

apply the attack in the secret key setting, we see that nothing prevents the

attacker from removing the original MAC tag or from adding a new one. This

new MAC tag passes the veri¬cation on the recipient tag. Moreover, the

encrypted message could be correctly decrypted with the secret key shared by

the original sender and the recipient. In truth, the attack fails because of the

natural hypothesis that, in the secret key setting, each secret key belongs to

a pair of users and is not shared by anyone else. Under this hypothesis, it is

highly unlikely that the recipient accepts to verify the MAC tag using a key

shared with a user and then to decrypt using a key shared with another user.

1.2.3.2.3 Signcryption In the public key setting, in order to avoid the

above attacks, it is essential to precisely de¬ne the expected security properties

and to carefully check that they are satis¬ed. The name signcryption for

such cryptographic schemes was proposed in [Zhe97]. A formal treatment of

signcryption was ¬rst given in [ADR02].

To avoid the above weaknesses of the encrypt then sign and sign then en-

crypt composition, other methods have often been proposed for applications.

A ¬rst idea is to bind the signature and encryption together by adding ¬elds,

for example at the beginning of the message, explicitly identifying the two

participants of the exchange, sender and recipient. With this additional pre-

caution, both sign-then-encrypt and encrypt-then-sign resist the above at-

tacks. A slight variation of this idea which adds the identities of the sender

and recipient in various places is proven secure in [ADR02]. The drawback

of this solution is that it needs to mix up routing information together with

the message itself. This is often judged to be unsatisfactory by application

developers who prefer to manage the message at the application layer and the

routing information at a lower layer. It is also inconvenient if the users desire

to archive a signed copy of the message after stripping it from the routing

information.

Another option relies on triple wrapping. Two ¬‚avors are possible: sign-

encrypt-sign and encrypt-sign-encrypt. They are resistant to ciphertext steal-

ing and forwarding. Note that sign-encrypt-sign is usually preferred, since it

allows the recipient to archive a signed copy of the original message. With

the triple wrapping method, the sender performs three cryptographic opera-

tions in sequence on the message, encrypting with the recipient public key and