https://neutrinox4b1.github.io/blog/2023/Invalid_RSA_decryption_code/
Invalid_RSA_decryption_code | Neutrinox4b1 ⚛
When d is the private key, RSA decryption using CRT is done as follows: mp = c^dp mod p (dp = d mod p-1) mq = c^dq mod q (dq = d mod q-1) qinvp = q^(-1) mod p s = (mp-mq) mod p m = mq+sqinvpq Unfortunately, I implemented the decryption code incorrectly. In
neutrinox4b1.github.io
핵테온 본선 문제이다.
이전에 BSidesSF CTF 에서 이와 비슷한 문제를 푼 경험이 있어서 풀었으나, 원리를 명확히 이해하지는 못했다.
이번 글에서는 그 원리를 자세히 이해해보고자 한다.
ECDSA Signatures Can Be Cracked With One Good Signature and One Bad One
I have been reading an excellent paper [1] and it outlines the usage of the fault attack on ECDSA signatures. With this we just need one…
medium.com
비슷한 글로 ECDSA에 대한 예시가 있다. 그러나 이 글에서는 RSA CRT에 대해서 알아본다.
RSA CRT
RSA는 몇 가지 버전이 있다. 가장 첫 버전은 RSA 78로 R. Rivest, A. Shamir, L Adleman에 의해 제안되었다. 우리가 익히 알고있는 RSA 방식이다. 이는 키의 길이가 커지면 지수 크기가 증가하여 연산이 기하급수적으로 증가한다는 특징이 있다.
RSA 82부터는 이 문제를 해결하기 위해서 CRT(Chinese Remainder Theorem)을 사용한다. 기존 RSA 연산을 p, q에 대해서 각각 수행하고 CRT를 이용해서 결합하는 것이다. 기존 RSA 에 비해 최대 4배정도 빠른 연산이 가능하다.
전자 서명에 대해서, 평문을 비밀키로 암호화할 때를 보자.
평문 $M$ 과 서명 $S$ 에 대해, 우리가 서명하는 과정은 $S = M^d \pmod N$이다.
이를 CRT를 사용하여 해결한다. 우선 비밀키 $d_p$와 $d_q$를 만든다. ($d_p$, $d_q$를 쓰지 않으면 RSA CRT를 쓰는 이유가 그닥..)
$$d_p = e^{-1} \pmod {p-1}$$
$$d_q = e^{-1} \pmod {q-1}$$
그리고 $d_p$와 $d_q$를 사용하여 각각 서명한다.
$$S_p = S \bmod p = M^{d_p} \pmod p$$
$$S_q = S \bmod q = M^{d_q} \pmod q$$
이제 $CRT(S_p, S_q)$를 하면 S를 얻을 수 있다. 이를 계산하는 방법으로 Gauss 방법과 Garner 방법이 있다.
보통 Garner 방법이 Gauss방법보다 효율적이라 Garner 방법을 사용한다.
$q_{inv} = q^{-1} \bmod p$ 인 $q_{inv}$를 구한다.
$$h = q_{inv} (S_p - S_q) \pmod p$$
$$S = S_q + hq$$
$h$는 p에 대한 q의 역원에
평문에 서명한 S를 구할 수 있다.
$h = q_{inv} (S_p - S_q) \pmod p$를 사용해서 $S = S_q + hq$로 구하는 과정에 대한 설명
이전에 CRT를 하기 위해서 그냥 생으로 연립한 과정이 있었는데 이를 일반화 한 것이다.
예를 들어
$x \equiv 2 \bmod 3$
$x \equiv 3 \bmod 5$
가 있다고 하자.
이걸 예시로 연립한다고 할 때, 첫번째 식에서 $y \in Z$ 에 대해 $x = 3y + 2$ 이고 이걸 두 번째 식에 대입하면
$3y + 2 \equiv 3 \bmod 5$이다. 그럼 우리는 y를 구하기 위해
$3y \equiv (3-2) \bmod 5$
mod 5에 대한 3의 역원은 2이므로 y=2이다.
따라서 x = 3 * 2 + 2 이므로 8이다.
여기서 일반화해본다.
$x \equiv 2 \bmod 3$에 대해 3은 $p$이고 $S_p = 2$이다.
$x \equiv 3 \bmod 5$에 대해 5는 $q$이고 $S_q = 3$이다.
처음에 만든 식 $x = 3y + 2$에서 $x = py + S_p$가 된다.
$3y + 2 \equiv 3 \bmod 5$ 에서 $y$를 구하는 과정 $3y \equiv (3-2) \bmod 5$ 는
$py \equiv (S_q - S_p) \bmod q$
양변에 $p^{-1} \bmod q$를 구해서 곱한다. 이게 $p_{inv}$
$y = p_{inv} (S_q - S_p) \bmod q$ 가 된다.
$y$를 $h$로 바꿔 생각해보면 이해가 된다.
그럼 여기서 구한 h를 가지고 $x = py + S_p$ 부분에 대입한다.
$x = S_p + ph$
이렇게 CRT를 일반화 한 것이었다...
Fault Attack (Bellcore attack)
위와 같이 서명하는 과정에서 오류가 있으면, 정상적인 서명, 비정상적인 서명을 가지고 p값을 계산할 수 있다.
$$h = q_{inv} (S_p - S_q) \pmod p$$
$$S = S_q + hq$$
이 과정에서 $S_p$가 오류가 생겨서 (이를테면, $d_p$를 잘못 구한다던가, $S_p$에서 모듈러를 잘못 쓴다던가) $S_p'$이 만들어졌다고 하자, $S_p, S_q$에서 한 가지만 집어서 말하는 이유는 오류가 두 곳에서 발생하면.. 그건.. 그냥 암호화가 안된거 아닌가?
어차피 p, q에는 순서가 없으니 $S_p$에서 오류가 있으면 $S_p'$이라고 하자.
그렇게 만들어진 정상적인 서명 $S$와 비정상 서명 $S'$에 대해서 $\gcd (S - S', N) = q$가 된다는 것이 Bellcore 공격이다.
$S_p$에 에러가 있고 $S_q$가 정상일때 두 서명을 빼면,
$S = S_q + hq$에서 $S_q$는 서로 공통이므로 제거된다.
h를 볼때, $S$와 $S'$은 서로 다른 h를 가진다.
$$h = q_{inv} (S_p - S_q) \pmod p$$
$$h' = q_{inv} (S_p' - S_q) \pmod p$$
따라서, $S - S' = hq - h'q$이고 $q \mid S - S'$이므로 $\gcd(S - S', N) = q$이다.
대응 방안 (작성 중, 미완성)
이러한 방법으로 공격이 가능하다는 걸 알았으니 대응 방안도 있을 것이다.
국내 논문(하재철; 박제훈; 문상재. 오류 확산 기법을 이용한 CRT-RSA 오류 주입 공격 대응 방안. 정보보호학회논문지, 2008, 18.2: 75-84.)에 소개된 대응 방법을 알아보자.
두 번 연산 확인 기법, 메시지 복원 기법
이 두 가지는 간단히 떠올릴 수 있는 방법이다.
우선, 두 번 연산 확인 기법은 오류가 생겼는지 검사하는 것이다.
그러나 많은 연산을 요구하고 영구적 결함을 가지는 시스템에서 오류가 생성되었는지 검사할 방법이 없다.
메시지 복원 기법은 공개키 e를 이용해서 원래 메시지를 복원하고 오류의 유무를 판단한다. 이 또한 공개키가 크다면 연산이 많아지고, 일부 시스템에서는 공개키에 대한 접근을 허용하지 않는다.
Shamir 기법
32bit 랜덤 수 r을 사용해서 $S^{*}_p = m^d \bmod pr$, $S^{*}_q = m^d \bmod qr$으로 생성한다.
그리고 $S^{*}_p \equiv S^{*}_q \bmod r$이라면 서명이 출력되도록 한다. 왜지..?
