Generation of polynomial coefficients in Sharmir's secret sharing

[onvej-sl]

Summary

I found a vulnerability in the implementation of Shamir's secret sharing scheme. The vulnerability allows an attacker to recover the mnemonic if the attacker knows t' out of t needed shares provided

1. t - t' is low and
2. t is high.

For example, the entropy of the secret is reduced by half if t' = 15 and t = 16. The vulnerability is due to the way the random numbers are generated.

Introduction

Shamir secret sharing

Shamir secret sharing scheme allows you to split a secret into n shares such that every t shares can be used to reconstruct the secret. The scheme makes use of Lagrange interpolation theorem that says that given t points in the plane (such that no two points has the same x coordinate) there exists exactly one polynomial that goes through the points. The secret is represented by the constant term of a degree t - 1 polynomial and the shares are represented by the points in the plane. Any t points are enough to reconstruct the polynomial and thus the secret.

Polynomial generation

Let me summarize how the shares are generated in your implementation. Suppose we have a one-byte secret s that we want to split into n shares such that each t (but no t-1) shares is enough to reconstruct the secret. The process is the following:

1. Let p be a polynomial of degree t - 1 over GF(256) such that 1.1. its constant coefficient is s and 1.2. the remaining t - 1 coefficients are generated uniformly at random from GF(256).
2. Let x_1, ..., x_n be a list of pairwise distinct non-zero elements from GF(256).
3. For each i in 1, ..., n let y_i be p(x_i) (evaluated in GF(256)).
4. The shares are (x_1, y_1), ..., (x_n, y_n).

When the secret has multiple bytes, the polynomial is generated independently for each byte, but x_1, ..., x_n are the same for each polynomial.

Vulnerability

Coefficients generation

The vulnerability lies in the fact that the coefficients aren't generated uniformly at random from GF(256). This is how a coefficient c is generated:

    a = random.SystemRandom().randint(0, 255)
    i = int((time.time() % 0.0001) * 1000000) + 1
    c = (a * i) % 255

In the language of mathematics:

1. a is drawn uniformly at random from 0, ..., 255.
2. i is drawn from 1, ..., 100. Although it is not drawn uniformly at random, for the sake of simplicity let's suppose it is.
3. The coefficient is a * i % 255.

The procedure suffers from the following two vulnerabilities:

1. The coefficient is never 255.
2. The result of (a * i) % 255 is not uniformly distributed over 1, ..., 254.

First vulnerability

Since the coefficient is the remainder of a * i after division by 255, the coefficient is never 255. That means the coefficient is not generated uniformly.

Let's turn this vulnerability into an attack. Assume an attacker knows t - 1 shares out of t shares needed to reconstruct a one-byte secret. The attacker guesses the remaining share and reconstructs the polynomial. If the guess is correct, no polynomial coefficient except for the constant one is equal to 255. In other words, if the polynomial has a coefficient except for the constant one that is equal to 255, the guess is incorrect. The probability that no coefficient is equal to 255 provided the guess is incorrect is (255 / 256) ^ (t - 1). That means the attacker is able eliminate at average 256 * (255 / 256) ^ (t - 1) out of 256 possible guesses. In other words, the entropy of the one-byte secret is lowered by (t - 1) * log2(256 / 255) bits.

Since the individual bytes of a multiple-byte secret are shared separately, the entropy of a l-bit secret is lowered by l / 8 * (t - 1) * log2(256 / 255) bits. Even if there where as much as 256 shares, the entropy of a 128-bit secret would be reduced to 105 bits, which is not so bad.

Second vulnerability

Multiplication modulo a non-prime number is a tricky operation, since the function that maps x to x * y % m is a permutation of the set {1, ..., m - 1} if and only if y is relative prime to m. Consequently, even if both x and y are generated uniformly at random from the set {1, ..., m - 1}, the result of the operation x * y % m isn't uniformly distributed over {1, ..., m - 1} unless m is a prime.

Suppose for example that m = 6 and x, y are distributed uniformly on the set {1, ..., 6}. This is the multiplication table x, y -> x * y % 6:

y/x	1	2	3	4	5
1	1	2	3	4	5
2	2	4	0	2	4
3	3	0	3	0	3
4	4	2	4	2	4
5	5	4	3	2	1

The probability distribution of the result is:

x * y % m	0	1	2	3	4	5
probability	0.16	0.08	0.24	0.20	0.24	0.08

Not only is the result not uniformly distributed, it's not even distributed over {1, ..., m -1}!

It can be calculated that the entropy of a coefficient generated by your implementation is about 7.72 bits. Although it seems to be sufficient, the conditional entropy of a secret provided the attacker knows t - 1 out of t needed shares decreases as t increases.

First, suppose the secret has a single byte. The attacker guesses the remaining share and reconstructs the polynomial. If the guess is correct, each coefficient of the polynomial but the constant one follows the distribution with the entropy of 7.72 bits. If the guess is not correct, the coefficients are distributed approximately uniformly. Based on this fact, the attacker is able to calculate for each guess the probability that the guess is correct. These probabilities define a probability distribution of the secret. The key question is: What is the entropy of the distribution?

I wrote a program that approximates the entropy using Monte Carlo simulation. The following graph shows the dependency between t and the entropy of a single byte secret conditioned on the knowledge of t - 1 out of t needed shares: Note that the graph is jagged, this is because the simulation approximates (rather than calculates) the entropy.

Without proof, this is an upper bound for the entropy of a single byte secret conditioned on the kowledge of t' out of t needed shares:

Now, suppose the secret has multiple bytes. Since the individual bytes of the secret are independent, the entropy of the whole secret is the sum of the entropies of the individual bytes. This is a bit more complicated from the attacker's perspective. The attacker is able to compute a probability distribution for every single byte of the secret. The complexity of such the computation is linear in the length of the secret. Since the individual bytes of the secret are independent, the probability of a secret is the product of the probabilities of the individual bytes. The attacker now tries to guess the secret starting from the most probable one. This is the trickiest part, since the attacker cannot enumerate all the secrets. The smaller the entropy of the secret, the sooner the attack succeeds.

[4tochka]

Good job, report is accepted as significant implementation bug. You will be paid 0.2 BTC as reward. Please specify your Bitcoin address. Are you going to visit ZeroNights conference on 25 august?

[onvej-sl]

Good job, report is accepted as significant implementation bug. You will be paid 0.2 BTC as reward. Please specify your Bitcoin address.

That's kind of you. I sent you GPG signed e-mail with the address. This is the fingerprint of my public key: 3266 AF27 2D90 E4D2 A1B0 E000 C520 534E E2B9 CD3F

Are you going to visit ZeroNights conference on 25 august?

Nope.

[onvej-sl]

I received the reward, thanks!

[4tochka]

Bug fixed:

https://github.com/bitaps-com/pybtc/blob/master/pybtc/functions/shamir.py#L114 https://github.com/bitaps-com/pybtc/blob/master/pybtc/functions/entropy.py#L5

NIST Randomnes tests on the fly added: https://github.com/bitaps-com/pybtc/blob/master/pybtc/functions/entropy.py#L111