Which kind of attack could be executed if SHA-256 would be broken?

[smemo92]

Hi, I've read this page on bitcoin wiki https://en.bitcoin.it/wiki/Contingency_plans#SHA-256_is_broken , mainly the section about sha-256. I'm triyng to understand why and how the attacks specified in this page could be done.
1) Attacker may be able to defeat OP_CHECKSIG, which hashes transactions before signing. I can't understand what means "defeat OP_CHECKSIG". I try to figure out what kind of attack would be related to this: user A sends transaction T to user B. User C intercepts T1 before spreading to the network and if we could crack che second preimage resistance of sha we could find another tx T2 that has the same hash of T1 (this preserve the integrity of the sign for T2). In particular if he could find a transaction T2 that is different from T1 only for the destination address (address X instead B address) (and T1 and T2 have the same hash)  he could modify the destination address and so send T2 to the network (and delete T1). With this operation A's bitcoin will be delivered to some "x" address instead of B. The problem of the attacker is now to obtain a private key of that address x to try to spend it (ECDSA probem)
Is this the attack related to OP_CHECKSIG? Or something else?
2) Attacker may be able to create blocks very quickly. I think this is related to the first preimage resistance: if I could break this properties of sha I could fix a hash value less than the target and I could obtain the header of the block that generates this hash. Even I could be able to do this I will also have a problem. What I obtain from this "reverse" operation has to have a reasonable meaning in bitcoin protocol, I mean that the bit string of a valid header has a structure and I can't use some random bit as an header block because it depends on what transaction the block contains. Even if I include only the coinbase transaction there would be a depence between this transaction and the block (merkle root hash). So what I've understand is that even if someone would be able to crack the first preimage resistance of sha it would be very difficult to mine a block using this attack. It is right what I've supposed?

3? double spend?) This isn't named in the wiki page but I think that if somone would break the second preimage resistance he could execute double-spend. It is similar to 2) attack: suppose I have sent a transaction T1 that now is confirmed. If I could create a transaction T2 to some user B, that has the same hash of T1 and spends the same input, when I spread it into the network other nodes will see that the T2 hash is a hash that it is confirmed in the blockchain yet? At this point every node will discard T2 or T2 will be spread again to the network?or they first will se that those input don't exist between utxo and so discard immediately T2?
Probably I don't understand how to double spend taking advantage of breaking some properties of sha. Have anyone some idea about this? Or double-spend could be done only whit computational power attack?

[johoe]

First, it is unlikely that SHA-256 will be seriously broken in the next year or decade.  In several decades computer power may increase so far that 128 bit security offered by SHA-256 and secp256k no longer feels secure, though.  Also Bitcoin uses double sha-256 which means that even if sha-256 is partly broken it cannot be easily applied to Bitcoin.

Basically a hash can be broken in two ways:
- preimage attack:  find a new clear text message for some fixed hash
- collision attack: find two clear texts messages that have the same hash.

The second attack is much simpler.  The first would take 2^256 steps with brute-force, the second "only" 2^128 steps.

1) Attacker may be able to defeat OP_CHECKSIG, which hashes transactions before signing. I can't understand what means "defeat OP_CHECKSIG".

Suppose there is a collision attack.  An evil attacker may trick you into signing your part of a harmless looking multi-sig transaction that returns most of the money back to your own address but the same signature can then be used for another transaction that sends the money to the attacker.

I try to figure out what kind of attack would be related to this: user A sends transaction T to user B. User C intercepts T1 before spreading to the network and if we could crack che second preimage resistance of sha we could find another tx T2 that has the same hash of T1 (this preserve the integrity of the sign for T2).

possible but unlikely.  You have to be fast, since after a few seconds the transaction has propagated through the network and your fake transaction is a double spent.   Also it requires a preimage attack.

