0CTF 2017 Quals: oneTimePad{,2}

oneTimePad and oneTimePad2 were two of the crypto challenges of this years 0CTF Quals. The CTF used a scoring system with dynamic points and the challenges were worth 114 and 366 points at the end of the competition.

The author solved these challenges while playing for Cyclopropenylidene, the CTF team of the Chaos Computer Club Hansestadt Hamburg.

oneTimePad

For this task, we are given an encryption routine in form of a python script and a text file containing three ciphertexts.

af3fcc28377e7e983355096fd4f635856df82bbab61d2c50892d9ee5d913a07f
630eb4dce274d29a16f86940f2f35253477665949170ed9e8c9e828794b5543c
e913db07cbe4f433c7cdeaac549757d23651ebdccf69d7fbdfd5dc2829334d1b

The script implements a pseudo random number generator, that is used to generate a stream of 256 bit words: \(k_1, k_2, k_3\). It encrypts three messages by xoring them to corresponding keys.

\begin{equation*} c_1 = m_1 \oplus k_1 \qquad\qquad c_2 = m_2 \oplus k_2 \qquad\qquad c_3 = m_3 \oplus k_3 \end{equation*}

While \(m_1\) contains the flag, \(m_2\) and \(m_3\) are given in the source code. By \(k_i = m_i \oplus c_i\) we can compute the last two outputs of the random number generator.

Let's see how the PRNG works:

def keygen(seed):
    key = str2num(urandom(32))
    while True:
        yield key
        key = process(key, seed)

The seed and the first output are 256 bit values chosen uniformly at random. The next outputs are generated by applying the function process to the last output and the seed.

The function process interprets the 256 bit integers as elements of the galois field \(GF(2^{256})\) using their bits as coefficients of a polynomial. For example the integer 0b101010 corresponds to the polynomial \(X^5 + X^3 + X\). The field is defined with the irreducible polynomial

\begin{equation*} P = X^{256} + X^{10} + X^5 + X^1 + 1 \in \mathbb{F}_2[X]. \end{equation*}

Addition of field elements can be computed as the XOR of the corresponding integers. Back to the function process: It takes \(m, k \in GF(2^{256})\) and computes \((m + k)^2\).

P = 0x10000000000000000000000000000000000000000000000000000000000000425L

def process(m, k):
    tmp = m ^ k
    res = 0
    for i in bin(tmp)[2:]:
        res = res << 1;
        if (int(i)):
            res = res ^ tmp
        if (res >> 256):
            res = res ^ P
    return res

Since we know two consecutive outputs \(k_2, k_3\), we can compute the \(seed\) (the square root is defined for all elements of a characteristic two field):

\begin{equation*} (k_2 + seed)^2 = k_3 \iff seed = \sqrt{k_3} + k_2 \end{equation*}

With the \(seed\) we can compute the first output of the random number generator

\begin{equation*} (k_1 + seed)^2 = k_2 \iff k_1 = \sqrt{k_2} + seed \end{equation*}

and then the plaintext

\begin{equation*} p_1 = k_1 + c_1 \end{equation*}

Decoding \(p_1\) to a string yields the flag:

flag{t0_B3_r4ndoM_en0Ugh_1s_nec3s5arY}

oneTimePad2

In the second part we are given a ciphertext and part of the corresponding plaintext.

0da8e9e84a99d24d0f788c716ef9e99c ... 1b91df5e5e631e8e9e50c9d80350249c

One-Time Pad is used here. You won't know that the flag is flag{ ... }

This part of the challenge also does arithmetic in a galois field. It uses 128 bit integers and interprets them as elements of \(GF(2^{128})\) wich is defined with the irreducible polynomial

\begin{equation*} P = X^{129} + X^7 + X^2 + X + 1 \in \mathbb{F}_2[X]. \end{equation*}

The functions process1 and process2 implement multiplication in \(GF(2^{128})\) and multiplication of \(2 \times 2\) matrices over the same field respectively.

