Quote from: jl777 on September 14, 2015, 11:04:58 PM

@TimRuffing

in your paper you say that the change can also be shuffled, but I do not see how it can avoid being correlated due to the specific amount of the change relative to the input. What I have done is separate the outputs into the shuffled amounts and change amounts and treat the change outputs at just one step above the normal unspents.

This is a misunderstanding actually. You don't get any privacy for the change, so we don't say that the change can be shuffled. The paragraph in the paper just clarifies that you can add change addresses to the list of output of the CoinJoin transaction in case some peer does not have the exact shuffle amount (which will be almost always the case, just as for ordinary transactions). As far as I understand, this is what your implementation does?

Quote from: Jean-Luc on September 14, 2015, 10:38:55 PM

Quote from: TimRuffing on September 14, 2015, 09:01:03 PM

Each peer must check that there are no duplicate plaintexts after decrypting. Otherwise attacks on unlinkability are possible.

Is that the same as checking that no two recipient addresses are the same, once the shuffle reaches the last participant, or is there more to it?

Multiple participants submitting the same recipient account would be a trivial attack to counteract, however there is no way to protect against a real sybil attack in which multiple participants, each submitting a different recipient address, are actually controlled by the same entity.

Right, this cannot be prevented. The reason checking for checking for duplicates is indeed different and there's more to it than just checking at the end.

Consider a shuffle of 50 participants with peers P1, ..., P50 (in that order). The attacker controls the two peers P2 and P50. Without the duplicate check, the attacker can break the unlinkability of P1 entirely.

The attack is as follows:
P2 (attacker) receives a single ciphertext from P1 (technically, it's a list of ciphertexts with one entry so far) and removes one layer of encryption, resulting in another ciphertext C1. C1 has still 49 layers of encryption and the inner plaintext is the output address OUT1 of P1.

P2 is now supposed to add his own ciphertext C2 (again 49 layers of encryption, inner plaintext his output address OUT2).
However P2 just duplicates the ciphertext C1, i.e., sets C2 = C1. So P2 sends in fact [C1, C1] to P3.

Then the protocol continues normally but P1's output address OUT1 is now the only one that is there twice. Now assume that the honest participants P3, ..., P49 do not check for duplicates after decryption. The last participant P50 (attacker), who removes the innermost layer of encryption, will obtain a list of 50 output addresses. All of these addresses will be different except for P1's output address OUT1, which is the only address that appears twice in the list! So P50 just knows P1's output address, i.e., unlinkability is totally broken for P1.

To ensure that the attack remains undetected, P50 corrects the list of output addresses before publishing it, i.e., P50 replaces one of the OUT1 entries by an address under the control of the attacker. Note that P2 will not complain that his output address is not there in the final list, because P2 is controlled by attacker, too.

So the attacker can fully deanonymize P1 with only two peers in the right positions. In contrast, if the protocol is implemented correctly, the attacker needs 49 peers to fully deanonymize P1, i.e., everybody expect P1 need to be malicious.

This example where the attacker is in the second and the last position is the worst case for P1 and easy to explain, but the attack works also if the attacker is in other positions and wants to decrease the size of the anonymity set for other peers.

Quote from: jl777 on September 14, 2015, 09:35:38 PM

I think you missed that I am generating onetime keypair from the sender side. Only the receiver's pubkey is known.
crypto_box_keypair(onetime_pubkey.bytes,onetime_privkey.bytes);
if ( (cipher= encode_str(&cipherlen,src,len,destpubkey,onetime_privkey,onetime_pubkey)) != 0 )

Since this onetime keypair is generated for each packet, I do not see how this is linkable.

I missed that indeed. However, it is still linkable even with new keypairs: assume again that the attacker controls P2 and P50. Then P2 sees which key belongs to P1, and P50 can use that knowledge the determine P1's output address.

You say that this is fixed now by using a common account. How does that work? Did you also change the encryption scheme? The current scheme needs a the secret key even for encrypting. So I don't see how that should work, because you obviously cannot give that secret key to everybody.