Erik Aronesty [ARCHIVE] on Nostr: 📅 Original date posted:2018-07-19 📝 Original message:Also Wagner's algorithm ...
📅 Original date posted:2018-07-19
📝 Original message:Also Wagner's algorithm shouldn't be applicable for a number of reasons.
you can't birthday attack something where there's only a single variable
that you can modify. And when you change the equation from additive you
now have a multi-dimensional equation we're partitioning won't function.
this is the basis of the perfect security of Shamir secret sharing.
On Wed, Jul 11, 2018, 10:45 AM Erik Aronesty <erik at q32.com> wrote:
> OK, so you're going with this scenario:
>
> 1. I know Apub and Bpub,
> 2. I know M is 3
> 3. I'm choosing a random number for C's private key
>
> Cpub is g^C
>
> The equation I am solving for .. and trying to factor myself out of is
> g^Ax + g^B*2 + g^C*3
>
> I don't know A or B... I only know their public keys.
>
> I don't think it's possible to adaptively choose C for an attack on the
> multisig construction, when using hash of the public key as the X
> coordinate in the polynomial, because in order to satisfy the equation and
> factor out C, you would need to be able to break the hash.
>
> With an additive construction, yes... adaptive attacks are possible. But
> in a shamir secret sharing interpolation, you need a public X coordinate as
> well as a secret share. Choosing hash(pub) as X, prevents this attack.
>
>
> On Wed, Jul 11, 2018 at 6:35 AM, Adam Back <adam.back at gmail.com> wrote:
>
>> On Wed, Jul 11, 2018, 02:42 Erik Aronesty via bitcoin-dev <
>> bitcoin-dev at lists.linuxfoundation.org> wrote:
>> > Basically you're just replacing addition with interpolation everywhere
>> in the musig construction
>>
>> Yes, but you can't do that without a delinearization mechanism to prevent
>> adaptive public key choice being used to break the scheme using Wagner's
>> attack. It is not specific to addition, it is a generalized birthday attack.
>>
>> Look at the delinearization mechanism for an intuition, all public keys
>> are hashed along with per value hash, so that pre-commits and forces the
>> public keys to be non-adaptively chosen.
>>
>> Adaptively chosen public keys are dangerous and simple to exploit for
>> example pub keys A+B, add party C' he chooses C=C'-A-B, now we can sign for
>> A+B+C using adaptively chose public key C.
>>
>> Btw Wagner also breaks this earlier delinearization scheme
>> S=H(A)*A+H(B)*B+H(C)*C
>>
>> Adam
>>
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.linuxfoundation.org/pipermail/bitcoin-dev/attachments/20180719/0ab2aed3/attachment.html>;
📝 Original message:Also Wagner's algorithm shouldn't be applicable for a number of reasons.
you can't birthday attack something where there's only a single variable
that you can modify. And when you change the equation from additive you
now have a multi-dimensional equation we're partitioning won't function.
this is the basis of the perfect security of Shamir secret sharing.
On Wed, Jul 11, 2018, 10:45 AM Erik Aronesty <erik at q32.com> wrote:
> OK, so you're going with this scenario:
>
> 1. I know Apub and Bpub,
> 2. I know M is 3
> 3. I'm choosing a random number for C's private key
>
> Cpub is g^C
>
> The equation I am solving for .. and trying to factor myself out of is
> g^Ax + g^B*2 + g^C*3
>
> I don't know A or B... I only know their public keys.
>
> I don't think it's possible to adaptively choose C for an attack on the
> multisig construction, when using hash of the public key as the X
> coordinate in the polynomial, because in order to satisfy the equation and
> factor out C, you would need to be able to break the hash.
>
> With an additive construction, yes... adaptive attacks are possible. But
> in a shamir secret sharing interpolation, you need a public X coordinate as
> well as a secret share. Choosing hash(pub) as X, prevents this attack.
>
>
> On Wed, Jul 11, 2018 at 6:35 AM, Adam Back <adam.back at gmail.com> wrote:
>
>> On Wed, Jul 11, 2018, 02:42 Erik Aronesty via bitcoin-dev <
>> bitcoin-dev at lists.linuxfoundation.org> wrote:
>> > Basically you're just replacing addition with interpolation everywhere
>> in the musig construction
>>
>> Yes, but you can't do that without a delinearization mechanism to prevent
>> adaptive public key choice being used to break the scheme using Wagner's
>> attack. It is not specific to addition, it is a generalized birthday attack.
>>
>> Look at the delinearization mechanism for an intuition, all public keys
>> are hashed along with per value hash, so that pre-commits and forces the
>> public keys to be non-adaptively chosen.
>>
>> Adaptively chosen public keys are dangerous and simple to exploit for
>> example pub keys A+B, add party C' he chooses C=C'-A-B, now we can sign for
>> A+B+C using adaptively chose public key C.
>>
>> Btw Wagner also breaks this earlier delinearization scheme
>> S=H(A)*A+H(B)*B+H(C)*C
>>
>> Adam
>>
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.linuxfoundation.org/pipermail/bitcoin-dev/attachments/20180719/0ab2aed3/attachment.html>;