[SECCON 2019] Follow me

follow_me

#reversing

※ 원본 Write Up : https://github.com/goseungduk/CTF_WriteUp/tree/master/SECCON_2019/rev/follow_me

---

---

우리의 숙제는 계산기 프로그램에서 실행했던 기록 중에서도 branch 명령에 대한 기록을 보고, 어떤 공식을 프로그램에 전달했는지 찾는 것이다.

파일은 총 3개, 계산기 프로그램 바이너리와 branch명령에 대한 기록, 그리고 branch명령을 따라가는 추적프로그램에 대한 소스코드를 준다.

필자는 앞의 계산기 프로그램 바이너리와 branch 명령에 대한 기록만 보고 문제를 풀었다.

---

main 함수이다. 바이너리의 사용법과 실제로 계산을 해주는 함수가 들어있다.

calculate 함수의 switch문 부분이다.

이 바이너리에서 다루는 연산자는 +, -, *, m, M 인 것으로 유추된다.

그리고 이 부분에 의해 숫자를 입력하면 입력한 숫자마다 차곡차곡 힙 메모리에 쌓인다.

아무튼 사전작업은 이정도이다.

calculate 함수를 분석하면서 어떤식으로 바이너리가 동작하는지 살펴보자.

한 가지 빼먹은 것이 있는데 ,(콤마) 문자를 입력하면 각 연산자 및 숫자를 구분할 수 있다. 이것도 아래에서 살펴보자.

---

우선, 각 숫자들은 입력한 순서대로 바이너리에서 지정한 스택에 차곡차곡 쌓인다.

그리고 연산자는 가운데에 쓰이는 중위연산이 아닌 후위연산으로 진행된다.

+, -, * 의 의미는 원래의 수학기호와 같고, m은 두 숫자 중 작은 것을 택하는 연산자, M은 두 숫자 중 큰 것을 택하는 연산자이다.

calc.trace 파일

calc.trace 파일에는 바이너리에서 거쳐간 모든 branch 명령어의 주소가 들어가있다. 그리고 그 부분에서 branch 를 했으면 true, 아니면 false로 표기해놓았다.

calc.trace의 개수가 많았다면 툴을 짜려고했으나, 생각보다 금방 분석할 것 같아서 수동으로 분석하였다.

---

우선 trace 기록을 연산자의 행동 단위로 쪼개서 볼 수 있다.
분석에는 IDA 7.0과 Ghidra를 같이 사용하였다.

숫자를 받아오는 부분

이 부분은 숫자하나를 받아오는 부분이다.

,(콤마) 를 받아오는 부분

이 부분은 ,(콤마) 하나를 받아오는 부분이다.

+ 를 받아오는 부분

이 부분은 + 연산자 하나를 받아오고 계산하는 부분이다.

다만 이제 주의할 점이 있다. 0xa1f 로 끝나는 주소부분이 + 연산자를 만날 때 마다 유동적으로 반복되는데, IDA로 자세히 보자.

무언가 소스가 나왔으나 뭔가 간단한 로직이 복잡하게 나온 것 같아서 Ghidra로 다시 확인해보기로 했다.

혹시나 했지만, 역시나였다.

단순히 그냥 두 번째 인자의 수를 10으로 나눈 후, 10을 곱해서 첫 번째 인자에 더한 다음, 두 번째 인자의 첫 자리 수 만큼 반복문을 돌아서 두 수의 합을 구하는 로직이다.

아마 0xa1f 로 끝나는 branch 명령주소는 저 반복문이 분기하는 주소일 것이다.

이를 토대로 어떤 형태의 수가 인자로 들어가야하는지 파악할 수 있다.

* 를 받아오는 부분

곱하는 * 는 소스를 통틀어서 단 한번, 마지막 부분 밖에 나오지않는다.

여기서도 주의해서 봐야할 부분이 있는데, 0xa81 부분이다.

이 부분도 Ghidra로 확인해야 깔끔하게 나온다.

중요한 부분은 + 에서 사용했던 덧셈 함수가 쓰인다는 점이다.

그래서 *의 branch 명령 기록에 0xa1f 로 끝나는 부분이 몇 번 나온 것이다.

그리고 0xa81로 끝나는 부분은 위의 곱셈함수의 반복문에 대한 것인데,

두 번째 인자의 수만큼 반복하는게 특징이다.

하지만, 단 한번 밖에 나오지 않는다. 고로 곱할 때 두번 째 인자로 1이 들어간다는 것을 알 수 있다.

- 를 받아오는 부분

이 부분은 그냥 뺄셈을 하는 과정이다. 별다른 특이사항은 없다.

m 을 받아오는 부분

이 부분은 두 개의 정수 중에 작은 것을 가져오는 연산이다.

M 을 받아오는 부분

이 부분은 두 개의 정수 중에 큰 것을 가져오는 연산이다.

---

이제 branch 기록이 어떻게 형성되어있는지 보았고 연산자마다 일정한 형태의 기록이 남아있다는 것을 알았으니, 각 연산자 branch 기록의 반복을 따라가면 최종적으로 이런 형태의 식이 나온다.

임의의 숫자는 1로 처리하였음.

111,111,111,111,111,1111,111,mm-mM-111,111,111,mm-111,111,111,111,111,-+-M+111,111,111,mm*

일단은 정답은 아니다.

이제 식에 대한 구조를 구했으니 정확히 어떤 수가 들어갈지 파악해야한다.

이 부분은 위의 연산자 설명에서 말한 +와 * 연산의 특징만 잘 파악하면 어떤 숫자가 들어갈지 파악할 수 있다. 뺄셈은 제외하고 덧셈과 곱셈만 설명하겠다.

위의 식을 뒤에서 부터 분석해보면,

곱셈연산을 하는데 branch 기록에서는 0xa81 branch가 단 한번 나왔으므로, 뒤의 인자가 1이어야한다.
그러면 결론적으로 곱셈을 하기전에 우선적으로 mm에 대한 결과가 1이어야한다.

따라서 111,111,111,mm* 는 001,002,003,mm* 으로 쓸 수 있겠다. 또한 곱셈 안에서도 덧셈을 6번을 하기에, 첫 번째 인자는 xx6 형태의 자연수가 될 것이다.

그리고 111,111,111,111,111,-+-M+ 여기서 첫 번째 덧셈은 맨 마지막에 입력한 두 수를 뺀 것을 더하는데 0xa1f branch가 3번 반복하므로 두 수를 뺀 것은 xx3 형태의 자연수가 될 것이다.

그리고 마지막 덧셈은 0xa1f branch가 8번 반복하므로 M에 의해 나온 수는 xx8 형태의 자연수가 될 것이다.

이를 고려하여 적합한 수를 입력하여 curl 명령을 보내주면 플래그를 얻을 수 있다.

formula

999,000,000,000,000,0000,000,mm-mM-931,932,933,mm-438,400,111,246,123,-+-M+001,002,003,mm*

• 공식에 대한 설명을 덧붙이려고 한다.

  0000m000 => 000  
  000m000 => 000  
  000-000 => 000  
  000m000 => 000  
  000M000 => 000  
  999-000 => 999  
  932m933 => 932  
  931m932 => 931  
  999-931 => 68  
  246-123 => 123  
  111+123 => 234 (0xa1f is repeated 3 times)  
  400-234 => 166  
  438M166 => 438  
  68+438 => 506  (0xa1f is repeated 8 times)  
  002m003 => 002  
  001m002 => 001  
  506*001 => 506  (0xa1f is repeated 6 times and 0xa81 is repeated 1 times)

flag

.
.
.

Contact : a42873410@gmail.com