Kang MyoungSeok

Kang MyoungSeok

Blog for Studying
Computer Science Engineering
and Cyber Security

[webhacking.kr] 4번 문제 풀이[SHA1,Rainbow Table]

6 분 소요

💡 Webhacking.kr challenge(old) 4번 문제에 대한 풀이입니다.

문제

소스코드

  <?php
    include "../../config.php";
    if($_GET['view-source'] == 1) view_source();
  ?><html>
  <head>
  <title>Challenge 4</title>
  <style type="text/css">
  body { background:black; color:white; font-size:9pt; }
  table { color:white; font-size:10pt; }
  </style>
  </head>
  <body><br><br>
  <center>
  <?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);
  ?><br>
  <form method=post>
  <table border=0 align=center cellpadding=10>
  <tr><td colspan=3 style=background:silver;color:green;><b><?=$hash?></b></td></tr>
  <tr align=center><td>Password</td><td><input name=key type=text size=30></td><td><input type=submit></td></tr>
  </table>
  </form>
  <a href=?view-source=1>[view-source]</a>
  </center>
  </body>
  </html>



문제 해석

4번 문제는 암호학에 대한 지식이 필요한 문제입니다. 문제를 처음 들어가면 해시 값이 보이는데, 저 해시 값을 어떻게 해야 되는지는 문제의 소스코드를 보고 분석해 보겠습니다.

image

우선 문제를 풀기위한 조건을 보면 다음과 같습니다.

 if((isset($_SESSION['chall4'])) && ($_POST['key'] == $_SESSION['chall4'])) solve(4);

SESSION['chall4']와 POST['key'] 값이 같으면 풀립니다.

  1. POST[‘key’] 값은 내가 문제 화면에서 입력하는 값
  2. SESSION[‘chall4’]값은 
     $hash = rand(10000000,99999999)."salt_for_you";
 $_SESSION['chall4'] = $hash;

23958927salt_for_you 와 같이 랜덤 값 + 'salt_for_you'꼴의 문자열 값 입니다. 즉, 랜덤 값을 찾으면 되는 문제 입니다.

그러면 화면에 출력되는 저 해시 값은 어떻게 산출된 것인지를 보면

 $_SESSION['chall4'] = $hash;
 for($i=0;$i<500;$i++) $hash = sha1($hash);
 ...
 <tr><td colspan=3 style=background:silver;color:green;><b><?=$hash?></b></td></tr> 
 ...

랜덤 값+salt_for_you 값을 500번 sha1해시한 결과 입니다.

문제를 종합해 보면, 주어진 해시값을 통해서 랜덤 값을 찾아내는 문제로 요약할 수 있습니다.

기본 상식으로, 해시 값을 보고 원본 값을 찾아내는 것은 불가능 합니다. 암호학적으로 접근해서 취약한 부분이 있는건 논외로 하고

그렇다면 해당 문제는 흔히 말하는 Rainbow table을 만들어 놓고, Rainbow Table을 통해서 값을 찾아야 합니다.

근데 이 포스팅을 쓰면서 Rainbow table을 이해하고 푼 사람들이 있을까 하는 호기심으로 여러 포스팅을 찾아보니까, 대부분의 사람들이 역시 Rainbow Table의 개념을 이해하지 못하고 해당 문제를 푼 것 같았습니다. 대부분의 사람들이 푼 풀이는

[1] Plain_text <-> hash value
[2] Plain_text <-> hash value

…

[9999999] plain_text <-> hash_value

처럼 많은 양의 원본 값과 그 값에 대응되는 해시 값을 저장해 놓고 Rainbow table이라고 부르고 있었는데,,, 엄밀히 말하면 이는 Rainbow Table이 아니고 그냥 사전파일 방식으로 푼 것입니다. 본 포스팅에서는 공부 차원에서 사람들이 풀던 풀이[사전 파일]와, Rainbow Table의 핵심인 Hash Chain을 이용한 방식을 이용하여 두가지가 무엇이 다른지를 비교해 보고자 합니다.

