Ethernaut Writeup CTF/Wargame

Ethernaut 32 Impersonator

Ethernaut 32 Impersonator 문제 풀이Ethernaut 32 Impersonator writeup

Part 32 of 40 8 min read9 min read
#Web3#Ethernaut#Writeup
Contents

문제

지문

SlockDotIt’s new product, ECLocker, integrates IoT gate locks with Solidity smart contracts, utilizing Ethereum ECDSA for authorization. When a valid signature is sent to the lock, the system emits an Open event, unlocking doors for the authorized controller. SlockDotIt has hired you to assess the security of this product before its launch. Can you compromise the system in a way that anyone can open the door?

코드

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

import "openzeppelin-contracts-08/access/Ownable.sol";

// SlockDotIt ECLocker factory
contract Impersonator is Ownable {
    uint256 public lockCounter;
    ECLocker[] public lockers;

    event NewLock(address indexed lockAddress, uint256 lockId, uint256 timestamp, bytes signature);

    constructor(uint256 _lockCounter) {
        lockCounter = _lockCounter;
    }

    function deployNewLock(bytes memory signature) public onlyOwner {
        // Deploy a new lock
        ECLocker newLock = new ECLocker(++lockCounter, signature);
        lockers.push(newLock);
        emit NewLock(address(newLock), lockCounter, block.timestamp, signature);
    }
}

contract ECLocker {
    uint256 public immutable lockId;
    bytes32 public immutable msgHash;
    address public controller;
    mapping(bytes32 => bool) public usedSignatures;

    event LockInitializated(address indexed initialController, uint256 timestamp);
    event Open(address indexed opener, uint256 timestamp);
    event ControllerChanged(address indexed newController, uint256 timestamp);

    error InvalidController();
    error SignatureAlreadyUsed();

    /// @notice Initializes the contract the lock
    /// @param _lockId uinique lock id set by SlockDotIt's factory
    /// @param _signature the signature of the initial controller
    constructor(uint256 _lockId, bytes memory _signature) {
        // Set lockId
        lockId = _lockId;

        // Compute msgHash
        bytes32 _msgHash;
        assembly {
            mstore(0x00, "\x19Ethereum Signed Message:\n32") // 28 bytes
            mstore(0x1C, _lockId) // 32 bytes
            _msgHash := keccak256(0x00, 0x3c) //28 + 32 = 60 bytes
        }
        msgHash = _msgHash;

        // Recover the initial controller from the signature
        address initialController = address(1);
        assembly {
            let ptr := mload(0x40)
            mstore(ptr, _msgHash) // 32 bytes
            mstore(add(ptr, 32), mload(add(_signature, 0x60))) // 32 byte v
            mstore(add(ptr, 64), mload(add(_signature, 0x20))) // 32 bytes r
            mstore(add(ptr, 96), mload(add(_signature, 0x40))) // 32 bytes s
            pop(
                staticcall(
                    gas(), // Amount of gas left for the transaction.
                    initialController, // Address of `ecrecover`.
                    ptr, // Start of input.
                    0x80, // Size of input.
                    0x00, // Start of output.
                    0x20 // Size of output.
                )
            )
            if iszero(returndatasize()) {
                mstore(0x00, 0x8baa579f) // `InvalidSignature()`.
                revert(0x1c, 0x04)
            }
            initialController := mload(0x00)
            mstore(0x40, add(ptr, 128))
        }

        // Invalidate signature
        usedSignatures[keccak256(_signature)] = true;

        // Set the controller
        controller = initialController;

        // emit LockInitializated
        emit LockInitializated(initialController, block.timestamp);
    }

    /// @notice Opens the lock
    /// @dev Emits Open event
    /// @param v the recovery id
    /// @param r the r value of the signature
    /// @param s the s value of the signature
    function open(uint8 v, bytes32 r, bytes32 s) external {
        address add = _isValidSignature(v, r, s);
        emit Open(add, block.timestamp);
    }

    /// @notice Changes the controller of the lock
    /// @dev Updates the controller storage variable
    /// @dev Emits ControllerChanged event
    /// @param v the recovery id
    /// @param r the r value of the signature
    /// @param s the s value of the signature
    /// @param newController the new controller address
    function changeController(uint8 v, bytes32 r, bytes32 s, address newController) external {
        _isValidSignature(v, r, s);
        controller = newController;
        emit ControllerChanged(newController, block.timestamp);
    }

    function _isValidSignature(uint8 v, bytes32 r, bytes32 s) internal returns (address) {
        address _address = ecrecover(msgHash, v, r, s);
        require (_address == controller, InvalidController());

        bytes32 signatureHash = keccak256(abi.encode([uint256(r), uint256(s), uint256(v)]));
        require (!usedSignatures[signatureHash], SignatureAlreadyUsed());

        usedSignatures[signatureHash] = true;

        return _address;
    }
}

배경지식

ECDSA는 Elliptic Curve Digital Signature Algorithm의 줄임말로, 타원곡선 디지털 서명 알고리즘이다. ECDSA는 보통 다음 세 가지를 보장하기 위해 쓰인다.

  • 인증: 이 서명이 특정 개인키 소유자에게서 나왔는지 확인
  • 무결성: 메시지가 바뀌지 않았는지 확인
  • 부인 방지: 개인키 없이는 같은 서명을 만들기 어렵게 함

ECDSA는 암호화 알고리즘이 아니라, 특정 개인키 소유자가 어떤 메시지에 서명했다는 사실을 증명하기 위해 사용된다.

ECDSA는 보통 소수체 위의 타원곡선을 쓴다. 소수 pp에 대한 유한체는 다음처럼 쓴다.

