[Pwn2Win CTF 2019] real-ec Writeups

In this writeup, I only show the solution how to solve the challenge, I didn't solve the challenge actually, because challenge itself was so boring.

I've been away from CTF for quite a long time, due to my busy research work and healthy work-life balance.

Let's dig into the challenge:

#!/usr/bin/python3 -u
from secrets import flag
from fastecdsa import keys, curve
import hashlib
import signal
import sys
import struct
import random
import os

def handler(signum, frame):
    print("\nGame over!")
    sys.exit(0)

signal.signal(signal.SIGALRM, handler)

secret = os.urandom(1000)
pub_keys = []
for i in range(0, len(secret), 4):
    p = struct.unpack(">I", secret[i:i+4])[0]
    n = 0
    while n == 0:
        for i in range(8):
            n = (n << 32) + (p * random.getrandbits(1))
    pk = keys.get_public_key(n, curve.P256)
    pub_keys.append((hex(pk.x), hex(pk.y)))

print(pub_keys)

signal.alarm(100)
h = input("Tell me the hash: ")
if h == hashlib.sha256(secret).hexdigest():
    print(flag)

To get the flag, we have to recover secret from os.urandom(1000), 1000 bytes.

Initially, I have 3 ideas to solve the challenge:

  • Weakness of urandom in Python3, getrandbits(1).
  • Bad implementation of fastecdsa
  • Calculate discrete log of ECC, mainly from the pk = keys.get_public_key(n, curve.P256)

For the 1st case, Python3 urandom has no weakness. So I clear this path. To guess getrandbit(), we need many of its output, at least 2500 bytes to predict the seed. But in our case we don't know its output. So attacking randomness is impossible.

In the 2nd case, I took a quick look at Github Issue, I found that the author mention the timing attack https://minerva.crocs.fi.muni.cz/#details, read through the link, I'm sure that this is not what intended. Timing side channel is something paranoid cryptographer barking for years, well, in networking environment it'll never work. Academia panic of everything.

The last resort is to compute discrete log. To know more about get_public_key function, you can take a look at here: https://github.com/AntonKueltz/fastecdsa/blob/master/fastecdsa/keys.py#L68

Explain the operation in the loop.

  1. Convert 4 bytes to INT32
  2. Generate INT256 from INT32 by mixing the bit
  3. Multiply the INT256 to Base Point of Curve.P256.

Step 1 is reversible if we have result from Step 2.

Step 2 is to mix up the INT32, the entropy of randomness output stay the same but the bitwidth increase.

cothan@xps:~/Work/2019/pwn2win/crypto/realec$ python real_ec.py 
p = 53fa0fd6
n = 0
n = 0
n = 0
n = 53fa0fd6
n = 53fa0fd653fa0fd6
n = 53fa0fd653fa0fd600000000
n = 53fa0fd653fa0fd60000000053fa0fd6
n = 53fa0fd653fa0fd60000000053fa0fd653fa0fd6
cothan@xps:~/Work/2019/pwn2win/crypto/realec$ python real_ec.py 
p = 6b0db0af
n = 0
n = 6b0db0af
n = 6b0db0af6b0db0af
n = 6b0db0af6b0db0af6b0db0af
n = 6b0db0af6b0db0af6b0db0af6b0db0af
n = 6b0db0af6b0db0af6b0db0af6b0db0af00000000
n = 6b0db0af6b0db0af6b0db0af6b0db0af000000006b0db0af
n = 6b0db0af6b0db0af6b0db0af6b0db0af000000006b0db0af00000000
cothan@xps:~/Work/2019/pwn2win/crypto/realec$ python real_ec.py 
p = 47675bf4
n = 0
n = 47675bf4
n = 47675bf447675bf4
n = 47675bf447675bf447675bf4
n = 47675bf447675bf447675bf400000000
n = 47675bf447675bf447675bf40000000000000000
n = 47675bf447675bf447675bf4000000000000000000000000
n = 47675bf447675bf447675bf400000000000000000000000000000000
cothan@xps:~/Work/2019/pwn2win/crypto/realec$ python real_ec.py 
p = f5b73bec
n = f5b73bec
n = f5b73becf5b73bec
n = f5b73becf5b73bec00000000
n = f5b73becf5b73bec0000000000000000
n = f5b73becf5b73bec0000000000000000f5b73bec
n = f5b73becf5b73bec0000000000000000f5b73bec00000000
n = f5b73becf5b73bec0000000000000000f5b73bec0000000000000000
n = f5b73becf5b73bec0000000000000000f5b73bec0000000000000000f5b73bec

