문제는 파이썬 소스코드가 주어진다.
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
|
import md5
def encode(input_string):
print input_string
h = md5.md5(input_string[:4]).hexdigest()
table = {
'a': 1,
'b': 2,
'c': 3,
'd': 4,
'e': 5,
'f': 6,
'g': 7,
'h': 8,
'i': 9,
'j': 0
}
out = ""
prev = ""
stage1 = []
stage2 = []
stage3 = ""
passbyte = -1
for ch in input_string:
if ch in table.keys():
stage1.append(table[ch])
else:
stage1.append(ch)
for index, ch in enumerate(stage1):
if len(stage1) <= index+1:
if index != passbyte:
stage2.append(ch)
break
if passbyte != -1 and passbyte == index:
continue
if type(ch) == int and type(stage1[index+1])==int:
tmp = ch << 4
tmp |= stage1[index+1]
stage2.append(tmp)
passbyte = index+1
else:
stage2.append(ch)
for ch in stage2:
if type(ch) == int:
stage3 += chr(ch)
else:
stage3 += ch
for index, ch in enumerate(stage3):
if index >= len(h):
choice = 0
else:
choice = index
out += chr(ord(ch) ^ ord(h[choice]))
print repr(out)
encoded = "~u/\x15mK\x11N`[^\x13E2JKj0K;3^D3\x18\x15g\xbc\\Gb\x14T\x19E"
encode(st)
|
cs |
코드는 암호문이 있으며 그에 상응하는 평문을 찾아내야 하는 문제이다. stage3개로 나뉘어 있으며 각 부분을 분석해야 한다.
1. Stage 1
stage1은 간단하다. 소스코드 내에 존재하는 table에서 1:1 치환을 해 준다. a~j까지만 존재하며 이 값을 1~90으로 변환을 시킨다. 문자열이 아닌 숫자라는 점을 유의해야 한다.
'a' -> 1 != '1'
2. Stage 2
stage2는 현재 작업하려는 문자가 숫자인 경우, 즉 stage1에서 치환된 문자에 대해서만 작업을 한다. 단, 다음 문자도 숫자여야 한다는 조건이 걸린다.
그러면 현재 문자는 shift left 4 연산을 하고 or 연산으로 다음에 올 문자열과 연산을 한다. 간단히 말하면, 4비트씩 이어 붙이는 것이다.
예를 들어 input값이 'ab'였을 경우, a -> 1, b -> 2가 된다. 1<<4를 하게 되면 10000이 되고, 여기에 or 2연산을 하게 되면 10010이 되는 것이다.
따라서 복호화 할 때 그냥 4비트씩 끊어서 연산을 하면 된다 라고 생각하면 쉽다.
3. Stage 3
Stage3은 그냥 숫자인 경우 문자로 치환해 주는 정도이다.
3개의 Stage 연산이 끝나면 마지막으로 처음에 생성한 해쉬값과 xor 연산을 진행한다. 단, 해쉬값은 input_string의 앞 4자리만 사용하게 된다. 해서 이 값을 먼저 유추해야 한다. 처음에는 brute force로 찾아내 볼까 했는데, 4자리라고 해도 시간적으로 별로 효율적이지 못해서 다른 방법을 찾아보았는데, 소스코드상 취약한 부분이 존재하였다.
해쉬값과 xor하는 전 부분을 보면 choice를 설정하는 부분이 있다. 여기서 현재 index의 숫자값이 해쉬의 길이보다 크면 0으로 셋팅하게 되어 있다.
md5 해쉬의 경우 길이는 32바이트이다. 하지만 암호문의 길이는 35바이트로, 뒤에서 3자리는 무조건 해쉬의 0번째 인덱스와 xor연산을 하는 것이다. 동일 키로 xor하는 것과 같다. 해서 먼저 이 값을 기준으로 알아내 보기로 하였다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
|
>>> table = list("abcdef0123456789")
>>>
>>> ax = 126
>>> bx = 84
>>> cx = 25
>>> dx = 69
>>>
>>> for i in table:
... a = ax ^ ord(i)
... b = bx ^ ord(i)
... c = cx ^ ord(i)
... d = dx ^ ord(i)
... print chr(a),chr(b),chr(c),chr(d),i
...
|
cs |
결과
5 x $ a
6 { ' b
7 z & c
0 } ! d
1 | e
2 # f
N d ) u 0
O e ( t 1
L f + w 2
M g * v 3
J ` - q 4
K a , p 5
H b / s 6
I c . r 7
F l ! } 8
G m | 9
>>>
x는 해쉬의 1번째 값이고, 각각 a는 평문의 첫번째, b,c,d는 평문 마지막의 3자리를 의미한다. ax는 평문[0] ^ hash[0], bx는 평문[-3] ^ hash[0]을 의미하는 것이다.
위에서 보면 첫 번째 문자가 F이며 마지막 문자가 }인 형태가 보인다. 보통 'Flag{correct}'와 같은 형태가 많이 존재하기 때문에 이 값이 맞다는 가정 하에 진행을 하였다. 또한, 첫 문자가 F라면, Flag, FLAG 등과 같은 문자열이라는 판단 하에 Fl, FL을 넣어놓고 나머지는 brute force를 돌리는 방법을 사용했다.
그 결과 해쉬 연산에 사용되는 평문 앞 4자리는 FLag라는 것을 알아냈다. 이제 이에 상응하는 부분만 맞추어 주면 된다. 소스 분석에 조금만 시간을 쓰면 되는 부분이다.
사용한 소스코드는 다음과 같다.
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
|
import hashlib
q_table = {
1:'a',
2:'b',
3:'c',
4:'d',
5:'e',
6:'f',
7:'g',
8:'h',
9:'i',
0:'j'
}
table="abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ_{}! "
h = hashlib.md5("FLag").hexdigest()
encoded = "~u/\x15mK\x11N`[^\x13E2JKj0K;3^D3\x18\x15g\xbc\\Gb\x14T\x19E"
out = ""
for index, ch in enumerate(encoded):
if index >= len(h):
choice = 0
else:
choice = index
chk = ord(ch)^ord(h[choice])
if chr(chk) not in table:
t = q_table[chk>>4]
if t != 'j':
out += t
out += q_table[chk&15]
else:
out += chr(chk)
print out
|
cs |
flag : FLag is {compress_is_always_helpful!}
'CTF | wargame' 카테고리의 다른 글
| xcz.kr / Rendzvous (패킷 분석, 알수없는 패킷 데이터 찾기) (0) | 2017.03.27 |
|---|---|
| 0ctf 2017 / integrity (AES_CBC IV취약점) (0) | 2017.03.21 |
| codegate 2016 / cryptinthe3sh3ll (프로그램 리소스 사용, [FindResource-SizeofResource-LoadResource-LockResource]) (0) | 2017.03.16 |
| insomnihack 16 - cryptoquizz - crypto (구글 검색 파싱) (0) | 2017.03.11 |
| Alexctf / usb probing (usb 패킷 분석 (0) | 2017.03.11 |