Codegate2019 - Map2048

2019 코드게이트 Final - Map2048

​

※ 들어가기 전 주의 사항 ※

​

안녕하세요, Map2048 제작자 Choirish 입니다.
본 글은, 문제 제작 시 간략히 정리해둔 readme 를 일부 가공한 것으로
바이너리를 직접 분석하는 내용의 일반적인 Writeup 형태가 아님을 미리 알려드립니다(!)

제작자의 입장에서, 문제를 만들며 고려한 Solving Point와 간략한 풀이 방법(How to Solve)을 글로 정리하였으니 문제 풀이 Tip 요약본으로 생각하고 가볍게 읽어 주시길 바랍니다 :)

Challenge Info

• Challenge Name : Map2048

• Category : Reversing ( + Pwnable ??? )

• Vulnerability : Heap Leak + 1byte Arbitrary Write

★★★ Solving Point ★★★

• 2048 블록을 만드는 것이 최종 목표

• 하지만 맵에는 2, 4, 8, 16, 32 블록만 있고, 블록을 저장할 수 있는 공간이 6칸으로 제한됨.

  • 즉 6칸만으로는 최대 1024까지만 만들 수 있다.

  • ★★★ 저장 공간을 늘릴 수는 없으니, 64 블록이 맵에 나타나도록 만들어야 함.

• 따라서 맵에 떨어지는 블록(a, b, c, d, e)의 값을 결정하는 Number 구조체 [2, 4, 8, 16, 32] 의 4번째 값을 변조하여 [2, 4, 8, 64, 32]로 만든다.

  • 즉 [a, b, c, d, e] 블록 중 'd' 블록을 먹었을 때 16 대신 64를 얻을 수 있도록 바꿔야 함.

  • 16인 블록과 64인 블록의 구조체할당 크기가 같으므로, (아마) 꼭 16을 64로 바꿔야만 에러가 안난다…(?!)

★★★ How to Solve ★★★

1. 게임 시작할 때 이름을 A@AA 로 설정한다. (두 번째 값이 꼭 @이어야 함)

   • @ = 0x40 = 64

   • 4번에서 Arbitrary Write 할 때, 이름의 2번 째 글자 1byte를 원하는 주소에 쓸 수 있다.

   • Number 구조체의 값 중 하나를 64로 변조할 것이므로, @를 이용해야 함(!)

2. 블록들을 (적절히) 모아서 1024를 만들면 Heap 주소를 Leak 할 수 있다.

   • 블록들을 적절한 순서로 잘 모아서… 256 + 256 = 512를 만들었을 때 512 구조체의 특정 위치(dummy = 블록 구조체의 첫 번째 8byte)에, 해제되었었던 구조체의 fd 값이 오도록 한다.

   • 따라서 512 + 512 합성하면서 money를 계산할 때 해당 dummy 값을 참조하기 때문에… 합성 후 얻은 머니를 통해 Heap의 주소(fd)를 릭할 수 있다.

   • 이 때, dummy 값에 있는 fd 값이 Heap의 어느 위치를 가리키는 지 알아야만! offset을 통해 Number 구조체의 주소를 구할 수 있다.

3. Money를 “Arbitrary Write할 주소 + 1024” 값으로 설정한다.

   • 4번에서 Arbitrary Write를 수행하기 전에 money를 맞춰 놓는 것 필수(!!!)

   • 이 때, “Arbitrary Write할 주소 = Number 구조체의 4번째 값 주소”

   • z, x, v 키를 통해 money 를 버릴 수 있다.

   • Arbitrary Write를 위해 1024를 Submit 할 때, 1024 money가 필요하므로 “주소 + 1024”로 설정해야 함.

4. 1024를 Submit Center에 제출하고, 돈을 탕진하여 랭크에 등록한다.

   • 그러면 게임 시작 시 등록한 이름의 두번쨰 값(64)을, money 크기만큼의 주소위치에 1byte 써준다.

