3 ms·

What a coincidence! I was just browsing the Shamir's Secret Sharing Wikipedia page 30 seconds ago. There is a python implementation on it and I was worried the

What a coincidence! I was just browsing the Shamir's Secret Sharing Wikipedia page 30 seconds ago. There is a python implementation on it and I was worried the same exact thing as you before opening HN. So maybe we could start with that one. Is that code implementation sufficiently secure and well documented? https://en.wikipedia.org/wiki/Shamir's_secret_sharing?wprov=sfti1#Python_code https://en.wikipedia.org/wiki/Shamir's_secret_sharing?wprov=...

some_furry 2y ago
https://zkdocs.com https://zkdocs.com has a whole chapter on Shamir's Secret Sharing. (Ironically, this stuff is documented, cryptographers just aren't good at marketing.) https://www.zkdocs.com/docs/zkdocs/protocol-primitives/shamir/ https://www.zkdocs.com/docs/zkdocs/protocol-primitives/shami...
- unscaled 2y ago
  I think this chapter just proves GP's point, rather than refuting it. It's much cleaner than the Wikipedia article and it mentions the zero share problem, but it doesn't mention any other concern like constant time implementations, cache side channel attacks or the leading zero coefficient that I pointed to at the other post. It's a good guide to learn about Secret Sharing, but it doesn't give you even 1% of what you need to know implement it safely by yourself.
  - some_furry 2y ago
    > or the leading zero coefficient that I pointed to at the other post. That isn't actually a problem, although I've seen a lot of people that think it is. The problem is framed as "if you have a leading zero coefficient, it's equivalent to a threshold of t-1", but you'd need a zero leading coefficient for every polynomial. With a 32 byte secret and GF(2^8), you expect at least 1 leading zero coefficient in 11% of random secrets, but a threshold reduction from t to t-1 only occurs with 2^-256 probability (that is, every leading coefficient has to be 0). You might think you can detect this condition, but SSS is kind of like a one-time pad if you don't have sufficient shares. > it doesn't mention any other concern like constant time implementations, cache side channel attacks These are table stakes for secure cryptography. ZKDocs is a guide to algorithms, not implementations.
cassonmars 2y ago
No, it is not. The arithmetic used is not constant time, meaning the actual computational steps involved leak information about the secret, were either the recombination of the shares or the initial splitting were observed via side channels. The arithmetic does not guard against party identifiers being zero or overflowing to zero, although it is not likely to occur when used this way.
- unscaled 2y ago
  Case in point: http://sbudella.altervista.org/blog/20230330-shamir-timing.html http://sbudella.altervista.org/blog/20230330-shamir-timing.h... I think that specific attack is pretty hard to pull off pratice (in normal scenarios, Vault secret unseals do not happen very often). But it can be a big problem if you were using a scheme where Shamir Secret sharing is used frequently (e.g. it can be triggered by a request sent by the attacker) and (I believe) with different parts of the secret every time. It's probably safer to use an audited library, but here's a library library that has been audited by two firms, and it's still using lookup tables: https://github.com/privy-io/shamir-secret-sharing/blob/main/src/index.ts#L13 https://github.com/privy-io/shamir-secret-sharing/blob/main/... The strangest thing is that the audit report by Cure53 mentions this issue, and says it was fixed, but it doesn't seem fixed (at least not in the way that I would expect and the way that HashiCorp fixed it, which is simply removing the tables and using constant-time math). The library maintainers seem to be very proactive and diligent about fixing other issues[1], so it really is strange. [1] https://privy.io/blog/zero-leading-coefficients-cryptography https://privy.io/blog/zero-leading-coefficients-cryptography

some_furry 2y ago

https://zkdocs.com https://zkdocs.com has a whole chapter on Shamir's Secret Sharing. (Ironically, this stuff is documented, cryptographers just aren't good at marketing.) https://www.zkdocs.com/docs/zkdocs/protocol-primitives/shamir/ https://www.zkdocs.com/docs/zkdocs/protocol-primitives/shami...

unscaled 2y ago
I think this chapter just proves GP's point, rather than refuting it. It's much cleaner than the Wikipedia article and it mentions the zero share problem, but it doesn't mention any other concern like constant time implementations, cache side channel attacks or the leading zero coefficient that I pointed to at the other post. It's a good guide to learn about Secret Sharing, but it doesn't give you even 1% of what you need to know implement it safely by yourself.
- some_furry 2y ago
  > or the leading zero coefficient that I pointed to at the other post. That isn't actually a problem, although I've seen a lot of people that think it is. The problem is framed as "if you have a leading zero coefficient, it's equivalent to a threshold of t-1", but you'd need a zero leading coefficient for every polynomial. With a 32 byte secret and GF(2^8), you expect at least 1 leading zero coefficient in 11% of random secrets, but a threshold reduction from t to t-1 only occurs with 2^-256 probability (that is, every leading coefficient has to be 0). You might think you can detect this condition, but SSS is kind of like a one-time pad if you don't have sufficient shares. > it doesn't mention any other concern like constant time implementations, cache side channel attacks These are table stakes for secure cryptography. ZKDocs is a guide to algorithms, not implementations.

cassonmars 2y ago

No, it is not. The arithmetic used is not constant time, meaning the actual computational steps involved leak information about the secret, were either the recombination of the shares or the initial splitting were observed via side channels. The arithmetic does not guard against party identifiers being zero or overflowing to zero, although it is not likely to occur when used this way.

unscaled 2y ago
Case in point: http://sbudella.altervista.org/blog/20230330-shamir-timing.html http://sbudella.altervista.org/blog/20230330-shamir-timing.h... I think that specific attack is pretty hard to pull off pratice (in normal scenarios, Vault secret unseals do not happen very often). But it can be a big problem if you were using a scheme where Shamir Secret sharing is used frequently (e.g. it can be triggered by a request sent by the attacker) and (I believe) with different parts of the secret every time. It's probably safer to use an audited library, but here's a library library that has been audited by two firms, and it's still using lookup tables: https://github.com/privy-io/shamir-secret-sharing/blob/main/src/index.ts#L13 https://github.com/privy-io/shamir-secret-sharing/blob/main/... The strangest thing is that the audit report by Cure53 mentions this issue, and says it was fixed, but it doesn't seem fixed (at least not in the way that I would expect and the way that HashiCorp fixed it, which is simply removing the tables and using constant-time math). The library maintainers seem to be very proactive and diligent about fixing other issues[1], so it really is strange. [1] https://privy.io/blog/zero-leading-coefficients-cryptography https://privy.io/blog/zero-leading-coefficients-cryptography