Double spend attack possible

[leijurv]

Once the leaker reveals the public key, the chunks can be decrypted. Since the private key for the bitcoin addresses aro the hashes of the unencrypted chunks, anyone with the unencrypted chunks has the private key for the bitcoin addresses. If this is done fast enough, the transaction that the leaker sends to redeem the funds can be double spent (e.g. with a higher fee).

[leijurv]

This could be solved fairly easily. Instead of sending the funds to a standard bitcoin address, they could be sent to a P2SH multisig address, with the two public keys being the public key derived from the chink, as well as the leakers own public key. This preserves the attribute that the spending from this address will reveal the public key used to encrypt the chunk.

[809894ac]

Can you elaborate on this attack?

Specfically:

If this is done fast enough, the transaction that the leaker sends to redeem 
the funds can be double spent (e.g. with a higher fee).

Which transaction ? If the leaker spends from the address, the key is revealed. Double spending in that context is a double spend on Bitcoin.

This confuses your proposed solution also, since the leaker still has enough information to spend Bitcoins with a higher fee.

[leijurv]

When the leaker has decided to release the information, he creates a transaction taking the bitcoin he has been paid, and sending it to a separate address he owns, that's the transaction I meant. And this reveals the public key, which allows an attacker to decrypt the chunks, and construct the secret keys for the addresses from the hashes of the chunks. Now imagine that replace-by-fee has been implemented. (apparently it already works some of the time) An attacker could create a transaction spending the same inputs, but sending the money to him instead of to the leaker, with a much higher fee. If this is done and the double-spending transaction broadcasted before the legitimate one is included in a block, the attacker could steal the leaker's bitcoin.

Now imagine that spending from the addresses required the signature of some random key that the leaker owns, as well as the key derived from the hash of the chunks. Spending from the addresses still will reveal the public key derived from the chunk, but it still can't be spent because the private key of the other signing key provided by the leaker is still secret.

[leijurv]

Here's one way this could be done (a sybil attack) : I create a very large amount of fake bitcoin nodes. I make a lot of connections to the leaker's node. Eventually, the leaker's node is only connected to my nodes. Once the leaker broadcasts the spending transaction, all my nodes withhold it from the rest of the network, and create their own double spending transaction. They broadcast that transaction to the network, and I have taken the bitcoin.

[lclc]

You don't have the private key for the addresses, only the public key ones he spends them.

[leijurv]

But aren't the private keys deterministically generated from the checksums of the unencrypted chunks?

[809894ac]

 which allows an attacker to decrypt the chunks, and construct 
the secret keys for the addresses from the hashes of the chunks.

I am beginning to understand, so if a sybil attack could capture the spending transactions from the leaker, it would be trivial to decrypt the chunk, run sha256 to generate a private key and spend the leaker's money before he would be able to. Adding another address/secret prevents this, thus the introduction of the leaker's own address in the scheme.

The critique relies on identifying the leaker, which should not be possible/is part of the security we should hope for.

[leijurv]

It doesn't have to be a sybil attack. Remember the transaction malleability vulnerability? That worked by modifying a transaction as it passed through your node, and hoping that the modified version was confirmed instead of the original. Now imagine a different scenario: you have your node connect to a lot of the biggest mining pools. (and not necessarily connected to the leaker directly) Once your node receives the spending transaction, the node quickly generates the stealing transaction and sends it to the largest mining pools. Assuming that the original transaction hasn't already reached the mining pools, the stealing transaction has pretty good chance of getting confirmed before the spending transaction. While this attack certainly wouldn't work anywhere close to all the time, since there are probably a lot of chunks, a modest success rate is good enough.

[leijurv]

This is also a lot like the bots that steal your bitcoin if you re-use your R value. They do almost this exact same thing, and all the bots "compete" to be the first to get their stealing transaction to a mining pool.

[leijurv]

Apparently, lots of miners already have replace-by-fee in their mempool policy. Therefore, you don't even need to be that fast in creating the stealing transaction, you just have to pay a higher fee and send the stealing transaction to a mining pool with that mempool policy.

[0kino7ori]

