유메의 티스토리

English: Link

서버에 접속하면 레지스터의 값들과 이상한 문자열이 주어집니다.

오는 문자열을 hex encode해보면 모두 c3으로 끝나는데, 이는 x64에서 retq 명령어입니다. 따라서 저 assembly코드를 실행한 뒤, 레지스터의 값들을 같은 형태로 반환해주면 됩니다.

python으로 어셈블리어를 실행하기는 힘드므로 python으로 socket통신을 해서 레지스터 초기값을 받은 뒤 subprocess를 이용해 C언어로 컴파일한 바이너리를 이용합시다.

C에서

register unsigned long long rax asm("rax");

로 rax변수를 선언하면 rax 레지스터의 값에 접근할 수 있습니다.

전해받은 assembly어를 code배열에 넣은 뒤 이를 실행합시다.

#include <stdio.h>
#include <stdlib.h>

int main(int argc, char *argv[]) {
    void (*f)();
    register unsigned long long rax asm("rax");
    register unsigned long long rbx asm("rbx");
    register unsigned long long rcx asm("rcx");
    register unsigned long long rdx asm("rdx");
    register unsigned long long rsi asm("rsi");
    register unsigned long long rdi asm("rdi");
    register unsigned long long r8 asm("r8");
    register unsigned long long r9 asm("r9");
    register unsigned long long r10 asm("r10");
    register unsigned long long r11 asm("r11");
    register unsigned long long r12 asm("r12");
    register unsigned long long r13 asm("r13");
    register unsigned long long r14 asm("r14");
    register unsigned long long r15 asm("r15");

    unsigned long long _rax=0,_rbx=0,_rcx=0,_rdx=0,_rsi=0,_rdi=0,_r8=0,_r9=0,_r10=0,_r11=0,_r12=0,_r13=0,_r14=0,_r15=0;
    unsigned char code[1024]={0,};
    unsigned char tmp[3]={0,};
    int tmp2=0;

    if(argc<17) { printf("nope\n"); return 0; }

    int i;
    // hex encode된 명령어 code에 넣기
    for(i=0; i<atoi(argv[1]); i++) {
        memcpy(tmp, argv[16]+i*2, 2);
        tmp2=strtol(tmp, &tmp, 16);
        code[i]=tmp2;
    }
    _rax =strtoll(argv[2], 0, 16);
    _rbx =strtoll(argv[3], 0, 16);
    _rcx =strtoll(argv[4], 0, 16);
    _rdx =strtoll(argv[5], 0, 16);
    _rsi =strtoll(argv[6], 0, 16);
    _rdi =strtoll(argv[7], 0, 16);
    _r8  =strtoll(argv[8], 0, 16);
    _r9  =strtoll(argv[9], 0, 16);
    _r10=strtoll(argv[10], 0, 16);
    _r11=strtoll(argv[11], 0, 16);
    _r12=strtoll(argv[12], 0, 16);
    _r13=strtoll(argv[13], 0, 16);
    _r14=strtoll(argv[14], 0, 16);
    _r15=strtoll(argv[15], 0, 16);

    f=(void *)code;

    rax=_rax;rbx=_rbx;rcx=_rcx;rdx=_rdx;
    rsi=_rsi;rdi=_rdi;r8=_r8;r9=_r9;
    r10=_r10;r11=_r11;r12=_r12;r13=_r13;
    r14=_r14;r15=_r15;

// f의 위치: rbp-0xb8
    asm volatile(
        "call -0xb8(%rbp)\n\t"
    );
    _rax=rax;_rbx=rbx;_rcx=rcx;_rdx=rdx;
    _rsi=rsi;_rdi=rdi;_r8=r8;_r9=r9;
    _r10=r10;_r11=r11;_r12=r12;_r13=r13;
    _r14=r14;_r15=r15;
    printf("rax=0x%llx\n", _rax);
    printf("rbx=0x%llx\n", _rbx);
    printf("rcx=0x%llx\n", _rcx);
    printf("rdx=0x%llx\n", _rdx);
    printf("rsi=0x%llx\n", _rsi);
    printf("rdi=0x%llx\n", _rdi);
    printf("r8=0x%llx\n",  _r8);
    printf("r9=0x%llx\n",  _r9);
    printf("r10=0x%llx\n", _r10);
    printf("r11=0x%llx\n", _r11);
    printf("r12=0x%llx\n", _r12);
    printf("r13=0x%llx\n", _r13);
    printf("r14=0x%llx\n", _r14);
    printf("r15=0x%llx", _r15);
    return 0;
}

