## CryptoDB

### Gregory V. Bard

#### Publications

**Year**

**Venue**

**Title**

2010

EPRINT

Improved Algebraic Cryptanalysis of QUAD, Bivium and Trivium via Graph Partitioning on Equation Systems
Abstract

We present a novel approach for solving systems of polynomial equations via graph partitioning. The concept of a variable-sharing graph of a system of polynomial equations is defined. If such graph is disconnected, then the corresponding system of equations can be split into smaller ones that can be solved individually. This can provide a significant speed-up in computing the solution to the system, but is unlikely to occur either randomly or in applications. However, by deleting a certain vertices on the graph, the variable-sharing graph could be disconnected in a balanced fashion, and in turn the system of polynomial equations are separated into smaller ones of similar sizes. In graph theory terms, this process is equivalent to finding balanced vertex partitions with minimum-weight vertex separators. The techniques of finding these vertex partitions are discussed, and experiments are performed to evaluate its practicality for general graphs and systems of polynomial equations. Applications of this approach in algebraic cryptanalysis on symmetric ciphers are presented. For the QUAD family of stream ciphers, we show how a malicious party can manufacture conforming systems that can be easily broken. For the stream cipher Trivium and its variants, we achieve significant speedups in algebraic attacks launched against them. In each of these cases, the systems of polynomial equations involved are well-suited to our graph partitioning method. These results may open a new avenue for evaluating the security of symmetric ciphers against algebraic attacks.

2007

EPRINT

Efficient Methods for Conversion and Solution of Sparse Systems of Low-Degree Multivariate Polynomials over GF(2) via SAT-Solvers
Abstract

The computational hardness of solving large systems of sparse and low-degree multivariate equations is a necessary condition for the security of most modern symmetric cryptographic schemes. Notably, most cryptosystems can be implemented with inexpensive hardware, and have a low gate counts, resulting in a sparse system of equations, which in turn renders such attacks feasible. On one hand, numerous recent papers on the XL algorithm and more sophisticated Groebner-bases techniques [5, 7, 13, 14] demonstrate that systems of equations are efficiently solvable when they are sufficiently overdetermined or have a hidden internal algebraic structure that implies the existence of some useful algebraic relations. On the other hand, most of this work, as well as most successful algebraic attacks, involve dense, not sparse systems, at least until linearization by XL or a similar algorithm. No polynomial-system-solving algorithm we are aware of, demonstrates that a significant benefit is obtained from the extreme sparsity of some systems of equations.
In this paper, we study methods for efficiently converting systems of low-degree sparse multivariate equations into a conjunctive normal form satisfiability (CNF-SAT) problem, for which excellent heuristic algorithms have been developed in recent years. A direct application of this method gives very efficient results: we show that sparse multivariate quadratic systems (especially if over-defined) can be solved much faster than by exhaustive search if beta < 1/100. In particular, our method requires no additional memory beyond that required to store the problem, and so often terminates with an answer for problems that cause Magma and Singular to crash. On the other hand, if Magma or Singular do not crash, then they tend to be faster than our method, but this case includes only the smallest sample problems.

2007

EPRINT

Algebraic and Slide Attacks on KeeLoq
Abstract

KeeLoq is a block cipher used in wireless devices that unlock doors in cars manufactured by Chrysler, Daewoo, Fiat, GM, Honda, Jaguar, Toyota, Volvo, Volkswagen, etc. It was designed in the 80's by Willem Smit from South Africa and in 1995 was sold to Microchip Technology Inc for more than 10 million USD. Though no attack on this cipher have been found thus far, the 64-bit key size makes it no longer secure. Hackers and car thieves exploit this, to recover the key by brute force with FPGA's.
From our point of view however, this cipher is interesting for other reasons. Compared to typical block ciphers that have a few carefully designed rounds, this cipher has 528 extremely simple rounds with extremely few intermediate variables (one per round). This seems a perfect target to study algebraic attacks on block ciphers. The cipher also has a periodic structure with period of 64 rounds, and an unusually small block size of 32 bits.
We present several slide-algebraic attacks on KeeLoq, the best of which allows one to recover the full key for the full cipher within 2^48 CPU clocks.
Until now algebraic attacks didn't give interesting results
on block ciphers and most researchers seriously doubted if any block cipher will EVER be broken by such attacks.
In this paper however, we show that, for the first time in history,
a full round real-life block cipher is broken by an algebraic attack.
Moreover, our attacks are easy to implement,
have been tested experimentally, and the full key
can be recovered in practice on a PC.

2006

EPRINT

A Challenging but Feasible Blockwise-Adaptive Chosen-Plaintext Attack on SSL
Abstract

