📅 Original date posted:2016-05-08
📝 Original message:I received this:
---------- Forwarded message ----------
From: Pieter Wuille <pieter.wuille at gmail.com>
Date: Fri, Apr 22, 2016 at 6:44 PM
Subject: Re: [bitcoin-dev] Proposal to update BIP-32
To: Marek Palatinus <marek at palatinus.cz>
Cc: Bitcoin Dev <bitcoin-dev at lists.linuxfoundation.org>
On Thu, Apr 21, 2016 at 2:08 PM, Marek Palatinus <marek at palatinus.cz> wrote:
> On Wed, Apr 20, 2016 at 6:32 PM, Jochen Hoenicke via bitcoin-dev <
> bitcoin-dev at lists.linuxfoundation.org> wrote:
>
>> Hello Bitcoin Developers,
>>
>> I would like to make a proposal to update BIP-32 in a small way.
>>
>> I think the backward compatibility issues are minimal. The chance
>> that this affects anyone is less than 10^-30. Even if it happens, it
>> would only create some additional addresses (that are not seen if the
>> user downgrades). The main reason for suggesting a change is that we
>> want a similar method for different curves where a collision is much
>> more likely.
>>
>
I think I change like this makes a lot of sense technically, and I wish I
had known how BIP-32 would end up being used inside higher level mechanisms
that automatically increment the position beyond the control of the
application generating them. The inclusion of the requirement was there
because ECDSA is notorious for security problems under biased secret keys,
though it's really only a certificational issue for secp256k1 (due to its
group order being so close to 2^256).
>
>> #QUESTIONS:
>>
>> What is the procedure to update the BIP? Is it still possible to
>> change the existing BIP-32 even though it is marked as final? Or
>> should I make a new BIP for this that obsoletes BIP-32?
>>
>
BIPs are not supposed to be updated with new ideas, only
remarks/links/typos/clarifications/..., so that their bumbers can
unambiguously be used to refer to an idea. My suggestion would be to write
a new BIP that overrides parts of BIP32, and then put a note in BIP32 that
a better mechanism is available that is unlikely to change things in
reality for the secp256k1 curve.
I guess
> What algorithm is preferred? (bike-shedding) My suggestion:
>>
>> ---
>>
>> Change the last step of the private -> private derivation functions to:
>>
>> . In case parse(I_L) >= n or k_i = 0, the procedure is repeated
>> at step 2 with
>> I = HMAC-SHA512(Key = c_par, Data = 0x01 || I_R || ser32(i))
>
>
>> ---
>>
>> I think this suggestion is simple to implement (a bit harder to unit
>> test) and the string to hash with HMAC-SHA512 always has the same
>> length. I use I_R, since I_L is obviously not very random if I_L >= n.
>> There is a minimal chance that it will lead to an infinite loop if I_R
>> is the same in two consecutive iterations, but that has only a chance
>> of 1 in 2^512 (if the algorithm is used for different curves that make
>> I_L >= n more likely, the chance is still less than 1 in 2^256). In
>> theory, this loop can be avoided by incrementing i in every iteration,
>> but this would make an implementation error in the "hard to test" path
>> of the program more likely.
>>
>
The chance for failure is a bit higher than that, as it only requires a
failed key (one in 2^128) in the first step, followed by an iteration that
results in the same I_R to cause a cycle. If you take multiple failures
before the cycle starts into account, the combined chance for failure is
p/(1-p)^2 / 2^256 (with p the chance for a random inadmissable key), which
is not much better than 1 in 2^128 for high values of p.
An alternative that always converges is to retry with an appended iteration
count is possible:
{
I = HMAC-SHA512(Key = c_par, Data = 0x01 || || ser32(i)) for the first
iteration
I = HMAC-SHA512(Key = c_par, Data = 0x01 || || ser32(i) || ser32(j)) for
iteration number j, with j > 0
}
Cheers,
--
Pieter
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.linuxfoundation.org/pipermail/bitcoin-dev/attachments/20160508/f42d5ac4/attachment.html>;
Marek Palatinus [ARCHIVE] /
npub1xt…acz68
2023-06-07 17:50:25
in reply to nevent1q…059q
Author Public Key
npub1xtqansnal58rjnnxvyke6kzuvxsz0twg4456awy6ff0525yqgjxqjacz68Published at
2023-06-07 17:50:25Event JSON
{
"id": "990f9ca03907c271cbd89b199afbe78e525eb6e3dc81fcc4f660e1ffe0ed772c",
"pubkey": "32c1d9c27dfd0e394e66612d9d585c61a027adc8ad69aeb89a4a5f455080448c",
"created_at": 1686160225,
"kind": 1,
"tags": [
[
"e",
"446652111863f0dc7461177f37d69042d72c9e064cfa3d2aaf15324193562e10",
"",
"reply"
],
[
"p",
"a23dbf6c6cc83e14cc3df4e56cc71845f611908084cfe620e83e40c06ccdd3d0"
]
],
"content": "📅 Original date posted:2016-05-08\n📝 Original message:I received this:\n\n---------- Forwarded message ----------\nFrom: Pieter Wuille \u003cpieter.wuille at gmail.com\u003e\nDate: Fri, Apr 22, 2016 at 6:44 PM\nSubject: Re: [bitcoin-dev] Proposal to update BIP-32\nTo: Marek Palatinus \u003cmarek at palatinus.cz\u003e\nCc: Bitcoin Dev \u003cbitcoin-dev at lists.linuxfoundation.org\u003e\n\n\nOn Thu, Apr 21, 2016 at 2:08 PM, Marek Palatinus \u003cmarek at palatinus.cz\u003e wrote:\n\n\u003e On Wed, Apr 20, 2016 at 6:32 PM, Jochen Hoenicke via bitcoin-dev \u003c\n\u003e bitcoin-dev at lists.linuxfoundation.org\u003e wrote:\n\u003e\n\u003e\u003e Hello Bitcoin Developers,\n\u003e\u003e\n\u003e\u003e I would like to make a proposal to update BIP-32 in a small way.\n\u003e\u003e\n\u003e\u003e I think the backward compatibility issues are minimal. The chance\n\u003e\u003e that this affects anyone is less than 10^-30. Even if it happens, it\n\u003e\u003e would only create some additional addresses (that are not seen if the\n\u003e\u003e user downgrades). The main reason for suggesting a change is that we\n\u003e\u003e want a similar method for different curves where a collision is much\n\u003e\u003e more likely.\n\u003e\u003e\n\u003e\nI think I change like this makes a lot of sense technically, and I wish I\nhad known how BIP-32 would end up being used inside higher level mechanisms\nthat automatically increment the position beyond the control of the\napplication generating them. The inclusion of the requirement was there\nbecause ECDSA is notorious for security problems under biased secret keys,\nthough it's really only a certificational issue for secp256k1 (due to its\ngroup order being so close to 2^256).\n\n\u003e\n\u003e\u003e #QUESTIONS:\n\u003e\u003e\n\u003e\u003e What is the procedure to update the BIP? Is it still possible to\n\u003e\u003e change the existing BIP-32 even though it is marked as final? Or\n\u003e\u003e should I make a new BIP for this that obsoletes BIP-32?\n\u003e\u003e\n\u003e\nBIPs are not supposed to be updated with new ideas, only\nremarks/links/typos/clarifications/..., so that their bumbers can\nunambiguously be used to refer to an idea. My suggestion would be to write\na new BIP that overrides parts of BIP32, and then put a note in BIP32 that\na better mechanism is available that is unlikely to change things in\nreality for the secp256k1 curve.\n\nI guess\n\n\n\u003e What algorithm is preferred? (bike-shedding) My suggestion:\n\u003e\u003e\n\u003e\u003e ---\n\u003e\u003e\n\u003e\u003e Change the last step of the private -\u003e private derivation functions to:\n\u003e\u003e\n\u003e\u003e . In case parse(I_L) \u003e= n or k_i = 0, the procedure is repeated\n\u003e\u003e at step 2 with\n\u003e\u003e I = HMAC-SHA512(Key = c_par, Data = 0x01 || I_R || ser32(i))\n\u003e\n\u003e\n\u003e\u003e ---\n\u003e\u003e\n\u003e\u003e I think this suggestion is simple to implement (a bit harder to unit\n\u003e\u003e test) and the string to hash with HMAC-SHA512 always has the same\n\u003e\u003e length. I use I_R, since I_L is obviously not very random if I_L \u003e= n.\n\u003e\u003e There is a minimal chance that it will lead to an infinite loop if I_R\n\u003e\u003e is the same in two consecutive iterations, but that has only a chance\n\u003e\u003e of 1 in 2^512 (if the algorithm is used for different curves that make\n\u003e\u003e I_L \u003e= n more likely, the chance is still less than 1 in 2^256). In\n\u003e\u003e theory, this loop can be avoided by incrementing i in every iteration,\n\u003e\u003e but this would make an implementation error in the \"hard to test\" path\n\u003e\u003e of the program more likely.\n\u003e\u003e\n\u003e\nThe chance for failure is a bit higher than that, as it only requires a\nfailed key (one in 2^128) in the first step, followed by an iteration that\nresults in the same I_R to cause a cycle. If you take multiple failures\nbefore the cycle starts into account, the combined chance for failure is\np/(1-p)^2 / 2^256 (with p the chance for a random inadmissable key), which\nis not much better than 1 in 2^128 for high values of p.\n\nAn alternative that always converges is to retry with an appended iteration\ncount is possible:\n{\n I = HMAC-SHA512(Key = c_par, Data = 0x01 || || ser32(i)) for the first\niteration\n I = HMAC-SHA512(Key = c_par, Data = 0x01 || || ser32(i) || ser32(j)) for\niteration number j, with j \u003e 0\n}\n\nCheers,\n\n-- \nPieter\n-------------- next part --------------\nAn HTML attachment was scrubbed...\nURL: \u003chttp://lists.linuxfoundation.org/pipermail/bitcoin-dev/attachments/20160508/f42d5ac4/attachment.html\u003e",
"sig": "1a7e675aed6cc02e1c9d41b1b4122d92a00958a2be010f0c8db827c911c1652a0132cb90508d2829690f9d0cf9e01e566aea7b9563cc695d8a7cb629f632d91d"
}