Write-up Codegate 2010 #17 - Crypto, Linear Congruential Generators and Vernam Cipher, the power of XOR

Challenge #17 was crypto, based on Linear Congruential Generators (LCG), a well known pseudorandom number generator (PRNG), and the Vernam Cipher which is basically a XOR cipher relying on exclusive OR . Sadly, we did not succeed this challenge in time. However my friend Ivan found it afterwards thanks to Julianor (a staff member).

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!