2025년 암호분석경진대회 write-up

2025년도 암호분석경진대회에 참여했습니다. 2022년 최우수상 수상 이후로는 처음 참여하는데, 해가 지날 수록 대회 퀄리티가 개선되는 것 같아 참가 경험이 즐거웠던 것 같습니다.

금년도 출제된 문제는 다음과 같은 주제의 6개 문제이며, 그중 제가 담당한 2,4,5번 문제의 풀이에 관해 이야기하려 합니다.

1) AES를 포함하는 해시의 최적화 (SIMD) 2) 국산암호 LEA에 대한 차분공격경로 자동탐색 …★ 3) Whitebox-AES 구현에 대한 키 복구 공격 4) 위성통신암호 A5-GMR-1에 대한 ciphertext-only 키 복구 공격 …★ 5) ECDH/ECDSA 비밀키 복구 …★ 6) 포렌식→암호학 연계

---

5번 - ECDH/ECDSA 비밀키 복구

5번은 금년도 출제된 6개 문제 중 가장 쉬운 문제였습니다.

문제는 Alice와 Bob이 ECDH를 이용해 키를 공유하고, ECDSA를 이용하여 공유한 키를 서명하는 과정을 담고 있습니다.

한 가지 재밌는 점은 ECDSA에서 서명하는 메세지를 감추지 않았으므로 ECDH를 이용해 키를 공유한 이점이 사라진다는 것입니다. 도청자는 ECDH를 깨기 위해 ECDLP를 풀 필요 없이 ECDSA의 메세지를 확인하면 됩니다. Bob이 ECDSA로 메세지를 서명하자고 제안하고 Alice가 이것을 받아들인 것은 상황상 조금 어색하다고 볼 수 있겠습니다.

문제에서 제시한 정보는 다음과 같습니다.

• ECDH 및 ECDSA는 표준곡선 중 하나인 P-521을 사용
• Alice, Bob의 ECDH 공개키
• Alice가 계산한 ECDH 공유비밀
• Alice가 계산한 ECDH 공유비밀의 ECDSA 서명

P-521은 표준 타원곡선 중 하나로, order가 소수이며 군으로써의 구조에 대해 별다른 문제가 알려지지 않은 타원곡선입니다.

해당 곡선과 관련하여 알려진 이슈 중에는 CVE-2024-31497(PuTTY 관련)이 있습니다만, 이는 다수의 서명이 필요한 취약점이므로 본 문제에서는 고려할 수 없습니다.

그렇다면 어딘가에 숨은 조건이 있음을 짐작할 수 있습니다. 아니나 다를까, Bob의 public key가 P-521에 존재하지 않는 점입니다.

TypeError: Coordinates [..., 1] do not define a point on Elliptic Curve defined by ... over Finite Field of size ...

Bob은 공유비밀을 ECDSA로 서명하자는 수상한 제안을 하고, ECDH에서 P-521 상에 없는 점을 제시했습니다. 이는 Alice에 대한 모종의 공격 시도라 생각할 수 있으며 마침 이러한 정보를 사용하는 공격 기법이 있습니다. 바로 Invalid Curve Attack입니다.

Invalid Curve Attack

Weierstrass form의 타원곡선에서, 두 점 $(x_P,y_P)$와 $(x_Q,y_Q)$의 덧셈은 다음과 같이 계산할 수 있습니다.

\[s = \frac{y_P-y_Q}{x_P-x_Q} \\ x_R = s^2-x_P-x_Q \\ y_R = y_P-s(x_P-x_R)\]

위의 계산법에서 식의 어느 부분에도 타원곡선 $y^2=x^3+ax+b$의 상수항 $b$를 이용하는 계산이 없습니다.

이는 doubling에서도 마찬가지입니다.

\[s = \frac{3{x_P}^2+a}{2y_P} \\ x_R = s^2-2x_P \\ y_R = y_P-s(x_P-x_R)\]

