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
Hmm... what?!
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')[1].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!
how can you know "a=65 c=7 m=256" ??
ReplyDeleteHello, indeed very good comment I didn't specify that and these numbers may come from nowhere.
ReplyDeleteAccording to Wikipedia (http://en.wikipedia.org/wiki/Linear_congruential_generator):
"The period of a general LCG is at most m, and for some choices of a much less than that. Provided that c is nonzero, the LCG will have a full period for all seed values if and only if:[2]
1. c and m are relatively prime,
2. a-1 is divisible by all prime factors of m,
3. a-1 is a multiple of 4 if m is a multiple of 4."
So I just chose an LCG verifying this so it has full period m. If I recall correctly, it worked for any other LCG parameters you give that also verified this property. Except those with low m.
It would be great to have the server source or binary to be sure how it was checked :)