0CTF 2017 Quals – OneTimePad 1 and 2

I swear that the safest cryptosystem is used to encrypt the secret!
oneTimePad.zip

Well, maybe the previous one is too simple. So I designed the ultimate one to protect the top secret!
oneTimePad2.zip

Summary: breaking a linear and an LCG-style exponential PRNGs.

In this challenges we need to break a PRNG. We are given a part of the keystream and we need to recover another part to decrypt the flag.

OneTimePad1

The code:

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()

The key observation here is that $process(m, k)$ is … just squaring of $m \oplus k$ in $GF(2^{256})$, with the irreducible polynomial given by $P$. To invert squaring, we can simply square $255$ times more:

c1 = 0xaf3fcc28377e7e983355096fd4f635856df82bbab61d2c50892d9ee5d913a07f
c2 = 0x630eb4dce274d29a16f86940f2f35253477665949170ed9e8c9e828794b5543c
c3 = 0xe913db07cbe4f433c7cdeaac549757d23651ebdccf69d7fbdfd5dc2829334d1b
 
k2 = c2 ^ str2num(fake_secret1)
k3 = c3 ^ str2num(fake_secret2)
 
kt = k3
for i in xrange(255):
    kt = process(kt, 0)
 
seed = kt ^ k2
print "SEED", seed
assert process(k2, seed) == k3
 
kt = k2
for i in xrange(255):
    kt = process(kt, 0)
 
k1 = kt ^ seed
print "K1", seed
assert process(k1, seed) == k2
 
m = k1 ^ c1
print `hex(m)[2:-1].decode("hex")`

The flag: flag{t0_B3_r4ndoM_en0Ugh_1s_nec3s5arY}

Another way to solve this is to see that process is linear (indeed, squaring in $GF(2^x)$ is linear) and can be inverted by linear algebra. More funny, a proper encoding of the problem for z3 yiels the result too, but only after ~1.5 hours on my laptop:

from z3.z3 import *
 
def proc(m, k):
    tmp = m ^ k
    res = 0
    for i in xrange(256):
        feedback = res >> 255
        res = res << 1
        mask = (tmp << i) >> 255
        res = res ^ (tmp & mask)
        res = res ^ (P & feedback)
    return res
 
# realk1 = k1
# realseed = seed
 
seed = BitVec("seed", 256)
k1 = BitVec("k1", 256)
 
s = Solver()
s.add(proc(k1, seed) == k2)
s.add(proc(k2, seed) == k3)
 
print "Solving..."
print s.check()
model = s.model()
k1 = int(model[k1].as_long())
print `hex(k1 ^ c1)[2:-1].decode("hex")`

OneTimePad 2

The code:

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')

This one is a bit trickier. Still, easy to spot – $process1(m, k)$ is a multiplication in $GF(2^{128})$. A closer look at $process2$ reveals that it is just a multiplication of two $2×2$ matricesn. What does $nextrand$ do? It implements a fast exponentiation. Let

$M = \begin{bmatrix}
A & B \\
1 & 0 \\
\end{bmatrix}$.

Then

$nextrand(rand) = M^N[0,0] \cdot rand + M^N[0,1]$,

and also $N$ is updated to $N^2$. What are the of values $M^N$ being used? Let’s look at powers of $M$ symbolically:

sage: R.<a,b> = GF(2**128, name='a')[]
sage: M = matrix(R, [[a, b], [0, 1]])
sage: M
[a b]
[0 1]
sage: M**2
[    a^2 a*b + b]
[      0       1]
sage: M**3
[            a^3 a^2*b + a*b + b]
[              0               1]
sage: M**4
[                    a^4 a^3*b + a^2*b + a*b + b]
[                      0                       1]

Hmm, the first entry is simply $A^N$ and the second entry is equal to

$B(A^{N-1} + A^{N-2} + \ldots + 1) = B(A^N-1)/(A-1)$.

Therefore, we have the following equations:

  1. $PRNG_1 = key$;
  2. $PRNG_2 = A^N \cdot PRNG_1 + B(A^N-1)/(A-1)$;
  3. $PRNG_3 = A^{N^2} \cdot PRNG_2 + B(A^{N^2}-1)/(A-1)$;
  4. and so on, the exponent is squared each time.

Here $N$ is unknown, but we can’t solve for it directly. Let’s solve for $A^N$ first and then solve a discrete logarithm problem.

Let’s multiply the second equation by $(A-1)$:

$PRNG_2 \cdot (A-1) = A^N \cdot PRNG_1 \cdot (A-1) + B(A^N-1),$

$\Leftrightarrow A^N = \frac{PRNG_2 \cdot (A-1) + B}{PRNG_1 \cdot (A – 1) + B}$.

Thus we can compute $A^N$. To get $N$ we need to compute discrete logarithm in $GF(2^{128})$. There are subexponential algorithms, so that the 128-bit size is quite practical. Indeed, sage can do it in a few minutes:

from sage.all import *
 
plain = "One-Time Pad is used here. You won't know that the flag is flag{"
ct = "0da8e9e84a99d24d0f788c716ef9e99cc447c3cf12c716206dee92b9ce591dc0722d42462918621120ece68ac64e493a41ea3a70dd7fe2b1d116ac48f08dbf2b26bd63834fa5b4cb75e3c60d496760921b91df5e5e631e8e9e50c9d80350249c".decode("hex")
 
vals = []
for i in xrange(0, 64, 16):
    vals.append(str2num(plain[i:i+16]) ^ str2num(ct[i:i+16]))
    print "KEY %02d" % i, hex(vals[-1])
 
p0 = vals[0]
p1 = vals[1]
uppp = process1(p1, A ^ 1) ^ B
down = process1(p0, A ^ 1) ^ B
down = pow1(down, 2**128-2)  # inversion
AN = process1(uppp, down)
print "A^N", AN
 
def ntopoly(npoly):
    return sum(c*X**e
        for e, c in enumerate(Integer(npoly).bits()))
 
X = GF(2).polynomial_ring().gen()
poly = ntopoly(P)
F = GF(2**128, modulus=poly, name='a')
a = F.fetch_int(A)
an = F.fetch_int(AN)
 
N = int(discrete_log(an, a))
# takes ~1 minute
# N = 76716889654539547639031458229653027958
assert a**N == an
 
def keygen2(key):
    while True:
        yield key
        key = nextrand(key)
 
K = vals[0]
print "K", K
print "N", N
print `encrypt(ct, keygen2(K))`

The flag: flag{LCG1sN3ver5aFe!!}

1 comment

    • y12uN on March 8, 2024 at 06:25
    • Reply

    What’s the definition of pow1 ?

    down = pow1(down, 2**128-2) # inversion

Leave a Reply

Your email address will not be published.