암호분석경진대회 2026

2026-09-02

2026 암호분석경진대회 Write-up 종합#

문제 1#

1.1. 설명#

문제 1은 고전 암호인 **시저 암호(Caesar Cipher)**와 **비제네르 암호(Vigenère Cipher)**의 차이를 이해하고, 통계적 특성을 이용해 두 암호를 구분한 뒤 실제 암호문을 복호화하는 문제이다.

시저 암호는 하나의 고정된 이동값 $k$ 를 사용하여 모든 문자를 동일하게 이동시키는 단일 치환 암호이다.

E_k(P)=(P+k)\bmod 26

D_k(C)=(C-k)\bmod 26

따라서 암호화 이후에도 평문에서 나타나는 알파벳의 **빈도 분포 형태 자체는 유지**된다. 반면 비제네르 암호는 키워드의 각 문자에 따라 서로 다른 이동값을 반복 적용한다.

C_i=(P_i+K_i)\bmod 26

이 때문에 동일한 평문 문자가 위치에 따라 다른 암호문 문자로 변환되고, 결과적으로 특정 알파벳에 집중되어 있던 빈도가 여러 문자로 분산된다.

1.2. 풀이#

먼저 `ciphertext1.txt`와 `ciphertext2.txt`의 **일치지수(Index of Coincidence, IC)**를 계산하였다. 두 암호문의 문자 수는 $N=19897$ 이며 계산 결과는 다음과 같다.

IC_1=0.068,\qquad IC_2=0.044

영어 자연어의 IC가 약 0.066이라는 점을 고려하면 `ciphertext1.txt`는 영어의 빈도 특성이 그대로 유지되어 있으므로 **시저 암호**, `ciphertext2.txt`는 빈도가 평탄화되어 있으므로 **비제네르 암호**로 판단하였다. 원문 설명 중 `0.68`로 적힌 부분이 있으나 실제 계산식의 결과는 `0.068`이다.

시저 암호에 대해서는 가능한 이동키를 전부 적용한 뒤 영어 알파벳 기대빈도와의 **카이제곱 적합도**를 계산하였다. 키가 6일 때 카이제곱 값이 39.860으로 가장 작았으며, 이를 통해 복호화 키가 $k=6$ 임을 결정하였다. 복호화 결과는 다음과 같다.

**THE SOVEREIGNTY OF THE REPUBLIC OF KOREA SHALL RESIDE IN THE PEOPLE, AND ALL STATE AUTHORITY SHALL EMANATE FROM THE PEOPLE**

전수조사 과정에서도 키 6일 때 `IT SHALL BE THE DUTY OF THE STATE TO PROTECT CITIZENS RESIDING ABROAD AS PRESCRIBED BY ACT`와 같이 정상적인 영어 문장이 나타나는 것을 확인할 수 있었다.

비제네르 암호는 반복 문자열 간 간격을 이용하는 방식으로 키 길이를 추정하였다. 반복 패턴의 간격으로 45 등이 관찰되었고 다른 간격과의 최대공약수를 계산한 결과 **키 길이는 5**로 결정되었다. 이후 암호문을 5개의 부분열로 나누고 각 부분열에 대해 카이제곱 검정을 수행한 결과 키는 **`KLVOJ`**로 복원되었다. 이 키를 이용한 최종 평문 역시 대한민국 헌법 제1조 제2항에 해당하는 문장으로 복원되었다.

마지막으로 두 학습 데이터에서 알파벳 상대빈도, IC, entropy, chi-square, column IC 등의 특징을 추출하고 `StandardScaler`와 `Logistic Regression`을 사용하여 시저/비제네르 이진 분류기를 구성하였다. 분류 결과 **암호문 1과 4는 Caesar, 암호문 2와 3은 Vigenere**로 판정되었다.

문제 2#

2.1. 설명#

문제 2는 4개의 64비트 워드로 이루어진 256비트 상태에 적용되는 미지의 permutation 구조를 테스트 벡터만으로 복원하고, 해당 연산을 20회 반복하는 구현을 최적화하는 문제이다.

사용 가능한 연산은 **64비트 rotation, XOR, 256비트 byte shuffle, 상수 addition**의 네 종류이며, 이 네 연산의 순서와 각 워드의 rotation 값을 찾아야 한다. Byte shuffle은 32바이트 전체를 역순으로 만드는 연산이므로 워드 순서 반전과 각 워드 내부 byte-swap으로 표현할 수 있다.

2.2. 풀이#

