Signature Forging

[Kwothe117]

I'm relatively new so please be patient with me.
So I read a lot about people trying to crack private keys and passwords for wallets but why is there no talk of forging transactions?
No signature is perfectly safe and if you can see it used enough it should be possible to replicate it.
So why aren't people pushing around false transactions and brute forcing until they steal the BTC from someone else? 

[bob123]

To be able to send BTC around you need to first create a Transactions (containing of Inputs/Outputs), and afterwards sign the TX with the corresponding private key(s).
As you (hopefully) already read, it is impossible (in human terms) to 'crack' the private key out of a public key.
Each TX which is not signed with the private key (which only the 'owner of the btc' should have) it will not get accepted by the nodes in the BTC network.
Each node has the ability to verify the signature of the TX's with the corresponding public key. This basically means the following:

• You are able to 'sign' a TX with a private key(only you know)
• Others are able to verify this signature with the public key

There is no possible attack vector in 'forging transactions'.

[Kwothe117]

As you (hopefully) already read, it is impossible (in human terms) to 'crack' the private key out of a public key.

This is where I get confused. I'm still reading into this. Private keys work on the basis of proving that you own the one and only privatekkey and the messages you write with it are indeed your own. But in blockchain, there is nothing hidden so the blockchain cannot verify using a private key. So how does it do that? How does it ensure the transaction uses the right key?

There is no possible attack vector in 'forging transactions'.

Even straight up brute forcing it, it's still possible right? Just not practical because it would take ages or tonnes of computer power.
Just out of curiosity though, if you poured the 1000s of THashes of computing involved in mining to crack a private key, how long do you reckon it would take?
Also, what would happen if you flooded the system (neighboring bitcoin nodes) with 1000s of random guesses?
Sorry for the tonnes of questions....

[Kwothe117]

Okay so I understand more now, a complete brute force would take multiple billion years because of the magnitude of possibilities (2²⁵⁶) Than you to https://bitcoin.stackexchange.com/questions/2847/how-long-would-it-take-a-large-computer-to-crack-a-private-key
But I'm still getting my head around the verification process for checking signatures. Even using the public key to cut down the possibilities there would still be billions of years of computing to crack the key. I was under the impression that you could get more info about the private key from every signature you see but that's incorrect, isn't it?
Also, what would happen if someone were to just send out random falsified transactions? Wouldn't that slow down the other nodes? couldn't you just write all the false transactions and have other nodes verify them?

[ranochigo]

Private keys work on the basis of proving that you own the one and only privatekkey and the messages you write with it are indeed your own. But in blockchain, there is nothing hidden so the blockchain cannot verify using a private key. So how does it do that? How does it ensure the transaction uses the right key?

For each transaction, there are outputs created. These output have specific requirements for it to be spendable. For those in P2PKH, the requirement is for the public key to be able to be hashed to the address.

For every transaction, it contains both the public key and the signature. The nodes can verify that the public key can hash to the address and the signature is signed by that public key.

Even straight up brute forcing it, it's still possible right? Just not practical because it would take ages or tonnes of computer power.

You can probably crack address but not to the extent of forging transactions. Bitcoin is designed in such a way that every transaction is linked until the block which has generated it. Nodes do not trust anyone but themselves.

For a transaction to be valid,
- It has to conform to the protocol rules.
- The inputs can be referenced to a previous transaction.
- The signature on it is valid.

If you can't fulfill any of this, you can't forge transactions.

Just out of curiosity though, if you poured the 1000s of THashes of computing involved in mining to crack a private key, how long do you reckon it would take?

Possibly way after the sun dies. Generating addresses aren't measured in the terahashes. They are measured in the number of keys per second. Current ASIC cannot work to crack private keys.

Also, what would happen if you flooded the system (neighboring bitcoin nodes) with 1000s of random guesses?
Sorry for the tonnes of questions...

Random guesses? After several invalid transactions, they would've banned you.

But I'm still getting my head around the verification process for checking signatures. How can everyone verify the signature without SIGNIFICANTLY reducing the number of guesses required to find the private key?

Public key cryptography allows anyone to verify the validity of a signature using only a public key.

Wouldn't that slow down the other nodes? couldn't you just write all the false transactions and have other nodes verify them?

Honestly, no. Bitcoin Core obviously doesn't let you spam them forever and the resources it takes isn't that much either.

