pwnable.kr - coin1 문제풀이(Write Up)

문제 분류: 코딩(Coding)

  이번 시간에 풀어 볼 문제는 대표적인 CTF 문제풀이 사이트인 pwnable.kr의 기초 문제 중 'coin1' 문제입니다. CTF 공부 카테고리에서 실질적으로 풀어보는 첫 번째 문제가 될 겁니다. pwnable.kr 공식 웹 사이트에서 coin1 문제를 확인하실 수 있습니다.

  ▶ 문제풀이 사이트 주소: http://pwnable.kr/play.php

  문제를 확인해보면 pwnable.kr에 9007번 포트로 접속해보라고 나오는 것을 알 수 있습니다.

  문제를 요약하면 다음과 같습니다.

- N은 코인의 개수, C는 시도 횟수

- 서버로 코인의 번호들을 보내면 서버는 해당 코인들의 무게 합을 반환합니다.

- 가짜 코인이 하나 숨어있는데, 가짜 코인의 무게는 9이고 정상 코인의 무게는 10입니다.

  따라서 이 문제를 해결하기 위해서는 이분 탐색을 수행하면 됩니다. 예를 들어 전체 코인이 4개가 있고, 각 코인의 무게가 다음과 같다고 해봅시다.

코인: 0 1 2 3

무게: 10 10 9 10

  이 때 맨 처음에 서버로 “0 1”을 보낼 수 있습니다. 그러면 서버에서는 두 코인의 무게 합인 20을 반환할 겁니다. 우리는 이 20이라는 결과를 통해서 ‘아, 0과 1 중에는 가짜 코인이 없구나.’ 라는 것을 알 수 있습니다. 그러면 0과 1은 더 이상 볼 필요 없이 2와 3을 보면 됩니다.

  2와 3 중에서 반드시 하나는 가짜 코인이 섞여있다는 것을 알고 있기 때문에 “2”만 보내면 됩니다. 만약에 서버로부터 돌아오는 결과가 9라면 2가 가짜 코인이고, 서버로부터 돌아오는 결과가 10이라면 3이 가짜 코인이 되는 것입니다.

  이와 같이 현재 ‘가짜 코인’이 섞여있는 코인의 집합 중에서 계속해서 절반(Half)만 확인하는 식으로 매 번 검사할 때마다 검사하는 집합의 크기를 1/2로 줄일 수 있습니다. 이것은 이분 탐색의 대표적인 예라고 할 수 있으며 통상적으로 코인의 개수가 N개일 때 O(logN)의 시간 복잡도를 가집니다.

  이제 문제를 푸는 방법을 알았으므로 Java를 이용해 서버 통신 모듈을 개발합니다.

import java.io.BufferedReader;

import java.io.BufferedWriter;

import java.io.IOException;

import java.io.InputStream;

import java.io.InputStreamReader;

import java.io.OutputStream;

import java.io.OutputStreamWriter;

import java.net.Socket;

public class Main {

private static Socket sock = null;

private static OutputStream out = null;

private static InputStream in = null;

private static BufferedWriter bw = null;

private static BufferedReader br = null;

public static void init() {

try {

sock = new Socket("pwnable.kr", 9007);

out = sock.getOutputStream();

in = sock.getInputStream();

bw = new BufferedWriter(new OutputStreamWriter(out));

br = new BufferedReader(new InputStreamReader(in));

} catch (Exception e) {

e.printStackTrace();

}

}

public static void close() {

try {

bw.close();

br.close();

sock.close();

} catch (IOException e) {

e.printStackTrace();

}

}

public static int findAnswer() {

    try {

    // 서버로부터 메시지를 전달 받습니다.

    String line = null;

        while((line = br.readLine()) != null){

        // 전달 받은 메시지를 출력합니다.

        System.out.println(line);

        // 첫 번째 문자가 'N'인 경우 문제 풀이가 시작된 것입니다.

        if(line.length() != 0 && line.charAt(0) == 'N') break;

        }

        // N과 C를 파싱하여 각각 숫자로 변환합니다.

        int N = Integer.parseInt(line.split("N=")[1].split(" C")[0]);

        int C = Integer.parseInt(line.split(" C=")[1]);

        System.out.println("N의 값은 " + N + ", C의 값은 " + C);

    } catch (Exception e) {

    e.printStackTrace();

    }

return -1;

    }

public static void main(String[] args) {

try {

init();

findAnswer();

close();

} catch (Exception e) {

System.out.println(e);

}

}

}

  전체 소스코드는 소켓 통신 관련 객체를 초기화하는 init() 함수, 소켓 통신 관련 객체를 파기하는 close() 함수, 서버와 직접 통신해 답을 찾아내는 findAnswer() 함수로 구성됩니다. 일단은 간단하게 findAnswer() 함수에서 서버로부터 메시지를 계속 전달 받되, 첫 번째 문자가 “N"인 라인을 만나면 N과 C의 값을 파싱하여 변수에 담는 것까지 작업해보았습니다.

  실행 결과는 위와 같습니다. 서버로부터 계속 데이터를 전달 받다가, “N=숫자 C=숫자”의 형태를 만나면 이를 Java의 split() 함수를 이용해 숫자 정보만 파싱하는 것입니다. 이제 N과 C를 받아오는 모듈까지 작성했으므로 이를 확장시켜서 이분 탐색을 활용해 정답을 도출하도록 확장시키면 됩니다.

import java.io.BufferedReader;

import java.io.BufferedWriter;

import java.io.IOException;

import java.io.InputStream;

import java.io.InputStreamReader;

import java.io.OutputStream;

import java.io.OutputStreamWriter;

import java.net.Socket;

public class Main {

private static Socket sock = null;

private static OutputStream out = null;

private static InputStream in = null;

private static BufferedWriter bw = null;

private static BufferedReader br = null;

public static void init() {

try {

sock = new Socket("pwnable.kr", 9007);

out = sock.getOutputStream();

in = sock.getInputStream();

bw = new BufferedWriter(new OutputStreamWriter(out));

br = new BufferedReader(new InputStreamReader(in));

} catch (Exception e) {

e.printStackTrace();

}

}

public static void close() {

try {

bw.close();

br.close();

sock.close();

} catch (IOException e) {

e.printStackTrace();

}

}

public static int findAnswer() {

    try {

    // 서버로부터 메시지를 전달 받습니다.

    String line = null;

        while((line = br.readLine()) != null){

        // 전달 받은 메시지를 출력합니다.

        System.out.println(line);

        // 첫 번째 문자가 'N'인 경우 문제 풀이가 시작된 것입니다.

        if(line.length() != 0 && line.charAt(0) == 'N') break;

        }

        // N과 C를 파싱하여 각각 숫자로 변환합니다.

        int N = Integer.parseInt(line.split("N=")[1].split(" C")[0]);

        int C = Integer.parseInt(line.split(" C=")[1]);

        int up = N - 1;

        int down = 0;

        while(down <= up && C > 0) {

            int middle = (up + down) / 2;

            String message = "";

            for(int i = down; i <= middle; i++) {

            message += i + " ";

            }

            // 서버로 확인하고자 하는 코인들의 번호를 전달합니다.

            System.out.println("보낸 값: " + message);

            bw.write(message);

            bw.newLine();

            bw.flush();

            C--;

            // 서버로부터 결과 정보를 전달 받습니다.

            line = br.readLine();

            System.out.println("받은 값: " + line);

            int next = Integer.parseInt(line);

            // 10으로 나누어진다면 해당 범위에 가짜 코인이 없습니다.

            if(next % 10 == 0) {

            down = middle + 1;

            }

            // 그렇지 않다면 해당 범위에 가짜 코인이 있습니다.

            else {

            up = middle - 1;

            }

        }

        // 아직 확인할 수 있는 횟수가 더 남았다면 다 쓸 때까지 전송합니다.

        if(C > 0) {

            bw.write(down + "");

            bw.newLine();

            bw.flush();

        }

        // 결과적으로 찾은 가짜 코인의 번호는 down에 담겨있습니다.

        return down;

    } catch (Exception e) {

    e.printStackTrace();

    }

return -1;

    }

public static void main(String[] args) {

try {

init();

// 게임이 여러 차례 존재하므로 무한정 실행시킵니다.

while(true) {

int bottom = findAnswer();

String message = bottom + "";

System.out.println("가짜 코인 발견: " + message);

// 한 차시 게임에서 찾은 답을 전송합니다.

            bw.write(message);

            bw.newLine();

            bw.flush();

}

} catch (Exception e) {

System.out.println(e);

}

}

}

  결과적으로 총 100차례의 게임이 빠르게 수행되고 플래그 값으로 b1NaRy_S34rch1nG_1s_3asy_p3asy를 찾았습니다. 이를 입력하면 정답 처리를 받게 됩니다.