Received: from sog-mx-3.v43.ch3.sourceforge.com ([172.29.43.193]
	helo=mx.sourceforge.net)
	by sfs-ml-2.v29.ch3.sourceforge.com with esmtp (Exim 4.76)
	(envelope-from <adam.back@gmail.com>) id 1UpKJB-0007R1-H7
	for bitcoin-development@lists.sourceforge.net;
	Wed, 19 Jun 2013 15:28:29 +0000
Received-SPF: pass (sog-mx-3.v43.ch3.sourceforge.com: domain of gmail.com
	designates 74.125.83.43 as permitted sender)
	client-ip=74.125.83.43; envelope-from=adam.back@gmail.com;
	helo=mail-ee0-f43.google.com; 
Received: from mail-ee0-f43.google.com ([74.125.83.43])
	by sog-mx-3.v43.ch3.sourceforge.com with esmtps (TLSv1:RC4-SHA:128)
	(Exim 4.76) id 1UpKJA-00006k-A2
	for bitcoin-development@lists.sourceforge.net;
	Wed, 19 Jun 2013 15:28:29 +0000
Received: by mail-ee0-f43.google.com with SMTP id l10so3293302eei.30
	for <bitcoin-development@lists.sourceforge.net>;
	Wed, 19 Jun 2013 08:28:22 -0700 (PDT)
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
	d=google.com; s=20120113;
	h=date:from:to:cc:subject:message-id:references:mime-version
	:content-type:content-disposition:in-reply-to:user-agent:x-hashcash
	:x-hashcash:x-hashcash:x-hashcash;
	bh=cYfgFDoDXJUThVh8Gh4IAnh0UnRhd9j3z2OllWZR2TM=;
	b=bLrMM5ET4uWv5qstX6o3pOIBE1JWUIIdAAAxrynXmJ8AFar6ONyzQ08vWsMQ/7MNnM
	XC+XR9hBtxSSAZTiN//5ZaKpDP2K44VfZCpr6j53wdEPL9oFdXCSfUXwMf7xM/a/yBRE
	jAiO0MS2Vr/FumgzQ4PlrFFgAILvL+injWy73o9lpcH8i0x/yvcTEmgzFGHu12tVJhy4
	CaEx7CR7rkYVTgGNPyxxYKdtqbuBTa50oPeK50kcYxg5wgUtBwSQvQkxBNe4oVeppc6x
	NHBjXsFo03RlXH1B959sQHlaDb5kVQolkSK/f+PKKeatnIMokcvg7RIligm3WfEsq+yJ
	3A3g==
X-Received: by 10.14.53.75 with SMTP id f51mr3229352eec.30.1371655701900;
	Wed, 19 Jun 2013 08:28:21 -0700 (PDT)
Received: from netbook (c83-90.i07-21.onvol.net. [92.251.83.90])
	by mx.google.com with ESMTPSA id b7sm37636640eef.16.2013.06.19.08.28.19
	for <multiple recipients>
	(version=TLSv1.1 cipher=ECDHE-RSA-RC4-SHA bits=128/128);
	Wed, 19 Jun 2013 08:28:20 -0700 (PDT)
Received: by netbook (Postfix, from userid 1000)
	id 76B2E2E05D8; Wed, 19 Jun 2013 17:28:18 +0200 (CEST)
Received: by flare (hashcash-sendmail, from uid 1000);
	Wed, 19 Jun 2013 17:28:16 +0200
Date: Wed, 19 Jun 2013 17:28:15 +0200
From: Adam Back <adam@cypherspace.org>
To: Alan Reiner <etotheipi@gmail.com>
Message-ID: <20130619152815.GA14729@netbook.cypherspace.org>
References: <51BFD886.8000701@gmail.com> <20130619142510.GA17239@crunch>
	<51C1C288.4000305@gmail.com>
MIME-Version: 1.0
Content-Type: text/plain; charset=us-ascii; format=flowed
Content-Disposition: inline
In-Reply-To: <51C1C288.4000305@gmail.com>
User-Agent: Mutt/1.5.21 (2010-09-15)
X-Hashcash: 1:20:130619:etotheipi@gmail.com::tehOFdZPg5gmBOc7:000000000000000000
	00000000000000000000000055XQ
X-Hashcash: 1:20:130619:timo.hanke@web.de::En1ioz1Dp/E9M8iu:00000000000000000000
	0000000000000000000000004fdM
X-Hashcash: 1:20:130619:bitcoin-development@lists.sourceforge.net::GBmIcbtiL9fpj
	Tpf:0000000000000000000029te
