Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top

2009 | Book

Introduction: How to Use this Book Read chapter Read first chapter

Algebraic Cryptanalysis

Author: Gregory V. Bard

Publisher: Springer US

Part of: Springer Professional "Wirtschaft+Technik" , Springer Professional "Technik" , Springer Professional "Wirtschaft"

Login to get access
insite
SEARCH

About this book

Algebraic Cryptanalysis bridges the gap between a course in cryptography, and being able to read the cryptanalytic literature. This book is divided into three parts: Part One covers the process of turning a cipher into a system of equations; Part Two covers finite field linear algebra; Part Three covers the solution of Polynomial Systems of Equations, with a survey of the methods used in practice, including SAT-solvers and the methods of Nicolas Courtois.

Topics include:

Analytic Combinatorics, and its application to cryptanalysis

The equicomplexity of linear algebra operations

Graph coloring

Factoring integers via the quadratic sieve, with its applications to the cryptanalysis of RSA

Algebraic Cryptanalysis is designed for advanced-level students in computer science and mathematics as a secondary text or reference book for self-guided study. This book is suitable for researchers in Applied Abstract Algebra or Algebraic Geometry who wish to find more applied topics or practitioners working for security and communications companies.

Table of Contents

Frontmatter
Chapter 1. Introduction: How to Use this Book
Abstract
As starlier, the purpose of this book is to help graduate students who wish to learn something about algebraic cryptanalysis, or researchers from either other branches of cryptography, computer algebra, or finite fields who may wish to try their hand at code-breaking.
Citations for all the topics described here appear in the respective chapters, and therefore are omitted in the introduction, to preserve readability.
Gregory V. Bard

Cryptanalysis

Frontmatter
Chapter 2. The Block Cipher Keeloq and Algebraic Attacks
Abstract
The purpose of this chapter is to supply a (relatively) new, feasible, and economically relevant example of algebraic cryptanalysis. The block cipher “Keeloq”1 has been used in the remote keyless-entry system of many automobiles. It has a secret key consisting of 64 bits, takes a plaintext of 32 bits, and outputs a ciphertext of 32 bits. The cipher consists of 528 rounds. In this chapter, we define the cipher.We also show some “frontal assaults” that are not effective. In the next chapter, we describe a successful attack from the author’s dissertation [31, Ch. 2]. Our attack is faster than brute force by a factor of around 214:77 as shown in Section 3.5 on Page 24.
A summary of the attack is given in Section 3.6 on Page 24. Many other attacks on Keeloq are known, discovered since this attack of mine was first written back in January of 2007. In fact, it seems clear from the dates of publication of other attacks, that work on Keeloq was simultaneous among the several research teams involved (see Section 3.8.1 on Page 27). The purpose here is not to describe all or even some of the attacks on Keeloq but to give the reader a non-trivial but straight-forward example of algebraic cryptanalysis succeeding on a real-world cipher.
Gregory V. Bard
Chapter 3. The Fixed-Point Attack
Abstract
Here the author will explain the attack that was the opening of his dissertation. The goal is first, to rewrite the cipher as a function g executed on the output of a function f which is iterated 8 times on the plaintext. Next, we will strip away g, and try to find fixed points of the 8th iterate of f. Some of these are fixed points of f. Using fixed points of f, we can recover the secret key by solving a polynomial system of equations. As you can see, the attack is rather indirect.
Gregory V. Bard
Chapter 4. Iterated Permutations
Abstract
The purpose of this chapter is to allow us to calculate what fraction of permutations in S n have a particular property ø, in the limit as n tends to infinity. This will be accomplished via analytic combinatorics.
Combinatorics is the branch of mathematics concerned with counting objects. The technique of using a function of a variable to count objects of various sizes, using the properties of multiplication and addition of series as an aid, is accredited to Pierre-Simon Laplace [116, Ch. “Invit.”].
Gregory V. Bard
Chapter 5. Stream Ciphers
Abstract
While Keeloq is an important cipher, used in industry and with an interesting set of methods for its cryptanalysis, the author believes that some more examples might be useful. Here, we present the ciphers Trivium and Bivium, as well as QUAD.
The purpose of this chapter is not only to exposit on how the ciphers presented here can be or cannot be attacked. Instead, the main purpose is to share some interesting ciphers and exposit on how those ciphers are converted into a system of equations. This relationship between the cipher and the equations is not trivial. The task of converting a cipher to equations, and doing so efficiently, is a major task in algebraic cryptanalysis. Also, because QUAD is based on random systems of equations, it is an endless source of cryptanalytic examples. The Bivium and Trivium equations are an excellent source for testing new techniques.
While great care has been taken to cite the work of others carefully, and note who has done what, the author wishes to be rather clear that nothing contained in this chapter whatsoever is his own idea, but rather taken from cited published papers, and presented in a more pedagogical style.
Gregory V. Bard

