TY - GEN

T1 - Analysis of QUAD

AU - Yang, B.Y.

AU - Chen, O.C.H.

AU - Bernstein, D.J.

AU - Chen, J.M.

PY - 2007

Y1 - 2007

N2 - In a Eurocrypt 2006 article entitled "QUAD: A Practical Stream Cipher with Provable Security," Berbain, Gilbert, and Patarin introduced QUAD, a parametrized family of stream ciphers. The article stated that "the security of the novel stream cipher is provably reducible to the intractability of the MQ problem"; this reduction deduces the infeasibility of attacks on QUAD from the hypothesized infeasibility (with an extra looseness factor) of attacks on the well-known hard problem of solving systems of multivariate quadratic equations over finite fields. The QUAD talk at Eurocrypt 2006 reported speeds for QUAD instances with 160-bit state and output block over the fields GF(2), GF(16), and GF(256).
This paper discusses both theoretical and practical aspects of attacking QUAD and of attacking the underlying hard problem. For example, this paper shows how to use XL-Wiedemann to break the GF(256) instance QUAD(256,20,20) in approximately 266 Opteron cycles, and to break the underlying hard problem in approximately 245 cycles. For each of the QUAD parameters presented at Eurocrypt 2006, this analysis shows the implications and limitations of the security proofs, pointing out which QUAD instances are not secure, and which ones will never be proven secure. Empirical data backs up the theoretical conclusions; in particular, the 245-cycle attack was carried out successfully.

AB - In a Eurocrypt 2006 article entitled "QUAD: A Practical Stream Cipher with Provable Security," Berbain, Gilbert, and Patarin introduced QUAD, a parametrized family of stream ciphers. The article stated that "the security of the novel stream cipher is provably reducible to the intractability of the MQ problem"; this reduction deduces the infeasibility of attacks on QUAD from the hypothesized infeasibility (with an extra looseness factor) of attacks on the well-known hard problem of solving systems of multivariate quadratic equations over finite fields. The QUAD talk at Eurocrypt 2006 reported speeds for QUAD instances with 160-bit state and output block over the fields GF(2), GF(16), and GF(256).
This paper discusses both theoretical and practical aspects of attacking QUAD and of attacking the underlying hard problem. For example, this paper shows how to use XL-Wiedemann to break the GF(256) instance QUAD(256,20,20) in approximately 266 Opteron cycles, and to break the underlying hard problem in approximately 245 cycles. For each of the QUAD parameters presented at Eurocrypt 2006, this analysis shows the implications and limitations of the security proofs, pointing out which QUAD instances are not secure, and which ones will never be proven secure. Empirical data backs up the theoretical conclusions; in particular, the 245-cycle attack was carried out successfully.

U2 - 10.1007/978-3-540-74619-5_19

DO - 10.1007/978-3-540-74619-5_19

M3 - Conference contribution

SN - 978-3-540-74617-1

T3 - Lecture Notes in Computer Science

SP - 290

EP - 308

BT - Fast Software Encryption (14th International Workshop, FSE2007, Luxembourg, Luxembourg, March 26-28, 2007. Revised Selected Papers)

A2 - Biryukov, A.

PB - Springer

CY - Berlin

T2 - conference; FSE2007, Luxembourg, Luxembourg; 2007-03-26; 2007-03-28

Y2 - 26 March 2007 through 28 March 2007

ER -