[Codegate 2016] compress

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 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76

import md5 import string, itertools   def encode(input_string):     h = md5.md5(input_string[:4]).hexdigest()     table = {         'a': 1,         'b': 2,         'c': 3,         'd': 4,         'e': 5,         'f': 6,         'g': 7,         'h': 8,         'i': 9,         'j': 0     }     out = ""     prev = ""     stage1 = []     stage2 = []     stage3 = ""     passbyte = -1     for ch in input_string:         if ch in table.keys():             stage1.append(table[ch])         else:             stage1.append(ch)       for index, ch in enumerate(stage1):         if len(stage1) <= index+1:             if index != passbyte:                 stage2.append(ch)             break           if passbyte != -1 and passbyte == index:             continue           if type(ch) == int and type(stage1[index+1])==int:             tmp = ch << 4             tmp |= stage1[index+1]             stage2.append(tmp)             passbyte = index+1         else:             stage2.append(ch)          for ch in stage2:         if type(ch) == int:             stage3 += chr(ch)         else:             stage3 += ch          for index, ch in enumerate(stage3):         if index >= len(h):             choice = 0         else:             choice = index           out += chr(ord(ch) ^ ord(h[choice]))       return out   def main() :     encoded = "~u/\x15mK\x11N`[^\x13E2JKj0K;3^D3\x18\x15g\xbc\\Gb\x14T\x19E"     assume_input_list = []       res = itertools.product(string.printable, repeat=4)     for tmp in res :         assume_input = ''.join(tmp)                  assume_out = encode(assume_input)         if assume_out[:3] == encoded[:3] :             assume_input_list.append(assume_input)             print assume_input   main() Colored by Color Scripter

cs

출력 가능한 문자 4개로 조합한 문자열 중에 encode된 값이 주어진 encoded와 3자리가 같으면 출력하는 프로그램이다.

3자리만 비교하는 이유는 stage1~stage2 때문이다.

4번째 문자가 table내에 존재하는 문자라 숫자로 변했을 경우에 5번째 문자가 존재하지 않아 문자로 변환되지 않는다.

이 경우에는 4번째 문자를 비교하지 못하기 때문에 3자리만 비교한다.

이 프로그램의 결과는 다음과 같다.

이제 이 값들을 decode하면 된다.

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 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65

import md5 import sys import string   table = {     1: 'a',     2: 'b',     3: 'c',     4: 'd',     5: 'e',     6: 'f',     7: 'g',     8: 'h',     9: 'i',     0: 'j' }   def decode(assume_out) :     global table       res = ''     for ch in assume_out :         if (string.printable.find(ch) == -1 or ch == '\t') and ch != ' ':             ch_ascii = ord(ch)             temp1 = ch_ascii & 0xF             temp2 = (ch_ascii >> 4) & 0xF                          if temp1 < 10 and temp2 < 10 :                 res += table[temp2]                 res += table[temp1]             else :                 res += ch         else :             res += ch       return res   def main(file_name) :     file = open(file_name, 'r')     assume_out_list = file.readlines()     file.close()       encoded = "~u/\x15mK\x11N`[^\x13E2JKj0K;3^D3\x18\x15g\xbc\\Gb\x14T\x19E"       for assume_out in assume_out_list :         h = md5.md5(assume_out[:4]).hexdigest()           i = 0         out = ''         for ch in encoded :             if i >= len(h):                 choice = 0             else:                 choice = i             i += 1               out += chr(ord(ch) ^ ord(h[choice]))           res = decode(out)           print assume_out + " : " + res   if len(sys.argv) > 1 :     main(sys.argv[1])   Colored by Color Scripter

cs

decode하는 방법을 나열하면 다음과 같다.

1. 입력된 문자열을 md5 인코딩한 값이랑 주어진 encoded 값을 xor 연산

2. xor 연산된 값 중 출력 불가능한 문자랑 \t인 문자를 stage1 ~ stage2 역연산

위 프로그램의 결과는 아래 사진과 같다.

Flag 문자열을 decode한 값이 정답으로 보인다.

중간중간에 들어가있는 j를 없애주면 flag가 된다.

FLag is {compress_is_always_helpful!}