# How can I calculate the feasibility of brute-forcing missing secret shares against the secret checksum?

Secret sharing has the problem of player cheating, where a forged share $$s'_i$$ can be sent to generate a fake secret $$m'$$ during reconstruction (and the cheaters can even collude to generate the real secret $$m$$). The literature covers that issue under the term cheating-detection on the Secret-Sharing researching field. The "naive" solution is to check the reconstruction output against the secret checksum (generated during the sharing phase as $$c = H(m)$$). Other approaches also include Message-Authentication of shares (akin to "signed" JWT tokens).

I'm using a XOR-based secret sharing instead of original Shamir's polynomials (referring to his paper How to share a secret). To make a $$(k, n)$$-threshold scheme, I'm using duplicate XOR-entries during the sharing phase (and eliminating duplicates during the reconstruction). But even with duplicates, it's possible to have missing pieces on the secret reconstruction matrix (assuming both share duplicates are not sent).

Here comes my solution for such problem: just brute-force the missing pieces against the secret checksum. I just want to know how I can make feasible the brute-force with $$k$$ of $$n$$ shares, and infeasible with $$k - 1$$ shares (following the definitions of Shamir's paper). The brute-force can be exponential due the number of combinations (suppose an offset of $$\{1, \ldots, 255\}$$ numbers - an ASCII character space/range without $$0$$ to not mess up the XOR-operation, $$x$$ rows with missing entries means $$255^x$$ to brute-force, that is, I would brute-force every incomplete $$m_i$$ instead of doing $$\oplus$$ on guessed entries missing here).

I know that there are issues regarding dedicated mining hardware (ASICs & FPGAs) as found on the cryptocurrency space, so a Password-Based Key Derivation Function such as Argon2 and Lyra2 could help. My headache and struggle is how to map the exponential curve of brute-forcing to be in pair with the minimum $$k$$ threshold requirement, including the reconstruction matrix duplicates.

Proof-of-work uses a variable difficulty balanced by the active number of mining nodes. Is there any calculations regarding the work needed to find a nonce data matching a specific kind of hash? Here in my case, the hash is fully known and the nonce would be the missing reconstruction matrix entries...

I'm working on this scheme here (disclaimer: I'm not an expert cryptographer). Suppose that:

• $$m$$ is the message secret;
• $$m_i$$ is the character of the secret at position $$i$$;
• $$l = \#m$$ is the secret length;
• $$r$$ is the matrix $$k \times l$$ of random integer numbers $$\{1, \ldots, 255\}$$;
• $$d$$ is the random matrix with some duplicates ($$n \times l$$, for $$n \ge k$$);
• $$s$$ is the matrix of shares with possibly missing pieces (a subset of $$r$$ if we remove the duplicates);
• $$\oplus$$ is the xor operation on integer level (bitwise);
• $$n$$ is the number of shares to generate;
• $$k$$ is the threshold;
• $$c$$ is the privately known checksum of the secret message.

Then, the split/share, for every character $$1 \le i \le l$$ is:

$$m_i = r_{(i,1)} \oplus r_{(i,2)} \oplus \ldots \oplus r_{(i,k)}$$

It's resistant for the plain-text attack and never reuses the values applied on the $$\oplus$$-operation (due the randomness axiom). I have tested this part of the whole idea here: https://gist.github.com/marcoonroad/e9339e462755f868500762ffb1287f90 (note: an insecure and unsafe silly code). So, with that we have:

$$(c, d) \leftarrow {\rm S{\small HARE}}(m, k, n)$$

The dealer $$D$$ would recover her secret key/message by running $${\rm R{\small ECOVER}} (c, s)$$ (which checks if the output message matches the previously generated checksum or fails with an error $$\perp$$). As a side note, I can use this secret checksum to encrypt the shares, every one is a "vertical" vector of the $$d$$ matrix (while the secret characters are $$\oplus$$-applied on "horizontal" vectors), the encrypted shares make it easy for validation of invariants and sort of that.

• The Wikipedia article for Secret Sharing only shows a XOR example of k = n, I'm thinking of how feasible is a XOR where k <= n (e.g, k threshold being 80% of shares). – Marco Aurélio da Silva Apr 20 '19 at 1:22
• The code you quoted appears to encrypt a message with a collection of one-time pads, as in a cipher cascade (and as such its security is determined by the security of Random.bits, which is to say—totally insecure); then, for a reason that's not clear to me, abuses List.sort in an attempt to shuffle them that may backfire because the cmp you passed is not even a function, let alone a total order. How do thresholds figure into it? What is the scheme you're proposing? – Squeamish Ossifrage Apr 20 '19 at 3:21
• That Gist code is just an initial implementation to test, I know that I must use secure and safe PRNGs such as the one implemented by the Nocrypto library (being Fortuna). That sort function is not needed as well too, random numbers are unordered and noisy. I just asking how feasible is to "break"/figure out the shared secret by cryptoanalysis on the missing pieces/shares, and how much time it takes (in the same sense of timed commitment schemes), excluding any possibilities of hash collision. – Marco Aurélio da Silva Apr 20 '19 at 4:51
• Your scheme is kind of confusingly described, but as far as I understand it, it's essentially just the trivial XOR-based secret sharing scheme described on Wikipedia (a.k.a. additive secret sharing in some sources). And that's fundamentally an $n$-out-of-$n$ threshold scheme, meaning that all the $n$ shares are needed to reconstruct the secret, and the lack of even one share renders the secret as hard to guess as if you had no shares of it at all. – Ilmari Karonen Apr 20 '19 at 11:43
• Given your definition of m[i] and Ilmari's comment above, how did you manage to test recover(c, s) if $s \subset r$? – Paul Uszak Apr 20 '19 at 12:39