TJCTF 2018 — Bad Cipher (50 pts)

Challenge Information

+------------+------------+---------------------+--------+
|   Event    | Challenge  |      Category       | Points |
+------------+------------+---------------------+--------+
| TJCTF 2018 | Bad Cipher | Reverse Engineering |     50 |
+------------+------------+---------------------+--------+

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?

Challenge Detail

At the start , we can get two files.

An encryption programm.

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

An encryed flag.

473c23192d4737025b3b2d34175f66421631250711461a7905342a3e365d08190215152f1f1e3d5c550c12521f55217e500a3714787b6554

So I write a program to leak some plain text , and guess the length of the key.

message = "tjctf{"+"\x00"*49+"}"
key = "b"
ans = "473c23192d4737025b3b2d34175f66421631250711461a7905342a3e365d08190215152f1f1e3d5c550c12521f55217e500a3714787b6554"
encryped_flag = []
for i in range(56):
  temp =  ""
  temp = temp + ans[i*2]
  temp = temp +ans[i*2+1]
  temp = "0x" + temp
  temp = int(temp,16)
  encryped_flag.append(temp)
keylen = [1,2,4,7,8,14,28,56]
for i in keylen:
  print "keylength"+str(i)
  l=i;s=[encryped_flag[j::l]for j in r(l)]
  tempm=[message[j::l]for j in r(l)]
  tempkey=""
  if i != 1:
    for j in range(i-1):
      secret = s[j][0]
      plain  = tempm[j][0]
      if plain == "\x00":
        tempkey= tempkey+"?"
      else :
        tempkey=tempkey+chr(secret^ord(plain)^0)
      secret = s[l-1][len(s[0])-1]
      lastsecret = s[l-1][len(s[0])-2]
      plain  = tempm[l-1][len(s[0])-1]
      tempkey = tempkey + chr(secret^ord(plain)^(lastsecret>>2))
    else :
      for j in range(i):
        secret = s[j][0]
        plain  = tempm[j][0]
        if plain == "\x00":
          tempkey= tempkey+"?"
        else :
          tempkey=tempkey+chr(secret^ord(plain)^0)
    for j in range(l):
      a = 0
      plain = ""
      for c in s[j]:
        plain = plain + chr((a>>2) ^ ord(tempkey[j]) ^  c )
        a=c
      print "plain["+str(j)+"]:"+plain

After execution the script , We can guess the length of the key is 8 , because the output of other key length is weird.We can get the some output like this.

plain[0]:ty330fv
plain[1]:jbinN__
plain[2]:cenc_Ws
plain[3]:t_gRM4m
plain[4]:fW_yYS4
plain[5]:{rmp5nR
plain[6]:T<1R
plain[7]:4t_1l_}

Turn that output into a string just like

"tjctf{?4ybe_Wr?t3ing_m1_3ncRypR10N_MY5?lf_W4Sn?_v_sm4R?}"

and I still don’t know what “?” is , so I wrtie some script to brute force it.

l=8
message = "tjctf{?4ybe_Wr?t3ing_m1_3ncRypR10N_MY5?lf_W4Sn?_v_sm4R?}"
ans = "473c23192d4737025b3b2d34175f66421631250711461a7905342a3e365d08190215152f1f1e3d5c550c12521f55217e500a3714787b6554"
tempm   = [message[j::l]for j in r(l)]
tempkey = "3V@mK<?6"
s=[encryped_flag[j::8]for j in r(l)]
for i in range(32,256):
  key = tempkey[0:6]+chr(i)+tempkey[7]
  a=0
  plain = ""
  for j in s[6]:
    plain = plain + chr(ord(key[6])^j^(a>>2))
    a=j
  tempm[6] = plain
  gg = "".join("".join(y)for y in zip(*tempm))
  result=e(gg,key)
  noflag = 1
  for j in range(len(result)):
    if ord(result[j])<32 or ord(result[j])>256:
      noflag = 0
      break
  if noflag == 1:
    print "flag="+gg
    print "len(result):"+str(len(result))
    
    print "key ="+key
    print plain

And then , I get some string just like flag.