[aplistir]

Also, what would happen if you flooded the system (neighboring bitcoin nodes) with 1000s of random guesses?

Random guesses? After several invalid transactions, they would've banned you.

I do  not know any way how they could ban anyone. But it wouldn't be necessary. verifying that a message is false and ignoring it is a really really quick operation.

And Kwothe117, you would not have to send your false guesses to the network. You could just check if your random guess is correct by yourself on your own computer. It would be much faster too.
Then if your random guess is correct you could broadcast it and it will be accepted in to the blockchain...

[ranochigo]

I do  not know any way how they could ban anyone. But it wouldn't be necessary. verifying that a message is false and ignoring it is a really really quick operation.

If you are broadcasting too many invalid transactions/blocks to any singular node, the node will ban your IP once it reaches the ban threshold. It takes up your precious bandwidth to be receiving invalid transactions repeatedly.

And Kwothe117, you would not have to send your false guesses to the network. You could just check if your random guess is correct by yourself on your own computer. It would be much faster too.
Then if your random guess is correct you could broadcast it and it will be accepted in to the blockchain...

Random guess for transactions? Wait how?

[cr1776]

Also, what would happen if you flooded the system (neighboring bitcoin nodes) with 1000s of random guesses?

Random guesses? After several invalid transactions, they would've banned you.

I do  not know any way how they could ban anyone. But it wouldn't be necessary. verifying that a message is false and ignoring it is a really really quick operation.

And Kwothe117, you would not have to send your false guesses to the network. You could just check if your random guess is correct by yourself on your own computer. It would be much faster too.
Then if your random guess is correct you could broadcast it and it will be accepted in to the blockchain...

If you are flooding neighboring bitcoin nodes (nodes your node is connected to) with 1000s of random guesses they could disconnect you and ban your IP from connecting to them.

As you say though, there is no reason to flood neighborhood nodes like that with “random guesses” to determine they are invalid.

[bob123]

As you (hopefully) already read, it is impossible (in human terms) to 'crack' the private key out of a public key.

This is where I get confused. I'm still reading into this. Private keys work on the basis of proving that you own the one and only privatekkey and the messages you write with it are indeed your own. But in blockchain, there is nothing hidden so the blockchain cannot verify using a private key. So how does it do that? How does it ensure the transaction uses the right key?

