Nxt Forum

Please login or register.

Login with username, password and session length
Advanced search  

News:

Latest Nxt Client 1.11.5 - NEW RELEASE: Ardor 2.0.3e TestNet IS LAUNCHED!

Pages: [1]

Author Topic: Coin Shuffling code review by Tim Ruffing  (Read 1540 times)

Jean-Luc

  • Core Dev
  • Hero Member
  • *****
  • Offline Offline
  • Posts: 1589
    • View Profile
  • Karma: +805/-81
Coin Shuffling code review by Tim Ruffing
November 12, 2015, 05:23:18 pm

This is the review that Tim Ruffing did on our coin shuffling implementation, posted with his permission. I will follow up with my responses to each of his findings.


Code Review for Shuffling
=========================

General Notes
-------------

I looked at the code superficially, and I started at random points. So I did not go line by line through the shuffling process.

The following list contains some problems and some potential problems that I spotted. Of course, there could also be problems that I just did not find.

The review is based on commit feb12c3d07a22efe8f6acbd2a854c3afa4bb19e3, i.e., I did not care about the updates you mentioned in your email. Sorry for that. The reason is just that I started the review before the email but I could not find time to write the results up earlier.

Problems
--------

### Missing duplicate check
The paper says in "Phase 2": "If a decryption fails or if two decryption operations lead to the same output, participant i enters the blame phase." This is crucial for privacy. (I described an attack here: https://bitcointalk.org/index.php?topic=1179305.msg12435878#msg12435878 .)

The check is missing around "REVIEW 1" in the code.

### Length of list of ciphertexts
I think the participants can send lists of ciphertext that are too long or too short in the shuffling. Recipients should check for that and blame the sender if the length is wrong. Also, a case has to be added to the blame phase.

See "REVIEW 5" in the code.


Things I'm not sure about
-----------------------

### Signatures
The paper mandates that all protocol messages are signed. It seems to me that you achieve that by wrapping every message in an attachment of a transaction. Just double-check that this is the case.

### Amounts
I've never seen a check that the input amounts of all participants are the same. I guess it's there, I just could not find it.

### Blame phase in general
In general, you changed a lot in the protocol to make it work with NXT. The blame is unfortunately pretty complicated in the paper and has several cases. I'm not sure if everything is covered in your implementation. In particular, you must make sure that all participants always get the same broadcast messages (Do you ensure that by putting the messages in your blockchain?)

It seems that you use a deposit to really punish the blamed participant. This means that the implementation of the blame phase is really crucial. In the original protocol as described in the paper, an implementation mistake in the (complicated) blame phase just means that the protocol is not resistant against DoS attacks. In your case, an implementation mistake means that a honest participant could lose its deposit, if he's blamed without proper justification.

How do you handle the case that a participant just disappears and never answers?
* If he is blamed and loses money, this means that a faulty machine / crash / loss of power can lead to loss of money, which is a bad idea I think.
* If he is not blamed and does not lose money, then the penalty of losing the deposit does not make much sense in the first place. A clever attacker will just pretend to be offline instead of actively disrupting the protocol.

### Publishing the keys of the encryptor
The idea of the protocol in the blame phase is that the receiver publishes the decryption keys. In your implementation, the sender of a message publishes his secret part of the key exchange. That looks okay superficially but I did not think much about it.

### Final list of recipients
What happens if the last participant sends different final lists to different participants? Since either version of the final transaction is not signed by everybody, nothing bad should happen in this case. It's just that the protocol could get stuck at this point... I don't know if this is covered in your implementation of the blame phase.
Note that weird things can happen, e.g., the last participant could send two version of the correct output list that just differ in the order of the entries.

### Mixing encryption and signature keys
It seems that you use the keys of the signature scheme (EC-KCDSA?) just as keys for an EC Diffie-Hellman key exchange for the encryption. In general, this is not a great idea, because nobody has formally looked at the security. That is, the security proof of EC-KCDSA just does not hold anymore if you re-use the keys for key exchange. Similarly, the security guarantee of the key exchange are not analysed if used together with EC-KCDSA. That does not mean that your scheme is insecure. I guess is secure, but we just do not know at the moment.

### Invalid public keys
I guess your protocol makes sure that the public keys are always valid, i.e., they have the correct length and are valid curve points. (I could not find it in the code.) This is important, because otherwise encryption could fail and you have to deal with that.

See "REVIEW 4" in the code.

### Deterministic nonces
The "nonce" parameter in the encryption function is set to the index of the participant. If a participant creates for some reason two ciphertexts for the same recipient in the same position, this can hurt privacy. I don't see a reason why it should happen but it is just safer to call SecureRandom...

See two instances of "REVIEW 2" in the code.

### secretPhrase
SecretPhrase seems to come from a HTTP request. This looks very suspicious. Shouldn't it be randomly generated?

See "REVIEW 5" in the code.

Misc
----

### Randomness for shuffling
Instead of shuffling randomly, sorting the list of ciphertexts is fine as well. This saves a call to SecureRandom.

See "REVIEW 3" in the code.


GPG key fingerprint: 263A 9EB0 29CF C77A 3D06  FD13 811D 6940 E1E4 240C
NXT-X4LF-9A4G-WN9Z-2R322

Jean-Luc

  • Core Dev
  • Hero Member
  • *****
  • Offline Offline
  • Posts: 1589
    • View Profile
  • Karma: +805/-81

My responses to each point:

>
> ### Missing duplicate check
> The paper says in "Phase 2": "If a decryption fails or if two decryption operations lead to the same output, participant i enters the blame phase." This is crucial for privacy. (I described an attack here: https://bitcointalk.org/index.php?topic=1179305.msg12435878#msg12435878 .)
>
> The check is missing around "REVIEW 1" in the code.


Actually, we did have a duplicates check, but in a different place, done when the transaction object is constructed from json received from peers. But thanks for bringing this to my attention, because I realized that when done this way it allows a rogue participant to sabotage the shuttle and at the same time have the next participant in turn take the blame and the penalty. I have fixed that, now there is a duplicates check both when a received transaction is validated:

ShufflingTransaction.SHUFFLING_PROCESSING.validateAttachment(), line 392

and when a participant decrypts the data sent from the previous participant:

Shuffling.process(), line 489 (ciphertexts are already sorted there).


>
> ### Length of list of ciphertexts
> I think the participants can send lists of ciphertext that are too long or too short in the shuffling. Recipients should check for that and blame the sender if the length is wrong. Also, a case has to be added to the blame phase.
>
> See "REVIEW 5" in the code.
>


The length of ciphertext lists is checked in:

ShufflingTransaction.SHUFFLING_PROCESSING.validateAttachment(), line 383.

Participant number i must submit either i+1 ciphertexts, or 0.

Submitting an empty list is used to indicate that the participant could not decrypt some of the encrypted data, or found another issue with it, e.g, duplicates after decryption, or invalid recipient keys, and doing this triggers entering the blame phase.


>
> Things I'm not sure about
> -----------------------
>
> ### Signatures
> The paper mandates that all protocol messages are signed. It seems to me that you achieve that by wrapping every message in an attachment of a transaction. Just double-check that this is the case.
>

Yes, our transactions have attachments, and what the transaction sender signs is a byte array consisting of all transaction data followed by the attachment represented as bytes. All data exchanged between participants is included in such attachments.

There is one level of indirection when submitting shuffling processing data, what is being signed is not the data itself but a sha256 hash of it. This allows "pruning" the data later, i.e. removing it from the blockchain, while keeping its sha256 hash only so that the transaction signature validity can still be verified.


> ### Amounts
> I've never seen a check that the input amounts of all participants are the same. I guess it's there, I just could not find it.
>

The way it works actually is that the amount to be shuffled is only defined in the ShufflingCreate transaction. When registering for the shuffling, participants have this amount deducted from their "available balance" (called unconfirmed balance in the code for historical reasons). Then, after the shuffling completes successfully, the participants regular balances are also updated accordingly. But each shuffling registration or processing transaction does not need to repeatedly specify the amount again, it only specifies the shuffling id (and shuffling current state), and the amount is taken from there, necessarily the same for all.



> ### Blame phase in general
> In general, you changed a lot in the protocol to make it work with NXT. The blame is unfortunately pretty complicated in the paper and has several cases. I'm not sure if everything is covered in your implementation. In particular, you must make sure that all participants always get the same broadcast messages (Do you ensure that by putting the messages in your blockchain?)
>

Yes, participants never send messages directly to each other. Each message is implemented as an attachment to a transaction, and must be included in the blockchain (which also means every node validates it, not just the next participant). This also allows us to enforce other constraints, such as each participant submitting only one processing transaction (he could submit more, but only one will get included, and if there are different blockchain forks it could happen that on different forks different transactions are included, but eventually one of the forks will win).

Each shuffling processing, or verification, or cancellation transaction, in addition to specifying the shufflingId to which it refers, specifies the current shuffling state, expressed as a 256-bit hash, see Shuffling.Stage.getHash() for how it is calculated depending on the current shuffling stage. This ensures that, if there are different blockchain forks on which the same shuffling has developed in a different way, e.g. with different participants registering for it, or a participant submitting different recipient accounts, each shuffling processing, verification, or cancellation transaction is only valid on the fork on which the shuffling it refers to is in the expected state.


> It seems that you use a deposit to really punish the blamed participant. This means that the implementation of the blame phase is really crucial. In the original protocol as described in the paper, an implementation mistake in the (complicated) blame phase just means that the protocol is not resistant against DoS attacks. In your case, an implementation mistake means that a honest participant could lose its deposit, if he's blamed without proper justification.
>
> How do you handle the case that a participant just disappears and never answers?
> * If he is blamed and loses money, this means that a faulty machine / crash / loss of power can lead to loss of money, which is a bad idea I think.
> * If he is not blamed and does not lose money, then the penalty of losing the deposit does not make much sense in the first place. A clever attacker will just pretend to be offline instead of actively disrupting the protocol.
>

Yes, we use a deposit, and the participant being blamed gets penalized by losing the deposit (it gets added as a forging reward to the account that generated the block in which the shuffling finishes).

I agree it is critical to get the blaming right, and this is why I have written many unit tests, trying to model each situation I could think of in which a shuffling can fail, and verifying that the correct participant takes the blame in each.

If a shuffling is canceled because it fails to enroll the required number of participants, nobody gets blamed.

If a participants registers, but then fails to submit processing transaction, this participant gets blamed (if several participants fail to submit, the first one in line takes the blame). I understand it can happen with no fault of the participant due to machine crash or internet connection loss, but penalizing a possibly innocent party in this case is the lesser evil than allowing any shuffling to be sabotaged at no cost, because indeed it is not possible to determine if the failure to submit was intentional or not.

If a participant registers, and submits processing, but fails to submit either verification, or cancellation, when the verification phase is entered, again such participant is blamed.

To reduce the likelihood of failing to submit a shuffling transaction when required, I have written a Shuffler, which once started takes care of submitting all necessary transactions on behalf of the participant, with no user action needed. If the machine crashes or needs a restart, the user will indeed have to re-start the Shuffler (this could also be automated, but would require saving the user secret phrase to disk, which I prefer to avoid). Also, each participant gets a 100 blocks interval (at one minute blocks, this is 1:40 hours) during which to submit the processing transaction, before it is considered a failure to submit.


> ### Publishing the keys of the encryptor
> The idea of the protocol in the blame phase is that the receiver publishes the decryption keys. In your implementation, the sender of a message publishes his secret part of the key exchange. That looks okay superficially but I did not think much about it.
>

Right, because in our implementation it is the one-time sender key that is unique and not reused. The recipient cannot really publish his decryption key, as this would require disclosing the main secret phrase for his account.

The blame determining logic verifies that the keys that the sender submitted can indeed be used to decrypt the ciphertexts he submitted, encrypted to the corresponding recipient public key. Indeed, here we are making the assumption that the recipient must have also been able to decrypt this ciphertext.


> ### Final list of recipients
> What happens if the last participant sends different final lists to different participants? Since either version of the final transaction is not signed by everybody, nothing bad should happen in this case. It's just that the protocol could get stuck at this point... I don't know if this is covered in your implementation of the blame phase.
> Note that weird things can happen, e.g., the last participant could send two version of the correct output list that just differ in the order of the entries.
>

I don't think it will get stuck, as explained above, our protocol ensures that on each blockchain fork/timeline, only one such transaction exists. Then, as each verification transaction also refers to the current shuffling state hash, which at this stage is dependent on the last participant transaction data, each verification (or cancellation) will be valid on its fork only. Eventually, one of the forks will win, and what happened on this fork is the final truth. Just changing the order of the entries also will change this shuffling state hash.


> ### Mixing encryption and signature keys
> It seems that you use the keys of the signature scheme (EC-KCDSA?) just as keys for an EC Diffie-Hellman key exchange for the encryption. In general, this is not a great idea, because nobody has formally looked at the security. That is, the security proof of EC-KCDSA just does not hold anymore if you re-use the keys for key exchange. Similarly, the security guarantee of the key exchange are not analysed if used together with EC-KCDSA. That does not mean that your scheme is insecure. I guess is secure, but we just do not know at the moment.
>

I have no opinion on that I am afraid, my cryptography knowledge is absolutely minimal I must admit.

I believe the same issue was noted in the first formal review one cryptographer ("DrEvil") performed on the Nxt crypto implementation in general, and his conclusion was again that it is probably ok, see last paragraph in his review:

https://gist.github.com/doctorevil/9521116


> ### Invalid public keys
> I guess your protocol makes sure that the public keys are always valid, i.e., they have the correct length and are valid curve points. (I could not find it in the code.) This is important, because otherwise encryption could fail and you have to deal with that.
>
> See "REVIEW 4" in the code.

To register for a shuffling, an account must sign and submit a transaction, at which point the blockchain stores the public key of that account and verifies the signature on the transaction (which also does the extra enforcement that both the signature and the public key are canonical, see Crypto.verify(), line 143. I assume this is a sufficient indirect verification that the public key of the participant account, used later to encrypt messages to it, is valid.

For the public keys of the intended recipient accounts in the shuffling (which are new accounts, not used before), I added a validation that they are of the correct length and canonical, in several places, see the calls to Crypto.isCanonicalPublicKey().

>
> ### Deterministic nonces
> The "nonce" parameter in the encryption function is set to the index of the participant. If a participant creates for some reason two ciphertexts for the same recipient in the same position, this can hurt privacy. I don't see a reason why it should happen but it is just safer to call SecureRandom...
>
> See two instances of "REVIEW 2" in the code.
>

I think you must have misread the code here, the nonce is not the index of the participant, but the id of the Shuffling. Shuffling id's are guaranteed to be globally unique for the blockchain (shufflingId is equal to the transaction id of the ShufflingCreate transaction). Since within each shuffling there are no duplicate participant accounts, there should be no such key reuse, each invocation of Crypto.getKeySeed (secretPhrase, theirPublicKey, nonce) will be with a different secretPhrase/publicKey/nonce combination.


> ### secretPhrase
> SecretPhrase seems to come from a HTTP request. This looks very suspicious. Shouldn't it be randomly generated?
>
> See "REVIEW 5" in the code.

No, this is fine, this is the secret phrase of the participant, submitted to localhost using the http API, this is normal for our architecture. And it cannot be random, this must be an existing account already funded with Nxt in it, not a creation of a new account.

>
> Misc
> ----
>
> ### Randomness for shuffling
> Instead of shuffling randomly, sorting the list of ciphertexts is fine as well. This saves a call to SecureRandom.
>
> See "REVIEW 3" in the code.

I know, I have been meaning to change this, done now.
GPG key fingerprint: 263A 9EB0 29CF C77A 3D06  FD13 811D 6940 E1E4 240C
NXT-X4LF-9A4G-WN9Z-2R322

Jean-Luc

  • Core Dev
  • Hero Member
  • *****
  • Offline Offline
  • Posts: 1589
    • View Profile
  • Karma: +805/-81

And a confirmation by Tim that all issues have been addressed:

> Thanks again for the review! I hope I have addressed all issues
> discovered so far.

No problem. Just to confirm: All your answers look reasonable and make sense to me.

On 09.11.2015 11:57, Jean-Luc Picard wrote:
>> ### Deterministic nonces
>> The "nonce" parameter in the encryption function is set to the index of the participant. If a participant creates for some reason two ciphertexts for the same recipient in the same position, this can hurt privacy. I don't see a reason why it should happen but it is just safer to call SecureRandom...
>>
>> See two instances of "REVIEW 2" in the code.
>>
>
> I think you must have misread the code here, the nonce is not the index
> of the participant, but the id of the Shuffling. Shuffling id's are
> guaranteed to be globally unique for the blockchain (shufflingId is
> equal to the transaction id of the ShufflingCreate transaction). Since
> within each shuffling there are no duplicate participant accounts,
> there should be no such key reuse, each invocation of
> Crypto.getKeySeed (secretPhrase, theirPublicKey, nonce)
> will be with a different secretPhrase/publicKey/nonce combination.

Indeed, I misread the code here. If you make sure that there are no duplicate participant accounts, then there should be no nonce reuse.

GPG key fingerprint: 263A 9EB0 29CF C77A 3D06  FD13 811D 6940 E1E4 240C
NXT-X4LF-9A4G-WN9Z-2R322

Brangdon

  • Hero Member
  • *****
  • Offline Offline
  • Posts: 1216
  • Quality is addictive.
    • View Profile
  • Karma: +203/-25

Yes, we use a deposit, and the participant being blamed gets penalized by losing the deposit (it gets added as a forging reward to the account that generated the block in which the shuffling finishes).
Does this mean the forger of the final block can effectively evade the penalty? Or has a vested interest in disrupting shuffles so as to collect their deposits? It sounds like if they could, eg, maintain a denial of service attack for 2 hours, they'd stand to gain 1000 NXT.

Although predicting who will forge the final block could be difficult, it might not be that difficult. In future people might put quite a lot of effort into predicting forgers way into the future, tracking which other forgers commonly miss their turns and which forgers don't, over 100s of blocks.

It might be wise to spread the deposit over several forgers, as we are going to do for high-fee transactions.

NXT-RTYD-LJXQ-EPNJ-H7AQ5. Sponsoring 1 public node at brangdon.duckdns.org.

Jean-Luc

  • Core Dev
  • Hero Member
  • *****
  • Offline Offline
  • Posts: 1589
    • View Profile
  • Karma: +805/-81

It is not possible to disrupt a shuffle with a DoS attack, because shuffles don't have a fixed finished height. Each change in the state of the shuffle pushes the finish height 100 blocks in the future, and those are counted not including full blocks. Blocks full of transactions trying to DoS a shuffle will only delay it but cannot prevent its completion.
GPG key fingerprint: 263A 9EB0 29CF C77A 3D06  FD13 811D 6940 E1E4 240C
NXT-X4LF-9A4G-WN9Z-2R322

_mr_e

  • Hero Member
  • *****
  • Offline Offline
  • Posts: 956
    • View Profile
  • Karma: +88/-18

This is some great stuff, could be a big use case for bring some new users to Nxt. I'm curious how is shuffling going to work from the point of view of the user? Will the system create a new account for you with a new passphrase to send the assets to? How does the mixing avoid an attacker watching for odd pattern of assets amounts. Such as 45.5512 assets moving to a new account shortly after a shuffle? Is there a more high level description of how this system is supposed to work for every day people?

NxtSwe

  • Hero Member
  • *****
  • Offline Offline
  • Posts: 659
    • View Profile
  • Karma: +119/-9

This is some great stuff, could be a big use case for bring some new users to Nxt. I'm curious how is shuffling going to work from the point of view of the user? Will the system create a new account for you with a new passphrase to send the assets to? How does the mixing avoid an attacker watching for odd pattern of assets amounts. Such as 45.5512 assets moving to a new account shortly after a shuffle? Is there a more high level description of how this system is supposed to work for every day people?
There's some info here: https://bitbucket.org/JeanLucPicard/nxt/issues/135/coin-shuffling-monetary-system
And all participants must shuffle the same amount.
Check out the NxtLib, the .NET Framework API for the Nxt platform.

Jean-Luc

  • Core Dev
  • Hero Member
  • *****
  • Offline Offline
  • Posts: 1589
    • View Profile
  • Karma: +805/-81

There's some info here: https://bitbucket.org/JeanLucPicard/nxt/issues/135/coin-shuffling-monetary-system
And all participants must shuffle the same amount.
This info is out of date on some points now. We should publish an updated description about how shuffling works from an end user point of view, probably after the UI is ready.
GPG key fingerprint: 263A 9EB0 29CF C77A 3D06  FD13 811D 6940 E1E4 240C
NXT-X4LF-9A4G-WN9Z-2R322
Pages: [1]