따라서 만약 곡선 상에 실제로 존재하는 점인지 확인하지 않는다면 공격자는 기존의 $b$ 대신 임의의 $b^\prime$을 사용하여 ECDLP가 쉽거나 order가 작은 소인수를 포함하는 등 취약한 타원곡선 $y^2=x^3+ax+b^\prime$ 에서의 계산 결과를 얻도록 유도할 수 있습니다.

본 문제에서는 Bob의 공개키가 order가 $2^{512}$인 타원곡선에 존재합니다. 곡선이 smooth order를 가지므로 부분군의 ECDLP를 해결하고 이를 elaborate하는 방식의 알고리즘을 사용할 수 있으며, 이는 다음과 같은 의사코드로 표현할 수 있습니다.

Input: DLP base point G, DLP target point P
answer ← 0
For e ← 0,1,2,...,520
    For bit ← 0,1
        If 2^520-e×(P-(bit×2^e+answer)×G) is the point at infinity Then
            answer ← (bit×2^e+answer)
            Break For
        End If
    End For
End For
Return answer

문제 감상

조건이 별도 언급이나 생성 코드 없이 자료에 내포되어있는, CTF Crypto에서는 드물게 마주치는 타입의 문제였습니다.

Invalid Curve Attack을 그대로 적용하며 따로 꼬아놓은 부분도 없었기에 숨겨진 조건을 발견하면 straightforward한 문제풀이가 가능했습니다.

---

2번 - LEA 차분공격경로 자동탐색

다음과 같은 3개 소문항으로 구성되는 문제입니다.

1) Modular Addition (mod 2^32)에 대해 차분 확률 0.1 이상인 입출력 차분 형태를 구하는 코드를 제시하라. 2) Modular Addition의 차분 경로 탐색이 어려운 이유와 이를 해결하기 위해 Nested Monte Carlo Tree Search(NMCTS)를 활용하는 방법을 설명하라. 3) 2번의 방법으로 NMCTS를 이용한 차분 경로를 탐색하는 코드를 제시하고 이를 이용해 찾은 차분 경로를 제시하라.

NMCTS를 이용해서 차분경로를 찾는다는 접근이 다소 특이합니다. 실제로 관련 자료를 탐색해보면 힌트로 제시된 논문 외에 이와 같은 접근법을 취하는 연구를 찾기 어렵습니다. 해당 논문을 이해하고 구현하라는 취지의 문제라 생각하고 풀이를 작성하였습니다.

1번, 2번 소문항의 경우 힌트로 제시된 논문에 있는 언급을 찾아 작성하면 되는 간단한 소문항이었습니다. 반면 3번의 경우 논문 내용을 토대로 조금 고민이 필요한 항목이었습니다.

우선 논문에서 제시하는 차분경로 탐색 방법에 대해 정리해보겠습니다.

Monte-Carlo Tree Search는 트리의 형태로 표현 가능한 탐색 공간에 대해 일종의 random walk를 시행합니다. 여러 random walk 중 최적인 것을 추출하는 휴리스틱한 방법으로 최적화 문제에 접근하는 방식입니다.

Nested Monte-Carlo Tree Search는 이러한 Monte-Carlo Tree Search의 상태를 탐색 공간으로 간주하는 탐색 방식입니다. 언급된 구체적인 방법은, Monte-Carlo Tree Search에서 얻은 부분최적 경로를 어느 정도 수용하여, 경로의 시작부분을 고정한 채로 Monte-Carlo Search를 다시 시행하는 것입니다.

이는 Monte-Carlo Tree Search의 탐색 공간인 트리에서 보면 시작점을 원래 시작점의 자식 노드로 이동시키는 연산으로 확인할 수 있습니다.

여기서 한 가지 문제가 발생하는데, 탐색 공간이 커도 지나치게 크다는 것입니다.

LEA의 Modular Addition 연산은 64비트의 입력을 32비트로 출력하는 함수이므로, 다른 블럭 암호들이 비선형성을 8비트의 S-Box에 의존한다는 것과 비교하면 다소 큰 탐색공간을 가진 함수입니다. 애초에 큰 탐색공간을 다루기 위해 Monte-Carlo Search를 적용하는 것인데, 이를 중첩함으로써 다시 탐색공간이 커져버렸습니다.

