Score:1

Time complexity of a brute force attack on Shamir's Secret Sharing SSS

in flag

I have searched everywhere in academic papers about time complexity of a brute force attack on a Shamir's Secret Sharing key. I'm confused between if it is $O(p^k)$ or $O(p)$, such that $p$ is the modulo of encryption and $k-1$ is the degree of the encryption polynome. Because practically, if we're going to rebuild the polynome of encryption, it's equivalent to brute forcing all $p$ possible values for the $k$ coeficients, which leads to an $O(p^k)$ algorithm. But searching directly the secret which is the constant coefficient of the polynome, and knowing that $S<p$, leads to an $O(p)$ algorithm. Could anyone tell me please what's the right one, and if it is $O(p^k)$, why the linear algorithm doesn't work ?

Score:3
my flag

I have searched everywhere in academic papers about time complexity of a brute force attack on a Shamir's Secret Sharing key.

A brute force attack isn't possible; even if you could perform any arbitrary computation, with $k-1$ shares, you still would not obtain any information on the secret (assuming that randomness was used to generate the shares; if they were generated via a deterministic random number generator, you could).

Because practically, if we're going to rebuild the polynome of encryption, it's equivalent to brute forcing all $p$ possible values for the $k$ coeficients, which leads to an $O(p^k)$ algorithm.

No, even that doesn't work, because there's no way to determine whether you found the correct polynomial; for any possible value of the secret, there is an equal number of polynomials that are consistent with it. Hence, you obtain no information (even probabilistic information) about the secret.

hambam avatar
in flag
thanks for the fast answer ! but I found here [link] (https://www.ijcaonline.org/archives/volume155/number13/kannan-2016-ijca-912051.pdf) that *The value of p should not be too small or it could be susceptible to brute-force attack. If the value of p is 128 bits then this provides 2^128 possible values, which is a range too large for brute force to ever attempt*. What does it mean then ?
Aman Grewal avatar
gb flag
If there's some way to verify the secret, it can be brute-forced, but that's not really attacking SSS.
hambam avatar
in flag
@AmanGrewal so that means that attacking SSS is equivalent to rebuilding the polynomial used in encryption and not only refinding the secret ?
poncho avatar
my flag
@HamzaBa-mohammed: that comment you found is wrong
poncho avatar
my flag
@AmanGrewal: "if there's some way to verify the secret"; well, yes, if you can search through all possible secret values, and detect which is the right one, yes, you can learn it. However, you're not using the shares; they don't give you any information that you didn't already have
mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.