International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Gregory V. Bard

Publications

Year
Venue
Title
2010
EPRINT
Improved Algebraic Cryptanalysis of QUAD, Bivium and Trivium via Graph Partitioning on Equation Systems
Kenneth Koon-Ho Wong Gregory V. Bard
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.
2008
FSE
2007
EPRINT
Efficient Methods for Conversion and Solution of Sparse Systems of Low-Degree Multivariate Polynomials over GF(2) via SAT-Solvers
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
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
Gregory V. Bard
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
Gregory V. Bard
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
Gregory V. Bard
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
Gregory V. Bard
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
Gregory V. Bard
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
Nicolas T. Courtois Gregory V. Bard
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
Gregory V. Bard
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.