Wednesday, March 17, 2010

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!

2 comments:

  1. how can you know "a=65 c=7 m=256" ??

    ReplyDelete
  2. Hello, indeed very good comment I didn't specify that and these numbers may come from nowhere.

    According 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 :)

    ReplyDelete