ghsa-q65w-fg65-79f4
Vulnerability from github
Description:
The feldman_vss library contains timing side-channel vulnerabilities in its matrix operations, specifically within the _find_secure_pivot function and potentially other parts of _secure_matrix_solve. These vulnerabilities are due to Python's execution model, which does not guarantee constant-time execution. An attacker with the ability to measure the execution time of these functions (e.g., through repeated calls with carefully crafted inputs) could potentially recover secret information used in the Verifiable Secret Sharing (VSS) scheme.
The _find_secure_pivot function, used during Gaussian elimination in _secure_matrix_solve, attempts to find a non-zero pivot element. However, the conditional statement if matrix[row][col] != 0 and row_random < min_value: has execution time that depends on the value of matrix[row][col]. This timing difference can be exploited by an attacker.
The constant_time_compare function in this file also does not provide a constant-time guarantee.
This advisory formalizes the timing side-channel vulnerabilities already documented in the library's "Known Security Vulnerabilities" section. The Python implementation of matrix operations in the _find_secure_pivot and _secure_matrix_solve functions cannot guarantee constant-time execution, potentially leaking information about secret polynomial coefficients.
An attacker with the ability to make precise timing measurements of these operations could potentially extract secret information through statistical analysis of execution times, though practical exploitation would require significant expertise and controlled execution environments.
Impact:
Successful exploitation of these timing side-channels could allow an attacker to recover secret keys or other sensitive information protected by the VSS scheme. This could lead to a complete compromise of the shared secret.
References:
- File:
feldman_vss.py - Function:
_find_secure_pivot - Function:
_secure_matrix_solve - Function:
constant_time_compare - Timing Attacks on Implementations of Diffie-Hellman, RSA, DSS, and Other Systems (1996) - A seminal paper on timing attacks.
- Side-Channel Attacks - Wikipedia article on side-channel attacks.
Remediation:
As acknowledged in the library's documentation, these vulnerabilities cannot be adequately addressed in pure Python. The advisory recommends:
-
SHORT TERM: Consider using this library only in environments where timing measurements by attackers are infeasible.
-
MEDIUM TERM: Implement your own wrappers around critical operations using constant-time libraries in languages like Rust, Go, or C.
-
LONG TERM: Wait for the planned Rust implementation mentioned in the library documentation that will properly address these issues.
Note that the usage of random.Random() identified in the _refresh_shares_additive function is intentional and secure as documented in the "False-Positive Vulnerabilities" section of the code, and should not be considered part of this vulnerability.
{
"affected": [
{
"package": {
"ecosystem": "PyPI",
"name": "PostQuantum-Feldman-VSS"
},
"ranges": [
{
"events": [
{
"introduced": "0"
},
{
"last_affected": "0.8.0b2"
}
],
"type": "ECOSYSTEM"
}
]
}
],
"aliases": [
"CVE-2025-29780"
],
"database_specific": {
"cwe_ids": [
"CWE-203",
"CWE-208",
"CWE-385"
],
"github_reviewed": true,
"github_reviewed_at": "2025-03-14T19:55:10Z",
"nvd_published_at": "2025-03-14T18:15:32Z",
"severity": "MODERATE"
},
"details": "**Description:**\n\nThe `feldman_vss` library contains timing side-channel vulnerabilities in its matrix operations, specifically within the `_find_secure_pivot` function and potentially other parts of `_secure_matrix_solve`. These vulnerabilities are due to Python\u0027s execution model, which does not guarantee constant-time execution. An attacker with the ability to measure the execution time of these functions (e.g., through repeated calls with carefully crafted inputs) could potentially recover secret information used in the Verifiable Secret Sharing (VSS) scheme.\n\nThe `_find_secure_pivot` function, used during Gaussian elimination in `_secure_matrix_solve`, attempts to find a non-zero pivot element. However, the conditional statement `if matrix[row][col] != 0 and row_random \u003c min_value:` has execution time that depends on the value of `matrix[row][col]`. This timing difference can be exploited by an attacker.\n\nThe `constant_time_compare` function in this file also does not provide a constant-time guarantee.\n\nThis advisory formalizes the timing side-channel vulnerabilities already documented in the library\u0027s \"Known Security Vulnerabilities\" section. The Python implementation of matrix operations in the _find_secure_pivot and _secure_matrix_solve functions cannot guarantee constant-time execution, potentially leaking information about secret polynomial coefficients.\n\nAn attacker with the ability to make precise timing measurements of these operations could potentially extract secret information through statistical analysis of execution times, though practical exploitation would require significant expertise and controlled execution environments.\n\n**Impact:**\n\nSuccessful exploitation of these timing side-channels could allow an attacker to recover secret keys or other sensitive information protected by the VSS scheme. This could lead to a complete compromise of the shared secret.\n\n**References:**\n\n* File: `feldman_vss.py`\n* Function: `_find_secure_pivot`\n* Function: `_secure_matrix_solve`\n* Function: `constant_time_compare`\n* [Timing Attacks on Implementations of Diffie-Hellman, RSA, DSS, and Other Systems (1996)](https://www.rambus.com/wp-content/uploads/2015/08/TimingAttacks.pdf) - A seminal paper on timing attacks.\n* [Side-Channel Attacks](https://en.wikipedia.org/wiki/Side-channel_attack) - Wikipedia article on side-channel attacks.\n\n**Remediation:**\n\nAs acknowledged in the library\u0027s documentation, these vulnerabilities cannot be adequately addressed in pure Python. The advisory recommends:\n\n1. SHORT TERM: Consider using this library only in environments where timing measurements by attackers are infeasible.\n\n2. MEDIUM TERM: Implement your own wrappers around critical operations using constant-time libraries in languages like Rust, Go, or C.\n\n3. LONG TERM: Wait for the planned Rust implementation mentioned in the library documentation that will properly address these issues.\n\nNote that the usage of random.Random() identified in the _refresh_shares_additive function is intentional and secure as documented in the \"False-Positive Vulnerabilities\" section of the code, and should not be considered part of this vulnerability.",
"id": "GHSA-q65w-fg65-79f4",
"modified": "2025-03-19T15:28:08Z",
"published": "2025-03-14T19:55:10Z",
"references": [
{
"type": "WEB",
"url": "https://github.com/DavidOsipov/PostQuantum-Feldman-VSS/security/advisories/GHSA-q65w-fg65-79f4"
},
{
"type": "ADVISORY",
"url": "https://nvd.nist.gov/vuln/detail/CVE-2025-29780"
},
{
"type": "WEB",
"url": "https://en.wikipedia.org/wiki/Side-channel_attack"
},
{
"type": "PACKAGE",
"url": "https://github.com/DavidOsipov/PostQuantum-Feldman-VSS"
},
{
"type": "WEB",
"url": "https://www.rambus.com/wp-content/uploads/2015/08/TimingAttacks.pdf"
}
],
"schema_version": "1.4.0",
"severity": [
{
"score": "CVSS:4.0/AV:L/AC:H/AT:P/PR:L/UI:N/VC:H/VI:L/VA:N/SC:N/SI:N/SA:N",
"type": "CVSS_V4"
}
],
"summary": "Post-Quantum Secure Feldman\u0027s Verifiable Secret Sharing has Timing Side-Channels in Matrix Operations"
}
Sightings
| Author | Source | Type | Date |
|---|
Nomenclature
- Seen: The vulnerability was mentioned, discussed, or seen somewhere by the user.
- Confirmed: The vulnerability is confirmed from an analyst perspective.
- Exploited: This vulnerability was exploited and seen by the user reporting the sighting.
- Patched: This vulnerability was successfully patched by the user reporting the sighting.
- Not exploited: This vulnerability was not exploited or seen by the user reporting the sighting.
- Not confirmed: The user expresses doubt about the veracity of the vulnerability.
- Not patched: This vulnerability was not successfully patched by the user reporting the sighting.