車輪の再開発ブログ

Python & CTF Beginner!

72の法則の誤差

72の法則の証明・・・(?)

先日、ふと、72の法則って、どれくらい正しい(近似的に正しい)のかなと思い、ググってみると、下の記事?サイト?が、ヒットして、読んでみました。

非常にわかりやすかったです。

www.mathwills.com

しかし、読んで、引っかかったところがありました。

説明を読んでいると、誤差を生み出す場所が、2ヶ所あります。

  •  \ln(1+x) \approx x の近似 (以下、近似1と呼ぶ)
  •  2\ln(100) \approx 69 への近似(以下、近似2と呼ぶ)

特に、近似1は、xが小さい時は成り立つ(誤差が小さい)のだけれども、利率rとして、r/100 が十分小さいのかどうかというところだ。

一応、この法則の利用想定の利率としては、1%から10%ぐらいの値なのだと思う。

1%なら0.01なので2桁違うからそこそこ小さいけど、10%だと0.1なので、1桁ぐらいなので、微妙なんじゃないかなと思いました。

数値計算

そこで、数値的に調べてみましょう。ということで、numpyとmatplotlibで、えいやと書いてみました。コードはgistにあげるかも。

比較対象は、

  • 近似なし
  •  \ln(1+x) \approx x の近似したもの(近似1を適用)
  • 72の法則 (  \frac{72}{r} )
  • 69の法則 (  \frac{69}{r} )(近似1と近似2を適用)

の4つです。 結果は以下の通り。

左図が全体で、右図は、利率が8%のところを拡大した図です。

全体としては、3つの近似ともに、近似なしと似た曲線をちゃんと描いているように見えます。 利率8%前後でみると、72の法則は、 ln(1+x) = xの近似、69の法則よりも、近似なし(青線)に近いことがわかります。

近似2だけでみると、72よりも69の方が正確なのですが、その前段階で、もっと大きい誤差があるよ、ということなのだと思います。

もう少し詳しく結果を確認したいと思います。 y軸を「2倍になる年数」で表示すると、線の順番がわかりにくいので、絶対誤差を表示させたいと思います。つまり、「|近似の値 ー 近似なしの値|」です。 この絶対値が小さいほど、より正確であるということです。

金利の小さいところ(3.5%ぐらいまで)では、「69の法則」の方が、「72の法則」よりも、誤差が小さい(精度が高い)であることがわかります。 逆に、3.5%ぐらいよりも大きいところでは、「72の法則」の方が、「69の法則」よりも誤差が小さいことがわかります。

実は、72のほうが割り算しやすいという勝手な理由で69を72で近似しているのだ。

こうとも言い切れなくて、4%から12%とかの範囲で使う場合は、72の方がより正確のようです。

では、72や69といった反比例の係数は、どのように影響するのだろうかということが気になったので、68から73の各法則を計算してみました。 今度は、絶対誤差ではなくて、単に誤差です。「近似の値 ー 近似なしの値」。(プラスであれば、実際よりも、年数が長めに算出されるという意味です。)

※線の色が、今までのものと違うところに注意。

どの法則が好きですか?

picoCTF 2022 unpackme

コンテスト中に解けなかった問題の復習です。

問題

Can you get the flag? Reverse engineer this binary.

バイナリファイル(unpackme-upx)がダウンロードできる。

ヒント

What is UPX?

解法

まず、UPXとはなんぞやということなのですが、

ja.wikipedia.org

みたいです。Ghidraで解析する前に、展開してあげたあげれば、良いらしいです。

https://ja.wikipedia.org/wiki/UPX

まずは、インストール方法は、単純で、aptでupxとやる。

$ apt -y install upx

これで、upxコマンドが使える。

ダウンロードしたファイルを、decompressするには、-dオプションを使う。

# upx -d unpackme-upx 
                       Ultimate Packer for eXecutables
                          Copyright (C) 1996 - 2018