Fp={0,1,2,…,p−1}\mathbb{F}_p = \{0,1,2,\dots,p-1\}

곡선 위의 좌표 계산은  mod p\bmod p로 진행한다. 일반적인 타원곡선은 다음과 같다.

E:y2≡x3+ax+b(modp)E: y^2 \equiv x^3 + ax + b \pmod p

곡선 위의 점들은 다음 조건을 만족해야 한다.

(x,y)∈Fp2(x,y)\in\mathbb{F}_p^2

여기에 항등원인 무한원점 OO를 추가한다.

타원곡선 위의 점들은 덧셈 연산을 가진다. 점 P=(x1,y1),Q=(x2,y2)P=(x_1,y_1), \quad Q=(x_2,y_2)에 대해 P+Q=(x3,y3)P+Q = (x_3,y_3)는 다음과 같은 규칙에 따라 계산된다. 먼저 P와 Q가 다를 때의 기울기는 다음과 같이 구한다.

λ≡y2−y1x2−x1(modp)\lambda \equiv \frac{y_2-y_1}{x_2-x_1} \pmod p

이때 나눗셈은 모듈러 역원 곱셈으로 진행한다.

ab≡a⋅b−1(modp)\frac{a}{b} \equiv a\cdot b^{-1}\pmod p

좌표는 다음과 같이 계산된다.

x3≡λ2−x1−x2(modp)x_3 \equiv \lambda^2 - x_1 - x_2 \pmod p

y3≡λ(x1−x3)−y1(modp)y_3 \equiv \lambda(x_1-x_3)-y_1 \pmod p

P와 Q가 같을 때, 즉 2P=P+P2P=P+P인 경우에는 계산이 조금 다르다. 기울기는 다음과 같다.

λ≡3x12+a2y1(modp)\lambda \equiv \frac{3x_1^2+a}{2y_1} \pmod p

각 좌표는 위와 비슷하게 계산된다.

x3≡λ2−2x1(modp)x_3 \equiv \lambda^2 - 2x_1 \pmod p

y3≡λ(x1−x3)−y1(modp)y_3 \equiv \lambda(x_1-x_3)-y_1 \pmod p

ECDSA에서는 점의 덧셈을 반복해서 스칼라 곱을 계산한다.

kG=G+G+⋯+G⏟k번kG = \underbrace{G+G+\cdots+G}_{k\text{번}}

여기서

  • GG: 기준점
  • kk: 정수
  • kGkG: 타원곡선 위의 다른 점

이다. 이 연산은 계산하기는 쉽지만, 반대로

Q=dGQ = dG

가 주어졌을 때 d를 찾는 것은 매우 어렵다고 알려져 있다. 이 어려움이 타원곡선 이산로그 문제, ECDLP다. ECDSA는 ECDLP에 기반한다. ECDSA를 쓰려면 먼저 곡선의 파라미터가 정해져 있어야 한다. 보통 다음 값들이 공개된다.

(p,a,b,G,n,h)(p,a,b,G,n,h)

각 의미는 다음과 같다.

  • pp: 유한체의 크기를 결정하는 소수
  • a,ba, b: 타원곡선의 계수
  • GG: 기준점
  • nn: GG의 부분군의 위수
  • hh: cofactor

기준점 G의 부분군의 위수가 nn이라는 것은,

nG=OnG = \mathcal{O}

이고 그보다 작은 양의 정수 tt에 대해

tG=OtG = \mathcal{O}

가 되지 않는다는 뜻이다. ECDSA에서는 보통 nn이 큰 소수이다. 개인키 dd는 정수 하나를 사용한다.

d∈{1,2,…,n−1}d \in \{1,2,\dots,n-1\}

공개키는 다음처럼 잡는다.

Q=dGQ=dG

여기서 QQ는 타원곡선 위의 점이다.

개인키 dd로 공개키 QQ를 계산하는 것은 쉽다.

하지만 공개키 QQ와 기준점 GG만 보고 dd를 찾는 것은 어렵다.

서명할 메시지를 mm이라고 하자. ECDSA는 메시지 전체를 직접 서명하지 않고, 먼저 해시한다.

e=H(m)e = H(m)

그다음 이 해시값을 정수로 해석하고, 보통 이를 z로 둔다.

z=int⁡(H(m))z = \operatorname{int}(H(m))

단, 해시 길이가 nn의 비트 길이보다 길면 왼쪽부터 필요한 만큼 잘라 쓴다.

개인키 dd로 메시지 mm에 서명한다고 하자. 먼저 무작위 정수 kk를 고른다.

k∈{1,2,…,n−1}k \in \{1,2,\dots,n-1\}

이 kk는 노출되거나 재사용하면 안 된다.

이제 점 RR을 계산한다.

R=kGR = kG

그리고 RR을 좌표로 쓰면 다음과 같다.

R=(xR,yR)R = (x_R, y_R)

서명의 첫 번째 값 rr은 xRx_R에서 만든다.

r≡xR(modn)r \equiv x_R \pmod n

만약 r=0r=0이라면 다른 kk를 골라야 한다.

주의할 점은 xRx_R은 Fp\mathbb{F}_p의 원소지만, rr을 만들 때는 xRx_R를 정수로 해석한 뒤  mod n\bmod n을 취한다.

서명의 두 번째 값 ss는 다음처럼 계산한다.

s≡k−1(z+rd)(modn)s \equiv k^{-1}(z + rd) \pmod n

만약 s=0s = 0이면 다른 kk를 골라 다시 진행한다.

최종 서명은 (r,s)(r,s)이다.

검증자는 메시지 mm, 서명 (r,s)(r,s), 공개키 QQ를 가진다.

개인키 dd는 모른다.

먼저 서명값이 유효한 범위 안에 있는지 확인한다.

1≤r,s≤n−11\le r, s \le n-1

범위를 벗어나면 거절한다.

그 다음 메시지 해시와 ss의 역원을 계산한다.

z=int⁡(H(m))w≡s−1(modn)\begin{aligned} z &= \operatorname{int}(H(m)) \\ w &\equiv s^{-1} \pmod n \end{aligned}

검증자는 이 값들로 u1u_1, u2u_2, XX를 만든다.

u1≡zw(modn)u2≡rw(modn)X=u1G+u2Q\begin{aligned} u_1 &\equiv zw \pmod n \\ u_2 &\equiv rw \pmod n \\ X &= u_1G + u_2Q \end{aligned}

XX를 좌표로 쓰면 다음과 같다.

X=(xX,yX)X = (x_X, y_X)

서명이 유효하려면 다음 조건이 성립해야 한다.

r≡xX(modn)r \equiv x_X \pmod n

이 검증이 성립하는 이유는 식으로 확인할 수 있다. 서명 과정에서 다음 식이 있었다.

s≡k−1(z+rd)(modn)s \equiv k^{-1}(z + rd) \pmod n

양변에 kk를 곱하면 다음과 같다.

ks≡z+rd(modn)ks \equiv z + rd \pmod n

다시 양변에 s−1s^{-1}를 곱한다.

k≡s−1(z+rd)(modn)k \equiv s^{-1}(z+rd) \pmod n

검증 과정에서 w=s−1w = s^{-1}라고 잡았으므로 다음처럼 쓸 수 있다.

k≡w(z+rd)(modn)k \equiv w(z+rd) \pmod n

이를 전개한다.

k≡wz+wrd(modn)k \equiv wz + wrd \pmod n

검증자는 u1=zwu_1 = zw, u2=rwu_2 = rw로 계산한다. 따라서 다음 관계가 나온다.

k≡u1+u2d(modn)k \equiv u_1 + u_2d \pmod n

이제 양변에 GG를 곱한다.

kG≡(u1+u2d)G=u1G+u2dG\begin{aligned} kG &\equiv (u_1 + u_2d)G \\ &= u_1G + u_2dG \end{aligned}

공개키가 Q=dGQ = dG이므로 위 식은 다음처럼 바뀐다.

kG=u1G+u2QkG = u_1G + u_2Q

즉 검증자가 계산한 점은 다음과 같다.

X=u1G+u2Q=kG=RX = u_1G + u_2Q = kG = R

결론적으로 서명자가 만든 rr과 검증자가 계산한 XX의 xx좌표가 같아야 한다.

r=xR mod n=xX mod nr = x_R \bmod n = x_X \bmod n

ECDSA에서 가장 위험한 부분은 kk다. 서명식은 다음과 같다.

s≡k−1(z+rd)(modn)s\equiv k^{-1}(z + rd) \pmod n

이를 개인키 dd에 대해 정리하면 다음 식이 된다.

d≡r−1(sk−z)(modn)d \equiv r^{-1}(sk - z) \pmod n

즉 공격자가 kk를 알면 개인키 dd를 바로 구할 수 있다.

두 메시지 m1m_1, m2m_2에 대해 같은 kk를 써서 서명했다고 하자.

각 해시를 z1z_1, z2z_2라 하고, 서명을 (r,s1)(r,s_1), (r,s2)(r,s_2)라 하자.

같은 kk를 쓰면 R=kGR=kG가 나오므로 같은 rr이 나온다. 각 서명식은 다음과 같다.

s1≡k−1(z1+rd)(modn)s2≡k−1(z2+rd)(modn)\begin{aligned} s_1 &\equiv k^{-1}(z_1 + rd) \pmod n \\ s_2 &\equiv k^{-1}(z_2 + rd) \pmod n \end{aligned}

두 식을 빼면 개인키 항이 사라진다.

s1−s2≡k−1(z1−z2)(modn)s_1 - s_2 \equiv k^{-1}(z_1-z_2) \pmod n

따라서 kk는 다음처럼 구할 수 있다.

k≡z1−z2s1−s2(modn)k \equiv \frac{z_1-z_2}{s_1-s_2} \pmod n

모듈러 나눗셈을 역원 곱셈으로 쓰면 다음과 같다.

k≡(z1−z2)(s1−s2)−1(modn)k \equiv (z_1-z_2)(s_1-s_2)^{-1} \pmod n

kk를 구하면 개인키도 복구할 수 있다.

d≡r−1(s1k−z1)(modn)d \equiv r^{-1}(s_1k-z_1) \pmod n

위의 설명대로라면 서명은 (r,s)(r, s)로 검증할 수 있다. Ethereum 서명에는 vv 값도 들어간다. Ethereum에서는 ecrecover(z, v, r, s)와 같은 함수를 쓴다. ecrecover는 서명이 유효하면 서명자의 주소를, 실패하면 address(0)을 반환하는 함수이다.

이더리움 주소는 공개키에서 만들어진다. 공개키를 Q=(xQ,yQ)Q=(x_Q,y_Q)라 하면, 대략 다음과 같이 주소가 정해진다.

hash=keccak256(xQ∣∣yQ)hash = keccak256(x_Q || y_Q)

이 hash의 마지막 20바이트가 주소가 된다. 따라서 ecrecover가 서명으로부터 공개키 QQ를 복구할 수 있다면, 그 공개키에 대응되는 주소도 구할 수 있다.

문제는 서명에 들어있는 rr이 원래 서명 과정에서 만든 점 R=kGR=kG의 xx좌표에서 나온다는 점이다.

타원곡선에서는 같은 xx값을 가진 점이 보통 (x,y)(x, y), (x,−y)(x, -y) 두 개가 있다.

즉 rr만으로는 둘 중 어느 점이 실제 RR인지 알 수 없다.

이때 어느 쪽 점을 써야 하는지 알려주는 recovery id가 vv이다. 이 문제에서는 일반적인 Ethereum 서명처럼 vv가 27 또는 28로 들어온다.

문제 코드 분석

Impersonator는 factory 역할을 하는 컨트랙트다. owner만 deployNewLock을 호출할 수 있고, 이 함수는 ECLocker를 새로 배포한다.

solidity
function deployNewLock(bytes memory signature) public onlyOwner {
    ECLocker newLock = new ECLocker(++lockCounter, signature);
    lockers.push(newLock);
    emit NewLock(address(newLock), lockCounter, block.timestamp, signature);
}

NewLock 이벤트에는 signature가 그대로 찍힌다. 즉, 공격자는 새 lock이 만들어질 때 사용된 초기 controller의 서명을 이벤트 로그에서 얻을 수 있다.

ECLocker의 생성자를 보면 먼저 lock마다 고정된 메시지 해시를 만든다.

solidity
assembly {
    mstore(0x00, "\x19Ethereum Signed Message:\n32")
    mstore(0x1C, _lockId)
    _msgHash := keccak256(0x00, 0x3c)
}

즉 서명 대상 메시지는 lockId이다. 이 값은 msgHash에 저장되고, 이후 open이나 changeController에서도 계속 같은 msgHash를 사용한다. 그 다음 생성자로 받은 _signature에서 v, r, s를 꺼내 ecrecover를 호출한다.

solidity
mstore(ptr, _msgHash)
mstore(add(ptr, 32), mload(add(_signature, 0x60)))
mstore(add(ptr, 64), mload(add(_signature, 0x20)))
mstore(add(ptr, 96), mload(add(_signature, 0x40)))

ecrecover precompile의 입력은 (hash, v, r, s) 순서이므로, _signature는 일반적인 (r, s, v) 형태로 들어온다. 복구된 주소는 initialController가 되고, 이 주소가 lock의 controller로 설정된다.

다음은 서명 재사용 방지다.

solidity
usedSignatures[keccak256(_signature)] = true;

생성자에서는 _signature 전체 bytes를 해시해서 사용 처리한다. 그런데 실제 검증 함수에서는 다른 방식으로 서명을 해시한다.

solidity
bytes32 signatureHash = keccak256(abi.encode([uint256(r), uint256(s), uint256(v)]));
require (!usedSignatures[signatureHash], SignatureAlreadyUsed());

즉 constructor에서는 keccak256(_signature)을 쓰고, _isValidSignature에서는 keccak256(abi.encode([r, s, v]))를 쓴다. 같은 서명이라도 해시되는 bytes 형태가 다르기 때문에, 생성자에서 사용 처리한 서명이 검증 함수에서는 사용된 것으로 인식되지 않는다. 이벤트에서 얻은 초기 서명을 그대로 재사용하는 것도 가능하다. 다만 여기서는 ECDSA 서명 자체의 malleability도 사용할 수 있다.

open과 changeController는 둘 다 _isValidSignature만 통과하면 실행된다.

solidity
function changeController(uint8 v, bytes32 r, bytes32 s, address newController) external {
    _isValidSignature(v, r, s);
    controller = newController;
    emit ControllerChanged(newController, block.timestamp);
}

그리고 _isValidSignature는 ecrecover(msgHash, v, r, s)의 결과가 현재 controller와 같은지만 확인한다.

solidity
address _address = ecrecover(msgHash, v, r, s);
require (_address == controller, InvalidController());

여기서 s 값이 lower half인지 확인하지 않고, OpenZeppelin의 ECDSA.recover 같은 안전한 래퍼도 쓰지 않는다. 따라서 같은 서명자 주소로 복구되는 다른 형태의 서명을 만들 수 있다. 결국 공격 방향은 다음과 같다.

  1. NewLock 이벤트에서 초기 서명 (r, s, v)를 얻는다.
  2. 원본 서명을 그대로 쓰거나, malleability를 이용해 다른 유효 서명을 만든다.
  3. 그 서명으로 changeController를 통과해 controller를 address(0)으로 바꾼다.
  4. 이후에는 잘못된 서명을 넣어 ecrecover가 address(0)을 반환하게 만들면 누구나 open을 호출할 수 있다.

풀이

이제 이벤트에서 얻은 서명이 있다고 하자.

(r,s,v)(r,s,v)

위에서 봤듯이 원본 서명을 그대로 재사용하는 것도 가능하다. 여기서는 ECDSA malleability를 이용해 다른 유효 서명을 만든다.

서명 검증에서 계산되는 점은 결국 RR의 xx좌표와 관련된다.

그런데 RR과 −R-R은 yy좌표만 반대이고 xx좌표는 같다.

따라서 RR 대신 −R-R을 만들 수 있으면 같은 rr로도 검증을 통과할 수 있다.

기존 검증에서

R=s−1zG+s−1rQR = s^{-1}zG + s^{-1}rQ

였다면, ss를 −s-s로 바꿨을 때는 다음과 같이 된다.

(−s)−1zG+(−s)−1rQ=−s−1(zG+rQ)=−R(-s)^{-1}zG + (-s)^{-1}rQ = -s^{-1}(zG+rQ) = -R

