Analysis of MQ-Sign
Monika Trimoska
Dear all,
We would like to announce a practical key-recovery attack on the MQ-Sign signature candidate. The attack exploits the sparseness property of the quadratic maps and it applies to MQ-Sign-SS and MQ-Sign-RS.
An explanatory note of the attack is attached to this email.
We implemented a verification script (https://github.com/mtrimoska/MQ-Sign-attack) that performs the attack in less than 7 seconds for security level 5. For convenience, we also provide an equivalent SageMath script in the repository, which is fairly slower.
All the best,
Thomas Aulbach, Simona Samardjiska, Monika Trimoska
Kyung-Ah Shim
We would like to thank you for sharing your analysis result.
The result showed that two sparse variants of MQ-Sign using an equivalent key T are vulnerable to the key recover attacks. We think that the attacks work.
However, according to specification of key generation algorithm of MQ-Sign, it uses a random invertible affine map T. Thus, the proposed attack cannot applied to MQ-Sign using the random affine maps.
Although our scheme specified the use of the random affine maps, we implemented it using a form of equivalent key for efficiency as in Rainbow (our implementation is based on the code of Rainbow).
Our implementation code will be changed to use a random map and will be updated.
In fact, it has been published before that UOV and Rainbow are insecure against the CPA when they use the equivalent keys instead of random maps (CHES 2018). These results show that the use of the equivalent key for efficiency can break security of the MQ-scheme.
We always only analyzed security of the case with random maps, so we missed security analysis of the case with equivalent keys.
We will also analyze the security of the sparse variants with a random affine map T. Please continue to pay attention to careful security analysis of our sparse variants.
Monika Trimoska
Dear authors,
Thank you for the clarification. However, we did not spot the use of the equivalent keys structure only in the reference implementation. The implementation specification in 4.1 explicitly states the form of T as used in the attack. Also, as far as we could tell, the secret key sizes that you report are derived using T in the specific structure (2vo for the central map + vo for T + (v+2o+32) for the linear and constant parts and the seed). If T is chosen as a random affine map, then the reported key sizes in Table 7 would not be correct.
With a random affine map, the secret key sizes are 26173, 63521, and 111749 Bytes for levels 1, 3, and 5 respectively. We agree that using a random affine map would protect against this attack, but the current version of MQ-Sign-{S/R}S, as described in its specification, is broken.
All the best,
Thomas, Simona, Monika
Hyungrok Jo
Monika Trimoska
We are writing to announce an attack on the last sparse MQ-Sign variant: MQ-Sign-SR. We develop an algebraic forgery attack and show that the sparseness in the vinegar-vinegar part of the central map yields a very specific structure in the polynomial systems. As a first result, we present a simple attack that exploits this structure and shows that the parameters chosen for MQ-Sign-SR slightly fail to provide the required security levels.
Please find attached an updated version of our paper for the description of the new attack and the complexity analysis.
All the best,
Thomas, Simona, Monika