I swear that the safest cryptosystem is used to encrypt the secret!
oneTimePad.zipWell, 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:
- $PRNG_1 = key$;
- $PRNG_2 = A^N \cdot PRNG_1 + B(A^N-1)/(A-1)$;
- $PRNG_3 = A^{N^2} \cdot PRNG_2 + B(A^{N^2}-1)/(A-1)$;
- 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
What’s the definition of pow1 ?
down = pow1(down, 2**128-2) # inversion