[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.](https://github.com/AustICCQuals/Challenges2025/tree/main/crypto/missingno) from OICC 2025. ```py # 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](https://github.com/sagemath/sage/commit/12afbff1651a2d91ef5d911b22da15ab525e89d9)에서 `R.random_element` 동작이 변경되어 명시한 것이었습니다. 따라서 아래의 코드 레벨로 알아보는 동작은 SageMath 10.7 내용을 소개합니다. ## 2-3. Dreamhack Version KalmarCTF 2026에서는 고정된 Ab.sobj의 seed값을 알아내야 했다면, Dreamhack은 접속 시마다 변경되는 seed를 5분 내로 계산해야 합니다. # 3. random_matrix(F, 52) 동작 요약 ## random_matrix in [matrix/](https://github.com/sagemath/sage/blob/10.7/src/sage/matrix/special.py#L215)[special.py](http://special.py) **Args:** - `ring` = GF(p^6) - `nrows` = 52 - `ncols` = 52 ```py 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 ``` ## A.randomize in [matrix2.pyx](https://github.com/sagemath/sage/blob/10.7/src/sage/matrix/matrix2.pyx#L10092) 각 원소들에 대해 하나씩 돌아가면서 `set_unsafe(base_ring().random_element())` 실행 ```py 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 >5, b=genrand_uint32(self)>>6; return PyFloat_FromDouble((a*67108864.0+b)*(1.0/9007199254740992.0)); } ``` ## **\_random_Random_getrandbits_impl in [\_randommodule.c](https://github.com/python/cpython/blob/3.12/Modules/_randommodule.c#L488)** *k* = 43이므로(32bit 초과하므로) `words = 2` `getrand_uint32()`를 2번 실행 여기서 32비트 + 상위 11비트만 쓰는 로직이 나옴 ```c 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.py` - `rand()`는 MT 32-bit `output` 2개를 사용합니다. - 원소를 만드는 중에 rejection이 일어날 수 있습니다. - `_randbelow` in `random.py` - `getrandbits(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** 참고 코드: `extract`는 `temper`와 같은 뜻입니다. ```py def extract(self): """ Extracts a 32bit word """ if self.index >= 624: self.twist() x = self.mt[self.index] x ^= x >> 11 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 좀 더 자세히** ```py 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)라고 할 때, 아래 코드를 사용하면 됩니다. ```py 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 검증식을 만들 수 있지 않을까요? ```py def validate(b, c, d): for a in [0, 1]: x = (a > 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 된 범위에 포함될 수 있습니다. 그러면 이 검증식은 정말로 만들 수 있을까요? ```py def F(s): x = ((0 or 1) > 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 구현 및 테스트** ```py import random s = [random.getrandbits(32) for _ in range(10000)] def F(s, b): x = (b > 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는 생략했습니다. # 15. rejection sampling, DSU 앞서 설명한 det1은 상위 11비트만 확인하기에 false positive가 많습니다. 따라서 det1은 weak clue로만 사용하고, 최대한 det2를 사용해서 각 계수의 MT output 상대 index를 확정짓는 것이 바람직합니다. 여기서 이 문제의 가장 까다로운 부분은 각 계수 사이에 일어난 rejection 횟수를 모른다는 것입니다. 저는 이 문제를 해결하기 위해 다음 순서대로 접근했습니다. 1. `DSU`(Disjoint Set Union)으로 `동일 계수를 포함한 triplet들을 연결`(component라고 명명함) 2. det2로는 단서가 부족해서 `det4 추가` 3. 인접한 계수끼리 붙일 때 참고할 용도로 `det1 보수적으로 추가` 4. det2 + det4로 만든 가장 큰 component를 중심으로 삼기 1. 그 다음으로 큰 component들을 (rejection 나면 밀리는 만큼인) 2의 배수만큼 MT output index를 띄우면서 배치 2. 해당 배치가 맞는지는 624개 정수가 연결되면 MT state 복구 --> matrix 생성해봐서 동일한지 확인 3. 이 과정을 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를 만들어 낼 수 있습니다. # **16. MT state --> pyseed --> Sage seed** | 추가 예정 # 17. Ab.sobj 시각화 Codex를 사용해서 Ab.sobj로 제공된 triplet들을 html로 시각화 시켜보았습니다. # 18. 마치며 이번에 해당 문제를 복기하면서 MT rejection sampling을 연습할 수 있는 좋은 문제였습니다. # 19. 참고자료 \[1\] soon_haari, "MissingNo.3", KalmarCTF 2026, \[2\] soon_haari, "MissingNo.3", Dreamhack, \[3\] soon_haari, "MissingNo.3 Writeup", Github, \[4\] soon_haari, "import random", \[5\] Neobeo, "MissingNo.", OICC 2025, \[6\] RBTree, "Breaking Python random module", \[7\] eboda, "**mersenne-twister-recover"**, \[8\] kyc2915 and soon_haari, messages in KalmarCTF discord