드림핵 S6R12 div2

goldenGlow_21·2024년 11월 30일

CTF dreamhack

CTF 기록

목록 보기

4/4

AFSR

LFSR: Linear Feedback Shift Register

"AFSR"의 작동 방식과 관련 데이터를 역으로 추적하여 FLAG를 복구하는 것이 목표?

분석 단계

AFSR.py

AFSR 클래스는 특정 상태(state)와 기반 값(base)을 사용해 난수를 생성. 주요 메소드는:

shift: 상태를 좌측으로 쉬프트하고, 기반 값(base)을 기준으로 상태를 조정하며 출력 비트를 생성
getNbits(num): num만큼의 비트를 생성

prob.py

FLAG를 숫자로 변환한 값을 AFSR의 base로 설정
AFSR.getNbytes(200)을 호출해 난수를 생성하고, 결과를 출력

output.txt

AFSR.getNbytes(200)으로 생성된 200 바이트의 데이터
이를 통해 FLAG 값을 유추해야 한다...

풀이 방향

AFSR의 동작 역추적:
- output.txt를 활용해 FLAG(base)를 찾는 역공격을 수행.
- AFSR.shift()는 base와 state를 기반으로 동작하기 때문에, 생성된 난수를 분석하면 base를 도출할 수 있다
FLAG 복구:
- base 값을 찾으면 FLAG는 숫자로 변환된 상태이므로, 이를 long_to_bytes로 다시 변환하면 원래 플래그를 복구할 수 있다

코드 구현

output.txt의 데이터를 이용해 base를 추정한 뒤 FLAG를 복구

from Crypto.Util.number import long_to_bytes

class AFSR:
    def __init__(self, base):
        self.state = 1
        self.base = base
    
    def shift(self):
        self.state <<= 1
        output = 0
        if self.state >= self.base:
            self.state -= self.base
            output = 1
        return str(output)
    
    def getNbits(self, num):
        output = ''
        for _ in range(num):
            output += self.shift()
        return output
    
    def getNbytes(self, num):
        output = b''
        for _ in range(num):
            o = self.getNbits(8)
            o = int(o, 2)
            output += bytes([o])
        return output

# output.txt에서 읽은 값 (16진수 문자열)
leaked_hex = "0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000003bfc4bf526d43ebf96ff37cd060ee98c64cc5d97abf89c4e668378ccfc9484a00fda30c8d455c3c2c8c6141272fc8ffb2c5c0c1ac6fb51dc15650ac621e8e978b928957a3f6b36c5312b76d7394e3f34248a5b828ce634d19a4e07ac27ba57ead12b18dff1f1851f266827f5b051f6533c2ed55a0dce683e3b840d0a82b07776dbfd50ab7"
leaked_bytes = bytes.fromhex(leaked_hex)

# Base 추정 및 플래그 복구
for base_candidate in range(1, 2**32):  # base의 범위 추정 필요
    afsr = AFSR(base_candidate)
    generated = afsr.getNbytes(200)
    if generated == leaked_bytes:
        print("Base Found:", base_candidate)
        flag = long_to_bytes(base_candidate)
        print("FLAG:", flag)
        break

엄청 오래 걸린다... 얼마 전 SECCON의 악몽이 여기에서도...

특이점 분석

shift()의 동작 특징:
- self.state <<= 1: 상태를 좌측으로 1비트 이동.
- self.state >= self.base: state가 base 이상이면, state -= base를 수행하고 출력 비트는 1.
- 그렇지 않으면 출력 비트는 0.
이 구조는 state가 base보다 작아질 때까지 반복적으로 base를 뺀다는 점에서 특정 패턴이 발생할 가능성이 있다

state의 초기값:
- 초기 상태는 항상 1이므로, base 값에 따라 state의 변동 패턴이 달라진다
출력 패턴 분석:
- 출력 비트는 base에 따라 결정되므로, 생성된 비트열에서 특정한 패턴이 나타날 가능성이 높다.
- 난수처럼 보이지만, 실제로는 base의 특성(예: 크기, 비트 길이)에 따라 출력 비트의 분포가 달라질 수 있다.

방향 변경

초기 출력 확인
- output.txt의 초반 부분이 모두 0으로 채워져 있다.
- 이는 초기 상태에서 base 값이 매우 크다는 것을 암시
- 초기 state는 1이므로, state가 base보다 커질 때까지 출력 비트는 0
base의 비트 길이 추정
- 출력 비트가 1이 되기 전에 몇 번의 shift()가 수행되었는지 확인하면, base의 비트 길이를 유추할 수 있다

from Crypto.Util.number import long_to_bytes