P = 0x100000000000000000000000000000087

def process1(m, k):
    res = 0
    for i in bin(k)[2:]:
        res = res << 1;
        if (int(i)):
            res = res ^ m
        if (res >> 128):
            res = res ^ P
    return res

def process2(a, b):
    res = []
    res.append(process1(a[0], b[0]) ^ process1(a[1], b[2]))
    res.append(process1(a[0], b[1]) ^ process1(a[1], b[3]))
    res.append(process1(a[2], b[0]) ^ process1(a[3], b[2]))
    res.append(process1(a[2], b[1]) ^ process1(a[3], b[3]))
    return res

The random number generator choses the first 128 bit output at random and applies the function nextrand to compute the next output.

def keygen():
    key = str2num(urandom(16))
    while True:
        yield key
        key = nextrand(key)

The nextrand function makes use of the global variables \(A, B\) and \(N\). While \(N\) is chosen randomly at initialization, \(A\) and \(B\) are given in the source code. \(A\) and \(B\) are generators of the finite field.

nextrand uses a square-and-multiply approach to compute the \(N\)-th power of the matrix \(\left( \begin{smallmatrix} A & B \\ 0 & 1 \end{smallmatrix} \right)\):

\begin{equation*} \begin{pmatrix} A & B \\ 0 & 1 \\ \end{pmatrix}^N = \begin{pmatrix} A^N & A^{N-1}B + \dotsb + AB + B \\ 0 & 1 \\ \end{pmatrix} = \begin{pmatrix} A^N & \frac{1 - A^N}{1 - A} \cdot B \\ 0 & 1 \\ \end{pmatrix} \end{equation*}

It uses the entries of the resulting first row to apply the function

\begin{equation*} x \mapsto A^N \cdot x + \frac{1-A^N}{1-A} \cdot B \end{equation*}

to the last output of the RNG. The result is then returned as next output. Furthermore each call to nextrand squares \(N\).

A = 0xc6a5777f4dc639d7d1a50d6521e79bfd
B = 0x2e18716441db24baf79ff92393735345
N = str2num(urandom(16))

def nextrand(rand):
    global N, A, B
    tmp1 = [1, 0, 0, 1]
    tmp2 = [A, B, 0, 1]
    s = N
    N = process1(N, N)  # N <- N^2
    while s:  # tmp2^s * tmp1
        if s % 2:
            tmp1 = process2(tmp2, tmp1)  # tmp1 <- tmp2 * tmp1
        tmp2 = process2(tmp2, tmp2)  # tmp2 <- tmp2^2
        s = s / 2
    return process1(rand, tmp1[0]) ^ tmp1[1]  # rand * tmp1[0] + tmp1[1]

We know the beginning of the plaintext and therefore the first outputs of the RNG. Since \(k_2 = nextrand(k_1)\), we can solve the following equation for \(N\) to get its initial value.

\begin{equation*} \begin{alignedat}{2} && k_2 &= A^N \cdot k_1 + \frac{1 - A^N}{1 - A} \cdot B \\ \iff&& k_2 &= A^N \cdot k_1 + \frac{B}{1 - A} - \frac{A^NB}{1 - A} \\ \iff&& k_2 - \frac{B}{1 - A} &= A^N \cdot k_1 - \frac{A^NB}{1 - A} \\ \iff&& k_2 - \frac{B}{1 - A} &= A^N \cdot \left( k_1 - \frac{B}{1 - A} \right) \\ \iff&& \left( k_2 - \frac{B}{1 - A} \right) \cdot \left( k_1 - \frac{B}{1 - A} \right)^{-1} &= A^N \\ \iff&& \log_{A} \left( \left( k_2 - \frac{B}{1 - A} \right) \cdot \left( k_1 - \frac{B}{1 - A} \right)^{-1} \right) &= N \\ \end{alignedat} \end{equation*}

Now we know with \(k_1\) and \(N\) all values that were chosen randomly. Thus we can reconstruct the keystream and decrypt the complete message:

