Description

Spear of Destiny.

Writeup

[0x0] Prerequisite

문제를 풀기 전 알아두면 좋은 것들

• Algorithm: Compiler Theory
  • CT: Lexical Analysis (Aho-Corasick)
• Reversing: VM..?
• Algorithm: HLD
• Math: Linear Algebra
  • Linear Algebra: Linear Equation (In $GF(2)$)

<aside> 💡 난이도: Hard

</aside>

xi의 곡 Longinus, 더 자세히는 이를 소재로 한 osu! 비트맵의 Spare of Destiny 난이도를 모티브로 한 문제이다.

[0x1] Abstract

주어진 파일은 spearshooter, longinus.txt 이다. spearshooter는 ELF 실행 파일이고 동시에 컴파일러이다. longinus.txt는 Ascii Art 처럼 보이지만 실제로는 spearshooter 바이너리에서 지원하는 언어로 작성된 소스 코드이다. (…)

바이너리는 flex로 Lexical Analysis를 실행하고 이를 토대로 VM Instruction을 복호화한다. 이때 Instruction을 알아내기 위해 디버깅을 쓸 수 있지만 Anti-Debugging 테크닉이 존재하고 어짜피 나중에 Input을 토대로 sbox를 파싱하는 부분이 또 flex로 되어있기 때문에 동적 분석으로 완벽히 알아내는 것은 거의 불가능하다.

문제의 출제 의도는 적절한 알고리즘으로 문제 분석에 필요한 정보를 알아내고, 정보를 토대로 암호화된 정보를 역연산하여 플래그를 얻어내는 것이다.

[0x2] Detail

프로그램을 열면 크게 파일을 여는 부분, 함수를 대입하는 부분, 아마도 longinus.txt 의 파일을 읽는 부분이 있다.