class AFSR:
    def __init__(self, base):
        self.state = 1
        self.base = base
    
    def shift(self):
        self.state <<= 1
        output = 0
        if self.state >= self.base:
            self.state -= self.base
            output = 1
        return str(output)
    
    def getNbits(self, num):
        output = ''
        for _ in range(num):
            output += self.shift()
        return output
    
    def getNbytes(self, num):
        output = b''
        for _ in range(num):
            o = self.getNbits(8)
            o = int(o, 2)
            output += bytes([o])
        return output

# output.txt에서 읽은 값 (16진수 문자열)
leaked_hex = "0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000003bfc4bf526d43ebf96ff37cd060ee98c64cc5d97abf89c4e668378ccfc9484a00fda30c8d455c3c2c8c6141272fc8ffb2c5c0c1ac6fb51dc15650ac621e8e978b928957a3f6b36c5312b76d7394e3f34248a5b828ce634d19a4e07ac27ba57ead12b18dff1f1851f266827f5b051f6533c2ed55a0dce683e3b840d0a82b07776dbfd50ab7"
leaked_bytes = bytes.fromhex(leaked_hex)

# 1. 초기 출력의 연속된 0의 개수 확인
initial_zeros = 0
for byte in leaked_bytes:
    if byte == 0:
        initial_zeros += 8  # 1 byte는 8비트
    else:
        # 마지막 0이 아닌 비트를 포함한 패턴 분석
        bits = bin(byte)[2:].zfill(8)  # 8비트로 표현
        initial_zeros += bits.index('1')
        break

print(f"초기 0의 개수: {initial_zeros}")

# 2. base의 범위 추정
# state가 1에서 시작하므로, 2^(initial_zeros-1) <= base < 2^(initial_zeros)
base_min = 2 ** (initial_zeros - 1)
base_max = 2 ** initial_zeros
print(f"base 범위: {base_min} ~ {base_max}")

# 3. base 추정 및 플래그 복구
for base_candidate in range(base_min, base_max):
    afsr = AFSR(base_candidate)
    generated = afsr.getNbytes(200)
    if generated == leaked_bytes:
        print("Base Found:", base_candidate)
        flag = long_to_bytes(base_candidate)
        print("FLAG:", flag.decode())
        break

noah@DESKTOP-GI79V9I  ~/ctf/DH_S6R12/AFSR   master  /home/noah/.pyenv/ver
sions/3.8.13/bin/python /home/noah/ctf/DH_S6R12/AFSR/solve.py
초기 0의 개수: 542
base 범위: 7198262071269114212496861612297570974191515389283066612961208916178940129074380592510465097766225371439873457013633432197133225688790879502413624289384262168215552 ~ 14396524142538228424993723224595141948383030778566133225922417832357880258148761185020930195532450742879746914027266864394266451377581759004827248578768524336431104

이거 맞나...?

분석... 다시

AFSR의 핵심 동작

state는 초기값이 1이며, 매번 왼쪽으로 쉬프트(<<= 1)
state >= base일 때만 state -= base가 실행되고 출력 비트가 1
따라서 출력 비트는 base에 따라 결정

즉, AFSR은 base를 이용해 특정 패턴의 비트열을 생성하는 단순한 결정론적 알고리즘

출력 데이터 분석

output.txt의 초반에는 대부분 0으로 채워져 있음
- 이는 초기 state(1)가 base보다 작기 때문에 발생하며, base의 크기가 상당히 크다는 것을 암시
이후 출력에서 1이 발생하기 시작
- state가 base 이상으로 커지는 순간을 의미
따라서 초기 0의 개수를 기반으로 base의 비트 길이를 추정할 수 있음

many-shuffle

shuffle shuffle shuffle

noah@DESKTOP-GI79V9I  ~/ctf/DH_S6R12/many-shuffle   master file many-shuffle
many-shuffle: ELF 64-bit LSB pie executable, x86-64, version 1 (SYSV), dynamically linked, interpreter /lib64/ld-linux-x86-64.so.2, BuildID[sha1]=8e261a0fff21890df80c145ef4e840b6137acf85, for GNU/Linux 3.2.0, stripped
 noah@DESKTOP-GI79V9I  ~/ctf/DH_S6R12/many-shuffle   master  file flag
flag: ASCII text, with no line terminators

사전 분석

many-shuffle
- ELF 64비트 실행 파일로, x86-64 아키텍처용
- 파일이 stripped 상태이므로, 심볼 테이블이 제거되어 디버깅이 어려움
flag
- ASCII 텍스트 파일
- 이 파일이 정답 플래그일 가능성이 높으나, 직접적으로 읽을 수 없는 방식으로 보호되었을 가능성?