One-Time Pad is used here. You won't know that the flag is flag{LCG1sN3ver5aFe!!}

Appendix

The given source code:

oneTimePad.py

#!/usr/bin/env python
# coding=utf-8

from os import urandom

def process(m, k):
    tmp = m ^ k
    res = 0
    for i in bin(tmp)[2:]:
        res = res << 1;
        if (int(i)):
            res = res ^ tmp
        if (res >> 256):
            res = res ^ P
    return res

def keygen(seed):
    key = str2num(urandom(32))
    while True:
        yield key
        key = process(key, seed)

def str2num(s):
    return int(s.encode('hex'), 16)

P = 0x10000000000000000000000000000000000000000000000000000000000000425L

true_secret = open('flag.txt').read()[:32]
assert len(true_secret) == 32
print 'flag{%s}' % true_secret
fake_secret1 = "I_am_not_a_secret_so_you_know_me"
fake_secret2 = "feeddeadbeefcafefeeddeadbeefcafe"
secret = str2num(urandom(32))

generator = keygen(secret)
ctxt1 = hex(str2num(true_secret) ^ generator.next())[2:-1]
ctxt2 = hex(str2num(fake_secret1) ^ generator.next())[2:-1]
ctxt3 = hex(str2num(fake_secret2) ^ generator.next())[2:-1]
f = open('ciphertext', 'w')
f.write(ctxt1+'\n')
f.write(ctxt2+'\n')
f.write(ctxt3+'\n')
f.close()

oneTimePad2.py

#!/usr/bin/env python
# coding=utf-8

from os import urandom

def process1(m, k):
    res = 0
    for i in bin(k)[2:]:
        res = res << 1;
        if (int(i)):
            res = res ^ m
        if (res >> 128):
            res = res ^ P
    return res

def process2(a, b):
    res = []
    res.append(process1(a[0], b[0]) ^ process1(a[1], b[2]))
    res.append(process1(a[0], b[1]) ^ process1(a[1], b[3]))
    res.append(process1(a[2], b[0]) ^ process1(a[3], b[2]))
    res.append(process1(a[2], b[1]) ^ process1(a[3], b[3]))
    return res

def nextrand(rand):
    global N, A, B
    tmp1 = [1, 0, 0, 1]
    tmp2 = [A, B, 0, 1]
    s = N
    N = process1(N, N)
    while s:
        if s % 2:
            tmp1 = process2(tmp2, tmp1)
        tmp2 = process2(tmp2, tmp2)
        s = s / 2
    return process1(rand, tmp1[0]) ^ tmp1[1]


def keygen():
    key = str2num(urandom(16))
    while True:
        yield key
        key = nextrand(key)

def encrypt(message):
    length = len(message)
    pad = '\x00' + urandom(15 - (length % 16))
    to_encrypt = message + pad
    res = ''
    generator = keygen()
    f = open('key.txt', 'w') # This is used to decrypt and of course you won't get it.
    for i, key in zip(range(0, length, 16), generator):
        f.write(hex(key)+'\n')
        res += num2str(str2num(to_encrypt[i:i+16]) ^ key)
    f.close()
    return res

def decrypt(ciphertxt):
    # TODO
    pass

def str2num(s):
    return int(s.encode('hex'), 16)

def num2str(n, block=16):
    s = hex(n)[2:].strip('L')
    s = '0' * ((32-len(s)) % 32) + s
    return s.decode('hex')

P = 0x100000000000000000000000000000087
A = 0xc6a5777f4dc639d7d1a50d6521e79bfd
B = 0x2e18716441db24baf79ff92393735345
N = str2num(urandom(16))
assert N != 0

if __name__ == '__main__':
    with open('top_secret') as f:
        top_secret = f.read().strip()
    assert len(top_secret) == 16
    plain = "One-Time Pad is used here. You won't know that the flag is flag{%s}." % top_secret

    with open('ciphertxt', 'w') as f:
        f.write(encrypt(plain).encode('hex')+'\n')