Basically, there is a TCP server listening to incoming connections. We simply use netcat (or telnet) to connect to it:
$ nc ctf3.codegate.org 10909 a? c? m? Bad values
Hopefully they gave us a hint:
HINT: "Lucy in the CodeGate with diamonds"Ok... there's a Beatles song named Lucy in the Sky with Diamonds but this is completely unrelated.
Looking at the uppercase letters, we see LCG which can stands for Linear Congruential Generator, and not a surprise the parameters of this generator are a, c and m, the three parameters we are asked to give. After reading the wikipedia page, we try to enter valid (LCG-compliant) a, c and m:
$ nc ctf3.codegate.org 10909 a? 65 c? 7 m? 256 a=65 c=7 m=256 s=1 \x1c\x20\x2c\xc4\x8b\x9e\xb8\x7d\xe5\xe6\x3c\xf5\x5f\x77\xac\x51\xe8\xd3 \xe7\x74\x31\x29\x0e\xa3\xa9\x98\xcb\x37\xac\xf5\x36\x80\x4f\x0f\x9f\x0e \xfe\xeb\xc7\x55\x05\x06\x5c\xdb\xb0\x40\x8d\x65\xde\xea\x08\xcb\x64\x49 \x6d\xef\xb9\xa3\x94\x2f\x41\x5e\x30\x8d\x45\x25\xfc\x6f\x8a\xa1
There we are, server accepted our input and replied us two things:
- our LCG parameters a, c and m, and s probably standing for the seed of the PRNG
- a string which is the hexadecimal representation of a byte stream The next step was to think of the classic Vernam Cipher - we didn't. Thus, the idea was to use the LCG parameters and the seed to generate a stream of pseudorandom numbers and XOR this as a byte stream with the byte stream that is given to us by the server. The following Python code does all of this by connecting to the server, sending the LCG parameters, receiving the byte stream and XORing it with the PRNG and finally displays the string.
#!/usr/bin/python import socket host, port = "ctf3.codegate.org", 10909 # working LCG parameters # multiplier (a), increment (c), modulus (m) and original seed (s) a, c, m, s = 65, 7, 256, 1 # Linear Congruential Generator of parameters a,c,m and global seed s def lcg(): global s s = (a*s+c)%m return s def main(): k = socket.socket(socket.AF_INET, socket.SOCK_STREAM) k.connect((host, port)) # Send valid a,c,m Linear Congruential Generator parameters k.recv(4), k.send(str(a)+"\n") k.recv(4), k.send(str(c)+"\n") k.recv(4), k.send(str(m)+"\n") # Receive confirmation of parameters, seed and ciphered text d = k.recv(1024) k.close() # Extract ciphered text (store integers) t = [int(i,16) for i in d.split('\n').split('\\x')[1:]] # XOR it with running LCG and display result print "".join([chr(i^lcg()) for i in t]) if __name__ == '__main__': main()Run it and read the flag!
$ ./17.py To:You Dear CTF Player, Your flag is: ULearnLCG4Fun&Profit -- LM**2.Thank you Codegate for this original crypto challenge and well done to teams who have solved it!