논문에서는 이를 다루기 위한 방법으로 partial Differential Distribution Table(pDDT)를 제시했습니다. Modular Addition에 의한 상태 전이 중 역치를 초과하는 전이만 고려하여, 탐색하는 공간을 줄이되 탐색되는 상태의 질을 높이는 전략입니다.

논문의 저자는 NMCTS를 통해 탐색(Exploring)을, pDDT로 공략(Exploiting)을 균형있게 가져가는 방법이라 설명합니다.

다만 이를 실제로 구현하는 것에는 몇몇 문제점이 있었습니다. 우선 논문에서 사용하는 역치 확률은 0.1이었는데, 이 수치가 상당히 애매합니다. 역치 확률 0.1을 초과하는 Modular Addition의 차분 전이는 총 3951388개입니다. 이보다 역치 확률을 낮추면 조건을 만족하는 전이의 수가 167065948개이므로 메모리와 탐색 시간 측면에서 0.1은 합리적인 선택처럼 보입니다.

각 차분 입출력에 대해 실제 실현 확률은 1/2^k 꼴로 나타납니다. 역치 확률을 0.1로 설정하면 실제로는 0.125 이상의 확률로 성공하는 차분 입출력만 고려하게 됩니다.

첫번째 문제는 이 역치가 생각보다 차분경로의 질을 높이는데에 도움이 되지 않는다는 것입니다. LEA는 블럭 크기가 128비트로, 이를 네 개의 32비트 값으로 나누어 Modular Addition을 적용합니다. 즉 0.125 이상의 확률이더라도 라운드 당 총 네 번 적용되고 나면 차분 경로의 성공 확률이 심하게 낮아지게 됩니다.

두번째 문제는 이 역치가 실제로 탐색(Exploring)을 그다지 보장하지 못한다는 것입니다. 논문의 Table 3과 Table 4는 저자가 해당 방법을 이용해 발견한 차분 경로입니다. 저자는 역치 0.1을 사용하여 pDDT를 구성하고 NMCTS를 사용하였다고 이야기하지만, Table 4의 첫 전이는 Weight가 -27로 해당 라운드에서 네 번의 Modular Addition 중 적어도 하나는 Weight -7(실현 확률 0.0078125) 혹은 그 이하의 성공 확률을 갖는 전이를 사용하였습니다. 실제로 역치 0.1의 pDDT만을 이용하여 탐색하면 상당히 형편없는 차분경로만을 얻을 수 있습니다. 라운드 수가 늘어날 수록 조건을 만족하는 차분 경로의 수 자체가 감소하는 것 또한 문제입니다.

실제로 저자는 이와 같은 문제를 논문 중에서 이러한 역치의 설정이 반드시 필요한 낮은 실현 확률의 전이를 배제할 수 있다고 언급합니다만, 이를 해결하는 방법은 구체적으로 언급되어 있지 않습니다.

이를 해결하기 위해, 논문에서 언급된 차분 확률 식을 이용하여 차분 확률을 먼저 결정한 후 해당하는 전이를 찾는 방식으로 코드를 작성하였고, 다음과 같은 이점을 취할 수 있습니다.

• 탐색 시간에 큰 영향을 미치지 않는다.
• 필요한 메모리의 양이 적다.(pDDT조차 계산하지 않아도 됨)
• 탐색 공간을 제한하지 않는다.(Exploring 확보)
• 기존의 NMCTS에 비해 탐색의 질을 포기하지 않는다.(NMCTS)
• 탐색의 질과 탐색 차분 경로의 길이의 trade-off가 가능하다.

논문에서는 Weight -98의 8라운드 차분경로(Table 3)과 Weight -126의 11라운드 차분경로(Table 4)를 제시했으며, 필자는 Weight -98의 11라운드 차분경로와 Weight -126의 12라운드 차분경로를 발견하여 해당 경로를 제출하였습니다.

문제 감상