X-Hashcash: 1:20:130619:adam@cypherspace.org::3vC31E0hCPb3No4d:00000000000000000
	0000000000000000000000005m6m
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
X-Headers-End: 1UpKJA-00006k-A2
Cc: Bitcoin Dev <bitcoin-development@lists.sourceforge.net>, timo.hanke@web.de
Subject: Re: [Bitcoin-development] Optional "wallet-linkable" address format
 - Payment Protocol
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: Wed, 19 Jun 2013 15:28:29 -0000

I think Timo's point is that while you cant do discrete log, you can do y-th
root.  So if P = xG is a parent public key (x private key, G base point),
then your proposed multiplier address is hash of Q=yP.  However its easy to
find another P such that Q=zP'.  ie just "divide by z" (EC multiply by z^-1
mod n, n the order of the curve).  So P'=z^-1.Q, which will work because
Q=zP', substituting P' you get Q=z.z^-1.Q, Q=Q.

Of course the attacker has just performed an unspenable DoS (maybe, or maybe
a useless collision) because he wont know the discrete log of Q, nor P, nor
P'.  So thats the question, does the protocol have any reliance on knowing
the discrete log - is it a problem if someone can find different multipliers
of different (unknown, uncomputable discrete log) parent keys.

If it was a concern I guess you could require a proof of knowledge of
discrete log.  ie as well as public key parent, multiplier the address must
include ECDSA sig or Schnorr proof of knowledge (which both demonstrate
knowledge of the discrete log of Q to base G.)

So his defense could probably be more simply viewed as hash rather than MAC
(same thing approximately) you provide the pre-image of the multiplier.  So
provide P (public parent), x' (mutiplier pre-image).  And compute Q=xP where
x=H(x',P).  You cant use just x=H(x') because I could choose random x',
compute x=H(x') compute x^-1 and multiply Q to find P'=x^-1.Q=H(x')^-1.Q as
before.  Because x includes P as well, I would have to simultaneously choose
a P' such that Q=H(x',P').P' which requires a birthday attack on the hash
(or MAC).

Adam

On Wed, Jun 19, 2013 at 10:39:04AM -0400, Alan Reiner wrote:
>
>On 06/19/2013 10:25 AM, Timo Hanke wrote:
>> Since you mention to use this in conjunction with the payment protocol,
>> note the following subtlety. Suppose the payer has to paid this address
>> called "destination":
>>>    Standard Address ~ Base58(0x00 || hash160(PubKeyParent * Multiplier[i]) ||
>>> checksum)
>> Also suppose the payee has spent the output, i.e. the pubkey
>> corresponding to "destination", which is PubKeyParent * Multiplier[i],
>> is publicly known. Then anybody can (in retrospect) create arbitrary
>> many pairs {PublicKeyParent, Multiplier} (in particular different
>> PublicKeyParent) that lead to the same "destination".
>>
>> Depending on what you have in mind that the transaction should "prove"
>> regarding its actual receiver or regarding the receiver's PubKeyParent,
>> this could be an unwanted feature (or it could be just fine). If it is
>> unwanted then I suggest replacing
>> PubKeyParent * Multiplier[i] by
>> PubKeyParent * HMAC(Multiplier[i],PubKeyParent)
>> which eliminates from the destination all ambiguity about PubKeyParent.
>>
>> This modification would not be directly compatible with BIP32 anymore
>> (unfortunately), but seems to be better suited for use in conjunction
>> with a payment protocol.
>>
>> Timo
>
>It's an interesting observation, but it looks like the most-obvious
>attack vector is discrete log problem:  spoofing a relationship between
>a target public key and one that you control.   For instance, if you see
>{PubA, Mult} produces PubB and you have PubC already in your control
>that you want to "prove" [maliciously] is related to PubB, then you have
>to find the multiplier, M that solves:  M*PubC = PubB.  That's a
>discrete logarithm problem.
>
>I'm not as familiar as you are, with the available operations on
>elliptic curves, but it sounds like you can produce essentially-random
>pairs of {PubX, Mult} pairs that give the same PubB, but you won't have
>the private key associated with those public keys.  It's an interesting
>point, and there may be a reason to be concerned about it.  Though, I
>don't see it yet.
>
>-Alan
>
>------------------------------------------------------------------------------
>This SF.net email is sponsored by Windows:
>
>Build for Windows Store.
>
>http://p.sf.net/sfu/windows-dev2dev
>_______________________________________________
>Bitcoin-development mailing list
>Bitcoin-development@lists.sourceforge.net
>https://lists.sourceforge.net/lists/listinfo/bitcoin-development