Logo
Overview
[D-CTF] kings

[D-CTF] kings

andso andso
November 13, 2025
2 min read
rev D-CTF

✨ 바이너리 공짜 다운로드 ✨

TL;DR

7x7 board에 대해 열 인덱스 0-6에 대해 하나씩 행을 고르는 순열을 정하고 그 순열이 체스의 킹이 서로 인접하지 않도록 하며 board 상 밟는 문자가 모두 다른 경우 찾기 문제 👿

Analysis

int __fastcall main(int argc, const char **argv, const char **envp)
{
  char *segment;
  int ok;
  int j, k, c;


  segment = malloc(0x100);
  printf("Enter solution: \n");
  __isoc99_scanf("%s", segment);
  if ( strlen(segment) != 252 ) {
    printf("Error: Expected %d digits, but received %zu.\n", 252, strlen(segment));
    return 1;
  }


  ok = 1;
  for ( int i = 0; i < 36; ++i ) {
    char *board = &BOARD[49 * i];
    char *slice = &segment[7 * i];
    if ( !check_solution(board, slice) )
      ok = 0;
  }


  if ( !ok ) {
    puts("The solution is invalid.");
    return 1;
  }


  puts("Correct! Here is the flag:");
  for ( j = 0; j < 36; ++j ) {
    c = 0;
    for ( k = 0; k <= 6; ++k ) {
      int digit = segment[7 * j + k] - '0';
      if ( digit == CHECK_LIST[7 * j + k] )
        c = (c << 1) | 1;
      else
        c <<= 1;
    }
    putc(c, stdout);
  }
  return 0;
}

입력은 252 길이의 문자열만 허용된다. 문자열은 길이 7짜리 chunk 36개로 나뉘며, 각 chunk는 한 board의 열→\rightarrow행 매핑을 의미한다.

  • chunk slice = &segment[7 * i];
  • board board = &BOARD[49 * i];

jj번째 chunk에 대해, segment[7*j + k] - '0' 값이 CHECK_LIST[7*j + k]와 같으면 1, 아니면 0 왼쪽에서부터 순서대로 shift하며 7비트 값을 만든 뒤 putc로 출력. 즉, 각 chunk당 1바이트, 총 36바이트의 플래그를 구성한다.

check_solution(0x1179)

__int64 __fastcall check_solution(const char *board, const char *slice)
{
  int digits[7];
  for (int i = 0; i < 7; ++i) {
    char ch = slice[i];
    if (ch < '0' || ch > '6') {
      printf("\n  [Error: Invalid character '%c' in solution]\n", ch);
      return 0;
    }
    digits[i] = ch - '0';
  }


  for (int j = 0; j < 7; ++j) {
    for (int k = j + 1; k < 7; ++k) {
      if ( digits[j] == digits[k] )
        return 0;
      if ( abs(digits[j] - digits[k]) <= 1 && abs(j - k) <= 1 )
        return 0;
    }
  }


  uint8_t seen[256] = {0};
  for (int m = 0; m < 7; ++m) {
    int row = digits[m];
    char letter = board[row * 7 + m];
    if ( seen[(unsigned char)letter] )
      return 0;
    seen[(unsigned char)letter] = 1;
  }
  return 1;
}

세 가지 조건이 동시에 만족해야 한다.

  1. chunk 안에 중복 숫자가 없어야 한다.
  2. ∣rowm−rown∣≤1\lvert row_m - row_n \rvert \le 1 이면서 ∣m−n∣≤1\lvert m - n \rvert \le 1 인 쌍이 없어야 한다. 즉 킹이 서로 붙을 수 없다.
  3. board 문자 행렬에서 방문하는 문자가 모두 달라야 한다.

board 데이터는 .rodata 0x2020에 저장된 36x49바이트 문자열이다. 문자 집합은 {A,B,C,D,E,F,G}

rowdata

각 board에 대해 permuation을 전수조사해야 한다. 열이 7개이므로 가능한 순열 수는 7!=50407! = 5040개다. brute force 중에는 위 조건들을 재현해야 하므로 check_solution의 로직을 그대로 쓰자

import itertools


def is_valid(board, perm):
    if any(abs(perm[i] - perm[i + 1]) <= 1 for i in range(6)):
        return False
    seen = set()
    for col, row in enumerate(perm):
        letter = board[row * 7 + col]
        if letter in seen:
            return False
        seen.add(letter)
    return True


solutions = []
for board in boards:
    for perm in itertools.permutations(range(7)):
        if is_valid(board, perm):
            solutions.append(perm)
            break

check_solution은 열 인접성만 검사하기 때문에 전체 (72)\binom{7}{2} 쌍을 모두 검사할 필요는 없다고 생각했지만, 실제 함수는 ∣m−n∣≤1\lvert m - n \rvert \le 1 조건도 포함한다. 따라서 ㅠ 상하대각선 인접까지 생각해야한다.

flag_chars = []
for i, perm in enumerate(solutions):
    bits = 0
    for k, digit in enumerate(perm):
        bits = (bits << 1) | (digit == check[7 * i + k])
    flag_chars.append(chr(bits))
flag = ''.join(flag_chars)

각 board당 첫 번째 valid 순열을 뽑고 찾은 순열을 CHECK_LIST와 비교해 문자 하나를 만든다.

362514031526406351402461520353042610352416026351435261402641530420536105246135146302264051352036416425130524061352406314025361315204620536145316402415036235204613164250625314063152404253160162530425316041463502504136241620530352416302461506135244253160

그렇게 값이 뽑히고 넣으면 플래그가 튀어나온다.

Terminal window
andsopwn@meow:~/ctftemp/defcamp$ ./kings
Enter solution:
362514031526406351402461520353042610352416026351435261402641530420536105246135146302264051352036416425130524061352406314025361315204620536145316402415036235204613164250625314063152404253160162530425316041463502504136241620530352416302461506135244253160
Correct! Here is the flag:
DCTF{k1ngs_4nd_qu33ns_s4a11_b3_n1ce}