This paper introduces a chosen-plaintext vulnerability in the Secure
Sockets Layer (SSL) and Trasport Layer Security (TLS) protocols which
enables recovery of low entropy strings such as can be guessed from a
likely set of 2--1000 options. SSL and TLS are widely used for
securing communication over the Internet. When utilizing block ciphers
for encryption, the SSL and TLS standards mandate the use of the
cipher block chaining (CBC) mode of encryption which requires an
initialization vector (IV) in order to encrypt. Although the first IV
used by SSL is a (pseudo)random string which is generated and shared
during the initial handshake phase, subsequent IVs used by SSL are
chosen in a deterministic, predictable pattern; in particular, the IV
of a message is taken to be the final ciphertext block of the
immediately-preceding message, and is therefore known to the adversary.
The one-channel nature of web proxies, anonymizers or Virtual Private
Networks (VPNs), results in all Internet traffic from one machine
traveling over the same SSL channel. We show this provides a feasible
``point of entry'' for this attack. Moreover, we show that the
location of target data among block boundaries can have a profound
impact on the number of guesses required to recover that data,
especially in the low-entropy case.
The attack in this paper is an application of the blockwise-adaptive
chosen-plaintext attack paradigm, and is the only feasible attack to
use this paradigm with a reasonable probability of success. The
attack will work for all versions of SSL, and TLS version 1.0. This
vulnerability and others are closed in TLS 1.1 (which is still in
draft status) and OpenSSL after 0.9.6d. It is hoped this paper will
encourage the deprecation of SSL and speed the adoption of OpenSSL
or TLS 1.1/1.2 when they are finially released.

2006

EPRINT

Achieving a log(n) Speed Up for Boolean Matrix Operations and Calculating the Complexity of the Dense Linear Algebra step of Algebraic Stream Cipher Attacks and of Integer Factorization Methods
Abstract

The purpose of this paper is to calculate the running time of dense boolean matrix operations,
as used in stream cipher cryptanalysis and integer factorization. Several variations of Gaussian
Elimination, Strassen's Algorithm and the Method of Four Russians are analyzed. In particular,
we demonstrate that Strassen's Algorithm is actually slower than the Four Russians algorithm for
matrices of the sizes encountered in these problems. To accomplish this, we introduce a new model
for tabulating the running time, tracking matrix reads and writes rather than field operations, and
retaining the coefficients rather than dropping them. Furthermore, we introduce an algorithm known
heretofore only orally, a ``Modified Method of Four Russians'', which has not appeared in the literature
before. This algorithm is $\log n$ times faster than Gaussian Elimination for dense boolean
matrices. Finally we list rough estimates for the running time of several recent stream cipher cryptanalysis
attacks.

2006

EPRINT

Accelerating Cryptanalysis with the Method of Four Russians
Abstract

Solving a dense linear system of boolean equations is the final step of several cryptanalytic
attacks. Examples include stream cipher cryptanalysis via XL and related algorithms, integer
factorization, and attacks on the HFE public-key cryptosystem. While both Gaussian Elimination
and Strassenâs Algorithm have been proposed as methods, this paper specifies an algorithm
that is much faster than both in practice. Performance is formally modeled, and experimental
running times are provided, including for the optimal setting of the algorithmâs parameter.
The consequences for published attacks on systems are also provided. The algorithm is named
Method of Four Russians for Inversion (M4RI), in honor of the matrix multiplication algorithm
from which it emerged, the Method of Four Russians Multiplication (M4RM).

2006

EPRINT

Modes of Encryption Secure against Blockwise-Adaptive Chosen-Plaintext Attack
Abstract

Blockwise-adaptive chosen-plaintext and chosen-ciphertext attack are new models for cryptanalytic
adversaries, first discovered by Joux, et al [JMV02], and describe a vulnerability in
SSH discovered by Bellare, et al [BKN02]. Unlike traditional chosen-plaintext (CPA) or chosen-ciphertext
(CCA) adversaries, the blockwise adversary can submit individual blocks for encryption
or decryption rather than entire messages. This paper focuses on the search for on-line
encryption schemes which are resistant to blockwise-adaptive chosen-plaintext attack. We prove
that one oracle query with non-equal inputs is sufficient to win the blockwise-adaptive chosen-plaintext
game if the game can be won by any adversary in ppt with non-negligible advantage.
In order to uniformly describe such encryption schemes, we define a canonical representation
of encryption schemes based on functions believed to be pseudorandom (i.e. Block Ciphers).
This Canonical Form is general enough to cover many modes currently in use, including ECB,
CBC, CTR, OFB, CFB, ABC, IGE, XCBC, HCBC and HPCBC. An immediate result of the
theorems in this paper is that CTR, OFB, CFB, HCBC and HPCBC are proven secure against
blockwise-adaptive CPA, as well as S-ABC under certain conditions. Conversely ECB, CBC,
IGE, and P-ABC are proven to be blockwise-adaptive CPA insecure. Since CBC, IGE and
P-ABC are chosen-plaintext secure, this indicates that the blockwise-adaptive chosen-plaintext
model is a non-trivial extension of the traditional chosen-plaintext attack model.

