QUAD (cipher)
Encyclopedia
In cryptography
, the QUAD, cipher is a relatively new stream cipher
, which was designed with provable security arguments in mind.
The keystream generation process simply consists in iterating the three following
steps in order to produce (k -1) n GF(q) keystream values at each iteration.
QUAD is a modern stream cipher, i.e. it uses a key and an initialisation value (IV) to produce a keystream sequence. A Key and IV setup is also defined which also rely on multivariate quadratic system.
generation of QUAD is provably reducible to the conjectured intractability of the MQ problem, namely solving a multivariate system of quadratic equations. The first proof was done over field GF(2) for an old-fashioned stream cipher (where the key is the initial state). It was later extended by Berbain and Gilbert in order to take into account the set-up procedure of a modern cipher (with a setup stage deriving the initial state from the key). The security of the whole cipher as a Pseudo Random Function can be related to the conjectured intractability of the MQ problem. The authors also studied the resistance of the cipher against classical attacks.
At Eurocrypt 2006, speed reports were presented for QUAD instances with 160-bit state and output block over the fields GF(2), GF(16), and GF(256). These speed reports were part of an analysis of "Efficient Implementations of Multivariate Quadratic Systems" which was published by Berbain, Billet, and Gilbert at SAC 2006. This analysis (which also covers several multivariate public-key schemes as well as the QUAD stream cipher) studied in part the impact of changing the size of the field on the performances without considering the security aspect.
Yang, Chen, Bernstein and Chen studied the security of the different parameter sets in the document "Analysis of Quad" and found some of them very insecure. Their 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, which was carried out successfully. However, according to this paper, it would take about 2110 to solve an instance of the QUAD(2,160,160) version recommended by the authors of QUAD using XL-Wiedemann.
The study by Yang et al. highlighted the fact that security theorems often rely on reductions with a looseness factor, and when this is taken into account, none of the parameter sets of the suggested versions are not sufficient to get a contradiction with the proof of security. An instance that will be provably secure would be QUAD(2,320,320), that is, twice as wide as originally proposed.
A security theorem can also be proved for GF(q), albeit with a larger looseness factor; this and extensions of QUAD for more efficient implementations is proposed by Liu et al. (see reference "Secure PRNGs from Specialized Polynomial Maps over Any Fq").
Cryptography
Cryptography is the practice and study of techniques for secure communication in the presence of third parties...
, the QUAD, cipher is a relatively new stream cipher
Stream cipher
In cryptography, a stream cipher is a symmetric key cipher where plaintext digits are combined with a pseudorandom cipher digit stream . In a stream cipher the plaintext digits are encrypted one at a time, and the transformation of successive digits varies during the encryption...
, which was designed with provable security arguments in mind.
Description
QUAD relies on the iteration of a randomly chosen multivariate quadratic system S=(Q1, ..., Qm) of m=kn equations in n unknowns over a finite field GF(q).The keystream generation process simply consists in iterating the three following
steps in order to produce (k -1) n GF(q) keystream values at each iteration.
- Compute the kn-tuple of GF(q) values S(x) = (Q1(x),..., Qkn(x)) where x is the current value of the internal state;
- Output the sequence (Qn+1(x),..., Qkn(x)) of (k-1)n GF(q) keystream values
- Update the internal state x with the sequence of n GF(q) first generated values (Q1(x),..., Qn(x))
QUAD is a modern stream cipher, i.e. it uses a key and an initialisation value (IV) to produce a keystream sequence. A Key and IV setup is also defined which also rely on multivariate quadratic system.
Security
The security of the keystreamKeystream
In cryptography, a keystream is a stream of random or pseudorandom characters that are combined with a plaintext message to produce an encrypted message ....
generation of QUAD is provably reducible to the conjectured intractability of the MQ problem, namely solving a multivariate system of quadratic equations. The first proof was done over field GF(2) for an old-fashioned stream cipher (where the key is the initial state). It was later extended by Berbain and Gilbert in order to take into account the set-up procedure of a modern cipher (with a setup stage deriving the initial state from the key). The security of the whole cipher as a Pseudo Random Function can be related to the conjectured intractability of the MQ problem. The authors also studied the resistance of the cipher against classical attacks.
Parameters recommended
The authors recommend to use a version of QUAD with a 80-bit key, 80-bit IV and an internal state of n = 160 bits. It outputs 160 keystream bits (m = 320) at each iteration until 240 bits of keystream have been produced.At Eurocrypt 2006, speed reports were presented for QUAD instances with 160-bit state and output block over the fields GF(2), GF(16), and GF(256). These speed reports were part of an analysis of "Efficient Implementations of Multivariate Quadratic Systems" which was published by Berbain, Billet, and Gilbert at SAC 2006. This analysis (which also covers several multivariate public-key schemes as well as the QUAD stream cipher) studied in part the impact of changing the size of the field on the performances without considering the security aspect.
Discussion on parameters
The initial security theorem for QUAD is valid for the field GF(2) only, and recommended parameters does not achieve to get a contradiction with the proof of security. The authors of QUAD who gave the security theorem acknowledged that a break of QUAD at their suggested parameters does not contradict the proof-of-security theorems when they proposed the scheme at Eurocrypt 2006. However it seemed that the authors had considered them as sufficient to provide the desired security level of about 280.Yang, Chen, Bernstein and Chen studied the security of the different parameter sets in the document "Analysis of Quad" and found some of them very insecure. Their 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, which was carried out successfully. However, according to this paper, it would take about 2110 to solve an instance of the QUAD(2,160,160) version recommended by the authors of QUAD using XL-Wiedemann.
The study by Yang et al. highlighted the fact that security theorems often rely on reductions with a looseness factor, and when this is taken into account, none of the parameter sets of the suggested versions are not sufficient to get a contradiction with the proof of security. An instance that will be provably secure would be QUAD(2,320,320), that is, twice as wide as originally proposed.
A security theorem can also be proved for GF(q), albeit with a larger looseness factor; this and extensions of QUAD for more efficient implementations is proposed by Liu et al. (see reference "Secure PRNGs from Specialized Polynomial Maps over Any Fq").