5. d(64) 블록을 모아 2048을 완성하고, 2048을 Submit 한다.

   • Number 구조체를 잘 변조했다면… ’d’(원래 16) 블록을 먹었을 때 64 블록이 생길 것이다(!)

   • 2048을 Submit 하면 Flag를 얻는다.

Key Information

• Opened Key

  • h/k/u/j or ←/→/↑/↓ : ←/→/↑/↓
  • g : get the block

• Hidden Key ( : must press the corresponding letter on each character in the map )

  • m : merge
  • s : submit
  • z : throw away 10000 money
  • x : throw away 100 money
  • v : throw away 1 money

Behind Story

• 제작자가 블록을 적절히 수집한 방법

  • 메모리 할당의 변수를 줄이기 위해… e(32) 블록만 수집한다… :)

  • 1024 블록을 만들어 Heap 주소를 Leak한 후 디버거를 붙여 offset을 확인한다.

    • offset : Leak된 Heap 주소 - Number 구조체의 4번째 값 주소

    • 일정한 방법으로 블록을 수집할 경우 웬만하면 offset이 일정하다.

    • 제공된 Dockerfile을 이용해 환경세팅 후 offset을 구하고 이를 Remote 서버에 똑같이 적용하면 된다.

• Heap Leak & 1byte Arbitrary Write

  • 사실 1byte 값을 쓰는 건, 해당 루틴을 찾아서 따라가기만 하면 되서 쉽다.

    • 다만 원하는 주소에 쓰기 위해서는 Heap 구조를 생각해야 함. (근데 사실 문제 쉬워져서 이것도 별로 필요없음)

    • 1byte를 쓸 때, 가지고 있는 블록의 값을 바꾸게 되면 너무 편리해지니까… 그 정도만 막아둠.

  • Heap Leak은 (아마도) 거의 항상 된다.

    • 원래 1024 블록 만들었을 때, Heap 주소가 Leak 되게 하려면 머리를 좀 썼어야 했는데… 어쩌다 쉬워짐…

    • Leak은 웬만하면 됨… 그래서 푸는 사람들도 여기서부터 뭔가 불타오르지 않았을까?!

• d(16) 블록의 값을 변조해야 하는 이유

  • 특정 블록을 주우면 각 블록에 따라 서로 다른 크기의 블록 구조체가 Heap에 할당된다.

  • 블록 숫자에 따라 할당되는 블록 구조체의 크기가 다른데…

  • [a, b, c, d, e] 블록을 먹었을 때는 항상 각각 [2, 4, 8, 16, 32] 블록의 고정된 크기만큼 할당된다.

  • 즉, a 블록을 먹었을 때 64를 얻도록 변조하더라도 a 블록을 먹으면 “2”짜리 블록의 지정된 크기(0x20)만큼 할당된다.

    • ※ “16”짜리 블록과 “64”짜리 블록을 얻었을 때 할당되는 블록 구조체의 크기는 0x60(헤더 제외)으로 같다(!)

    • 각 블록값에 따른 할당 크기는 전역 변수에 배열로 정의되어있다.

  • a 블록의 값을 64로 변조하면 어디서 문제가 발생할까?

    • a 블록을 변조하더라도, 해당 블록의 값은 64이지만 크기는 무조건 0x20(값이 2인 블록의 크기)이다…

    • 그런데 두 블록을 합치는(merge) 함수에서 해당 블록을 free하기 전에 memset()으로 해당 버퍼를 초기화할 때, 그 블록의 값(=64)에 따라 초기화할 버퍼의 크기를 정한다…

    • 즉, 해당 블록의 크기보다 더 큰 크기에 0을 memset하니까…. 그 다음 구조체의 헤더까지 망가뜨려서… free할 때 에러가 터지는 것이다(!!!)

• sleep……..

  • 사실 원래 sleep을 괴롭히려고 넣은 게 아니고… 출력되는 메세지를 읽을 시간은 있어야 할 것 같아서 한 장치인데..

  • sleep 말고 다른 방법을 썼어야 했다…

  • sleep 으로 고통받으신 분들께 사과말씀 드립니다(!)

문제 풀어주신 분들 모두 감사합니다 :)