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

한국어(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()