[드림핵] 워게임 rev-basic-7 풀이

문제

https://dreamhack.io/wargame/challenges/21/

풀이

프로그램 실행

문제 유형을 파악하기 위해 Windows의 PowerShell을 이용하여 프로그램을 실행시켜줍니다. 아래와 같이 임의의 문자열을 입력하면 'Wrong'이 출력됩니다.
이를 통해 오답 시 'Wrong', 정답 시 'Correct'가 출력됨을 예측할 수 있습니다.

IDA 실행

main 함수를 디컴파일합니다. (단축키 F5)

int __cdecl main(int argc, const char **argv, const char **envp)
{
  char v4[256]; // [rsp+20h] [rbp-118h] BYREF

  memset(v4, 0, sizeof(v4));
  sub_140001120("Input : ", argv, envp);
  sub_1400011B0("%256s", v4);
  if ( (unsigned int)sub_140001000((__int64)v4) )
    puts("Correct");
  else
    puts("Wrong");
  return 0;
}

sub_140001000 함수를 더블클릭하여 함수의 내용을 확인합니다.

__int64 __fastcall sub_140001000(__int64 a1)
{
  int i; // [rsp+0h] [rbp-18h]

  for ( i = 0; (unsigned __int64)i < 0x1F; ++i )
  {
    if ( (i ^ (unsigned __int8)__ROL1__(*(_BYTE *)(a1 + i), i & 7)) != byte_140003000[i] )
      return 0i64;
  }
  return 1i64;
}

해결 과정

문제 rev-basic-7는 ROL에 대해 알지 못해 검색을 해야했습니다.

In left rotation, the bits that fall off at left end are put back at right end.
In right rotation, the bits that fall off at right end are put back at left end.

참조 : https://www.geeksforgeeks.org/rotate-bits-of-an-integer/


rol 함수를 생성하여 left rotation 코드를 작성했습니다.

def rol(value, count) :
    tmp1 = value << count
    tmp2 = value >> (8 - count)
    return((tmp1 + tmp2) % 2**8)

count만큼 왼쪽 비트 시프트 후, 넘어간 비트들은 오른쪽에 추가해주고 (tmp1과 tmp2의 덧셈 대신 OR 연산을 사용해도 무관) 총 8bits의 제한도 걸어주었습니다.

i ^ rol(a1[i], i & 7) == byte_140003000[i]

를 만족해야합니다.
위 식을 구하고자 하는 a1[i]를 기준으로 작성하겠습니다.

a1[i] == ror(byte_140003000[i] ^ i, i & 7)

여기서 ror은 right rotation입니다.

따라서 rol 대신 ror 함수를 생성하여 아래의 코드를 작성합니다.

nums = [0x52, 0xDF, 0xB3, 0x60, 0xF1, 0x8B, 0x1C, 0xB5, 0x57, 0xD1, 0x9F, 0x38, 0x4B, 0x29, 0xD9, 0x26, 0x7F, 0xC9, 0xA3, 0xE9, 0x53, 0x18, 0x4F, 0xB8, 0x6A, 0xCB, 0x87, 0x58, 0x5B, 0x39, 0x1E]

def ror(value, count) :
    tmp1 = value >> count
    tmp2 = value << (8 - count)
    return((tmp1 + tmp2) % 2**8)

i = 0
res = [0] * len(nums)

for i in range(0x1F) :
    res[i] = ror(nums[i] ^ i, i & 7)
    print(chr(res[i]), end='')

정답

Roll_the_left!_Roll_the_right!