여기서 f()로 호출하면 컴파일러가 rax에 f의 주소를 넣고 call *%rax의 형태로 바뀌어서 rax값을 보존하기 위해 call 어셈블리를 inline으로 직접 넣었습니다. rbp-0xb8은 한번 컴파일을 해본 뒤 f가 어디에있는지 직접 찾아서 넣은 것입니다. f를 직접 호출하려고했는데 inline assembly와 C언어 변수간의 호환이 어렵더군요...

컴파일 할 때는 stack을 실행해야하므로 다음과같이 컴파일합니다.

gcc -o catwestern catwestern.c -z execstack -fno-stack-protector -g

그런 뒤 python wrapper로 인자를 맞춰서 전달해주면 됩니다.

from socket import *

s = socket(2,1)
s.connect(('catwestern_631d7907670909fc4df2defc13f2057c.quals.shallweplayaga.me',9999))
reg = s.recv(2048)

print reg
reg = reg.split('\n')[1:]
for i in reg:
    exec i

a = s.recv(2048)
print a
a = a.split('\n')
a = '\n'.join(a[2:])
print 'LENGTH:', len(a)

regs = [rax,rbx,rcx,rdx,rsi,rdi,r8,r9,r10,r11,r12,r13,r14,r15]
for n,i in enumerate(regs):
    if i>0x7fffffffffffffff:
        regs[n] = -(0xffffffffffffffff-i+1)
cmd=('./catwestern %d ' +'%x '*14+ '%s')%(len(a),
    regs[0],regs[1],regs[2],regs[3],regs[4],
    regs[5],regs[6],regs[7],regs[8],regs[9],
    regs[10],regs[11],regs[12],regs[13],a.encode('hex'))

import subprocess
print cmd
t = subprocess.check_output(cmd, shell=True)

for i in t.split('\n'):
    exec i

ans = '''rax=0x%x
rbx=0x%x
rcx=0x%x
rdx=0x%x
rsi=0x%x
rdi=0x%x
r8=0x%x
r9=0x%x
r10=0x%x
r11=0x%x
r12=0x%x
r13=0x%x
r14=0x%x
r15=0x%x
''' % (rax,rbx,rcx,rdx,rsi,rdi,r8,r9,r10,r11,r12,r13,r14,r15)
print ans
s.send(ans)
print s.recv(2048)

Flag: Cats with frickin lazer beamz on top of their heads!

한국어(Korean): Link

Encryption is done in 95Byte string of "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789!"#$%&'()*+,-./:;<=>?@[\]^_`{|}~ ". You send any string and it shows the string encrypted. It means we'll have to do chosen plaintext attack in blackbox.

Stage 1 is simple. You send strings like "ABC" and it is encrypted as "def", and key is different every time.

ABC

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

Let's say plaintext is \(x_0, x_1, ..., x_n\) and ciphertext is \(y_0, y_1, ..., y_n\) then encryption method is as follows: (All the operations are done in modulus 95, the number of characters available)

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

Stage 2 it gets a little more complex.

ABCDEFG

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

ABBBBBB

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

Since same plaintexts are encrypted as same ciphertext, there is no key. Looking into it, you can find the encryption method:

\[ 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} \]

Stage 3.

AA

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

ACCCC

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

Same plaintexts are not encrypted the same. Encryption method is:

\[ 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} \]

Stage 4.

QWERQWER

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

\(n\) being the length of string,

\[ 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} \]

That is,

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\)

I could not find out how the first character is encrypted, so I tried all 95 characters and chose one that made sense.

Stage 5. It took nearly 3 hours solving stage 4 and 5 alone.

A

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

AA

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

AAA

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

Encrypting the first character 'A' solely resulted in 'Z', but with the second character it became 'a'. So I thought it was block cipher.

I tried a couple of things and assumed the size of block is 4.

AAAAAAAAAAAAAAAA

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

Writing these in numbers:

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

The relationship between \(y_0\) and \(y_1\) can be defined as \(y_1=2\times y_0+1\). But it does not hold for \(y_2\) and \(y_3\).

It's because they're permuted. In the block of size 4, the third and the fourth characters are switched.

Switching back results in:

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

Now it is certain that \(y_n=2\times y_{n-1}+1\).

Let's take a look at others.

ABCD

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

P: 00 01 02 03

C: 54 15 66 32

C': 54 15 32 66

All components are in the form of \(y_n=2\times y_{n-1}+2\).

So we can normalize the process:

In a sequence C' where 3rd and 4th characters are switched from 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} \]

Again I couldn't find out how first character is encrypted, so I tried every character.

Decrypting the last Exptected [sI~Od$5Z?KBfUw|n7R&P5{\a;D{| 7p"h=K=)5`hH`-[6W] to get:

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

I wrote my code as below.

I was going fine until stage 3, but I had to try things in other module so I put them altogether. That's why it is so messy..

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()

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()