Deanonymization of the Dero Network: Sender, Receiver, Amounts, and Messages

Full thread: https://twitter.com/kayabaNerve/status/1791485161013694565

Just the technical writeup: https://gist.github.com/kayabaNerve/b754e9ed9fa4cc2c607f38a83aa3df2a

Proof following challenge: https://twitter.com/techleaks24/status/1791512329722442045

Copy of the full technical writeup:

The Dero Protocol

The protocol uses a pair of rings, one for the senders, one for the receivers, represented as a singular ring. With each transfer, a list of ElGamal ciphertexts is provided for all accounts within the joint ring. This ElGamal ciphertext is formed as r * G, (r * K) + (a * G), where r is some randomness, K is the key for the account the ciphertext is for, and a is the amount.

The Dero Wallet Protocol

Dero offers an 'encrypted message' with every transaction. Even if the user does not explicitly provide one, a message will exist (either with internally provided values or left empty). For the only defined type of message, the message is encoded as the index of the sender, a CBOR-encoded object, and zero-padding. The message is encrypted with the Chacha20 stream created by a key of H(H(r * K) || K) where r is some randomness and K is the key for the account the ciphertext is for.

The Issue

Dero reuses the randomness for the ElGamal ciphertexts and the message encryption. This means, if the amount is 0, the second part of the ElGamal ciphertext is the shared key and the message can be decrypted (also revealing the receiver, as the ElGamal ciphertext used is for a specific receiver). If the amount isn't 0, one can subtract 1 * G until the amount term has a 0 coefficient. When the message does decrypt, the amount of subtractions performed is the amount, breaking amount privacy.

Since the first byte of the message is the sender index, this also reveals the sender. In total, this compromises sender, amount, receiver, and message privacy.

Technical Notes

Since the encryption isn't authenticated (as far as the author of this work can tell), we cannot explicitly know if a decryption is valid or invalid. Practically, we can. The last 16 bytes of the message will be zeroes, with very high statistical probability, if the message doesn't fill those bytes and the decryption key is correct. A random decryption key should produce random noise there instead.

If the message does fill those bytes, then it's a long stream of CBOR for which it's unlikely to be valid once further bounds are added. Dero encodes all keys with an additional byte for the type (forcing said byte to be one of a few options and the corresponding value to be of that type). While not a strict limitation, all pre-defined keys are one letter, potentialy practically offering the bound of keys being two-byte ASCII (though that assumes no callers defined their own keys which are either non-ASCII or longer than one letter). With only the certain additional bounds, a CBOR object which takes up the entire space will match random noise approximately once out of every 2**40 trials. It'd be sane to flag CBOR objects which look incorrect (despite passing the trial), and if so, continue brute forcing (the sanest result being the likely one with drastically increasing probability as it appears saner, any result shorter than 129 bytes being effectively certain).

In summary, the trial decryption algorithm is checking if the result is a valid sender index (less than the ring length, for one of the potential senders), checking there's a valid CBOR object with the certain additional bounds, and finally checking the remaining bytes are all zeroes. Distinctly, since there's a lack of authentication (other than setting the sender ring length to 1, its own issue in this context), it's presumed possible for a transaction's sender to claim to be someone else (impersonating them). This is a distinct vulnerability in the messaging protocol, at least as it's being advertised for usage (in place of existing encrypted messengers).

The byte intended for the sender index was historically mistakenly used for the receiver index. This was only patched six months ago in https://github.com/deroproject/derohe/pull/147. Accordingly, sender privacy specifically was only broken for transactions made with wallet software updated to include the patch.

The amount does need to be brute forced. Dero amounts take 41 bits (due to only using 5 decimals and a supply in the low tens of millions), and with the maximum joint ring size of 128 (leaving 64 receivers, or 2**6 candidates), takes 47 bits of effort at most (which is quite feasible for computers). Due to most transactions having smaller than larger amounts, most transactions can be cracked faster than the max time brute force, and statistical analysis could be used to prioritize certain receivers (reducing the average time for any algorithm which is even slightly more right than wrong).

Because this is an attack on the wallet protocol, it can decrypt any message (as the message is part of the wallet protocol). The recovery of the amount, receiver, and sender assume the transaction was made in accordance with the Dero wallet protocol. Theoretically, someone could have their own non-compliant Dero wallet, which either could not have its privacy broken or could provide false readings (depending on if it was programmed to use distinct encryption keys in explicit preparation for a work such as this, making this vulnerability prior discovered). While no such wallets are known to the author of this to work, and are extremely unlikely to exist, that must be noted.

