Topic: The case for moving from a 160 bit to a 256 bit Bitcoin address - page 2. (Read 6961 times)

So, the solution to this (for me) is to insist that I'm the one that generates the contract address.  This removes the counterparty's ability to engage in this attack.

If the counterparty is aware of the risk and doesn't have reason to trust me, then their only recourse is to offer the "multiple rounds of communication with commitments".

Since in practice "no one will implement this" AND "most people don't understand this collision vulnerability", the odds are that I can almost always get away with being the one to generate the contract address every time (unless I'm engaged in a transaction with gmaxwell, since he understands enough to know better).  Someone may eventually fall victim to this, but I now understand enough to keep myself safe (from this particular attack).

Yes. Up to a few factors of 2, we're talking orders of magnitude here, not an exact amount of trials.

You've got it.

You should generally think of birthday problem numbers as approximate in any case,  because to achieve the bound you need lots of storage.  A cost optimized solver will make some time/memory tradeoff and usually end up using a couple times more computation than the birthday number in exchange for little to no storage.  (google floyds cycle finding algorithim)

And yes, thats the risk-- that your counterparties degree of freedom in choosing part of the contract will let them find an alternative contract with only collision like work, rather than with second-preimage like work.

You can mitigate by having multiple rounds of communication with commitments, but few to no one will implement this in practice:  Each communication round is a huge software engineering and UI cost, and most people don't understand this collision vulnerability (or _any_ collision vulnerability) even after having it explained.  The longer hash should also be somewhat more secure against second preimages assuming our hash functions become weakened by attacks in the future.

[Basically _any_ time I've seen a collision come up in discussions about the protocols people-- even people who should know better-- get them wrong. Someone on Reddit just the other day argued that a 64-bit collision would take 2^64 work, so I generated one based on his message.. then he argued that I got really lucky to have managed to produce one using only a 32-bit nonce and couldn't provide another, so I did...   they're highly unintuitive to people)

Am I right in assuming that this reduction in security is because the attacker can generate 2⁷⁹ reasonable looking 2-of-2 contracts (and their associated P2SH addresses), and then generate 2⁷⁹ single-signature P2SH addresses, and in doing so would have an extremely high probability of finding an address in the set of 2-of-2 contracts that collides with one of the single-signature P2SH addresses?

2⁷⁹ contracts + 2⁷⁹ single-signature P2SH addresses = 2⁸⁰ generations.

Or more specifically, that the attacker can:

• 1. Generate one 2-of-2 contract and one single-signature P2SH addresses and see if they collide...
• 2. Then generate an additional 2-of-2 contract and see if it collides with ANY of the single-signature P2SH addresses generated so far
• 3. Then generate an additional single-signature P2SH addresse and see if it collides with ANY of the 2-of-2 contracts generated so far
• 4. Repeat steps 2 and 3 until a collision is found

And that in doing so they will succeed, on average, after repeating steps two and three 2⁸⁰ times (although they could get lucky and collide sooner, or get unlucky and collide much later).

Is that the risk here?

The whole point is: you don't need a multisig to get paid out !  I didn't immediately realize this either, but the whole principle of bitcoin is that in order to have the "spending right" of an UTXO, you have to solve a puzzle of which the "question" hashes to the output address of that UTXO.  In a simple transaction, that puzzle is "make a signature that corresponds to the public key that is this hash".  In a 2-2 contract, however, that puzzle is whatever hashes to the given hash ; one such puzzle is the intended multisig: "make a signature that corresponds to the first public key, and make another signature that corresponds to the second public key".
But if you can find *another* puzzle description that hashes to the same hash, the solution to that other puzzle ALSO satisfies the spending requirement of that UTXO.  That other puzzle has nothing to do with the first guy's public key. 
You see, the explicit requirement is not present in the block chain: only its hash is.  So whatever requirement that hashes to the same hash, can be considered as the "true requirement".

Compare it to the following situation: you buy a house, and instead of registering the whole act of sales, you only register its HASH with the notary.   The notary knows that this house goes with that hash, that's all.  So anyone that can write another act of sale, that hashes to the same hash, can act as the owner of the house, the notary will agree, and will let him sell the house while you don't even know it.

Now, the nasty thing with a double signature, is that the guy providing HIS signature has a lever on the true document, and is hence able to find a collision with a document entirely of his making.  This is what reduces the 160 bit second-pre-image security to 80 bit collision security.

gmaxwell,

I have a lot of respect for your knowledge in this area, so I'm pretty sure I'm the one who still isn't understanding.

Edit: Perhaps I am beginning to understand?  By the time I finished writing this post I realized that the 2-set method might not be as difficult as I thought.  My initial assumption (in my earlier post) was 1 address in one set, and multiple addresses in the other set until there was a collision with the single-address set. As I wrote this post it dawned on me that it might be more efficient to generate equal numbers of addresses in each set until one set collided with the other.

Using the public key that I'm provided with, I can generate MANY plausible contracts until two of them collide with each other.  However, this isn't useful, since I won't be able to use either to spend the coins.

I could also generate MANY addresses that let me spend all the coins until two of them collide with each other.  However, this isn't useful, since I won't be able to show my counterparty either of them.

After some thought, I suppose I'd need to generate 2 sets.  I can generate MANY addresses in one set that let me spend all the coins , and then generate MANY plausible contracts in the other set.  I'd have to continue this until an address in set 1 collides with an address in set 2.

I'm not 100% certain on the maths, but (depending on how much more effort the contract generation requires) while that seems to require less effort than my initial example (where the "plausible contracts" set only has 1 address), it would seem to require more effort than the "birthday problem".  My intuition is that on average it requires twice as many P2SH addresses to be generated as the "birthday problem" would (since each new address in one set is effectively a new potential match in the other set)?  If that's right, then I suppose that means it's just one extra "bit" of security over the birthday problem?

I'm sorry if I was unclear.   You are not provided with an address. You are provided with a public key.   Now you construct many possible addresses looking for a pair where one is a plausible contract and the other lets you spend all the coins.

You show your counterparty one, then spend with the other.

Basic pseudo code implementation of algorithm to find hash collisions:


Everything here is easy except the storage of the previous results into the hash table.  Ideally for speed the hash table would contain space for 2¹⁶⁰ private keys.

That is 2¹⁶⁵ bytes!  Not possible.  The largest unit of data we even have today is the yottabyte (2⁸⁰ bytes) and it would take 2⁸⁵ of those to store that much data.

So, even though the loop would need to be run "only" about 2⁸³ (2⁸⁰ if you are lucky) times you would still need to store and search through all the previous results in order to detect the first collision due to the birthday problem/paradox described in the OP.

Danny I was essentially asking the same thing: how do you get the address that you've already found a collision for, into the multisig agreement.

I did, but that won't work for gmaxwell's theoretical attack will it?

The "birthday problem" calculates the odds of ANY TWO addresses in a set matching EACH OTHER.

Unless I'm misunderstanding gmaxwell's post, he's talking about ONE address in a set (the work) matching a specific given address (the contract).

If I roll a 20-sided die until ANY number shows up more than once, we are looking at the "birthday problem".
(Odds improve with every roll until eventually odds are effectively 100%)

If I roll a 20-sided die once, and then roll it again until that initial number re-appears, then we are looking at gmaxwell's post.
(Odds remain at 5% on every roll, with an average of one success out of 20 rolls)

Am I missing something here?

In the "birthday problem" presented in the OP, a collision may occur after 2⁸³ attempts, but the odds of that collision being with an address that actually has bitcoins in it (or ever will) is extremely unlikely (since at any given time there won't be more than 2⁵¹ addresses associated with a UTXO, and in reality significantly less).

In gmaxwell's post, I don't see how finding a collision that doesn't collide with the contract address helps?

Danny,  did you read the OP describing the collision rate calculation?  I was about to pen the algorithm that would be needed.  Will do so soon.

I think I'm missing a piece here on how this attack only requires (on average) 2⁸⁰ attempts.


I can see that I can just generate a 1-of-1 P2SH script with a nonce, and then try MANY nonce values until I get an address that collides with the 2-of-2 contract address.  In that case, I think I can reduce my operations to hashing only, and not need to mess around with multiple private keys and generating public keys.

Once I find an address that collides, I no longer need the victim to sign anything.  I can sign with my private key and can broadcast my nonce based script in the input.  The 2-of-2 contract is no longer important.

What I don't fully understand is how I can expect to see a collision after only 2⁸⁰ attempts.  Wouldn't I need 2¹⁵⁹ attempts just to have a 50% chance of success?

It seems likely that some other attack is being suggested by gmaxwell, but if it is then I've failed to understand how that attack would work.

So once you do that, how does the attack work? How do you get the other party to use the compromised keys in the multisig?

Yes, it took me some time to understand that too.  The "lever arms" are a couple of private keys drawn from a set, that gives rise to a couple of public keys, to be combined with conditions (one is the counterparty's public key, the other is an own public key arbitrarily chosen of which one has the private key), giving rise to two P2SH hashes.  One only needs to test on average a set of 2^80 private keys to find such a couple that has identical such P2SH hashes.
Note that it is somewhat more involved than just testing 2^80 private keys ; one needs to store somehow these results to find out what couple has a collision after the fact.  

I did, but didn't get it, but maybe I do now on rereading: We're talking about a collision of two P2SH addresses. That makes sense.

Did you see the final paragraph in this post?

https://bitcointalksearch.org/topic/m.18832108

Forgive me, but I still don't quite get that. Where does the transaction with a different policy come from? If you only find two colliding addresses yourself, how can you use it for a contract that steals someone else's fund?

Could someone elaborate on this attack?

Besides, doesn't that require you to create 2^80 "proper" addresses. Thus 2^80 times keypair creation plus double hashing?

Well, the room for a full "transaction cycle" consists the room taken for the output on the transaction that has the UTXO, and the corresponding room for the input in the transaction that spends it.  When you look at it, this mainly consists of:

- output amount 8 bytes
- output script, about 25 bytes, of which 20 bytes are the output address (output)

- transaction hash (32 bytes) of the previous output transaction  (input)
- output number of this transaction (4 bytes) (input)
- scriptsig, containing the signature (~64 bytes) AND the pubkey (also, old version ~64 bytes, compact version ~32 bytes)
- 4 bytes "sequence number"

Total usage: about 169 bytes (in compact format)
Of these, 32 bytes (the pub key) are redundant, because one can restore the pub key from the signature and the message.

But:
If an address was only used once, then the transaction hash, and the output number are also redundant (one can find them), and we would save still 36 bytes more.   As such, in the most compact form, if addresses were used only once, we would save 68 bytes out of 169. 

However, the initial argument was that reducing the address from potentially 256 bits to 160 bits "to save space" cannot be correct, because of the wasteful usage of 256 bits of the transaction hash, and 32 bits of the output indication.  If bits were considered expensive, this is where one wasted many of them.
There's no fundamental reason to have more indications of transactions than of addresses for instance, and 32 bits for the output are also overkill.  8 bits would be sufficient I'd think.  Transactions with more than 256 outputs are not very common.

I do not entirely get that.  You need 2^80 work to find a collision, that is to say, to find 2 (new) pub keys that hash to the same address.  But how is this helping in this case, because I have no free choice of *counterparty's* pubkey ?   I could find two different pub keys that hashed to the same address, and use one of them in the contract, but what would I do with the other one ?  

I guess I don't have to tell you that in a collision attack, I cannot "fix" one of the hashes - that's a "second pre-image" attack, not a collision attack, and that doesn't suffer from the birthday paradox.

EDIT: ah, I got it: the collision is between the pub key you generate for the actual 2 - 2 contract, and another pub key you generate, that will result in the same final address but where you master all the conditions, so that in the end, you can entirely satisfy the conditions for the first contract, by using the "proofs" of the second, given that they result in the same final hash.  Right, indeed.

I think you haven't caught the real reason that 256 bit addresses are important.  Any N-bit address has only N/2 bits of security against collision, right?

So here is the interesting attack:  You give me your pubkey, and then I create my pubkey for a 2-of-2 (or some other more elaborate contract), and then we pay to the resulting address.

Oops.  In the background I did ~2^80 work and found a colliding address which didn't have the same policy, and I use it to steal the funds.

2^80 is a lot of work, but it isn't enough to be considered secure by current standards.

Unrelated, it's also the case that many hashes of the same vintage of ripemd160 have been significantly broken or substantially weakened.

You are free to store transactions however you like and negoiate with your peers to send them however you like, there is no need for space to be wasted as a product of serialization.  Using a larger hash does take up more resources but the difference is pretty small compared to the rest of the transaction.