생각할수록 뭔가 이상한 문제였습니다. 취한 방법론도 너무 이색적인 방법에, 다른 자동탐색 방법과 비교해도 효율이 좋지 않습니다. 제시한 아이디어도 구체화가 되어있지 않고 제시한 탐색 결과물의 라운드 수도 잘못 기재되어 있는 등 다소 읽기에 어려움과 답답함이 있는 연구였습니다.

관련한 다른 논문을 탐색하던 중 대수적인 방법으로 차분공격경로를 탐색하는 논문을 발견했는데, 시간이 되면 해당 논문을 읽어봐야겠습니다.

---

4번 - A5-GMR-1 ciphertext-only attack

사실 4번 문제를 이야기하고자 글을 썼다 해도 무방합니다. 가장 많은 시간을 썼고, 가장 재밌게 푼 문제입니다.

A5-GMR-1은 일부 위성통신에 사용하던 암호입니다. 재밌는 점은 LFSR를 사용하는데 필터링이 고작 2차의 다항함수라는 점입니다. A5-GMR-1은 필터링 함수뿐만 아니라 LFSR의 clock timing으로부터 비선형성을 창출한다는 신기한 아이디어를 사용합니다.

A5-GMR-1은 고정된 길이의 블럭(이하 프레임)을 암호화합니다. 각 프레임의 암호화는 64비트 마스터키 $\alpha$와 프레임에 배정된 19비트 프레임번호 $N$을 사용하여 key stream을 생성하는 stream cipher입니다. 구체적으로는 다음과 같은 절차로 암호화합니다.

1. 선형 연산을 통해 $\alpha$와 $N$으로부터 프레임 키 $\alpha^\prime$을 계산합니다.
2. 각각 19, 22, 23, 17비트의 상태를 갖는 LFSR 4개를 생성합니다. 이하 $L_1,L_2,L_3,L_4$라 지칭하겠습니다.
3. $\alpha^\prime$의 각 비트를 순서대로 LFSR의 가장 최근 비트에 xor하고 clock하는 과정을 64번 반복합니다. 이는 modulus가 $f$인 $F_{2^{\text{deg}{f}}}$에 대해 각 LFSR의 상태를 $\alpha$로 설정하는 것과 동일합니다. 이후 최하위 비트를 1로 고정합니다.
4. $L_4$의 상태 중 고정된 위치의 3개 비트 값 $a,b,c$를 확인합니다. 이 중 개수가 더 많은 값을 $m$이라 합시다.
5. $a=m$이면 $L_1$을, $b=m$이면 $L_2$를, $c=m$이면 $L_3$을 clock합니다.
6. 각각 $L_1,L_2,L_3$의 상태를 이용해 정의되는 2차 부울 다항식 $f_1,f_2,f_3$에 대해 $f_1\oplus f_2\oplus f_3$을 계산하여 출력합니다.
7. 4~6번을 프레임의 비트 길이만큼 반복하여 key stream으로 사용합니다. 이를 평문과 xor합니다.

A5-GMR-1의 비선형성은 2차 다항식인 필터링 함수와 $L_4$에 의한 각 LFSR의 clock timing에 있습니다.

필터링 함수가 2차이며 각 LFSR의 상태는 18, 21, 22비트의 자유도를 갖습니다. 즉 필터링 함수의 출력은

\[18+21+22+\binom{18}{2}+\binom{21}{2}+\binom{22}{2}=655\]

개의 부울 변수의 선형결합으로 표현 가능합니다.

즉, A5-GMR-1의 비선형성은 다음과 같은 조건이 충족되면 제거할 수 있습니다.

• $L_4$의 상태가 온전히 알려짐
• 한 프레임의 $L_1,L_2,L_3$ 초기 상태에 대해 2차식으로 표현되는 변수의 실제 값 655개

한편 $L_4$는 16비트의 자유도를 가지므로 $2^{16}=65536$가지의 경우만 존재합니다. 이는 충분히 brute-force를 고려할 수 있는 크기입니다. brute-force에서는 각 경우에 $L_4$의 초기 상태를 안다고 생각할 수 있습니다. 이후 내용에서는 이를 가정하고 논리를 전개하겠습니다.