Disclosure Timeline

This issue was found on May 14th, with a proof of concept built the same day. The proof of concept will be released in a week (leaving those affected a bit of time to prepare, though this post is detailed enough to enable independent development of such tools in practice). It isn't optimized to the degree necessary to crack every single transaction on the network now (as it'd need to be rebuilt for GPUs, or potentially ideally FPGAs) yet suffices as a proof of concept.

Dero offers a 50,000 USD bug bounty for vulnerabilities which affect the financial integrity of the blockchain. It includes no details on how to disclose bugs however. The author anonymously reached out to the maintainer of the Dero Project ("Captain Dero") over Matrix to inquire if the bug bounty would still apply and to report their findings. Due to:

1) Not receiving a reply from the maintainer within two days (a fair time to have the initial message acknowledged, per the author's opinion and the opinion of a leading Web3 security platform)
2) Contacting a developer successfully who said "Whatever you're looking at is likely a misunderstanding on your part" (with no context other than there being a critical privacy issue attempting to be disclosed), who then said to submit a PR with my "proposal" (despite it being a security disclosure?), and when emphasized the desire to privately disclose to the maintainer before going public, being told the options were to go public or simply wait until the maintainer gets around to it. When following up a day later to again attempt to cause a successful connection with the maintainer, noting the lack thereof thus far, "Then just disclose it, no need to harass me over it"
3) Deciding users should be made aware as soon as possible so they no longer expect privacy for what would inevitably not have privacy

The author decided to publish this without achieving successful communication with the maintainer. While that does make these findings unconfirmed by the Dero project, the proof of concept establishes the theory works.

Moving Forward

If such a vulnerability was found in Signal, the author of this work would not be able to decrypt all sent messages on the network as they would not have access. By placing messages on a highly replicated ledger, it's trivial for any adversary to obtain the ciphertexts of any message ever sent. This means a wallet compromised years after use can still have all its messages read, and since Dero doesn't use a post-quantum key exchange, any adversary with a discrete log oracle (such as one with a quantum computer) would eventually be able to decrypt all messages. Highly replicated ledgers should not be used for storage of extremely sensitive information in general, even if encrypted. If such a ledger is used regardless, it should be in a forward-secret manner with only a bounded subset of messages being readable on compromise.

The immediate fix for this specific issue is to use distinct randomness for the message encryption key. That alone does not fix the variety of issues with this design (when posited as a secure messaging protocol). For context on the difficulty of secure messaging protocols, please see https://eprint.iacr.org/2022/376 (a 94-page analysis of Signal), Signal's post-quantum protocol https://signal.org/docs/specifications/pqxdh/, the SimpleX documentation and specifications https://github.com/simplex-chat/simplexmq/blob/stable/protocol/overview-tjr.md (which argues themselves a notable improvement upon Signal), and iMessage's extensive work on Contact Key Verification https://security.apple.com/blog/imessage-contact-key-verification. This is an extensive field of theory for a reason.

The Dero (wallet) protocol has largely been undocumented and without peer review. Its proofs for a transfer use a Bulletproofs inner-product at the end, yet the higher-level constructions aren't documented other than one or two incredibly vague comments, such as how they're forming 'one-out-of-many' proofs (which are an explicit thing and it's not contested that the intent of these proofs is to implement one. The question is which it intends to implement). Hopefully, the Dero developers start formalizing their protocol and develop better relations with the wider cryptographic community as to cause peer review and help prevent issues such as this in the future.

To the members of the Dero community, and people in general, the recommendation is to only use secure messengers which have a peer-reviewed protocol and FOSS clients, such as Signal (with Molly being the leading FOSS client). This same line of reasoning also applies to privacy protocols in general, including those which apply to financial transactions. For a private, verifiable protocol for financial transactions, please see Monero or Zcash Orchard (the latter achieves stronger privacy in theory yet has only been deployed on a network which doesn't require all transactions be private).

Finally, the Dero community frequently has very grandiose marketing which claims their technology the best. While it's understandable for fans of a project to believe their project is the best, every project has hard limits. With this effective full-loss of privacy (except for sender privacy on transactions made by wallet software older than ~6 months), may they hopefully acknowledge no one is perfect, and especially not Dero.