Bitcoin Forum
March 28, 2024, 04:21:25 PM *
News: Latest Bitcoin Core release: 26.0 [Torrent]
 
   Home   Help Search Login Register More  
Pages: [1] 2 3 »  All
  Print  
Author Topic: Potential attack vector in generating Bitcoin addresses?  (Read 8001 times)
joepie91 (OP)
Sr. Member
****
Offline Offline

Activity: 294
Merit: 250


View Profile
July 05, 2011, 06:30:44 PM
 #1

So, I was thinking about the address generation scheme that is used for Bitcoin. Please note I did not do any math here yet to see if it is likely to happen, it's just a concept.


To my understanding no network communication takes place when generating Bitcoin addresses. It's basically done locally. From my understanding Bitcoin address generation is also predictable in the sense that generating the same address twice, while unlikely, will result in the same private and public keypair.

Now from what I understood, the chance of a collision (that you would get an address that already belongs to someone else) is possible, but so unlikely that it's discountable. All fine up to this point.

Now what if someone made a botnet generate addresses all the time, 24/7, and would import those addresses into a wallet.dat to try and see if someone else already generated the address, and has funds 'assigned' to it - essentially trying to find collisions? Wouldn't this be an extremely efficient way to generate addresses until an address was found that held funds, to then steal the funds on that address by transfering them elsewhere?

Is this a possible attack vector and if yes, how likely is it to succeed?

Like my post(s)? 12TSXLa5Tu6ag4PNYCwKKSiZsaSCpAjzpu Smiley
Quote from: hawks5999
I just can't wait for fall/winter. My furnace never generated money for me before. I'll keep mining until my furnace is more profitable.
1711642885
Hero Member
*
Offline Offline

Posts: 1711642885

View Profile Personal Message (Offline)

Ignore
1711642885
Reply with quote  #2

1711642885
Report to moderator
1711642885
Hero Member
*
Offline Offline

Posts: 1711642885

View Profile Personal Message (Offline)

Ignore
1711642885
Reply with quote  #2

1711642885
Report to moderator
1711642885
Hero Member
*
Offline Offline

Posts: 1711642885

View Profile Personal Message (Offline)

Ignore
1711642885
Reply with quote  #2

1711642885
Report to moderator
"Bitcoin: mining our own business since 2009" -- Pieter Wuille
Advertised sites are not endorsed by the Bitcoin Forum. They may be unsafe, untrustworthy, or illegal in your jurisdiction.
1711642885
Hero Member
*
Offline Offline

Posts: 1711642885

View Profile Personal Message (Offline)

Ignore
1711642885
Reply with quote  #2

1711642885
Report to moderator
1711642885
Hero Member
*
Offline Offline

Posts: 1711642885

View Profile Personal Message (Offline)

Ignore
1711642885
Reply with quote  #2

1711642885
Report to moderator
BitcoinPorn
Hero Member
*****
Offline Offline

Activity: 630
Merit: 500


Posts: 69


View Profile WWW
July 05, 2011, 06:32:45 PM
 #2

Damn fine theory, I don't know specifics enough to say if such schemes would work, but if the way things work the way you say they do, then in theory it seems like that would be possible.

gentakin
Member
**
Offline Offline

Activity: 98
Merit: 10


View Profile
July 05, 2011, 06:34:51 PM
 #3

It is possible.

At the same time - right now, it is much more profitable to just use all that power needed for such an attack for mining.

1HNjbHnpu7S3UUNMF6J9yWTD597LgtUCxb
MiningBuddy
Hero Member
*****
Offline Offline

Activity: 927
Merit: 1000


฿itcoin ฿itcoin ฿itcoin


View Profile
July 05, 2011, 06:36:09 PM
 #4

I was thinking bout this last night while playing around with vanitygen.
So in theory, I could ask vanitygen to generate an address that I already know and use this to find the key pairs?

Littleshop
Legendary
*
Offline Offline

Activity: 1386
Merit: 1003



View Profile WWW
July 05, 2011, 06:39:30 PM
 #5

I was thinking bout this last night while playing around with vanitygen.
So in theory, I could ask vanitygen to generate an address that I already know and use this to find the key pairs?

You could not do that with all of the computing power on earth.  Well not in the next 100 years at least.

rabit
Member
**
Offline Offline

Activity: 62
Merit: 10


View Profile
July 05, 2011, 06:40:05 PM
 #6

The botnet would need many years for reaching a 50% probability of key collision.
joepie91 (OP)
Sr. Member
****
Offline Offline

Activity: 294
Merit: 250


View Profile
July 05, 2011, 06:44:06 PM
 #7

The point is I am not talking about targeting one specific address and finding collisions, but about targeting "every address", just generating until you find addresses that hold BTC to some extent, and taking whatever it is you find on the way.

