Paper summary: MoneyMorph: Censorship Resistant Rendezvous using Permissionless Cryptocurrencies (PETS 2020)

MoneyMorph: Censorship Resistant Rendezvous using Permissionless Cryptocurrencies
Mohsen Minaei, Pedro Moreno-Sanchez, and Aniket Kate

This paper is about bootstrapping a connection into a censorship circumvention system by steganographically encoding rendezvous information into cryptocurrency transactions. It can be used, for example, by a censored user to retrieve the address of a Tor bridge, in a way that a censor cannot easily block. The unblockability argument rests on the economic importance of cryptocurrencies, and on the covert transactions being indistinguishable from ordinary transactions. The authors formalize a generic “stego-bootstrapping” scheme as a two-way challenge and response, in which a censored user and a remote decoder exchange short messages. The decoder has a public key known in advance, but the user does not. They then describe MoneyMorph, an instantiation of stego-bootstrapping over cryptocurrency transactions, and show that it meets the security goals of rareness (ordinary transactions are not spuriously interpreted as MoneyMorph transactions) and security against chosen-covertext attacks (it is not possible to distinguish a MoneyMorph message from a regular transaction, without the key, even if you control the plaintext of the message). Parties send messages by encoding them into transactions on the public blockchain, keyed so that only the intended recipient may decode them. Receivers scan the blockchain for recent transactions, try to decode them, and act on the ones that are decodable. Specifically, the decoder looks for transactions whose decryption contains a distinguished tag bitstring, and the user looks for a return payment from an address to which it has previously sent a challenge.

MoneyMorph itself is generic over cryptocurrencies: it calls out to an encoding scheme tailored for a specific one. Encoding schemes must produce transactions that are not only syntactically valid, but also do not stand out from other transaction formats commonly found on the blockchain. The authors provide encoding schemes for Bitcoin, Zcash, Monero, and Ethereum. They differ in terms of how much bandwidth they offer and how much they cost to use. In the Bitcoin encoding scheme, for example, the user publishes a transaction with two outputs: one that sends a small amount of Bitcoin to an address the decoder can spend from, and one to an “address” that is really the user’s encrypted message, up to 20 bytes long. The latter coins become permanently unspendable. The decoder uses the user’s sent coins to cover its own costs in sending a response transaction, whose two outputs similarly encode a ciphertext message; these coins too are lost. The Bitcoin encoding scheme provides 20 bytes of bandwidth upstream and 40 bytes downstream, with one exchange costing about 1.25 USD in transaction fees and lost coins. Zcash has the greatest efficiency of the encoding schemes, offering 1148/1168 bytes up/down, at a cost of about 0.01 USD.

Thanks to the authors for commenting on a draft of this summary.