[crypto] KalmarCTF 2026, Dreamhack M4 - MissingNo.3
1. Overview
This challenge appeared in KalmarCTF 2026, received 2 solves, and was later uploaded to Dreamhack as Master 4, or Level 10 before the difficulty system was reorganized.
It was a very interesting challenge that required accurately understanding rejection sampling in Mersenne Twister, SageMath's random_matrix, and Python randrange behavior.
This article is a CTF writeup, but since the same challenge is uploaded to Dreamhack, I was careful not to go beyond the scope explained in the writeup by the challenge author, soon_haari. Therefore, I do not publish the full solver code, and some algorithms are explained in a simplified form.
2. Challenge Information
2-1. MissingNo.
The OICC 2025 challenge MissingNo. mentioned in the statement has the following setting.
b: public vector of length 52
A: public matrix of size 52x52
s: random vector of length 52
r: random integer
f: vector of length 52 whose elements are the FLAG characters
The goal is to recover f from b = As + fs.
The intended solution is to solve it with lattice reduction, namely LLL or BKZ.
However, there can be an unintended solution where the Sage seed can be computed just from A generated by random_matrix(F, 52)[:,:-3], which immediately reproduces s and r.
2-2. MissingNo.3
This challenge intentionally uses that point. The phrase "forensics challenge" in the statement is a kind of joke, because solving it requires reading the contents of the 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{}")
When connecting to the challenge, we can learn that Sage 10.7 is being used.
chall.sage itself is simple code where we only need to find a seed that reproduces the matrix A.
0xdead1337cec2a21ad8d01f0ddabce77f57568d649495236d18df76b5037444b1 = 0x634270e2ad7 ^ 6. This affects the behavior of random_matrix in the SageMath 10.7 environment.
At the time of the CTF, the version was printed, so I tried to find meaningful parts from version differences. What was revealed after the contest ended was that the behavior of R.random_element changed in 10.8.beta2, which is why the version was specified. Therefore, the behavior discussed below at the code level is for SageMath 10.7.
2-3. Dreamhack Version
In KalmarCTF 2026, the goal was to recover the seed value for the fixed Ab.sobj, while in the Dreamhack version, the seed changes on every connection and must be computed within 5 minutes.
3. Summary of random_matrix(F, 52) Behavior
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
For each entry, it iterates one by one and executes 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(...))
Since the given R is GF(p^6), it executes vector_space().random_element().
vector_space().random_element() internally executes random_element() again rank times.
At this point, degree() = 1, so it executes randrange(order() = p).
Since log2(p)=42.6…, randrange(p) uses 32+11 bits.
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)
Starting from 10.8.beta9, if there are no args and kwds, it directly executes return self.from_integer(randrange(self.order())), which changes the behavior. This is why the challenge explicitly states that the sage version is 10.7.
vector_space.random_element in free_module.py
Since rank() is 6, it executes R.random_element() 6 times.
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
Observing the A[0][0] Element of Ab.sobj
(4309812620277z6^5 + 564698381371z6^4 + 2482046981087z6^3 + 3286340353355z6^2 + 2396756075089z6 + 4896304883077)
When observing it while knowing the seed, we can confirm that it is generated through randrange from the lowest degree coefficient.
4. Summary of Python randrange() Behavior
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 is defined as _randbelow_with_getrandbits.
k = 43, so it executes r = getrandbits(43).
If r ≥ n, rejection occurs, and it executes once more.
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
The rand() from free_module.py above consumes 2 MT outputs.
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
Since k = 43, which is greater than 32 bits, words = 2.
It executes getrand_uint32() twice.
This is where the logic that uses 32 bits + the top 11 bits appears.
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. Summarizing Only the Necessary Behavior
Sage uses MT (Mersenne Twister), Python's default random module.
One matrix element consists of a vector of 6 coefficients.
Before making one vector coefficient, rand() consumes 2 MT outputs.
getrandbits(43) also first consumes 2 MT outputs and checks the condition; if rejection occurs, it keeps consuming 2 more outputs until rejection no longer occurs.
6. Mersenne Twister state recovery
Mersenne Twister uses an internal state that is an array of 624 32-bit values.
Therefore, the fact that the state can be recovered if we know 624 consecutive 32-bit integer outputs is a topic covered by many blogs and RandCrack Github repositories.
And even if they are not consecutive, roughly speaking, state recovery is possible if we know about 624 integers and which output positions they came from, although this is an imprecise summary.
7. Bits exposed in missingNo.3
By analyzing the behavior of random_matrix(F, 52), we can know which indices of the MT 32-bit output stream are used and exposed.
A matrix element 1 <- vector of size=6 1
vector of size=6 1 <- getrandbits(43) result 6
There are 2 points to be careful about here.
- It calls
rand() every time it creates a vector element.
vector_space.random_element in free_module.pyrand() uses 2 MT 32-bit outputs.
- Rejection can occur while creating an element.
_randbelow in random.pygetrandbits(43) uses 2 MT 32-bit outputs.
- If rejection occurs, the 2 outputs that were already drawn are discarded and 2 new outputs are drawn.
- This repeats until rejection does not occur.
Below is a table showing the number of exposed bits in the MT 32-bit output stream.
- 2 rejections occur while creating the 1st
vector element
- 1 rejection occurs while creating the 3rd
vector element
| 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 |
| the case described above |
0 |
0 |
0 |
0 |
0 |
0 |
32 |
11 |
0 |
0 |
32 |
11 |
0 |
0 |
0 |
0 |
32 |
11 |
0 |
0 |
32 |
11 |
0 |
0 |
Therefore, to recover the MT state in a partial exposed situation, we need to know exactly 1. how many rejections occurred for each element and 2. which index in the MT output stream the visible bit came from.
8. temper and twist
Reference code: https://github.com/eboda/mersenne-twister-recover/blob/master/MersenneTwister.py
extract means the same thing as 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
To make validation equations, we need to understand these two functions.
MT has a state consisting of 624 32bit integers, and every time randomness is called, it applies temper (called extract in the code above) and outputs a 32-bit integer.
Then, after 624 random calls are over, it twists the state into a new state.
The point to pay attention to is that twist uses three integers (s[i], s[i+1], s[i+397]) to create a new s[i], that is, s[i+624]. In the code, s = mt.
9. twist in More Detail
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
(new s[i] means the same thing as s[i+624].)
twist can be written out in words as follows.
x = upper 1 bit of s[i] + lower 31 bits of s[i+1]
s[i+624] = s[397] ^ (x >> 1)
if the lower 1 bit of s[i+1] is 1:
s[i+624] ^= 0x9908b0df
10. (i, i+1, i+397) -> i+624 validation equation
If we want to know whether four integers (a′,b′,c′,d′) visible in the output were originally at positions (i,i+1,i+397,i+624), we can transform twist into a validation equation.
If the untempered values of (a′,b′,c′,d′) are (a,b,c,d), we can use the code below.
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) validation equation
However, s[i] only uses the upper 1 bit. Then, couldn't we make a (i+1,i+397)→i+624(i+1,i+397)→i+624 validation equation by trying both possibilities for s[i]?
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
This gives a (d,d+396,d+623) validation equation when d=i+1.
Using this validation equation, we can know the relative positions in the original stream of three visible MT outputs, and we can know the number of rejections in each interval.
And if enough triplets pass the validation equation, we can learn the original stream indices.
12. It Cannot Be Used Directly in missingNo.3
There is one problem. Aside from whether every triplet is exposed because of rejection, as seen in "Bits exposed in missingNo.3", outputs where the full 32-bit value is exposed are always at even indices.
That is, if d and d+396 are matched to even indices, d+623 is always an odd index, so at most 11 bits are exposed and the validation equation cannot be used. Overcoming this is the main point of this challenge.
13. Is the (d, d+792, d+1246) Validation Equation Possible?
After KalmarCTF ended, the user kyc2915 shared on the KalmarCTF discord the idea of doubling the index differences in the existing validation equation to get (d,d+792,d+1246), and the author soon_haari replied that it was correct. If this validation equation is possible, all referenced bits can be included in the range where 32 bits are exposed because all of them are even. Then is this validation equation really possible?
def F(s):
x = ((0 or 1) << 31) + (s & 0x7fffffff)
if x & 1:
return (x >> 1) ^ 0x9908b0df
else:
return x >> 1
For convenience, if we define F(s) as above,
the three equations combine into the (d,d+396,d+792,d+1246) validation equation.
However, F(s) satisfies the property F(a⊕b) = F(a) ⊕ F(b). I got an intuition for this by expanding all cases of whether x in F(a) and F(b) is odd or even. Therefore, the s396 term is canceled as follows, deriving the (d,d+792,d+1246) validation equation.
# 14. Implementing and Testing 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 is omitted.
15. rejection sampling, DSU
The det1 explained above only checks the top 11 bits, so it has many false positives. Therefore, det1 should only be used as a weak clue, and it is preferable to use det2 as much as possible to fix the relative MT output index of each coefficient.
The most difficult part of this challenge is that we do not know the number of rejections that occurred between coefficients.
I approached this problem in the following order.
- Use
DSU (Disjoint Set Union) to connect triplets containing the same coefficient (I call each connected set a component)
- Add
det4 because det2 alone does not provide enough clues
- Conservatively add
det1 as a reference when attaching adjacent coefficients
- Use the largest component made from det2 + det4 as the center
- Place the next largest components while spacing MT output indices by multiples of 2, which is how much they are shifted when rejection occurs
- Check whether the placement is correct by recovering the MT state once 624 integers are connected, then generating the matrix and checking whether it is the same
- Explore this process with DFS
Isn't there no guarantee that the recovered MT state is the same as when the matrix was made?
This question can arise because we cannot know how many rejections occurred when creating the very first coefficient, but it does not matter. In the end, even if we find a state where the first rejection count is 0 to 1000, it is enough as long as it reproduces A.
If the first coefficient is not tied into any triplet, doesn't that mean the initial state cannot be recovered?
This is a similar issue. The state consists of 624 integers, and when 624 outputs are generated, the next 624 values are updated through twist. If we look closely at that process, we can regard the MT output stream as an infinite stream rather than ending at 624, because it is as if the new state[i] is added at state[i+624], rather than overwriting state[i].
In the situation in the question, if we try state recovery, we will find 624 consecutive integers in the stream starting from index [624k + l]. Since twist is linear, we can rewind it and produce a state starting from [0].
16. MT state --> pyseed --> Sage seed
| To be added
17. Ab.sobj Visualization
Using Codex, I visualized the triplets provided as Ab.sobj in HTML.
https://drive.google.com/file/d/1dg5LHwVv81Vg8pLci-OhWnXspaN-CaA2/view?usp=sharing
18. Closing
While reviewing this challenge, it was a good opportunity to practice MT rejection sampling.
19. References
[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