Satoshilabs secret shared private key scheme
14 messages, 17 to 23 Jan 2018. Started by Ondřej Vejpustek.
Ondřej Vejpustek (5), Gregory Maxwell (5), Russell O'Connor (2), Matt Corallo, Adam Back
The entropy argument is as follows:
There is a rule of thumb which says it is safer plaintext to have low redundancy, see https://en.wikipedia.org/wiki/Redundancy_(information_theory), i. e. it's better to encrypt random or compressed data than natural language. This rule is based on Shannon's information theory which means that a breach of the rule usually doesn't induce a vulnerability (there is no known generic attack). This rule is application of a precautionary principle.
Nevertheless, here are some examples of cryptographic attacks which may be considered as a consequence of the breach of the rule: * Related Message Attack by Coppersmith, Franklin, Patarin, Reiter (https://pdfs.semanticscholar.org/899a/4fdc048102471875e24f7fecb3fb8998d754.pdf) - given RSA ciphertext of two plaintexts x and a*x + b, where a, b are known, it's possible to effectively compute x provided public exponent is three. From the informaton-theoretic point of view the second message is redundant, because it's determined by the first one. Which means that relative redundancy of both messages is at least one half. * Stereotyped Messages by Coppersmith (https://www.di.ens.fr/~fouque/ens-rennes/coppersmith.pdf, section 7) - given RSA ciphertext and (1-1/e) fraction of plaintext (where e is public exponent), it's possible to effectively compute x. Message is highly redundant, because only 1/e of the message is unknown. Relative redundancy of the message is at least (1-1/e).
Consider a few notes: * Nowadays there exists more complicated variants of mentioned attacks which have weaker premisses. * There is a considerable similarity between RSA and SSS. Both schemes are algebraically-based (rather than boolean function based). * CRCs (and error-correcting codes generally) introduce redundancy into the message. Moreover the redundancy is induced by a linear relationship among message (compare with the premise of the Related Message Attack). * Related Message Attack wouldn't be possible if you had two plaintexts x and hash(x). The relationship between messages has to be (algebraically) uncomplicated. From the information-theoretic point of view the situation is the same, but from the practical point of view it is completely different.
To sum it up, there is a precautionary principle which tells us not to increase redundancy of a message unless it is introduced in a complicated way (for example by a hash function). That's why we use SHA rather than CRC. One more reason why we stick to the principle is that there's no randomisation in our scheme (such as padding or initialisation vector). We understood advantages of error-correctings codes over hash functions (minimal codewords distance property, performance) and we considered it thoroughly.
Ondřej Vejpustek
Hi Ondřej,
1. There is no similarity between SSS and RSA or any other public-key or symmetric crypto. SSS is effectively a one-time pad and is information-theoretically secure.
2. Even if there were a problem (which there cannot be, due to (1)), using error correcting codes and truncated hash functions create identical amounts of information theoretic redundancy.
Let me repeat that SSS is "information-theoretically secure"! It isn't only computationally infeasible to break SSS; it is impossible to break SSS. If you have all but one necessary share of SSS, there is no information leaked about the the hidden data, because for every possible message that could be encoded, there exists some final share that would decode to that message. Any of the possibilities for the missing final share are equally as likely.
It is of no use to apply the precautionary principle against impossible attacks, especially at the cost of losing the useful properties of a real error correcting codes that would provide actual guarantees against likely errors.
On Wed, Jan 17, 2018 at 6:39 AM, Ondřej Vejpustek via bitcoin-dev < bitcoin-dev@lists•linuxfoundation•org> wrote:
Quoted text (58 lines)
> The entropy argument is as follows: > > There is a rule of thumb which says it is safer plaintext to have low > redundancy, see > https://en.wikipedia.org/wiki/Redundancy_(information_theory), i. e. > it's better to encrypt random or compressed data than natural language. > This rule is based on Shannon's information theory which means that a > breach of the rule usually doesn't induce a vulnerability (there is no > known generic attack). This rule is application of a precautionary > principle. > > Nevertheless, here are some examples of cryptographic attacks which may > be considered as a consequence of the breach of the rule: > * Related Message Attack by Coppersmith, Franklin, Patarin, Reiter > (https://pdfs.semanticscholar.org/899a/4fdc048102471875e24f7fecb3fb89 > 98d754.pdf) > - given RSA ciphertext of two plaintexts x and a*x + b, where a, b are > known, it's possible to effectively compute x provided public exponent > is three. From the informaton-theoretic point of view the second message > is redundant, because it's determined by the first one. Which means that > relative redundancy of both messages is at least one half. > * Stereotyped Messages by Coppersmith > (https://www.di.ens.fr/~fouque/ens-rennes/coppersmith.pdf, section 7) - > given RSA ciphertext and (1-1/e) fraction of plaintext (where e is > public exponent), it's possible to effectively compute x. Message is > highly redundant, because only 1/e of the message is unknown. Relative > redundancy of the message is at least (1-1/e). > > Consider a few notes: > * Nowadays there exists more complicated variants of mentioned attacks > which have weaker premisses. > * There is a considerable similarity between RSA and SSS. Both schemes > are algebraically-based (rather than boolean function based). > * CRCs (and error-correcting codes generally) introduce redundancy > into the message. Moreover the redundancy is induced by a linear > relationship among message (compare with the premise of the Related > Message Attack). > * Related Message Attack wouldn't be possible if you had two > plaintexts x and hash(x). The relationship between messages has to be > (algebraically) uncomplicated. From the information-theoretic point of > view the situation is the same, but from the practical point of view it > is completely different. > > To sum it up, there is a precautionary principle which tells us not to > increase redundancy of a message unless it is introduced in a > complicated way (for example by a hash function). That's why we use SHA > rather than CRC. One more reason why we stick to the principle is that > there's no randomisation in our scheme (such as padding or > initialisation vector). We understood advantages of error-correctings > codes over hash functions (minimal codewords distance property, > performance) and we considered it thoroughly. > > Ondřej Vejpustek > _______________________________________________ > bitcoin-dev mailing list > bitcoin-dev@lists•linuxfoundation•org > https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev >
On Wed, Jan 17, 2018 at 11:39 AM, Ondřej Vejpustek via bitcoin-dev <bitcoin-dev@lists•linuxfoundation•org> wrote:
Quoted text (5 lines)
> Consider a few notes: > * Nowadays there exists more complicated variants of mentioned attacks > which have weaker premisses. > * There is a considerable similarity between RSA and SSS. Both schemes > are algebraically-based (rather than boolean function based).
I'm sorry but I must not be following your message. I read the above as "these are similar because they are based on math"...
Shamir secret sharing, correctly implemented (which indeed seems to be many parties problem...) achieves information theoretic security. In this critical sense it is utterly unrelated to RSA.
In fact this applies generally given any fixed threashold-1 set of shares there is an value of the final remaining share which decodes to every possible message. So without knowing of an extra share you know nothing of the message.
The simplest demonstration is the 2 of 2 case, which can most simply be constructed over GF(2) as in the traditional "one time pad": message = share1 xor share2. For any given share1 or given share2 there exist a value of share2 or share1 respectively which yields every possible message.
If the generalization isn't obvious, it might be helpful to make a little test utility that tries all possible one byte messages with all possible share values using the GF(256) sharing scheme proposed in the draft-- in this case information theory is why we can know SSS (and similar) have (within their limited scope) _perfect_ security, rather than it being a reason to speculate that they might not turn out to be secure at all. (or, instead of a test utility just work through some examples on paper in a small field).
This doesn't change when you add additional conditionals on it-- e.g. Say you a 2-of-3 sharing where you have your choice of any of the three shares but do not know the others and assume you know every bit of the plaintext save one bit or any linear or non-linear relationship between plaintext bits (excepting for actually knowing the secret)...
In these case there can still be no attack arising out of this charitably bad plaintext structure because-- as pointed out above-- all possible plaintexts are equal-probable you know nothing of which of the two possible solutions is correct without knowing about the other shares because for each possible value there exists a value for the unknown shares which would cause that decoding-- there is no leakage at all, the share doesn't teach you anything you didn't already know.
In my view any SSS tool should also include a forgery utility which demonstrates this property, both as a critical test-- but also because being able to forge an alternative answer to deceive an attacker which has compromised some of your shares is one of the (at least theoretical) arguments for using SSS over computational secret sharing.
Quoted text (1 line)
> unless it is introduced in a complicated way
Complicated does not mean secure. And from an information theoretic perspective the hash does almost nothing (other then some small destruction of entropy due to its lack of perfect uniformity which is information theoretically equivalent to using a smaller perfect code). There are many cases where I too am more comfortable using a hash -- where it may destroy some structure which I cannot _prove_ would be safe to retain, but this is not one of those cases.
Quoted text (1 line)
> * CRCs (and error-correcting codes generally) introduce redundancy
into the message
The discussion of using a proper code was primarily related to the outer check value which protects the shares themselves and is sitting unprotected in plaintext; not so much the one inside the sharing in any case; since its the outer one which could be structured to provide perfect detection of errors that align with words (e.g. transposing two words).
On Wed, Jan 17, 2018 at 3:28 PM, Russell O'Connor via bitcoin-dev <bitcoin-dev@lists•linuxfoundation•org> wrote:
Quoted text (1 line)
> it is impossible to break SSS.
Obligatory repeated point: if the scheme being used actually is SSS and not a Shamir-Shaped-Sharing instead. This should go without mention by my experience is that a great many things which claim to be SSS aren't. Sometimes precisely because they stuck in some hashes in arbitrary places and destroyed the properties (in fact, the really old broken armory implementation effectively did that, and in fact resulted in a real weakness not just a theoretical one).
Or make it a part of your secret-split logic... Gotta love how fast GF(2^8) is: https://github.com/TheBlueMatt/shamirs/blob/master/main.c#L57
On January 17, 2018 3:31:44 PM UTC, Gregory Maxwell via bitcoin-dev <bitcoin-dev@lists•linuxfoundation•org> wrote:
Quoted text (9 lines)
>If the generalization isn't obvious, it might be helpful to make a >little test utility that tries all possible one byte messages with all >possible share values using the GF(256) sharing scheme proposed in the >draft-- in this case information theory is why we can know SSS (and >similar) have (within their limited scope) _perfect_ security, rather >than it being a reason to speculate that they might not turn out to be >secure at all. (or, instead of a test utility just work through some >examples on paper in a small field). >
Thank you for your comments, Gregory and Russell!
Gregory, thank you for you explanation of perfect secrecy, there is no need for that, however. I'm professional mathematician and cryptographer.
Quoted text (2 lines)
> I read the above > as "these are similar because they are based on math"...
They are based on algebra (group and commutative ring theory), which is a great similarity. RSA and SHA, for example, are based on completely distinct parts of mathematics.
Quoted text (5 lines)
> Complicated does not mean secure. And from an information theoretic > perspective the hash does almost nothing (other then some small > destruction of entropy due to its lack of perfect uniformity which is > information theoretically equivalent to using a smaller perfect code). > using error correcting codes and truncated hash functions create
identical amounts of information theoretic redundancy I agree, see my last note in the previous mail. Adding redundancy by a hash function is more secure than adding redundancy by a linear relations. Just my opinion.
I see the difference between RSA and SSS you mentioned and I understand your arguments about perfect secrecy. Just two comments: (1) Our proposal doesn't use SSS for the whole secret, but it divides the secret into bytes and uses SSS for every byte separately. This scheme is weaker because to reconstruct n-th byte it suffices to have n-th bytes from k shares. (2) SSS is information-theoretic secure if you know k-1 or less shares, where k is the threshold. But the proof doesn't hold if you know for example a small part of every share.
Quoted text (1 line)
> It is of no use to apply the precautionary principle against
impossible attacks, especially at the cost of losing the useful properties of a real error correcting codes that would provide actual guarantees against likely errors. The discussion isn't about mathematics or about security proofs but about cryptographic scheme design. In our use case you cannot assume that all premises of security proof theorems (including SSS's perfect secrecy) hold true (see the comment above).
In my opinion, to make a cryptographic scheme more robust it's better to stick to general "intuitive" principles. Of course you have to consider the advantages and disadvantages of this approach. That's why we disclosed our draft and welcome all comments.
Quoted text (3 lines)
> The discussion of using a proper code was primarily related to the > outer check value which protects the shares themselves and is sitting > unprotected in plaintext
OK then. I was defending the hash in the inner check value.
On Thu, Jan 18, 2018 at 1:50 PM, Ondřej Vejpustek <ondrej.vejpustek@satoshilabs•com> wrote:
Quoted text (4 lines)
> (1) Our proposal doesn't use SSS for the whole secret, but it divides > the secret into bytes and uses SSS for every byte separately. This > scheme is weaker because to reconstruct n-th byte it suffices to have > n-th bytes from k shares.
If being secure against partial share leakage is really part of your threat model the current proposal is gratuitously insecure against it. And the choice of check algorithm really doesn't matter for that.
For example, in a 2-of-3 share say I have the first half of shares 1,2 and the second half of shares 2,3 with the current proposal the secret is directly revealed, even though I didn't have any single complete share.
If partial share disclosure were an actual concern, I would recommend that after sharing and before encoding for transmission (e.g. before applying check values and word encoding to the share) the individual shares be passed through a large block unkeyed cryptographic permutation. Under reasonable-ish assumptions about the difficulty of inverting the permutation with partial knowledge, this transformation would prevent attacks from leaks of partial share information.
Quoted text (2 lines)
> If being secure against partial share leakage is really part of your > threat model the current proposal is gratuitously insecure against it.
I don't think that is true. Shared secret is an input of KDF which should prevent this kind of attack.
Quoted text (7 lines)
> If partial share disclosure were an actual concern, I would recommend > that after sharing and before encoding for transmission (e.g. before > applying check values and word encoding to the share) the individual > shares be passed through a large block unkeyed cryptographic > permutation. Under reasonable-ish assumptions about the difficulty of > inverting the permutation with partial knowledge, this transformation > would prevent attacks from leaks of partial share information.
Actually, we've been considering something like that. We concluded that it is to much "rolling your own crypto". Instead of diffusion layer we decided to apply KDF on the shared secret.
On Thu, Jan 18, 2018 at 4:59 PM, Ondřej Vejpustek <ondrej.vejpustek@satoshilabs•com> wrote:
Quoted text (5 lines)
>> If being secure against partial share leakage is really part of your >> threat model the current proposal is gratuitously insecure against it. > > I don't think that is true. Shared secret is an input of KDF which > should prevent this kind of attack.
My post provided a concrete example. I'd be happy to answer any questions about it, but otherwise I'm not sure how to make it more clear.
Quoted text (1 line)
> Actually, we've been considering something like that. We concluded that it is to much "rolling your own crypto". Instead of diffusion layer we decided to apply KDF on the shared secret.
Quite the opposite-- a large block cipher is a standard construction... and the off-label application of a KDF that you've used here doesn't provide any protection against the example I gave.
Quoted text (4 lines)
> > My post provided a concrete example. I'd be happy to answer any > questions about it, but otherwise I'm not sure how to make it more > clear.
My apologies, I didn't read it carefully. You are absolutely right. Our scheme doesn't protect against the scenario.
Quoted text (2 lines)
> Quite the opposite-- a large block cipher is a standard > construction
I'm happy to hear it. Nevertheless, I didn't find any standartisation or implementation of the CMC mode (excluding the paper).
Do you have some experience with other modes (such as HCTR, HEH)?
On Thu, Jan 18, 2018 at 1:58 PM, Gregory Maxwell via bitcoin-dev < bitcoin-dev@lists•linuxfoundation•org> wrote:
Quoted text (21 lines)
> On Thu, Jan 18, 2018 at 4:59 PM, Ondřej Vejpustek > <ondrej.vejpustek@satoshilabs•com> wrote: > >> If being secure against partial share leakage is really part of your > >> threat model the current proposal is gratuitously insecure against it. > > > > I don't think that is true. Shared secret is an input of KDF which > > should prevent this kind of attack. > > My post provided a concrete example. I'd be happy to answer any > questions about it, but otherwise I'm not sure how to make it more > clear. > > > Actually, we've been considering something like that. We concluded that > it is to much "rolling your own crypto". Instead of diffusion layer we > decided to apply KDF on the shared secret. > > > Quite the opposite-- a large block cipher is a standard > construction... and the off-label application of a KDF that you've > used here doesn't provide any protection against the example I gave. >
At this point, is it better just to use GF(2^256+n)? Is GF(2^256+n) going to be that much slower than GF(2^8) that we care to make things this complicated? (I honestly don't know the answer.)
On Mon, Jan 22, 2018 at 7:21 PM, Russell O'Connor <roconnor@blockstream•io> wrote:
Quoted text (3 lines)
> At this point, is it better just to use GF(2^256+n)? Is GF(2^256+n) going > to be that much slower than GF(2^8) that we care to make things this > complicated? (I honestly don't know the answer.)
I expect it would be especially since operations must be implemented in sidechannel resistant manners.
Also, binary extension fields are doing to have linear subgroup properties where leaking part of elements wouldn't be good. Not as obviously broken as the example I gave above, but still in the domain of "get chunks of a lot of a supra threshold set of shares, and setup a latices basis problem that can provide an efficient subspace to search".
Quoted text (2 lines)
> Yes, this scheme. > https://bitcointalk.org/index.php?topic=311000.msg3342217#msg3342217
In addition to the scheme, I found out, that Makwa (https://www.bolet.org/makwa/), a hashing function which received a special recognition in the Password Hashing Competition, supports a delegation. In fact, Makwa is similar to the suggested scheme.
Unfortunately, both schemes have two drawbacks: (1) There is no proof that the host computes what he's suppose to do. (2) The delegation is far more slower than the normal computation. According to the Makwa paper (https://www.bolet.org/makwa/makwa-spec-20150422.pdf) the delegation is typically 100 to 1000 slower. So I see little advantage in delegating.
I doubt there is a scheme that suits our needs.
Makwa sites [1] https://bitcointalk.org/index.php?topic=311000.0
Seems like they independently rediscovered it.
Adam
On 23 January 2018 at 05:54, Ondřej Vejpustek via bitcoin-dev <bitcoin-dev@lists•linuxfoundation•org> wrote:
Quoted text (20 lines)
>> Yes, this scheme. >> https://bitcointalk.org/index.php?topic=311000.msg3342217#msg3342217 > > In addition to the scheme, I found out, that Makwa > (https://www.bolet.org/makwa/), a hashing function which received a > special recognition in the Password Hashing Competition, supports a > delegation. In fact, Makwa is similar to the suggested scheme. > > Unfortunately, both schemes have two drawbacks: > (1) There is no proof that the host computes what he's suppose to do. > (2) The delegation is far more slower than the normal computation. > According to the Makwa paper > (https://www.bolet.org/makwa/makwa-spec-20150422.pdf) the delegation is > typically 100 to 1000 slower. So I see little advantage in delegating. > > I doubt there is a scheme that suits our needs. > _______________________________________________ > bitcoin-dev mailing list > bitcoin-dev@lists•linuxfoundation•org > https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev