Choi.ethTech Blog

Cryptography

타원 곡선 서명의 s-malleability(가단성)과 Low-S Restriction

작성자: Choi.eth

13 min read

image.png

Intro

디지털 서명이란 내가 만든 데이터를 내가 만들었음을 증명하는 기술이다. 이를 구현하기 위해 다양한 암호학 기법이 활용되는데, 이더리움과 비트코인 같은 블록체인 프로토콜에서는 주로 타원 곡선 암호(ECC) 기반의 디지털 서명을 사용한다.

타원 곡선 디지털 서명 알고리즘(ECDSA)을 위해 메시지를 설계하고 암호학 스킴을 구현하는 개발자가 반드시 깊은 학문적 지식을 갖출 필요는 없지만, 암호학 원리로부터 파생될 수 있는 보안적 허점을 이해하고 있어야만 실수 없이 안전한 코드를 작성할 수 있다. 그중에서 본 아티클에서는 디지털 서명 구현 과정에서 중요하지만 종종 간과되는 세부 사항 중 하나인 ECDSA 서명 가단성과 이를 방지하기 위한 Low-S Restriction(제한) 규칙에 대해 다뤄보고자 한다.

Background: ECDSA 디지털 서명 원리

ECDSA 서명 비가역성을 알아보기전, 먼저 타원 곡선 디지털 서명 알고리즘(ECDSA)에 대해 알아보자.

Weierstrass equation

y2=x3+ax+by^2=x^3+ax+b

우리가 자주 쓰는 타원곡선은 Weierstrass equation라는 방정식이 사용되며, 위와 같이 표현된다. 해당 방정식의 a와 b에 어떤 값을 대입하냐에 따라 암호학 스킴이 달리진다.

a=0,b=7a=0,b=7
y2=x3+7y^2=x^3+7

예를 들어, 이더리움과 비트코인에서 사용하는 Seck256k1은 a와 b에 각각 0, 7적용하여 위와 같은 방정식을 사용한다.

base field(p)와 group order(n)

y2=x3+ax+b (mod p)y^2=x^3+ax+b~(mod~p)

Weierstrass equation의 정확한 공식은 base field(p) 모듈러 연산이 적용된 상태이다. 이러한 모듈러를 적용한 이유는 무한한 수가 아닌 유한한 수를 사용하기 위함이다. 무한한 수를 대상으로 암호 체계를 구성하면 더 안전하리라 생각할 수도 있다. 그런데 아무리 안전해도 만약 현대의 컴퓨터로 서명하거나 암호화하는 데에 너무 긴 시간이 걸린다면 그 활용 범위가 너무 제한적이다.

image.png

타원 곡선의 수를 제한하는 모듈러에는 두 가지가 있다.

  1. Finite(base) field order(p)는 x,y 좌표의 범위를 제한하는 역할을 하며, 곡선상의 좌표 연산(점 덧셈, 스칼라 곱 등)과 같은 기하적 연산에 적용된다.
  2. Cyclic group order(n)은 곡선 위의 총 점 개수를 의미하며, 개인키, nonce, 서명 파라미터 등과 같은 스칼라(계수) 연산에 적용된다.

ECDSA 디지털 서명 생성

ECDSA 디지털 서명은 ‘r’, ‘s’ 두가지 파라미터로 구성되어 있으며, 아래와 같은 과정을 통해 생성된다.

  1. mod n범위 내에 임의의 숫자 k 선택한다.

    k mod nk~mod~n

  2. 선택한 k에 생성점(G)를 곱하여 R(x,y)를 통해 구한다. 이때 구한 좌표 R의 x는 r로 정의한다.

R(x,y)=G∗k mod pR(x,y) = G*k~mod~p
R(x,y)→x=rR(x,y)\to x=r

  1. 서명하고자 하는 메시지(m)를 해시(hash)하여 z를 구한다.

    z=hash(m)z=hash(m)

  2. 지금까지 정의한 변수 k, m, r와 개인키(sk)를 통해 서명값 s를 구한다.

    s=k−1(m+r∗sk) mod ns=k^{-1}(m+r*sk)~mod~n

ECDSA 디지털 서명 검증

ECDSA 디지털 서명은 위에서 구한 서명 데이터(r,s)와 서명 메시지(z), 그리고 개인키(sk)에서 파생된 **공개키(P = sk * G)**를 통해 아래와 같은 공식을 통해 검증하게 된다.

U1∗G + U2∗P=R(r′,y)U1*G~+~U2*P=R(r',y)
(2.5)     r=?r′(2.5)~~~~~r \overset{?}{=}r'

위 공식에 새롭게 등장하는 U1과 U2는 아래와 같이 정의된다.

(1.1)     w=s−1 mod n(1.1)~~~~~w=s^{-1}~mod~n
(1.2)     U1=m∗w mod n(1.2)~~~~~U1=m*w~mod~n
(1.3)     U2=r∗w mod n(1.3)~~~~~ U2=r*w ~mod~n

서명 검증의 원리는 s를 계산하는 공식을 역으로 전개함으로써 확인할 수 있다.

  1. s를 구하는 공식은 아래와 같다.
(2.1)     s=k−1(m+r∗sk) mod n(2.1)~~~~~s=k^{-1}(m+r*sk)~mod~n
  1. ss와 k−1k^{-1}위치를 바꾸고 풀어쓰면 아래와 같다.
(2.2)     k=s−1∗m+(s−1∗r)sk (mod n)(2.2)~~~~~k = s^{-1}*m + (s^{-1}*r)sk~(mod~n)

  1. 양 변에 생성점(G)를 곱한다.

    (2.3)     kG=s−1∗m∗G+(s−1∗r)sk∗G (mod n)(2.3)~~~~~kG = s^{-1}*m*G + (s^{-1}*r)sk*G~(mod~n)

  2. 지금까지 정의한 변수 R, U1, U2를 대입하면 아래와 같은 공식이 된다.

    (2.4)     U1∗G + U2∗P=R(r′,y)(2.4)~~~~~U1*G~+~U2*P=R(r',y)

  3. 위에서 구한 R(r’,y)R(r’,y)의 r’r’과 디지털 서명 rr과 비교하여 디지털 서명을 검증한다.

    (2.5)     r=?r′(2.5)~~~~~r \overset{?}{=}r'

s-malleability(가단성) 문제

지금까지 디지털 서명 s,r 를 활용하여 ECDSA 디지털 서명을 검증하는 과정을 살펴보았다. 그러나 이 과정에서는 생성된 디지털 서명(r, s)와 (r,n−s) 두 서명이 모두 유효한 결과를 낳는다.

암호학적 관점에서 유일성(Uniqueness)이 보장되어야 하므로 이는 보안상 취약점으로 작용하며, 이러한 현상을 s-malleability(가단성)문제라 부른다.

이 변형은 공격자가 새로운 메시지에 대한 서명을 위조할 수 있게 하는 취약점은 아니다. 하지만 동일한 메시지에 대해 서로 다른 바이트 표현의 유효한 서명이 존재하므로, 서명값이나 트랜잭션 해시를 고유 식별자로 사용하는 시스템에서 문제가 발생할 수 있다. 이러한 성질을 ECDSA 서명 가단성이라고 한다.

s의 덧셈에 대한 역원: n-s

덧셈의 역원은 어떤 숫자에 더했을 때 덧셈 항등원(0)이 되는 수를 의미한다. 즉 a에 대한 덧셈의 역원은 -a이다. 하지만 모듈러 연산에서 덧셈에 대한 역원은 다르다. 모듈러 n에 대한 a의 덧셈 역원 -a은 아래와 같이 표현할 수 있다.

−a≡n−a (mod n)-a \equiv n-a ~(mod~n)

이를 통해 서명데이터 s의 덧셈의 역원 -s는 아래와 같이 n-s가 된다.

−s≡n−s (mod n)-s \equiv n-s ~(mod~n)

즉, (r,s)와 (r, n-s)가 모두 유효한 결과를 낳는 다는건 s의 역원(-s)을 대입해도 동일한 결과가 도출된다는것을 의미한다.

👻 모듈러 덧셈의 역원에 대한 내용이 생소하다면 아래 글을 참조하면 이해가 쉬울 것이다.
https://borntodev.tistory.com/entry/암호학-시리즈-2-모듈러-연산과-암호학

서명 공식에 s의 역원을 대입하는 경우

(1.1)에서 w를 구하는 공식에 s의 역원을 대입하면 아래와 같다.

(3.1)     w=−s−1 (mod n)(3.1)~~~~~w=-s^{-1}~(mod~n)
(3.2)     U1=m∗w=−m∗s−1 (mod n)(3.2)~~~~~U1=m*w=-m*s^{-1}~(mod ~n)
(3.3)     U2=r∗w=−r∗s−1 ( mod n)(3.3)~~~~~ U2=r*w =-r*s^{-1}~(~mod~n)

이를 서명 검증 공식에 대입하면 아래와 같다.

(3.4)     R(r′,y)=−(U1∗G + U2∗P)(3.4)~~~~~R(r',y) = -(U1*G~+~U2*P)

여기서 좌표 R은 타원곡선 상의 점으로, 음수(-1)를 곱하면 아래와 같은 좌표가 나오게 된다.

(3.5)     −R(r′,y)=R(r′,−y)(3.5)~~~~~ -R(r',y) = R(r',-y)

이는 타원 곡선의 방정식인 Weierstrass equation y2=x3+ax+by^2=x^3+ax+b 꼴을 보면 알 수 있는데,

y2=f(x)=x3+ax+by^2 = f(x)= x^3+ax+b

y^2에 대해 어떤 x에 대한 방정식을 f(x) 필드로 표현한다면,

y=±f(x)y = \pm \sqrt{f(x)}

제곱수인 y는 위와 같이 +- 두 가지 모두 성립한다.

이때 y는 음수로 변형됬지만 x좌표의 r’는 s를 대입했을 때와 n-s를 대입했을 때와 동일한다.

r=?r′r \overset{?}{=}r'

(2.5)에서 설명했던것 처럼 실제 서명데이터는 x좌표로 정의된 r과 r’를 비교하여 검증한다. 때문에, y가 음수로 바뀌더라도 동일한 r값이 도출되기 때문에 (r,s)와 (r, n-s)가 모두 유효한 결과를 낳게된다.

Low-S Restriction 규칙

이러한 문제를 해결하기 위해 보편적으로 활용되는 방안으로 암호학 스킴에 Low-S Restriction 규칙을 적용한다. 해당 규칙은 간단하다. Low-S Restriction은 유효한 서명값 s의 범위를 1 ≤ s ≤ n/2로 제한하는 규칙이다. (r,s)와 (r,n-s)가 모두 유효하더라도, 두 값 중 하나만 n/2 이하이므로 하나의 정규화된 서명만 허용할 수 있다.

/// @dev N/2 for excluding higher order `s` values
uint256 private constant HALF_N = 0x7fffffff800000007fffffffffffffffde737d56d38bcf4279dce5617e3192a8;


function _isProperSignature(bytes32 r, bytes32 s) private pure returns (bool) {
    return uint256(r) > 0 && uint256(r) < N && uint256(s) > 0 && uint256(s) <= HALF_N;
}

https://github.com/OpenZeppelin/openzeppelin-contracts/blob/99eda2225c0246c265c902475c47ec0c6321f119/contracts/utils/cryptography/P256.sol#L45

OpenZeppelin에서 구현한 Secp256r1 커브의 서명(P256)을 검증하는 코드를 보면 uint256(s) <= HALF_N 를 검증하여 유효한 s값인지를 검증한다. 이를 통해 서명 데이터의 유일성을 보장한다.

이더리움의 EIP-2

이더리움 또한 타원 곡선 Secp256k1을 활용하여 트랜잭션 서명을 검증한다.

All transaction signatures whose s-value is greater than secp256k1n/2 are now considered invalid. The ECDSA recover precompiled contract remains unchanged and will keep accepting high s-values; this is useful e.g. if a contract recovers old Bitcoin signatures.
> EIP-2:  Specification

이더리움 트랜잭션 서명은 공개키 복구에 필요한 v와 ECDSA 서명값 r, s로 구성된다. 서명 가단성이 존재하면 (r,s,v)를 (r,n-s,v')로 변형해도 동일한 공개키가 복구될 수 있으며, 이 과정에서 v의 parity 값도 함께 반전된다.

EIP-2는 Homestead 하드포크부터 s > n/2인 트랜잭션 서명을 유효하지 않은 것으로 처리하도록 변경했다. 다만 과거 서명과의 호환성을 위해 ecrecover 프리컴파일은 여전히 high-S 서명을 허용한다.

Reference

Keep reading

모두 보기