2006

EPRINT

Spelling-Error Tolerant, Order-Independent Pass-Phrases via the Damerau-Levenshtein String-Edit Distance Metric
Abstract

It is well understood that passwords must be very long and complex to
have sufficient entropy for security purposes. Unfortunately, these
passwords tend to be hard to memorize, and so alternatives are
sought. Smart Cards, Biometrics, and Reverse Turing Tests (human-only
solvable puzzles) are options, but another option is to use
pass-phrases.
This paper explores methods for making pass-phrases suitable for use
with password-based authentication and key-exchange (PAKE) protocols,
and in particular, with schemes resilient to server-file
compromise. In particular, the $\Omega$-method of Gentry, MacKenzie
and Ramzan, is combined with the Bellovin-Merritt protocol to provide
mutual authentication (in the random oracle model
[CGH04,BBP04,MRH04]. Furthermore, since common password-related
problems are typographical errors, and the CAPSLOCK key, we show how a
dictionary can be used with the Damerau-Levenshtein string-edit
distance metric to construct a case-insensitive pass-phrase system
that can tolerate zero, one, or two spelling-errors per word, with no
loss in security. Furthermore, we show that the system can be made to
accept pass-phrases that have been arbitrarily reordered, with a
security cost that can be calculated.
While a pass-phrase space of $2^{128}$ is not achieved by this scheme,
sizes in the range of $2^{52}$ to $2^{112}$ result from various
selections of parameter sizes. An attacker who has acquired the
server-file must exhaust over this space, while an attacker without
the server-file cannot succeed with non-negligible probability.

2006

EPRINT

Algebraic Cryptanalysis of the Data Encryption Standard
Abstract

In spite of growing importance of AES, the Data Encryption Standard is by no means obsolete. DES has never been broken from the practical point of view. The triple DES is believed very secure, is widely used, especially in the financial sector, and should remain so for many many years to come. In addition, some doubts have been risen whether its replacement AES is secure, given the extreme level of ``algebraic vulnerability'' of the AES S-boxes (their low I/O degree and exceptionally large number of quadratic I/O equations).
Is DES secure from the point of view of algebraic cryptanalysis, a new very fast-growing area of research? We do not really hope to break it, but just to advance the field of cryptanalysis. At a first glance, DES seems to be a very poor target - as there is (apparently) no strong algebraic structure of any kind in DES. However Courtois and Pieprzyk showed that ``small'' S-boxes always have a low I/O degree (cubic for DES as we show). In addition, due to their low gate count requirements, by introducing additional variables, we can always get an extremely sparse system of quadratic equations.
To assess the algebraic vulnerabilities is the easy part, that may appear unproductive. In this paper we demonstrate that in this way,
several interesting attacks on a real-life ``industrial'' block cipher can be found. One of our attacks is the fastest known algebraic attack on 6 rounds of DES. Yet, it requires only ONE SINGLE known plaintext (instead of a very large quantity) which is quite interesting in itself.
Though (on a PC) we recover the key for only six rounds, in a much weaker sense we can also attack 12 rounds of DES. These results are very interesting because DES is known to be a very robust cipher,
and our methods are very generic. They can be applied to DES with modified S-boxes and potentially other reduced-round block ciphers.

2004

EPRINT

The Vulnerability of SSL to Chosen Plaintext Attack
Abstract

The Secure Sockets Layer (SSL) protocol is widely used for securing communication over the Internet. When utilizing block ciphers for encryption, the SSL standard mandates the use of the cipher block chaining (CBC) mode of encryption which requires an initialization vector (IV) in order to encrypt. Although the initial IV used by SSL is a (pseudo)random string which is generated and shared during the initial handshake phase, subsequent IVs used by SSL are chosen in a deterministic, predictable pattern; in particular, the IV of a message is taken to be the final ciphertext block of the immediately-preceding message. We show that this introduces a vulnerability in SSL which (potentially) enables easy recovery of low-entropy strings such as passwords or PINs that have been encrypted. Moreover, we argue that the open nature of web browsers provides a feasible ``point of entry'' for this attack via a corrupted plug-in; thus, implementing the attack is likely to be much easier than, say, installing a Trojan Horse for ``keyboard sniffing''. Finally, we suggest a number of modifications to the SSL standard which will prevent this attack.

#### Coauthors

- Nicolas Courtois (4)
- Chris Jefferson. (1)
- David Wagner (2)
- Kenneth Koon-Ho Wong (1)