즉 ss를 −s-s로 대체하면 −R-R을 만들 수 있고, RR과 −R-R은 같은 xx좌표를 가지므로 같은 rr 검증을 통과한다.

−s-s는 음수 그대로 넣는 것이 아니라  mod n\bmod n 위에서 표현해야 한다.

−s≡n−s(modn)-s \equiv n - s \pmod n

따라서 새 ss 값은 n−sn-s가 된다.

이제 vv도 같이 바꿔야 한다.

vv는 27과 28을 사용하는데, 둘 중 어느 yy좌표를 가진 RR을 쓸지 나타내는 값이다.

RR을 −R-R로 바꿨으니 vv도 반대 값으로 바꿔야 한다.

vv가 27 또는 28이라면 반대 값은 다음처럼 구할 수 있다.

v′=55−vv' = 55 - v

따라서 원본 서명 대신 다음 값을 사용한다.

(r,n−s,55−v)(r,n-s,55-v)

이 값은 원본과 다른 서명이지만 같은 controller 주소로 복구된다.

익스플로잇

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

import "forge-std/Script.sol";

interface IECLocker {
    function changeController(uint8 v, bytes32 r, bytes32 s, address newController) external;
}

contract Sol32 is Script {
    uint256 private constant SECP256K1_N = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141;

    function run() external {
        uint256 privateKey = vm.envUint("PRIVATE_KEY");
        IECLocker target = IECLocker(0x46887e09d735a4E2081A253cD78c656093183bD2);
        bytes memory signature =
            hex"1932cb842d3e27f54f79f7be0289437381ba2410fdefbae36850bee9c41e3b9178489c64a0db16c40ef986beccc8f069ad5041e5b992d76fe76bba057d9abff21b";

        uint8 v;
        bytes32 r;
        bytes32 s;

        assembly {
            r := mload(add(signature, 0x20))
            s := mload(add(signature, 0x40))
            v := byte(0, mload(add(signature, 0x60)))
        }

        vm.startBroadcast(privateKey);
        target.changeController(55 - v, r, bytes32(SECP256K1_N - uint256(s)), address(0));
        vm.stopBroadcast();
    }
}

Challenge

Description

SlockDotIt’s new product, ECLocker, integrates IoT gate locks with Solidity smart contracts, utilizing Ethereum ECDSA for authorization. When a valid signature is sent to the lock, the system emits an Open event, unlocking doors for the authorized controller. SlockDotIt has hired you to assess the security of this product before its launch. Can you compromise the system in a way that anyone can open the door?

Code

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

import "openzeppelin-contracts-08/access/Ownable.sol";

// SlockDotIt ECLocker factory
contract Impersonator is Ownable {
    uint256 public lockCounter;
    ECLocker[] public lockers;

    event NewLock(address indexed lockAddress, uint256 lockId, uint256 timestamp, bytes signature);

    constructor(uint256 _lockCounter) {
        lockCounter = _lockCounter;
    }

    function deployNewLock(bytes memory signature) public onlyOwner {
        // Deploy a new lock
        ECLocker newLock = new ECLocker(++lockCounter, signature);
        lockers.push(newLock);
        emit NewLock(address(newLock), lockCounter, block.timestamp, signature);
    }
}

contract ECLocker {
    uint256 public immutable lockId;
    bytes32 public immutable msgHash;
    address public controller;
    mapping(bytes32 => bool) public usedSignatures;

    event LockInitializated(address indexed initialController, uint256 timestamp);
    event Open(address indexed opener, uint256 timestamp);
    event ControllerChanged(address indexed newController, uint256 timestamp);

    error InvalidController();
    error SignatureAlreadyUsed();

    /// @notice Initializes the contract the lock
    /// @param _lockId uinique lock id set by SlockDotIt's factory
    /// @param _signature the signature of the initial controller
    constructor(uint256 _lockId, bytes memory _signature) {
        // Set lockId
        lockId = _lockId;

        // Compute msgHash
        bytes32 _msgHash;
        assembly {
            mstore(0x00, "\x19Ethereum Signed Message:\n32") // 28 bytes
            mstore(0x1C, _lockId) // 32 bytes
            _msgHash := keccak256(0x00, 0x3c) //28 + 32 = 60 bytes
        }
        msgHash = _msgHash;

        // Recover the initial controller from the signature
        address initialController = address(1);
        assembly {
            let ptr := mload(0x40)
            mstore(ptr, _msgHash) // 32 bytes
            mstore(add(ptr, 32), mload(add(_signature, 0x60))) // 32 byte v
            mstore(add(ptr, 64), mload(add(_signature, 0x20))) // 32 bytes r
            mstore(add(ptr, 96), mload(add(_signature, 0x40))) // 32 bytes s
            pop(
                staticcall(
                    gas(), // Amount of gas left for the transaction.
                    initialController, // Address of `ecrecover`.
                    ptr, // Start of input.
                    0x80, // Size of input.
                    0x00, // Start of output.
                    0x20 // Size of output.
                )
            )
            if iszero(returndatasize()) {
                mstore(0x00, 0x8baa579f) // `InvalidSignature()`.
                revert(0x1c, 0x04)
            }
            initialController := mload(0x00)
            mstore(0x40, add(ptr, 128))
        }

        // Invalidate signature
        usedSignatures[keccak256(_signature)] = true;

        // Set the controller
        controller = initialController;

        // emit LockInitializated
        emit LockInitializated(initialController, block.timestamp);
    }

    /// @notice Opens the lock
    /// @dev Emits Open event
    /// @param v the recovery id
    /// @param r the r value of the signature
    /// @param s the s value of the signature
    function open(uint8 v, bytes32 r, bytes32 s) external {
        address add = _isValidSignature(v, r, s);
        emit Open(add, block.timestamp);
    }

    /// @notice Changes the controller of the lock
    /// @dev Updates the controller storage variable
    /// @dev Emits ControllerChanged event
    /// @param v the recovery id
    /// @param r the r value of the signature
    /// @param s the s value of the signature
    /// @param newController the new controller address
    function changeController(uint8 v, bytes32 r, bytes32 s, address newController) external {
        _isValidSignature(v, r, s);
        controller = newController;
        emit ControllerChanged(newController, block.timestamp);
    }

    function _isValidSignature(uint8 v, bytes32 r, bytes32 s) internal returns (address) {
        address _address = ecrecover(msgHash, v, r, s);
        require (_address == controller, InvalidController());

        bytes32 signatureHash = keccak256(abi.encode([uint256(r), uint256(s), uint256(v)]));
        require (!usedSignatures[signatureHash], SignatureAlreadyUsed());

        usedSignatures[signatureHash] = true;

        return _address;
    }
}

Background

ECDSA stands for Elliptic Curve Digital Signature Algorithm. ECDSA is typically used to provide three guarantees:

  • Authentication: verifies that the signature came from the holder of a specific private key
  • Integrity: verifies that the message has not been modified
  • Non-repudiation: makes it hard to produce the same signature without the private key

ECDSA is not an encryption algorithm. It is used to prove that the holder of a specific private key signed a given message.

ECDSA usually works over an elliptic curve defined over a prime field. The finite field for a prime pp is written as follows.

Fp={0,1,2,…,p−1}\mathbb{F}_p = \{0,1,2,\dots,p-1\}

Coordinate arithmetic on the curve is done  mod p\bmod p. A general elliptic curve looks like this.

E:y2≡x3+ax+b(modp)E: y^2 \equiv x^3 + ax + b \pmod p

Points on the curve must satisfy the following.

(x,y)∈Fp2(x,y)\in\mathbb{F}_p^2

On top of that, we add the point at infinity OO as the identity element.

Points on an elliptic curve have an addition operation. For points P=(x1,y1),Q=(x2,y2)P=(x_1,y_1), \quad Q=(x_2,y_2), P+Q=(x3,y3)P+Q = (x_3,y_3) is computed by the following rules. First, when P and Q are different, the slope is computed as follows.

λ≡y2−y1x2−x1(modp)\lambda \equiv \frac{y_2-y_1}{x_2-x_1} \pmod p

Division here is done as multiplication by the modular inverse.

ab≡a⋅b−1(modp)\frac{a}{b} \equiv a\cdot b^{-1}\pmod p

The coordinates are computed as follows.

x3≡λ2−x1−x2(modp)x_3 \equiv \lambda^2 - x_1 - x_2 \pmod p

y3≡λ(x1−x3)−y1(modp)y_3 \equiv \lambda(x_1-x_3)-y_1 \pmod p

Now consider the case where P and Q are equal, i.e. 2P=P+P2P=P+P. The slope is as follows.

λ≡3x12+a2y1(modp)\lambda \equiv \frac{3x_1^2+a}{2y_1} \pmod p

Each coordinate is computed similarly to the above.

x3≡λ2−2x1(modp)x_3 \equiv \lambda^2 - 2x_1 \pmod p

y3≡λ(x1−x3)−y1(modp)y_3 \equiv \lambda(x_1-x_3)-y_1 \pmod p

In ECDSA, scalar multiplication is computed by repeated point addition.

kG=G+G+⋯+G⏟k timeskG = \underbrace{G+G+\cdots+G}_{k\text{ times}}

where

  • GG: base point
  • kk: an integer
  • kGkG: another point on the elliptic curve

This operation is easy to compute, but in the other direction, given

Q=dGQ = dG

finding d is known to be very hard. This hardness is the elliptic curve discrete logarithm problem, ECDLP. ECDSA is based on ECDLP. To use ECDSA, the curve parameters must be fixed first. The following values are usually public.

(p,a,b,G,n,h)(p,a,b,G,n,h)

Their meanings are as follows.

  • pp: the prime that determines the size of the finite field
  • a,ba, b: the coefficients of the elliptic curve
  • GG: base point
  • nn: the order of the subgroup generated by GG
  • hh: cofactor

The order of the subgroup generated by base point G being nn means that

nG=OnG = \mathcal{O}

and for no smaller positive integer tt does

tG=OtG = \mathcal{O}

hold. In ECDSA, nn is usually a large prime. The private key dd is a single integer.

d∈{1,2,…,n−1}d \in \{1,2,\dots,n-1\}

The public key is defined as follows.

Q=dGQ=dG

Here QQ is a point on the elliptic curve.

Computing the public key QQ from the private key dd is easy.

But finding dd given only the public key QQ and the base point GG is hard.

Let mm be the message to sign. ECDSA does not sign the whole message directly; it hashes it first.

e=H(m)e = H(m)

This hash is then interpreted as an integer, usually denoted z.

z=int⁡(H(m))z = \operatorname{int}(H(m))

If the hash is longer than the bit length of nn, only the leftmost bits needed are used.

Suppose we sign message mm with private key dd. First, pick a random integer kk.

k∈{1,2,…,n−1}k \in \{1,2,\dots,n-1\}

This kk must never be leaked or reused.

Now compute the point RR.

R=kGR = kG

Writing RR in coordinates gives the following.

R=(xR,yR)R = (x_R, y_R)

The first signature value rr is derived from xRx_R.

r≡xR(modn)r \equiv x_R \pmod n

