SECCON CTF 2023 quals

全然時間が取れず，時間内には何も解けなかった．時間切れになってからいくつか取り組んでみたのでその記録．

cryptoのplai_n_rsaは時間内にワンチャンあったけど，結局ロジックをミスって時間内に処理が終わらなかったのが心残り．

# crypto

## plai_n_rsa

個人的に一番簡単な問題．

### 問題

- RSA暗号の複合
- 本来秘匿されるべきdは与えられているがnが与えられていない
- nを特定する問題

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/245540/4a63fdf0-1c3e-f092-ff14-e3d086cc0bdf.png" width="50%" />


```problem.py
import os

from Crypto.Util.number import bytes_to_long, getPrime

flag = os.getenvb(b"FLAG", b"SECCON{THIS_IS_FAKE}")
assert flag.startswith(b"SECCON{")
m = bytes_to_long(flag)
e = 0x10001
p = getPrime(1024)
q = getPrime(1024)
n = p * q
e = 65537
phi = (p-1)*(q-1)
d = pow(e, -1, phi)
hint = p+q
c = pow(m,e,n)

print(f"e={e}")
print(f"d={d}")
print(f"hint={hint}")
print(f"c={c}")
```

```output.txt
e=65537
d=15353693384417089838724462548624665131984541847837698089157240133474013117762978616666693401860905655963327632448623455383380954863892476195097282728814827543900228088193570410336161860174277615946002137912428944732371746227020712674976297289176836843640091584337495338101474604288961147324379580088173382908779460843227208627086880126290639711592345543346940221730622306467346257744243136122427524303881976859137700891744052274657401050973668524557242083584193692826433940069148960314888969312277717419260452255851900683129483765765679159138030020213831221144899328188412603141096814132194067023700444075607645059793
hint=275283221549738046345918168846641811313380618998221352140350570432714307281165805636851656302966169945585002477544100664479545771828799856955454062819317543203364336967894150765237798162853443692451109345096413650403488959887587524671632723079836454946011490118632739774018505384238035279207770245283729785148
c=8886475661097818039066941589615421186081120873494216719709365309402150643930242604194319283606485508450705024002429584410440203415990175581398430415621156767275792997271367757163480361466096219943197979148150607711332505026324163525477415452796059295609690271141521528116799770835194738989305897474856228866459232100638048610347607923061496926398910241473920007677045790186229028825033878826280815810993961703594770572708574523213733640930273501406675234173813473008872562157659306181281292203417508382016007143058555525203094236927290804729068748715105735023514403359232769760857994195163746288848235503985114734813
```

### 自分の解法

$hint = p + q$ なので，

$$ n = phi + hint - 1 $$

$n$ を特定するために $phi$ を見つけ出す問題．
以下の関係を利用する．

$$ ed - 1 \equiv 0 \quad (\text{mod} \ phi) $$

$$ \exists k \quad s.t. \quad ed - 1 = phi * k $$

ポイントとしては，上記式で $phi$ と $k$ を比べたときに明らかに $k$ の方が小さいから， $k$ で総当りしたほうが早く済む．  
この問題は解法がすぐに思いついて，これだけなら時間内に行けそう，と思ったけれど，最初 $phi$ で総当りしてたら結局間に合わなかった．  
時間切れになったあと，効率いい方法模索する中でこのことに気づいた．  
数学的な式をどういうロジックで組むか，というところでまだまだ修行が必要だと思わされた．

```solve.py
from Cryptodome.Util.number import long_to_bytes

e=65537
d=15353693384417089838724462548624665131984541847837698089157240133474013117762978616666693401860905655963327632448623455383380954863892476195097282728814827543900228088193570410336161860174277615946002137912428944732371746227020712674976297289176836843640091584337495338101474604288961147324379580088173382908779460843227208627086880126290639711592345543346940221730622306467346257744243136122427524303881976859137700891744052274657401050973668524557242083584193692826433940069148960314888969312277717419260452255851900683129483765765679159138030020213831221144899328188412603141096814132194067023700444075607645059793
hint=275283221549738046345918168846641811313380618998221352140350570432714307281165805636851656302966169945585002477544100664479545771828799856955454062819317543203364336967894150765237798162853443692451109345096413650403488959887587524671632723079836454946011490118632739774018505384238035279207770245283729785148
c=8886475661097818039066941589615421186081120873494216719709365309402150643930242604194319283606485508450705024002429584410440203415990175581398430415621156767275792997271367757163480361466096219943197979148150607711332505026324163525477415452796059295609690271141521528116799770835194738989305897474856228866459232100638048610347607923061496926398910241473920007677045790186229028825033878826280815810993961703594770572708574523213733640930273501406675234173813473008872562157659306181281292203417508382016007143058555525203094236927290804729068748715105735023514403359232769760857994195163746288848235503985114734813

k = 1
while True:
    if (e*d - 1) % k == 0:
        phi = (e * d - 1) // k
        n = phi + hint - 1

        m = pow(c, d, n)

        try:
            word = long_to_bytes(m).decode()

            if 'SECCON' in str(word):
                print(f"phi={str(phi)}")
                print(f"n={str(n)}")
                print(f"m={str(m)}")
                print(word)
                # SECCON{thank_you_for_finding_my_n!!!_GOOD_LUCK_IN_SECCON_CTF}
                break
        except:
            pass

    k += 1
```

# misc

## readme

### 問題

なんとかしてflag.txtの中身を読み取れ，という問題．
docker起動してローカルで起動できるようになっていた．python環境なくでも動かせるから助かる．（実際はあるけどバージョン違いとか面倒だし）

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/245540/c8486733-8b27-5bcb-5e8e-a33add4a3609.png" width="50%" />


```server.py
import mmap
import os
import signal

signal.alarm(60)

try:
    f = open("./flag.txt", "r")
    mm = mmap.mmap(f.fileno(), 0, prot=mmap.PROT_READ)
except FileNotFoundError:
    print("[-] Flag does not exist")
    exit(1)

while True:
    path = input("path: ")

    if 'flag.txt' in path:
        print("[-] Path not allowed")
        exit(1)
    elif 'fd' in path:
        print("[-] No more fd trick ;)")
        exit(1)

    with open(os.path.realpath(path), "rb") as f:
        print(f.read(0x100)) 
```

```flag.txt
FAKECON{******* FIND ME ON REMOTE SERVER *******} 
```

### 解決のためにやったこと

知識がなくて解決まで時間がかかり時間内に解けなかった．
mmapの処理が気になって，設問に不備が出ないようにflag.txtの存在チェックしてるだけなのかな，と思ったんだけれど，どうしても気になったからその辺からなんとかしようと考えた．

https://qiita.com/Yusuke_Pipipi/items/bf6ebeb22404c3d3e814

とりあえずこの記事をざっくり読んで，共有メモリっていうことは，メモリ領域に情報入ってるんじゃないか？　ということまでは時間内に分かったんだけど，じゃあどうする，というあたりが全然．

最終的には他の人のwriteupを見てアプローチ自体は理解したけど，まだきちんとは分かっていない．