Mar
20

## 0CTF 2017 Quals – OneTimePad 1 and 2

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

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

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.

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

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, b) ^ process1(a, b)) res.append(process1(a, b) ^ process1(a, b)) res.append(process1(a, b) ^ process1(a, b)) res.append(process1(a, b) ^ process1(a, b)) 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) ^ tmp1     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 p1 = vals 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 print "K", K print "N", N print encrypt(ct, keygen2(K))

The flag: flag{LCG1sN3ver5aFe!!}