Algebraic Fault Analysis of UOV and Rainbow With the Leakage of Random Vinegar Values

A public-key cryptographic algorithm based on multivariate quadratic equations is one of promising post-quantum alternatives for current public-key cryptography. The security of multivariate quadratic schemes has been sufficiently analyzed mathematically, but few works have been devoted to implementation attacks. In this paper, we present algebraic fault analysis of two well-known multivariate quadratic schemes, UOV and Rainbow, which combines fault attacks with key recovery attacks using good keys. We focus on fault attacks which cause faults on random Vinegar values used in signing. Our fault models are divided into three cases according to the leakage types of the Vinegar values: reused, revealed and set to zero. We show that the equivalent key of UOV is completely recovered in polynomial time from (m+1), n and m signatures generated by the entire faulty Vinegar values in the three cases, respectively. Specifically, the equivalent key of UOV is completely recovered from 45, 103 and 44 signatures generated by 59 bytes of faulty Vinegar values in the three cases, respectively, at a 128-bit security level. The equivalent key of Rainbow is also recovered from 44, 79 and 43 signatures with 36 bytes of faulty Vinegar values in the three cases, respectively. This is the first result that leads to the full secret key recovery of UOV and Rainbow from the leakage of the Vinegar values. In the other cases, we show that complexities of the key recovery attacks on Rainbow and UOV are significantly weakened in terms of the number of faulty Vinegar values. Our attacks can be applied to Rainbow and LUOV selected to NIST Post-Quantum Cryptography Standardization Round 2. Countermeasures against our attacks are investigated.