:: Re: [Libbitcoin] address collision?
Top Page
Delete this message
Reply to this message
Author: Eric Voskuil
Date:  
To: Mike Miller
CC: Neill Miller, libbitcoin
Subject: Re: [Libbitcoin] address collision?
It is possible for you to prove hash collision once the output is spent by its owner. Simply obtain the public key from the input script and then show that your public key also hashes to the same value.

The probability of you having found a collision are much higher than you having found the same public key, and if the keys don’t match you indeed probably found a collision.

e

> On Mar 29, 2019, at 06:29, Mike Miller <mike@???> wrote:
>
> Hmm, I had a feeling someone might question the veracity of my claim. And you're right, there's no wait for me to prove it happened. I'm rather shocked about it, personally, given the probabilities involved. I'm no expert on these matters, and thought I'd bring it to your attention in case there was some sort of vulnerability. If not, I think I'll go and spread my bitcoin around a bit more thinly given that "guessing" a private key appears to be possible. More baskets for my eggs, as it were.
>
> -Mike
>
>
>> On Thu, Mar 28, 2019 at 7:20 PM Eric Voskuil <eric@???> wrote:
>> Libbitcoin seeding wouldn’t contribute to an increased likelihood of finding a hash collision. For example, a poor seeding algorithm, such as one that less-than-randomly duplicates values, would only make finding a collision *less* likely. The best approach for collision finding may be to just increment from zero (ie avoiding duplicates).
>>
>> Unfortunately it’s impossible to verify this claim, so I’d take it with a bit of salt. On the other hand hash collisions do happen. It’s just a matter of probability.
>>
>> e
>>
>> > On Mar 29, 2019, at 05:43, Neill Miller <neillm@???> wrote:
>> >
>> > Hello Mike,
>> >
>> > Interesting find!
>> >
>> > It's true that the "bx seed" command provides psuedo-random numbers
>> > provided by the OS. The intent of all libbitcoin commands is to never
>> > generate randomness internally where necessary (and to rather accept
>> > randomness as an input where needed), but "bx seed" is an exception,
>> > mostly for example purposes. To be clear, we don't recommend using it
>> > for strong cryptographic purposes (of which generating Bitcoin private
>> > keys is one such example).
>> >
>> > It is quite possible that's a reason for the collision, or at least
>> > that's my best guess at the moment.
>> >
>> > That said, I have run similar sorts of programs (more optimized than
>> > what's shown) for extended periods of time in the past out of
>> > curiosity and also to 'convince' myself of the same thing you were
>> > thinking about, and never produced a result like yours. I know we're
>> > not the only ones who have tried this as well :-)
>> >
>> > -Neill.
>> >
>> >> On Thu, Mar 28, 2019 at 05:32:27PM -0400, Mike Miller wrote:
>> >> Approximately 18 months ago I became fascinated with the magic of extremely
>> >> large numbers and that this is basically what's protecting my bitcoin.
>> >>
>> >> e.g. https://learnbtc.tech/PowerOfLargeNumber.jpg
>> >>
>> >> In an effort to somewhat "prove" this to myself, I whipped up a script to
>> >> run an endless loop generating random public/private keypairs (using the
>> >> libbitcoin library) and checking the received "balance" at each address,
>> >> and to email me if anything was found. Naturally this script never seemed
>> >> to "find" any bitcoin. This was comforting to me, as it meant that my
>> >> bitcoin was relatively safe from others doing the same thing.
>> >>
>> >> The meat of the loop is:
>> >>
>> >> $bx = '/usr/local/bin/bx'
>> >> $private_key = `$bx seed | $bx ec-new|$bx ec-to-wif`
>> >> $public_key = `$bx wif-to-public $private_key`
>> >> $address = `$bx ec-to-address $public_key`
>> >> $balance = `$bx fetch-balance $address`
>> >>
>> >> I completely forgot about this script, but it's been running all this time
>> >> (~18 months), just running in an infinite loop on my desktop linux box.
>> >> This morning I woke up to a surprise email that something had been found.
>> >>
>> >> balance
>> >> {
>> >>    address 1CeuzQcb5pmM1PmyoDgV5rfPsJDkAY8ScR
>> >>    received 1965000
>> >>    spent 0
>> >> }

>> >>
>> >>
>> >> I used electrum to "import" the associated private key to verify this
>> >> amount was accessible. But I didn't move it -- of course I don't want to
>> >> steal the poor guy's BTC.
>> >>
>> >> I'm a little bit blown away here. I thought the known universe would hit
>> >> end of life before finding anything. If I can get this lucky finding a
>> >> needle in a haystack with few lines of Perl code, I don't feel quite as
>> >> safe about my bitcoin.
>> >>
>> >> Or might this mean that, despite the fact that it took 18 months to produce
>> >> a collision, there might be something nonrandom about the seeding mechanism?
>> >>
>> >> It says mine is Version: 4.0.0, which was the latest version at that time.
>> >>
>> >> Thoughts?
>> >>
>> >> -Mike
>> >
>> >> _______________________________________________
>> >> Libbitcoin mailing list
>> >> Libbitcoin@???
>> >> https://mailinglists.dyne.org/cgi-bin/mailman/listinfo/libbitcoin
>> >
>> > _______________________________________________
>> > Libbitcoin mailing list
>> > Libbitcoin@???
>> > https://mailinglists.dyne.org/cgi-bin/mailman/listinfo/libbitcoin
>> _______________________________________________
>> Libbitcoin mailing list
>> Libbitcoin@???
>> https://mailinglists.dyne.org/cgi-bin/mailman/listinfo/libbitcoin