 # 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

### 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

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