When you start initializing an address in your wallet (or when you create an address by your own) what basicaly happens is that your PC will randomly(!) generate a private key (following rules, ofc.).
Out of this private key you can calclulate your public key (an address is the 'visualisation' of a public key). This is a one-way-function. This means you can generate the pub key out of the priv key easily..
but its (in human terms) not possible to calculate the priv key out of the pub key.
And as already mentioned.. Noone needs the private key to verify anything signed with it. You can verify signatures from a private key with the corresponding public key.
I would recommend you to read a bit about asymetric cryptography (https://en.wikipedia.org/wiki/Public-key_cryptography).

There is no possible attack vector in 'forging transactions'.

Even straight up brute forcing it, it's still possible right? Just not practical because it would take ages or tonnes of computer power.
Just out of curiosity though, if you poured the 1000s of THashes of computing involved in mining to crack a private key, how long do you reckon it would take?
Also, what would happen if you flooded the system (neighboring bitcoin nodes) with 1000s of random guesses?
Sorry for the tonnes of questions....

Bruteforcing isn't really 'forging'. Its just trying out every possible combination until you have found the private key you were looking for.

There are 2^160 (~ 1,460,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000) possible priv-/pub- key pairs which can be generated.
In theory you have to search half of the search space until you find a collision (birthday-paradox). So you have to test 2^159 combination until you have found a collision.
1 TH = 1.000.000.000 Hashes  ; 1000 TH/s = 1.000.000.000.000 H/s. So you would basically need 7.307.508.200.000.000.000.000.000.000.000.000.000.000.000 seconds,
which are about 84.577.641.000.000.000.000.000.000.000.000.000.000 (24h-)Days.

I hope that awnsers your question.

[nullius]

So why aren't people pushing around false transactions and brute forcing until they steal the BTC from someone else?  ???

Even straight up brute forcing it, it's still possible right?

And Kwothe117, you would not have to send your false guesses to the network. You could just check if your random guess is correct by yourself on your own computer. It would be much faster too.
Then if your random guess is correct you could broadcast it and it will be accepted in to the blockchain...

Yes, “straight up brute forcing” is indeed possible.  I sincerely suggest that you try this.  It will keep you busy and out of trouble.  To make it easier, there is a public directory of all Bitcoin private keys.  Yes, that site really does list all Bitcoin private keys.  Get rich!  Happy hunting!

(P.S., why are highly intelligent people in a “Development & Technical Discussion” forum seriously answering questions about bruteforcing secp256k1!?  Doubly-hashed, undisclosed public keys are just gravy.)

[Kwothe117]

When you start initializing an address in your wallet (or when you create an address by your own) what basicaly happens is that your PC will randomly(!) generate a private key (following rules, ofc.).
Out of this private key you can calclulate your public key (an address is the 'visualisation' of a public key). This is a one-way-function. This means you can generate the pub key out of the priv key easily..

I see. Seems pretty secure. The last problem that I have then is how hard would it be to imitate the public key? a public key is derived from the private one but it is considerably shorter (64-bit?). Shouldn't multiple private keys match that public key? couldn't it be possible (and easier than a brute force on the private key) to simply find something that hashes out to the private key as it is the only part that is actually verified?

Yes, “straight up brute forcing” is indeed possible.  I sincerely suggest that you try this.  It will keep you busy and out of trouble.  To make it easier, there is a public directory of all Bitcoin private keys.  Yes, that site really does list all Bitcoin private keys.  Get rich!  Happy hunting!

(P.S., why are highly intelligent people in a “Development & Technical Discussion” forum seriously answering questions about bruteforcing secp256k1!?  Doubly-hashed, undisclosed public keys are just gravy.)

I'm just learning here and as I understand this forum's main goal is to educate/demystify/discuss bitcoin. It seems that you understand but I'm just starting to.
I appreciate everyone's help by the way. I know this must seem trivial.

[bakerlisa510]

The private key and the public key is algorithmically related, whatever is encrypted with a Public Key may only be decrypted by its corresponding Private Key and vice versa. Your wallet.dat contains your keypairs that lets you use your coins. If you lose those, you will lose access to your money.
The actual coins, however, are encoded in the Blockchain. Each time you make a payment with your coins, you have to refer to the last time you made such a payment and in case of the Signature what is being signed is indeed a mod version of the entire transaction, which cannot be figured out in a short time until you can the transaction will be already completed. And by the way, until you figure the mathematical algorithm of the keys then you would be already 300 years old.

[bob123]

I see. Seems pretty secure. The last problem that I have then is how hard would it be to imitate the public key? a public key is derived from the private one but it is considerably shorter (64-bit?). Shouldn't multiple private keys match that public key? couldn't it be possible (and easier than a brute force on the private key) to simply find something that hashes out to the private key as it is the only part that is actually verified?

You don't hash the private key to get your public key. The algorithm usd is the Elliptic Curve Digital Signature Algorithm (ECDSA: https://en.bitcoin.it/wiki/Elliptic_Curve_Digital_Signature_Algorithm).
Basically its a multiplication on elliptic curves (x*y). The private key is 256 bits long and the public key is either:
1) Prefix (1 byte) + 256 bit integer (x) + 256 bit integer (y) = 520 bit (for uncompressed public keys) or
2) Prefix (1 byte) + 256 bit integer (x) = 264 bit (for compressed public keys, where the y-value can be derived from the prefix and x-value)

I hope that clears everything.

[DannyHamilton]

I see. Seems pretty secure. The last problem that I have then is how hard would it be to imitate the public key? a public key is derived from the private one but it is considerably shorter (64-bit?). Shouldn't multiple private keys match that public key? couldn't it be possible (and easier than a brute force on the private key) to simply find something that hashes out to the private key as it is the only part that is actually verified?

You don't hash the private key to get your public key. The algorithm usd is the Elliptic Curve Digital Signature Algorithm (ECDSA: https://en.bitcoin.it/wiki/Elliptic_Curve_Digital_Signature_Algorithm).
Basically its a multiplication on elliptic curves (x*y). The private key is 256 bits long and the public key is either:
1) Prefix (1 byte) + 256 bit integer (x) + 256 bit integer (y) = 520 bit (for uncompressed public keys) or
2) Prefix (1 byte) + 256 bit integer (x) = 264 bit (for compressed public keys, where the y-value can be derived from the prefix and x-value)

