How to steal Satoshi's stash?

[DeathAndTaxes]

I thought the public keys were the same as the bitcoin address?

Addresses are the Public Key Hash (PubKeyHash) along with with version and checksum information encoded in Base58.  When you send funds to a user you are sending it to their PubKeyHash (which your client reverses from the address you provide).  This is why one reason why address reuse is discouraged.  Once funds are spent from an address the actual PubKey is known (it included in the input so other nodes can validate the signature).

[1714027192]

1714027192

[1714027192]

1714027192

[1714027192]

1714027192

[vinipoars]

I'm renting my quantum miner. Please, deposit 10000 BTC to the adress below and we'll do the job.
 

Hello borther from the future, if you can go back in time why don't you just start mining with Nakamoto when he released the code, you'll probably be riched if you just want bitcoins

Are you sure I didn't? 

[jonald_fyookball]

I thought the public keys were the same as the bitcoin address?

Addresses are the Public Key Hash (PubKeyHash) along with with version and checksum information encoded in Base58.  When you send funds to a user you are sending it to their PubKeyHash (which your client reverses from the address you provide).  This is why one reason why address reuse is discouraged.  Once funds are spent from an address the actual PubKey is known (it included in the input so other nodes can validate the signature).

Thanks for the info on that, but then how to avoid address resuse?  If i have 10 coins and I send you 2 coins, what I do with the 8 left in my wallet?  Are you saying I have to immediately move
them to another address? 

[jonald_fyookball]

while we're on the topic of "can wallets be bruteforce cracked"...

when we talk about supercomputer speed (petaflops, etc)  (floating point operations) -- how many
floating point operations actually go into trying 1 private key ? 

[DeathAndTaxes]

Thanks for the info on that, but then how to avoid address resuse?  If i have 10 coins and I send you 2 coins, what I do with the 8 left in my wallet?  Are you saying I have to immediately move them to another address? 

Your wallet already does that.  Bitcoin doesn't work on the concept of balances it works on the concept of creating and destroying outputs.

So if you have an output worth 10 BTC and you want to send me two your client creates a tx which destroys the 10 BTC output and creates two new outputs valued at 2 BTC (to me) and 8 BTC (to a new address in your wallet).

while we're on the topic of "can wallets be bruteforce cracked"...

when we talk about supercomputer speed (petaflops, etc)  (floating point operations) -- how many
floating point operations actually go into trying 1 private key ? 

Zero.  We are interested in integer math when brute forcing private keys.  Flops refers to floating point math.  There is no conversion factor which would work for all systems.  Generally speaking computer science doesn't look at the individual implementations to determine if something is infeasible.

As an example say a given computer would require 1000 steps to make one attempt to brute force a key and it will take more energy than 20 of our suns and 10 billion years.  Now lets say you could reduce that to a single step.  Ok now it only takes 1 billion years and more energy than 2 of our suns.  Either way it is infeasible.

Any classical computing problem which is more complex then O (2^128) is generally viewed as infeasible.  Some people use the word improbable but infeasible is a stronger word.  It is improbable you will win the lottery however it is infeasible that you will brute force a 128 bit symmetric key (simply requires material and energy on a scale the human race is utterly incapable of).  In comparison to the lottery it would be like you win seven lotteries in a row by purchasing just a single ticket.

[jonald_fyookball]

it is infeasible that you will brute force a 128 bit symmetric key (simply requires material and energy on a scale the human race is utterly incapable of).

Cool!

I think people just want to know exactly how infeasible it really is...  It can help confidence in bitcoin.

My thinking goes like this:  if there's 2^128 combinations, then if you could try a trillion, trillion combinations
a second, it would take you 8.9 million years.  I'm just wondering if we can really try that many per second.

It sounds like maybe a lot longer to try a private key than to do 1 floating point operation

[DeathAndTaxes]

I think people just want to know exactly how infeasible it really is...  It can help confidence in bitcoin.

Someone with a lot of bitcoins could do a public contest.  Brute forcing a 256 bit ECDSA key (has 128 bit security) is infeasible so nobody would attempt it (well not anyone with any real power) however one could make the problem simpler.

For example move 1,000 BTC to an address and provide publicly half of the private key.  This would mean someone could brute force the key on average in 2^64 attempts.  The blockchain will be proof of if someone accomplished it or not.  Even that would be an incredibly difficult problem, but it is feasible (back to the whole infeasible vs improbable).

If/when someone can steal those coins just keep in mind that brute forcing a full key would be 2^64 = 18,446,744,073,709,600,000 x harder/longer.

[Buffer Overflow]

Why would anyone want to even figure out a way to steal the coins? It would destroy Bitcoin, would it not?

How would it destroy bitcoin?

Would you still use bitcoin if your private key could be derived from your public bitcoin address?

[jonald_fyookball]

I think people just want to know exactly how infeasible it really is...  It can help confidence in bitcoin.