네 연산의 가능한 순서는 총 $4!=24$ 개이다. 각 후보에 대해 rotation 이전의 연산을 입력에 적용하고, rotation 이후의 연산을 출력에서 역연산하여 rotation 직전·직후의 값을 비교하였다. 올바른 구조라면 모든 테스트 벡터에서 동일한 rotation 값이 존재해야 한다.

그 결과 실제 연산 순서는 다음과 같이 복원되었다.

**Rotation → XOR → Byte Shuffle → Addition**

즉 한 round는

F(X)=S(R_r(X)\oplus C_2)+C_1 \pmod {2^{64}}

로 표현된다. 출력에서 Addition, Shuffle, XOR을 역순으로 제거하고 각 워드에 대해 가능한 $0\sim63$ 의 rotation을 조사한 결과 최종 rotation 배열은 다음과 같았다.

\boxed{\{43,\;7,\;29,\;14\}}

구조 복원 이후에는 AVX2를 사용해 네 개의 64비트 워드를 하나의 256비트 YMM 레지스터에서 병렬 처리하였다. Rotation에는 `_mm256_sllv_epi64`와 `_mm256_srlv_epi64`, XOR에는 `_mm256_xor_si256`, Addition에는 `_mm256_add_epi64`을 사용하였다.

특히 byte shuffle

S=BP

를 워드 순서를 뒤집는 $P$ 와 각 워드 내부 byte-swap인 $B$ 로 분해하였다. $P^2=I$ 이고 $B$ 와 $P$ 가 교환 가능하다는 점을 이용하여 두 round를 하나의 pair로 처리했다. 첫 round의 결과를 역순 lane 표현으로 그대로 유지한 뒤 두 번째 round에서 rotation과 상수의 lane 순서를 반대로 사용함으로써 hot loop에서 매번 발생하던 64비트 lane permutation을 제거하였다. 또한 rotation count와 상수, byte shuffle mask를 반복문 밖에서 미리 계산하고 20 rounds 동안 상태를 레지스터에 유지하였다.

최종 구현에서는 1-round 테스트 벡터 1000쌍과 20-round 테스트 벡터가 모두 `OK`로 검증되었다. 작성된 실행 결과 기준으로 20-round permutation을 1,000,000회 수행했을 때 총 약 **0.027216초**, 20-round 한 번당 약 **0.027216 μs**가 측정되었다.

문제 3#

3.1. 설명#

문제 3은 TLS 1.2로 보호된 급여 정보 패킷에서 세 번째 Application Data 레코드의 평문

`action=set_salary&uid=0007&amt=0100&month=202603`

을

`action=set_salary&uid=0007&amt=0500&month=202603`

으로 변조한 뒤에도 정상적인 TLS 레코드로 인증되도록 만드는 문제이다.

패킷 분석 결과 Cipher Suite는 **TLS_ECDHE_RSA_WITH_AES_128_GCM_SHA256**이며, TLS Application Data는 Frame 15~18에 존재하였다. AES-GCM fragment는 `Explicit Nonce || Ciphertext || Authentication Tag`의 구조를 가진다.

3.2. 풀이#

Frame 15~18의 explicit nonce를 조사한 결과 Frame 15, 16, 17은 모두

`9c269a9f29810ab0`

을 사용하고 있었으며 Frame 18만 마지막 값이 `…ab1`이었다. 즉 동일한 AES-GCM 키에서 nonce가 세 번 재사용되고 있었다.

AES-GCM의 암호화 부분은 CTR 모드를 사용하므로

C=P\oplus KS

가 성립한다. Frame 17의 원본 평문을 알고 있으므로

KS=P\oplus C

를 통해 키스트림을 직접 복원하였다. `amt=0100`에서 `amt=0500`으로 변경되는 문자는 `‘1’(0x31)`에서 `‘5’(0x35)` 하나뿐이므로 XOR 차이는 `0x04`이다. 따라서

C'=C\oplus P\oplus P'

를 이용해 목표 암호문을 생성하였다. 복원한 키스트림으로 다시 복호화하여 `amt=0500`이 정상적으로 생성되는 것도 확인하였다.

하지만 AES-GCM은 암호문뿐 아니라 authentication tag도 검증하므로 암호문만 변경해서는 패킷이 정상 처리되지 않는다. GCM 태그는

T=M\oplus GHASH_H(AAD,C)

로 표현할 수 있다. 동일 nonce를 사용하는 레코드들은 태그 마스크 $M$ 을 공유하므로 두 태그를 XOR하여 $M$ 을 제거할 수 있다. Frame 15, 16, 17을 이용해 $H$ 를 미지수로 하는 두 다항식 $f_{12}(H)$ , $f_{13}(H)$ 을 구성하고 SageMath에서 두 식의 최대공약수를 구해 GHASH 서브키를 복원하였다.