I hope that clears everything.

I assume that Kwothe117 was making the very common mistake of referring to the bitcoin address as a "public key".  Then he compounded that mistake by assuming that it was only 64 bits long.

Assuming we are talking about the classical P2PKH address type, the bitcoin address is derived from a hash of the public key.  Specifically, the public key is first hashed with SHA256, and then the result of that is hashed with RIPEMD160.  This 160 bit hash value is then encoded in base58 along with an 8-bit version number (telling the network that it is to be used in a P2PKH output script) and a 32-bit checksum (to allow wallets to catch most typing errors).  As such the "address" is actually a 200 bit value, but only 160 bits of that are determined by the choice of key-pair.

While Kwothe117 is incorrect in stating that "multiple private keys match that public key" (there is a one-to-one relationship between private keys and public keys).  He would be correct in stating that multiple key pairs match the same bitcoin address.  In the case of a classical P2PKH address type, there are on average 2⁹⁶ different key pairs that would all result in the same address.

Finding any one of those 2⁹⁶ key pairs is a probability of 1 in 2¹⁶⁰, so it is computationally infeasible to "brute force" with any currently known technology.

[gargavaar]

Finding any one of those 2⁹⁶ key pairs is a probability of 1 in 2¹⁶⁰, so it is computationally infeasible to "brute force" with any currently known technology.

I've heard that quantum computing could do it. Is there any truth to that?

[DannyHamilton]

Finding any one of those 2⁹⁶ key pairs is a probability of 1 in 2¹⁶⁰, so it is computationally infeasible to "brute force" with any currently known technology.

I've heard that quantum computing could do it. Is there any truth to that?

Quantum computing is not any better at brute force than a classical computer. (Note, "brute force" means try a value, see if it works, if it doesn't try another value, repeat the process until a value that you try actually works).

Quantum computing, if the hardware ever advances enough, is theoretically much better at factoring numbers than a classical computer, but (unlike RSA) bitcoin's cryptographic functions don't rely on the difficulty of prime factorization.

Quantum computing might be somewhat better at the discrete logarithm problem that protects bitcoin private keys from the public keys, but bitcoin addresses are HASHES of the public keys.  There aren't any known quantum algorithms that will make it any faster or easier to determine the public key from the bitcoin address. Therefore, if all you have is the bitcoin address, it still won't be computationally feasible to determine the private key.

[gargavaar]

Quantum computing is not any better at brute force than a classical computer. (Note, "brute force" means try a value, see if it works, if it doesn't try another value, repeat the process until a value that you try actually works).

Quantum computing, if the hardware ever advances enough, is theoretically much better at factoring numbers than a classical computer, but (unlike RSA) bitcoin's cryptographic functions don't rely on the difficulty of prime factorization.

Quantum computing might be somewhat better at the discrete logarithm problem that protects bitcoin private keys from the public keys, but bitcoin addresses are HASHES of the public keys.  There aren't any known quantum algorithms that will make it any faster or easier to determine the public key from the bitcoin address. Therefore, if all you have is the bitcoin address, it still won't be computationally feasible to determine the private key.

Ah, that's good to know that bitcoins will still be safe in the foreseeable future. Did some quick and dirty Wikipedia learning, looks like it's mainly RSA that's on the chopping block when/if quantum computers get advanced enough to effectively run Shor's Algorithm.
Is it safe to say that bitcoin is more or less quantum proof then?

[DannyHamilton]

Is it safe to say that bitcoin is more or less quantum proof then?

That will depend on what new algorithms are developed in the future, and how quickly advancements are made on the discrete logarithm problem.

That being said, if it begins to look like weaknesses in Bitcoin could be exploited, then new address algorithms which are secure against quantum computing algorithms could be developed and added to Bitcoin.

[gargavaar]

Is it safe to say that bitcoin is more or less quantum proof then?

That will depend on what new algorithms are developed in the future, and how quickly advancements are made on the discrete logarithm problem.

That being said, if it begins to look like weaknesses in Bitcoin could be exploited, then new address algorithms which are secure against quantum computing algorithms could be developed and added to Bitcoin.

Implementing quantum proof algorithms would require a fork, right?
In any case, let's hope these security measures are implemented quickly if quantum computing takes off in earnest. Even a rumor about the possibility to breach the bitcoin encryption could turn very turbulent.