Solution Script for stratum challenge from InterkosenCTF 2020

stratum_solve.py

# The main algo for encryption can be depicted as :
'''
==== flag.enc ====
636d 6668 6e66 676a 636c 676a 666d 6a68 ____        
2f3e 2670 6659 6e06 0902 6d24 250d 380e ----\-------------      
6e6d 6b73 6b6c 6d6b 6c66 6d68 6b76 7a6d _____\            \
3314 566d 2704 5234 442e 3e02 180c 153e ------\------------XORED
6468 6b6d 6868 666a 6876 6d66 7a62 676d ______/__SHUFFLED  /  
003f 6756 2337 2176 6071 0f74 4c4b 2161 -----/------------/     
736e 686b 6468 666b 7361 6e68 6278 6161 ____/            /
793e 3137 2f12 1514 494a 6534 527b 7665 -----------------        
====

SHUFFLED = pshufb( inp, 'asdfghjklzxcvbnm' )
XORED = (inp ^ (lzcnt|popcnt))
'''


def popcnt(n): 
  cnt = 0
  while (n): 
    cnt += n & 1
    n >>= 1
  return cnt 


def lzcnt(ax):
  bits = bin(ax)[2:].zfill(16)
  bits = [int(x) for x in bits]
  #print bits
  j = 0

  for i in range(16):
    if bits[i] == 0:
      j+=1
    else:
      break
  return j 


def shuffle(inp):
  seed = [ord(x) for x in "asdfghjklzxcvbnm"]
  shuffled = [0]*16

  for i in range(16):
    if (inp[i] < 0):
      shuffled[i] = 0
    else:
      shuffled[i] = seed[inp[i] % 16]

  return shuffled

def xor_elem(inp):
  xored = []
  
  for i in range(len(inp)):
    elem = inp[i]
    x = popcnt(elem) << 4
    y = lzcnt(elem << 8)

    j = (i+16) % len(inp)
    xored.append((x|y) ^ inp[j])

  return xored

# possible characters generator
def gen_possible_chars(possible_chars_dict,j):
  for a in possible_chars_dict[j]:
    for b in possible_chars_dict[16+j]:
      for c in possible_chars_dict[ (48+j) % 64 ]:
        yield a,b,c




'''
Flag format and the charset is disclosed by the author : 

if [[ "$FLAG" =~ ^KosenCTF\{[-a-zA-Z0-9_!?]+\}$ ]]; then
    echo $FLAG | ./chall > flag.enc
'''
import string
charset = string.ascii_letters + string.digits + "{_!?}" + "\n\x00"




if __name__ == '__main__':

  shuff_org, xor_org = '',''

  with open("flag.enc", "rb") as f:
    for i in range(4):
      shuff_org += f.read(0x10)
      xor_org += f.read(0x10)


  possible_chars_dict = {}

  for i in range(0x1,0x41):
    possible = []
    for d in charset:
      #dummy input
      inp = 'x'*64
      inp = [ord(x) for x in inp]
      inp[i-1] = ord(d)

      #dividing input into chunks of 16 elements for shuffling using pshufb
      chunks = [inp[x:x+16] for x in xrange(0, len(inp), 16)]
      gotshuffled = ''

      for tmparr in chunks:
        shuffled_res = shuffle(tmparr)
        gotshuffled += ''.join(map(chr,shuffled_res))

      if gotshuffled[i-1] ==  shuff_org[i-1]:
        possible.append(d)
    possible_chars_dict[i-1] = possible


  # remove false positives using flag format
  flg_fmt = "KosenCTF{"
  for i in range(len(flg_fmt)):
    possible_chars_dict[i] = [flg_fmt[i]]

  # minimized key space for bruteforcing using first algo ie. shuffling (pshufb)
  for item in possible_chars_dict:
    print "Possible for :",item, possible_chars_dict[item]

  filtered_chars_dict = {}

  for j in range(32):
    print "Find for :" , hex(ord(xor_org[j])), hex(ord(xor_org[(48+j) % 64]))
    for a,b,c in gen_possible_chars(possible_chars_dict, j):
      #dummy input
      inp = 'x'*64
      inp = [ord(x) for x in inp]

      #setting possible chars at appropriate indices
      inp[j] = ord(a)
      inp[16+j] = ord(b)
      inp[(48+j) % 64] = ord(c)

      #print "Trying : ",  a, b, c

      xored_res = xor_elem(inp)
      gotxored = ''.join(map(chr, xored_res))

      #print hex(ord(gotxored[j])), hex(ord(gotxored[(48+j) % 63]))

      if gotxored[j] == xor_org[j] and gotxored[(48+j) % 64] == xor_org[(48+j) % 64]:

        print "Candidate :", a,b,c

        # checking if a candidate already exists for an index
        if j in filtered_chars_dict and (16+j) in filtered_chars_dict and ((48+j) % 64) in filtered_chars_dict:
          filtered_chars_dict[j].append(a)
          filtered_chars_dict[16+j].append(b)
          filtered_chars_dict[(48+j) % 64].append(c)
        else:
          filtered_chars_dict[j] = [a]
          filtered_chars_dict[16+j] = [b]
          filtered_chars_dict[(48+j) % 64] = [c]

  # used second algo for further reducing key space (popcnt, lzcnt)
  for item in filtered_chars_dict:
    print "Possible (filtered) for : ", item, ":", filtered_chars_dict[item ]


  # some false positives still remain...

  from itertools import product

  for lol in product(*filtered_chars_dict.values()):
    flag = ''.join(lol)
    flag = flag.replace('\n\x00\x00','')
    print flag


  # but we can easily recognize our flag as :
  # Flag : KosenCTF{h4v3_fUn_w17h_7h3_ugly_bu7_u53ful_SIMD_1n57ruc710n5}