In particular if he could find a transaction T2 that is different from T1 only for the destination address (address X instead B address) (and T1 and T2 have the same hash)  he could modify the destination address and so send T2 to the network (and delete T1). With this operation A's bitcoin will be delivered to some "x" address instead of B. The problem of the attacker is now to obtain a private key of that address x to try to spend it (ECDSA probem)

In a preimage or collision attacks you usually can fix most parts of the transactions and only change an unimportant part (e.g. using an OP_RETURN output, or an output with small value, where you choose a random public key).

2) Attacker may be able to create blocks very quickly. I think this is related to the first preimage resistance: if I could break this properties of sha I could fix a hash value less than the target and I could obtain the header of the block that generates this hash. Even I could be able to do this I will also have a problem. What I obtain from this "reverse" operation has to have a reasonable meaning in bitcoin protocol, I mean that the bit string of a valid header has a structure and I can't use some random bit as an header block because it depends on what transaction the block contains.

There are some random bits: the nonce (and you can misuse some bits of the time-stamp). What you need is a preimage attack that tells you if there is a valid nonce faster than trying all 2^32 possible values for the nonce. You may also try to preimage a merkle-tree hash that would produce a valid block-header hash and then preimage the merkle-tree hash a few times and in the end find a valid coinbase transaction.  However, this sounds much harder.

3? double spend?) ...

I don't think what you described is what happens.  I think there were transactions with the same hash (if the coinbase doesn't contain a unique identifier it happens automatically; now all coinbases contain the block depth for that reason). The Bitcoin full node should not get confused by transactions with the same hash.  Worst case is that some transactions cannot be spent.

Of course, if you can drive attack 2) you easily have 51% and can rewrite history to double-spend your own transactions after they were confirmed.

[Furio]

Since SHA2 hasn't bene broken yet.... I think we're safe Then we can switch to sha512

[hhanh00]

If SHA-256 is broken in such a way that I have an algorithm that instantly tells me what to change in a block of bytes so that the hash = anything you give me:

1. I pick a transaction that you have already signed in the past.
It has a valid signature but it's only valid for a given tx hash.
If you are using the same pub key, there is some other unspent output
I create a tx that sends that to me. The tx hash will be different to start with.
But I can adjust the output and use that as a nonce - I just have to add
an OP_RETURN. By changing the content of that output, I will change the
tx hash. If I know how to reverse sha-256 I know how to make the new
tx hash match the one from the tx that you signed and your coins will be
sent to me.

2. Mining aims to find a block hash < target. If I could find a nonce that makes the blockhash equal to anything I want, obviously the target doesn't matter.
Basically, this is equivalent to have unlimited hashing power. While other people have to work by trial and error, I would have a crystal ball that locates what they are looking for.

But that's a big if. Note that even the previous hashes didn't fail in such a catastrophic way and yet were retired. The crypto community is very cautious.

[DeathAndTaxes]

It depends on what you mean by "broken".   People outside of the cryptography field often treat it is a binary outcome.  A hashing algorithm is either secure or broken when in reality it is a little more complex.

Let take SHA-1 for an example.  Unless a flaw is found there is no faster solution to a collision than a number of operations equal to 2^(hash length/2).  So for SHA-1 (160 bit length = 2^80 operations).  A flaw has been found in SHA-1 which in theory allows a collision to be found in "only" 2^61 operations.  Now that is 524,288x faster than expected (2^19) but 2^61 is still a huge number.   To date no SHA-1 collision has been found however due to Moore's law it is only a matter of time.  The important part is that this weakness was published in 2011.   Here we are in 2015 and there has not only been any real world attack (and yes lots of SSL certs still use SHA-1) there hasn't even been an academic demonstration of a collision such as showing SHA-1("useless blob of data") = SHA-1("a different useless blob of data).   Over the last 30 years breaks in hashing algorithms have occurred incrementally and slowly.  There is no reason to expect this to change in the future.

The second thing to consider is that a collision is not a preimage and for Bitcoin a collision attack would be almost useless to steal Bitcoins or reverse transactions.  A collision occurs when two arbitrary inputs produce he same hash.   For example if you created an address collision in Bitcoin the overwhelming likelihood is that it would be between two unused addresses.   Any effective attack involving bitcoin would need to be a preimage attack.  With SHA-256 that means and expected 2^256 operations. With SHA-1 there is no preimage weakness so it is still the full 2^160 despite being "weak".  Even MD5 which has a preimage weakness still requires 2^123 operations (vs 2^128 expected).

Simple version:
Given enough time it is likely that SHA-2 will eventually be considered "weakened".  That only means that the actual number of operations to find a preimage or collision will be less than the theoretical brute force attack (2^256 and 2^128 respectively).   Just because it is theoretically less secure than expected doesn't mean it is exploitable in the real world.   History has shown it has taken years if not decades to go from academic weakness to an attack with a complexity low enough that it is feasible.   This provides time to extend the protocol to support a stronger algorithm (possibly one which is provably secure or one which doesn't even exist yet).

