[Webhacking.kr] 4번 문제풀이

우선 4번은 정말 미친 문제다 ㅋㅋ.. 내 컴퓨터 CPU를 정말 여러모 힘들게 했던 문제다.

문제 첫 화면

이상한 문자가 나열되어 있고, 패스워드를 제출하라고 한다. 우선 이게 뭘까..하고 생각했다. 글자수가 40자리인 걸 보고 바로 SHA-1 암호화인 걸 알아내셨다면, 당신은 어쩌면 '진짜'다.. 잠시 대표적 해시함수들에 대해 길이를 나눠보자면

 

∙ md5 해시값 길이 = 128비트 (16진수로 32바이트)

∙ sha-1의 해시값 길이 = 160비트 (16진수로 40바이트)

∙ sha-256의 해시값 길이 = 256비트 (16진수로 64바이트)

 

위에 문제에서 나온 문자 하나당 16진수의 냄새를 느끼고 길이가 40인걸로 보아 sha-1 해시값이라고 바로 아실 필요는 없다. 왜냐면 문제에서 제공해준다. 어디냐고? 바로 [view - source ] 를 클릭해보자.

<?php
  sleep(1); // anti brute force
  if((isset($_SESSION['chall4'])) && ($_POST['key'] == $_SESSION['chall4'])) solve(4);
  $hash = rand(10000000,99999999)."salt_for_you";
  $_SESSION['chall4'] = $hash;
  for($i=0;$i<500;$i++) $hash = sha1($hash);
?>

쓸데없는 부분은 다 지우고 이 부분만 보면 된다. 코드를 읽어보아하니..

천만부터 1억 미만까지의 수를 랜덤으로 뽑은 뒤에 "salt_for_you"라는 문자와 문자열 덧셈 연산을 하고, 이를 sha1 함수로 500번 연산한 값이 바로 저 위에 보여준 문자값이란다. 그렇다. 이 문제는 바로 레인보우 테이블을 만들라는 문제다. 레인보우 테이블이 뭐냐고? 단방향 암호화 알고리즘의(=해시 알고리즘) 특징인 '문자열 A를 암호화하면 어떤 경우에도 문자열 B가 된다'는 특징을 이용하여, 특정 문자열들에 대한 암호화를 통해 도출된 결과값들을 모두 저장한 것이 레인보우 테이블이다. 단방향 알고리즘의 특성 상 결과값을 통해 입력값을 알아낼 수 없으므로, 아예 입력값들을 가능한 범위 내에서 최대한 만들어 단방향 알고리즘을 시킨 뒤 이 결과를 결과값과 비교하도록 만드는 것이다.

문제에서 숫자가 1천만부터 1억 미만까지이므로 이 숫자를 구하는 게 목표인데, 그냥 웹사이트에 처음부터 끝까지 넣지 못하게 anit brute force 문을 적용시켜놨다. 즉 우리는 무조건 레인보우 테이블을 만들어야 한다 ㅋㅋ..

 

90,000,000 x 500 의 연산을 수행해야 한다. 코딩에 따라 며칠이 걸릴 수도 있다. 나는 그래도 시간을 절약하고자 9개의 쓰레드를 이용했다. 처음에는 내 맥북 프로로 1시간정도 넘게 돌렸는데, 맥북이 금방이라도 터질듯이 달아오르는 바람에 바로 데스크탑으로 이동했다. 데스크탑에서 결과값을 찾는 데 까지 프로그램을 돌린 시간은 약 6시간. 물론 프로그램은 끝까지 진행되지 않았다. 내가 도중에 운 좋게 얻어걸렸을 뿐.. 웹 페이지에서 계속해서 랜덤으로 값을 주기 때문에 프로그램의 흐름과 거리가 먼 수일 수록 굉장히 오랜 시간이 걸릴 것이다.

 

참고로 레인보우 테이블을 만들지 않고 해시값을 바로바로 비교해서 결과를 찾는 방식 따위는 시도하지도 말아라.

결과를 찾는 데 시간이 정말 오래 걸리는데, 그 사이 웹 페이지와의 로그인 세션이 종료되는 순간에 이미 다른 랜덤값으로 결과는 업데이트 될 것이다... JAVA 소스 첨부하면서 이만 줄이겠습니다.. 행운을 빌어요.. 벌써 해가 떴네 ㅎ.

import java.io.*;
import java.math.BigInteger;
import java.security.MessageDigest;

public class hello {
    public static void main(String args[])
    {
        brute_thread b_[] = new brute_thread[9];

        for(int i = 1; i < 10 ; i++)
        {
            b_[i-1] = new brute_thread(i*10000000, (i+1)*10000000);
            b_[i-1].start();
        }
    }
}

class brute_thread extends Thread {
    int start_ = 0;
    int end_ = 0;
    String str, w;
    FileOutputStream fos;
    File f;

    brute_thread(int s, int e) {
        start_ = s;
        end_ = e;
        f = new File("생성할 파일 경로/생성할 파일");
        try {
            fos = new FileOutputStream(f);
        }catch (Exception x){

        }
    }

    @Override
    public void run() {
        super.run();
        try {
            for (int i = start_; i < end_; i++) {
                str = "" + i + "salt_for_you";
                for (int j = 0; j < 500; j++)
                    str = makeSHA_t(str);

                w = "i : "+i+" sh : "+str+"\n";
                fos.write(w.getBytes());
            }
        } catch (Exception e) {

        }
    }

    //이게 제대로 된, 그니까 다른 언어들과 공통되는 (php, python 등) 표준 SHA1 방식이라고 보면 돼.
    public static String makeSHA_t(String inputText) throws Exception {
        MessageDigest digest = MessageDigest.getInstance("SHA-1");
        digest.reset();
        digest.update(inputText.getBytes("utf8"));
        return String.format("%040x", new BigInteger(1, digest.digest()));
    }
}

인터넷에 존재하는 SHA-1 해싱함수 중에, 결과가 문제에서 사용하는 php에서 제공하는 해싱함수의 결과와 동일하지 않는 알고리즘들도 많으니 주의하시길 바랍니다. (문제에서 사용하는 sha1해싱 함수가 php의 함수이므로 이 함수의 결과와 동일한 작용을 하는 함수를 사용해야 되겠죠?)