[Dreamhack] amocafe

페이지에 접속하면 귀여운 고양이가 제일 좋아하는 메뉴가 "1_c_3_c_0__ff_3e" 라고 한다.

@app.route('/', methods=['GET', 'POST'])
def index():
    menu_str = ''
    org = FLAG[10:29]
    # 입력값(org)은 19자리이다.
    org = int(org)
    # 입력값(org)은 정수이다.
    st = ['' for i in range(16)]
    # 알고리즘 결과값인 16자리 문자열 '1_c_3_c_0__ff_3e'가 들어갈 함수 초기화 

    for i in range (0, 16):
        res = (org >> (4 * i)) & 0xf
        if 0 < res < 12:
            if ~res & 0xf == 0x4:
                st[16-i-1] = '_'
            else:
                st[16-i-1] = str(res)
        else:
            st[16-i-1] = format(res, 'x')
    menu_str = menu_str.join(st)

    # POST
    if request.method == "POST":
        input_str =  request.form.get("menu_input", "")
        if input_str == str(org):
            return render_template('index.html', menu=menu_str, flag=FLAG)
        return render_template('index.html', menu=menu_str, flag='try again...')
    # GET
    return render_template('index.html', menu=menu_str)

코드를 해석하고 문제를 이해하는데 굉장히 애를 먹었다.

이 문제를 간단히 요약하자면 코드 내에 포함되어 있는 알고리즘(for문)의 출력값이 "1_c_3_c_0__ff_3e" 인 입력값을 찾는 문제이다.

코드의 알고리즘을 역설계해서 입력값을 얻을 수도 있고 출력값이 길지 않기에 코드 없이도 알고리즘을 이해한다면 쉽게 입력값을 알아낼 수 있다.

 

그러려면 알고리즘을 확실히 이해해야한다.

res = (org >> (4 * i)) & 0xf

위 코드가 어떻게 동작하는지 보자.

우리가 입력한 정수(org)를  오른쪽으로 (4 * i)만큼 시프트 연산을 수행한 뒤 0xf를 AND연산한다.

 

예를 들어 우리가 입력한 정수가 '1000000000000000000' 이라고 가정해보자

(위 코드에 주석에서 설명했듯이 입력값은 19자리 정수이다)

 

오른쪽으로 시프트 연산을 수행하려면 입력한 정수를 아래와 같이 2진수로 바꿔야한다.

'110111100000101101101011001110100111011001000000000000000000'

 

여기서 i = 1이면, 4만큼 오른쪽으로 시프트 연산을 수행하면 오른쪽 끝 4자리가 사라지고 왼쪽 끝 4자리에 0이 들어온다.

'000011011110000010110110101100111010011101100100000000000000'   0000

 

그리고 16진수인 0xf를 2진수로 바꾸고 AND연산을 하면 아래와 같이 '0000'이 나온다.

   000011011110000010110110101100111010011101100100000000000000

x                                                                                                               1111

   000011011110000010110110101100111010011101100100000000000000

 

간단히 연산결과만 보자면 i=0일 때, res에는 입력한 값의 맨 끝 4자리 '0000'이 들어가고

'110111100000101101101011001110100111011001000000000000000000'

 

 i=1일 때, res에는 그 다음 4자리

'110111100000101101101011001110100111011001000000000000000000'

 

 i=2일 때는, res에는 그 다음 4자리가 들어가는 식이다.

'110111100000101101101011001110100111011001000000000000000000'

 

이렇게 16번 반복되는동안 오른쪽 끝부터 차례대로 4자리씩 res에 들어가고 res의 숫자에 따라 문자를 출력한다.

 1. 0 < res < 12 (res가 1이상 11이하일 경우)

   1-1) res = 11일때(~res & 0xf == 0x4, res를 NOT 시키고 0xf와 AND연산했을때 0x4인 경우, 즉 res가 11인 경우)

        문자열 '_'를 출력한다.

   1-2) res가 1이상 10이하일 경우

        정수를 문자형으로 출력한다.

 2. res가 12이상일 경우

        16진수 포맷으로 변환하여 출력한다.

 

이렇게 출력된 문자열이 '1_c_3_c_0__ff_3e' 이어야 한다.

알고리즘을 역설계할 필요없이 '1'은 '0001', '_'은 '1011', 'c'는 '1100' 이런식으로 쭉 써보면

'0001101111001011001110111100101100001011101111111111101100111110'가 나오고 이를 10진수로 변환하면

'1_c_3_c_0__ff_3e' 문자열을 얻을 수 있는 입력값 ' 2002760202557848382'를 알 수 있다.

 

def rev():
    menu_str="1_c_3_c_0__ff_3e"
    org = 0
    i = 15

    for c in menu_str:
        if (c == '_'):
            res = 11
            org = (res << (4 * i)) | org
        elif (c in ['c','d','e','f']):
            res = int(c, base=16)
            org = (res << (4 * i)) | org
        else:
            res = int(c)
            org = (res << (4 * i)) | org
        i -= 1
    return org
print(rev())

알고리즘을 완벽히 이해하고 나서야 역설계 코드를 직접 만들어볼 수 있었다.