CyBRICS Quals 2019: Zakukozh (Cyber)

This image containing flag is encrypted with affine cipher. Scrape it

zakukozh.bin

In this challenge, we are given a file with an extension of .bin. We start off by trying to identify it.

[email protected]:/vagrant/zakukozh$ file zakukozh.bin

zakukozh.bin: data

The file command tells us that it seems to be just binary data. Lets get an idea of what we’re working with by doing a hexdump.

[email protected]:/vagrant/zakukozh$ hexdump -C zakukozh.bin | head

00000000  60 09 eb 82 1c ef df ef  59 59 59 1c a0 91 55 27  |`.......YYY...U'|
00000010  59 59 77 bc 59 59 59 2e  d1 77 59 59 59 a9 44 38  |YYw.YYY..wYYY.D8|
00000020  31 59 59 59 68 16 27 82  37 59 8b 6b fd 00 59 59  |1YYYh.'.7Y.k..YY|
00000030  59 95 62 28 dc 28 59 59  b8 ba fe 1d 08 a4 59 59  |Y.b(.(YY......YY|
00000040  59 e0 e9 91 90 16 59 59  2b c6 59 59 2b c6 68 02  |Y.....YY+.YY+.h.|
00000050  da 31 35 59 59 fe 7e a0  55 28 45 61 db 3c 3d 10  |.15YY.~.U(Ea.<=.|
00000060  08 a6 a1 a3 a4 89 ab 3e  68 b0 1b 82 a6 35 fd cd  |.......>h....5..|
00000070  1c e0 d9 de 59 67 7f e3  45 70 b0 e2 e6 22 55 17  |....Yg..Ep..."U.|
00000080  32 d9 de 3e 87 1d d2 c2  59 51 e7 e6 59 49 a2 82  |2..>....YQ..YI..|
00000090  68 39 eb ab 77 19 7d fd  a4 d9 a1 b0 ef 59 f8 07  |h9..w.}......Y..|

Based on the challenge description, this file is the output of an image that has been encrypted with an affine cipher. An affine cipher is a monoalphabetic cipher (implies each input has a one-to-one mapping to its output) which has an encryption function of

where the modulus is the size of the alphabet, and and are the keys. Since we’re dealing with binary data, the size of our “alphabet” would be since each byte can have a value of to which means that . Additionally, and are chosen such that they are coprime, meaning that they have a gcd of .

Given that this is a monoalphabetic cipher, the decryption function is simply the inverse of . In simple terms, if , then . Therefore, we just need to derive the original mapping, i.e. figure out the values of and . Based on what what we mentioned earlier, and must be coprime. As for , since we are doing a modulus by , it implies that should be less than . Therefore, we can conclude that

Considering that this is a CTF, we’d like to solve this as fast as possible. Since finding the coprimes might be too much of a hassle, we can just assume that

This is reasonable since a search space of is still pretty small. The following script bruteforces the values of and .

def reffine(a, b, c):
    return chr((a * (ord(c) - b)) % 256)

with open('zakukozh.bin') as f:
	encrypted = f.read()

for i in range(256):
    for j in range(256):
        decrypted = ''.join([reffine(i, j, c) for c in encrypted])

        with open('output/dec_{}_{}.out'.format(i, j), 'wb') as f:
            f.write(decrypted)

Since the challenge description mentioned that it’s supposed to be an image, we can just filter our results based on that.

[email protected]:/vagrant/zakukozh/output$ file * | grep image

dec_136_107.out: BS image, Version 8352, Quantization 8200, (Decompresses to 61480 words)
dec_136_11.out:  BS image, Version 8352, Quantization 8200, (Decompresses to 61480 words)
dec_136_139.out: BS image, Version 8352, Quantization 8200, (Decompresses to 61480 words)
dec_136_171.out: BS image, Version 8352, Quantization 8200, (Decompresses to 61480 words)
dec_136_203.out: BS image, Version 8352, Quantization 8200, (Decompresses to 61480 words)
dec_136_235.out: BS image, Version 8352, Quantization 8200, (Decompresses to 61480 words)
dec_136_43.out:  BS image, Version 8352, Quantization 8200, (Decompresses to 61480 words)
dec_136_75.out:  BS image, Version 8352, Quantization 8200, (Decompresses to 61480 words)
dec_151_122.out: floppy image data (IBM SaveDskF)
dec_15_176.out:  Netpbm PAM image file
dec_162_184.out: PBF image (deflate compression)
dec_162_56.out:  PBF image (deflate compression)
dec_177_15.out:  SGI image data, 64992-D, 53472 x 10794, 11005 channels, "[\202F**?\277AfIV\262\014\035\316\261)g\362T\005Z\334\177\211QL\203gF\216^\375\201\252\037*\330p\224V\021Q\343\247#f\2103\252\037\177\370\256\323\303*\242X\247*\032\243\203\211\012\034\334\350\352\016\216\005\252\362Q\340*\031x\226*\010\306\002*\346\3019*\242\267\247*\032"
dec_177_177.out: JPEG image data
dec_194_199.out: JPEG 2000 image
dec_194_71.out:  JPEG 2000 image
dec_221_148.out: SVr3 curses screen image, little-endian
dec_234_123.out: RLE image data, 2152 x 60652, lower left corner: 26208, lower right corner: 2090, alpha channel, comment, 42 color channels, 28 color map channels
dec_234_251.out: RLE image data, 2152 x 60652, lower left corner: 26208, lower right corner: 2090, alpha channel, comment, 42 color channels, 28 color map channels
dec_239_89.out:  PNG image data, 621 x 219, 8-bit/color RGB, non-interlaced
dec_254_181.out: floppy image data (IBM SaveDskF, old)
dec_254_53.out:  floppy image data (IBM SaveDskF, old)
dec_35_213.out:  SVr3 curses screen image, big-endian

Looking through the results, we discover that dec_239_89.out is a PNG that contains the flag.

Flag: cybrics{W311_C0M3_2_CY13R1C5}