From mboxrd@z Thu Jan 1 00:00:00 1970 Received: from sog-mx-3.v43.ch3.sourceforge.com ([172.29.43.193] helo=mx.sourceforge.net) by sfs-ml-4.v29.ch3.sourceforge.com with esmtp (Exim 4.76) (envelope-from ) id 1VUH7s-0002Uq-PC for bitcoin-development@lists.sourceforge.net; Thu, 10 Oct 2013 14:22:04 +0000 Received-SPF: pass (sog-mx-3.v43.ch3.sourceforge.com: domain of gmail.com designates 209.85.215.173 as permitted sender) client-ip=209.85.215.173; envelope-from=adam.back@gmail.com; helo=mail-ea0-f173.google.com; Received: from mail-ea0-f173.google.com ([209.85.215.173]) by sog-mx-3.v43.ch3.sourceforge.com with esmtps (TLSv1:RC4-SHA:128) (Exim 4.76) id 1VUH7r-0006xZ-L4 for bitcoin-development@lists.sourceforge.net; Thu, 10 Oct 2013 14:22:04 +0000 Received: by mail-ea0-f173.google.com with SMTP id g10so1200000eak.4 for ; Thu, 10 Oct 2013 07:21:57 -0700 (PDT) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20130820; h=date:from:to:cc:subject:message-id:references:mime-version :content-type:content-disposition:in-reply-to:user-agent; bh=bBKcVEyV52DoU86UTzUINZ1LoSGSUjohHrhaY2tojPI=; b=J5M1Srs2RLGQKs0lUz3GmLAXdOlyJwihiP0e3bkUNQJ+lI2QDpsCzYqjT2YlXJ78Mz MqHGPgilHY46CmjC0KXrPRA+6XBaBalemxCkj4xznh/KFmhjCyz2W3UayjtwcatWcxZx nwKu5hK4aJNpje+wTsEK8uBl0O88RVekOFTZd4s6XABlaF5REnDeo77xIRv3HTELq2Z1 5gnrQWrr6BjnE/bCGAE5m6U4C5borDWewrRasdAc+oCcZzeelJmvchBAeweTbyGPDqPL Pl7fVTggl55xO9j+KI4L4Kt4C5Ykj7DsSlV3jVnm/Dq9JcTKMdlDNj5ybvKRTP5HvkzE gBXw== X-Received: by 10.15.101.137 with SMTP id bp9mr2596842eeb.53.1381414917292; Thu, 10 Oct 2013 07:21:57 -0700 (PDT) Received: from netbook (c83-90.i07-21.onvol.net. [92.251.83.90]) by mx.google.com with ESMTPSA id h45sm102164447eeg.5.1969.12.31.16.00.00 (version=TLSv1.1 cipher=ECDHE-RSA-RC4-SHA bits=128/128); Thu, 10 Oct 2013 07:21:56 -0700 (PDT) Received: by netbook (Postfix, from userid 1000) id DDA162E0887; Thu, 10 Oct 2013 16:21:56 +0200 (CEST) Received: by flare (hashcash-sendmail, from uid 1000); Thu, 10 Oct 2013 16:21:55 +0200 Date: Thu, 10 Oct 2013 16:21:54 +0200 From: Adam Back To: Jeremy Spilman Message-ID: <20131010142154.GA28656@netbook.cypherspace.org> References: MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii; format=flowed Content-Disposition: inline In-Reply-To: User-Agent: Mutt/1.5.21 (2010-09-15) X-Hashcash: 1:20:131010:jeremy@taplink.co::QNSHxT9RNVpvGHjT:00000000000000000000 0000000000000000000000004P4b X-Hashcash: 1:20:131010:bitcoin-development@lists.sourceforge.net::PWO3U/q60kmsp BHF:000000000000000000000ldK X-Hashcash: 1:20:131010:adam@cypherspace.org::uSpl3oqU4p+E/kDu:00000000000000000 0000000000000000000000006Zs0 X-Spam-Score: -1.5 (-) X-Spam-Report: Spam Filtering performed by mx.sourceforge.net. See http://spamassassin.org/tag/ for more details. -1.5 SPF_CHECK_PASS SPF reports sender host as permitted sender for sender-domain 0.0 FREEMAIL_FROM Sender email is commonly abused enduser mail provider (adam.back[at]gmail.com) -0.0 SPF_PASS SPF: sender matches SPF record 0.0 URIBL_BLOCKED ADMINISTRATOR NOTICE: The query to URIBL was blocked. See http://wiki.apache.org/spamassassin/DnsBlocklists#dnsbl-block for more information. [URIs: plan99.net] X-Headers-End: 1VUH7r-0006xZ-L4 Cc: Bitcoin Dev Subject: [Bitcoin-development] malleability work-around vs fix (Re: 0.8.5 with libsecp256k1) X-BeenThere: bitcoin-development@lists.sourceforge.net X-Mailman-Version: 2.1.9 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Thu, 10 Oct 2013 14:22:05 -0000 Determinstic ECDSA signature aka k=H(d,m) insead of k=random, with signature (r,s) calculated r=[kG].x, s=k^-1(H(m)+rd) with public key Q=dG and verificaton relation [H(m)s^-1G+rs^-1Q].x=?r is cool and should be done. Otherwise RNG issues like EC_DRBG or even leaked partial bits like the RNG bias in the original DSA spec that Bleichenbacher pointed out and then they corrected. On Wed, Oct 09, 2013 at 09:10:09PM -0700, Jeremy Spilman wrote: >Can this be combined with the ideas on deterministic signing to show >matching signatures with OpenSSL's implementation? But k=random and k=H(d,m) create compatible signatures - or were you eaning to cross check the two implementations with fuzz tester on lots of messages? btw about malleability: Mike Hearn wrote: > I believe the main issue at the moment is the malleability issues? If > so, it would seem possible to use OpenSSL to parse the signature into > components and then libsecp256k1 to verify them. other than the ASN.1 related parsing ambiguity, if any (openSSL asn.1 parsing code is evil and shold not be used), the (r,s) vs (r,-s) ambiguity can be plugged as discussed (eg define -s as invalid). But that is ECDSA specific, and signature malleability and its impact is a generic problem. Its probably a non-requirement of a signature scheme in terms of the analysis effort put in by cryptanalysts that the signature itself be non-malleable, eg there are some encryption schemes which are publicly reblindable, like Elgamal. By plugging the (r,s), (r,-s) specific case as a DSA specific work-around there may be other malleability even in DSA, unless someone has a clear proof that there is not. And we may want to add ECS (schnorr) because it's simpler and allows more flexibility and efficiency (eg native n of n multisig at the storage cost of 1 signature vs n with ECDSA, and k of n threshold signature at the cost of 1 sig (but some threshold secret share setup up front). The relying party doesnt need to know how many multi-sigs there are there is a single public key. So I was thinking a more generic / robust way to fix this would be to change the txid from H(sig,inputs,outputs,script) to H(pubkey,inputs,outputs,script) or something like that in effect so that the malleability of the signature mechanism doesnt affect the security of conditional payments. Adam