## TUMCTF: hiecss
----------## Challenge details| Contest        | Challenge     | Category  | Points ||:---------------|:--------------|:----------|-------:|| TUM CTF | hiecss | crypto | 150 + $ALGORITHM  |
*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.>```
----------## Write-up
For this challenge we get the following python code:
>```python>#!/usr/bin/env python3>import gmpy2>from Crypto.Hash import SHA256>>e = 65537>order = 'Give me the flag. This is an order!'>>def sqrt(n, p):>    if p % 4 != 3: raise NotImplementedError()>    return pow(n, (p + 1) // 4, p) if pow(n, (p - 1) // 2, p) == 1 else None>># just elliptic-curve addition, nothing to see here>def add(q, a, b, P, Q):>    if () in (P, Q):>        return (P, Q)[P == ()]>    (Px, Py), (Qx, Qy) = P, Q>    try:>        if P != Q: lam = (Qy - Py) * gmpy2.invert(Qx - Px, q) % q>        else: lam = (3 * Px ** 2 + a) * gmpy2.invert(2 * Py, q) % q>    except ZeroDivisionError:>        return ()>    Rx = (lam ** 2 - Px - Qx) % q>    Ry = (lam * Px - lam * Rx - Py) % q>    return int(Rx), int(Ry)>># just elliptic-curve scalar multiplication, nothing to see here>def mul(q, a, b, n, P):>    R = ()>    while n:>        if n & 1: R = add(q, a, b, R, P)>        P, n = add(q, a, b, P, P), n // 2>    return R>>def decode(bs):>    if len(bs) < 0x40:>        return None>    s, m = int(bs[:0x40], 16), bs[0x40:]>    if s >= q:>        print('\x1b[31mbad signature\x1b[0m')>        return None>    S = s, sqrt(pow(s, 3, q) + a * s + b, q)>    if S[1] is None:>        print('\x1b[31mbad signature:\x1b[0m {:#x}'.format(S[0]))>        return None>    h = int(SHA256.new(m.encode()).hexdigest(), 16)>    if mul(q, a, b, e, S)[0] == h:>        return m>    else:>        print('\x1b[31mbad signature:\x1b[0m ({:#x}, {:#x})'.format(*S))>>if __name__ == '__main__':>>    q, a, b = map(int, open('curve.txt').read().strip().split())>>    for _ in range(1337):>        m = decode(input())>        if m is not None and m.strip() == order:>            print(open('flag.txt').read().strip())>            break>```
### The idea
The first thing the script does is:
>```python>q, a, b = map(int, open('curve.txt').read().strip().split())>```
Which means the parameters for this curve are unknown to us, hinting that thesecurity of this scheme might be based on the secrecy of the curve, which isobviously a Very Bad Idea.
The following line confirms as much:
>```python>    h = int(SHA256.new(m.encode()).hexdigest(), 16)>    if mul(q, a, b, e, S)[0] == h:>```
This is the actual signature verification and we know *e* and *h*. We need tofind a point S on the curve (h, y) such that eS = (h, y). But if we know theorder of the curve this is trivial because the multiplicative inverse is givenb:
> ```> k = gmpy2.invert(n, l)> ```
Where *l* is the order of the curve and n the element to invert (here 65537).
### Retrieving q
In the decode function we have the following lines:
>```python>    s, m = int(bs[:0x40], 16), bs[0x40:]>    if s >= q:>        print('\x1b[31mbad signature\x1b[0m')>        return None>```
Since we control *s*, and this error is distinguisable from the other errors, wecan use it to search for *q* with a binary search.
>```python>  for _ in range(256):>      if L > R:>          print 'uhh'>          exit(-1)>      m = (L + R) / 2>      msg = '%064x' % m>      msg += order>      s.sendline(msg)>      r = s.recvline()>      if ':' in r:>          # lower>          L = m + 1>      else:>          R = m + 1>```
Which gives us *q*:
>```> q = 0x247ce416cf31bae96a1c548ef57b012a645b8bff68d3979e26aa54fc49a2c297>```
### Retrieving a and b
Now for a given s, the script constructs a point S on the curve, since itreturns us this point when the signature is wrong we can use this information tomake two equations with the two unknows *a* and *b*. This equation is solvableand gives us *a* and *b*.
>```python> ans = []> points = []> for i in [3, 6]:>     msg = '%064x' % i>     msg += order>     s.sendline(msg)>     # We get the root of i back from the server>     root = int(s.recvline().strip().split(',')[1][1:-1], 16)>     points.append((i, root))>     # square to get the root out>     orig = pow(root, 2, q)>     # remove to power to get an equation in a and b>     orig = orig - pow(i, 3, q)>     # got an equation in a and b>     ans.append(orig)  # s * a + b>>  a, b = sp.symbols('a b')>  sol = sp.solve([ans[0] - (3 * a + b), ans[1] - (6 * a + b)], a, b)>```
This gives us:
> ```> sol[a] = -1264784453881987711378734714637094073662569449865694247234410111979889287160/3> sol[b] = 8575167449093451733644615491327478728087226005203626331099704278682109092640> ```
Or in hex, reduced modulo q:
> ```> a = 0xb3b04200486514cb8fdcf3037397558a8717c85acf19bac71ce72698a23f635> b = 0x12f55f6e7419e26d728c429a2b206a2645a7a56a31dbd5bfb66864425c8a2320> ```
### Retrieving a flag
To get the order of the curve I used sage:
> ```> sage: a = 0xb3b04200486514cb8fdcf3037397558a8717c85acf19bac71ce72698a23f635> sage: b = 0x12f55f6e7419e26d728c429a2b206a2645a7a56a31dbd5bfb66864425c8a2320> sage: q = 0x247ce416cf31bae96a1c548ef57b012a645b8bff68d3979e26aa54fc49a2c297> sage: E = EllipticCurve(GF(q), [a,b])> sage: E.order()> 16503925798136106726026894143294039201930439456987742756395524593191976084900> ```
Therefor for any messagehash smaller than *q* we can now calculate a point Ssuch that eS = H. The hash of the given order is greater than *q* but because thewhitespace stripping we can just append whitespace until we get a hash smallerthan *q*.
The final part is:
>```> curve = libnum.ecc.Curve(a, b, q)> orderpad = 'Give me the flag. This is an order!    '> h = int(hashlib.sha256(orderpad).hexdigest(), 16)> H = curve.check_x(h)[0]> n = 65537> l = 16503925798136106726026894143294039201930439456987742756395524593191976084900> # Multiplicative inverse> k = gmpy2.invert(n, l)> Q = curve.power(H, k)> msg = '%064x' % Q[0]> msg += orderpad> s.sendline(msg)> print s.recvline()>```
The flag is:
> ```> hxp{H1dd3n_Gr0uP_0rD3rz_4r3_5uPP0s3D_t0_B3_k3p7_h1DD3n!}> ```