H=\texttt{112332a84132bc0c5c23a61037723683}

TAG_MASK=\texttt{1e023d8461003896981f1441c5feab90}

복구한 값으로 Frame 15~17의 기존 인증 태그를 다시 계산했을 때 모두 원본 태그와 일치하였다. 이후 수정된 ciphertext에 대한 새로운 GHASH와 authentication tag를 생성하고 기존 explicit nonce와 결합하여 완전한 TLS 1.2 Application Data 레코드를 만들었다. 최종 제출용 레코드는 다음과 같다.

`17030300489c269a9f29810ab0a99141d1d84c3df6bfdcdb7dec7cf30462db203fbc36a29772edbf159643b468f1f1e520e7341daee867a49665542cd9f01f5a9c906b73ba3e13bbfea0e98a18`

문제 4#

4.1. 설명#

문제 4는 대용량 `server.log`를 분석하여 사용된 LLM 모델과 인코딩된 채팅을 복원하고, 채팅 속 단서를 이용해 모델의 가중치에 스테가노그래피 방식으로 숨겨진 `CRYPTO{…}` 플래그를 찾는 문제이다.

로그 전체를 순차적으로 읽는 대신 `head`, `tail`, `ripgrep`을 이용해 모델 정보와 `chat_id`, `q1`, `a1` 형태의 기록을 탐색하였다. 그 결과 사용 모델은 **TinyLlama/TinyLlama-1.1B-Chat-v1.0**임을 확인하였다.

4.2. 풀이#

채팅 데이터를 분석한 결과 Base64와 ROT 계열 변환이 조합되어 있었고, 이를 역변환하여 대화를 복원하였다. 특히 `chat-000005`에서 다음 메시지를 확인할 수 있었다.

`What secret does the model have?`

`The LLM knows the secret. Trust me. “square” for open seasame!!!`

따라서 **square**가 숨겨진 데이터에 접근하기 위한 핵심 단서라고 판단하였다.

처음에는 `square`를 직접 모델 프롬프트에 입력하여 숨겨진 응답이 출력되는지 조사했지만 플래그는 나타나지 않았다. 이에 square를 숫자 **4**와 연결하여 모델 가중치의 **4비트 단위 nibble**에 정보가 은닉되어 있다고 추론하였다.

모델 tensor는 주로 float32였지만 실행 로그는 float16을 사용하고 있었다. float16의 fraction은 10비트, float32는 23비트이므로 float16 값이 float32로 변환될 경우 하위 13비트가 0으로 채워질 수 있다. 따라서 tensor별로 하위 13비트가 실제로 사용되는지 검사하여 `shift=0` 또는 `shift=13`을 결정하고, 해당 위치에서

(raw >> shift)\ \&\ 0x0F

연산으로 4비트씩 추출하였다.

추출한 두 nibble을 하나의 byte로 합칠 때 순서를 알 수 없으므로 **High-first**와 **Low-first** 두 방식을 모두 시험하였다. 약 11억 개의 가중치를 한 번에 메모리에 올리지 않고 4,000,000개 단위의 chunk로 처리하고, chunk 경계에서 남는 nibble도 다음 chunk와 연결하여 전체 비트 스트림의 정렬이 유지되도록 구현하였다.

총 201개 tensor와 1,100,048,384개의 가중치를 분석한 결과 Low-first에서는 플래그가 나오지 않았으나 High-first 결과의 offset `32768139`에서 `CRYPTO` 문자열이 발견되었다. 최종 플래그는 다음과 같다.

**`CRYPTO{G00D_J0B!_y0u_f0und_7h3_h1dd3n_s3cr37_1n_LLM}`**

문제 5#

5.1. 설명#

문제 5는 textbook-BGV 기반 비밀키 동형암호에서 **암호문 모듈러스 $q$ **와 **평문 모듈러스 $t$ **가 서로소가 아닌 잘못된 파라미터 설정을 이용하여 비밀 다항식 $s$ 와 반복적으로 사용되는 `State`를 복구하는 문제이다.

사용되는 환은

R=\mathbb Z[x]/(x^{64}+1)

이고 암호화 관계는

c_1=c_0s+te+m\pmod q

이다. 두 날짜의 평문은 `State || Padding || Date` 구조이며 State와 padding은 동일하고 마지막 8개 날짜 부분만 변한다.

5.2. 풀이#

두 암호문의 차이를 취하면

\Delta c_1=\Delta c_0s+t\Delta e+\Delta m\pmod q

가 된다. 이때 가장 중요한 취약점은

\gcd(q,t)=257

