unforgiven - Unbound recursive function call can use unlimited gas and break hats operation

[sherlock-admin]

unforgiven

medium

Unbound recursive function call can use unlimited gas and break hats operation

Summary

some of the functions in the Hats and HatsIdUtilities contracts has recursive logics without limiting the number of iteration, this can cause unlimited gas usage if hat trees has huge depth and it won't be possible to call the contracts functions. functions getImageURIForHat(), isAdminOfHat(), getTippyTopHatDomain() and noCircularLinkage() would revert and because most of the logics callings those functions so contract would be in broken state for those hats.

Vulnerability Detail

This is function isAdminOfHat() code:

    function isAdminOfHat(address _user, uint256 _hatId) public view returns (bool isAdmin) {
        uint256 linkedTreeAdmin;
        uint32 adminLocalHatLevel;
        if (isLocalTopHat(_hatId)) {
            linkedTreeAdmin = linkedTreeAdmins[getTopHatDomain(_hatId)];
            if (linkedTreeAdmin == 0) {
                // tree is not linked
                return isAdmin = isWearerOfHat(_user, _hatId);
            } else {
                // tree is linked
                if (isWearerOfHat(_user, linkedTreeAdmin)) {
                    return isAdmin = true;
                } // user wears the treeAdmin
                else {
                    adminLocalHatLevel = getLocalHatLevel(linkedTreeAdmin);
                    _hatId = linkedTreeAdmin;
                }
            }
        } else {
            // if we get here, _hatId is not a tophat of any kind
            // get the local tree level of _hatId's admin
            adminLocalHatLevel = getLocalHatLevel(_hatId) - 1;
        }

        // search up _hatId's local address space for an admin hat that the _user wears
        while (adminLocalHatLevel > 0) {
            if (isWearerOfHat(_user, getAdminAtLocalLevel(_hatId, adminLocalHatLevel))) {
                return isAdmin = true;
            }
            // should not underflow given stopping condition > 0
            unchecked {
                --adminLocalHatLevel;
            }
        }

        // if we get here, we've reached the top of _hatId's local tree, ie the local tophat
        // check if the user wears the local tophat
        if (isWearerOfHat(_user, getAdminAtLocalLevel(_hatId, 0))) return isAdmin = true;

        // if not, we check if it's linked to another tree
        linkedTreeAdmin = linkedTreeAdmins[getTopHatDomain(_hatId)];
        if (linkedTreeAdmin == 0) {
            // tree is not linked
            // we've already learned that user doesn't wear the local tophat, so there's nothing else to check; we return false
            return isAdmin = false;
        } else {
            // tree is linked
            // check if user is wearer of linkedTreeAdmin
            if (isWearerOfHat(_user, linkedTreeAdmin)) return true;
            // if not, recurse to traverse the parent tree for a hat that the user wears
            isAdmin = isAdminOfHat(_user, linkedTreeAdmin);
        }
    }

As you can see this function calls itself recursively to check that if user is wearer of the one of the upper link hats of the hat or not. if the chain(depth) of the hats in the tree become very long then this function would revert because of the gas usage and the gas usage would be high enough so it won't be possible to call this function in a transaction. functions getImageURIForHat(), getTippyTopHatDomain() and noCircularLinkage() has similar issues and the gas usage is depend on the tree depth. the issue can happen suddenly for hats if the top level topHat decide to add link, for example:

1. Hat1 is linked to chain of the hats that has 1000 "root hat" and the topHat (tippy hat) is TIPHat1.
2. Hat2 is linked to chain of the hats that has 1000 "root hat" and the topHat (tippy hat) is TIPHat2.
3. admin of the TIPHat1 decides to link it to the Hat2 and all and after performing that the total depth of the tree would increase to 2000 and transactions would cost double time gas.

Impact

it won't be possible to perform actions for those hats and funds can be lost because of it.

Code Snippet

https://github.com/Hats-Protocol/hats-protocol/blob/fafcfdf046c0369c1f9e077eacd94a328f9d7af0/src/Hats.sol#L831-L883

https://github.com/Hats-Protocol/hats-protocol/blob/fafcfdf046c0369c1f9e077eacd94a328f9d7af0/src/Hats.sol#L1022-L1067

https://github.com/Hats-Protocol/hats-protocol/blob/fafcfdf046c0369c1f9e077eacd94a328f9d7af0/src/HatsIdUtilities.sol#L194-L200

https://github.com/Hats-Protocol/hats-protocol/blob/fafcfdf046c0369c1f9e077eacd94a328f9d7af0/src/HatsIdUtilities.sol#L184-L188

Tool used

Manual Review

Recommendation

code should check and make sure that hat levels has a maximum level and doesn't allow actions when this level breaches. (keep depth of each tophat's tree and update it when actions happens and won't allow actions if they increase depth higher than the threshold)

[spengrah]

Tentative solution is to cap the number of nested trees at a reasonable value that ensures the tippy top hat will always be able to exercise its admin rights over the lowest tree, eg 10

1. Count the number of nested trees in the would-be child tree
2. Count the number of nested trees in the would-be parent tree
3. If sum of values (1) and (2) exceeds the cap, revert

We can calculate (1) and (2) by incrementing a counter each step up as we traverse the linkedTreeAdmins mapping, potentially in noCircularLinkage().

cc @zobront

[spengrah]

Will need to test out gas impacts of higher numbers of nested trees to find a good cap value.

[zobront]

@spengrah Agree this is the best solution. Two questions:

• Will you try to cap to an amount where the gas price will be reasonable, or where it'll fit in a block?
• If this differs by chain, will you have different versions by chain, or keep them consistent at mainnet values?

[spengrah]

Great questions @zobront. Overall, I would strongly prefer to not have different versions across different networks, so will likely constrain cheaper / higher capacity networks based on the limits of more expensive networks.

That said, I think it should be up to the user org to determine the cost their willing to spend to add more trees, so overall I think I'm likely to set the cap based on block size rather than gas price.

[spengrah]

@zobront after further research, it's actually going to be pretty expensive to enforce a cap. We can relatively easily count the depth of the would-be parent tree (step 2 above) since we can traverse up the "linked list" of the linkedTreeAdmin mapping. But counting the depth of the would-be child would require a new data model since we need to count down.

So, at this point in the process, what I think is most appropriate is to document this risk and recommend that any tophats that have more than N (say, 10) nested trees below them not grant any authorities to the trees below N.

[spengrah]

@zobront We figured out a fix!

Was thinking that the additional data structure needed to count down would be onerous, but realized that we can just add another mapping that goes the other way, basically creating a doubly-linked list without having to impact the first mapping. So we can now count down pretty easily.

Hats-Protocol/hats-protocol#118

[jacksanford1]

zobront added the "Fix Approved" label