Linear Systems Mod 2

Frontmatter
Chapter 6. Some Basic Facts about Linear Algebra over $$\mathbb{G}\mathbb{F}$$ (2)
Abstract
The purpose of this chapter is to identify some facts about \(\mathbb{G}\mathbb{F}\)(2)-vector spaces and about matrices over \(\mathbb{G}\mathbb{F}\)(2). To emphasize the differences between matrices over ℙ, or ℂ, and matrices over \(\mathbb{G}\mathbb{F}\)(2), we note several interesting phenomena. The contents of this chapter are already known, but we present them here as a “warm up.” They are stated here so that they can be used elsewhere, and for background.
Gregory V. Bard
Chapter 7. The Complexity of $$\mathbb{G}\mathbb{F}$$ (2)-Matrix Operations
Abstract
Here, we propose a new model, counting matrix-memory operations instead of field operations, for reasons to be discussed. It turns out this model describes reality only partially—but we will explicitly discuss the circumstances in which the model is descriptive and in which it fails, see Section 7.1.4 on Page 92. The complexity expressions are summarized in Table 7.1 on Page 105. Also of interest are certain data structure choices that we made in arranging our linear algebra library, see Section 9 on Page 133. This library was used by Nicolas Courtois in his cryptographic research, as well as by the author, and now forms part of the \(\mathbb{G}\mathbb{F}\)(2) linear algebra suite of SAGE [7], an open source competitor to MAGMA [2], MATLAB [5], MAPLE [3], and MATHEMATICA[4]. These are described in Section 7.4 on Page 94.
Gregory V. Bard
Chapter 8. On the Exponent of Certain Matrix Operations
Abstract
A great deal of research was done in the period 1969–1987 on fast matrix operations, including [185, 212, 206, 213, 62]. Various proofs showed that many important matrix operations, such as QR-decomposition, LU-factorization, inversion, and finding determinants, are no more complex than matrix multiplication, in the big-Oh sense, see [13, Ch. 6] or [63, Ch. 28].
For this reason, many fast matrix multiplication algorithms were developed. Almost all were intended to work over a general ring. However, one in particular was intended for boolean matrices, and by extension \(\mathbb{G}\mathbb{F}\)(2)-matrices, which was named the Method of Four Russians, “after the cardinality and the nationality of its inventors.” While the Method of Four Russians was conceived as a boolean matrix multiplication tool, we show how to use it for \(\mathbb{G}\mathbb{F}\)(2) matrices and for inversion, in Section 9.3 on Page 137 and Section 9.4 on Page 141.
Gregory V. Bard
Chapter 9. The Method of Four Russians
Abstract
As we’ve seen throughout this text, solving a linear system of GF(2) equations lies at the heart of many cryptanalytic techniques. Some examples include stream cipher cryptanalysis via the XL algorithm and its many variants [22, 23, 24, 25, 66, 67, 69, 79, 134, 82]; the algebraic attacks on the HFE public-key cryptosystem and Quartz [65, 111, 78, 72, 77, 68, 70]; cryptanalysis of QUAD [42]; and solving the matrix square root (provably NP-Hard for matrices over the boolean semiring) with the XL algorithm [155].
Gregory V. Bard
Chapter 10. The Quadratic Sieve
Abstract
This chapter will discuss the Linear Sieve and Quadratic Sieve, algorithms for factoring the product of two distinct prime integers, or any other composite number. The main purpose of the algorithm is to break the famous cryptosystem RSA. The algorithms use matrices over \(\mathbb{G}\mathbb{F}\)(2), but they will be sparse matrices rather than dense matrices.
This chapter is here for several reasons. First, we have written primarily of dense matrices over \(\mathbb{G}\mathbb{F}\)(2), and the exposition would be incomplete without discussing sparse matrices. The sparse matrix techniques described in Appendix D can be used anywhere that sparsity occurs in cryptanalysis, but many were designed for the Quadratic Sieve. Second, we have written of how to break block ciphers and stream ciphers, so it would be a pity not to discuss how to break public-key systems as well. Third, the Quadratic Sieve algorithm, when taken with all its variants and modifications, stands as one of the most sophisticated algorithms in all of computer science, and fourth, it uses some elegant number theory.
This is only the tip of a very large iceberg. There are many variations, improvements, and enhancements which are omitted here. Many of those are crucial in factoring larger numbers. Furthermore, we exclude many other important factoring algorithms, because they are unrelated to the Quadratic Sieve. While the NFS (Number Field Sieve) has eclipsed the Quadratic Sieve as an algorithm, understanding the NFS is much easier after studying the QS. We hope this section will inspire the reader to read further on this vital topic.
Gregory V. Bard