Someone with a lot of bitcoins could do a public contest.  Brute forcing a 256 bit ECDSA key (has 128 bit security) is infeasible so nobody would attempt it (well not anyone with any real power) however one could make the problem simpler.

For example move 1,000 BTC to an address and provide publicly half of the private key.  This would mean someone could brute force the key on average in 2^64 attempts.  The blockchain will be proof of if someone accomplished it or not.  Even that would be an incredibly difficult problem, but it is feasible (back to the whole infeasible vs improbable).

If/when someone can steal those coins just keep in mind that brute forcing a full key would be 2^64 = 18,446,744,073,709,600,000 x harder/longer.

are we correct to assume that to "try" a private key, you'd have to go through all the steps in the SHA256 algo?

[kuroman]

Which is still essentially nothing.  For classical computing you move the timescale from quadrillions of years down to only millions of years.  Congratulations.  

Wait what? did you even read beyond that point? you are partially quoting to prove that you are right is that what you trying to do here? I repeat my self todays computing power 10^15+ so theoritically if classical computing keeps going forward at the same pace it's advanced with since the 60s we will be looking at 10^30 10^40 Flops in the next decade or two which is enough to crack 128bits in a few seconds and we will move on to 10^70 Flops and beyond in another decade or two from there, that is without taking into consideration anything else! which not even remotly true

No we haven't, no key with 128 bit strength has been brute forced. You can't simply compare key size.  A 256 bit ECC key has equivalent strength to a 3,072 bit RSA key and a 128 bit symmetric key/hash.  You may be talking about some individual algorithms being cryptographically broken, it is hard to tell because you are all over the place.  I already pointed out that is possible but it has nothing to do with

You do really have some reading issues, please reread my sentence, and correct your statement I think I was clear enough, I do understand that I make mistakes from time to time because I'm not an english native speaker but please.

No people like me would have been warning that 56 bits was insufficient due to the fact that it was within 1000x of what current computing power was capable of.  That is a far cry from saying 128 bit key strength is secure because it uses energy on a scale that would make brute infeasible.   If we pretend the entire Bitcoin network (30 PH/s) "could" brute force symmetric keys at the same speed instead it would be able to brute force an 80 bit symmetric key in about one year.  If it was 1000x more powerful it could brute force a 96 bit symmetric key in about a century.  If it was a million times powerful it would still take on average a millennium to brute force a 128 bit symmetric key.  To do it in a year would require a system which is a billion times more powerful.

No you woudn't, because people like you did claim the same and it was similar case scenarion in the 80s. And it wasn't x1000 diference I don't even know where are you getting that number from, The Cray Supercomputer from the 80s had 80MFlops or 80x10^6 (The Cray 2 which came in the end of the 80s has 1.2GFlops!) Todays supercomputer for example the Tianhe-2 has a computing power of 34x10^15 ! moving from 56bit to 128 means we squared the difficulty aka (2^56)^2 = 2^128 now if you compare this to computing power and how it is increasing (10^6)^2 = 10^12 <<< 10^15


And again you are taking into consideration CURRENT technology, with CURRENT technology it will take almost infinity to brute force even 128bit not even talking about 256 and I DO NOT DISAGREE WITH THIS, but that's not the point as I've been explaning to you repeatdly you are just being obstined here

None of those (except QC) would do anything more than switching from a teaspoon to a bucket when trying to empty an ocean.  

Wrong as proven above.

Proven doesn't mean what you think it means.  Proven doesn't mean spouting out false statements, gibberish, and strawmen.

False statement? the one you didn't prove wrong or false? the math calculation? the Flops from the supercomputer trough the decades which part is fasle? I'm sorry but you are loosing even more credibility here.

Dwave's system is not capable of implementing Shor's algorithm.  It uses a process called quantum annealing.  Quantum Computing isn't some super duper magical bullet which solves all problems all the time.   Quantum annealing is a pretty cool concept for solving certain types of problems like pathfinding, simulating organic processes, network optimization, etc.   It is completely useless for the purposes of breaking cryptographic keys.

On the progress of building a true general purpose quantum computer capable of implementing shor's algorithm the progress has been very slow.  15 was factored in 2001 using Shor's algorithm and a 4 qubits QC.  By 2012 that had progressed to factoring 21 in using 5 qubits.  One estimate for the total physical qubits (including circuits for error control and correction) necessary for breaking 256 bit ECC is on the order of 40,000 qubits.  We went from 4 to 5 in the space of a decade and the "finish line" is 40,000 qubits.  That could be doubled by switching to a 512 bit curve.  Quantum Decoherence is a bitch.  

The problem becomes increasingly difficult as the size of the computer grows.  It may not be possible to accomplish that in our lifetimes.  Wake me up when someone factors 32 bit number using quantum computing.  If QC becomes a credible threat Bitcoin can evolve to addresses which use post-quantum cryptography.

That's a whole other debate and the only credible paper about on how DWave computer or how much it is a Quantum Computer is this one http://arxiv.org/abs/1401.7087