UPX 3.95        Markus Oberhumer, Laszlo Molnar & John Reiser   Aug 26th 2018

        File size         Ratio      Format      Name
   --------------------   ------   -----------   -----------
   1002408 <-    379116   37.82%   linux/amd64   unpackme-upx

Unpacked 1 file.

これを、Bbbboatと同じように、Ghidraにかける。

で、kusuwada先生のアドバイス picoCTF2022 [Reverse Engineering] writeup - 好奇心の足跡 にしたがって、

Exportsの中の、main関数を見つける。

ここに、0xb83cb、つまり、754635 が見つけたい数値となる。

で、

# ./unpackme-upx 
What's my favorite number? 754635
picoCTF{up><_m3_f7w_5769b54e}

をして、(Ghidraの使い方がよくわからないとかいろいろあるけど、とりあえず)flagゲット!

picoCTF 2022 Bbbbloat

コンテスト中に解けなかった問題の復習です。

問題

Can you get the flag? Reverse engineer this binary.

バイナリファイル(bbbbloat)がダウンロードできる。

ヒント

なし

解法

他の人のWriteupを入れると、Ghidraを入れて、それを使えばOKみたいななのが多かったのですが、Ghidraを使ったことがないので、まずはインストールするところから。

https://ghidra-sre.org/ のトップページから、Githubに飛んで、.zipをダウンロードする。適当なフォルダに、展開する。

次に、Javaを準備する。自分は、homebrewのインストール自体は済んでいる状態だったので、

qiita.com

を参考にしながら、Javaを入れる。途中で、sudoしたりした。

$ java --version
openjdk 18.0.1 2022-04-19
OpenJDK Runtime Environment Homebrew (build 18.0.1+0)
OpenJDK 64-Bit Server VM Homebrew (build 18.0.1+0, mixed mode, sharing)

Javaが入った状態で、ghidraのディレクトリにあるディレクトリで、

./ghidraRun

をする。

で、ここから、Ghidraを適当なプロジェクトで開くが、何が表示されているのか、さっぱりわからない。

クリックしていると、「開発元を検証できないため開けません」が出てきて、うまく動かないので、

macOSからアプリに起動すると「開発元を検証できないため開けません。」と表示 | IODATA アイ・オー・データ機器

を参考にして、decompileを利用できるようにすると、画面の右端に、ソースが表示されるようになった!!!(ここまでがすごく長かった)。

entryから、呼び出しているファンクションを見つけて、入力を読み取っているであろう場所を探すと、

があって、local_48が0x86187、つまり、549255 のときでOKの模様。

実際に動かして、549255を入力して、フラグゲット!

picoCTF 2022 Torrent Analyze writeup

コンテスト中に解けなかった問題の復習です。

問題

SOS, someone is torrenting on our network. One of your colleagues has been using torrent to download some files on the company’s network. Can you identify the file(s) that were downloaded? The file name will be the flag, like picoCTF{filename}. Captured traffic.

ヒント

Download and open the file with a packet analyzer like Wireshark.

You may want to enable BitTorrent protocol (BT-DHT, etc.) on Wireshark. Analyze -> Enabled Protocols

Try to understand peers, leechers and seeds. Article

Articleのリンク What are seeds, peers and leechers in Torrents' language?

The file name ends with .iso

解法

まず、DeepLに問題文の翻訳をお願いします。

SOS、誰かが私たちのネットワーク上でtorrentしています。あなたの同僚の一人が、会社のネットワーク上でtorrentを使用していくつかのファイルをダウンロードしています。ダウンロードされたファイルを特定できますか?ファイル名はpicoCTF{filename}のようなフラグになります。捕捉されたトラフィック

そもそも、torrentってなんだろうと思ったので、少しググって知識を仕入れる。

ヒントにあった peers, leechers, seedsの記事を読む。 DeepL翻訳を貼っておく。

シードとは、クライアントでトレントファイル(あなたがダウンロードしようとしているのと同じファイルとします)を開いている人のことで、あなたと彼らの唯一の違いは、彼らはすでにダウンロードした完全なファイルを持っていて、今「シード」していること、つまり、ピアとファイルを共有しているが、他の人からファイルのどの部分もダウンロードしていないことです。