이라는 것이다. 식을 modulo 257에서 계산하면 $t\Delta e$ 가 완전히 사라지고 $q$ 의 배수 역시 사라지므로

\Delta c_0s=\Delta c_1-\Delta m\pmod{257}

라는 **오류가 없는 선형식**을 얻을 수 있다.

두 메시지는 연속된 날짜이므로 $\Delta m$ 은 마지막 8개의 날짜 계수에서만 발생한다. 따라서 2025~2027년의 가능한 연속 날짜들을 모두 생성하여 날짜 자리별 차이 후보를 구성하였다. 단순히 마지막 자리가 1 증가하는 경우뿐 아니라 월말·연말처럼 여러 자리 숫자가 동시에 변하는 경우도 모두 포함하였다.

환 $R_{257}=\mathbb F_{257}[x]/(x^{64}+1)$ 에서 $\Delta c_0$ 와 비밀키 $s$ 의 곱을 64×64 negacyclic convolution 행렬 $A$ 로 표현하여

As=b\pmod{257}

를 구성하였다. 실제 공격 행렬의 rank는 64였으며 RREF를 이용해 affine 해공간을 구하였다. BGV의 비밀키는 일반적인 $\mathbb F_{257}$ 원소가 아니라 각 계수가 $-1,0,1$ 중 하나인 삼진 다항식이므로 modulo 257에서 각 계수가 `256`, `0`, `1` 중 하나인 후보만 남겼다.

후보 비밀키로 두 암호문을 실제 복호화하여 두 State가 동일한지, 마지막 8개 값이 올바른 날짜인지, 두 날짜가 정확히 하루 차이인지, 그리고 복호화 오차가 $t$ 의 배수인지 검증하였다.

최종적으로 삼진 비밀 다항식 $s$ 가 복원되었으며 두 날짜는 **2026-04-10**과 **2026-04-11**, 공통 State는 다음과 같이 복원되었다.

**`BGV DAILY STATUS CORE-A LINK OK TEMP NORMAL POWER STABLE`**

문제 6#

6.1. 설명#

문제 6은 타원곡선 기반 난수 생성기 **Dual_EC_DRBG**의 백도어 구조와 추가적인 telemetry 정보 누출을 이용하여 내부 상태를 복원하고 다음 출력값 $r_3$ 를 예측하는 문제이다.

Dual_EC_DRBG의 상태 갱신과 출력은 다음과 같다.

s_{i+1}=X(s_iP)

r_i=\operatorname{MSB}(X(s_{i+1}Q))

문제에서는 88비트 필드에서 출력의 하위 16비트가 제거된 72비트 값 $r_0,r_1,r_2$ 가 제공되며, telemetry에서는 비밀 스칼라 $d$ 와 관련된 affine 연산의 상위 비트가 누출된다.

6.2. 풀이#

각 telemetry 행은

v_i=(a_i d+b_i)\bmod n

t_i=v_i>>20

형태이며 $v_i$ 의 하위 20비트만 알려져 있지 않다. 첫 번째 telemetry에 대해

v_0=(t_0<<20)+l_0,\qquad 0\le l_0<2^{20}

로 두고 $2^{20}$ 개의 하위 비트를 전수조사하였다. 각 후보로 $d$ 를 계산하고 나머지 모든 telemetry 행의 상위 비트와 일치하는지를 검사하여 유일한 비밀 스칼라를 결정하였다.

복원된 값은

d=\texttt{0x1c3cdd6b221806db0a7b28}

이다. 이 값은 타원곡선 백도어 관계 $P=dQ$ 를 만족한다.

다음으로 $r_0$ 에서 제거된 하위 16비트를 전수조사하였다.

x_R=(r_0<<16)+l,\qquad 0\le l<2^{16}

각 $x_R$ 에 대해 타원곡선 위의 실제 점이 존재하는지 확인하고, 후보 상태로부터 계산한 출력이 주어진 $r_1$ , $r_2$ 와 연속해서 일치하는 경우만 남겼다. 올바른 후보가 결정되면

s_2=X(dR),\qquad s_3=X(s_2P),\qquad s_4=X(s_3P)

를 계산한 뒤

r_3=X(s_4Q)>>16

으로 다음 출력값을 얻었다.

최종 복원 결과는 다음과 같다.

`r0 하위 16비트 = 0x5338`

`d = 0x1c3cdd6b221806db0a7b28`

`s2 = 0x638d9d631ab436da51e640`

`s3 = 0x948173253ad6d120a3f562`

`s4 = 0x5a8d3d3a755870b4298827`

따라서 예측해야 하는 다음 난수는

\boxed{r_3=\texttt{0x2443c8daf1a9d52b09}}

이다.

=======