제가 봤을 때, Rainbow Table에 대한 설명이 가장 깔끔하게 되어 있는 건 위키피디아였습니다. 해당 사이트에서 레인보우 테이블에 대한 예시를 이해하고 보시면 될 것 같습니다.

풀이

1. Dictionary attack

개념

문제에서 가능한 수의 범위인 10000000 ~ 99999999 까지의 모든 수에 대해서 해시값을 미리 구해놓고, 답을 구하는 방식입니다. 해당 방식의 가장 큰 문제점은 파일의 크기가 매우 커진다는 점입니다. 문제 조건이 아주 한정적임에도 불구하고, 제가 만든 사전 파일의 경우 10000000 ~ 20000000 까지의 값만 넣어놨을 때, 500MB정도의 크기가 나왔습니다.

image

문제를 풀다보면 알겠지만 굳이 10000000 ~ 99999999 까지의 모든 숫자에 해당하는 해시 값을 구할 필요가 없습니다. 그렇게 하면 파일 용량이 매우 커질 뿐만 아니라, 구하는데 걸리는 시간이 매우 길어집니다. 저같은 경우 10%정도만 구했지만 1시간 정도의 시간이 걸렸습니다.

저는 이 문제를 풀때 1000000 ~ 20000000 까지의 값만 구해놓고 문제에서 주어진 해시 값이 사전 파일에 없으면 다시 접속 해서 나의 사전파일에 존재하는 해시값이 나올 때까지 재접속을 시도하는 방식으로 했습니다.

만약 문제의 전체, 1억개의 해당하는 모든 값을 구하려고 한다면 파일을 만드는데만 10시간 이상이 걸릴테니 매우 비효율 적입니다.

Make_Dictionary

다음과 같이 사전 파일에 천만개에 대한 해시 값을 넣어줬습니다.

dictionary.txt 파일 구성

10000000:9d5c178303e59cc8e1266f088f54db1333164a38
10000001:fac92fc681904515285d6856707b566e0c961116
10000002:b9d75ef1ef20f0f770ade1d8504e98ee0a43c9af
10000003:44b59a1c3b0479a6fcad91c4f69a5348f2cc7d1c
10000004:c8628b1c8d5288ffe49a7889ff36e6c69c9a78bb
10000005:0aa4a375bef19361d34fff0a34b936209bc64485
10000006:267f111d681c9421f2b229951636b2fa2b94ec61
10000007:916c7cdf1d6e99504251c50a20433bc1d67421e5
10000008:22687438d25343bef450d74872cb482760796e27
10000009:fef869c263a221c3e7c12efce4c076947ad3e09a

... 1000만개의 column

20000000: b929ccd6672f219d6bd1f6e1ca9f2a49af4e84f1

Search_Dictionary

그 다음은 문제에서 준 해시값이 내 사전파일에 있는지 찾고, 없으면 다시 해시값을 구해오는 과정을 자동화 시켰습니다.

위의 코드를 실행하면 그림과 같이 여러번 찾기를 시도하다가, 사전파일에 값이 있으면 문제를 풀고 종료합니다.

dictionary_시연

2. Rainbow Table

이번에는 레인보우 테이블을 이용해서 문제를 풀어 보겠습니다.

레인보우 테이블의 개념

레인보우 테이블에서의 핵심 원리는 CPU 연산을 조금 더 해서 저장 공간을 줄이겠다는 아이디어입니다. 본 문제에서는 제시한 Input의 크기가 1억개 밖에 안되기 때문에 파일의 크기가 사전파일로 전부 구해봐야 5기가 정도 수준밖에 안됩니다. 하지만 현실세계에서는 몇 천기가, 테라바이트를 넘어갈 것이기 때문에 비용적인 면에서 천문학적인 비용이 듭니다. 이러한 경우에 저장공간에 제약에 막히기 때문에 저장공간을 줄이기 위한 기법이 레이보우 테이블입니다. 작동방식을 이해하기 위해 다음 그림으로 예시를 들어 보겠습니다.

아래 그림이 해시 테이블을 생성하는 과정입니다.

