Defcon23 (2015) blackbox (misc 2) writeup (KR)

English: Link

서버에 접속하면 "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789!"#$%&'()*+,-./:;<=>?@[\]^_`{|}~ "의 95Byte 문자열 안에서 암호화가 이루어집니다. 아무 문자열이나 보내면 입력한 문자열에 대한 암호문이 주어지고, 해독해야하는 암호문이 주어집니다. 즉 코드를 알 수 없는 blackbox에서 chosen plaintext attack을 해야하는 문제입니다.

1단계는 간단합니다. ABC를 보내면 def 등으로 암호화되는데, key는 매번 달라집니다.

ABC

Password [def]\tExpected [????]

평문을 \(x_0, x_1, ..., x_n\), 암호문을 \(y_0, y_1, ..., y_n\)이라고 하면 암호화 방식은 다음과 같습니다. (모든 연산은 modulus 95(가능한문자열들)로 이루어집니다.)

\[y_n = x_n + \text{key}\]

2단계부터는 살짝 복잡해집니다.

ABCDEFG

Password [ABDHPF"]\tExpected [????]

ABBBBBB

Password [BDGMYwB]\tExpected [????]

똑같은 암호를 보내면 똑같은 암호문이 오는 것으로 보아 달라지는 key는 없습니다.

잘 살펴보면 다음과 같이 암호화되는 것을 알 수 있습니다.

\[ y_n = \begin{cases} x_0 & \text{if } n=0 \cr x_n + \sum \limits_{i=0}^{n-1} y_i & \text{if } n\ge 1 \end{cases} \]

3단계입니다.

AA

Password [Ad]\tExpected [????]

ACCCC

Password [Af8`X]\tExpected [????]

같은 문자열을 보내도 암호문이 같지 않습니다. 다음 식으로 암호화됩니다.

\[ y_n = \begin{cases} x_0 & \text{if } n=0 \cr \text{key}+x_n-x_{n-1} & \text{if } n\ge 1 \end{cases} \]

4단계입니다.

Stage 4.

QWERQWER

Password [Zl}@+k{<]\tExpected [????]

n이 문자열의 길이일 때,

\[ y_i = \begin{cases} \text{?} & \text{if } i=0 \cr 2\times y_{i-1}-(x_{n-i}-x_{n-i-1}) & \text{if } i\ge 1 \end{cases} \]

즉

P: 16 22 04 17 16 22 04 17

C: 25 37 92 83 72 36 90 79

\( y_1 = 2\times y_0 - (x_7-x_6) = 2\times 25-(17-04) = 37\)

\( y_2 = 2\times y_1 - (x_6-x_5) = 2\times 37-(04-22) = 92\)

이 됩니다.

첫 글자가 어떻게 암호화/복호화되는지는 알아내지 못해서 첫 글자를 하나씩 다 대입해보면서 문자열을 암호화해봤습니다.

5단계입니다. 4, 5단계 푸는데 합쳐서 3시간정도 걸린 것 같네요...

5단계를 알아낸 다음에는 어이없음과 허탈한 느낌이었어요.

A

Password [Z]\tExpected [????]

AA

Password [a1]\tExpected [????]

AAA

Password [AdL]\tExpected [????]

첫 A를 암호화했을 때 Z가 나왔는데 두 번째에서는 a가 됩니다. 따라서 이는 block cipher일 것이라고 생각을 했어요.

몇 가지를 더 시도해본 뒤 블록이 4글자정도일 것이라고 추측했습니다.

AAAAAAAAAAAAAAAA

Password [d7xYEJnT<#((is`-[]\tExpected [????]

이를 숫자로 표현하면 다음과 같습니다.

P: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 

C: 29 59 49 24 04 09 39 19 79 64 69 34 44 89 74 84

\(y_0\)와 \(y_1\)의 관계는 \(y_1=2\times y_0+1\)로 표현됩니다. 그런데 그 뒤로는 전혀 엉뚱한 것이 나오죠.

이는 Permutation이 이루어진 것입니다. 4개의 블록 안에서 3번째와 4번째의 위치가 서로 바뀐 것이죠.

다시 3번째와 4번째를 바꾸면 다음과 같습니다.

C': 29 59 24 49 04 09 19 39 79 64 34 69 44 89 84 74

이렇게 보면 \(y_n=2\times y_{n-1}+1\)임이 확실해지죠.

다른 문자열은 어떻게 되는지 살펴봅시다.

ABCD

Password [2P%g]\tExpected [????]

P: 00 01 02 03

C: 54 15 66 32

C': 54 15 32 66

모두 \(y_n=2\times y_{n-1}+2\)임을 알 수 있습니다.

따라서 일반화를 하면 다음과 같습니다.

C를 4Byte씩의 Block으로 나눈 뒤 3번째와 4번째를 바꾼 C'의 수열에서

\[ y_n = \begin{cases} \text{?} & \text{if } n=0 \cr 2\times y_{n-1} +1 + (x_n-x_{n-1}) & \text{if } n\ge 1 \end{cases} \]

이것도 첫 글자를 모르기 때문에 첫 글자를 바꿔가며 복호화했습니다.

마지막 Exptected [sI~Od$5Z?KBfUw|n7R&P5{\a;D{| 7p"h=K=)5`hH`-[6W]를 복호화하면 다음 문자열이 나옵니다.

The flag is: Gr3aT j0b! BlackBox Ma$Ter$@!!!%%

코드는 다음과 같습니다.

3단계까지는 하나에 짜고 그 다음부터는 테스트해본다음 원래코드에 붙여넣은거라 코드가 난잡합니다..

from socket import *
import re
import telnetlib

s = socket(2,1)
s.connect(('blackbox_ced7f267475a0299446fa86c26d77161.quals.shallweplayaga.me', 18324))
s.recv(1024) # you need to ~
print s.recv(1024)

#level 1
s.send('ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz\n')
tmp = s.recv(1024)
pat = re.compile("Password \[(.+)\]\tExpected \[(.+)\]")
pw1, expected = re.findall(pat, tmp)[0]

s.send('''0123456789!"#$%&'()*+,-./:;<=>?@[\]^_`{|}~ \n''')
tmp = s.recv(1024)
pw2 = re.findall(pat, tmp)[0][0]

pw = pw1+pw2
d={}
allchars = '''ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789!"#$%&'()*+,-./:;<=>?@[\]^_`{|}~ '''
p = ''
for i in expected:
    p += allchars[pw.index(i)]
print 'PASSWORD:',p
s.send(p+'\n')

s.recv(1024)
s.recv(1024)

#level 2
#s.send('ABCDEFGHIJKLMNOPQRSTUVWXYZ'+'\n')
s.send('a'+'\n')
tmp = s.recv(1024)
print tmp
pw1, expected= re.findall(pat, tmp)[0]

pw=''
smallsum = 0

for i in expected:
    pw += allchars[(allchars.index(i)-smallsum)%len(allchars)]
    smallsum += allchars.index(i)
print 'PW=',pw
s.send(pw+'\n')
s.recv(1024)

#level 3
print s.recv(1024)
s.send('ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz\n')
tmp = s.recv(1024)
pw1, expected = re.findall(pat, tmp)[0]

s.send('''0123456789!"#$%&'()*+,-./:;<=>?@[\]^_`{|}~ \n''')
tmp = s.recv(1024)
pw2 = re.findall(pat, tmp)[0][0]

pw = pw1[::-1]+pw2[::-1]
p = ''
for i in expected:
    p += allchars[pw.index(i)]
p=p[::-1]
print 'PASSWORD:',p
s.send(p+'\n')
s.recv(1024)
print s.recv(1024)

s.send('AA\n')
tmp = s.recv(1024)
pw1, expected = re.findall(pat, tmp)[0]

key = allchars.index(pw1[1])-allchars.index(pw1[0])
k = ''
for n,i in enumerate(expected):
    if not k: k += i
    else: k += allchars[(allchars.index(i) - allchars.index(expected[n-1]) + allchars.index(k[-1]) -key)%len(allchars)]
print 'PW=',k
s.send(k+'\n')
s.recv(1024)
s.recv(1024)

#level 5
s.send('A\n')
tmp = s.recv(1024)
pw1, expected = re.findall(pat, tmp)[0]
def do(key, expected):
    k = ''
    t = []
    for i in expected:
        t.append((allchars.index(i)*2)%len(allchars))
    r = []
    for i,j in zip(t, expected[1:]):
        r.append(i-allchars.index(j))

    k += allchars[(allchars.index(expected[0])-key)%len(allchars)]
    for i in r[::-1]:
        k += allchars[(allchars.index(k[-1])+i)%len(allchars)]
    return k

for key in range(95):
    aaaaa555=do(key,expected)
    if ' ' in aaaaa555:
        print key, aaaaa555
key = input('Please chose key:')
k = do(key, expected)
s.send(k+'\n')

print s.recv(1024)
print s.recv(1024)

tc = telnetlib.Telnet()
tc.sock = s
tc.interact()