Codegate CTF 2020 Finals

September 8, 2020

We are ranked 6th in CODEGATE CTF 2020 Finals. The result is a little disappointing to me, but I think we did our best, so I have no regrets!

My position is crypto and little misc problems.

I solved cloud9, gaemgam, MIC Check, patternmania. I want to write my solutions about cloud9.

cloud9

We've been tricked, we've been backstabbed and we've been quite possibly, bamboozled.

This problem is crypto and gives chall.sage and output. Get this File.

Solution

I studied this attacks about three days before the competition. What a lucky guy.. Actually, I don’t know these two attacks specifically.

We should solve sd, ld. sd is easy to solve.

First, let’s solve sd.

n = 2183
order = 35 # elliptic curve's order
G = (132, 1142)
Q = (910, 1641)

\[Q=sd\cdot G\]

We can get the a and b by substitute G and Q in Elliptic Curve.

a = 940
b = 2178

Just bruteforce the sd! And we can get 2.

Second, let’s solve ld.

We should use Zero-Value Point Attack. I will explain this attack soon.. maybe..

a = 38240914061990796438737366831519229758147826122081713763266278781817042433002
b = 46190729283374747896507274087688474070284211702985162903204546328076483000624

If you multiply order and G, there occurs the error and we can factorize the n.

The reason is that we know if we multiply order and G, the output is Origin. However, n is not a prime so we can’t get the inverse of Origin and get the error instead of Origin.

If \(Q=ld*Q\) in mod n, it also satisfies in mod p and q. So I make the elliptic curve with mod q and I know that order of elliptic curve is same with q!!! If we do smart attack to elliptic curve, we can get ld easily.

Here is my Smart Attack Solution.

n = 5836992596022446937012188954528837967652088799787297418688161952734029742601918639776384293816907277293165804095447608755394244018171460874413413360601287
a = 38240914061990796438737366831519229758147826122081713763266278781817042433002
b = 46190729283374747896507274087688474070284211702985162903204546328076483000624
p = 97940012926710762153437884674079301076391785734843620993390248274679651111717
q = 59597629422310897332995051052435766506780710137496164204389350135087152537211

E2 = EllipticCurve(Zmod(q), [a,b])

G = E2(4791064145174837833113077069599757584947381216841105432787931481123835537923996904590176334618000141035959257993847069760040827648845993882710813263422518, 2007135516277895026771627676893419200766568709594031697039637947675097596595809713825936430608820664600227626467013163201670055105153466868380086912003923)
Q = E2(2906660915459424515040277093002683642589488507112805139726386938933880929506501185082819430093812825540133325640097413100449877310669418449600698325701077, 3812143203765395705358551712573539116980648501774991245491977901798688330759954052153901303962483747022229555022370548381218346760417689877969168781021420)

def HenselLift(P,p,prec):
    E = P.curve()
    Eq = E.change_ring(QQ)
    Ep = Eq.change_ring(Qp(p,prec))
    x_P,y_P = P.xy()
    x_lift = ZZ(x_P)
    y_lift = ZZ(y_P)
    x, y, a1, a2, a3, a4, a6 = var('x,y,a1,a2,a3,a4,a6')
    f(a1,a2,a3,a4,a6,x,y) = y^2 + a1*x*y + a3*y - x^3 - a2*x^2 - a4*x - a6
    g(y) = f(ZZ(Eq.a1()),ZZ(Eq.a2()),ZZ(Eq.a3()),ZZ(Eq.a4()),ZZ(Eq.a6()),ZZ(x_P),y)
    gDiff = g.diff()
    for i in range(1,prec):
        uInv = ZZ(gDiff(y=y_lift))
        u = uInv.inverse_mod(p^i)
        y_lift = y_lift - u*g(y_lift)
        y_lift = ZZ(Mod(y_lift,p^(i+1)))
    y_lift = y_lift+O(p^prec)
    return Ep([x_lift,y_lift])

def SmartAttack(P, Q, p, prec):
    E = P.curve()
    Eqq = E.change_ring(QQ)
    Eqp = Eqq.change_ring(Qp(p,prec))

    P_Qp = HenselLift(P, p, prec)
    Q_Qp = HenselLift(Q, p, prec)

    p_times_P = p*P_Qp
    p_times_Q = p*Q_Qp

    x_P, y_P = p_times_P.xy()
    x_Q, y_Q = p_times_Q.xy()

    phi_P = -(x_P/y_P)
    phi_Q = -(x_Q/y_Q)

    k = phi_Q / phi_P
    k = Mod(k, p)
    return k

print(SmartAttack(G, Q, q, 8))

If you get the ld, make the key with sd and ld and decrypt the encrypted message!

The flag is CODEGATE2020{Here_comes_the_crypto_genius}.

I will update the solution of sculptor soon.