본 문제의 조건을 비롯하여 많은 상황에서 A5-GMR-1의 평문은 인코딩된 평문입니다. 이러한 인코딩은 원문보다 큰 비트 수를 가져, 상태 공간 전체를 span하지 않습니다. 해당 조건은 선형연립방정식의 과조건을 암시하고, 이러한 과조건은 흔히 에러 검출에 사용됩니다.

본 문제의 풀이에서는 상태공간 전체가 span되지 않음을 이용해, 인코딩 행렬의 kernel로부터 정보를 추출합니다. 구체적으로는 다음과 같은 식이 성립함을 이용합니다.

\[H^T := \text{basis matrix of }\ker(G)\\ HG = 0 \Rightarrow H(Gp) = 0\]

즉, 인코딩된 평문과 곱하면 영행렬이 되는 행렬 $H$(parity-check matrix)을 이용해 LFSR 초기 상태에 대한 선형방정식을 얻는 것입니다.

\[Hc = H(Gp\oplus z) = HGp\oplus Hz = Hz\]

위 식은 암호문에 parity-check matrix를 곱하여 key stream에 관한 선형연립방정식을 얻을 수 있음을 보여줍니다. 문제에서 제시된 조건에서는 인코딩 행렬 $G$가 160비트 평문을 208비트로 인코딩하므로, $H$는 48x208의 행렬이며 key stream에 대한 선형방정식 48개를 알 수 있습니다.

48개의 식은 변수가 655개인 선형방정식을 풀기에 부족한 수치입니다. 부족한 식의 수를 충당하기 위해서 프레임 키 사이의 관계에 주목해봅시다.

1. 선형 연산을 통해 $\alpha$와 $N$으로부터 프레임 키 $\alpha^\prime$을 계산합니다.

암호화 과정의 1번 스텝으로부터, $\alpha^\prime = A\alpha+BN$을 만족하는 64x64의 행렬 $A$와 64x19의 행렬 $B$가 존재함을 알 수 있고, 이를 통해 다음과 같은 사실을 확인할 수 있습니다.

\[\alpha^\prime\vert_{N} = A\alpha+BN = A\alpha+BN_0+B(N+N_0)=\alpha^\prime\vert_{N_0}+B(N+N_0)\]

이후 프레임 키가 선형적인 과정을 통해 LFSR의 초기 상태로 설정되므로,

• $N_0$번 프레임에서의 $L_4$ 초기 상태를 결정하면 나머지 프레임에서도 $L_4$ 초기 상태를 결정할 수 있습니다.
• 각 프레임에서 $L_1,L_2,L_3$의 초기 상태는 모두 $N_0$번 프레임에서의 초기 상태에 대한 선형 결합으로 표현할 수 있습니다.

이는 각 프레임의 key stream $z\vert_{N}$이 다음과 같은 벡터 $x$와 어떤 행렬 $C\vert_{N}$로부터 계산할 수 있음을 알 수 있습니다.

\[\begin{matrix*}[l]x = (&\\ &L_{1,0},\cdots,L_{1,17},L_{2,0},\cdots,L_{2,20},L_{2,0},\cdots,L_{2,21},\\ & L_{1,0}L_{1,1},\cdots,L_{1,16}L_{1,17},L_{2,0}L_{2,1},\cdots,L_{2,19}L_{2,20},L_{3,0}L_{3,1},\cdots,L_{3,20}L_{3,21},\\&1\\ )\end{matrix*} \\ z\vert_{N} = C\vert_{N}x\]

지금까지 도출한 결과를 종합하면 다음과 같이 정리할 수 있습니다.

\[Hc = H(Gp\oplus z) = Hz\vert_{N} = HC\vert_{N}x\]

여러 프레임의 결과를 종합한다면 다음과 같은 행렬 $M$을 얻을 수 있습니다.

