TL;DR

  • 自分が与えた点が何倍かされるので、その点をノーヒントで当てる問題
  • 最初に与える点が与えられた曲線に乗っているかどうかのチェックが無い
  • よって、Invalid Curve Attackと同じ要領で別の曲線における位数が非常に小さい点を与える

Prerequisite

  • 楕円曲線上の演算
  • Invalid Curve Attack

Writeup

次のようなスクリプトが動いている。

from collections import namedtuple
import random
from secret import flag
from Crypto.Util.number import inverse
def moddiv(x,y,p):
    return (x * inverse(y,p)) %p
Point = namedtuple("Point","x y")
class EllipticCurve:
    INF = Point(0,0)
    def __init__(self, a, b, p):
        self.a = a
        self.b = b
        self.p = p
    def add(self,P,Q):
        if P == self.INF:
            return Q
        elif Q == self.INF:
            return P

        if P.x == Q.x and P.y == (-Q.y % self.p):
            return self.INF
        if P != Q:
            Lambda = moddiv(Q.y - P.y, Q.x - P.x, self.p)
        else:
            Lambda = moddiv(3 * P.x**2 + self.a,2 * P.y , self.p)
        Rx = (Lambda**2 - P.x - Q.x) % self.p
        Ry = (Lambda * (P.x - Rx) - P.y) % self.p
        return Point(Rx,Ry)
    def multiply(self,P,n):
        n %= self.p
        if n != abs(n):
            ans = self.multiply(P,abs(n))
            return Point(ans.x, -ans.y % p)
        R = self.INF
        while n > 0:
            if n % 2 == 1:
                R = self.add(R,P)
            P = self.add(P,P)
            n = n // 2
        return R
# P256 parameters, secure.
p = 115792089210356248762697446949407573530086143415290314195533631308867097853951
order = 115792089210356248762697446949407573529996955224135760342422259061068512044369
a = -3
b = 41058363725152142129326129780047268409114441015993725554835256314039467401291
E = EllipticCurve(a,b,p)
print("Welcome to my prediction centre!")
print("We're always looking out for psychics!")
print("We're gonna choose a random number. You get to choose a point. We'll multiply that point by our random number.")
print("Since this curve is of perfect and prime order, it'll be impossible to break this test.")
print("Only a psychic could know!")
print("Be psychic, get the flag.")
x = int(input("Enter point x: "))
y = int(input("Enter point y: "))
P = Point(x,y)
n = random.randint(1,order)
Q = E.multiply(P,n)
print("Ok, where do you think the point will go?")
px = int(input("Enter point x: "))
py = int(input("Enter point y: "))
prediction = Point(px,py)
if prediction == E.INF or prediction == P:
    print("Psychics don't use dirty tricks.")
    quit()
if prediction == Q:
    print("Wow! You're truly psychic!")
    print(flag)
    quit()
print("Better luck next time.")
print(f"Point was {Q}")

ある点$P$を入力し、それをP256曲線の上の演算で$n$倍した点$Q \coloneqq nP$を当てたらフラグが開示されるという極めてシンプルな問題。

予想する点として、無限遠点((0,0)として表現される)を提出することは出来ないので$P$を無限遠点として最初に与える戦略は使えない。

ここで、$P$を与える際にP256曲線の上に乗っているかのチェックはされないことから、Invalid Curve Attackが出来る。

これは楕円曲線の乗算の実装においてワイエルシュトラス標準形: $y^2 = x^3 + ax + b$における$b$が使われていないことから、$b$以外のパラメータがP256曲線と同じである別の曲線$E': y^2 = x^3 + ax + b'$における乗算を行わせることが出来ることを利用した攻撃であり、$E'$における位数が小さい点を$P$として提出することで$Q$の取りうる範囲を小さくする事が出来る。

このような$b'$についてだが、$E'$の位数が非常に小さい素数$p$(今回は3)の倍数となるものを選ぶ。この時$|E'| = pc$とおく。

続いて$P$についてだが、$E'$の点の内、位数が$p$の倍数となる点$G$に対して$P \coloneqq cG$を考えると、$pP = p\cdot cG = (pc)G = O$となることから、$P = cG$のスカラー倍は高々$p$通りしか存在しないことになる。

というわけで$P$として$cG$を提出し、今回$p=3$としたから、適当に$2P$を予想として提出すると、1/3の確率で予想が当たることになり、これは十分少ない試行回数で済む。

ちなみに$p=2$とすると、$Q = O \lor Q = P$となり、if prediction == E.INF or prediction == P:で弾かれるため、$p$は2より大きい素数である必要がある。

Code

p = 115792089210356248762697446949407573530086143415290314195533631308867097853951
order = 115792089210356248762697446949407573529996955224135760342422259061068512044369
a = -3
b = 41058363725152142129326129780047268409114441015993725554835256314039467401291

"""
while True:
    _b = randint(0, p)
    curve = EllipticCurve(GF(p), [a,_b])
    order = curve.order()
    if order % 3 == 0:
        print("[+] New Curve is Found!!")
        print(f"{_b=}")
        break

while True:
    G = curve.random_point()
    if G.order() % 3 == 0:
        print("[+] Base point is found!!")
        print(G)
        break
"""

_b = 88443694825587779591313680321433713549896588777673925683600207917849356682984
curve = EllipticCurve(GF(p), [a, _b])
_order = curve.order()
gx = 102459816122588158032348643305719453656933692802540279003958970974159650723689
gy = 15446786386404991716983541540082594001679756541477843162606688224048865729992
G = curve((gx, gy))

r = _order // 3
P = r*G
assert P.order() == 3
px, py = P.xy()

from pwn import remote
sc = remote("localhost", 13337)

sc.recvuntil(b"Enter point x: ")
sc.sendline(str(int(px)).encode())
sc.recvuntil(b"Enter point y: ")
sc.sendline(str(int(py)).encode())

pred = 2*P
qx, qy = pred.xy()
sc.recvuntil(b"Enter point x: ")
sc.sendline(str(int(qx)).encode())
sc.recvuntil(b"Enter point y: ")
sc.sendline(str(int(qy)).encode())
sc.interactive()

Flag

rarctf{w0ah_str4ight_cl41r0v0y4nc3!!_8119733d69}

Resources