풀이 방향

1. `many-shuffle` 실행 파일의 동작 분석

many-shuffle 실행 파일이 어떤 방식으로 flag 파일을 처리하는지 확인해야 함
기본적인 동작을 확인하기 위해 파일을 실행
실행 과정에서 추가 입력이나 환경 설정이 필요한지 확인

2. 실행 파일의 동작 원리 추출

strace, ltrace 등을 사용해 시스템 호출 및 라이브러리 호출을 추적
실행 중 flag 파일에 접근하거나 데이터를 처리하는 방식이 확인되면, 이를 분석

3. 리버스 엔지니어링

many-shuffle 실행 파일의 내부 동작을 분석
IDA, Ghidra, 또는 Radare2를 사용해 바이너리 코드를 디스어셈블링하여 데이터 처리 로직을 확인

4. `flag` 복구

many-shuffle이 flag 데이터를 섞거나 암호화했다면, 복구 알고리즘을 구현

동적 분석 및 풀이 시도

noah@DESKTOP-GI79V9I  ~/ctf/DH_S6R12/many-shuffle   master  ./many-shuffle
Random String Generated! Now Shuffle...
Shuffled String: LLTDTNSFVSPNMTTM
Original String?:

main 함수 디컴파일

__int64 __fastcall main(__int64 a1, char **a2, char **a3)
{
  unsigned int v3; // eax
  size_t v4; // rax
  int i; // [rsp+1Ch] [rbp-A4h]
  int j; // [rsp+20h] [rbp-A0h]
  int k; // [rsp+24h] [rbp-9Ch]
  char *lineptr; // [rsp+28h] [rbp-98h] BYREF
  size_t n; // [rsp+30h] [rbp-90h] BYREF
  FILE *stream; // [rsp+38h] [rbp-88h]
  char s[64]; // [rsp+40h] [rbp-80h] BYREF
  char dest[32]; // [rsp+80h] [rbp-40h] BYREF
  char s2[24]; // [rsp+A0h] [rbp-20h] BYREF
  unsigned __int64 v15; // [rsp+B8h] [rbp-8h]

  v15 = __readfsqword(0x28u);
  sub_1664(a1, a2, a3);
  v3 = time(0LL);
  srand(v3);
  for ( i = 0; i <= 15; ++i )
    s[i] = rand() % 26 + 65;
  s[16] = 0;
  puts("Random String Generated! Now Shuffle...");
  v4 = strlen(s);
  strncpy(dest, s, v4);
  for ( j = 0; j <= 15; ++j )
  {
    for ( k = 0; k <= 15; ++k )
    {
      if ( (j & 1) != 0 )
        dest[byte_4020[16 * j + k]] = s[k + 32];
      else
        s[byte_4020[16 * j + k] + 32] = dest[k];
    }
  }
  printf("Shuffled String: %s\n", dest);
  printf("Original String?: ");
  fgets(s2, 18, stdin);
  s2[strcspn(s2, "\n")] = 0;
  if ( !strcmp(s, s2) )
  {
    lineptr = 0LL;
    n = 0LL;
    stream = fopen("./flag", "r");
    getline(&lineptr, &n, stream);
    printf("Match! Here's your flag: %s", lineptr);
    free(lineptr);
    fclose(stream);
  }
  else
  {
    puts("Wrong...");
  }
  return 0LL;
}

문자열은 16자리의 임의의 알파벳 배열

# byte_4020 배열 값 (256개 값, 16x16 매트릭스)