image

  1. 먼저 주어진 input에 대해서 해시 연산을 한다.
  2. 나온 해시값에서 앞에서 부터 숫자 8개를 추출하여 다시 Input을 만든다. [이러한 기능을 하는 함수를 축소 함수라고 부른다.]
  3. 다시 해시를 한다.
  4. 다시 축소 함수로 input을 만든다.
  5. 그리고 마지막 해시 값을 저장한다.

위의 예제는 길이가 3짜리 해시 체인을 만든 것입니다. 레인보우 테이블은 이렇게 해서 만든 해시 체인에서 처음 인풋 10000000과 마지막 해시 결과값인 03fdc73b6667a6dc7d5609020ee9d190a407ee9c 값만 저장하는 것입니다.

그러면 마지막 값만 저장되어 있는 레인보우 테이블에서 해시값은 어떻게 찾는 것인지 보여드리겠습니다.

위의 해시 체인은 3개의 해시 값을 구할 수 있습니다. 각각의 해시 값을 구하는 과정은 다음과 같습니다.

1. 03fdc73b6667a6dc7d5609020ee9d190a407ee9c 값의 input 구하기

  • 1.1 레인보우 테이블에서 해시 값이 있는지 검색 -> 해시 값이 있다.
  • 1.2 레인보우 테이블에서 해시 값이 있다면 해당 체인의 시작점인 10000000으로부터 다시 해시 체인을 생성하기
  • 1.3 해시 체인에서 원하는 해시값을 만드는 input을 찾기 image

2. 3be59ab41a504142932e7b0f6e6144a3535f54c7 해시 값의 input 구하기

  • 1.1 레인보우 테이블에서 해시 값이 있는지 검색 -> 해시 값이 없다.
  • 1.2 해당 해시 값을 축소 함수 및 해시 함수로 한번 더 구하고 다시 비교를 한다.
  • 1.3 해시 값이 파일에 있으므로 해당 체인의 시작점인 10000000으로부터 다시 해시 체인을 생성한다.
  • 1.4 해시 체인에서 원하는 해시 3be59ab41a504142932e7b0f6e6144a3535f54c7 를 만드는 input인 41381625값을 찾을 수 있다. image

위의 예시를 보면 알겠지만 이렇게 해시 체인을 통해서 찾는 과정에서 해시 체인을 추가적으로 만드는 연산이 추가되었지만, 저장하는 공간은 체인의 길이가 3 이므로 하나의 결과값에 3개의 해시 값이 저장이 됩니다. 따라서 공간의 크기는 1/3로 줄어들었다고 볼 수 있습니다.

이렇게 해서 문제에서 주어진 10000000 부터 시작해서 해시 체인을 만든다면 아래 그림처럼 만들어 지며, 파일에는 처음 시작 input과 마지막 해시 값만 저장하면 됩니다.

image

추가

  • 궁금해 하실 분이 있을것 같아서 부연 설명을 좀 적어 보자면, Reduce Function의 전제 조건은 다음 해시 값으로 들어가는 input을 만드는 함수입니다. 따라서 본 문제에서는 해시 값의 input 정의역이 10000000 ~ 99999999 이므로 숫자 8자리입니다. 즉 해시 값으로부터 reduce function을 통해서 나온 결과 값은 저 범위에 있는 input이 나오기만 하면 되는 것입니다. 그래서 저는 해시 값에서 앞에 8자리의 숫자를 뽑아서 다음 input으로 만들었는데 누군가는 뒤에 8자리 혹은 다른 로직을 통해서 숫자 8자리가 나오기만 하면 상관은 없습니다.

  • 그리고 본 포스팅 내용이 너무 길어질 것 같아서 적진 않겠지만 해시 체인에서는 충돌이 발생하는 경우가 생깁니다. 저는 코드 상에서 충돌이 발생하는 경우는 그냥 통과하도록 코드를 짰습니다.

Make_Rainbow_table

아래는 rainbow 테이블을 만드는 전체 소스 코드입니다.

