2007 | OriginalPaper | Buchkapitel
Analysis of QUAD
verfasst von : Bo-Yin Yang, Owen Chia-Hsin Chen, Daniel J. Bernstein, Jiun-Ming Chen
Erschienen in: Fast Software Encryption
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
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 2
66
Opteron cycles, and to break the underlying hard problem in approximately 2
45
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 2
45
-cycle attack was carried out successfully.