Discussion:
Satoshilabs secret shared private key scheme
(too old to reply)
Ondřej Vejpustek via bitcoin-dev
2018-01-17 11:39:42 UTC
Permalink
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
Russell O'Connor via bitcoin-dev
2018-01-17 15:28:15 UTC
Permalink
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 <
Post by Ondřej Vejpustek via bitcoin-dev
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
* 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).
* 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
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
Gregory Maxwell via bitcoin-dev
2018-01-17 15:36:25 UTC
Permalink
On Wed, Jan 17, 2018 at 3:28 PM, Russell O'Connor via bitcoin-dev
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).
Gregory Maxwell via bitcoin-dev
2018-01-17 15:31:44 UTC
Permalink
On Wed, Jan 17, 2018 at 11:39 AM, Ondřej Vejpustek via bitcoin-dev
Post by Ondřej Vejpustek via bitcoin-dev
* 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.
Post by Ondřej Vejpustek via bitcoin-dev
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.
Post by Ondřej Vejpustek via bitcoin-dev
* 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).
Matt Corallo via bitcoin-dev
2018-01-18 05:00:28 UTC
Permalink
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
Post by Gregory Maxwell via bitcoin-dev
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).
Gregory Maxwell via bitcoin-dev
2018-01-18 14:34:24 UTC
Permalink
On Thu, Jan 18, 2018 at 1:50 PM, Ondřej Vejpustek
(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.
Ondřej Vejpustek via bitcoin-dev
2018-01-18 16:59:09 UTC
Permalink
Post by Gregory Maxwell via bitcoin-dev
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.
Post by Gregory Maxwell via bitcoin-dev
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.
Gregory Maxwell via bitcoin-dev
2018-01-18 18:58:14 UTC
Permalink
On Thu, Jan 18, 2018 at 4:59 PM, Ondřej Vejpustek
Post by Ondřej Vejpustek via bitcoin-dev
Post by Gregory Maxwell via bitcoin-dev
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.
Post by Ondřej Vejpustek via bitcoin-dev
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.
Ondřej Vejpustek via bitcoin-dev
2018-01-22 15:00:25 UTC
Permalink
Post by Gregory Maxwell via bitcoin-dev
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.
Post by Gregory Maxwell via bitcoin-dev
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)?
Russell O'Connor via bitcoin-dev
2018-01-22 19:21:14 UTC
Permalink
On Thu, Jan 18, 2018 at 1:58 PM, Gregory Maxwell via bitcoin-dev <
On Thu, Jan 18, 2018 at 4:59 PM, Ondřej Vejpustek
Post by Ondřej Vejpustek via bitcoin-dev
Post by Gregory Maxwell via bitcoin-dev
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.
Post by Ondřej Vejpustek via bitcoin-dev
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.)
Gregory Maxwell via bitcoin-dev
2018-01-23 01:05:44 UTC
Permalink
On Mon, Jan 22, 2018 at 7:21 PM, Russell O'Connor
Post by Russell O'Connor via bitcoin-dev
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".
Ondřej Vejpustek via bitcoin-dev
2018-01-23 13:54:48 UTC
Permalink
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.
Adam Back via bitcoin-dev
2018-01-23 14:16:22 UTC
Permalink
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
Post by Ondřej Vejpustek via bitcoin-dev
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.
(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
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
Loading...