---

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.

---