Like my post(s)? 12TSXLa5Tu6ag4PNYCwKKSiZsaSCpAjzpu Smiley
Quote from: hawks5999
I just can't wait for fall/winter. My furnace never generated money for me before. I'll keep mining until my furnace is more profitable.
ribuck
Donator
Hero Member
*
Offline Offline

Activity: 826
Merit: 1039


View Profile
July 05, 2011, 06:49:59 PM
 #8

The botnet would need many years for reaching a 50% probability of key collision.

Many millions of years.

It's not impossible for a collision to be found, but there's not enough profit in it. Even if someone can find one address every hundred million years, all they get to spend is the balance of that one address. This equates to an averaged cost of fraud of way less than a millionth of a cent per transaction.

It's not worth worrying about, when any simple trojan or social engineering attack is sure to net a few wallets.
rabit
Member
**
Offline Offline

Activity: 62
Merit: 10


View Profile
July 05, 2011, 06:50:31 PM
 #9

The set of all used addresses is so small compared to the 2^160 possible addresses, so that it really doesnt matter if you search for one or for all used.
legion050
Newbie
*
Offline Offline

Activity: 51
Merit: 0



View Profile
July 05, 2011, 06:57:01 PM
 #10

The point is I am not talking about targeting one specific address and finding collisions, but about targeting "every address", just generating until you find addresses that hold BTC to some extent, and taking whatever it is you find on the way.
I think it is semi-possible.

while going for one address is unlikely to the extreme, just going after multiple random addresses is much more likely..

I was testing keygen and memory once, and I had bitcoin generate 1 million keypairs.
If a botnet was to do this scheme, I would think that there would be a good probablility of getting a small few. however the likelyhood of getting a single address with a large amount of bitcoins, is as impossible as attacking one address.

I also wonder how many addresses most people have..
rabit
Member
**
Offline Offline

Activity: 62
Merit: 10


View Profile
July 05, 2011, 07:00:36 PM
Last edit: July 05, 2011, 08:06:12 PM by rabit
 #11

Here is a short computation: assuming that a botnet can compute 1000000^2 addresses per second, then it would compute lesser than 2^75 keys in 1000 years. So ~0% of all addresses can be computed by a botnet in 1000 years.
TiagoTiago
Hero Member
*****
Offline Offline

Activity: 616
Merit: 500


Firstbits.com/1fg4i :)


View Profile
July 05, 2011, 07:05:26 PM
 #12

I've been told that the odds are there will be no collision before the heat death of the universe even if everyone dedicated all their machines to that goal

(I dont always get new reply notifications, pls send a pm when you think it has happened)

Wanna gimme some BTC/BCH for any or no reason? 1FmvtS66LFh6ycrXDwKRQTexGJw4UWiqDX Smiley

The more you believe in Bitcoin, and the more you show you do to other people, the faster the real value will soar!

Do you like mmmBananas?!
EricJ2190
Full Member
***
Offline Offline

Activity: 134
Merit: 102


View Profile
July 05, 2011, 07:05:42 PM
 #13

Even if you have enough CPU power it takes you only a minute to generate a block at the current difficulty, it will probably take you billions of years to find a collision with another already used address. See my post from the vanity address thread.
bcearl
Full Member
***
Offline Offline

Activity: 168
Merit: 103



View Profile
July 05, 2011, 07:06:31 PM
 #14

Low chances to get a collision. You could do the same trick with any ECDSA signature, if you could do it with bitcoin.


Assuming that there are 10 million Bitcoin addresses out there in the block chain with value. The ECDSA keys are 256 bit.

This means you have to try out 2^256/10^7 = 1.2 * 10^70 addresses to get a match.

Misspelling protects against dictionary attacks NOT
DamienBlack
Jr. Member
*
Offline Offline

Activity: 56
Merit: 1


View Profile
July 05, 2011, 07:28:35 PM
 #15

The botnet would need many years for reaching a 50% probability of key collision.

Many millions of years.

It's not impossible for a collision to be found, but there's not enough profit in it. Even if someone can find one address every hundred million years, all they get to spend is the balance of that one address. This equates to an averaged cost of fraud of way less than a millionth of a cent per transaction.

It's not worth worrying about, when any simple trojan or social engineering attack is sure to net a few wallets.

Many trillions of year. It is not possible.
bcearl
Full Member
***
Offline Offline

Activity: 168
Merit: 103



View Profile
July 05, 2011, 07:56:25 PM
 #16

The botnet would need many years for reaching a 50% probability of key collision.

Many millions of years.

It's not impossible for a collision to be found, but there's not enough profit in it. Even if someone can find one address every hundred million years, all they get to spend is the balance of that one address. This equates to an averaged cost of fraud of way less than a millionth of a cent per transaction.

It's not worth worrying about, when any simple trojan or social engineering attack is sure to net a few wallets.

Many trillions of year. It is not possible.

