You are here

Algorithmic Cryptanalysis

Antoine Joux
Publisher: 
Chapman & Hall/CRC
Publication Date: 
2009
Number of Pages: 
501
Format: 
Hardcover
Series: 
Chapman & Hall/CRC Cryptography and Network Security
Price: 
89.95
ISBN: 
9781420070026
Category: 
Monograph
[Reviewed by
Tom Schulte
, on
04/29/2010
]

This is a work suitable for first-year graduate students or advanced undergraduates. Obviously designed as a textbook, the addition of the online materials makes this book usable by independent readers or industry algorithm implementers in need of a reference work.

Focused on the implementation of algorithms, Algorithmic Cryptanalysis is a work in three parts. A preliminary section gives a brief, historical introduction to cryptography along with relevant topics from elementary number theory and algebra. The meat of the book is the central portion, on algorithms, including examples in pseudocode or C. Concluding the work is a part detailing cryptographic applications. Each chapter ends with exercises, usually about ten of them. Roughly a third of these have hints or solutions residing at the text’s web site. This site also has the C programs available for download and various auxiliary materials.

The first part, entitled “Background,” includes elementary number theory with a focus on the finite fields relevant to cryptography: modular arithmetic, primality tests, univariate polynomials, vector spaces, and linear maps. The RSA and Diffie-Hellman cryptosystems are analyzed in this portion.

The strength of the algorithm part is the rich bevy of algorithms presented in the coherent context of teaching cryptography as a science. I would wager that the pseudocode, the more prevalent form for algorithms in this book, is enough for the C programmer to get going. I wish the author, when going as far as far to show the syntax-specific programs for the Walsh transform or even Eratosthenes’s sieve, had picked a more widely used, higher-level language, such as Java or C#. If not wanting to commit to one of those divisive camps, even MATLAB would be nice. In the book’s defense, it may be more natural to show the effects of more current computer architecture, such as L1 and L2 cache usage in line sieving, when using a more low-level language such as C.

Entitled “Applications,” the final part of the book offers details on stream cipher attacks, lattice-based cryptanalysis, elliptic curves, and applications of index calculus. These chapters employ the work’s key elements: recognition of the impact of computer architecture such as LFSR-based keystream generators, the explanation of relevant theory such as the group structure of elliptic curves, and explicitly practical algorithms such as the pseudocode on computing the number of smooth polynomials presented in the index calculus chapter. The index calculus chapter features a very illustrative and complete toy example on computing discrete logs in F101.

Combining practical algorithms and supported by explanation of the relevant theory, this is a good introduction to cryptanalysis that improves on that good recipe by including key details on current computer architecture. This makes this work succeed as both handbook and textbook.


Tom Schulte is a lead systems engineer at Plex Systems in Michigan with a focus on application security.

BACKGROUND

A Bird’s-Eye View of Modern Cryptography

Preliminaries

Defining security in cryptography

Elementary Number Theory and Algebra Background

Integers and rational numbers

Greatest common divisors in Z

Modular arithmetic

Univariate polynomials and rational fractions

Finite fields

Vectors spaces and linear maps

The RSA and Diffie–Hellman cryptosystems

ALGORITHMS

Linear Algebra

Introductory example: multiplication of small matrices over F2

Dense matrix multiplication

Gaussian elimination algorithms

Sparse linear algebra

Sieve Algorithms

Introductory example: Eratosthenes’s sieve

Sieving for smooth composites

Brute Force Cryptanalysis

Introductory example: dictionary attacks

Brute force and the DES algorithm

Brute force as a security mechanism

Brute force steps in advanced cryptanalysis

Brute force and parallel computers

The Birthday Paradox: Sorting or Not?

Introductory example: birthday attacks on modes of operation

Analysis of birthday paradox bounds

Finding collisions

Application to discrete logarithms in generic groups

Birthday-Based Algorithms for Functions

Algorithmic aspects

Analysis of random functions

Number theoretic applications

A direct cryptographic application in the context of blockwise security

Collisions in hash functions

Hellman’s time memory tradeoff

Birthday Attacks through Quadrisection

Introductory example: subset sum problems

General setting for reduced memory birthday attacks

Extensions of the technique

Some direct applications

Fourier and Hadamard–Walsh Transforms

Introductory example: studying S-boxes

Algebraic normal forms of boolean functions

Goldreich–Levin theorem

Generalization of the Walsh transform to Fp

Fast Fourier transforms

Lattice Reduction

Definitions

Introductory example: Gauss reduction

Higher dimensions

Shortest vectors and improved lattice reduction

Dual and orthogonal lattices

Polynomial Systems and Gröbner Bases Computations

General framework

Bivariate systems of equations

Definitions: multivariate ideals, monomial orderings, and Gröbner bases

Buchberger algorithm

Macaulay’s matrices

Faugère’s algorithms

Algebraic attacks on multivariate cryptography

On the complexity of Gröbner bases computation

APPLICATIONS

Attacks on Stream Ciphers

LFSR-based keystream generators

Correlation attacks

Algebraic attacks

Extension to some nonlinear shift registers

The cube attack

Time memory data tradeoffs

Lattice-Based Cryptanalysis

Direct attacks using lattice reduction

Coppersmith’s small roots attacks

Elliptic Curves and Pairings

Introduction to elliptic curves

The Weil pairing

The elliptic curve factoring method

Index Calculus Algorithms

Introduction to index calculus

A simple finite field example

Generalization to finite fields with small enough characteristics

Introduction to the number field sieve

Smoothness probabilities

References