flag=tjctf{o4ybe_Wr3t3ing_m[_3ncRypV10N_MY5glf_W4Snv_v_sm4R5}
key =3V@mK<X6
flag=tjctf{n4ybe_Wr2t3ing_mZ_3ncRypW10N_MY5flf_W4Snw_v_sm4R4}
key =3V@mK<Y6
flag=tjctf{m4ybe_Wr1t3ing_mY_3ncRypT10N_MY5elf_W4Snt_v_sm4R7}
key =3V@mK<Z6
flag=tjctf{l4ybe_Wr0t3ing_mX_3ncRypU10N_MY5dlf_W4Snu_v_sm4R6}
key =3V@mK<[6

I guess the first word is “maybe” , so I choose “tjctf{m4ybe_Wr1t3ing_mY_3ncRypT10N_MY5elf_W4Snt_v_sm4R7}”.

解題過程

一開始會給兩個檔案，一個是加密用的程式(python)。

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

另一個是加密過後的flag。

473c23192d4737025b3b2d34175f66421631250711461a7905342a3e365d08190215152f1f1e3d5c550c12521f55217e500a3714787b6554

從程式碼可以看出目標大概就是flag跟key進行加密後會拿到加密過後的flag。並且跑跑看程式碼，可以發現flag的長度=加密過後的flag的長度(以hex的角度看待加密過後的flag)，所以flag長度是56個字元。

仔細閱讀程式碼後，可以知道加密方式是把明文拆成key長度個。ex:flag=”tjctf{“+”a”*49+”}”，key=”bbbbbbb”(長度為7)則會先把flag拆成

taaaaaaa
jaaaaaaa
caaaaaaa
taaaaaaa
faaaaaaa
{aaaaaaa
aaaaaaa}

所以可以知道key的長度一定是56的因數(1,2,4,7,8,14,28,56)，所以每一種key的長度都去嘗試，並解因為flag的格式一定會是”tjctf{“開頭，並且以”}”結尾，可以利用這點推算出大部分的明文，而無法推測的明文則用暴力猜。

寫一個簡單的python來猜測key長度。

message = "tjctf{"+"\x00"*49+"}"
key = "b"
ans = "473c23192d4737025b3b2d34175f66421631250711461a7905342a3e365d08190215152f1f1e3d5c550c12521f55217e500a3714787b6554"
encryped_flag = []
for i in range(56):
  temp =  ""
  temp = temp + ans[i*2]
  temp = temp +ans[i*2+1]
  temp = "0x" + temp
  temp = int(temp,16)
  encryped_flag.append(temp)
keylen = [1,2,4,7,8,14,28,56]
for i in keylen:
  print "keylength"+str(i)
  l=i;s=[encryped_flag[j::l]for j in r(l)]
  tempm=[message[j::l]for j in r(l)]
  tempkey=""
  if i != 1:
    for j in range(i-1):
      secret = s[j][0]
      plain  = tempm[j][0]
      if plain == "\x00":
        tempkey= tempkey+"?"
      else :
        tempkey=tempkey+chr(secret^ord(plain)^0)
    secret = s[l-1][len(s[0])-1]
    lastsecret = s[l-1][len(s[0])-2]
    plain  = tempm[l-1][len(s[0])-1]
    tempkey = tempkey + chr(secret^ord(plain)^(lastsecret>>2))
  else :
    for j in range(i):
      secret = s[j][0]
      plain  = tempm[j][0]
      if plain == "\x00":
        tempkey= tempkey+"?"
      else :
        tempkey=tempkey+chr(secret^ord(plain)^0)
      print "key:" + tempkey
  for j in range(l):
    a = 0
    plain = ""
    for c in s[j]:
      plain = plain + chr((a>>2) ^ ord(tempkey[j]) ^  c )
      a=c
    print "plain["+str(j)+"]:"+plain

跑完這個python後，可以發覺當key長度為8時，明文的樣子會比較沒有“不可視字元”，所以可以猜測出key的長度為8，此時的key為"3V@mK<?6"。

這是摺疊後的樣子，可以看到第七列大致上是錯誤的，所以key的第七個元素是錯的。

plain[0]:ty330fv
plain[1]:jbinN__
plain[2]:cenc_Ws
plain[3]:t_gRM4m
plain[4]:fW_yYS4
plain[5]:{rmp5nR
plain[6]:T<1R
plain[7]:4t_1l_}

還原成字串後，會是這樣 ，問號的部分是需要暴力猜測的部分。

"tjctf{?4ybe_Wr?t3ing_m1_3ncRypR10N_MY5?lf_W4Sn?_v_sm4R?}"

於是再寫一個script來暴力猜測這部分。

l=8
message = "tjctf{?4ybe_Wr?t3ing_m1_3ncRypR10N_MY5?lf_W4Sn?_v_sm4R?}"
ans = "473c23192d4737025b3b2d34175f66421631250711461a7905342a3e365d08190215152f1f1e3d5c550c12521f55217e500a3714787b6554"
tempm   = [message[j::l]for j in r(l)]
tempkey = "3V@mK<?6"
s=[encryped_flag[j::8]for j in r(l)]
for i in range(32,256):
  key = tempkey[0:6]+chr(i)+tempkey[7]
  a=0
  plain = ""
  for j in s[6]:
    plain = plain + chr(ord(key[6])^j^(a>>2))
    a=j
  tempm[6] = plain
  gg = "".join("".join(y)for y in zip(*tempm))
  result=e(gg,key)
  noflag = 1
  for j in range(len(result)):
    if ord(result[j])<32 or ord(result[j])>256:
      noflag = 0
      break
  if noflag == 1:
    print "flag="+gg
    print "len(result):"+str(len(result))
    print "key ="+key
    print plain

可以拿到許多很像flag的字串：

flag=tjctf{o4ybe_Wr3t3ing_m[_3ncRypV10N_MY5glf_W4Snv_v_sm4R5}
key =3V@mK<X6
flag=tjctf{n4ybe_Wr2t3ing_mZ_3ncRypW10N_MY5flf_W4Snw_v_sm4R4}
key =3V@mK<Y6
flag=tjctf{m4ybe_Wr1t3ing_mY_3ncRypT10N_MY5elf_W4Snt_v_sm4R7}
key =3V@mK<Z6

flag=tjctf{l4ybe_Wr0t3ing_mX_3ncRypU10N_MY5dlf_W4Snu_v_sm4R6}
key =3V@mK<[6

因為第一個單字很像maybe，所以就選用"tjctf{m4ybe_Wr1t3ing_mY_3ncRypT10N_MY5elf_W4Snt_v_sm4R7}"作為flag。

說不定會有更好的解法，因為有許多地方還是用猜測的。