ふむふむ。

リーチャーとは、ダウンロードとアップロードを同時に行っている人のことを指します。ユーザーがすでに持っているファイルの共有を開始し、他のユーザーがすでにアップロードしたもの、またはトレントファイルをアップロードしている最中のものをダウンロードすると、そのユーザーはリーチャーになります。

むむむ。

ピアとは、スウォームでファイルのダウンロードとアップロードの両方を行う人のことです。ファイルは断片的にダウンロードされます。ダウンロードしたファイルをアップロードすると、自動的にアップロードが始まります。

あんまり分からないけど、flagを得るには、pcapのファイルから、torrentが使われているファイル名を特定するということらしい。

全然、わからないので、他の人のwriteupを読む。

もう一つ、このpcapファイルの中にファイル名を見つけることはできません。これは少し難しいです。トレントについて読めば、遅かれ早かれ、トレントファイルのSHA1合計であるinfo_hashという用語に行き着くことでしょう。それを調査してみましょう!

とのこと。pcapファイルには、flagになるファイル名は含まれていないので、info_hashを見つけるのが先になると。なるほど。けど、Wiresharkプロトコルのところに、BT-DHT なんて現れない・・・。kusuwada先生のwriteupを参考にすると・・・

さっきもUDPしかヒットしなかったし、BT-DHTとその下の bittorrent_dht_udpをポチッと有効にしてみました。

これで、とりあえず、ProtocolにBT-DHTが表示されるようになりました。

これで、あとは、1つ目のwriteupに書かれているように、 info_hash を見つけて、ググれば・・・ https://www.google.com/search?q=e2467cbf021192c241367b892230dc1e05c0580e ubuntuのisoがヒットします。

これを、フラグとして提出すればOK!

picoCTF 2022 SideChannel writeup

コンテスト中に解けなかった問題の復習です。

問題

There's something fishy about this PIN-code checker, can you figure out the PIN and get the flag?
Download the PIN checker program here pin_checker
Once you've figured out the PIN (and gotten the checker program to accept it), connect to the master server using nc saturn.picoctf.net 52680 and provide it the PIN to get your flag.

pin_checkerがダウンロードできる。

ヒント

Read about "timing-based side-channel attacks."
Attempting to reverse-engineer or exploit the binary won't help you, you can figure out the PIN just by interacting with it and measuring certain properties about it.
Don't run your attacks against the master server, it is secured against them. The PIN code you get from the pin_checker binary is the same as the one for the master server.

解法

ダウンロードしたファイルを、 file で確認する。

# file pin_checker 
pin_checker: ELF 32-bit LSB executable, Intel 80386, version 1 (SYSV), dynamically linked, interpreter /lib/ld-linux.so.2, stripped

(32-bitなので、dockerで、32-bitを動かせるようにしておいてから)

# chmod +x pin_checker 

# ./pin_checker 

これで、とりあえず、動かすことができた。

さっぱりわからなので、ヒントの サイドチャネル攻撃 - Wikipedia を読んでみる。

攻撃手法の雰囲気はわかったけど、この問題をどのように解くのかまでは、さっぱりということで、kusuwada先生の picoCTF2022 [Forensics] writeup - 好奇心の足跡 を読む。

実行時間に当たりをつけて、プログラムを実行していくことになるらしい。

プログラムの実行速度を測ると、最上位の桁を0から9に動かしながら、(00000000から90000000)を実行すると、明らかに、1つだけ、時間がかかっていた。 ということで、正解するほど、実行時間がかかると予想して、一番時間がかかった数字を、その桁に固定しながら、10x8の総当たりを実行する。

import time
import subprocess

pin = [0, 0, 0, 0, 0, 0, 0, 0]
for i in range(8):
    max_time = 0
    for j in range(10):
        pins = "".join(map(str, pin[0:i] + [j] + [0 for k in range(7-i)]))

        start = time.time()
        ret = subprocess.run(["./pin_checker"], input=pins+"\n", text=True, capture_output=True)
        elapsed_time = time.time() - start
        print(pins, elapsed_time)

        if max_time < elapsed_time:
            pin[i] = j
            max_time = elapsed_time
    print(i, pin)
print("".join(map(str, pin)))
... 略 ...
48390510 1.034353494644165
48390511 1.0456459522247314
48390512 1.0493018627166748
48390513 1.1346185207366943
48390514 1.0250821113586426
48390515 1.032979965209961
48390516 1.0264122486114502
48390517 1.066084861755371
48390518 1.0343708992004395
48390519 1.0656943321228027
7 [4, 8, 3, 9, 0, 5, 1, 3]
48390513

となり、pinが出てきた。実際に、pin_checkerに渡してみると、

# echo 48390513 | ./pin_checker
Please enter your 8-digit PIN code:
8
Checking PIN...
Access granted. You may use your PIN to log into the master server.

で、OKと。あとは、実際のサーバーで、同じPINを渡してやれば、フラグゲット。

picoCTF 2022 Operation Orchid writeup

コンテスト中に解けなかった問題の復習です。

問題文

Download this disk image and find the flag. Note: if you are using the webshell, download and extract the disk image into /tmp not your home directory.

* Download compressed disk image

リンクから disk.flag.img.gz がダンロードできる。

ヒント

なし

解法

まずは、ファイルを展開する。

# gunzip disk.flag.img.gz

# ls
disk.flag.img

sleuthkit を使って、探し出す。全体を、mmlsで確認。

# mmls disk.flag.img 
DOS Partition Table
Offset Sector: 0
Units are in 512-byte sectors

      Slot      Start        End          Length       Description
