[crypto] KalmarCTF 2026, Dreamhack M4 - MissingNo.3
1. 개요
KalmarCTF 2026에 출제되어 2 solves가 나오고, 대회 종료 이후 Dreamhack에 Master 4, 난이도 체계 개편 전에는 Level 10을 할당받은 문제입니다.
Mersenne Twister의 rejection sampling, SageMath의 random_matrix, Python randrange 동작을 정확히 알아야 하는 매우 흥미로운 문제였습니다.
본 글은 CTF Writeup이지만 Dreamhack에 동일한 문제가 업로드되어 있으므로 이 문제의 제작자인 soon_haari님의 Writeup에서 설명하는 범위를 벗어나지 않도록 주의했습니다. 따라서 전체 솔버 코드를 공개하지 않으며 일부 알고리즘은 간소화해서 설명합니다.
2. 문제 정보
2-1. MissingNo.
문제에서 말하는 OICC 2025의 MissingNo.는 다음 세팅을 가집니다.
b: 길이 52의 공개 vector
A: 크기 52x52의 공개 matrix
s: 길이 52의 랜덤 vector
r: 랜덤 정수
f: FLAG 각 문자를 원소로 가지는 길이 52의 vector
b = As + fs 에서 f를 알아내는 문제입니다.
Intended 풀이는 lattice reduction, 즉 LLL 또는 BKZ로 푸는 문제입니다.
그런데, random_matrix(F, 52)[:,:-3]으로 생성된 A만 보고도 Sage Seed가 계산되어 바로 s와 r을 재현할 수 있는 unintented 풀이가 나올 수 있습니다.
2-2. MissingNo.3
그 점을 의도한 문제입니다. 문제 설명의 "forensics challenge"는 Ab.sobj Sage object file의 내용을 읽어야 풀 수 있어서 사용한 일종의 농담입니다.
author: soon_haari
Bonus forensics challenge.
This is a revenge challenge of MissingNo. from OICC 2025.
# chall.sage
set_random_seed(input(version() + "\nseed: "))
F = GF(0xdead1337cec2a21ad8d01f0ddabce77f57568d649495236d18df76b5037444b1)
A = random_matrix(F, 52)[:,:-3]
# github.com/AustICCQuals/Challenges2025/blob/main/crypto/missingno/publish/Ab.sobj
if A == load("Ab")[0]:
print("kalmar{}")
문제에 접속하면 Sage 10.7을 사용하고 있다는 정보를 얻을 수 있습니다.
chall.sage 자체는 A 행렬을 재현하는 seed를 찾아내면 되는 간단한 코드입니다.
0xdead1337cec2a21ad8d01f0ddabce77f57568d649495236d18df76b5037444b1 = 0x634270e2ad7 ^ 6 입니다. 이는 SageMath 10.7 환경에서 random_matrix 동작에 영향을 줍니다.
CTF 참여 당시에는 version을 출력해줘서 version diff로 유의미한 부분을 찾고자 했습니다. 끝나고 난 후 공개된 사실은 10.8.beta2에서 R.random_element 동작이 변경되어 명시한 것이었습니다. 따라서 아래의 코드 레벨로 알아보는 동작은 SageMath 10.7 내용을 소개합니다.
2-3. Dreamhack Version
KalmarCTF 2026에서는 고정된 Ab.sobj의 seed값을 알아내야 했다면, Dreamhack은 접속 시마다 변경되는 seed를 5분 내로 계산해야 합니다.
3. random_matrix(F, 52) 동작 요약
Args:
ring = GF(p^6)nrows = 52ncols = 52
import sage.matrix.matrix_space as matrix_space
def random_matrix(ring, nrows, ncols=None, ...):
parent = matrix_space.MatrixSpace(ring, nrows, ncols, ...)
if algorithm == 'randomize':
# zero matrix is immutable, copy is mutable
A = copy(parent.zero_matrix())
if density is None:
A.randomize(...)
return A
각 원소들에 대해 하나씩 돌아가면서 set_unsafe(base_ring().random_element()) 실행
cdef class Matrix(Matrix1):
def randomize(self, density=1, nonzero=False, ...):
R = self.base_ring()
cdef Py_ssize_t i, j
if nonzero:
...
else:
if density >= 1:
for i from 0 <= i < self._nrows:
for j from 0 <= j < self._ncols:
self.set_unsafe(i, j, R.random_element(...))
전달받은 R이 GF(p^6)이므로 vector_space().random_element() 실행
vector_space().random_element()는 내부에서 rank만큼 random_element()를 다시 실행
이때는 degree() = 1이므로 randrange(order() = p) 실행
log2(p)=42.6… 이므로 randrange(p)는 32+11비트를 사용
def random_element(self, ...):
if self.degree() == 1:
return self(randrange(self.order()))
v = self.vector_space(map=False).random_element(*args, **kwds)
return self(v)
10.8.beta9에서부터는 args와 kwds가 없으면 바로 return self.from_integer(randrange(self.order()))를 실행해서 동작이 변경되므로 대회에서는 sage version이 10.7임을 명시
vector_space.random_element in free_module.py
rank()가 6이므로 6번의 R.random_element()를 실행
class FreeModule_ambient(FreeModule_generic):
def random_element(self, ...):
rand = current_randstate().python_random().random
R = self.base_ring()
v = self(0)
prob = float(prob)
for i in range(self.rank()):
if rand() <= prob:
v[i] = R.random_element(*args, **kwds)
return v
Ab.sobj의 A[0][0] 원소 관찰
(4309812620277z6^5 + 564698381371z6^4 + 2482046981087z6^3 + 3286340353355z6^2 + 2396756075089z6 + 4896304883077)
seed를 알고 있는 상태에서 관찰해보면 낮은 차수부터 randrange를 통해 생성됨을 확인 가능
4. Python randrange() 동작 요약
class Random(_random.Random):
def randrange(self, start, stop=None, step=_ONE):
istart = _index(start)
if stop is None:
if istart > 0:
return self._randbelow(istart)
_randbelow는 _randbelow_with_getrandbits로 정의됨
k = 43, 따라서 r = getrandbits(43)을 실행
만약 r ≥ n 이라면 rejection, 한 번 더 실행
class Random(_random.Random):
def _randbelow_with_getrandbits(self, n):
k = n.bit_length()
r = getrandbits(k)
while r >= n:
r = getrandbits(k)
return r
앞선 free_module.py의 rand()는 MT output 2개를 소비
static PyObject *_random_Random_random_impl(RandomObject *self)
{
uint32_t a=genrand_uint32(self)>>5, b=genrand_uint32(self)>>6;
return PyFloat_FromDouble((a*67108864.0+b)*(1.0/9007199254740992.0));
}
_random_Random_getrandbits_impl in _randommodule.c
k = 43이므로(32bit 초과하므로) words = 2
getrand_uint32()를 2번 실행
여기서 32비트 + 상위 11비트만 쓰는 로직이 나옴
static PyObject *_random_Random_getrandbits_impl(RandomObject *self, int k)
{
int i, words;
uint32_t r;
uint32_t *wordarray;
PyObject *result;
words = (k - 1) / 32 + 1;
wordarray = (uint32_t *)PyMem_Malloc(words * 4);
#if PY_LITTLE_ENDIAN
for (i = 0; i < words; i++, k -= 32)
#else
for (i = words - 1; i >= 0; i--, k -= 32)
#endif
{
r = genrand_uint32(self);
if (k < 32)
r >>= (32 - k); /* Drop least significant bits */
wordarray[i] = r;
}
result = _PyLong_FromByteArray((unsigned char *)wordarray, words * 4,
PY_LITTLE_ENDIAN, 0 /* unsigned */);
PyMem_Free(wordarray);
return result;
}
5. 필요한 동작만 요약한다면
Sage는 Python의 기본 랜덤 모듈인 MT(Mersenne Twister)를 사용합니다.
matrix의 원소 하나는 계수 6개의 vector로 구성합니다.
vector의 계수 1개를 만들기 전에는 rand()로 MT output 2개를 소비합니다.
getrandbits(43)도 MT output 2개를 먼저 소비하고 조건을 확인, rejection이 발생하지 않을 때까지 2개씩 계속 소비합니다.
6. Mersenne Twister state recovery
Mersenne Twister는 내부 state로 크기가 624인 32-bit 배열을 사용합니다.
그래서 연속된 32-bit 정수 출력 624개를 알고 있으면 state를 복구할 수 있다는 것은 많은 블로그와 RandCrack Github repositories가 다루는 주제입니다.
그리고 연속되지 않아도 (오류가 있는 요약이지만) 대략 624개의 정수와 몇 번째 output인지 알고 있어도 state 복구가 가능합니다.
7. missingNo.3에서 exposed되는 비트
random_matrix(F, 52) 동작 분석을 통해 MT 32-bit 단위 output stream 중 어느 index가 사용되고, exposed 되는지 알 수 있습니다.
A matrix의 element 1개 <- size=6의 벡터 1개
size=6의 벡터 1개 <- getrandbits(43)의 결과 6개
여기서 주의해야 하는 지점이 2개가 있습니다.
vector의 원소를 만들 때마다 rand()를 호출합니다.
vector_space.random_element in free_module.pyrand()는 MT 32-bit output 2개를 사용합니다.
- 원소를 만드는 중에 rejection이 일어날 수 있습니다.
_randbelow in random.pygetrandbits(43)은 MT 32-bit outpu 2개를 사용합니다.
- rejection이 일어나면 기존에 뽑은
output 2개는 버리고 새로 2개 뽑습니다.
- rejection이 안일어날 때까지 반복합니다.
아래는 MT 32-bit output stream에서 노출되는 비트 수에 대한 예제를 표로 적어보았습니다.
- 1번째
vector element를 만들 때 rejection이 2번 일어남
- 3번째
vector element를 만들 때 rejection이 1번 일어남
| MT output stream idx |
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
13 |
14 |
15 |
16 |
17 |
18 |
19 |
20 |
21 |
22 |
23 |
| no rejection |
0 |
0 |
32 |
11 |
0 |
0 |
32 |
11 |
0 |
0 |
32 |
11 |
0 |
0 |
32 |
11 |
0 |
0 |
32 |
11 |
0 |
0 |
32 |
11 |
| 위에서 말한 상황 |
0 |
0 |
0 |
0 |
0 |
0 |
32 |
11 |
0 |
0 |
32 |
11 |
0 |
0 |
0 |
0 |
32 |
11 |
0 |
0 |
32 |
11 |
0 |
0 |
따라서 partial exposed 상황에서 MT state 복구를 하기 위해서는 1. 각 element에서 rejection이 몇 번 일어났으며, 2. 보이는 bit가 MT output stream의 어느 index인지 정확하게 알아야 합니다.
8. temper와 twist
참고 코드: https://github.com/eboda/mersenne-twister-recover/blob/master/MersenneTwister.py
extract는 temper와 같은 뜻입니다.
def extract(self):
""" Extracts a 32bit word """
if self.index >= 624:
self.twist()
x = self.mt[self.index]
x ^= x >> 11
x ^= (x << 7) & 0x9d2c5680
x ^= (x << 15) & 0xefc60000
x ^= x >> 18
self.index += 1
return self._int32(x)
def twist(self):
""" The twist operation. Advances the internal state """
for i in range(624):
upper = 0x80000000
lower = 0x7fffffff
x = self._int32((self.mt[i] & upper) +
(self.mt[(i + 1) % 624] & lower))
self.mt[i] = self.mt[(i + 397) % 624] ^ (x >> 1)
if x & 1 != 0:
self.mt[i] ^= 0x9908b0df
검증식을 만들기 위해서는 두 함수를 이해할 필요가 있습니다.
MT는 624개의 32bit 정수로 이루어진 state를 가지고 있고, 랜덤을 호출할 때마다 temper(위 코드는 extract)를 해서 32비트 정수를 출력합니다.
그리고, 624번의 랜덤 호출이 끝나면 state를 twist해서 새로운 state로 만듭니다.
여기서 주의깊게 봐야하는 점은 twist를 사용하면 3개의 정수 (s[i], s[i+1], s[i+397])을 사용해서 새로운 s[i], 즉 s[i+624]를 만들어냅니다. (코드 상으로는 s = mt 입니다.)
9. twist 좀 더 자세히
def twist(self):
""" The twist operation. Advances the internal state """
for i in range(624):
upper = 0x80000000
lower = 0x7fffffff
x = self._int32((self.mt[i] & upper) +
(self.mt[(i + 1) % 624] & lower))
self.mt[i] = self.mt[(i + 397) % 624] ^ (x >> 1)
if x & 1 != 0:
self.mt[i] ^= 0x9908b0df
(새로운 s[i]는 s[i+624]와 같은 뜻입니다.)
twist는 아래와 같이 한글로 풀어 쓸 수 있습니다.
x = s[i]의 상위 1비트 + s[i+1]의 하위 31비트
s[i+624] = s[397] ^ (x >> 1)
if s[i+1] 하위 1비트가 1이라면:
s[i+624] ^= 0x9908b0df
10. (i, i+1, i+397) -> i+624 검증식
만약 출력으로 보이는 (a′,b′,c′,d′) 네 정수가 원래 (i,i+1,i+397,i+624) 자리에 있었는지 알고 싶다면 twist를 변형해 검증식으로 사용할 수 있습니다.
(a′,b′,c′,d′)를 untemper한 값을 (a,b,c,d)라고 할 때, 아래 코드를 사용하면 됩니다.
def validate(a, b, c, d):
x = (a & 0x80000000) + (b & 0x7fffffff)
v = c ^ (x >> 1)
if x & 1 != 0:
v ^= 0x9908b0df
return v == d
11. d=i+1, (d, d+396, d+623) 검증식
그런데, s[i]는 상위 1비트만 사용합니다. 그렇다면 s[i] 2가지의 경우를 다 계산해보는 (i+1,i+397)→i+624(i+1,i+397)→i+624 검증식을 만들 수 있지 않을까요?
def validate(b, c, d):
for a in [0, 1]:
x = (a << 31) + (b & 0x7fffffff)
v = c ^ (x >> 1)
if x & 1 != 0:
v ^= 0x9908b0df
if v == d:
return True
return False
이렇게 d=i+1이라 할 때의 (d,d+396,d+623) 검증식을 만들었습니다.
이 검증식을 사용하면 눈에 보이는 MT output 3개가 원래 stream에서의 상대적인 위치를 알아낼 수 있고, 각 구간별 rejection 횟수를 알아낼 수 있습니다.
그리고 검증식을 통과하는 삼중항이 충분히 많이 발견된다면 원래 stream의 index도 알아낼 수 있게 됩니다.
12. missingNo.3에는 바로 사용할 수 없다
문제가 하나 있습니다. 모든 triplet이 rejection 때문에 노출되냐 안되냐는 둘째치고, "missingNo.3에서 exposed되는 비트"에서 보셨듯이 32-bit 전체 exposed 되는 output은 항상 짝수 index에만 있습니다.
즉, d와 d+396을 짝수에 맞추면 d+623은 항상 홀수 index라서 최대 11 bit exposed라서 검증식을 사용할 수 없게 됩니다. 이것을 돌파하는게 이번 문제의 메인입니다.
13. (d, d+792, d+1246) 검증식은 가능한가
KalmarCTF discord에서는 대회 종료 후 kyc2915 유저가 기존의 검증식에서 index 차이를 2배한 (d,d+792,d+1246) 검증식 아이디어를 떠올렸다고 공유했고, soon_haari 출제자가 그것이 정확하다고 답했습니다. 만약 이 검증식이 가능하다면 모두 짝수 비트를 참조하므로 32 bit exposed 된 범위에 포함될 수 있습니다. 그러면 이 검증식은 정말로 만들 수 있을까요?
def F(s):
x = ((0 or 1) << 31) + (s & 0x7fffffff)
if x & 1:
return (x >> 1) ^ 0x9908b0df
else:
return x >> 1
편의를 위해 F(s)를 위와 같이 정의하면
세 개의 식이 합쳐져 (d,d+396,d+792,d+1246) 검증식이 됩니다.
그런데 F(s)는 F(a⊕b) = F(a) ⊕ F(b) 성질을 만족시킵니다(F(a)와 F(b)의 x가 홀수인지 짝수인지에 대한 모든 경우를 다 풀어 써보는 걸로 감을 잡았습니다). 따라서, 다음과 같이 s396 관련 항이 소거된 (d,d+792,d+1246) 검증식이 유도됩니다.
# 14. F, det1, det2 구현 및 테스트
import random
s = [random.getrandbits(32) for _ in range(10000)]
def F(s, b):
x = (b << 31) + (s & 0x7fffffff)
if x & 1:
return (x >> 1) ^ 0x9908b0df
else:
return x >> 1
def det1(s0, s396, s623):
for b in [0, 1]:
if s623 == s396 ^ F(s0, b):
return 1
return 0
def det2(s0, s792, s1246):
for b1 in [0, 1]:
for b2 in [0, 1]:
if s1246 == s792 ^ F(F(s0, b1), b2):
return 1
return 0
print('(d, d+396, d+623)')
count = 0
for i in range(10000 - 623):
count += det1(untemper(s[i]), untemper(s[i+396]), untemper(s[i+623]))
print(f'{count} / {10000 - 623}\n')
print('(d, d+792, d+1246)')
count = 0
for i in range(10000 - 1246):
count += det2(untemper(s[i]), untemper(s[i+792]), untemper(s[i+1246]))
print(f'{count} / {10000 - 1246}\n')
untemper는 생략했습니다.
14. rejection sampling, DSU
앞서 설명한 det1은 상위 11비트만 확인하기에 false positive가 많습니다. 따라서 det1은 weak clue로만 사용하고, 최대한 det2를 사용해서 각 계수의 MT output 상대 index를 확정짓는 것이 바람직합니다.
여기서 이 문제의 가장 까다로운 부분은 각 계수 사이에 일어난 rejection 횟수를 모른다는 것입니다.
저는 이 문제를 해결하기 위해 다음 순서대로 접근했습니다.
DSU(Disjoint Set Union)으로 동일 계수를 포함한 triplet들을 연결(component라고 명명함)- det2로는 단서가 부족해서
det4 추가
- 인접한 계수끼리 붙일 때 참고할 용도로
det1 보수적으로 추가
- det2 + det4로 만든 가장 큰 component를 중심으로 삼기
- 그 다음으로 큰 component들을 (rejection 나면 밀리는 만큼인) 2의 배수만큼 MT output index를 띄우면서 배치
- 해당 배치가 맞는지는 624개 정수가 연결되면 MT state 복구 --> matrix 생성해봐서 동일한지 확인
- 이 과정을 DFS로 탐색
복구한 MT state가 matrix 만들 때와 같다는 보장이 없잖아요?
가장 처음의 계수를 만들 때 rejection이 몇 번 발생했는지 알아낼 수 없기 때문에 나올 수 있는 질문인데, 상관없습니다. 결국 맨 처음 rejection이 0번~1000번인 state를 찾더라도 A만 재현하면 되기 때문입니다.
맨 처음 나오는 계수가 triplet으로 묶이는게 없으면 초기 state 복구 안되는거 아니에요?
비슷한 맥락입니다. state는 624개의 정수로 이루어져있고, 624개의 output을 만들면 twist로 다음 624개를 갱신합니다. 그 과정을 잘 살펴보면, 새로운 state[i]에 덮어 씌우는게 아니라, state[i+624]에 추가해서 MT output stream이 624가 끝이 아닌 무한 길이의 stream으로 간주할 수 있습니다.
질문의 상황에서 state 복구를 시도하면 [624k + l] index부터 시작해서 624개의 연속된 정수 stream이 찾아질 겁니다. twist는 선형이므로 앞으로 되감을 수 있고, [0]부터 시작하는 state를 만들어 낼 수 있습니다.
15. MT state --> pyseed --> Sage seed
| 추가 예정
16. Ab.sobj 시각화
PPT나 Markdown으로 Ab.sobj를 예시로 원소 간 연결 관계와 그 위치를 표현해보고 싶었는데 det2/det4 hit triplet 개수는 2485/2466개여서 쉽지 않았습니다. 그래서 Codex를 활용해서 html로 만들어보았습니다. 아래 링크에서 다운받으실 수 있습니다.
https://drive.google.com/file/d/1dg5LHwVv81Vg8pLci-OhWnXspaN-CaA2/view?usp=sharing
17. 마치며
이번에 해당 문제를 복기하면서 MT rejection sampling을 연습할 수 있는 좋은 문제였습니다.
18. 참고자료
[1] soon_haari, "MissingNo.3", KalmarCTF 2026, https://kalmarc.tf/challenges#MissingNo.3-23
[2] soon_haari, "MissingNo.3", Dreamhack, https://dreamhack.io/wargame/challenges/2825
[3] soon_haari, "MissingNo.3 Writeup", Github, https://github.com/soon-haari/my-ctf-challenges/tree/main/2026-kalmar/missingno3
[4] soon_haari, "import random", https://soon.haari.me/import-random/
[5] Neobeo, "MissingNo.", OICC 2025, https://github.com/AustICCQuals/Challenges2025/tree/main/crypto/missingno
[6] RBTree, "Breaking Python random module", https://rbtree.blog/posts/2021-05-18-breaking-python-random-module/
[7] eboda, "mersenne-twister-recover", https://github.com/eboda/mersenne-twister-recover/blob/master/MersenneTwister.py
[8] kyc2915 and soon_haari, messages in KalmarCTF discord