From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org [172.17.192.35]) by mail.linuxfoundation.org (Postfix) with ESMTPS id 54594118F for ; Wed, 17 Jan 2018 11:47:43 +0000 (UTC) X-Greylist: delayed 00:06:43 by SQLgrey-1.7.6 Received: from mail.sldev.cz (mail.sldev.cz [51.254.7.247]) by smtp1.linuxfoundation.org (Postfix) with ESMTPS id 7F006557 for ; Wed, 17 Jan 2018 11:47:42 +0000 (UTC) Received: from localhost (localhost [127.0.0.1]) by mail.sldev.cz (Postfix) with ESMTP id F04FBEB64 for ; Wed, 17 Jan 2018 12:06:29 +0000 (UTC) X-Virus-Scanned: Debian amavisd-new at mail.sldev.cz Received: from mail.sldev.cz ([127.0.0.1]) by localhost (mail.sl [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id AbUL1ErPyw_4 for ; Wed, 17 Jan 2018 12:06:19 +0000 (UTC) Received: from qwerty.kolej.mff.cuni.cz (unknown [10.8.8.156]) by mail.sldev.cz (Postfix) with ESMTPSA id C84FAE31D for ; Wed, 17 Jan 2018 12:06:19 +0000 (UTC) To: bitcoin-dev@lists.linuxfoundation.org From: =?UTF-8?Q?Ond=c5=99ej_Vejpustek?= Message-ID: <51280a45-f86b-3191-d55e-f34e880c1da8@satoshilabs.com> Date: Wed, 17 Jan 2018 12:39:42 +0100 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:52.0) Gecko/20100101 Thunderbird/52.5.2 MIME-Version: 1.0 Content-Type: text/plain; charset=utf-8 Content-Language: en-GB Content-Transfer-Encoding: 8bit X-Spam-Status: No, score=-1.9 required=5.0 tests=BAYES_00 autolearn=ham version=3.3.1 X-Spam-Checker-Version: SpamAssassin 3.3.1 (2010-03-16) on smtp1.linux-foundation.org X-Mailman-Approved-At: Wed, 17 Jan 2018 14:27:50 +0000 Subject: [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 11:47:43 -0000 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