Polynomial Systems and Satisfiability

Frontmatter
Chapter 11. Strategies for Polynomial Systems
Abstract
Before we devote numerous pages to the topic of polynomial systems of equations over finite fields, we should pause and ask why one would want to do this. This will give us an opportunity to highlight the several applications of this interesting area.
Before that, however, an important distinction must be made. In this book, when one has a system of equations over the finite field \(\mathbb{G}\mathbb{F}\)(p n ), we assume that one is interested only in those solutions which are also elements of \(\mathbb{G}\mathbb{F}\)(pn). If one is also interested in solutions in some extension field, (e.g. \(\mathbb{G}\mathbb{F}\)(p m ) with n|m), then since \(\mathbb{G}\mathbb{F}\)(p n ) is a subfield of \(\mathbb{G}\mathbb{F}\)(p m ), it is safe to consider the system of equations as if it were over \(\mathbb{G}\mathbb{F}\)(p n ), or at worse the splitting field.
Gregory V. Bard
Chapter 12. Algorithms for Solving Polynomial Systems
Abstract
Because of the previously mentioned NP-Complete status of MQ, the topic of how to actually solve these systems has the disadvantage that truly efficient (i.e. polynomial time) algorithms have not yet been found. In fact, they will never be found if P ≠ NP. Nonetheless, there are algorithms available for experimentation, many of which we describe below.
Gregory V. Bard
Chapter 13. Converting MQ to CNF-SAT
Abstract
In this chapter, we study methods for efficiently converting GF(2) systems of multivariate polynomial equations into a conjunctive normal form satisfiability (CNF-SAT) problem, for which excellent heuristic algorithms have been developed in recent years. Please note that much of this information can be found in the paper by the author, Chris Jefferson, and Nicolas Courtois [33], which also has some preliminary experiments.
Gregory V. Bard
Chapter 14. How do SAT-Solvers Operate?
Abstract
The purpose of this chapter is to explain how SAT-solvers operate (at least at the time of the writing of this book, late 2008). Two major families will be described in this section. The family of SAT-solvers used by the author are based on the Chaff Algorithm [182], culminating in MINISAT, a popular SAT-solver [104] [6]. This gives insight into Chapter 13 on Page 245 in particular, by highlighting why the number of variables per clause, number of clauses, and number of variables, are taken as the three general barometers of difficulty for a particular SAT problem. As a contrast, we will first describe Walk-SAT, a very different type of solver, to show how these methods and approaches differ and are similar. At this time, many SATsolvers are in use, most of them of the Chaff/MINISATtype. However, that could someday change, perhaps even soon.
Besides the Chaff family and the Walk-SAT family, many other SAT algorithms have been proposed in previous years, and also many preprocessing techniques, none of which will be described below. While the author makes frequent and extensive use of SAT-solvers, he is not an expert on their internals. The following is meant to be informative and general, and so many details are omitted.
Gregory V. Bard
Chapter 15. Applying SAT-Solvers to Extension Fields of Low Degree
Abstract
In this book we have been discussing polynomial equations over finite fields of characteristic two for quite some time. However, the finite field in question has almost always been \(\mathbb{G}\mathbb{F}\)(2). In cryptanalysis, this is usually the field of interest, with notable exceptions, including several ciphers: Rijndael [89] which later become the Advanced Encryption Standard (AES), which uses \(\mathbb{G}\mathbb{F}\)(256); the cryptosystem called TTM [127], over the same field; the Courtois Toy Cipher (CTC) [14] [73], can be modeled over \(\mathbb{G}\mathbb{F}\)(8) for certain settings. The stream cipher family QUAD [42] can operate over any finite field, but finite fields of characteristic two would be the natural setting (see Section 5.2 on Page 66).
Gregory V. Bard
Backmatter
Metadata
Title
Algebraic Cryptanalysis
Author
Gregory V. Bard
Copyright Year
2009
Publisher
Springer US
Electronic ISBN
978-0-387-88757-9
Print ISBN
978-0-387-88756-2
DOI
https://doi.org/10.1007/978-0-387-88757-9

Premium Partner

    Image Credits