TJCTF 2018 : Bad Cipher

Challenge details

Event	Challenge	Category	Points	Solves
TJCTF 2018	Bad Cipher	Reverse Engineering	50	53

Description

My friend insisted on using his own cipher program to encrypt this flag, but I don’t think it’s very secure. Unfortunately, he is quite good at Code Golf, and it seems like he tried to make the program as short (and confusing!) as possible before he sent it.

I don’t know the key length, but I do know that the only thing in the plaintext is a flag. Can you break his cipher for me?

Encryption Program

Encrypted Flag

TL;DR

This challenge was an analyse of Python code, we must find the cryptographic protocol and find after the flag.

Files

The encrypted flag:

473c23192d4737025b3b2d34175f66421631250711461a7905342a3e365d08190215152f1f1e3d5c550c12521f55217e500a3714787b6554

It’s a hexa string.

The encryption program:

message = "[REDACTED]"
key = ""

r,o,u,x,h=range,ord,chr,"".join,hex
def e(m,k):
 l=len(k);s=[m[i::l]for i in r(l)]
 for i in r(l):
  a,e=0,""
  for c in s[i]:
   a=o(c)^o(k[i])^(a>>2)
   e+=u(a)
  s[i]=e
 return x(h((1<<8)+o(f))[3:]for f in x(x(y)for y in zip(*s)))

print(e(message,key))

The script seems to be obfuscated, let’s start to understand it.

Deobfuscation

First I changed the name of variables and after I modified the script:

def encrypt(message,key):
    lengthKey = len(key)
    s = [message[i::lengthKey]for i in range(lengthKey)]
    """
    If the key = "123" and message = "123456789"
    => len(key) = 3 so len(s) = 3
    s = ['147', '258', '369']
    Why "147" in first ? Take the fisrt character of the message and incremente by 3 (the key length)
    """

    for i in range(lengthKey): #To all letters of the key
        a = 0
        e = ""

        for c in s[i]: #To all character of s[i], group of letters
            a = ord(c)^ord(key[i])^(a>>2) #Xor : letter ^ key ^ (a without his last two bits)
            e += chr(a) # add the character to e

        s[i]=e # Replace the substring by the xor substring

    cipher = "".join("".join(y) for y in zip(*s)) # reset the string in the good order : s = ['147', '258', '369'] => "123456789"

    cipherHex = "".join(hex((1<<8)+ord(f))[3:]for f in cipher) # cipher.encode("hex")
    return cipherHex

print(encrypt(message,key))

Ok, the script is a simple XOR with:

• letter
• a key
• and original : a variable which depends on the previous XOR result (a)

The length of the cipher…

After some test, I saw that:
key = “123”
message= “123456789” => 000000050705070b0b
message= “1234567891” => 000000050705070b0b

What? The message are differents but they have the same out? How is it possible?

I investigated and the modification arrive after this line:

cipher = "".join("".join(y) for y in zip(*s))

When you run zip(), if the zipped iterables have different number of elements, zip takes the mimimum of value (Example 3 : https://www.programiz.com/python-programming/methods/built-in/zip).

I deduct: len(message) % len(key) = 0.

Here, the length is 112 / 2 = 56. The length of the key must be in [1,2,4,7,8,14,28,56].

The Decrypt Fonction

def decrypt(message,key):
    message = message.decode("hex")
    lengthKey = len(key)
    s=[message[i::lengthKey]for i in range(lengthKey)]

    for i in range(lengthKey):
        a=0
        b=0
        e=""
        for c in s[i]:
            a=ord(c)^ord(key[i])^(b>>2)
            b=ord(c)
            e+=chr(a)

        s[i]=e

    concat = "".join("".join(y) for y in zip(*s))
    return concat

But … what are the changes?

• Decode in first the hexa message
• I add a new variable : b to have the previous character without his two last bit

Simple ;)

Find the flag

The length

To find the flag, I must find the length of the key:
If the text is the flag, the begin is:

print decrypt(flag, "tjctf{")
>>> 3V@mK<Rg0I@^n58{GTzk"yx_M[V8}~kn~Cir^-6|a?s6R tSu

Take the first six character: 3V@mK<

import string

flag = "473c23192d4737025b3b2d34175f66421631250711461a7905342a3e365d08190215152f1f1e3d5c550c12521f55217e500a3714787b6554"

for i in [1,2,4,7,8,14,28,56]:
    if i < 7:
        key="3V@mK<"[:i]
    else:
        key="3V@mK<"+"a"*(i-6)

    tmp = decrypt(flag,key)
    print "***************************************"
    print key
    for i in range(0,len(tmp),len(key)):
        print tmp[i:i+len(key)]

With this output, I saw a very interesting part:

3V@mK<aa
tjctf{Vc
ybe_Wr
#
3ing_mb
3ncRypof
0N_MY5^;
f_W4SnO
v_sm4R
      *

The begin of each line seems a string of printable characters.
The length is 8!

Brute-force

import string

flag = "473c23192d4737025b3b2d34175f66421631250711461a7905342a3e365d08190215152f1f1e3d5c550c12521f55217e500a3714787b6554"

for i in range(128):
    c=chr(i)
    for j in range(128):
        o=chr(j)
        key="3V@mK<"+c+o

        tmp = decrypt(flag,key)
        if all(g in string.printable for g in tmp) and tmp[-1] == "}": # Check if the character are printable and if the end of the flag is "}"
            print "***************************************"
            print key
            print tmp

In the output:

***************************************
3V@mK<Z6
tjctf{m4ybe_Wr1t3ing_mY_3ncRypT10N_MY5elf_W4Snt_v_sm4R7}

Flag

tjctf{m4ybe_Wr1t3ing_mY_3ncRypT10N_MY5elf_W4Snt_v_sm4R7}

Iptior