\[M = \begin{bmatrix} HC\vert_{N_0}\\ HC\vert_{N_1}\\ \vdots \\ HC\vert_{N_t} \end{bmatrix}\]

만약 $\text{span}(M)$이 다음과 같은 행렬 $M^\prime$에 대해 $\text{span}(M^\prime)$을 포함한다면 $N_0$번 프레임의 LFSR 초기 상태를 계산할 수 있습니다.

\[M^\prime = \left[ \begin{array}{c|c} I_{61} & 0 \end{array} \right]\]

이는 실험적으로 평균 12.25개, 최대 13개의 프레임이 필요합니다.

문제에서는 총 15개의 프레임 중 2개 비트에 오류가 있으므로 오류가 없는 프레임이 최소 13개입니다. 즉, 오류가 있는 비트를 찾아낸다면 올바르게 평문을 복구할 수 있습니다.

이는 위 풀이를 총 $65536\times\binom{15}{2}=6881280$번 수행하며, 40코어 기준 약 33시간의 런타임을 통해 모든 경우의 수를 시도할 수 있었습니다.

풀이 개선하기

이러한 문제에서 흔히 “올바르게 해독된” 평문은 읽을 수 있는 영문 문자열입니다. 해당 가정이 맞다면, ASCII 코드를 기준으로 매 바이트의 최상위비트는 0이 됩니다.

이는 위 풀이에서 인코딩된 문자열이 160차원의 공간을 span한다는 가정을 강화하여, 단 140차원만을 span한다고 가정할 수 있게 됩니다. 각 프레임의 parity-check matrix가 48개 행에서 20개가 늘어난 68개 행을 가지므로, 키 복구에 필요한 프레임 수는 줄어들 것이라 예상할 수 있습니다.

실제 실험을 통해서 얻은 결과는 9개의 프레임만으로 키를 복구할 수 있다는 것입니다. 오류가 있는 프레임의 조합을 모두 brute-force해야 했던 이전의 경우와 달리, 지금은 조금 더 현명한 프레임 조합 선택 방법이 존재합니다.

우선 1번부터 15번의 프레임을 연속한 3개씩 묶어 총 5개의 청크로 정의하겠습니다. 다음과 같은 조합 선택으로 $L_4$ 초기상태 후보 1개 당 11번의 시도만으로 에러가 없는 조합의 시도를 보장할 수 있습니다.

1. (1,2,3),(1,2,5),(3,4,5)
2. (2,3,5),(1,3,5)
3. (1,2,4),(1,3,4),(1,4,5),(2,3,4),(2,4,5),(3,4,5)

1번의 조합이 모두 에러를 포함하는 시도라면, 모든 청크가 세 시도 중 적어도 하나에서 배제되어 있으므로 에러가 두 청크에 나뉘어 존재함을 알 수 있습니다.

2번의 조합도 모두 에러를 포함하는 시도라면, 4번 청크를 사용하지 않는 조합을 모두 시도하였으므로 4번 청크는 에러가 없는 청크입니다.

3번의 조합은 4번 청크를 사용하는 모든 조합입니다. 3번의 조합도 모두 에러를 포함할 수는 없습니다.

총 11번의 시도는 기존의 105번의 시도에 비해 10.47%에 불과한 수치입니다. 이는 상당한 런타임 개선을 기대할 수 있고, 실제로 약 7시간 내로 올바른 키와 평문을 찾을 수 있었습니다.

후기

CTF를 주로 참가하는 입장에서 암호분석경진대회의 문제들은 매년 신선한 느낌을 받습니다.

암호학 전공의 교수님들이 출제하시다 보니 최신 근황과 관련한 문제도 종종 나오는 것 같습니다.

군 입대 전인 22년도에 참가했을 때도 Isogeny 기반의 SIDH나, 컴퓨터비전에 관한 인공지능 문제도 출제되었었죠.(대회 당시에는 무려 Castryck-Decru attack이 공개되기 전이었습니다)

공모전 형식이라 시간 압박도 덜해 CTF의 타이트한 경쟁이 싫을 때 풀면 재밌는 것 같습니다.