Return-Path: Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org [172.17.192.35]) by mail.linuxfoundation.org (Postfix) with ESMTPS id 93F4B10B1 for ; Wed, 17 Jan 2018 15:31:47 +0000 (UTC) X-Greylist: whitelisted by SQLgrey-1.7.6 Received: from mail-vk0-f48.google.com (mail-vk0-f48.google.com [209.85.213.48]) by smtp1.linuxfoundation.org (Postfix) with ESMTPS id 04B00157 for ; Wed, 17 Jan 2018 15:31:46 +0000 (UTC) Received: by mail-vk0-f48.google.com with SMTP id e125so8490381vkh.13 for ; Wed, 17 Jan 2018 07:31:46 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=mime-version:sender:in-reply-to:references:from:date:message-id :subject:to:content-transfer-encoding; bh=z3+F3pl4LAhBYFCzsXUa/7v1l9fUNDxXdDE/CjUtNjE=; b=QKIocIoLOSEfKyCI38LzEfmFdtGiuG52oWzqpYG7XVzwryN/hX0XWzZLPB+EKzk2Gx IoMY4uP1fhb5KMSA6B0IKd10b692frI7UakdUVKRdEgQzG4owRQzU0Wl0bXNbMtgo81T zjVAHQV81ex6Ap8PCtP//xpDg7FEEY3zo4z1rvbpK1iFqwQgn+XyzuGQqoCucBZDp1Mt QVuo0NCIf/I0wIyuIf3op1FzjC0bSTqOkdlRMBxWzGTZECMgSIbvpFvVXnkKTedW3gfl y/cmM86TewPH0GMihANIlEnzPOgnFV5yGzUqQJ9XO2e2ghPKIF4QiyQ3PsD9rYxlbRh1 Zejw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:mime-version:sender:in-reply-to:references:from :date:message-id:subject:to:content-transfer-encoding; bh=z3+F3pl4LAhBYFCzsXUa/7v1l9fUNDxXdDE/CjUtNjE=; b=tG29vXzbakUbi1Y1z577BP1iYjPPZZHSZrP2gDbwXMXOtls3aa3UlApeSL4uEiUdH0 3vcqBUHdh2LNun7rpCGNbPeGcnBVQco10ZNDix3TTdXioRIiWoNYjNVpjStnvj81HWyn J7S+smHzwjXVna+ewbBq3wt/m1sSe1bJw5dbpLONbTarBc0eBwk8wQy3G03O8nmn6E2X 8Mz8U3xJY6qX3FbNxxJ7vEa01SZTb/BXgAXlGGjw2Foh5RWdwbTIrCA73tbukV013sPk mFbAMAQ8AQEJYPu+V5S5WWQQO4I7xQ3WsyAWSlmj9Sfa/MWDoFM1YT/ZndyHr11qlN+K 10zw== X-Gm-Message-State: AKwxytdcBSoAe3sV2MZDEkrfe5JtdymcjO8/hW095S9DSlpXMzhRUL9+ YGSKPcFiqd+0IyGYY/dazZwi6GrXWtOx+REAdnMFbw== X-Google-Smtp-Source: ACJfBouINu/RvTdsrgIR9Db1rSptE8vrI6bgOVjDskA5+aVQMzAHPjKhy5Zz6KVE9QHQ3Gy4xIkogxmgQJ9Jc0RVO8U= X-Received: by 10.31.3.94 with SMTP id 91mr2228577vkd.124.1516203105957; Wed, 17 Jan 2018 07:31:45 -0800 (PST) MIME-Version: 1.0 Sender: gmaxwell@gmail.com Received: by 10.103.85.152 with HTTP; Wed, 17 Jan 2018 07:31:44 -0800 (PST) In-Reply-To: <51280a45-f86b-3191-d55e-f34e880c1da8@satoshilabs.com> References: <51280a45-f86b-3191-d55e-f34e880c1da8@satoshilabs.com> From: Gregory Maxwell Date: Wed, 17 Jan 2018 15:31:44 +0000 X-Google-Sender-Auth: cjJx6mBqjvpYSoZrr4dSrXVHSl8 Message-ID: To: =?UTF-8?Q?Ond=C5=99ej_Vejpustek?= , Bitcoin Protocol Discussion Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: quoted-printable X-Spam-Status: No, score=-1.9 required=5.0 tests=BAYES_00,DKIM_SIGNED, DKIM_VALID, FREEMAIL_FROM, RCVD_IN_DNSWL_NONE autolearn=ham version=3.3.1 X-Spam-Checker-Version: SpamAssassin 3.3.1 (2010-03-16) on smtp1.linux-foundation.org Subject: Re: [bitcoin-dev] Satoshilabs secret shared private key scheme X-BeenThere: bitcoin-dev@lists.linuxfoundation.org X-Mailman-Version: 2.1.12 Precedence: list List-Id: Bitcoin Protocol Discussion List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Wed, 17 Jan 2018 15:31:47 -0000 On Wed, Jan 17, 2018 at 11:39 AM, Ond=C5=99ej Vejpustek via bitcoin-dev 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 =3D 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).