TL;DR
This paper presents a practical, polynomial-time attack that can recover the secret key of the PROV signature scheme, a candidate for post-quantum cryptography. The attack exploits a flaw in the initial specification where a component of the secret key was inadvertently leaked during the signing process, a vulnerability that has since been addressed in a revised version of the scheme.
What Problem Does This Paper Address?
The National Institute of Standards and Technology (NIST) is in the process of standardizing post-quantum cryptographic algorithms to secure communications against future quantum computers. Among the candidates are multivariate signature schemes, which offer attractive properties like fast verification. PROV is one such scheme, based on the Unbalanced Oil and Vinegar (UOV) family, that boasts a strong security proof under the assumption that solving its underlying multivariate polynomial system is hard. However, the security of any cryptographic scheme hinges on its concrete implementation and adherence to its theoretical security model. This paper addresses the critical question of whether the initial specification of PROV (v1.0) is indeed as secure as claimed, specifically by investigating potential weaknesses that could lead to key recovery.
Methods
The core of the attack leverages a technique inspired by the Kipnis-Shamir attack on UOV. The authors first identify that in the PROV v1.0 specification, a component of the secret key, referred to as the "vinegar vector" (part of the secret vanishing subspace $O$), is leaked during the signature generation process. This leaked vector, combined with the public key, allows an adversary to deduce a non-zero vector within the secret vanishing subspace $O$.
The attack then proceeds in two main stages:
- Kernel Approach: The paper extends the Kipnis-Shamir attack by analyzing the properties of the polar form of PROV's public-key polynomials. They show that the kernels of certain matrices derived from the public key are likely to contain the secret vanishing subspace $O$. By computing these kernels, they can effectively reduce the problem to a smaller system with fewer variables, while retaining the secret vanishing subspace.
- Key Recovery: After reducing the problem, the authors apply a technique to recover a basis of the secret vanishing subspace $O$ from the reduced system. This is achieved by exploiting the structure of the public-key polynomials restricted to the kernel found in the previous step.
The attack is implemented using the SageMath software, and its efficiency is demonstrated through experimental results.
Datasets
Not discussed in the paper. The paper focuses on theoretical attacks and experimental validation using the parameters of the PROV signature scheme as defined in its specification.
Key Insights and Ideas
- Leaky Secret Component: The most significant insight is the discovery that the initial PROV specification (v1.0) inadvertently leaks a component of the secret key (the vinegar vector) during signature generation. This leak is not a structural weakness of the underlying mathematical problem but an implementation flaw.
- Practicality of the Attack: The attack is not merely theoretical; it is shown to be highly practical, recovering the secret key in a matter of seconds for all proposed security parameters of PROV. This highlights the importance of careful implementation in cryptographic schemes.
- Exploiting Kernel Properties: The paper effectively adapts and extends existing techniques for UOV to PROV by leveraging the properties of the kernel of matrices derived from the public-key polynomials. This demonstrates a powerful approach for cryptanalyzing multivariate signature schemes.
- Countermeasure Simplicity: The fix for this vulnerability is remarkably simple: ensuring the vinegar vector is uniformly generated and kept secret. This underscores how subtle implementation details can have profound security implications.
Key Results
The paper demonstrates a polynomial-time key-recovery attack against the PROV specification v1.0. The attack successfully recovers the entire secret key by exploiting the leaked vinegar vector. Experimental results show that for all proposed security levels of PROV, the secret key can be recovered in at most 8 seconds using a standard laptop. This practical efficiency highlights the severity of the discovered vulnerability.
Limitations and Future Work
The authors acknowledge that their attack is not structural but exploits a specific flaw in the v1.0 specification. They also note that the attack relies on the assumption that the kernels of the public-key matrices are sufficiently related to the secret vanishing subspace, which they show holds with high probability.
The paper concludes by discussing a simple countermeasure that makes PROV immune to this attack. This countermeasure involves ensuring the vinegar vector is uniformly generated and kept secret. The authors report this vulnerability to the PROV designers, who subsequently updated the specification to v1.1, incorporating this fix. Future work would naturally involve analyzing the security of the updated PROV v1.1 specification and other post-quantum signature schemes.
Summary updated