Post-Quantum Secure Feldman's Verifiable Secret Sharing Timing Side-Channel Vulnerability

A timing side-channel vulnerability has been identified in the 'feldman_vss' library, which implements Feldman's Verifiable Secret Sharing (VSS) scheme. This vulnerability exists in versions through 0.8.0b2 and is rooted in Python's execution model, which does not ensure constant-time performance. The issue arises in the library's matrix operations, particularly within the '_find_secure_pivot' function and potentially other areas of '_secure_matrix_solve'. An attacker capable of measuring the execution time of these functions could exploit the timing variations to recover secret information, such as polynomial coefficients, used in the VSS scheme. The vulnerability could lead to a complete compromise of the shared secret, allowing an attacker to access sensitive information protected by the VSS protocol.

Impact

Exploitation of this vulnerability could enable an attacker to recover secret keys or other sensitive information safeguarded by the VSS scheme, leading to a total compromise of the shared secret.

Reproduction

The vulnerability can be reproduced by calling the '_find_secure_pivot' function or '_secure_matrix_solve' with crafted inputs that exploit the timing variations in matrix operations. This can be done by measuring the execution time of these functions and analyzing the data to infer secret information.

Remediation

The library's documentation acknowledges that these vulnerabilities cannot be effectively addressed in pure Python. Users are advised to use the library only in environments where timing attacks are not feasible, to implement wrappers around critical operations with constant-time libraries in languages like Rust, Go, or C, and to await the planned Rust implementation that will properly resolve these issues.