:: Re: [Libbitcoin] address collision?
Etusivu
Poista viesti
Vastaa
Lähettäjä: Mike Miller
Päiväys:  
Vastaanottaja: Neill Miller
Kopio: libbitcoin, Eric Voskuil
Aihe: Re: [Libbitcoin] address collision?
I'm sorry, I'm very much a newbie here and I'm surely using the wrong
terminology. Please forget I ever used the word "collision". Let's break
it down in dumb words I can understand:

(1) It is my understanding that there are just so many possible private
keys that this "power of large numbers" is what secures my bitcoin, in
effect. Again I may not be using precisely the right words, but that seems
to be the gist of it. Ref:
- https://learnbtc.tech/PowerOfLargeNumber.jpg
- https://www.youtube.com/watch?v=ZloHVKk7DHk

(2)  Based on the idea in #1, I had the idea to use libbitcoin ("bx") to
use "bx" to:
       (a)  generate a random private key
       (b)  derive a public key from said private key
       (c)  derive a bitcoin address from said public key
       (d)  check for any unspent inputs at said bitcoin address


(3) The idea was that if I never found anything it made my nimble brain
feel better about this crazy "big number" stuff, and thus feel better that
my bitcoin is safe. (I understand this is rather silly, for a variety of
reasons, but it was a fun experiment anyway).

(4) I ran this in an infinite loop a zillion times for 18 months, and
eventually one of the private keys "bx" generated mapped to an address that
contained someone's bitcoin.

(5) I was led to believe (due to the above links, for example) that the
probability of this ever happening was like winning the PowerBall lottery a
million times in a row, or something. So when my script turned up
someone's bitcoin, it shocked me.

(6) Given that the probability of what just happened is so low, it
occurred to me that perhaps the "random" seed generated by "bx" isn't so
random, or some other technical vulnerability that's above my pay grade.
Maybe the person who owns the bitcoin I found also used a wallet or tool
that employed libbitcoin or something similar, and due to the pseudorandom
nature of it, the odds of my finding something were significantly
increased. But even if that's true, it does frighten me a bit that some
other schmuck like me, scripting out a few lines of code, can find and
steal my bitcoin. (At this point I'm mostly trusting the random seed my
Trezor generated for me for my BTC).

(7) In my mind, the possibilities are (a) I just hit the Powerball a
million times in a row and this would never again happen in my lifetime, or
(b) something else I'm not technically able to conceive of.

(8) Given that I'm using libbitcoin to generate my addresses for this
exercise, I thought to bring this to your attention on this mailing list.
I'm not technical enough to posit that there's anything wrong with
libbitcoin, so please don't think that's what I'm claiming here. I haven't
a clue.

I hope this helps clear things up. Mainly I'm looking for someone to tell
me why I shouldn't be nervous about what happened.

Thanks.

-Mike


On Fri, Mar 29, 2019 at 7:45 AM Neill Miller <neillm@???>
wrote:

> Hello,
>
> I believe Mike's claim is that using 'bx seed' he generated a random
> number, converted to a private key and found a bitcoin balance there.
>
> While likely as unlikely, it's not exactly the same as an address
> collision, where a hash of some different public key collides via hash
> function with a duplicate address.
>
> Mike, can you clarify? The "address collision" subject does make me
> wonder if it's the latter and I've misinterpreted.
>
> -Neill.
>
> On Fri, Mar 29, 2019 at 01:00:35PM +0700, Eric Voskuil wrote:
> > 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
>