From: Gregory Maxwell <greg@xiph•org>
To: "Ondřej Vejpustek" <ondrej.vejpustek@satoshilabs•com>,
"Bitcoin Protocol Discussion"
<bitcoin-dev@lists•linuxfoundation.org>
Subject: Re: [bitcoin-dev] Satoshilabs secret shared private key scheme
Date: Wed, 17 Jan 2018 15:31:44 +0000 [thread overview]
Message-ID: <CAAS2fgRQk4EUp6FO2f+RkJpDTyZX0N4=uGp7ZF=0aUchZX8hSA@mail.gmail.com> (raw)
In-Reply-To: <51280a45-f86b-3191-d55e-f34e880c1da8@satoshilabs.com>
On Wed, Jan 17, 2018 at 11:39 AM, Ondřej Vejpustek via bitcoin-dev
<bitcoin-dev@lists•linuxfoundation.org> wrote:
> 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.
> 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.
> * 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).
next prev parent reply other threads:[~2018-01-17 15:31 UTC|newest]
Thread overview: 32+ messages / expand[flat|nested] mbox.gz Atom feed top
2018-01-17 11:39 Ondřej Vejpustek
2018-01-17 15:28 ` Russell O'Connor
2018-01-17 15:36 ` Gregory Maxwell
2018-01-17 15:31 ` Gregory Maxwell [this message]
2018-01-18 5:00 ` Matt Corallo
2018-01-18 13:50 ` Ondřej Vejpustek
2018-01-18 14:34 ` Gregory Maxwell
2018-01-18 16:59 ` Ondřej Vejpustek
2018-01-18 18:58 ` Gregory Maxwell
2018-01-22 15:00 ` Ondřej Vejpustek
2018-01-22 19:21 ` Russell O'Connor
2018-01-23 1:05 ` Gregory Maxwell
2018-01-23 13:54 ` Ondřej Vejpustek
2018-01-23 14:16 ` Adam Back
-- strict thread matches above, loose matches on Subject: below --
2018-01-08 4:22 Gregory Maxwell
2018-01-08 6:33 ` nullius
2018-01-08 12:39 ` Pavol Rusnak
2018-01-08 12:45 ` Peter Todd
2018-01-08 13:00 ` Pavol Rusnak
2018-01-08 19:37 ` Peter Todd
2018-01-08 22:26 ` Ben Kloester
2018-01-09 0:37 ` Peter Todd
2018-01-08 23:47 ` Gregory Maxwell
2018-01-09 0:40 ` Rhavar
2018-01-09 1:13 ` Peter Todd
2018-01-09 12:44 ` jens
[not found] ` <274aad5c-4573-2fdd-f8b0-c6c2d662ab7c@gibsonic.org>
2018-01-12 9:50 ` Peter Todd
2018-01-09 15:12 ` Pavol Rusnak
2018-01-10 20:28 ` Pavol Rusnak
2018-01-10 23:47 ` Gregory Maxwell
2018-01-11 9:55 ` Pavol Rusnak
2018-01-09 16:20 ` Russell O'Connor
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to='CAAS2fgRQk4EUp6FO2f+RkJpDTyZX0N4=uGp7ZF=0aUchZX8hSA@mail.gmail.com' \
--to=greg@xiph$(echo .)org \
--cc=bitcoin-dev@lists$(echo .)linuxfoundation.org \
--cc=ondrej.vejpustek@satoshilabs$(echo .)com \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox