Fault Attack on RSA CRT

 

https://neutrinox4b1.github.io/blog/2023/Invalid_RSA_decryption_code/

Invalid_RSA_decryption_code | Neutrinox4b1 ⚛

핵테온 본선 문제이다.

 

이전에 BSidesSF CTF 에서 이와 비슷한 문제를 푼 경험이 있어서 풀었으나, 원리를 명확히 이해하지는 못했다.

 

이번 글에서는 그 원리를 자세히 이해해보고자 한다.

https://medium.com/asecuritysite-when-bob-met-alice/ecdsa-signatures-can-be-cracked-with-one-good-signature-and-one-bad-one-2d8bc71949e9

ECDSA Signatures Can Be Cracked With One Good Signature and One Bad One

 

비슷한 글로 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$이라면 서명이 출력되도록 한다. 왜지..?