Advisory: secret size attack on cross-chain hash lock smart contracts

atomic-size-attack.md

---

Advisory: secret size attack on cross-chain hash lock smart contracts

Dr. Mark B Lundeberg, 2018 Feb 15 bitcoincash:qqy9myvyt7qffgye5a2mn2vn8ry95qm6asy40ptgx2

This security advisory notes a vulnerability in the common construction of cross-chain smart contracts (contracts between distinct cryptocurrencies) through hash locking. I focus on the primary use case in atomic swap contracts, which allow two cryptocurrencies to changes hands simultaneously and safely. A simple fix is provided.

Review: hash locked atomic swaps the standard way

The canonical bitcoin atomic swap works as follows: Alice prepares a random secret k with a 20-byte hash H=HASH160(k) and then funds the following contract (a P2SH redeem script, which she shows to swap counterparty Bob), in Bitcoin script:

IF
  <BKey> CHECKSIGVERIFY
  HASH160 <H> EQUAL
ELSE
  <AKey> CHECKSIGVERIFY
  <ATime> CHECKLOCKTIMEVERIFY
ENDIF

Meaning of this contract: A signature from Bob's public key BKey in combination with secret k can spend the money. However as a fallback in case of cancellation, a signature from Alice's public key AKey lets her get a refund, but only after ATime.

Bob does not know k, yet. He funds a similar contract on his blockchain using Alice's H value, but with a BTime expiring significantly sooner than ATime:

IF
  <AKey> CHECKSIGVERIFY
  HASH160 <H> EQUAL
ELSE
  <BKey> CHECKSIGVERIFY
  <BTime> CHECKLOCKTIMEVERIFY
ENDIF

Now, Alice may redeem Bob's contract but in doing so, she must reveal k. Bob can now see k which allows him to redeem Alice's contract. If the deal is called off then Bob is allowed to get a refund at BTime, and then Alice can get her refund after ATime. The above setup is generally perceived as perfectly secure and is being proposed for safe on-chain cryptocurrency exchanges that do not involve a third party.

...

But what if Alice could construct a k that works in Bob's contract, and not in her own contract?

The attack

Bitcoin scripts have a maximum allowed data element size of 520 bytes ^ref , which means that k cannot exceed 520 bytes in a valid bitcoin transaction. This arbitrary number, 520 bytes, is not identical in all cryptocurrencies. Although atomic swaps conventionally use a 32 byte secret k, nothing in the above contracts prevents Alice from using a much much larger k.

Let SmallCoin be a cryptocurrency with maximum element size of 520 bytes, and BigCoin be a cryptocurrency with maximum element size of 1000 bytes (or unlimited). Alice owns some SmallCoin and wishes to scam owners of LargeCoin through cross-chain atomic swaps.

1. Alice and Bob agree to exchange her SmallCoins for his LargeCoins via atomic swap.

2. Alice prepares a 700 byte secret k, and proceeds as normal to fund her atomic swap SmallCoin contract with 20-byte hash H=HASH160(k).

3. Bob waits for her contract to confirm, then funds his BigCoin contract (as above) with the same hash H.

4. Alice redeems Bob's contract, revealing k in the process.

5. Bob tries to use Alice's k to redeem Alice's contract, however the size of k is simply too large for SmallCoin and is rejected.

6. Alice waits until her own contract expiry time ATime and is now able to redeem her own contract. She now owns both the SmallCoins and BigCoins, and Bob has nothing.

In step 5, Alice's contract is impossible for Bob to redeem, however he had no way of knowing that since Alice only provided the 20-byte hash H at the start. Bob is screwed the moment he completes step 3; only in step 4 does he finds out the length of k.

With Bitcoin in particular, there is no way for Bob to write a script that constructs a 900 byte string out of smaller pieces, due to scripting language limitations (string concatenation, multiplication, and bit shifting are all disabled opcodes).

The fix

Bob's contract must be modified to include a check on the size of Alice's secret, which forces her to honestly tell him the length beforehand. For example, if she claims her secret is 16 bytes (128 bit strength) then he should write:

IF
  <AKey> CHECKSIGVERIFY
  SIZE 16 EQUALVERIFY HASH160 <H> EQUAL
ELSE
  <BKey> CHECKSIGVERIFY
  <BTime> CHECKLOCKTIMEVERIFY
ENDIF

Alice cannot redeem this script if she lied about the size of k. In Bitcoin script, including SIZE 16 EQUALVERIFY or SIZE 32 EQUALVERIFY only adds 3 or 4 bytes respectively.

Bob must check Alice's contract first, to see whether any possible value of k that satisfies his contract will also satisfy her contract (her contract may have explicit/implicit size limitations).

Affected software

The atomic swaps from decred's setup look to be accidentally immune since the supported cryptocurrencies appear to all be forked from bitcoin and thus have the same 520 byte limit. The contracts do however lack size checks, meaning they will be exploitable when expanding to other cryptocurrencies.

Upon expansion to alien cryptocurrencies like Ethereum, the attack described here will become a concern and can go two ways:

• (Alice has BTC, Bob has ETH) If Bob's ETH contract uses a dynamically-sized bytes array for k values, Alice can steal using a 700 byte k as described above.

• (Alice has ETH, Bob has BTC) If Alice's ETH contract uses a bytes32 fixed-length array for k but Bob's BTC contract permits variable-length k (up to 520 bytes), Alice can steal by using a 64 byte k.

---

Komodo's BarterDEX is already immune from this attack:

BarterDEX is already immune from it as alice validates bob's redeemscript whenever it receives a bob tx, ie. the actual bytes to generate the p2sh address are exchanged, which means not only is the length known, but the exact redeemscript is known.

Nice find. It's an obvious flaw in retrospect but I never thought of it.

You don't need to use OP_SIZE. Just need the trick described in BIP180: https://github.com/bitcoin/bips/blob/master/bip-0180.mediawiki

EDIT: I think the trick only works if the secret size is big. Otherwise, you basically need to expose the secret

Great find. Your fix can be made radically simpler though w/o on chain checks.

SHA256 commits to the length of the string to prevent length extension attacks. By making the hashes a 64 byte nonce, one can just reveal the midstate and prove that any string that could satisfy the hash would be of length 64 bytes.

edit: This is the same thing that @jl2012 is recommending, my bad -- didn't really read the other comments (just scanned to see if anyone mentioned midstates). It does require the nonce to be at least 57 bytes long, but the extra data could be zeros (and hence more easily compressible)

Great find! It's simple, but I've never seen this pointed out before.

Another solution is for Bob's redemption to use

RIPEMD160 <H> EQUAL

(Alice's redemption can still use HASH160.)

Good catch. I propose that the fix is not that the variable length gets encoded into contract, but instead that lengths are always required to be exactly 32 bytes.

We came to the same conclusion regarding a hardcoded required secret size of 32 bytes since there is no reason to work with anything else, but the length must still be encoded in the contract with a size verification so that the redeeming party is capable of auditing the size. This is the updated contract construction that the decred atomic swap tools will be using: https://gist.github.com/jrick/79d3fa2a05424bd4bd67f187cb8a40cd.

@jrick I wrote a new gist that you might be interested in, regarding an alternative atomic swap structure. Nothing to make you worry this time, but rather a way to help anonymize atomic swaps and allow them to work with high-frequency trading:

"SwapChannels: hide your atomic swaps using ordinary payment channels"
https://gist.github.com/markblundeberg/ee027cb12b1e882145bebcd658a1630f

I imagine it's probably too drastic of a change to make on the existing decred/atomicswap codebase, but even then it's something you might want to keep it in mind if there's ever a big overhaul.