- Reported
-
- Issued
-
- Package
-
sharks
(crates.io)
- Type
-
Vulnerability
- Categories
-
- Keywords
-
#shamir
#cryptography
#sss
- References
-
- Patched
-
no patched versions
Description
Affected versions of this crate allowed for a bias when generating random
polynomials for Shamir Secret Sharing, where instead of being within the range
[0, 255] they were instead in the range [1, 255]. A description from
Cure53, who originally found the issue, is available:
The correct method to select a random polynomial would be to select
all coefficients (including the most significant coefficient) uniformly
in the range 0..255 (inclusive). Otherwise, knowledge that a coefficient
in a polynomial cannot be 0 permits the exclusion of single byte values
for the shared secret given one share less than required. [...]
Exploiting this weakness necessitates sharing the same secret multiple
times. In this scenario, an attacker could exclude an exponential number
of values for each of the shared bytes until sufficiently few values
remain for brute forcing. Cure53 estimates that under ideal
circumstances (e.g., a 2-out-of-N scheme) a shared secret can be
reconstructed if the same secret has been distributed 500-1500 times.
Secrets that have been shared a low amount of times (ideally, once) would not
be impacted. However, secrets that are repeatedly shared may be vulnerable,
especially if the shares are still available, and should be rotated.
The vulnerability does not impact reconstitution of secrets: secrets that have
already been split can be recombined without issue.
The flaw can be corrected by changing the lower bound of the polynomial
coefficient range in the sharks::math::random_polynomial function to 0. The
blahaj crate has been made available with a fixed version of the code, after
attempts to reach the maintainer of the sharks crate were unsuccessful.
Advisory available under CC0-1.0
license.