[DeathAndTaxes]

If SHA-256 is broken in such a way that I have an algorithm that instantly tells me what to change in a block of bytes so that the hash = anything you give me:

That has never happened outside of science fiction. 

[jbrnt]

If I know how to reverse sha-256 I know how to make the new
tx hash match the one from the tx that you signed and your coins will be
sent to me.

Your explaination was very clear and concise. Thanks.
I think Satoshi's solution to your point one, was to never reuse an address. A lot of us are using bitcoin addresses incorrectly. 

[DeathAndTaxes]

Suppose there is a collision attack.  An evil attacker may trick you into signing your part of a harmless looking multi-sig transaction that returns most of the money back to your own address but the same signature can then be used for another transaction that sends the money to the attacker.

That would be a second preimage attack not a collision attack.  The distinction is important as the collision resistance of hashes is significantly lower than the preimage resistance.  Also at least historically preimage resistance has held up significantly better than collision resistance.

[smemo92]

first thanks for answering
I know that sha is secure and every kind of possible attack need a very very very lot of time and computation and so they are not possible to be done but my questions are only for studying purpose of the bitcoin protocol.
I've understand that collision attack is useless for bitcoin and so I've asked only about first and second preimage attack. It seems that the first preimage attack so can involve only block mining, while second preimage attack in some way could involve spend some other's money but still it's not very clear to me how. I've still not understood exactly what "defeat OP_CHECKSIG" means.

Suppose there is a collision attack.  An evil attacker may trick you into signing your part of a harmless looking multi-sig transaction that returns most of the money back to your own address but the same signature can then be used for another transaction that sends the money to the attacker.

That would be a second preimage attack not a collision attack.  The distinction is important as the collision resistance of hashes is significantly lower than the preimage resistance.  Also at least historically preimage resistance has held up significantly better than collision resistance.

ok it is a second preimage attack and If I have understand that it could be a right example of taking favour of break second preimage resistance.

[johoe]

Suppose there is a collision attack.  An evil attacker may trick you into signing your part of a harmless looking multi-sig transaction that returns most of the money back to your own address but the same signature can then be used for another transaction that sends the money to the attacker.

That would be a second preimage attack not a collision attack.  The distinction is important as the collision resistance of hashes is significantly lower than the preimage resistance.  Also at least historically preimage resistance has held up significantly better than collision resistance.

No I meant it as a collision attack.  The scenario could be a CoinJoin transaction.  The attacker claims he wants to do a CoinJoin transaction with you.  He generates both the harmless and the evil transaction with the same hash (more exactly such that OP_CHECKSIG would produce the same hash for your input).  He gives you the harmless to sign.  You check it, see that it looks right, and sign it. Since he didn't sign it you cannot transmit it yourself but you send it back.  The attacker can now use the signature in the evil transaction and send that instead.

[hhanh00]

In a classical collision attack, you don't get to choose the messages. You found two messages that hash to the same value but they would not parse as a transaction. A chosen prefix collision attack is much stronger.