Tokyo Westerns CTF 3rd 2017: BabyDLP

,

寝てる間にkonjoさんが解いてくれました。

problem

素数$p$と整数$g$および暗号化oracle $\mathrm{oracle}(s) = c \equiv g^{m \oplus s} \pmod{p}$が与えられる。$m$を答えよ。

solution

$\mathrm{oracle}(2^k)$を考えると$m$の$k$-bit目に対応して$\mathrm{oracle}(0) \cdot g^{\pm 2^k}$。 これをそれぞれの$k$で試せば終わり。

$g = 2$でなくても解ける。 line = fin.readline()[:4+bits//4]は今回は何も邪魔をしない。$m$のbit数より小さい制約だと問題になる。

implementation

#!/usr/bin/env python2
from pwn import * # https://pypi.python.org/pypi/pwntools
import argparse
parser = argparse.ArgumentParser()
parser.add_argument('host', nargs='?', default='ppc2.chal.ctf.westerns.tokyo')
parser.add_argument('port', nargs='?', default=28459, type=int)
parser.add_argument('--log-level', default='debug')
args = parser.parse_args()
context.log_level = args.log_level

# params
p = 160634950613302858781995506902938412625377360249559915379491492274326359260806831823821711441204122060415286351711411013883400510041411782176467940678464161205204391247137689678794367049197824119717278923753940984084059450704378828123780678883777306239500480793044460796256306557893061457956479624163771194201
g = 2
bits = 1024

# connect
proc = remote(args.host, args.port)
def oracle(s):
    line = hex(s)[2 :]
    assert line == line[: 4 + bits // 4]
    proc.sendline(line)
    c = int(proc.recvline(), 16)  # c = pow(g, m ^ s, p)
    return c

# run
c0 = oracle(0)
m = 0
i = 1
while i <= p:
    ci = oracle(i)
    if c0 == ci * pow(g, i, p) % p:
        m |= i
    else:
        assert ci == c0 * pow(g, i, p) % p
    log.info('m = %#x', m)
    i <<= 1

# result
log.info('flag = %s', hex(m)[2 :].decode('hex'))

Tokyo Westerns CTF 3rd 2017: My Simple Cipher

,

本番では自明っぽかったのでやらずに放置したらnkhrlab氏がやってくれた。

solution

等式 $\mathrm{encrypted}_{i + 1} \equiv \mathrm{message}_i + \mathrm{key}_i + \mathrm{encrypted}_i \pmod{128}$ を満たすように順に決めていけば決まる。

implementation

#!/usr/bin/env python3

# params
encrypted = '7c153a474b6a2d3f7d3f7328703e6c2d243a083e2e773c45547748667c1511333f4f745e'
encrypted = bytes.fromhex(encrypted)
key     = bytearray(b'?????????????')
message = bytearray(b'TWCTF{??????????????}|?????????????')
assert 1 + len(message) == len(encrypted)

# solve
while ord('?') in message:
    for i in range(len(message) - 1):
        if message[i] != ord('?'):
            c = (encrypted[i + 1] - encrypted[i] - message[i]) % 128
            key[i % len(key)] = c
            message[len('TWCTF{??????????????}|') + i % len(key)] = c
        elif key[i % len(key)] != ord('?'):
            c = (encrypted[i + 1] - encrypted[i] - key[i % len(key)]) % 128
            message[i] = c

# check
for i in range(len(message)):
    assert encrypted[i + 1] == (message[i] + key[i % len(key)] + encrypted[i]) % 128

# output
print('key:', bytes(key).decode())
print('message:', bytes(message).decode())

Tokyo Westerns CTF 3rd 2017: Freshen Uploader

,

動的scoringと基本点の結果によりWelcome問より得点が低いの好き。

solution

1

http://fup.chal.ctf.westerns.tokyo/download.php?f=../index.php のようにすればindex.php, download.phpが取れる。

download.php:

<?php
// TWCTF{then_can_y0u_read_file_list?}
$filename = $_GET['f'];
if(stripos($filename, 'file_list') != false) die();
header("Contest-Type: application/octet-stream");
header("Content-Disposition: attachment; filename='$filename'");
readfile("uploads/$filename");

2

file_list.phpを読みたいが普通に読みにいくと弾かれる。

stripos($filename, 'file_list') != false してるがstriposが返すのはindexなので: http://fup.chal.ctf.westerns.tokyo/download.php?f=file_list/../../file_list.php


AtCoder Regular Contest 082: F - Sandglass

,

http://arc082.contest.atcoder.jp/tasks/arc082_d

バグか誤読がなければぎりぎり間に合っていたかと思われます。(rating $-38$)

clar

  • Q. サンプルは正しいですか? たとえばサンプル1のクエリ2では、ひっくり返す前にはBには砂がX入っているので答えはX-1 = 179に見えます。
  • A. 各クエリでは、時刻 $t_i$ にパーツ A に入っている砂の量を答えてください(パーツ A が下になっていたとしてもです)。

solution

$O(K + Q)$。

例えばサンプル1で$t = r_1$より先では$0 \le a \le 60 = r_1$の場合の答えは全て等しい。 $\min, \max$の操作により情報が潰れるため、開始時点での$a$を

  • $a = 0$と同一視できるもの ($0 \le a le l$)
  • $a = X$と同一視できるもの ($r \le a le X$)
  • それ以外 ($l \le a \le r$)

の$3$つに分類できる。 反転する各時刻$t = r_j$での境界$l, r$と$a = 0, X$で始めたときの$a$の値を$O(K)$かけて事前計算しておけば、$a_i$で始めたときの同じ$t$での値は$O(1)$で求まる。

implementation

クエリは時系列順に与えられるのでしゃくとりっぽくすれば二分探索は不要。

#include <algorithm>
#include <cstdio>
#include <vector>
#define repeat(i, n) for (int i = 0; (i) < int(n); ++(i))
#define whole(x) begin(x), end(x)
using ll = long long;
using namespace std;
template <class T> inline void setmax(T & a, T const & b) { a = max(a, b); }
template <class T> inline void setmin(T & a, T const & b) { a = min(a, b); }

constexpr int inf = 1e9+7;
int main() {
    int x, k; scanf("%d%d", &x, &k);
    vector<int> r(k); repeat (i, k) scanf("%d", &r[i]);
    if (r[0]) r.insert(r.begin(), 0);
    r.push_back(inf);
    vector<int> hi(k + 1, x);
    vector<int> ub(k + 1, x);
    vector<int> lb(k + 1);
    vector<int> lo(k + 1);
    repeat (i, k) {
        ll dt = r[i + 1] - r[i];
        if (i % 2 == 0) {
            hi[i + 1] = hi[i] - dt;
            ub[i + 1] = ub[i];
            lo[i + 1] = lo[i] - dt;
            lb[i + 1] = lb[i] + max<ll>(0, - lo[i + 1]);
        } else {
            hi[i + 1] = hi[i] + dt;
            lb[i + 1] = lb[i];
            lo[i + 1] = lo[i] + dt;
            ub[i + 1] = ub[i] - max(0, hi[i + 1] - x);
        }
        setmax(hi[i + 1], 0); setmin(hi[i + 1], x);
        setmax(ub[i + 1], 0); setmin(ub[i + 1], x);
        setmax(lb[i + 1], 0); setmin(lb[i + 1], x);
        setmax(lo[i + 1], 0); setmin(lo[i + 1], x);
    }
    int q; scanf("%d", &q);
    while (q --) {
        int t, a; scanf("%d%d", &t, &a);
        auto j = (upper_bound(whole(r), t) - r.begin()) - 1;
        if (a <= lb[j]) {
            a = lo[j];
        } else if (ub[j] <= a) {
            a = hi[j];
        } else {
            a = (a - lb[j]) + lo[j];
        }
        int dt = t - r[j];
        a = j & 1 ? min(x, a + dt) : max(0, a - dt);
        printf("%d\n", a);
    }
    return 0;
}

AtCoder Regular Contest 082: D - Derangement

,

http://arc082.contest.atcoder.jp/tasks/arc082_b

solution

なにか貪欲っぽく。$O(N)$。

$i$を$p_i = i$なものの中で最小として$(i, i+1)$でswapすることを繰り返す。 $p_i = i$であれば$p_{i+1} \ne i$であるので、swapすれば$p_i \ne i \land p_{i+1} \ne i+1$となる。 これより早く解決する方法はないのは明らか(本当か?)なのでこれでよい。

implementation

#!/usr/bin/env python3
n = int(input())
p = list(map(lambda p_i: int(p_i) - 1, input().split()))
result = 0
for i in range(n):
    if p[i] == i:
        j = i + 1
        if j >= n:
            j = i - 1
        p[i], p[j] = p[j], p[i]
        result += 1
print(result)

AtCoder Regular Contest 082: C - Together

,

http://arc082.contest.atcoder.jp/tasks/arc082_a

solution

$X$の候補は$a_i - 1, a_i, a_i + 1$のみ考えればよい。 これを全て試す。 $O(N \log N)$。

implementation

#include <cstdio>
#include <map>
#define repeat(i, n) for (int i = 0; (i) < int(n); ++(i))
using namespace std;
template <class T> inline void setmax(T & a, T const & b) { a = max(a, b); }

int main() {
    int n; scanf("%d", &n);
    map<int, int> cnt;
    repeat (i, n) {
        int a_i; scanf("%d", &a_i);
        cnt[a_i] += 1;
    }
    int result = 0;
    for (auto it : cnt) {
        for (int x : {
                    it.first - 1,
                    it.first,
                    it.first + 1 }) {
            int acc = 0;
            if (cnt.count(x - 1)) acc += cnt[x - 1];
            if (cnt.count(x    )) acc += cnt[x    ];
            if (cnt.count(x + 1)) acc += cnt[x + 1];
            setmax(result, acc);
        }
    }
    printf("%d\n", result);
    return 0;
}

Tokyo Westerns CTF 3rd 2017: Liar's Trap

,

メンバーの契約してる計算資源などを借りて殴る準備をしていたら先に手元で当たりを引いてしまった。 運がよかったっぽい。

problem

Shamirの秘密分散法。 $(K, N)$閾値法だが、$N$個中に$L$個の嘘が混じっている。 鯖に繋ぐとそのようなデータが降ってくるので秘密を復元せよ。

solution

Brute-force。

秘密の復号には多項式補間を使う。 閾値$K = 25$だけの点を集めてそれを全て通る次数が最小の多項式を計算する。 嘘が混じってないかの多項式の補間結果$f$の正当性の確認には、十分多くの他の点$(x, y)$が一致する$f(x) = y$ことを確認すればよい。 $K + 1$点使って補間して次数が$K - 1$であることを見て検証するのは確率上で損をする。

$N$個から勝手に$K$個選んで$L$個ある嘘をひとつも踏まない確率$\frac{{}_{N-L}C_K}{{}_NC_K} = \mathrm{binomial}(62, 25) / \mathrm{binomial}(100, 25) \approx 6.07 \times 10^{-7}$。 $1.65 \times 10^6$回の試行で成功することが期待できる。

多項式補間を$O(K^3)$でやるとすると$25^3 \cdot 1.65 \times 10^6 \approx 2.58 \times 10^{10}$なのでなんとかならないこともない。 検証にも$O(KL)$かかるが無視できる。 鯖は$30$秒で接続が切れるが、そのたびに再接続すればよいのでこの制限時間は無視できる。 実際にsagemath PolynomialRinglagrange_polynomialで書いてみると秒あたり$300$回程度の試行が可能。$90$分程度回せばflagになるのなら十分短かいので待てばよい。

implementation

sagemathをpwn.tubes.process.processで呼び出しつついい感じにする。

memo:

  • 次の同様の機会にも使えそう
  • workersのcloseは複数なのでtry-catchしたがcontextlib.ExitStackとかすべき
  • sagemathの起動が遅いので先に起動しておくなど
  • 不慮のerrorが怖いので握り潰し
#!/usr/bin/env python2
from pwn import * # https://pypi.python.org/pypi/pwntools
import sys
import os

## parameters
P = 115792089237316195423570985008687907853269984665640564039457584007913129639747 # modulus
N = 100 # The number of users
K = 25 # (The degree of the polynomial) - 1
L = 38 # The number of liars

## options
import argparse
parser = argparse.ArgumentParser()
parser.add_argument('host', nargs='?', default='ppc2.chal.ctf.westerns.tokyo')
parser.add_argument('port', nargs='?', default=42453 , type=int)
parser.add_argument('--log-level', default='debug')
parser.add_argument('--sage-script', default='a.sage')
parser.add_argument('--num-threads', default=2, type=int)
args = parser.parse_args()
context.log_level = args.log_level

## run
while True:
    try:
        workers = []
        for _ in range(args.num_threads):
            worker = process([ 'sagemath', args.sage_script ], stderr=sys.stderr)
            workers += [ worker ]
        for worker in workers:
            assert 'ready' == worker.recvline().strip()
        with remote(args.host, args.port) as p:
            user = []
            for i in range(N):
                p.recvuntil('User %d: ' % i)
                user_i = int(p.recvline())
                user += [ user_i ]
            p.recvuntil("What's secret? \n")
            rlist = []
            for worker in workers:
                for user_i in user:
                    worker.sendline(str(user_i))
            while True:
                for worker in workers:
                    if worker.can_recv():
                        secret = int(worker.recvline())
                        p.sendline(str(secret))
                        log.info('%s', p.recvall())
                        sys.exit(os.EX_OK)
                try:
                    p.recv(timeout=0.1)
                except EOFError:
                    break
    except Exception as e:
        print e
    finally:
        for worker in workers:
            worker.close()
#!/usr/bin/env sagemath
from sage.all import *
import itertools
from random import shuffle as random_shuffle
import sys

## Parameters
P = 115792089237316195423570985008687907853269984665640564039457584007913129639747 # modulus
N = 100 # The number of users
K = 25 # (The degree of the polynomial) - 1
L = 38 # The number of liars
R.<x> = PolynomialRing(GF(P))

print 'ready'
points = []
for i in range(N):
    user_i = GF(P)(raw_input())
    points += [ (i + 1, user_i) ]

for i in itertools.count():
    random_shuffle(points)
    f = R.lagrange_polynomial(points[: K])
    denied = 0
    for x, y in points[K :]:
        if f(x) != y:
            denied += 1
            if denied > L:
                break
    else:
        print >> sys.stderr, 'found'
        print >> sys.stderr, f
        print f.coefficients()[0]
        break
    if i % 1000 == 0:
        print >> sys.stderr, 'iteration', i

実行結果

$ ./a.py
[+] Starting local process '/usr/bin/sagemath' argv=['sagemath', 'a.sage'] : Done
[+] Starting local process '/usr/bin/sagemath' argv=['sagemath', 'a.sage'] : Done
[DEBUG] Received 0x6 bytes:
    'ready\n'
[DEBUG] Received 0x6 bytes:
    'ready\n'
[+] Opening connection to ppc2.chal.ctf.westerns.tokyo on port 42453: Done
[DEBUG] Received 0x5a0 bytes:
    '--- Distributed Secret ---\n'
    'User 0: 81150319008277935651190969669213782378172579767382815157805982988728819992206\n'
    'User 1: 11712555490012558886089714254641987873285130609221007180864414830910473851875\n'
    'User 2: 63730717344568907876086325724193290114861305343889640416686199506982018899873\n'
    'User 3: 66766397461503971913832844733723049489193095618663319391332778263232193261357\n'
    'User 4: 82638996802643671737543023348237439555817057572349855415482387999067978356731\n'
    'User 5: 70240109086723286657969138586351499304140843802722151452774961683333964365012\n'
    'User 6: 98497625628627988968440523867397599312872565328340665904352039077473936314627\n'
    'User 7: 16122740533639510438943185226043413199786771566979722609611793614677750557290\n'
    'User 8: 36945603640529079359757649050369886737692682895334891442986567053099133422971\n'
    'User 9: 65544388190508452438984490674749688592697674035792275776355146814172533097313\n'
    'User 10: 81518537191575827367039496057882920866023583343034947918370796881435953162275\n'
    'User 11: 87817338660745849043240772812950586374890772491457345016050817558616520517875\n'
    'User 12: 10516424861752371647340014472744545312651558592566281200888348459406328440156\n'
    'User 13: 80771093250148514662089812673968530273945484362230329643515886003592964990486\n'
    'User 14: 5049873803532529953118671325607512024716607382534373842293970111292242134202\n'
    'User 15: 56000312085477626295163884714875982570949405662276973667933309764126454881275\n'
    'User 16: 92069397866212126588286'

...

[DEBUG] Sent 0x4d bytes:
    '8220802122483356817954269691176257566602927371584327025726217758008456434958\n'
[DEBUG] Sent 0x4e bytes:
    '91932182849279606453521420188291709083625432117098630942570447165997071352429\n'
iteration 0
iteration 0
found
69624823218008388921315805060888208141581825988501473246594270689394450169161*x^24 + 64825073055848227291292694348193758809854906501104559347853076227037391403153*x^23 + 31808109129684417299527507936450302010771854844782383011782158199922227331125*x^22 + 12666869281384521659157298884656507926829151137712447899126621260816705356159*x^21 + 21640542208372067903582837172056664439239331251462253201439737499592337646702*x^20 + 9829356453176815294712267387987855219897167396608323519667877896738510296663*x^19 + 34236329816422036178151957912905500636029769444808071449010532397768197110819*x^18 + 110771620903969556259749942118821452607974718767421055691912391573219821596766*x^17 + 92748409927816854017308634583773270215071392990488041276626649577983209235029*x^16 + 101202385066351133406711815082529273555980359682045061775391263338564855173093*x^15 + 81408988486927615874977618623024025905557143965433485808629839959635887747460*x^14 + 59212838114321546358653549408562895603302506538517130369773568546827821810240*x^13 + 76773541028442642735305238590860243334662973229753940529543002597620868897597*x^12 + 50118826016219124347602984350366761933191885879101290175967417660291962314458*x^11 + 55658973461556436551790370307930826873846432771196618234426089443648821947729*x^10 + 68559093225558574101794018004406524889265750699563937967041101285014658097693*x^9 + 5850846357819829925515053051966387701663303023274354636458618870338886552767*x^8 + 77070114240801487407279837730030838825961179153377510505808185027643964986136*x^7 + 43854269077892311931885860253718848444772912693919556406187462506177074586709*x^6 + 38055456239059329959750665101346473712893179053134588772104107941633575030365*x^5 + 31130704079602104420632307046741960074707171644507123627197478958473556885564*x^4 + 959672696712703270049437238053215023200349134726653557662525631952968771803*x^3 + 57463224607975981727415116112331068042892938545254190753713626264463809075234*x^2 + 92090930618783324495003716760378392451067470415954366988472129961056036406627*x + 107667459642126628678155167126081725752852688200361260853307092404499189992800
[DEBUG] Received 0x4f bytes:
    '107667459642126628678155167126081725752852688200361260853307092404499189992800\n'
[DEBUG] Sent 0x4f bytes:
    '107667459642126628678155167126081725752852688200361260853307092404499189992800\n'
[+] Recieving all data: Done (78B)
[DEBUG] Received 0x4e bytes:
    "OK. I'll give you the flag\n"
    "TWCTF{Error_correction_to_Shamir's_Secret_Sharing}\n"
[*] Closed connection to ppc2.chal.ctf.westerns.tokyo port 42453
[*] OK. I'll give you the flag
    TWCTF{Error_correction_to_Shamir's_Secret_Sharing}
[*] Stopped program '/usr/bin/sagemath'
[*] Stopped program '/usr/bin/sagemath'
------------------------------------------------------------------------
/usr/lib/sagemath/local/lib/python2.7/site-packages/cysignals/signals.so(+0x45f8)[0x7f4d14bc15f8]
/usr/lib/sagemath/local/lib/python2.7/site-packages/cysignals/signals.so(+0x4665)[0x7f4d14bc1665]
/usr/lib/sagemath/local/lib/python2.7/site-packages/cysignals/signals.so(+0x8007)[0x7f4d14bc5007]
/lib/x86_64-linux-gnu/libpthread.so.0(+0x11390)[0x7f4d174e1390]
/usr/lib/sagemath//local/lib/libpython2.7.so.1.0(PyObject_Call+0x8)[0x7f4d17741fb8]
/usr/lib/sagemath//local/lib/libpython2.7.so.1.0(PyEval_CallObjectWithKeywords+0x47)[0x7f4d177f5137]
/usr/lib/sagemath//local/lib/libpython2.7.so.1.0(PyErr_CheckSignals+0xa9)[0x7f4d1783f959]
/usr/lib/sagemath//local/lib/libpython2.7.so.1.0(Py_MakePendingCalls+0x9a)[0x7f4d177f4c8a]
/usr/lib/sagemath//local/lib/libpython2.7.so.1.0(PyEval_EvalFrameEx+0x4fb9)[0x7f4d177fa709]
/usr/lib/sagemath//local/lib/libpython2.7.so.1.0(PyEval_EvalCodeEx+0x81c)[0x7f4d177ff00c]
/usr/lib/sagemath//local/lib/libpython2.7.so.1.0(+0x8762c)[0x7f4d1777462c]
/usr/lib/sagemath//local/lib/libpython2.7.so.1.0(PyObject_Call+0x43)[0x7f4d17741ff3]
/usr/lib/sagemath//local/lib/libpython2.7.so.1.0(PyObject_CallFunctionObjArgs+0x16f)[0x7f4d17742c0f]
/usr/lib/sagemath//local/lib/libpython2.7.so.1.0(PyObject_ClearWeakRefs+0x2d8)[0x7f4d177bb0d8]
/usr/lib/sagemath//local/lib/libpython2.7.so.1.0(+0x63457)[0x7f4d17750457]
/usr/lib/sagemath//local/lib/libpython2.7.so.1.0(+0x9be47)[0x7f4d17788e47]
/usr/lib/sagemath//local/lib/libpython2.7.so.1.0(PyDict_SetItem+0x67)[0x7f4d1778a937]
/usr/lib/sagemath//local/lib/libpython2.7.so.1.0(_PyModule_Clear+0x16c)[0x7f4d1778ed9c]
/usr/lib/sagemath//local/lib/libpython2.7.so.1.0(PyImport_Cleanup+0x419)[0x7f4d17812689]
/usr/lib/sagemath//local/lib/libpython2.7.so.1.0(Py_Finalize+0xfe)[0x7f4d178248ce]
/usr/lib/sagemath//local/lib/libpython2.7.so.1.0(Py_Main+0x5f4)[0x7f4d1783b464]
/lib/x86_64-linux-gnu/libc.so.6(__libc_start_main+0xf0)[0x7f4d17126830]
python(_start+0x29)[0x400759]
------------------------------------------------------------------------
$ Attaching gdb to process id 15922.

Saved trace to /home/user/.sage/crash_logs/crash_1dEuLA.log
------------------------------------------------------------------------
Unhandled SIGSEGV: A segmentation fault occurred.
This probably occurred because a *compiled* module has a bug
in it and is not properly wrapped with sig_on(), sig_off().
Python will now terminate.
------------------------------------------------------------------------

$ 

  • 2017年 9月 5日 火曜日 00:56:18 JST
    • 補間結果の検証に関して追記

Tokyo Westerns CTF 3rd 2017: The Worst

,

problem

RSA暗号。 暗号化に使われたコード encrypt.c が与えられるので復号せよ。

solution

  1. srand()がないのでflag長を仮定すればpaddingが定まる
  2. Coppersmith’s attack

paddingはrand()により生成されているがsrand()がないので予測できる。 flag長$\lt 32$を総当たりすればpaddingは決定できる。 このpaddingはflag長に対して十分長いので、平文のほとんどが分かっていることになる。

特に平文$m$の下位bitが$n$のbit数の $1-1/e$ 以上分かっていることになり、Coppersmith’s attackが使える。 $\overline{m} = \mathrm{padding}$で$k = (\text{paddingのbit数})$とすれば多項式$f(x) = (\overline{m} + 2^k x)^e - c \equiv 0 \pmod{n}$の解$x$を使って$m = \overline{m} + 2^k x$であり、解$x$がflagである。 これはsagemathに投げれば解いてくれるのでflagが得られる。

参考: http://inaz2.hatenablog.com/entry/2016/01/20/022936

implementation

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

#define BITS 1024
#define N "d1e44ef6c387eeff8b4852372a68cfdcfe3c14da22f1933e3d0fb11d434f480e3415ab08ee42e8d5a7a5ad34e1c114e5d7f2fa970eb968d492542089325301f4090c850c4ece500388d720fb7b5e2772a063ecf238675b8bcde0cb8ba54eb663d74b80e459c803980d7f5cbe4fc76aa036dfc3d6e7a7ec750f2a4ef2658c9029"
#define e 3

char flag[BITS / 8];
char message[BITS];
void read_flag() {
  int i = 0;
  fgets(flag, 32, stdin);
  for(i = strlen(flag); i < sizeof(flag); i++) {
    flag[i] = rand() % 256;
  }
}

int main() {
  int i, j;
  mpz_t m, n, c;
  mpz_init(m);
  mpz_init(n);
  mpz_init(c);

  read_flag();
  for(i = 0; i < sizeof(flag); i++) {
    sprintf(&message[i * 2], "%02x", (unsigned int)flag[i]);
  }
  mpz_set_str(n, N, 16);
  mpz_set_str(m, message, 16);
  mpz_powm_ui(c, m, e, n);
  fprintf(stderr, "m = 0x");
  mpz_out_str(stdout, 16, m);
  puts("");
  fprintf(stderr, "c = 0x");
  mpz_out_str(stdout, 16, c);
  puts("");
}
#!/usr/bin/env python3
import subprocess

def encrypt(s):
    proc = subprocess.run('./a.out', input=s, stdout=subprocess.PIPE)
    lines = proc.stdout.decode().splitlines()
    m = int(lines[0], 16)
    c = int(lines[1], 16)
    return m, c

e = 3
n = 0xd1e44ef6c387eeff8b4852372a68cfdcfe3c14da22f1933e3d0fb11d434f480e3415ab08ee42e8d5a7a5ad34e1c114e5d7f2fa970eb968d492542089325301f4090c850c4ece500388d720fb7b5e2772a063ecf238675b8bcde0cb8ba54eb663d74b80e459c803980d7f5cbe4fc76aa036dfc3d6e7a7ec750f2a4ef2658c9029
c = 0x998225e156e8d77d3d936283a3f04aba11da3365e776ee5f779dcda44176698908d0970ad5daa32b774e023351b1237783c876e8be62cccddcad6adb362925b6b611e82995a53a1df97b15af55394fe0b544d59b6fd6d3057a5e448b40b2405ffcc3a7e8115cfb57b43729dcfe410c17063cf6d63fdc6c621e2e845934b7c32f
for newline in [ '', '\n', '\r\n', '\r' ]:
    for l in range(32):
        flag = 'A' * l + newline
        mbar, _ = encrypt(flag.encode())
        print(e)
        print(n)
        print(c)
        print(mbar)
        print(len(flag) * 8)
#!/usr/bin/env sagemath
from sage.all import *

while True:
    e = input()
    n = input()
    c = input()
    mbar = input()
    kbits = input()
    e, n, c, mbar, kbits = map(sage.rings.integer.Integer, [ e, n, c, mbar, kbits ])

    nbits = n.nbits()
    beta = 0.5
    epsilon = beta^2/7

    PR.<x> = PolynomialRing(Zmod(n))
    f = (mbar + 2 ^ (nbits - kbits - 10) * x)^e - c
    f = f.monic()

    xs = f.small_roots(X=2^(kbits + 20), beta=beta)
    for x in xs:
        m = mbar + 2 ^ (nbits - kbits - 10) * x
        print m
        if pow(m, e, n) == c:
            print 'found'
            print 'm =', hex(int(m))

Tokyo Westerns CTF 3rd 2017: BabyPinhole

,

problem

Paillier暗号による公開鍵$(n, g)$と暗号文$c$が与えられている。 整数$b$が固定されており、復号結果の$b$-bit目を返すoracleがある。 $c$を復号せよ。

solution

準同型性(加法)をやる。

Paillier暗号は準同型性を持つ: $\mathrm{enc}(m_1 ; r_1) \mathrm{enc}(m_2 ; r_2) = \mathrm{enc}(m_1 + m_2 ; r_1 r_2)$。 $\mathrm{oracle}(c \cdot \mathrm{enc}(\delta ; r_2))$とすれば$c + \delta$の復号結果の$b$-bit目が得られる。 $\delta = 2^{b-1}$として$\mathrm{oracle}(c ) \ne \mathrm{oracle}(c \cdot \mathrm{enc}(2^{b-1} ; r_2))$であれば$m + 2^{b-1}$としたときに繰り上がりが発生していたことになり、つまり$m$の$b-1$-bit目は$1$であるかどうかが分かる。 繰り上がりが発生したかどうかで$b$-bit目が変わるように$\delta$を決めて繰り返していけばflagが取れる。 flagの後半については単純にすればよい。flagの前半については$\bmod N$のoverflowが効いてくるので少し手間だが、やればなんとかなる。

implementation

#!/usr/bin/env python2
from pwn import * # https://pypi.python.org/pypi/pwntools
import argparse
parser = argparse.ArgumentParser()
parser.add_argument('host', nargs='?', default='ppc2.chal.ctf.westerns.tokyo')
parser.add_argument('port', nargs='?', default=38264, type=int)
parser.add_argument('--log-level', default='debug')
args = parser.parse_args()
context.log_level = args.log_level

# params
from Crypto.Util.number import *
from hashlib import sha1
bits = 1024
def LCM(x, y):
    return x * y // GCD(x, y)
def L(x, n):
    return (x - 1) // n
def encrypt(m, r):
    m %= n2
    assert 1 <= r < n2
    c = pow(g, m, n2) * pow(r, n, n2) % n2
    return c
def complement(s):
    return ''.join(map(lambda c: str(1 - int(c)), s))
with open('publickey') as fh:
    n = int(fh.readline(), 16)
    n2 = int(fh.readline(), 16)
    g = int(fh.readline(), 16)
with open('ciphertext') as fh:
    ciphertext = int(fh.readline(), 16)

# connect
p = remote(args.host, args.port)
def oracle(c, memo={}):
    c %= n2
    assert 0 <= c < n2
    if c not in memo:
        p.sendline(hex(c))
        memo[c] = bool(int(p.recvline()))
    return memo[c]

# find b
i = 512 + 3
while oracle(ciphertext) == oracle(ciphertext * encrypt(1 << i, 1) % n2):
    i -= 1
b = i
log.info('b = %d', b)

# offset
oracle_ciphertext = oracle(ciphertext)
if oracle_ciphertext:
    ciphertext *= encrypt(- 1 << b, 1)

# mc
i = 1023
mc = ''
while i >= 0:
    pad = (int(complement(mc) + '1', 2) << i)
    bit = (int(oracle(ciphertext) != oracle(ciphertext * encrypt(pad, 1) % n2)))
    mc += str(bit)
    log.info('i = %d: mc = %s', i, mc)
    i -= 1

# m
m = (- (int(complement(mc), 2) + 1 - (1 << b))) % n
if oracle_ciphertext:
    m += 1 << b
log.info('m = %d', m)

# flag
oracle(ciphertext * encrypt(- m, 1), memo={})
flag = 'TWCTF{' + sha1(str(m).encode('ascii')).hexdigest() + '}'
log.info('flag = %s', flag)

  • 2017年 9月 11日 月曜日 21:50:55 JST
    • 怪しい部分を修正

Tokyo Westerns CTF 3rd 2017: pplc

,

private

縛りgolf。dir(p)[0]_Private__flag

$ nc ppc1.chal.ctf.westerns.tokyo 10000
eval('p.%s()'%dir(p)[0])

TWCTF{__private is not private}

local

code objectを覗けばよい

$ nc ppc1.chal.ctf.westerns.tokyo 10001
get_flag.__code__.co_consts

(None, 'TWCTF{func_code is useful for metaprogramming}')

comment

commentといいつつ実際はdocstringなので通常の方法で取れる

$ nc ppc1.chal.ctf.westerns.tokyo 10002
comment_flag.__doc__

Welcome to unreadable area!
FLAG is TWCTF{very simple docstring}

AtCoder Grand Contest 009: B - Tournament

,

http://agc009.contest.atcoder.jp/tasks/agc009_b

solution

木DP。$O(N \log N)$。

数値$a_i$は人$i, a_i$が戦って$a_i$が勝ったことを示す。 つまりトーナメント中に次のような部分が存在する。

       a_i
        |
     .--+--.
     |     |
    a_i    i

優勝者は決まっているので、それぞれの人がどの順番で相手を倒したかしか自由度はない。 例えば$a_i = a_j = a$なら、次の図の*ijを配置する$2$通り。

           a
           |
        .--+--.
        |     |
        a     *
        |
     .--+--.
     |     |
     a     *

部分木の高さは低くて損しないので、木DPで下から決めていけばよい。

implementation

#include <algorithm>
#include <cstdio>
#include <functional>
#include <vector>
#define repeat(i, n) for (int i = 0; (i) < int(n); ++(i))
#define whole(x) begin(x), end(x)
using namespace std;

int main() {
    int n; scanf("%d", &n);
    vector<vector<int> > g(n);
    repeat (i, n - 1) {
        int a_i_1; scanf("%d", &a_i_1); -- a_i_1;
        g[a_i_1].push_back(i + 1);
    }
    vector<int> dp(n);
    function<void (int)> go = [&](int i) {
        if (g[i].empty()) return;
        vector<int> acc;
        for (int j : g[i]) {
            go(j);
            acc.push_back(dp[j]);
        }
        sort(whole(acc));
        reverse(whole(acc));
        repeat (k, acc.size()) acc[k] += k + 1;
        dp[i] = *max_element(whole(acc));
    };
    go(0);
    printf("%d\n", dp[0]);
    return 0;
}

AtCoder Grand Contest 005: A - STring

,

http://agc005.contest.atcoder.jp/tasks/agc005_a

$i$回目には$a_i$番目のSTを取り除く、のようにすると$O(|X|^2)$になりそう。

solution

貪欲な感じで。$O(|X|)$。

最も左側のものを取り除くことを繰り返すので、空文字列から始めて末尾に$X$から$1$文字ずつ付け加えていき消せるか見ればよい。 操作対象は長さ$2$の連続な部分文字列のみなので、見る範囲は追加した部分のみでよい。 $O(|X|)$回の操作ごとに$O(1)$なので全体で$O(|X|)$。

implementation

#!/usr/bin/env python3
x = input()
s = 0
t = 0
for c in x:
    if c == 'S':
        s += 1
    elif c == 'T':
        if s:
            s -= 1
        else:
            t += 1
    else:
        assert False
print(s + t)


AtCoder Regular Contest 072: F - Dam

,

https://beta.atcoder.jp/contests/arc072/tasks/arc072_d

solution

dequeでいい感じにする。$O(N)$。

水の流入の履歴をdequeで持ち、前から見ていく。 このとき流入する水の温度が時間に対して単調増加なら、履歴の先頭の水を流入しなかったことにすればよい。 新しい朝を迎えたときに単調増加の仮定が壊れる可能性がある。 これは前日の水と当日の水が同時に流れ込んで来たと見做すことで解消できる。 低い方の温度の水が流れ込んでくる前に水を捨てるのは損なのでこれでよい。 dequeの操作はならし$O(N)$回なので全体でも$O(N)$。

反省

単調増加の仮定を置くのに気付けなかった。 緩和は積極的にしていくべきぽい。

implementation

#include <cstdio>
#include <deque>
#include <tuple>
#include <vector>
#define repeat(i, n) for (int i = 0; (i) < int(n); ++(i))
#define repeat_from(i, m, n) for (int i = (m); (i) < int(n); ++(i))
using namespace std;

int main() {
    int n, l; scanf("%d%d", &n, &l);
    vector<int> t(n), v(n); repeat (i, n) scanf("%d%d", &t[i], &v[i]);
    deque<pair<int, double> > deq;
    deq.emplace_back(v[0], t[0]);
    double acc = t[0] *(double) v[0];
    printf("%.12lf\n", acc /(double) l);
    repeat_from (i, 1, n) {
        for (int nv = v[i]; nv > 0; ) {
            int dv = min(nv, deq.front().first);
            nv -= dv;
            deq.front().first -= dv;
            acc -= deq.front().second * dv;
            if (deq.front().first == 0) {
                deq.pop_front();
            }
        }
        int nv = v[i];
        double nt = t[i];
        while (not deq.empty() and deq.back().second > nt) {
            int pv; double pt; tie(pv, pt) = deq.back();
            deq.pop_back();
            nt = (nt * nv + pt * pv) / (nv + pv);
            nv += pv;
        }
        deq.emplace_back(nv, nt);
        acc += t[i] *(double) v[i];
        printf("%.12lf\n", acc /(double) l);
    }
    return 0;
}

HITB GSEC Singapore 2017: HACK IN THE CARD I

,

このようにするというのは分かっていたが、本番では解けず。 writeup (https://tradahacking.vn/hitb-gsec-singapore-2017-ctf-write-ups-crypto-category-803d6c770103)を読んで追試した。

problem

サイドチャネル攻撃をする問題。RSAの復号処理の際の電圧の波形が与えられるので秘密鍵を出せばよい。

solution

単純電力解析をする。 操作pow(c, d, n)が繰り返し二乗法による$O(\log d)$回の乗算で実現されているとする。 例えばコードは次のようになる。

def pow(c, d, n):
    m = 1
    i = 1
    while i <= d:
        if d & i:
            m = m * c % n
        c = c * c % n
        i <<= 1
    return m

乗算の実行が分かればif d & i:で分岐がどうなったのか分かり、これから$d$が復元できる。

波形を離散的なデータに直すのはやるだけ。 そこから$d$を読みとるのはエスパー気味。 結論としては、波形のhigh/lowを+/-で書くとして++-ならif内が実行され+-ならそうでない。 先頭のいくらかは$d$に関与しないデータであるが、今回は残り全てが$d$の情報であった。 loopの形を見れば分かるが、最後に反転するのを忘れないようにする。

implementation

#!/usr/bin/env python3

# read
with open('data.txt') as fh:
    data = list(map(float, fh.read().split()))
last = False
cnt = 0
wave = []
for i, y in enumerate(data):
    x = 0.001 * (i + 1)
    # print('#' * int(y - 150), y, x)
    ave = 0
    ave += (i - 1 >= 0 and data[i - 1] or data[i])
    ave += data[i]
    ave += (i + 1 < len(data) and data[i + 1] or data[i])
    ave /= 3
    cur = ave > 230
    if cur == last:
        cnt += 1
    else:
        # print('-+'[last], cnt)
        wave += [ '-+'[last] * round(cnt / 50) ]
        last = cur
        cnt = 0
wave += [ '-+'[last] * round(cnt / 50) ]
wave = ''.join(wave)
print(wave)

# decode
s = ''
i = 4
while i < len(wave):
    if wave[i : i + 3] == '++-':
        s += '1'
        i += 3
    else:
        assert wave[i : i + 2] == '+-'
        s += '0'
        i += 2
print(s)
d = int(s[:: -1], 2)

# check
import Crypto.PublicKey.RSA
import random
import gmpy2
with open('publickey.pem') as fh:
    key = Crypto.PublicKey.RSA.importKey(fh.read())
e = gmpy2.mpz(key.e)
n = gmpy2.mpz(key.n)
for _ in range(100):
    m = random.randint(0, n - 1)
    c = pow(m, e, n)
    assert pow(c, d, n) == m
print('d =', d)

AtCoder Grand Contest 019: C - Fountain Walk

,

https://beta.atcoder.jp/contests/agc019/tasks/agc019_c

LISって言われれば(バグらせたのを除いて)すぐだった。本番でもDをバグらさなければ解けてたのかも。

solution

LIS。$O(N \log N)$。

サンプルから分かるように、噴水は曲がるときに通るとショートカットになり、直進するときに通るとロスとなる。 まず、$[x_1, x_2] \times [y_1, y_2]$の長方形の中を最短経路で通ればよい。 そうでない経路があったとすると、経路中に長方形の境界を伸ばした直線を踏み越えて戻ってくる部分があるが、これを境界上を一直線に進むように書き換えて経路長を減少させられる。 長方形の中で戻りが発生する場合も同様。

噴水を曲がり角に配置したいが後戻りは禁止とする。 すると使う噴水の座標は$x_i \lt x_{i+1} \land y_i \lt y_{i+1}$を満たし、LISを使ってその長さの回数$k$だけできる。 さらに基本的に横切ることは回避できる。 ただし噴水が壁のように配置されている場合は回避できない。 $w = |x_1 - x_2|$かつ$y = |y_1 - y_2|$とおいて$k = \max \{ w, h \} + 1$の場合がそれ。 この場合$1$度だけ横切る必要がある。

implementation

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <map>
#include <vector>
#define repeat(i, n) for (int i = 0; (i) < int(n); ++(i))
#define whole(x) begin(x), end(x)
using namespace std;

template <typename T>
vector<T> longest_increasing_subsequence(vector<T> const & xs) {
    vector<T> l; // l[i] is the last element of the increasing subsequence whose length is i+1
    l.push_back(xs.front());
    for (auto && x : xs) {
        auto it = lower_bound(l.begin(), l.end(), x);
        if (it == l.end()) {
            l.push_back(x);
        } else {
            *it = x;
        }
    }
    return l;
}

int main() {
    // input
    int lx, ly, rx, ry, n; scanf("%d%d%d%d%d", &lx, &ly, &rx, &ry, &n);
    int h = abs(ry - ly);
    int w = abs(rx - lx);
    vector<pair<int, int> > f;
    repeat (i, n) {
        int x, y; scanf("%d%d", &x, &y);
        x = lx <= rx ? x - lx : lx - x;
        y = ly <= ry ? y - ly : ly - y;
        if (0 <= x and x <= w and 0 <= y and y <= h) {
            f.emplace_back(x, y);
        }
    }
    // solve
    vector<int> lis;
    if (not f.empty()) {
        vector<int> g;
        sort(whole(f));
        for (auto it : f) g.push_back(it.second);
        lis = longest_increasing_subsequence(g);
    }
    double result = 100.0 * (h + w) - (20 - 5 * M_PI) * lis.size();
    if (lis.size() == min(w, h) + 1) {
        result += 5 * M_PI;
    }
    // output
    printf("%.15lf\n", result);
    return 0;
}