[Reversing] simultaneous

문제 정보#

출처: 정보보안 콘테스트를 위한 CTF 문제집
분야: Reversing
풀이 날짜: 2026. 06. 22

문제#

프로그램은 실행 시 12개의 정수를 입력받는다.
입력된 값은 check() 함수에서 검증되며, 모든 조건을 만족하면 입력한 정수들을 ASCII 문자로 출력하여 Flag를 생성한다.
즉, check() 함수의 검증 로직을 분석하여 조건을 만족하는 입력값을 찾는 것이 목표이다.

분석 및 Exploit#

프로그램 분석#

main() 함수 분석#

1
int __cdecl __noreturn main(int argc, const char **argv, const char **envp)
2
{
3
  int i; // [esp+0h] [ebp-2Ch]
4
  int j; // [esp+4h] [ebp-28h]
5
  _DWORD *v5; // [esp+8h] [ebp-24h]
6
  int status; // [esp+10h] [ebp-1Ch]
7

8
  v5 = calloc(4u, argc - 1);
9
  if ( argc != 13 )
10
  {
11
    puts("Usage: ./equation_revenge x1 x2 x3 x4 x5 x6 x7 x8 x9 x10 x11 x12");
12
    exit(-1);
13
  }
14
  for ( i = 0; i < 12; ++i )
15
    v5[i] = atoi(argv[i + 1]);
16
  status = check(v5);
17
  printf("FLAG{");
18
  for ( j = 0; argc - 1 > j; ++j )
19
    putchar(v5[j]);
20
  putchar(125);
21
  exit(status);
22
}

IDA에서 main() 함수를 분석한 결과 다음과 같은 흐름을 확인하였다.

입력 인자는 총 12개
atoi()를 이용하여 문자열을 정수 배열로 변환
변환된 배열을 check() 함수로 전달
검증 성공 시 입력값을 문자로 출력하여 Flag 생성

check() 함수 분석#

1
int __cdecl check(int a1)
2
{
3
  int i; // [esp+Ch] [ebp-4h]
4

5
  for ( i = 0; i <= 11; ++i )
6
  {
7
    if ( sum(a1, i) != b[i] )
8
      return 1;
9
  }
10
  return 0;
11
}

check() 함수를 분석한 결과 전역 변수 int coefficients[144]와 int b[12] 를 이용하여 입력값을 검증하고 있었다.

또한 반복문이 총 12번 수행되며, 조건문에 sum() 함수를 호출한다.

sum() 함수 분석#

1
int __cdecl sum(int a1, int a2)
2
{
3
  int v3; // [esp+8h] [ebp-8h]
4
  int i; // [esp+Ch] [ebp-4h]
5

6
  v3 = 0;
7
  for ( i = 0; i <= 11; ++i )
8
  // v3 += a1[i] * coefficients[12 * a2 + i]
9
    v3 += *(_DWORD *)(4 * i + a1) * cofficients[12 * a2 + i];
10
  return v3;
11
}

a1은 사용자가 입력한 12개의 정수가 저장된 배열의 시작 주소이고, a2는 사용할 계수 행렬의 행 번호이다.

sum() 함수는 입력 배열의 각 원소 a1[i]와 coefficients[12 * a2 + i]를 곱한 뒤 모두 더한다. 즉, 입력 벡터와 coefficients의 a2번째 행을 내적한 결과를 반환한다.

이 반환값은 check() 함수에서 b[a2]와 비교되므로, 하나의 선형방정식이 성립하는지를 검사하는 구조이다.

분석 결과#

전역 배열의 크기가 12 × 12 = 144 인 점을 보고 12개의 미지수를 갖는 연립방정식의 계수 행렬이라고 판단하였다.

수식으로 표현하면 다음과 같은 형태이다.