Once the leaker reveals the public key, the chunks can be decrypted. Since the private key for the bitcoin addresses are the hashes of the unencrypted chunks, anyone with the unencrypted chunks has the private key for the bitcoin addresses. If this is done fast enough, the transaction that the leaker sends to redeem the funds can be double spent (e.g. with a higher fee).

@leijurv - It makes complete sense, kudos for bringing that up!
In fact, if an attacker possesses the original file (the leaker got it from someone in the first place), the same chunks and private keys could be generated (this time from private to public instead of public to private) since the attacker has access to the chunk size (from the released chunks). So the attacker doesn't even have to wait for the transaction to be redeemed.

This could be solved fairly easily. Instead of sending the funds to a standard bitcoin address, they could be sent to a P2SH multisig address, with the two public keys being the public key derived from the chunk, as well as the leakers own public key. This preserves the attribute that the spending from this address will reveal the public key used to encrypt the chunk.

@leijurv - It looks like a good solution but adds a little burden to the leaker and increases the transaction size. How about adding a random factor to the private key generation? I glanced at the code and the private key appears to be a bitcoin_hash (e.g. double SHA256 hash) of the chunks, which is in fact deterministic.

From the private keys, all public keys could be created before any spending, giving the attacker the power not only to spend transactions, but to sabotage the leak/leaker and reveal all content.

Any thoughts?

[leijurv]

Thanks!
I hadn't thought of that, that the original source of the document could redeem the payment. Perhaps padding each chunk with a few bytes of random data, making each chunk unpredictable even for someone who has an unaltered copy of the original file?

I've been thinking about it, and I'm wondering why the addresses have to be deterministic at all? As far as I can tell, the addresses could be just random addresses that the leaker generates. As long as the chunks are encrypted using the public keys, the private keys could be just about anything, and not have any impact on the working of the system.

[0kino7ori]

Yes, good point, I guess randomness is always a good idea when there's some hashing, back and forth.

I wouldn't tamper with the chunks, though. You could accomplish the same (?) level of protection by adding noise to the hash e then rehashing it into a private key.

As you said, I don't believe the keys need to be deterministic at all. Perhaps the developers chose to avoid pseudo-random number generators?

When you visualize the whole process, you notice that the original chunk was actually encrypted with a secret key (bitcoin public key) which was itself generated from a hash of the very same original chunk. Everything is connected.

I am speculating here, but a cryptographer might argue that it weakens the system. By disconnecting the original chunk from the secret key that is used to encrypt it, the system would avoid any potential weakness while maintaining the functionality.

Are we missing something here?

[leijurv]

Maybe leave the chunks the same, but instead of calculating the hash of the chunk, calculate the hash of (chunk + randomdata)? And maybe you provide the encrypted randomdata in the same place that you are providing the encrypted chunks?

Yeah, I noticed that about it being deterministic. It's basically convergent encryption: http://en.wikipedia.org/wiki/Convergent_encryption

The only property of the system being convergent that might be desirable (as far as I can tell) is that if you try to leak the same file, with the exact same chunks, it will result in the exact same addresses. So you can't leak the exact same file divided up in the same way twice. However, if you change the size/number of chunks, the addresses are different and you can leak it again, so it's not that useful...

[0kino7ori]

The critique relies on identifying the leaker, which should not be possible/is part of the security we should hope for.

@809894ac - I went back to read the issue from the beginning and was captured by this last comment of yours. While I believe the exploit described by @leijurv could be solved early in the private key generation phase instead of the pubkey scipt, would you please explain why an extra address from the leaker would compromise her anonymity? It could be a one-time-throw-away pubkey/address. And the leaker most likely will spend the transaction to one of her addresses anyway.

BTW, thank you for darkleaks and all the inspiring work. It really helped me glue some disconnected project ideas in my head.

[0kino7ori]

Yeah, I noticed that about it being deterministic. It's basically convergent encryption: http://en.wikipedia.org/wiki/Convergent_encryption

@leijurv - Very nice, thanks for sharing! I had never heard about it and yet it seems to relate a lot to what we are discussing.