If r=0r=0, a different kk must be chosen.

xRx_R is an element of Fp\mathbb{F}_p, but to produce rr it is interpreted as an integer and then reduced  mod n\bmod n.

The second signature value ss is computed as follows.

s≡k−1(z+rd)(modn)s \equiv k^{-1}(z + rd) \pmod n

If s=0s = 0, pick a different kk and start over.

The final signature is (r,s)(r,s).

The verifier has the message mm, the signature (r,s)(r,s), and the public key QQ.

The verifier does not know the private key dd.

First, check that the signature values are within the valid range.

1≤r,s≤n−11\le r, s \le n-1

If they are out of range, reject.

Next, compute the message hash and the inverse of ss.

z=int⁡(H(m))w≡s−1(modn)\begin{aligned} z &= \operatorname{int}(H(m)) \\ w &\equiv s^{-1} \pmod n \end{aligned}

From these values the verifier builds u1u_1, u2u_2, and XX.

u1≡zw(modn)u2≡rw(modn)X=u1G+u2Q\begin{aligned} u_1 &\equiv zw \pmod n \\ u_2 &\equiv rw \pmod n \\ X &= u_1G + u_2Q \end{aligned}

Writing XX in coordinates gives the following.

X=(xX,yX)X = (x_X, y_X)

For the signature to be valid, the following must hold.

r≡xX(modn)r \equiv x_X \pmod n

Why this verification works can be shown algebraically. During signing we had the following equation.

s≡k−1(z+rd)(modn)s \equiv k^{-1}(z + rd) \pmod n

Multiplying both sides by kk gives the following.

ks≡z+rd(modn)ks \equiv z + rd \pmod n

Then multiply both sides by s−1s^{-1}.

k≡s−1(z+rd)(modn)k \equiv s^{-1}(z+rd) \pmod n

Since verification defines w=s−1w = s^{-1}, we can write this as follows.

k≡w(z+rd)(modn)k \equiv w(z+rd) \pmod n

Expanding it:

k≡wz+wrd(modn)k \equiv wz + wrd \pmod n

The verifier computes u1=zwu_1 = zw and u2=rwu_2 = rw. This gives the following relation.

k≡u1+u2d(modn)k \equiv u_1 + u_2d \pmod n

Now multiply both sides by GG.

kG≡(u1+u2d)G=u1G+u2dG\begin{aligned} kG &\equiv (u_1 + u_2d)G \\ &= u_1G + u_2dG \end{aligned}

Since the public key is Q=dGQ = dG, this becomes the following.

kG=u1G+u2QkG = u_1G + u_2Q

So the point the verifier computes is the following.

X=u1G+u2Q=kG=RX = u_1G + u_2Q = kG = R

In conclusion, the rr produced by the signer must equal the xx coordinate of the XX computed by the verifier.

r=xR mod n=xX mod nr = x_R \bmod n = x_X \bmod n

The most dangerous part of ECDSA is kk. The signing equation is as follows.

s≡k−1(z+rd)(modn)s\equiv k^{-1}(z + rd) \pmod n

Solving for the private key dd gives the following.

d≡r−1(sk−z)(modn)d \equiv r^{-1}(sk - z) \pmod n

So if an attacker knows kk, they can recover the private key dd immediately.

Suppose two messages m1m_1 and m2m_2 are signed with the same kk.

Let their hashes be z1z_1 and z2z_2, and the signatures be (r,s1)(r,s_1) and (r,s2)(r,s_2).

Using the same kk yields the same R=kGR=kG, and therefore the same rr. The signing equations are as follows.

s1≡k−1(z1+rd)(modn)s2≡k−1(z2+rd)(modn)\begin{aligned} s_1 &\equiv k^{-1}(z_1 + rd) \pmod n \\ s_2 &\equiv k^{-1}(z_2 + rd) \pmod n \end{aligned}

Subtracting the two cancels out the private key term.

s1−s2≡k−1(z1−z2)(modn)s_1 - s_2 \equiv k^{-1}(z_1-z_2) \pmod n

So kk can be computed as follows.

k≡z1−z2s1−s2(modn)k \equiv \frac{z_1-z_2}{s_1-s_2} \pmod n

Writing modular division as multiplication by the inverse:

k≡(z1−z2)(s1−s2)−1(modn)k \equiv (z_1-z_2)(s_1-s_2)^{-1} \pmod n

Once kk is known, the private key can be recovered as well.

d≡r−1(s1k−z1)(modn)d \equiv r^{-1}(s_1k-z_1) \pmod n

By the explanation above, a signature can be verified with (r,s)(r, s). Ethereum signatures also carry a vv value. Ethereum uses a function like ecrecover(z, v, r, s). ecrecover returns the signer's address if the signature is valid, and address(0) on failure.

An Ethereum address is derived from the public key. If the public key is Q=(xQ,yQ)Q=(x_Q,y_Q), the address is determined roughly as follows.

hash=keccak256(xQ∣∣yQ)hash = keccak256(x_Q || y_Q)

The last 20 bytes of this hash become the address. So if ecrecover can recover the public key QQ from a signature, it can also derive the corresponding address.

The catch is that rr in the signature comes from the xx coordinate of the point R=kGR=kG created during signing.

On an elliptic curve, there are usually two points with the same xx value: (x,y)(x, y) and (x,−y)(x, -y).

So rr alone does not tell you which of the two is the actual RR.

The recovery id vv tells you which point to use. In this challenge, as with typical Ethereum signatures, vv is either 27 or 28.

Code analysis

Impersonator is a factory contract. Only the owner can call deployNewLock, which deploys a new ECLocker.

