. 1
( 18)



>>

Algorithmic
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

. 1
( 18)



>>