[Codegate 2016] reversing : compress

compress

이번 문제는 그냥 암호화된 문자열하고 인코드 하는 파이썬 코드를 던져줬네요

import md5
 
def encode(input_string):
    print "Input : %s" % 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(ch ^ h[choice])
    return repr(out)
 
encoded = "~u/\x15mK\x11N`[^\x13E2JKj0K;3^D3\x18\x15g\xbc\\Gb\x14T\x19E"
encode(st)

먼저 간략하게 이 코드가 뭘 하는지 적어보자면

1. 문자열을 입력받는다.

2. 문자열 앞 4글자의 md5 해쉬값을 h 에 저장함.

3. Stage 1 에선 위에 table 을 가지고 치환 작업을 한다. 그리고 그 치환한 문자들을 stage1 에 저장. ex ) asdf 면 1s46 으로

4. Stage 2 에선 stage1 에 저장된 문자열 중 숫자가 연속으로 이어져 있는 것을 16진수 를 사용해 하나로 합친다. 

   그리고 stege2 에 저장한다. ex) asdf -> 1s46 -> 1 s 70    // 46 은 0x46 -> 70

5. Stage 3 에선 stage2 에 있는 int 형 값들을 chr 를 통해서 문자로 바꾼다.

6. 그리고 위에 구해놨던, h 에 저장했던 값과 1대1 로 xor 을 진행한다.

7. 끗!

매우 간단한 암호화 과정이지만 하나 걸리는 점은 md5 해쉬한 값하고 진행한다는 점

하지만 다행이 문제가 안되는게 4자리 문자의 해쉬 값이다. 게다가 추측을 하자면 숫자는 정답에 들어갈 수 없으므로

즉 해봤자 대문자, 소문자로 이뤄진 4자리 문자다.

% ( table 에서 숫자로 치환을 하는 과정이 있어서 만약 답에 숫자가 들어가면 문제가 생길 수 있으니까 ㅇㅇ )

이 부분은 brute-force 로 돌려 보다보면 알 수 있다. 대략적인 코드는 다음과 같다. 

from md5 import *
def encode(input_string):
   ...skip...
 
charset = [a-z,A-Z]
 
for a in charset:
   for b in charset:
      for c in charset:
         for d in charset:
            tmp = a
            tmp += b
            tmp += c
            tmp += d
            enc = encode(tmp)
            if enc == "~u/" or enc == "~u/\x15":
               print tmp
encode(st)

대략적으로 이런 코드를 돌리면 구할 수 있다. ( ~u/\x15 는 주어진 encoded 앞자리 4 개 데이터다 )

그럼 'FLag' 란 문자가 나올 거다.

그럼 역연산을 위해 먼저 'FLag' 의 md5 값과 encoded 데이터를 xor 해 보자.

from md5 import *
def decode(key, encoded):
    decoded = ""
    print "Encoded : %s" % encoded
    
    h = md5(key).hexdigest()
    for idx, ch in enumerate(encoded):
        if idx >= len(h):
            choice = 0
        else:
            choice = idx
        decoded += chr(ord(ch)^ord(h[choice]))
    print "Decoded : %s" % repr(decoded)
               
encoded = "~u/\x15mK\x11N`[^\x13E2JKj0K;3^D3\x18\x15g\xbc\\Gb\x14T\x19E"
decode("FLag", encoded)

그럼 아래같은 결과가 나온다.

Encoded : ~u/mKN`[^E2JKj0K;3^D3gﾼ\GbTE
Decoded : 'FL\x17 \ts {\x03ompr\x05ss_\ts_\x01lw\x01ys_\x85lp\x06ul!}'

뭐 완벽히 복원해 주는 코드를 짜도 되긴 하는데 저 정도면 그냥 나온 결과만 보고 바로 답을 맞춰 볼 수 있을거 같다.

\x17 -> ag \x03 -> c \x05 -> e 
\x01 -> a \x85 -> he \x06 -> f

FLag is {compress_is_always_helpful!}