reduce_function은 아래처럼 숫자를 모두 추출한다음 처음 8자리를 반환하도록 기능을 구현했습니다.

  def reduce_function(hash):
    numbers = re.findall("\d",hash)
    for i in range(8):
        next_plain_number +=numbers[i]
    return int(next_plain_number)

레인보우 테이블을 만들기 위한 해시 체인을 만드는 함수는 다음처럼 100번을 hash,reduce를 반복해서 나온 해시 값을 결과로 반환하도록 기능을 구현했습니다.

 def make_hash_chain(number):
    # 반환값은 [start,end] 로 한다.
    plain_number = number
    for i in range(100):
        hash_value = sha1_500(str(plain_number) + SALT)
        plain_number = reduce_function(hash_value)
    return hash_value

rainbow_table 결과 값은 다음과 같이 구성되었으며, 사전 파일은 1000만개의 열이 생성된 반면, 레인보우 테이블은 체인의 길이를 100으로 설정 했기 때문에 비슷한 범위의 해시 값을 커버 하지만 값을 10만개로 충분합니다.

 10000000:9d5c178303e59cc8e1266f088f54db1333164a38
 10000001:fac92fc681904515285d6856707b566e0c961116
 10000002:b9d75ef1ef20f0f770ade1d8504e98ee0a43c9af
 10000003:44b59a1c3b0479a6fcad91c4f69a5348f2cc7d1c
 10000004:c8628b1c8d5288ffe49a7889ff36e6c69c9a78bb
 10000005:0aa4a375bef19361d34fff0a34b936209bc64485
 10000006:267f111d681c9421f2b229951636b2fa2b94ec61

 ... 10만개의 열
 10099996:dc2b1e9d6a9a6533c330b611cbdefccc9fdc1113
 10099997:e0573482c0af2a39158276e6f5ec0189febdefd7
 10099998:364300f3e1d4afc049a4653d1da7f119daa50a26
 10099999:7fc430e88242f2179e21ff21d43eb96bd2720fc7

Search_Rainbow_table

아래 소스 코드는 레인보우 테이블에서 해시 값을 찾는 로직입니다. Search_Dictionary 코드와 비교해 보면 알겠지만, 사전 파일에서는 그냥 해당 해시 값이 있는지 find만 하면 되지만 레인보우 테이블에서는 해시 체인을 다 만들어보고 비교를 하면서 연산 값이 훨씬 많아졌습니다.

사전 파일에서 찾는 방식과 동일하게 사이트에서 해시 값을 불러오고, 레인보우 테이블에서 검색을 한 후 해당 해시값이 없으면 사이트에서 다시 불러오는 것을 자동화 하는 기능까지 구현하였습니다.

아래 그림은 코드를 실행했을 때의 결과입니다.

rainbow_시연

비교

Dictionary 방식과 Rainbow Table 방식을 비교해 보면 다음과 같은 결과가 나왔습니다.

방식 파일의 크기 파일 생성에 걸리는 시간 해시값을 찾는데 걸리는 시간
Dictionary_file 500MB 1시간 평균 : 0.15초
Rainbow_table 5MB 1시간 평균: 0.5초

결과를 보면 왜 Rainbow_table을 이용해야 하는지 확실하게 알 수 있습니다. 개념을 설명할 땐, 시간을 조금 더 소비해서 공간을 확보한다(Time/Space Tradeoff)라고 했는데 실제로 코드를 돌려보니 코드상에서 사전파일 방식도 메모리에 너무 많은 데이터[1000만개]를 올리고 서칭을 하다보니 생각보다 시간이 많이 걸렸습니다.

결국 위 문제는 Rainbow Table방식으로 풀면 파일 크기는 무려 1/100로 감소 시켰지만 해당 파일에서 찾기를 하는데 걸리는 시간은 3배 정도 밖에 더 걸리지 않고, 이 마저도 0.2~0.3초 수준이기 때문에 체감이 되는 정도가 아니었습니다.

평소 레인보우 테이블에 대한 내용을 이론적으로만 알고 있었는데, 이를 코드로 구현해보고 결과를 내보니 확실하게 개념을 잡을 수 있었던 문제 였던것 같습니다.

댓글남기기

참고