# SECCON決勝観戦CTF writeup

## Crypto
### Long Flag
FBでした。

`pycryptodome`の`bytes_to_long()`で数値に変換されたFLAGを
元に戻す問題です。`long_to_bytes()`を使えば戻せます。

### tripple
次に説明する問題を先に覗いていたのでtimeは遅め。

RSA暗号で`n=p*q`の代わりに`n=p*p*p`としたものです。
秘密鍵`d`は法`φ(n)` の下での`e`の逆元になります。
https://ja.wikipedia.org/wiki/%E3%82%AA%E3%82%A4%E3%83%A9%E3%83%BC%E3%81%AE%CF%86%E9%96%A2%E6%95%B0

n,c=(272361880253535445317143279209232620259509770172080133049487958853930525983846305005657, 69147423377323669983172806367084358432369489877851180970277804462365354019444586165184)
p=64820957398311054088331897993
phi = p**3- p**2
d = pow(0x10001,-1,phi)
print(long_to_bytes(pow(c,d,n)))

### 42
フラグに42bit素数を42回かけた値が渡されます。
[factordb](https://factordb.com/)に投げると、3,23と大きな数が渡され素因数分解の結果は得られませんでした。
こんなときは https://www.alpertron.com.ar/ECM.HTM を使います。
楕円曲線法や二次篩法によりCTFで解くにはちょうど良い中程度の大きさの素因数分解をしてくれます。
46個の素因数に分解できたので42bitでない4つの数の積がFLAGです。

from Crypto.Util.number import  long_to_bytes
a =[3 , 23 , 2205496470181 , 2219555763769 , 2233425033163 , 2239061295271 , 2259023796727 , 2284404776567 , 2291370145123 , 2416633488457 , 2419508288471 , 2434758174067 , 2500841090549 , 2503738093453 , 2573045476847 , 2680923822481 , 2778916602433 , 2788061078027 , 2796482148853 , 2874516939989 , 3132015040537 , 3139228584347 , 3155640636023 , 3194390562137 , 3284689931333 , 3395646793247 , 3450918694961 , 3542857468897 , 3558548169959 , 3723346041941 , 3734921299007 , 3741754738429 , 3881331302137 , 3955397572079 , 3975840251293 , 4072584462841 , 4130457980197 , 4158189715259 , 4194605058227 , 4207350753019 , 4244137496801 , 4299476105167 , 4327600625807 , 4333485694679 , 64527453873583290390233 , 360296424708927327075211324489217]
print(len(a))
print(long_to_bytes(a[0]*a[1]*a[-1]*a[-2]))

### 42*
こちらは素数関係なく42bitの数が42回かけられます。
ただし、"42"と同様の要領で素因数分解できます。
42bitよりも大きい2つの素因数はFLAGの素因数であることが確定します。
FLAGのbit長が最低148に対し、確定した2つの積から150bitは得られていたので残りはそんなに掛けないだろうと見積り探索したらすぐFLAGになりました。

from Crypto.Util.number import long_to_bytes
from math import prod
from itertools import combinations

a = [2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,7,7,7,7,11,11,11,11,13,13,13,19,19,19,29,29,31,31,37,37,37,41,41,59,73,89,101,113,127,139,167,181,251,313,353,397,421,461,479,521,877,881,1039,1301,1319,2503,4253,4931,5153,5393,6047,7577,11939,13591,14281,15061,16063,17107,34589,79139,136247,542687,699151,5232047,6826271,7940341,8128741,13613293,15013367,16218857,26849519,34568459,44246567,44924899,131319997,159166789,193282213,270757631,441225131,748234759,3959747513,4019043439,8208095579,9261327707,21565514297,25903166119,40170254417,2820984713 , 3453026453 , 7711108879 , 14178556339 , 14955780253 , 260671393973 , 633521692649,5342437369, 7973344633, 27943524131, 51379149413, 613612427189, 2815337843287, 6300966946522285730659, 176828107660926468363751]

o=302825260919317779466638288706941757478119936504864503289299111810878557424069832851837952929397907929396668240458993245662741522591539210493306557224673507192171095532552008396687356525313836501117714017702880902013061423179550493813470620956236263763510927657899587551000326509836294794948423351121777067521675908878203343378571238778872260377769563951765315203164771192344115744888944635103673374760547507150197387248980588584664707496184797486345139870127142403853041203948936595396757260050089360185668376949219377211437731767603055237909466371770346897408000000000000000
print(f"{o.bit_length()=}")
print(f"flag.bit_length() ≒ {len(bin(o)[2:])-42*42}")
assert o == prod(a)
b = a[-1]*a[-2] # 42bitより大きい2つは確定
print(f"{b.bit_length()=}")

s = a[:-2]
n = len(s)
for r in range(n+1):
    for combo in combinations(s, r):
        c = prod(combo) * b
        if b"Alpaca{" in long_to_bytes(c):
            print(long_to_bytes(c))
            exit()

### Customizable EC
惜しくもFBならず。
楕円曲線上の離散対数問題を解く問題です。
楕円曲線のパラメータ`a`,`b`,`p`は自分で選べます。
ただし、`assert 512 <= p.bit_length() < 1024 and 0 <= a < p and 0 <= b < p`を守ること。

- 攻撃方法の選定
- 不正なパラメータを選んで楕円曲線上の離散対数が解かれるパターンはいくつかあります
- Singular curve：楕円曲線でないため今回のEllipticCurve()で作れない
- Anomalous curve：Smart attack, SSSA attack
- Super Singular curve: MOV攻撃, FR攻撃
- 位数がsmooth: pohlig-hellman
->　 **Anomalous curve**を**Smart attack**で解く。
- パラメータの決定
- パラメータ生成ツールを使う(`ecgen 512 --fp --anomalous -r`)
https://github.com/J08nY/ecgen
- ~~過去問を漁る~~
- Smart Attackの準備
- https://github.com/jvdsn/crypto-attacks/blob/master/attacks/ecc/smart_attack.py

import re
from sage.all import *
from ptrlib import *
from Crypto.Util.number import long_to_bytes

load("smart_attack.sage")
p = 0x958f3556872c18f6b198ddc7dbcc35a405d46b3f8dfa2c33e62b504c97cf9c8b8f1942dde1cc2c43fe8a29b307b6dc2da25599dbf5b893acb2afec4c407bbebb
a = 0x1838d8e61de6a3d1a5cb64cbb3ec3b290c5ed648210383bf37989e40f85411857d6e3b9c3f81fca93bf9b5efbe4c6e47ef6ddbecda89854c87a04bedf432c048
b = 0x0dfc9c59b7ffabcdbf6e742fcf1c8be288c41b6138af24ba28048d227b8d627e353dbdc74f2737205602b910ae86bd648d3177b92cb649e839ea50b805b5c9f0

io = Socket("nc 34.170.146.252 41536")
io.sendlineafter(b"Enter p,a,b:", f"{p},{a},{b}".encode())

data = io.recvline().decode()
pattern = r"P=\(\s*(\d+)\s*:\s*(\d+)\s*:\s*(\d+)\s*\),\s*Q=\(\s*(\d+)\s*:\s*(\d+)\s*:\s*(\d+)\s*\)"
match = re.search(pattern, data)
if match:
    Px, Py, Pz, Qx, Qy, Qz = map(int,match.groups())

E = EllipticCurve(GF(p), [a, b])
P = E(Px, Py)
Q = E(Qx, Qy)

print(long_to_bytes(attack(P, Q)))
io.close()

## Others
### Welcome!
問題文のFLAGを提出するだけ。16秒で出しましたが3位でした。

### Can U Keep A Secret?
srcで2回rand()呼び出してるけど配られたバイナリとサーバでは1回っぽい。
>追記
>トライグラフというらしい。へぇ～

### 1linepyjail4b
`[].__class__.__base__.__subclasses__()[158].__init__.__globals__['system']('sh')`
でシェル起動。
158番は多分`os._wrap_close`

### Concurrent Flag Printer
リバースと並行で運が良ければフラグ出るかなと思いプログラム走らせてました。
↓くらい収集した時点でguessできてしまった。

※正解は無いけど..?
Alpaca{vEE]^F[Rku}
Alpaca{rqBZWWJTmu}
Alpaca{HKKBOWORZD}
Alpaca{HEELOWJRLu}
Alpaca{HKBZWOOQhu}
Alpaca{HHELOWJsku}
Alpaca{HEELORLT\D}
Alpaca{rrABORJBZD}

---
Webが弱いことを再認識させられた一方で、面白い問題も結構あって楽しかったです。