Unnecessary ruling out of zero in (CS)PRNG

[scrovy]

Thanks for your implementation. Since this is audited, I'm using it as a basis for a (simplified) Python implementation of my own. Nevertheless I don't understand one thing: why do you restrict the cryptographically secure pseudo-random number generator to spit out non-zero coefficients for the polynomials? This reduces the search space slightly by 1/2^bits for each coefficient (for large bits this is not an issue but it is for small bits (for bits=1 the algorithm would break down completely since the coefficients would always be equal to 1, but fortunately you only allow bits>=3)).

https://github.com/grempe/secrets.js/blob/14a4b682a28242b1dbe5506674b5d5f476b78dbf/secrets.js#L228-L231

Here, the construct function returns null on all-zeros (i.e., the zero vector) https://github.com/grempe/secrets.js/blob/14a4b682a28242b1dbe5506674b5d5f476b78dbf/secrets.js#L252-L255 https://github.com/grempe/secrets.js/blob/14a4b682a28242b1dbe5506674b5d5f476b78dbf/secrets.js#L273-L280

In these two, you keep generating new PRNG numbers until they are not the zero vector. For bits=3 this means that the only coefficients allowed are $1, 2, 3, \ldots, 7 \in GF(8)$, but not 0.

[jeffkitson-music]

@scrovy Did you ever get this solved? Do you have a working version in Python? Is available? Cross-compatibility is important!

[scrovy]

As far as I know it's a non crucial issue, especially for a large number of bits. Typically bits=8 is used. But in principle yes, you should allow $0 \in GF(2^{bits})$ as well.

[poing]

Do you have a working version in Python? Is available? Cross-compatibility is important!

@jeffkitson-music I just finished working on my own cross-compatible port of secrets.js to Python. You can find it here.

[poing]

To answer the non-zero question... I am sure it was a conscious decision.

If random provided $0$ for both coefficients $a_1$ and $a_2$, it could potentially reveal the secret.

$q(x) = a_0 + a1x + \dotsi + a{k-1}x^{k-1}$

$1234 + (0\times 1) + (0\times 1^2) = 1234$ $1234 + (0\times 2) + (0\times 2^2) = 1234$ $1234 + (0\times 3) + (0\times 3^2) = 1234$ $1234 + (0\times x) + (0\times x^2) = 1234$

[scrovy]

What you're saying is that if all the coefficients $a_1, a_2, \ldots, a_k$ are identically zero, then your polynomial is constant hence the share is equal to the secret for any abscissa. Shouldn't then the check be $(a_1, a_2, \ldots, a_k) = 0$, I.e. all the coefficients equal to zero, instead of any coefficient equal to zero? Or is there an additional weakness I'm not seeing where a polynomial of the form $a_0 + a_1 x + a2 x^2 + \ldots + a{k-1} x^{k-1}$ with some of the $a_i, i\geq 1$ but not all of them zero, discloses any information on $a_0$?

[poing]

@scrovy

Dividing a secret into pieces, with the simplified method, without the galileo field $GF(p)$, every $0$ on the right would reduce $k$, reducing the number of shares needed to reconstruct a secret.

$q(x) = a_0 + a_1x + a_2x^2 + a_3x^3 + a_4x^4\implies k=5$ $q(x) = a_0 + a_1x + a_2x^2 + a_3x^3 + 0x^4\implies k=4$ $q(x) = a_0 + a_1x + a_2x^2 + 0x^3 + 0x^4\implies k=3$ $q(x) = a_0 + a_1x + 0x^2 + 0x^3 + 0x^4\implies k=2$ $q(x) = a_0 + 0_1x + 0x^2 + 0x^3 + 0x^4\implies a_0\implies secret$

Interpolation doesn't use $k$, it just derives the values from the shares. It's a reason why for $k=3$, you can combine $3$ or $30$ shares and get the same result. The $0$'s on the right would be canceled out.

With a galileo field $GF(p)$, having a $0$ might not be an issue.
Since the polynomials involved in $k=3$ reconstruction [47, 123, 67] might become a 0, but $GF(p)$ maintain $k=3$, since reconstruction can't determine the value is $0$ without the correct number of shares.

Technically, according to the original paper... the polynomials used for $a1 + \dotsi + a{k-1}$ are supposed to be randomly chosen from a uniform distribution over the integers in $[0,p)$. Which implies $0$ would be valid.

$f(x_0)\implies (x_0, y_0)\implies D_0\implies a_0\implies secret$

Because $0$ implies the $secret$, using $(1,p)$ for random integers seems to be a safer path.