\begin{aligned} -72x_{1}-74x_{2}+91x_{3}+59x_{4}+53x_{5}-95x_{6}-32x_{7}-39x_{8}+93x_{9}+76x_{10}-31x_{11}+22x_{12} &= 4885 \\ 78x_{1}-84x_{2}-96x_{3}+69x_{4}-21x_{5}-72x_{6}+89x_{7}-26x_{8}+21x_{9}+65x_{10}+3x_{11}+49x_{12} &= 10656 \\ -46x_{1}+11x_{2}-39x_{3}+54x_{4}+57x_{5}-14x_{6}+59x_{7}-10x_{8}+77x_{9}-34x_{10}+0x_{11}+99x_{12} &= 14249 \\ 27x_{1}+4x_{2}+52x_{3}+23x_{4}-x_{5}+43x_{6}-41x_{7}+13x_{8}+9x_{9}-70x_{10}-16x_{11}+91x_{12} &= 7244 \\ 60x_{1}-92x_{2}+84x_{3}+58x_{4}-8x_{5}-6x_{6}+91x_{7}+8x_{8}-30x_{9}-11x_{10}-5x_{11}-96x_{12} &= 17152 \\ -91x_{1}-16x_{2}-96x_{3}+51x_{4}-56x_{5}-85x_{6}-52x_{7}+46x_{8}-78x_{9}+87x_{10}+96x_{11}-83x_{12} &= -22439 \\ -32x_{1}-80x_{2}-80x_{3}+54x_{4}-28x_{5}-85x_{6}-38x_{7}-75x_{8}+5x_{9}+32x_{10}-80x_{11}-72x_{12} &= -41829 \\ 5x_{1}-18x_{2}+6x_{3}+74x_{4}-9x_{5}-64x_{6}+30x_{7}-44x_{8}-26x_{9}-6x_{10}-22x_{11}+13x_{12} &= -7222 \\ 30x_{1}+61x_{2}-100x_{3}+63x_{4}-19x_{5}-92x_{6}+68x_{7}-38x_{8}-11x_{9}-96x_{10}+44x_{11}-50x_{12} &= -12530 \\ 59x_{1}+4x_{2}+99x_{3}-62x_{4}-34x_{5}-89x_{6}-52x_{7}+87x_{8}+22x_{9}+38x_{10}+86x_{11}+15x_{12} &= 18797 \\ -75x_{1}-92x_{2}-21x_{3}+62x_{4}-77x_{5}-31x_{6}-10x_{7}+90x_{8}+83x_{9}+89x_{10}+66x_{11}-17x_{12} &= 13201 \\ -5x_{1}+23x_{2}-29x_{3}+16x_{4}+25x_{5}+50x_{6}+95x_{7}+65x_{8}-57x_{9}+35x_{10}+4x_{11}+22x_{12} &= 22623 \end{aligned}

총 12개의 식으로 구성된 연립방정식을 만족하는 해를 구해야 한다.

Exploit#

계수 추출#

IDA Free에서는 전역 배열 전체를 한 번에 확인하기 어려웠기 때문에 GDB를 이용하여 메모리에서 계수를 직접 추출하였다.

cofficients[144] 전역 배열 데이터 추출

1
gdb ./equation_revenge
2
(gdb) x/144dw &cofficients

b[12] 전역 배열 데이터 추출

1
gdb ./equation_revenge
2
(gdb) x/12dw &b

연립방정식 풀이#

NumPy의 numpy.linalg.solve()를 이용하여 미지수 12개를 계산하였다.

1
import numpy as np
2

3
A = np.array([
4
    [-72, -74, 91, 59, 53, -95, -32, -39, 93, 76, -31, 22],
5
    [78, -84, -96, 69, -21, -72, 89, -26, 21, 65, 3, 49],
6
    [-46, 11, -39, 54, 57, -14, 59, -10, 77, -34, 0, 99],
7
    [27, 4, 52, 23, -1, 43, -41, 13, 9, -70, -16, 91],
8
    [60, -92, 84, 58, -8, -6, 91, 8, -30, -11, -5, -96],
9
    [-91, -16, -96, 51, -56, -85, -52, 46, -78, 87, 96, -83],
10
    [-32, -80, -80, 54, -28, -85, -38, -75, 5, 32, -80, -72],
11
    [5, -18, 6, 74, -9, -64, 30, -44, -26, -6, -22, 13],
12
    [30, 61, -100, 63, -19, -92, 68, -38, -11, -96, 44, -50],
13
    [59, 4, 99, -62, -34, -89, -52, 87, 22, 38, 86, 15],
14
    [-75, -92, -21, 62, -77, -31, -10, 90, 83, 89, 66, -17],
15
    [-5, 23, -29, 16, 25, 50, 95, 65, -57, 35, 4, 22]
16
], dtype=np.int64)
17

18
b = np.array([
19
    4885, 10656, 14249, 7244, 17152, -22439, -41829, -7222, -12530, 18797, 13201, 22623
20
], dtype=np.int64)
21

22
x = np.linalg.solve(A, b)
23

24
print("Solution:")
25
for i, value in enumerate(x, start=1):
26
    print(f"x{i} = {value}")
27

28
print("\nRounded:")
29
print(np.round(x).astype(int))

코드 실행 결과:

결과#

Flag#

파이썬 코드로 구한 연립방정식들의 해를 매개변수로 입력하면 Flag를 얻을 수 있다.

1
FLAG{z3_beginner!}