solidity
function deployNewLock(bytes memory signature) public onlyOwner {
    ECLocker newLock = new ECLocker(++lockCounter, signature);
    lockers.push(newLock);
    emit NewLock(address(newLock), lockCounter, block.timestamp, signature);
}

The NewLock event logs the signature as-is. This means an attacker can pull the initial controller's signature used to create the new lock straight from the event logs.

Looking at the ECLocker constructor, it first builds a fixed message hash per lock.

solidity
assembly {
    mstore(0x00, "\x19Ethereum Signed Message:\n32")
    mstore(0x1C, _lockId)
    _msgHash := keccak256(0x00, 0x3c)
}

So the signed message is the lockId. This value is stored in msgHash, and the same msgHash is used afterwards in open and changeController. Next, it extracts v, r, s from the _signature passed to the constructor and calls ecrecover.

solidity
mstore(ptr, _msgHash)
mstore(add(ptr, 32), mload(add(_signature, 0x60)))
mstore(add(ptr, 64), mload(add(_signature, 0x20)))
mstore(add(ptr, 96), mload(add(_signature, 0x40)))

The ecrecover precompile takes its input in (hash, v, r, s) order, so _signature is effectively passed in the usual (r, s, v) layout. The recovered address becomes initialController, and that address is set as the lock's controller.

Next is the signature replay protection.

solidity
usedSignatures[keccak256(_signature)] = true;

The constructor hashes the entire _signature bytes and marks it as used. However, the actual verification function hashes the signature differently.

solidity
bytes32 signatureHash = keccak256(abi.encode([uint256(r), uint256(s), uint256(v)]));
require (!usedSignatures[signatureHash], SignatureAlreadyUsed());

The constructor uses keccak256(_signature), while _isValidSignature uses keccak256(abi.encode([r, s, v])). Even for the same signature, the bytes being hashed differ, so a signature marked as used in the constructor is not recognized as used by the verification function. Simply replaying the initial signature from the event works. That said, we can also use the malleability of ECDSA signatures themselves.

Both open and changeController execute as long as _isValidSignature passes.

solidity
function changeController(uint8 v, bytes32 r, bytes32 s, address newController) external {
    _isValidSignature(v, r, s);
    controller = newController;
    emit ControllerChanged(newController, block.timestamp);
}

And _isValidSignature only checks whether the result of ecrecover(msgHash, v, r, s) equals the current controller.

solidity
address _address = ecrecover(msgHash, v, r, s);
require (_address == controller, InvalidController());

It does not check that s is in the lower half, nor does it use a safe wrapper like OpenZeppelin's ECDSA.recover. So we can craft a different form of the signature that recovers to the same signer address. The attack plan is as follows.

  1. Get the initial signature (r, s, v) from the NewLock event.
  2. Either reuse the original signature as-is, or use malleability to craft another valid signature.
  3. Use that signature to pass changeController and set controller to address(0).
  4. From then on, anyone can call open by submitting an invalid signature that makes ecrecover return address(0).

Solution

Suppose we have the signature obtained from the event.

(r,s,v)(r,s,v)

As shown above, simply reusing the original signature is possible. Here, ECDSA malleability gives a different valid signature.

The point computed during signature verification ultimately comes down to the xx coordinate of RR.

But RR and −R-R differ only in the sign of their yy coordinate; their xx coordinates are the same.

So if we can produce −R-R instead of RR, verification passes with the same rr.

If the original verification computed

R=s−1zG+s−1rQR = s^{-1}zG + s^{-1}rQ

then replacing ss with −s-s gives the following.

(−s)−1zG+(−s)−1rQ=−s−1(zG+rQ)=−R(-s)^{-1}zG + (-s)^{-1}rQ = -s^{-1}(zG+rQ) = -R

So replacing ss with −s-s produces −R-R, and since RR and −R-R share the same xx coordinate, the check against the same rr passes.

−s-s is not passed as a negative number; it must be represented  mod n\bmod n.

−s≡n−s(modn)-s \equiv n - s \pmod n

So the new ss value is n−sn-s.

Now vv must be changed as well.

vv takes the values 27 and 28 and indicates which of the two yy coordinates RR has.

Since we replaced RR with −R-R, vv must be flipped to the other value.

If vv is 27 or 28, the opposite value is computed as follows.

v′=55−vv' = 55 - v

So instead of the original signature, we use the following.

(r,n−s,55−v)(r,n-s,55-v)

This is a different signature from the original, but it recovers to the same controller address.

Exploit

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

import "forge-std/Script.sol";

interface IECLocker {
    function changeController(uint8 v, bytes32 r, bytes32 s, address newController) external;
}

contract Sol32 is Script {
    uint256 private constant SECP256K1_N = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141;

    function run() external {
        uint256 privateKey = vm.envUint("PRIVATE_KEY");
        IECLocker target = IECLocker(0x46887e09d735a4E2081A253cD78c656093183bD2);
        bytes memory signature =
            hex"1932cb842d3e27f54f79f7be0289437381ba2410fdefbae36850bee9c41e3b9178489c64a0db16c40ef986beccc8f069ad5041e5b992d76fe76bba057d9abff21b";

        uint8 v;
        bytes32 r;
        bytes32 s;

        assembly {
            r := mload(add(signature, 0x20))
            s := mload(add(signature, 0x40))
            v := byte(0, mload(add(signature, 0x60)))
        }

        vm.startBroadcast(privateKey);
        target.changeController(55 - v, r, bytes32(SECP256K1_N - uint256(s)), address(0));
        vm.stopBroadcast();
    }
}

Esc

Search titles, content and code.