티스토리 뷰

최종 수정: 2015-11-08

hackability@TenDollar


안녕하세요. Hackability 입니다.


이번에 포스팅 할 내용은 2015 School CTF 의 Reverse 200 문제 입니다.


문제에서는 C 파일을 하나 제공해줍니다.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
#include <stdlib.h>
#include <stdio.h>
#include <pthread.h>
 
#define FLAG_LEN 20
 
void * checking(void *arg) {
    char *result = malloc(sizeof(char));
    char *argument = (char *)arg;
    *result = (argument[0]+argument[1]) ^ argument[2];
    return result;
}
 
int highly_optimized_parallel_comparsion(char *user_string)
{
    int initialization_number;
    int i;
    char generated_string[FLAG_LEN + 1];
    generated_string[FLAG_LEN] = '\0';
 
    while ((initialization_number = random()) >= 64);
    
    int first_letter;
    first_letter = (initialization_number % 26+ 97;
 
    pthread_t thread[FLAG_LEN];
    char differences[FLAG_LEN] = {09-9-113-13-4-11-9-1-76-131339-13-116-7};
    char *arguments[20];
    for (i = 0; i < FLAG_LEN; i++) {
        arguments[i] = (char *)malloc(3*sizeof(char));
        arguments[i][0= first_letter;
        arguments[i][1= differences[i];
        arguments[i][2= user_string[i];
 
        pthread_create((pthread_t*)(thread+i), NULL, checking, arguments[i]);
    }
 
    void *result;
    int just_a_string[FLAG_LEN] = {11511611497110103101951151161141051101039510511695105115};
    for (i = 0; i < FLAG_LEN; i++) {
        pthread_join(*(thread+i), &result);
        generated_string[i] = *(char *)result + just_a_string[i];
        free(result);
        free(arguments[i]);
    }
 
    int is_ok = 1;
    for (i = 0; i < FLAG_LEN; i++) {
        if (generated_string[i] != just_a_string[i])
            return 0;
    }
 
    return 1;
}
 
int main()
{
    char *user_string = (char *)calloc(FLAG_LEN+1sizeof(char));
    fgets(user_string, FLAG_LEN+1, stdin);
    int is_ok = highly_optimized_parallel_comparsion(user_string);
    if (is_ok)
        printf("You win!\n");
    else
        printf("Wrong!\n");
    return 0;
}
cs

요약하면 사용자가 20글자를 입력하는데 스레드가 20개 생성되면서 각 위치별로 문자를 연산하게 됩니다. 그리고 연산된 문자가 just_a_string 변수의 문자열 처럼 되면 정답이 되는 문제입니다.
(2014 코드게이트 Reverse 250, Clone Technique 이라는 유형과 비슷합니다.)

중요한건 사용자 입력 값과 연산을 하는 스레드 연산 내용입니다.

checking 함수 중

result = (argument[0] + argument[1]) ^ argument[2];

를 하게 되는데 소스코드를 잘 보면 arg[0] 은 소문자 a ~ z 중에 한개 값이고 arg[1]은 differences 배열이고 arg[2] 는 사용자 입력 값 입니다. 그 뒤를 보게 되면 result 된 값들 (배열)과 just_a_string 배열을 더해서 generated_string 이라는 걸 만들게 되는데 이 배열이 just_a_string 배열과 동일한지 확인하는게 문제 입니다. 따라서 위 리버싱 코드를 아래와 같이 식으로 만들 수 있습니다.

처음 랜덤하게 생성되는 문자 1개 = first_letter 변수 = W
differences 배열 = differences 변수 = X 배열
사용자 입력 = user_string 변수 = Y 배열
마지막 비교 문자 = just_a_string 변수 Z 배열

이라고 한다면 우리가 구하고자 하는 식은 다음과 같습니다.

(W + X[i]) ^ Y[i] + Z[i] = Z[i], i = 0 ~ 19

양변에 Z[i] 가 동일하므로 빼주면

(W + X[i]) ^ Y[i] = 0

Y[i]를 우변으로 이동시키면

(W + X[i]) = Y[i]

위에 잘 보면 Y 는 사용자 입력 값인데 알파벳과 X[i] xor 한 값과 동일합니다.

그러면 우리가 해 줄건 differences 배열과 문자 a 부터 z 까지 한번씩 다 xor 을 해서 정상적인 ascii 문자대역으로 나오는 스트링을 찾으면 그것이 우리의 입력이 될 것 입니다.

위 내용을 python 코드로 구현 하면 다음과 같습니다.

1
2
3
4
5
6
7
diff  = [09-9-113-13-4-11-9-1-76-131339-13-116-7]
match = [11511611497110103101951151161141051101039510511695105115]
 
for i in range(9797+26):
    for j in range(020):
        print chr(i + diff[j]), 
    print 
cs

결과는 다음과 같습니다.

a j X ` n T ] V X ` Z g T n d j T V g Z
b k Y a o U ^ W Y a [ h U o e k U W h [
c l Z b p V _ X Z b \ i V p f l V X i \
d m [ c q W ` Y [ c ] j W q g m W Y j ]
e n \ d r X a Z \ d ^ k X r h n X Z k ^
f o ] e s Y b [ ] e _ l Y s i o Y [ l _
g p ^ f t Z c \ ^ f ` m Z t j p Z \ m `
h q _ g u [ d ] _ g a n [ u k q [ ] n a
i r ` h v \ e ^ ` h b o \ v l r \ ^ o b
j s a i w ] f _ a i c p ] w m s ] _ p c
k t b j x ^ g ` b j d q ^ x n t ^ ` q d
l u c k y _ h a c k e r _ y o u _ a r e  <-- 요놈이 플래그
m v d l z ` i b d l f s ` z p v ` b s f
n w e m { a j c e m g t a { q w a c t g
o x f n | b k d f n h u b | r x b d u h
p y g o } c l e g o i v c } s y c e v i
q z h p ~ d m f h p j w d ~ t z d f w j
r { i q e n g i q k x e u { e g x k
s | j[Decode error - output not utf-8]
[Decode error - output not utf-8]
u ~ l t [Decode error - output not utf-8]
x [Decode error - output not utf-8]
m u[Decode error - output not utf-8]
[Decode error - output not utf-8]
[Decode error - output not utf-8]
[Decode error - output not utf-8]
[Decode error - output not utf-8]
[Decode error - output not utf-8]
[Decode error - output not utf-8]
l n r
z [Decode error - output not utf-8]
q y[Decode error - output not utf-8]
[Decode error - output not utf-8]
[Decode error - output not utf-8]


댓글
  • 프로필사진 ㅁㄴㅇ 감사합니다 잘봤습니다
    옛날 포스팅에 지금 답변을 요구하는 것이 조금은 죄송하지만
    (W+ X[i]) ^ Y[i] 에서 XOR을 무시하고 Y[i]를 우항으로 옮기나요?
    2017.09.14 01:59 신고
  • 프로필사진 hackability 양변에 Y[i]를 xor 을 해줫습니다 :)

    (W + X[i]) ^ Y[i] = 0
    (W + X[i]) ^ Y[i] ^Y[i] = 0 ^ Y[i]
    W + X[i] = Y[i]
    2017.09.14 12:52 신고
댓글쓰기 폼