Breaking Bad (26 인코 ctf)

영어 문장들이 적혀있는 텍스트 파일( gale_notebook.txt ), 문제 설명에 적힌 프로그램 파일이 주어졌다.

프로그램 파일을 IDA 로 열어준다.

이러한 main() 함수가 있다.

문제 설명에서는 프로그램이 무언가를 검증하고
그 검증을 통과하는 정확한 입력값을 찾아야 한다고 했다. 그리고 텍스트 파일에 있는 시가 열쇠가 된다고 했다.

init_buffer(argc, argv, envp);
  if ( g_key_len > 0 )
  {
    printf("input: ");
    if ( fgets(s, 256, _bss_start) )
    {
      s[strcspn(s, "\r\n")] = 0;

g_key : 텍스트 파일에서 나온 암호화에 쓸 키
input 으로 사용자의 입력을 기다리고 strcspn() 으로 엔터키값 제거

if ( (unsigned int)strlen(s) == 54 )
      {
        if ( (unsigned int)check_input((__int64)s) )
          puts("You're Goddamn Right");
        else
          puts("Wrong answer. Better call Saul!");
        return 0;
      }
      else
      {
        puts("Wrong length. Better call Saul!");
        return 1;
      }

입력값이 정확히 54글자인지 확인
아닐경우 탈락
그리고 check_input() 함수를 거쳐서 입력값이 플래그와 일치하는지 확인

check_input() 함수를 보자

for ( i = 0; i <= 53; ++i )
  {
    if ( (unsigned __int8)enc_byte(*(_BYTE *)(i + a1), i) != target_0[i] )
      return 0;
  }
  return 1;
}

0번 인덱스~53번 인덱스까지 검사

a1(사용자가 키보드로 입력한 글자에서 '현재 처리중인 한 글자'를 의미) 에서 i번째 글자 한개 가져옴
enc_byte() 를 거침
enc_byte() 를 거친 결과가 target_0[i] 와 일치하는지 확인
일치하면 return 1 (참)
일치하지 않으면 return 0 (거짓)

 

enc_byte() 함수를 보자

{
  return (unsigned __int8)swap4((unsigned __int8)(a2 + g_key[a2 % g_key_len]) ^ a1);
}

a2 + g_key[a2 % g_key_len]

a2 = 현재 인덱스 번호를 알려주는 변

텍스트 파일에서 생성된 키 배열(g_key) 중 하나를 가져와 더함

(이때 인덱스가 키의 길이를 넘지 않도록 % 연산자를 사용함)

(위에서 합친 값) ^ a1

위에서 조합한 것과 사용자가 입력한 실제 글자(a1)를 XOR(^) 연산

swap4((위에서 합친 값) ^ a1)

swap4() 함수를 보자

{
  return (a1 >> 4) | (16 * (unsigned int)a1);
}

a1 >> 4 : 비트를 오른쪽으로 4칸 민다.

16 * a1 : 곱하기 16은 비트를 왼쪽으로 4칸 미는 것과 같음!!

| : OR(|) 연산을 통해 두 값을 하나로 합친다.

따라서 앞 4비트와 뒤 4비트를 swap 하게 된다.

 

target_0 값

사용자가 입력한 글자를 enc_byte() 로 암호화했을 때, 이 target_0에 적힌 숫자들과 똑같이 나와야 통과된다.

그렇다면 target_0 에 54바이트만큼 숫자가 있는 것이고 암호화된 결과물이라는 것이다.

그럼 해야할 것은 이 target_0 배열을 가지고 복호화를 해서 원본=플래그를 알아내는 것이다.

암호화 :

1. 텍스트 파일을 읽어 숫자 배열인 g_key를 만든다.
2. 위치 더하기: 입력한 글자의 인덱스(i)와 그에 해당하는 키 값(g_key[i])을 더한다.
3. XOR : 위에서 만든 값과 사용자가 입력한 글자를 XOR(^) 연산. 
4. 비트 위치 바꾸기 (swap4)

 

따라서 복호화는

1. target_0 배열에 들어있는 16진수 값 54개를 그대로 가져온다.
2. 비트 위치 되돌리기 (swap4) : target_0의 값들에 다시 한번 swap4를 실행해서 원래대로 돌아오게 한다.
3. XOR 되돌리기: 암호화 때 썼던 똑같은 키 값(index + key)을 가져와서 다시 XOR 해줘서 원래대로 돌아오게 한다.

4. 계산된 숫자(ASCII 코드)를 문자로 변환하여 합친다.

 

그렇다면

(내가 입력한 글자(내가 알아내야 하는 플래그)) ^ (g_key 관련 숫자) = target_0 인 것인데

g_key 가 뭘까??

처음엔 g_key 가 영어문자열인줄 알았지만 그러기엔 너무 길고,, 어떤 규칙이 있을까 찾아보다가 

여기 왼쪽 함수명에 extract_spaces 로 되어있는 것을 발견했다. 즉 공백을 기준으로 키 배열을 만드는 것이 맞지 않을까 생각했다. 또 공백의 개수가 54 바이트와 비슷했다,,

if ( v8 == 32 && (int)v7 < a3 ) : 32 = 공백(Space)의 ASCII 코드
*(_DWORD *)(a2 + 4LL * v4) = v6;  : 찾은 공백의 위치(v6)를 배열에 저장

 

따라서 복호화 과정을 파이썬 코드로 만들면 다음과 같다.

import os

# 1. swap4() 함수
def swap(byte_val):
    return ((byte_val >> 4) | (byte_val << 4)) & 0xFF
    # 문제 main 코드의 swap4() 함수랑 같음
    # 비트를 왼쪽으로 밀 때 8비트 범위를 넘을 수 있으므로 0xFF(=8비트)를 곱해서 크기고정

# 2. target_0 값
target_hex = (
    "d4c47474d4a59644348ff684976605271466e6e6e6f6778351"
    "f13100babc4475c3c36345f4745536336293d202334c1c328365a09083"
)
target_bytes = bytes.fromhex(target_hex)

# 3. 텍스트 파일 읽기, 줄바꿈 처리
file_path = "gale_notebook.txt"

with open(file_path, "rb") as f:
    raw_data = f.read()

# 줄바꿈을 CRLF(\r\n)로 통일하여 인덱스 계산(엔터 글자수를 통일해주지 않으면 글자가 밀림)
normalized = raw_data.replace(b"\r\n", b"\n").replace(b"\n", b"\r\n")

# 4. 공백(= 0x20) 위치 찾기, 키 생성
space_pos = [] # 위치 번호를 담을 빈 바구니
for i, b in enumerate(normalized): # 번호(i)와 글자(b)를 하나씩 확인
    if b == 0x20: # 만약 글자가 공백이라면
        space_pos.append(i) # 그 번호(i)를 넣는다
# enumerate() : 리스트에서 값을 하나씩 꺼낼 때 몇번째인지의 순서(i)와 그 위치값(pos)을 동시에 가져오는 함수 
g_key = [] # 결과를 담을 빈 바구니
for i, pos in enumerate(space_pos): # 순서(i)와 위치(pos)를 하나씩 꺼내서
    temp = pos ^ (7 * i) # XOR 계산을 하고
    key_value = temp & 0xFF # 1바이트 크기로 자른다.
    g_key.append(key_value) 

# 5. 복호화
flag = ""
for i in range(len(target_bytes)):
    # swap => XOR(key + index)
    val = swap(target_bytes[i])
    key_val = g_key[i % len(g_key)]
    plain_char = val ^ ((key_val + i) & 0xFF)
    flag += chr(plain_char)

print("flag:", flag)

이때 위 코드에서

temp = pos ^ (7 * i)

이렇게 순서 * 7을 해주지 않으면 안된다.

이것에 관해서는 extract_spaces() 함수 바로 다음에 실행되는 init_buffer() 안에서 찾을 수 있다.

g_key[i] = v3[4 * i] ^ (7 * i);

v3[4 * i] = extract_spaces 함수가 텍스트파일에서 찾은 공백의 인덱스

^ (7 * i) : 순서 * 7, XOR연산

g_key[i] : 암호 키

따라서 플래그는 INCOGNITO{your_answer_is_99.1_percent_pure_perfection} 이다.

(문제를 맞춘 학회원에게 이 플래그가 맞는지 확인받음.)