Let say the INT32 is k, we can see that in Step 2 they do as follow:

k . 2224 . randbit(1) + k . 2192 . randbit(1) + ... + k . 232.randbit(1) + k.randbit(1)

which is equal to

k. (2224.randbit(1) + 2192.randbit(1) + ... + 232.randbit(1) + randbit(1))

So we just need to build a table of k, which is 32 bit, and the thing in bracket is easy to compute.

Step3, Curve P.256 is safe curve (it's from NIST), so there is no special attack on the curve itself, like malicious curve. No known backdoor.

After a while, I'm keep thinking to myself there should be a better way than bruting INT32, turn out there is no way else.

Here is how we attack:

  • We create a hash table ( O(1) lookup) with 2**32.
  • For each public key P receive from the server, we will multiply point P with inverse of 8 bit. E.g: Q = P*inverse(i) % G.order() where i in precomputed table, and check if the point Q.x is in the hash table or not. If it is, we found the result, otherwise move on searching.
  • The precomputed 256 bit table is permutation of all possible value it may have. The length of the table is 256.

If we compute the hash table large enough, we can recover 1000 bytes, then we can have the flag.

However, the size the table is the problem, if you have 64GB of RAM, it's fine, I guess, but if you have the table length is about 231, you have only 50% to guess the input. Let's say birthday attack work, the require table to have 1000 bytes in 01 succesfully guess is 28000/2, well, that's suck. Also I'm not sure my formula is correct but if you know the correct fomular, let me know.

As I tested, I create a hash table size 224, which I have 0.39% successful rate for 01 guess, or I can increase the table size to 226 to have 1.56% successful rate, over 100 connection, I will have the flag.

This is where I get bore, I wait for the table increase up to  224, and it's take quite a while, then I increase the hash table size 226, it's take longer.

So I gave up, because I felt the challenge was boring.

I don't know the actually flag, I don't think the flag string would have some serious meaning in it. I have no point to wait or move forward.

Here is the script, it will save the hash table to disk once you finish computing the hash table, and then it connects to server to solve the problem.

from fastecdsa import keys, curve, point
import hashlib
import signal
import sys
import struct
import random
import os
import numpy as np

from gmpy2 import invert
from pwn import remote

load = 0
host, port = '167.172.225.246', 1337

SIZE = 2**24

if load:
    big_dict = np.load('save_dict.npy', allow_pickle=TRUE).item()
else:
    big_dict = {}

if not load:
    for n in range(0, SIZE):
        pk = keys.get_public_key(n, curve.P256)
        big_dict[pk.x] = n

    np.save('save_dict.npy', big_dict)

r = remote(host, port)

pub_keys = r.readline()
pub_keys = eval(pub_keys)

print r.readuntil(":")

# Recover secret


def recover(pub_keys):
    result = []
    p256_order = 115792089210356248762697446949407573529996955224135760342422259061068512044369
    bla = # Permutation table
    for each_key in pub_keys:
        for rand in bla:
            xx, yy = each_key
            P = point.Point(xx, yy, curve.P256)
            inv_rand = invert(rand, p256_order)
            Q = P*inv_rand
            pk_temp = Q.x
            if pk_temp in big_dict:
                result.append(big_dict[pk_temp.x])
                break

    return result


secret = recover(pub_keys)
secret = map(lambda x: struct.pack(">I", x), secret)
hash_secret = hashlib.sha256(secret).hexdigest()

r.sendline(hash_secret)

r.interactive()

Congrats to whoever solve the challenge, It's either painful or not fun to solve the challenge, isn't it?

If  you are the author if this challenge, it would be more interesting to me if you made INT24 and then do permutation to get INT240. That's more fun.

Thanks for reading.

Show Comments

Get the latest posts delivered right to your inbox.