Not exactly that easy. As Bitcoin is meant to last a while and computers get faster exponentially, you have to look what's up in 50 years. Bitcoin will adapt newer crypto parameters as times passes, but old bitcoins have to be transferred to new addresses then.

Misspelling protects against dictionary attacks NOT
jrmithdobbs
Newbie
*
Offline Offline

Activity: 67
Merit: 0


View Profile
July 05, 2011, 08:24:21 PM
 #17

The botnet would need many years for reaching a 50% probability of key collision.

Many millions of years.

It's not impossible for a collision to be found, but there's not enough profit in it. Even if someone can find one address every hundred million years, all they get to spend is the balance of that one address. This equates to an averaged cost of fraud of way less than a millionth of a cent per transaction.

It's not worth worrying about, when any simple trojan or social engineering attack is sure to net a few wallets.

Many trillions of year. It is not possible.
Highly improbable. Not impossible.

Let's assume you can gen and encode 2500 pubkeys a second with known privkeys. Right now that's this many days to exhaust the entire key space:

Code:
536074487209797201035050856521703277098472151229817426108599925962560.8
or
Code:
1468697225232321098726166730196447334516362058163883359201643632774.1
years

Now let's assume you can make that 50 times faster ... then it'd take this many days:
Code:
10721489744195944020701017130434065541969443024596348522171998519251.2
or
Code:
146869722523232109872616673019644733451636205816388335920164363277.4
years
DamienBlack
Jr. Member
*
Offline Offline

Activity: 56
Merit: 1


View Profile
July 05, 2011, 08:29:18 PM
 #18

The botnet would need many years for reaching a 50% probability of key collision.

Many millions of years.

It's not impossible for a collision to be found, but there's not enough profit in it. Even if someone can find one address every hundred million years, all they get to spend is the balance of that one address. This equates to an averaged cost of fraud of way less than a millionth of a cent per transaction.

It's not worth worrying about, when any simple trojan or social engineering attack is sure to net a few wallets.

Many trillions of year. It is not possible.
Highly improbable. Not impossible.

Let's assume you can gen and encode 2500 pubkeys a second with known privkeys. Right now that's this many days to exhaust the entire key space:

Code:
536074487209797201035050856521703277098472151229817426108599925962560.8
or
Code:
1468697225232321098726166730196447334516362058163883359201643632774.1
years

Now let's assume you can make that 50 times faster ... then it'd take this many days:
Code:
10721489744195944020701017130434065541969443024596348522171998519251.2
or
Code:
146869722523232109872616673019644733451636205816388335920164363277.4
years


I believe you have a better chance of quantum tunneling a tennis ball through a wall by throwing it. At that point, I call it impossible. And it is for all intents and purposes.
makomk
Hero Member
*****
Offline Offline

Activity: 686
Merit: 564


View Profile
July 05, 2011, 09:10:55 PM
 #19

Now what if someone made a botnet generate addresses all the time, 24/7, and would import those addresses into a wallet.dat to try and see if someone else already generated the address, and has funds 'assigned' to it - essentially trying to find collisions? Wouldn't this be an extremely efficient way to generate addresses until an address was found that held funds, to then steal the funds on that address by transfering them elsewhere?
Not really. Let's try some really ridiculous figures. Suppose that everyone in the world had, on average, 1 million bitcoin addresses with money in. Further suppose that you control a billion computers, each of which can try a billion possible addresses a second. If my calculations are correct, you'd still only find an address every 6.6 million years on average.

Edit: Or another way of looking at it: if you had a billion computers testing a billion addresses per second, on average you'd expect to earn one satoshi every 22 million years.

Quad XC6SLX150 Board: 860 MHash/s or so.
SIGS ABOUT BUTTERFLY LABS ARE PAID ADS
garyrowe
Full Member
***
Offline Offline

Activity: 198
Merit: 102



View Profile WWW
July 05, 2011, 09:38:46 PM
 #20

Now what if someone made a botnet generate addresses all the time, 24/7, and would import those addresses into a wallet.dat to try and see if someone else already generated the address, and has funds 'assigned' to it - essentially trying to find collisions? Wouldn't this be an extremely efficient way to generate addresses until an address was found that held funds, to then steal the funds on that address by transfering them elsewhere?
Not really. Let's try some really ridiculous figures. Suppose that everyone in the world had, on average, 1 million bitcoin addresses with money in. Further suppose that you control a billion computers, each of which can try a billion possible addresses a second. If my calculations are correct, you'd still only find an address every 6.6 million years on average.

Edit: Or another way of looking at it: if you had a billion computers testing a billion addresses per second, on average you'd expect to earn one satoshi every 22 million years.

And given the non-inflationary aspect of Bitcoin, that satoshi would probably get you a cup of coffee.

Pages: [1] 2 3 »  All
  Print  
 
Jump to:  

Powered by MySQL Powered by PHP Powered by SMF 1.1.19 | SMF © 2006-2009, Simple Machines Valid XHTML 1.0! Valid CSS!