byte_4020 = [
    0x0B, 0x08, 0x03, 0x04, 0x01, 0x00, 0x0E, 0x0D, 0x0F, 0x09, 0x0C, 0x06, 0x02, 0x05, 0x07, 0x0A,
    0x0F, 0x04, 0x08, 0x0B, 0x06, 0x07, 0x0D, 0x02, 0x0C, 0x03, 0x05, 0x0E, 0x0A, 0x00, 0x01, 0x09,
    0x04, 0x0C, 0x0E, 0x05, 0x0D, 0x06, 0x09, 0x0A, 0x01, 0x00, 0x0B, 0x0F, 0x02, 0x07, 0x03, 0x08,
    0x0F, 0x03, 0x04, 0x06, 0x00, 0x0B, 0x01, 0x0D, 0x09, 0x07, 0x05, 0x02, 0x0C, 0x0E, 0x08, 0x0A,
    0x0E, 0x03, 0x0C, 0x0D, 0x00, 0x05, 0x04, 0x08, 0x07, 0x09, 0x04, 0x0B, 0x05, 0x06, 0x0F, 0x08,
    0x00, 0x03, 0x01, 0x0A, 0x0D, 0x02, 0x0E, 0x0C, 0x07, 0x0A, 0x0E, 0x09, 0x07, 0x08, 0x0D, 0x03,
    0x0B, 0x0C, 0x0F, 0x02, 0x00, 0x04, 0x05, 0x06, 0x01, 0x05, 0x04, 0x0D, 0x01, 0x00, 0x02, 0x09,
    0x0B, 0x0C, 0x07, 0x08, 0x0A, 0x06, 0x0E, 0x0F, 0x03, 0x04, 0x08, 0x05, 0x02, 0x0A, 0x0F, 0x0B,
    0x07, 0x00, 0x01, 0x0C, 0x03, 0x0E, 0x06, 0x09, 0x0D, 0x0D, 0x0E, 0x0F, 0x0B, 0x00, 0x02, 0x0A,
    0x04, 0x07, 0x06, 0x09, 0x01, 0x05, 0x03, 0x08, 0x0C, 0x0E, 0x02, 0x03, 0x05, 0x0A, 0x01, 0x07,
    0x00, 0x09, 0x0D, 0x0C, 0x0B, 0x04, 0x06, 0x0F, 0x08, 0x03, 0x0B, 0x0E, 0x0A, 0x06, 0x04, 0x07,
    0x01, 0x02, 0x0D, 0x0F, 0x00, 0x0C, 0x09, 0x05, 0x08, 0x0D, 0x0F, 0x01, 0x02, 0x0C, 0x0A, 0x03,
    0x07, 0x09, 0x06, 0x08, 0x05, 0x00, 0x04, 0x0B, 0x0E, 0x00, 0x0E, 0x04, 0x0D, 0x06, 0x01, 0x0A,
    0x05, 0x03, 0x0C, 0x07, 0x0B, 0x0F, 0x02, 0x08, 0x09, 0x0B, 0x02, 0x08, 0x07, 0x05, 0x03, 0x09,
    0x0D, 0x04, 0x0F, 0x00, 0x01, 0x06, 0x0C, 0x0E, 0x0A, 0x0B, 0x01, 0x08, 0x00, 0x0C, 0x0D, 0x04,
    0x0E, 0x0A, 0x06, 0x0F, 0x07, 0x09, 0x05, 0x03, 0x02
]

Shuffle 알고리즘 분석

for ( j = 0; j <= 15; ++j )
{
    for ( k = 0; k <= 15; ++k )
    {
        if ( (j & 1) != 0 )
            dest[byte_4020[16 * j + k]] = s[k + 32];
        else
            s[byte_4020[16 * j + k] + 32] = dest[k];
    }
}

p-rho

noah@DESKTOP-GI79V9I  ~/ctf/DH_S6R12/p-rho/deploy   master  checksec ./prob
[*] '/home/noah/ctf/DH_S6R12/p-rho/deploy/prob'
    Arch:       amd64-64-little
    RELRO:      Partial RELRO
    Stack:      Canary found
    NX:         NX enabled
    PIE:        No PIE (0x400000)
    SHSTK:      Enabled
    IBT:        Enabled
    Stripped:   No

goldenGlow_21

안드로이드는 리눅스의 꿈을 꾸는가

이전 포스트

드림핵 S6R12 div2

CTF 기록

AFSR

분석 단계

AFSR.py

prob.py

output.txt

풀이 방향

코드 구현

특이점 분석

방향 변경

분석... 다시

AFSR의 핵심 동작

출력 데이터 분석

many-shuffle

사전 분석

풀이 방향

1. `many-shuffle` 실행 파일의 동작 분석

2. 실행 파일의 동작 원리 추출

3. 리버스 엔지니어링

4. `flag` 복구

동적 분석 및 풀이 시도

Shuffle 알고리즘 분석

p-rho

SECCON CTF 13 QUALS

0개의 댓글

관련 채용 정보

드림핵 S6R12 div2

CTF 기록

AFSR

분석 단계

AFSR.py

prob.py

output.txt

풀이 방향

코드 구현

특이점 분석

방향 변경

분석... 다시

AFSR의 핵심 동작

출력 데이터 분석

many-shuffle

사전 분석

풀이 방향

1. many-shuffle 실행 파일의 동작 분석

2. 실행 파일의 동작 원리 추출

3. 리버스 엔지니어링

4. flag 복구

동적 분석 및 풀이 시도

Shuffle 알고리즘 분석

p-rho

SECCON CTF 13 QUALS

0개의 댓글

관련 채용 정보

1. `many-shuffle` 실행 파일의 동작 분석

4. `flag` 복구