But Again DWave is by far not the only one in the field.

As for Quantum Annealing is a LEGIT interpretation of Quantum computing, as we are talking about Quantum-mechanical superposition principale here! And when use Quantum Mechanics principales and Quanta to compute, isn't this what Quantum computing is about?

[porcupine87]

Here you have list of all private keys. You can just simply look it up:
http://directory.io/

[DeathAndTaxes]

Flop flop flop flop flops

I am not going to waste my time if you can't even realize that flops aren't ever used in brute forcing private keys.

[kuroman]

Flop flop flop flop flops

I am not going to waste my time if you can't even realize that flops aren't ever used in brute forcing private keys.

lol Mr Obvious (that's to say I don't disagree or rather it's partially true), but aren't the Flops used to represent the computing power of a device? or at least legit way to do so?

[porcupine87]

Brute forcing a 256 bit ECDSA key (has 128 bit security) is infeasible

Sorry, why is it only 128bit security?

[lnternet]

Sorry, why is it only 128bit security?

Best algorithms need around sqrt(#bit) steps, so you have about half the exponent level in bit security.

[kuroman]

Brute forcing a 256 bit ECDSA key (has 128 bit security) is infeasible

Sorry, why is it only 128bit security?

AES-128, RSA-3072 because the size of the corps needs to be approximatly twice as big as the security degree F(2^m)  
Elliptical curbs, the discrete function is O(sqrt(n)) rho Pollard Alghorithm? I'm not sure about the algho

[lnternet]

kuroman, Moore's law will not go on much longer the way it has been advancing by smaller hardware. by ~2020 you reach the point where moore's law requires a transistor the size of an atom. (eg http://www.pcworld.com/article/2032913/the-end-of-moores-law-is-on-the-horizon-says-amd.html)

There could a major break through elsewhere, but it would be a coincidence if that happens to match with Moore's. Anything is this area is wild speculation and will probably not get us anywhere.

[Remember remember the 5th of November]

Here you have list of all private keys. You can just simply look it up:
http://directory.io/

Look harder in the website. Do you see a search button? Figured.

But of course if you call simply look it up the act of traversing 2^256 keys manually, page by page, then you need to visit a mental hospital.

[DeathAndTaxes]

Brute forcing a 256 bit ECDSA key (has 128 bit security) is infeasible

Sorry, why is it only 128bit security?

The fastest known algorithms to derive a private ECC key from the public key are O ( 2^(n/2) ) where n is key length.  Now if the attacker ignores this faster solution and simply tried random (or sequential) private keys until a match was found then it would take much longer (2^256 not 2^128) however security is based on the fastest possible solution.

It is important to point out that the fastest algorithms require the PubKey to be known.  If the PubKey is not known then the only method would be an exhaustive attack on the private key and computing the PubKey.  This is another good reason to not reuse addresses (and thus the pubkey remains unknown).

Key size doesn't necessarily equal security.

All of these key/digest sizes have 128 bit security
128 bit AES (symmetric encryption)
128 bit SHA-2 (hashing algorithm)
256 bit ECC (public key cryptography - elliptical curve)
3,072 bit RSA (public key cryptography - Integer factorization)

Generally hashing algorithms and symmetric key systems have a security equal to their key length (unless they have vulnerabilities or weaknesses).  However due to the nature of public key systems (the public key has a mathematical relationship to the private key) this not true for public key systems.  The key size will always be larger than the effective security (or key strength).  How much larger depends on how difficult it is to derive the private key from the public key.  If you look at RSA and ECC you can see that to achieve the same security RSA requires much larger keys (and signatures).  This makes ECC based systems more useful in decentralized systems like Bitcoin.

[kuroman]

kuroman, Moore's law will not go on much longer the way it has been advancing by smaller hardware. by ~2020 you reach the point where moore's law requires a transistor the size of an atom. (eg http://www.pcworld.com/article/2032913/the-end-of-moores-law-is-on-the-horizon-says-amd.html)

There could a major break through elsewhere, but it would be a coincidence if that happens to match with Moore's. Anything is this area is wild speculation and will probably not get us anywhere.

Actually I've already answered this question, there are many ways to extend the moors law, such as 3D transistors and nanomaterials breaktrough such as Graphen and these aren't vaporware, they already exist, it's just that the manufacturing process needs to be generalised and it will not happen till we start hitting Silicon/Copper limits (as it will require to review the whole fab industry from technics to equipement which requires $$$$) http://e2e.ti.com/blogs_/b/thinkinnovate/archive/2013/03/01/graphene-s-potential-to-extend-moore-s-law.aspx
http://phys.org/news/2014-02-team-aims-graphene-nanoribbon-wires.html

Eventually we will reach the point of quantum mechanics interference, and where the lasers won't be able to keep up, but by that time which is at least a couple of decades ahead of us Quantum computer would operational, todays Quantum computer are still far from it