Bitcoin Forum
December 07, 2016, 08:25:13 PM *
News: Latest stable version of Bitcoin Core: 0.13.1  [Torrent].
 
   Home   Help Search Donate Login Register  
Pages: [1] 2 3 »  All
  Print  
Author Topic: Potential attack vector in generating Bitcoin addresses?  (Read 7191 times)
joepie91
Sr. Member
****
Offline Offline

Activity: 294


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.
Advertised sites are not endorsed by the Bitcoin Forum. They may be unsafe, untrustworthy, or illegal in your jurisdiction. Advertise here.
BitcoinPorn
Hero Member
*****
Offline Offline

Activity: 560


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


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
Staff
Legendary
*
Offline Offline

Activity: 1058


฿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: 1316



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


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
Sr. Member
****
Offline Offline

Activity: 294


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
Legendary
*
Offline Offline

Activity: 826


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


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
Jr. Member
*
Offline Offline

Activity: 51



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


View Profile
July 05, 2011, 07:00:36 PM
 #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


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 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


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



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


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.

I trade bitcoin options at https://bitoption.org/ ... Join me.
I play poker at https://betco.in/ ... Join me.
Support the bitcoin economy, what do you do?
Tips: 1NfXhiTFEdKQTdLy49s6DYAP1K7MeFWyao
bcearl
Full Member
***
Offline Offline

Activity: 168



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
Jr. Member
*
Offline Offline

Activity: 59


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

1B8TSDzXdyTRX5eF77gWQoXujBaDtKFE6H
DamienBlack
Jr. Member
*
Offline Offline

Activity: 56


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.

I trade bitcoin options at https://bitoption.org/ ... Join me.
I play poker at https://betco.in/ ... Join me.
Support the bitcoin economy, what do you do?
Tips: 1NfXhiTFEdKQTdLy49s6DYAP1K7MeFWyao
makomk
Hero Member
*****
Offline Offline

Activity: 686


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: 124



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.

Bitcoin enthusiast and Java programmer contributing to https://multibit.org and http://bitcoin.stackexchange.com
Pages: [1] 2 3 »  All
  Print  
 
Jump to:  

Sponsored by , a Bitcoin-accepting VPN.
Powered by MySQL Powered by PHP Powered by SMF 1.1.19 | SMF © 2006-2009, Simple Machines Valid XHTML 1.0! Valid CSS!