summaryrefslogtreecommitdiff
path: root/b5/2e2f498b068e99c023a6fe8579a578775095e7
blob: 88ac8f371f78b93491e4376d577ae8ab66cf628f (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
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 <adam.back@gmail.com>) 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 <bitcoin-development@lists.sourceforge.net>;
	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 <adam@cypherspace.org>
To: Jeremy Spilman <jeremy@taplink.co>
Message-ID: <20131010142154.GA28656@netbook.cypherspace.org>
References: <CAEz79PrCSjSV=FcSMyYtNip8Jg8oa8nMaHbqKNKKyoB-NEqRDQ@mail.gmail.com>
	<op.w4p0i7a3yldrnw@laptop-air>
MIME-Version: 1.0
Content-Type: text/plain; charset=us-ascii; format=flowed
Content-Disposition: inline
In-Reply-To: <op.w4p0i7a3yldrnw@laptop-air>
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 <bitcoin-development@lists.sourceforge.net>
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: <bitcoin-development.lists.sourceforge.net>
List-Unsubscribe: <https://lists.sourceforge.net/lists/listinfo/bitcoin-development>,
	<mailto:bitcoin-development-request@lists.sourceforge.net?subject=unsubscribe>
List-Archive: <http://sourceforge.net/mailarchive/forum.php?forum_name=bitcoin-development>
List-Post: <mailto:bitcoin-development@lists.sourceforge.net>
List-Help: <mailto:bitcoin-development-request@lists.sourceforge.net?subject=help>
List-Subscribe: <https://lists.sourceforge.net/lists/listinfo/bitcoin-development>,
	<mailto:bitcoin-development-request@lists.sourceforge.net?subject=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 <mike@plan99.net> 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