000:  Meta      0000000000   0000000000   0000000001   Primary Table (#0)
001:  -------   0000000000   0000002047   0000002048   Unallocated
002:  000:000   0000002048   0000206847   0000204800   Linux (0x83)
003:  000:001   0000206848   0000411647   0000204800   Linux Swap / Solaris x86 (0x82)
004:  000:002   0000411648   0000819199   0000407552   Linux (0x83)

構成的には、 Sleuthkit Apprentice と同じようだった。 /root/flag.txt.enc がすぐに見つかる。

fcat -o 0000411648 /root/flag.txt.enc disk.flag.img すると、 Salted__ から始まる文字列がある。はて、どうしたものか。

picoCTF2022 [Forensics] writeup - 好奇心の足跡 を読む。 なるほど、 .ash_history も関係があるのか。

/root/ディレクトリには、

# fls -o 0000411648 disk.flag.img 472
r/r 1875:   .ash_history
r/r * 1876(realloc):    flag.txt
r/r 1782:   flag.txt.enc

があり、 .ash_history を覗いてみると・・・

# fcat -o 0000411648 /root/.ash_history disk.flag.img 
touch flag.txt
nano flag.txt 
apk get nano
apk --help
apk add nano
nano flag.txt 
openssl
openssl aes256 -salt -in flag.txt -out flag.txt.enc -k unbreakablepassword1234567
shred -u flag.txt
ls -al
halt

となっている。 flag.txt.enc を利用して、decodeして戻してあげれば良さそう。

# fcat -o 0000411648 /root/flag.txt.enc disk.flag.img > flag.txt.enc
# openssl aes256 -d -salt -in flag.txt.enc -out flag.txt -k unbreakablepassword1234567
*** WARNING : deprecated key derivation used.
Using -iter or -pbkdf2 would be better.
bad decrypt
139926876464448:error:06065064:digital envelope routines:EVP_DecryptFinal_ex:bad decrypt:../crypto/evp/evp_enc.c:610:

エラーが出たけど、

# cat flag.txt
picoCTF{h4un71ng_p457_1d02081e}

が得られた。

picoCTF 2022 Operation Oni writeup

コンテスト中に解けなかった問題の復習です。

問題文

Download this disk image, find the key and log into the remote machine.
Note: if you are using the webshell, download and extract the disk image into /tmp not your home directory.
* Download disk image
* Remote machine: ssh -i key_file -p XXXXXX ctf-player@saturn.picoctf.net

XXXXは伏字。 圧縮されたイメージファイル ( disk.img.gz ) がダウンロードできる。

ヒント

なし

解法

全く手も足も出なかったので、kusuwada先生のwriteup picoCTF2022 [Forensics] writeup - 好奇心の足跡 を読む。

ふむふむ。ざっくりとした流れは、「ディスクイメージの中に秘密鍵があるので獲得して、用意されたリモートサーバーにsshで入る」っぽい。

(ここで、自分の英語力がないことが発覚。「find the key and log into the remote machine.」って、「キーとログをリモートサーバーの中から探せ」じゃなくて、「keyを見つけて、リモートマシーンにログインせよ」なんですね。下のコマンドにも、key_fileって書いてくれてるし・・・。すごい親切な問題じゃん。)

ということで、まずは、秘密鍵を取り出すところから。

まずは、gz展開をする。

# gunzip disk.img.gz

# ls
disk.img

sleuthkit を使って、探し出す。全体を、mmlsで確認。

# mmls disk.img 
DOS Partition Table
Offset Sector: 0
Units are in 512-byte sectors

      Slot      Start        End          Length       Description
000:  Meta      0000000000   0000000000   0000000001   Primary Table (#0)
001:  -------   0000000000   0000002047   0000002048   Unallocated
002:  000:000   0000002048   0000206847   0000204800   Linux (0x83)
003:  000:001   0000206848   0000471039   0000264192   Linux (0x83)

003の中身は、

# fls -o 0000206848 disk.img 
d/d 11: lost+found
d/d 12: boot
d/d 13: etc
d/d 79: proc
d/d 80: dev
d/d 81: tmp
d/d 82: lib
d/d 85: var
d/d 94: usr
d/d 104:    bin
d/d 118:    sbin
d/d 458:    home
d/d 464:    media
d/d 468:    mnt
d/d 469:    opt
d/d 470:    root
d/d 471:    run
d/d 473:    srv
d/d 474:    sys
V/V 33049:  $OrphanFiles

今回は、writeupを読んで、場所を知っているので、root ディレクトリ(470) の .ssh ディレクトリ (3916)の中身が

# fls -o 0000206848 disk.img 3916
r/r 2345:   id_ed25519
r/r 2346:   id_ed25519.pub

と辿ります。 id_ed25519 があるので、key_fileとして出力しておきます。

# fcat -o 0000206848 /root/.ssh/id_ed25519 disk.img > key_file

(ここで、sshがdockerに入っていないことがわかったので、apt intall sshをした。)

ssh -i key_file -p XXXXX ctf-player@saturn.picoctf.net

をすると、

# ssh -i key_file -p 59214 ctf-player@saturn.picoctf.net
The authenticity of host '[saturn.picoctf.net]:59214 ([18.217.86.78]:59214)' can't be established.
ECDSA key fingerprint is SHA256:0L/+wJ14/Sk4s6Ue+TxXnAW7qNBuaMeIxA9dXp2zzaU.
Are you sure you want to continue connecting (yes/no/[fingerprint])? yes
Warning: Permanently added '[saturn.picoctf.net]:59214,[18.217.86.78]:59214' (ECDSA) to the list of known hosts.
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
@         WARNING: UNPROTECTED PRIVATE KEY FILE!          @
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
Permissions 0644 for 'key_file' are too open.
It is required that your private key files are NOT accessible by others.
This private key will be ignored.
Load key "key_file": bad permissions
ctf-player@saturn.picoctf.net's password: 

とkey_fileのファイルの権限がオープンすぎるぞ怒られたので、

chmod 600 key_file

をしてやり直すと、ログインできました。

ログイン後は、

ctf-player@challenge:~$ ls
flag.txt
ctf-player@challenge:~$ cat flag.txt 
picoCTF{k3y_5l3u7h_339601ed}

に鍵があります。