defund made a simple OFB cipher, if you can even call it that. Here’s the source and the encrypted flag.

Let’s look at the encryption script first.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 |
import struct def lcg(m, a, c, x): return (a*x + c) % m m = pow(2, 32) with open('lcg') as f: a = int(f.readline()) c = int(f.readline()) x = int(f.readline()) d = open('flag.png').read() d += '\x00' * (-len(d) % 4) d = [d[i:i+4] for i in range(0, len(d), 4)] e = '' for i in range(len(d)): e += struct.pack('>I', x ^ struct.unpack('>I', d[i])[0]) x = lcg(m, a, c, x) with open('flag.png.enc', 'w') as f: f.write(e) f.close() |

First, it reads the flag.png and if the total number of bytes are not divisible by 4, it appends null bytes at the end of it to make it divisible by 4.

Next, it divides the byte array to the 4-byte blocks. Then, it iterates over each block, converts them to unsigned integers, xors them with random numbers that are generated by Linear Congruential Generator (LCG), and packs the result as a big-endian .

In order to crack the LCG algorithm, we need to find 2 equations since we have 2 unknowns. We know the original file is png and every png starts with the following 16 bytes:

1 |
89 50 4E 47 0D 0A 1A 0A 00 00 00 0D 49 48 44 52 |

So, we already know the first 4 blocks of the original file. If we convert these 4 blocks to 4 integers and xor them with the encrypted ones, we will retrieve the first 4 random number that are generated by the LCG. Actually, first value of x is the seed of the LCG and the rest are generated by the LCG.

Now, we know x0, x1, x2, x3 values. We also know that x[n + 1] = (a * x[n] + c) % m.

Let’s write down two equations.

x[1] = a * x[0] + c (mod m)

x[2] = a * x[1] + c (mod m)

We can solve these equations for *a*.

a = (x[2] – x[1]) / (x[1] – x[0]) (mod m)

Note that we need to use modular inverse since the formula includes modular division.

After we find *a*, we can calculate *c* by using one of the equations above.

Finally, we will generate the same numbers the encryption function did and we will xor the encrypted file’s blocks with the same values. It is because k^k=0 and p^0=p. It means that if you xor a number with the same value twice, it will stay the same, i.e. k^p^p=k^0=k.

Here is the decryption script.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 |
import struct import gmpy def find_c(states, m, a): c = (states[1] - a * states[0]) % m return c def find_a(states, m): a = (states[2] - states[1]) * gmpy.invert(states[1] - states[0], m) % m return a def lcg(m, a, c, x): return (a*x + c) % m m = pow(2, 32) d = open('flag.png.enc').read() d = [d[i:i+4] for i in range(0, len(d), 4)] p = '' x0 = 0x89504e47 ^ struct.unpack('>I', d[0])[0] x1 = 0x0d0a1a0a ^ struct.unpack('>I', d[1])[0] x2 = 0x0000000d ^ struct.unpack('>I', d[2])[0] x3 = 0x49484452 ^ struct.unpack('>I', d[3])[0] states = [x0, x1, x2, x3] x = x0 a = find_a(states, m) c = find_c(states, m, a) for i in xrange(len(d)): p += struct.pack('>I', x ^ struct.unpack('>I', d[i])[0]) x = lcg(m, a, c, x) with open('flag.png', 'w') as f: f.write(p) f.close() |

After running the script, we got the following image: