CTF問題とセキュリティ(4年実験)
この実験では、セキュリティコンテストのCTF問題(Capture The Flag競技)について、インターネットの仕組みを理解し、その問題の解き方を考え、新しく自分自身でCTF問題を作ってもらいます。
日程
実験は、4週にわたり、以下の日程で行います。
- 1回目の実験グループは、Cyber SAKURA CTF大会(オンライン) 10/26に腕試しで参加しませんか?
週 | 内容 |
1 | (前半)暗号・ファイル・Web |
2 | |
3 | (後半) プログラム作成・インターネット・OS |
4 |
前半・後半でそれぞれ、問題例(もしくは自分で見つけたCTF問題)の1つの説明と自作のCTF問題1つを新しく作り説明をしてください。最終的に4つの問題の説明のレポートを提出となります。
提出物
- 実験の目的
- 問題例(or 自分で見つけたCTF問題)を1つ選び
- 前半・後半それぞれについて
- その問題が情報セキュリティにどう関係しているのか
- 問題の解き方のしくみと解説
- 自作問題について
- 前半・後半それぞれ
- その問題が情報セキュリティにどう関係しているのか
- 問題の解き方、問題の作り方
- しくみと解説
- 提出先はこちらのTeams共有フォルダに。
- 自作問題の例
- サブリミナル効果で隠されたGIF
- 電子透かし
- 学校からアクセスする時だけ、答えが見える。(REMOTE_HOST)
- スマホでアクセスした時だけ、答えが見える。(HTTP_USER_AGENT)
- Google 検索した後だけ、答えが見える。(HTTP_REFERER)
追記(2024/10/29)
Ethernet LANとWAN接続
前回の物理層のLANの話に引き続き、WANの話を説明。
前回の復習
10BASE5, 10BASE2 では、同軸ケーブルにPCが接続。
10BASE5 トランシーバ
10BASE2 とT型分岐コネクタ
10BASE-T
Ethernet と通信速度
10BASE 5/2/-T といった 10BASE は、通信速度の上限が 10Mbps (bit per second) を意味する。100BASE-T といった 100BASE は、100Mbps を意味する。最近では、1000BASE-T は、1000 Mbps = 1Gbps の通信速度となる。最近では、10G BASE-T といった記載であれば、10Gbps を意味する。
バス接続(LAN)と転送速度
基本的な Ethernet の接続では、1本の通信路を共有するバス型接続のため、1本の信号線をパケット単位の通信の短い時間に区切って、送信を交代しながら行う時分割多重方式で行い通信を行う。パケット(イーサネットフレーム)とは、通信データを送る単位で最大1500byteとなっている。(MTU値:Maximum Transmission Unit)
例えば、10BASE のネットワークでつながった4台のパソコンで、A-B間、C-D間で同時に通信を行おうとすると、A-Bの通信中は、通信路が使用中のため、C-D間の通信はできない。このため、A-B間、C-D間の通信をパケットを送る毎に交代しながら通信路を利用する。これにより、見かけ上は A-B, C-D 間が同時に通信しているようにみえる。
-
- 10BASE/5の PC-AとPC-Bの間で、音楽CD1枚のデータ(700MB)をを送る場合、通信時間はどの位かかるか?
- →答え:
700M[byte] = 5.6G[bit] なので、10M[bit/sec]で送ると、560[sec]
- →答え:
- 同じく、A-B間、C-D間で同時に送る場合は、通信時間はどのくらいかかるか?
- →答え:
短時間的には同時に通信ができないので、通信路を切り替えながら送るため、倍の時間がかかる。よって、1120[sec]
- →答え:
- 10BASE/5の PC-AとPC-Bの間で、音楽CD1枚のデータ(700MB)をを送る場合、通信時間はどの位かかるか?
10BASE/T, 100BASE-T, *BASE-T では、HUBの内部構造に注意が必要。基本的には、見かけ上は木構造のように分配しているように見えるけど、内部はバス型の通信路に変わりはない。10BASE/5/2と異なり、データの送信用,受信用の2つの信号のペアとなっている。10BASE/T を利用している頃は、HUBは高価であり単純なバス型接続のHUB(Dumb HUB)であれば、短時間的にみればC-D間通信中はE-F間通信ができない。(前述のようにパケットに小分けして通信するので見かけ上は並行して通信しているように見える)
しかしこれでは、通信速度が無駄になるので、最近はスイッチングHUBが利用される。このHUBは、通信相手に応じてHUB内部の通信路を切り分けるので、A-B間通信中でも、C-D間通信が可能となる。送り先を区別するためには通信機器ごとに固有値が割り振られているMACアドレスを使う。
理解確認
- 前述の2つのカスケード接続されたDumb HUBで、A,B,C,D,E,Fのコンピュータが繋がっている時、A-C間、B-D間で音楽CD700MBのデータを送る場合、通信時間はどうなる?
電話線接続
同じ敷地内のネットワーク接続のLANどうしを、ネットワークで相互接続するWAN(Wide Area Network)では、昔は電話線を用いていた。電話は、本来音声を伝えるためのものであるため、0/1のデジタル信号を、音の信号に変換(変調)し、受信側は音をデジタル信号に(復調)する。これらを行う機器は、変復調装置(モデム)と呼ばれる。
変調の際には、0/1信号を、音の強弱(振幅変調/AM),音程の高低(周波数変調/FM),位相の前後(位相変調/PM)の組み合わせによって、送受信を行う。参考:ダイヤルアップ接続音(YouTube)
当初は、300bps程度であったが、最終的には64Kbps 程度の通信速度が得られた。(電話線は元々10kHzの音を送るために開発されていたため、64Kbpsが限界だった)
これらの通信速度の改善のため、電話線にデジタル信号で送る ISDN , 電話線の音の信号の高帯域を使った通信 ADSLなどが用いられた。(ADSLでは高周波帯を使うので、自宅から交換機までの距離が長い時は通信速度が速くできなかったりした)
最近では、光ファイバによる FTTH(Fiber To The Home) が広く普及し、1Gbps を越える通信が可能となっている。このほかには、ケーブルテレビ事業者による回線を利用した HFC(Hybrid Fiber-Coaxial) も普及している。HFCでは幹線部分を光ケーブルで接続し、地域の拠点から家庭までは同軸ケーブルで配線することで、テレビ放送とインターネット接続を実現している。
光ファイバ
光ファイバでは、内側(コア)に屈折率の高い透過材料と、外側に屈折率の低い透過材料でケーブルを使い、屈折率の違う断面で全反射することを利用して光を遠くまで運ぶ。中身がガラス繊維なので、中の繊維が折れない工夫や、コネクタで光が減衰しないような工夫が重要。
光ファイバで自宅までネットワーク回線が引かれている場合、光ファイバと自宅内インターネットの間には、ONU(Optical Network Unit/光回線終端装置)が設置されている。一般的にモデムが音の信号を電気的なデジタル信号に変換するのに対し、ONU は光信号をデジタル信号に変換する。音声電話を使う場合には、音声信号をデジタル化して、これをインターネットで通信する VoIP(Voice over IP network) 技術が使われる。
通信速度の理解と、古い時代の通信速度を体験してもらうため、試しに「2000ドット✕1500ドットのRGB画像(1ドット3byte)のデータ(無圧縮)を、9600bps で通信したら、どの程度の時間を要するか、いくらかかるのか?」を計算してみよう。ちなみに2000年頃は、携帯電話では、1Kbyteあたり10円の通信料がかかった。
→答え:
データ量 2000✕1500✕3✕8 [bit] = 72 M[bit]
通信速度 9600[bps] であれば、72 M / 9600 = 7500[sec] = 約2時間(1/5に圧縮されても24分)
通信費 72M[bit]/8/1000 = 9000[Kbyte]、
通信料金 9000[Kbyte]=9000[パケット]、1パケット(1KB)10円だから90,000円 😥
# 画像が320✕240✕RGB(16bit)で圧縮で1/5であれば、それでも100円超え
J-PHONE(J-SH04,200年発売)で始めてカメラ付き携帯が登場。(解像度の低い自撮り写真をスマホで1枚送れば100円かかった時代)
ネットワークトポロジ
ネットワークに機器を接続する形態をネットワークトポロジと言う。
1本の線を共有するバス型、機器どうしがリング型に接続するリング型、中央の機器を通して接続されるスター型が基本となる。
基本的に、Ethernet は 1本の線を機器で共有するバス型。ただし、10BASE-T,100BASE-TX などの HUB で繋がることから、HUB を中心に広がるスター型とも言える。それぞれれのネットワークは相互につながることから、木の枝状に見えるものはツリー型と呼ばれる。また、上流ネットワークでは、機器が故障した場合に一切の通信ができなくなるのは問題があるため、複数のネットワークで相互に接続される。この場合、網が絡むような構造になることから、ネットワーク型と呼ばれる。
データベースの用語など
データベースの機能
データベースを考える時、利用者の視点で分類すると、以下の3つの視点の違いがある。
- データベースの管理者(データベース全体の管理)、
- 応用プログラマ(SQLなどを使って目的のアプリケーションに合わせた処理を行う)、
- エンドユーザ(データベース処理の専門家でなく、DBシステムのGUIを使ってデータベースを操作する)
データベース管理システム(DBMS)では、データとプログラムを分離してプログラムを書けるように、データ操作言語(SQL)で記述する。
また、データは独立して扱えるようにすることで、データへの物理的なアクセス方法があっても、プログラムの変更が不要となるようにする。
データベースは、利用者から頻繁に不定期にアクセスされる。このため、データの一貫性が重要となる。これらを満たすためには、(a) データの正当性の確認、(b) 同時実行制御(排他制御)、(c) 障害回復の機能が重要となる。
これ以外にも、データベースからデータを高速に扱えるためには、検索キーに応じてインデックスファイルを管理してくれる機能や、データベースをネットワーク越しに使える機能などが求められる。
データベースに対する視点
実体のデータをそれぞれの利用者からデータベースを記述したものはスキーマと呼ばれる。そのスキーマも3つに分けられ、これを3層スキーマアーキテクチャと呼ぶ。
- 外部スキーマ – エンドユーザからどんなデータに見えるのか (create view の例)
- 概念スキーマ – 応用プログラマからは、どのような表の組み合わせで見えるのか、表の中身はどのようなものなのか。
- 内部スキーマ – データベース管理者からみて、表の中身は、どのようなファイル名でどのような形式でどう保存されているのか
データモデル
データを表現するモデルには、いくつかのモデルがある。
- 階層型データモデル – 木構造で枝葉に行くにつれて細かい内容
- ユーザ情報を扱うLDAP(Light Weight Directory Access Protocol)は、階層モデルの例
- ディレクトリサービス: コンピュータのリソースの属性や情報のデータベース (Windows の Active Directory)
- ネットワーク型モデル – データの一部が他のデータ構造と関係している。
- 関係モデル – すべてを表形式で表す。
関係データベースの基礎
関係データベースは、1970年頃に、E.F.コッド博士によりデータベースのための数学的な理論が確立された。
1974 – IBM SEQUEL言語開発, Ingres初期型
1977 – ラリー・エリソンらが Oracle の前進となった SDL 社を創業, 1982に Oracle に改称
- 集合 A, B – 様々なデータ
- 直積 A✕B = { (x,y) | x∈A , y∈B } 集合A,Bのすべての組み合わせ
- 関係 R(A,B) すべての組み合わせのうち、関係があるもの。直積A,Bの部分集合
例えば、A={ s,t,u } , B={ p,q } (定義域) なら、
A✕B = { (s,p) , (s,q) , (t,p) , (t,q) , (u,p) , (u,q) }
このうち、Aが名前(sさん,tさん,uさん)、Bが性別(p=男性,q=女性)を表すなら、
R(A,B) = { (s,p) , (t,q) , (u,p) } (例)
(例):(sさん,男性) , (tさん,女性) , (uさん,男性)
前の例を使うなら、集合<学生>, 集合<科目> であり、直積 <学生> ✕ <科目> のうち、実際に受講したという結果が、関係 R( <学生> , <科目> ) に相当する。
SQLの導入
コッドが提唱した関係データベースの理論に基づいて作った Alpha 言語を元に、IBM が SEQUEL を開発したが、商標の問題で SQL と名前が変更された。同じころにコッドらの論文を元に、ラリー・エリソンらにより Oracle が開発されている。
SQLは、データベース管理システム(RDBMS)において、データの操作や定義を行うためのデータベース言語(問い合わせ言語)である。プログラミングにおいてデータベースへのアクセスのために、他のプログラミング言語と併用される。COBOL の影響が大きく英語の文章のような文法となっている。
SQLの機能は、以下の3つに大きく分けられている。
- データ定義言語(Data Definition Language)
- CREATE , DROP , ALTER
- データ操作言語(Data Manipulation Language)
- INSERT INTO , UPDATE…SET , DELETE FROM , SELECT…FROM…WHERE
- データ制御言語(Data Control Language)
- GRANT , REVOKE , COMMIT , ROLLBACK
今回の授業では、Paiza.IO の MySQL 環境を使って演習を行う。
理解確認
- データベースにおける3層スキーマアーキテクチャについて説明せよ
- 集合A,Bが与えられた時、関係R(A,B) はどのようなものか、数学定義や実例をあげて説明せよ。
双方向リストとdeque
deque(両端キュー)
双方向循環リストを使うと、(1)先頭にデータを挿入(addFirst/unshift)、(2)先頭のデータを取り出す(removeFirst/shift)、(3)末尾にデータを追加(addLast/push)、(4)末尾のデータを取り出す(removeLast/pop)、といった処理が簡単に記述できる。この4つの処理を使うと、単純リスト構造で説明した、待ち行列(queue)やスタック(stack) が実現できる。この特徴を持つデータ構造は、先頭・末尾の両端を持つ待ち行列ということで、deque (double ended queue) とも呼ばれる。
先頭への挿入/削除
末尾への挿入削除
import java.util.*; class BDListNode { BDListNode prev ; int data ; BDListNode next ; BDListNode( BDListNode p , int d , BDListNode n ) { this.prev = p ; this.data = d ; this.next = n ; } BDListNode() { this.prev = this ; this.data = -1 ; // dummy this.next = this ; } } public class Main { static void addFirst( BDListNode p , int d ) { p.next = new BDListNode( p , d , p.next ) ; p.next.next.prev = p.next ; } static int removeFirst( BDListNode p ) { int ans = p.next.data ; p.next = p.next.next ; p.next.prev = p ; return ans ; } static void addLast( BDListNode p , int d ) { p.prev = new BDListNode( p.prev , d , p ) ; p.prev.prev.next = p.prev ; } static int removeLast( BDListNode p ) { int ans = p.prev.data ; p.prev = p.prev.prev ; p.prev.next = p ; return ans ; } public static void main(String[] args) throws Exception { BDListNode top = new BDListNode() ; // 先頭で Stack addFirst( top , 11 ) ; addFirst( top , 22 ) ; System.out.println( removeFirst( top ) ) ; System.out.println( removeFirst( top ) ) ; // 末尾で Stack addLast( top , 33 ) ; addLast( top , 44 ) ; System.out.println( removeLast( top ) ) ; System.out.println( removeLast( top ) ) ; // Queue として使う addFirst( top , 55 ) ; addFirst( top , 66 ) ; System.out.println( removeLast( top ) ) ; System.out.println( removeLast( top ) ) ; } }
Javaでの LinkedList(Deque) のクラスの使い方
Javaで Deque のような双方向リスト(2重リスト)を使うには、LinkedList<E> を用いる。クラス宣言などで <E> の内側に型Eを指定する機能はジェネリクスと呼ばれる。クラス名に Deque というのもあるけど、LinkedList などの内部の処理を記述するために使われているものなので、ユーザが直接 Deque クラスを使うことはない。
LinkedList でデータ構造を宣言する場合には、LinkedList<E> のように、どのテータ構造を要素にもつ LinkedList なのかを指定する。ただし int,double といったプリミティブ型を型の欄に書くことはできない。こういった場合には Integer,Double といったオブジェクトを記載すること。
また、リストの要素で繰り返しをする場合には、for( 型 item : LinkedList型 ) {…} のように書けば、繰り返しが記述できる。
import java.util.*; public class Main { public static void main(String[] args) throws Exception { LinkedList<Integer> lst = new LinkedList<Integer>() ; lst.addFirst( 11 ) ; // lst の先頭に11を挿入 lst.addFirst( 22 ) ; // lst の先頭に22を挿入 for( Integer item : lst ) { System.out.println( item ) ; } lst.addLast( 33 ) ; // lst の末尾に33を追加 // 全要素の繰り返し for( Integer item : lst ) { System.out.println( item ) ; } // 先頭を取り出す while( !lst.isEmpty() ) { // isEmpty() : lst の要素が空か判定する System.out.println( lst.removeFirst() ) ; // lstの先頭要素を取り出す } } }
LinkedList クラスは双方向リストだけど、単純リスト専用のクラスは無い。このため、これまでの授業のように自分でクラスを宣言して使う必要がある。
ArrayList クラス
これと同じように自由な配列サイズのデータクラスとして、ArrayListクラスも存在する。以下の例は、ArrayList<Integer> の使用例。
ArrayList はジェネリクスを使った、要素数を増やすことができる配列である。
import java.util.*; public class Main { public static void main(String[] args) throws Exception { ArrayList<Integer> lst = new ArrayList<Integer>() ; lst.add( 11 ) ; lst.add( 22 ) ; for( Integer item : lst ) { System.out.println( item ) ; } lst.add( 33 ) ; for( Integer item : lst ) { System.out.println( item ) ; } for( int x = 0 ; x < lst.size() ; x++ ) { System.out.println( lst.get( x ) ) ; } } }
型推論
上記のプログラムで、LinkedList<Integer> lst = new LinkedList<Integer>() ; で宣言しているが、初期化の右辺と左辺で型を揃える必要があるが、複雑な型だとプログラムが煩雑になる。このため、最近の Java には型推論の機能があるため、下の様に型を省略して記述できる。
LinkedList<Integer> lst = new LinkedList<Integer>() ; // 型推論なし LinkedList<Integer> lst = new LinkedList<>() ; // 後半のIntegerは明らか var lst = new LinkedList<Integer>() ; // lst の型は new LinkedList<Integer> で明らか for( Integer item : lst ) { ... } // 型推論なし for( var item : lst ) { ... } // 型推論でIntegerを省略
LinkedListとArrayListの違い
LinkedList や ArrayList は同じ使い方ができるようにadd(int,E),get(int)クラスメソッド等が定義されている。しかし、LinkedList は双方向リスト、ArrayList は配列を使って実装されているので、同じ名前のメソッドでもそのメソッドの処理時間には、以下のような特徴がある。
処理時間のオーダ | LinkedList | ArrayList | メソッドの機能 |
---|---|---|---|
addFirst(E e) / add(E e) |
O(1) | O(1) | リストの末尾に要素を追加 |
add(int index, E e) | 指定した場所探しにO(N) その場所に挿入O(1) |
指定した場所探しにO(1) その場所に挿入O(N) |
リストの指定したインデックスに要素を追加 |
addFirst(E e) / add(0, E e) | 先頭に挿入O(1) | 先頭に挿入O(N) | リストの先頭に要素を追加 |
E get(int index) | O(N) | O(1) | リストのインデックス番目を参照 |
理解確認
- ジェネリックス ArrayList, LinkedList を使って逆順のリストを作る、最小値を探すプログラムを作成せよ。
LinkedListで逆順,最小値を返す練習問題 - 型推論とは何か?