duksctf

Bunch of sec. enthusiasts who sometimes play CTF

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 and a corresponding valid signature . The signature has to be 64 byte long. The signature is verfified by computing . Then the point on the elliptic curve with axis coordinate is multiplied by . If the resulting point has its coordinate matching 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 which defines the underling finite field. Thus I could find 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 Then I could starts playing with the server. I sent the signature and it outputs:

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

Meaning that is a valid point of the curve. Since the and elliptic curve follows the Weierstrass equation

We have from the previous point

Then by trial and error I found another valid point

Wich allows to recover the value of :

At this point, the curve was completly defined. The valid signature is given by the point such that

And thus where is the order of the curve . 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 compute a valid signature point . However, our signature was always refused by the server. Looking closer to the code we noticed that:

which is greater than so it will be reduced modulo 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 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