TUM CTF 2016 - hiecss

RSA signature over an unknown elliptic curve.

Description

Our intern insisted on designing an elliptic-curve signature scheme. Needless to say, it went… quite wrong.He is now back at brewing coffee all day long.

nc 130.211.200.153 25519

download

Details

Points: 150 Basepoints + 200 Bonuspoints * min(1, 3/27 Solves)

Category: crypto

Validations: 27

Solution

According to the script we have to input the server a message \(m\) and a corresponding valid signature \(S\). The signature has to be 64 byte long. The signature is verfified by computing \(h = \textrm{SHA}_{\textrm{256}}(m)\). Then the point \(H\) on the elliptic curve with axis coordinate \(h\) is multiplied by \(e = 65537\). If the resulting point has its \(x\) coordinate matching \(S\) then the signature is valid.

The signature is verified over an elliptic curve howevever, the parameters of the curve are read from a file curve.txt which is not available to us. When I saw the connection parameters, I noticed that the port is 25519 so I thought that the server is using the parameters of the Curve25519 but I was wrong. Nevertheless, the first check of the script is to test is the signature is bigger than the prime \(q\) which defines the underling finite field. Thus I could find \(q\) with a simple binary search:

#!/usr/bin/env python3

import socket
import binascii

tooBigMsg = b'\x1b[31mbad signature\x1b[0m\n'
upperNum = 0x24FB57DBA1EEA9BC3E660A909D838D726E3BF623D52620282013481D1F6E5377
lowerNum = 1

s = socket.socket()
host = "130.211.200.153"
port = 25519 
s.connect((host, port))

while upperNum - lowerNum > 3 :
    m = (upperNum + lowerNum) // 2
    s.send(binascii.hexlify(m.to_bytes(0x20, "big")) + b"\n")
    rsp = s.recv(1024)
    
    if rsp == tooBigMsg:
        upperNum = m+1
    else:
        lowerNum = m-1
    
print(m)
s.close()

which outputs \(q=16503925798136106726026894143294039201809205899921475051089186096065043153559\) Then I could starts playing with the server. I sent the signature \(0\) and it outputs:

$ nc 130.211.200.153 25519
0000000000000000000000000000000000000000000000000000000000000000Give me the flag. This is an order!
bad signature: (0x0, 0x18aae6ca595e2b030870f49d1aa143f4b46864eceab492f6f5a0f0efc9c90e51)

Meaning that \(P = (0, 11157465223991239684062113655986352032428557288843673787383336400593609100881)\) is a valid point of the curve. Since the and elliptic curve follows the Weierstrass equation

\[E:y^2=x3+ax+b\]

We have from the previous point \(b = \sqrt{y_P} = 8575167449093451733644615491327478728087226005203626331099704278682109092640\)

Then by trial and error I found another valid point \(Q = (454086624460063511464984254936031011189294057512315937409637584344757371137, \\ 11208099281518563318368897553609546096980221818831719178800111818393340854694)\)

Wich allows to recover the value of \(a\):

\[a = \frac{y_Q^2 - x_Q^3 - b}{x_Q} = 5079713781418039671549386476218981709382212150018593601284925328028384622133\]

At this point, the curve \(E\) was completly defined. The valid signature is given by the point \(D = d \cdot H\) such that

\[e \cdot d \cdot H = H\]

And thus \(d = e^{-1} \mod \#E\) where \(\#E\) is the order of the curve \(E\). Sage revealed easly the order of the curve:

a = 0xb3b04200486514cb8fdcf3037397558a8717c85acf19bac71ce72698a23f635
b = 0x12f55f6e7419e26d728c429a2b206a2645a7a56a31dbd5bfb66864425c8a2320
p = 0x247ce416cf31bae96a1c548ef57b012a645b8bff68d3979e26aa54fc49a2c297
e = 65537

F = FiniteField(p)
E =  EllipticCurve(F, [ a, b ])
order =E.order()
d = e.inverse_mod(order)

print(order)
print(d)


16503925798136106726026894143294039201930439456987742756395524593191976084900
13325880669850135947955584744200843377764515689540570722495414420830062384373

Thus we can create the hash point \(H\) compute a valid signature point \(D = d \cdot H\). However, our signature was always refused by the server. Looking closer to the code we noticed that:

\[h = 10826343561888283586707329693140326181071376199543143027569123040469103293774\]

which is greater than \(q\) so it will be reduced modulo \(q\) and the hash will never match. Nevertheless, the ending spaces are remove from the message before the comparison. So I tried to add ending spaces to the message until the hash is less than \(q\) and finally I got the solution:

$./solution.py
Message: b'Give me the flag. This is an order!    '
Signature: b'10feab68fea4ecbc95e2f7c67ebcf83e75fc0e0357006ca2429559f4aa83fce8'

b'hxp{H1dd3n_Gr0uP_0rD3rz_4r3_5uPP0s3D_t0_B3_k3p7_h1DD3n!}\n'

Written on October 2, 2016