2023 Christmas CTF
This post will probably be the last post of 2023. I wish everyone had a nice year, and even better one incoming.
2023 Christmas CTF was held on Dreamhack, with users as authors.
2 crypto challenges were made in total. Christmas tree seedling by me and Tropical Santa by RBTree.
I will breifly explain the solutions, since I think both of the challenges were not too hard, but absolutely challenging. Solve code will not be provided because… what’s the fun in that? :)
Also, Tropical Santa has a backstory that is a little bit related to me.
Christmas tree seedling
chall.py
import sys; sys.set_int_max_str_digits(100000)
import random; getstate = lambda x: random.Random(x).getstate()
from secret import flag, banner
print(banner)
"The only supported seed types are: None, int, float, str, bytes, and bytearray."
"Let's try all of them!"
# s_None = None # Edit: Wait, this is used for initialization! This ain't a seed at all!
s_int1 = int(input("Int seed 1 please: ")); assert 2**40000 <= s_int1 < 2**80000
s_int2 = int(input("Int seed 2 please: ")); assert 2**20000 <= s_int2 < 2**40000
s_int3 = int(input("Int seed 3 please: ")); assert 2**2000 <= s_int3 < 2**20000
s_int4 = int(input("Int seed 4 please: ")); assert 0 <= s_int4 < 2**2000
s_int5 = int(input("Int seed 5 please: ")); assert s_int5 < 0
# s_float = float(input("Float seed please: ")) # Edit: Nah, this is too useless.
s_str = input("String seed please: ")
s_bytes = bytes.fromhex(input("Bytes seed please: "))
# s_bytearray = bytearray.fromhex(input("Bytearray seed please: ")) # Edit: I think this one's same with bytes one.
assert len(set(map(getstate, [s_int1, s_int2, s_int3, s_int4, s_int5, s_str, s_bytes]))) == 1
"Oh right, almost forgot the most important one...."
the_most_important_one = "Merry Christmas! You are the True winner, regardless of the ranking, running nonstop towards your dreams! Thanks for playing, and have fun!!"
assert s_str == s_int1.to_bytes(10000, "big")[-len(s_str):].decode() == the_most_important_one
print(flag)
Python’s random is implemented with the Mersenne Twister.
This challenge’s goal is to find multiple seeds that leads to the same state.
There is a CPython implementation for the seeding algorithm, but luckily I ported one into python. This should be helpful.
def seed(s):
if type(s) == int:
n = abs(s)
elif type(s) == str or type(s) == bytes or type(s) == bytearray:
if type(s) == str:
s = s.encode()
n = int.from_bytes(s + hashlib.sha512(s).digest(), "big")
elif s == None:
print("NoneType seed leads to random result")
exit()
elif type(s) == float:
raise NotImplementedError # cuz I was lazy..
uint32_mask = 1 << 32
mt = [0 for i in range(624)]
mt[0] = 0x12bd6aa
for i in range(1, 624):
mt[i] = (0x6c078965 * (mt[i - 1] ^ (mt[i - 1] >> 30)) + i) % uint32_mask
keys = []
while n:
keys.append(n % uint32_mask)
n >>= 32
if len(keys) == 0:
keys.append(0)
i, j = 1, 0
for _ in range(max(624, len(keys))):
mt[i] = ((mt[i] ^ ((mt[i-1] ^ (mt[i-1] >> 30)) * 0x19660d)) + keys[j] + j) % uint32_mask
i += 1
j += 1
if i >= 624:
mt[0] = mt[623]
i = 1
j %= len(keys)
for _ in range(623):
mt[i] = ((mt[i] ^ ((mt[i-1] ^ (mt[i-1] >> 30)) * 0x5d588b65)) - i) % uint32_mask
i += 1
if i >= 624:
mt[0] = mt[623]
i = 1
mt[0] = 0x80000000
state = (3, tuple(mt + [624]), None)
return state
String or bytes seeds uses sha512 hash to make them into integer, which was interesting to me.
I didn’t study much about float seeds, because there are only $2^{32}$ float numbers. Didn’t seem too much meaningful to me.
Key size matters for this algorithm, that’s why there are so many range assertions for integer seeds.
Reversing the algorithm shouldn’t be too hard, especially if you are familiar with PS. I saw one user solved this despite he wasn’t much into cybersecurity.
Wish all of you solve this and be good friends with Mersenne Twister seed.
Don’t forget:
the_most_important_one = "Merry Christmas! You are the True winner, regardless of the ranking, running nonstop towards your dreams! Thanks for playing, and have fun!!"
Tropical Santa
task.py
#!/usr/bin/env python3
from tropical import *
import hashlib
import itertools
import os
import random
import signal
import string
def handler(_signum, _frame):
print("Time out!")
exit(1)
def PoW():
return True
random.seed(os.urandom(10))
CHARSET = string.ascii_letters + string.digits
to_digest = "".join(random.sample(CHARSET, 20))
result = hashlib.sha256(to_digest.encode()).hexdigest()
print(f"SHA-256( XXXX + {to_digest[4:]} ) = {result}")
user_input = input("What is the answer? > ").strip()
return user_input == to_digest[:4]
def main():
signal.signal(signal.SIGALRM, handler)
signal.alarm(60)
if not PoW():
print("PoW failed.")
exit(1)
print("Welcome!")
for stage in range(10):
signal.alarm(5)
print(f"=== [STAGE {stage + 1}] ===")
privkey, pubkey = PrivateKey.gen_key_pair()
msg = os.urandom(16)
signature = privkey.sign(msg)
print(f"Here is a public key: {pubkey},")
print(f"and this is the signature: {signature}")
print(f"for a message {msg.hex()}.")
user_msg = bytes.fromhex(input("Give me your message > ").strip())
if user_msg == msg:
print(">:(")
exit(1)
print("Give me your signature: ")
sig1 = Polynomial([Elem(int(v)) for v in input("1 > ").strip().split()])
sig2 = Polynomial([Elem(int(v)) for v in input("2 > ").strip().split()])
sig3 = Polynomial([Elem(int(v)) for v in input("3 > ").strip().split()])
sig4 = Polynomial([Elem(int(v)) for v in input("4 > ").strip().split()])
user_sig = (sig1, sig2, sig3, sig4)
print("Now verifying...")
if not pubkey.verify(user_msg, user_sig):
print(":(")
exit(1)
with open("./flag", "r") as f:
print("Congratz.")
print(f"Flag is: {f.read()}")
if __name__ == "__main__":
main()
tropical.py
from hashlib import sha512
import os
...
class Elem:
...
class Polynomial:
...
class PublicKey:
...
class PrivateKey:
...
This challenge is about an interesting signature scheme called Tropical.
It was based on the following paper: More forging (and patching) of tropical signatures.
It would be good enough to find the paper and implementing it, but I have a little backstory.
While I was reviewing the according challenge, I first tried solving it without reading the paper. And eventually found an interesting solution.
Unfortunately, RBTree said there were minor implementation errors in the chall, so my attack didn’t work after the fix.
However after modifying a slight bit with some deep thinking, I was able to solve the challenge which was exactly same with the paper with much simpler attack.
I emailed the paper authors about my attack considering RBTree’s advice.
To me, it felt like a Christmas present.
My attack explanation will be following.
Thanks for reading and I wish all of you happy new year, again.
Hope to meet all of you in person someday.
Exploiting the fact that the result of division is not unique
Tropical polynomial division was explained in More forging (and patching) of tropical signatures. It is pretty obvious that result of division is not unique after some tests.
However, the following properties always hold.
- $(R / S) \otimes S = R$.
- $R \otimes S$ is always divisible by $S$, however the result is more likely not $R$.
And the division algorithm was used to check if both $S_1$ and $S_2$ are multiple of $H$. And also used during the succeeding attack.
I thought this fact was very interesting, and try to use it generating random signature that can pass the verification.
$M$ is given, and it is hard to factorize since first and last coefficient is 0, which is the smallest.
And the challenge is to generate $m, S_1, S_2, N$ which satisfies the following tests.
- $H = {hash}(m)$
- $S_1 \otimes S_2 = M \otimes N \otimes H \otimes H$
- And some more including both $S_1, S_2$ should be divisable by $H$
I first generated random $N$ of size (2 * d, 2 * r), and $m, H$ which are random message and hash of it.
And defined $S_1, S_2 = H \otimes M, H \otimes N$. This signature fails because $S_1$ is mono-multiple of $H \otimes N$, and same for $S_2$.
I will define $T = S_1 \otimes S_2 = M \otimes N \otimes H \otimes H$.
When I put value of $T / S_2$ info $S_1$, the multiplication will succeed, however the verification will fail because $S_1$ is not divisible to $H$.
Then what will happen if $S_1 = (T / (S_2 \otimes H)) \otimes H$?
$S_1$ is divisible by $H$, but does the multiplication succeed?
We can see that the multiplication also succeeds, and the generated $S_1$ passes all the tests on it, just $S_2$ fail.
$S_2$ can also be regenerated through the same method.
The regeneration of $S_1, S_2$ should be calculated sequentially, not simultaneously.
After that, the signature of $(m, S_1, S_2, N)$ successfully verfies.
This attack always succeeds for any kind of $M$, and any $m$ is allowed to use.