###### tags: `InterKosenCTF` `Crypto`
# [InterKosenCTF|Crypto 300]Slot Machine
スロットでお金を大量に稼ぐタイプの問題。Cryptoで、ソースコード付き
## 動作
つなぐとまずPoWを求められる。`sha256(x).hexdigest()[-5:] == "xyzab"`のようになるalphanumericalなxを求めろとのこと。今回はyoshikingに書いてもらった。
```python=
from hashlib import sha256
import string
import random
y = raw_input(">")
while True:
x = random.sample(string.ascii_table, 10)
if sha256(x).hexdigest()[-5:] == y:
print(x)
break
```
続いてSLOTが始まる。最初は$500を持っていて、1-500までのコインを賭けられる。スロットを遊んで$1000000以上のお金持ちになるとフラグが手に入る。お金がなくなるとゲームオーバー
スロットは中断/再開ができて、中断するとトークンがもらえ、そのトークンを入力することで再開できる。
## 攻略
まともにスロットをやるのは効率的ではないので、不正なトークンを作ってお金を増やせないかを試してみる。そのために、トークンの生成アルゴリズムを見る。処理が短いのでソースコードをそのまま貼り付ける。
```python=
import base64
from fastecdsa.asn1 import _asn1_public_key
from fastecdsa.curve import P256
from fastecdsa.point import Point
from secret import a, b, c, prime
def sign(m):
""" Calculate a signature for the money """
G, q = P256.G, P256.q
if m >= q:
raise ValueError("Too large value to sign.")
if m <= -q:
raise ValueError("Too small value to sign.")
sign = 1 if m >= 0 else -1
P, Q, R = sign*a*G, sign*b*G, c*G
S = pow(m, prime, q)*G + m*m*P + m*Q + R
enc = _asn1_public_key(S)
return base64.b64encode(enc)
def save_token(money):
""" Save a signed token """
return str(money) + '@' + sign(money)
def load_token(token):
""" Load a signed token """
try:
money, signature = token.split('@')
if money < 0:
raise ValueError("Something is wrong.")
if sign(int(money)) == signature:
return int(money)
except:
pass
return None
```
見ると、楕円曲線暗号で暗号化・復号することで所持金が改竄されていないかどうかを確かめている。楕円曲線で使われているパラメータ`P256.G`, `P256.q`は有名なもので既知、対して `a`, `b`, `c`, `prime`はわからないので同様に`P`, `Q`, `R`や`pow(m, prime, q) * G`も不明になっている。
## 楕円曲線の性質
唐突に復習する
- 楕円曲線は2次元平面上の点の演算
- つまり各値は(x, y)の二つのパラメータを持っている
- 楕円曲線上の点X, Y, 定数C、楕円曲線の位数qがあったとき
- X + Y, X - Yはできる
- X*Y, X / Y はできない
- CXやX/Cはできる
- CX/X はできない
- 当然 C + X はできない
- q*X = 0(0は無限遠点=単位元)
- すなわち係数kについて k = k mod q
## P, Q, Rを求める
何がうれしいのかは置いておいてとりあえずP, Q, Rを求める。普通は求まらないんだけど今回は求まる。sign関数でmが負の値の場合を考慮していることからもわかるが、実はBETの処理が不十分で、自分が持っている以上のお金をBETして所持金をマイナスにすることができる。これを使って money=1とmoney=-1の場合のトークンを手に入れると次のようになる。TOKEN(-1)の第一項が(q-1)Gとなるのは$(-1)^{prime} \equiv -1 \equiv q - 1 \mod q$よりわかる。
$TOKEN(1) = G + P + Q + R$
$TOKEN(-1) = (q-1)G - P + Q + R$
ここで`q`と`G`は既知なので`G`と`(q-1)G`を求めることが出来るから$2P$が手に入る。
$(TOKEN(1) - G) - (TOKEN(-1) - (q-1)G) = 2P$
$2*x \equiv 1 \mod q$となるようなxを求めて、$2xP = P$より2PからPが求まる。xの値は2x=q+1より$x=\frac{q+1}{2}$として決められる。
また、 $TOKEN(0) = R$よりRがもとまり、これによってG, P, Rが既知になるので$TOKEN(1) - G - P - R = Q$となる
## 不正なトークンを作る
$(q-1)G$を知っているので次のように不正なトークンを作ることが出来る。これで$(q-1)を不正に入手できるのでフラグを取れるはず
$TOKEN(q-1) = (q-1)G+(q-1)^2P+(q-1)Q+R$
$(q-1)^{prime} \equiv q-1 \mod q$ は次のように導出できる。
$(q-1)^{prime} \equiv (-1)^{prime} \equiv q-1 \mod q$
## 計算する
```python=
import base64
import import asn1
from fastecdsa.asn1 import _asn1_public_key
from fastecdsa.curve import P256
from fastecdsa.point import Point
def decode(token):
decoder = asn1.Decoder()
decoder.start(base64.b64decode(token)
_, value = decoder.read()
value = value.lstrip(b'\x00\x04')
x = int(hexlify(value[:len(value) // 2]), 16)
y = int(hexlify(value[len(value) // 2:]), 16)
return Point(x, y, curve=P256)
P, q = P256.G, P256.q
TOKEN_ONE = decode("...snip...")
TOKEN_ZERO = decode("...snip...")
TOKEN_MINUS = decode("...snip...")
P = ((TOKEN_ONE - G) − (TOKEN_MINUS − (q−1)*G)) * ((q + 1) / 2)
R = TOKEN_ZERO
Q = TOKEN_ONE - G - P - R
q_1 = TOKEN_MINUS + P - Q - R
PAYLOAD = q_1 + (q-1)*(q-1)*P + (q-1)*Q + R
print(str(q - 1) + '@' + base64.b64encode(_asn1_public_key(PAYLOAD)))
```