## Speedy Signatures
>Guess my number!
`nc 2020.redpwnc.tf 31452`
### Challenge 
```py#!/usr/bin/env python3
from Crypto.Util.number import inverseimport ecdsaimport randomimport hashlib
flag = open('flag.txt','rb').read()
C = ecdsa.NIST256pG = C.generatorn = C.orderk = random.randint(1,n-1)
for i in range(100):	print("> ROUND ",i+1)
	ans = random.randint(1,n-1)	Q = G*ans	print(Q.x(),Q.y())
	m1 = input("Enter first message: ").encode()	h1 = int(hashlib.sha256(m1).hexdigest(),16)	done = False	while not done:		k1 = k+random.randint(1,4096)		P = k1*G		r1 = P.x()%n		if r1 == 0:			continue		s1 = inverse(k1,n)*(h1+r1*ans)%n		if s1 == 0:			continue		done = True
	m2 = input("Enter second message: ").encode()	h2 = int(hashlib.sha256(m2).hexdigest(),16)	done = False	while not done:		k2 = k+random.randint(1,4096)		if k1 == k2:			continue		P2 = k2*G		r2 = P2.x()%n		if r2 == 0:			continue		s2 = inverse(k2,n)*(h2+r2*ans)%n		if s2 == 0:			continue		done = True
	sigs = [str(r1),str(s1),str(r2),str(s2)]	random.shuffle(sigs)	sigs.pop(random.randint(0,3))	print(' '.join(sigs))
	user_ans = int(input("What's my number?\n").strip())	if user_ans == ans:		print("Correct!")		if i == 99:			print("Here's your flag: {}".format(flag))	else:		print("Wrong! Better luck next time...")		break	print()```
### TL;DR 
#### Stage 1
- Connect to the server until we recieve a data package with `(s1,s2,r1)`.- Guess all permutations of the data and use the guessed `r1` to calculate `2*4096` possible `r2`.- From guessing all `r1, r2` we also obtain the differences in the nonces `dk`.- Use `dk` to find `secret` from the given data together with the guessed `r2`. - Use `secret` to calculate `k1_first`.- Send `secret` to the server.
#### Other stages
- From `k1_first` guess the nonce `k1_round` for the pair `(s1,r1)` from `2*4096` possible `k1_round`- Find `secret` from `f(s1,r1,k1)`. - Use `k1` to lower the bounds on the brute for additional nonces.- Send `secret` to the server.
### Solution
**Note:** My main motivation for writing this up is so I can ask the challenge author Tux if it is the intended solution. This script is pretty slow and requires a lot of guessing. I would love to know if given `s1,s2,r1` or `s1,r1,r2` is suffient to find `secret` knowing that `|k1 - k2| < 4096`.
This challenge, like most CTF challenges associated to ECDSA, is about the closeness of nonce values. The canoncial challenge is the famous playstation three attack where the nonces are reused. For ECDSA there is the message `m` we want to sign. To sign `m` the server creates a private key `d`, and a public key `Q`. The public key is produced from the private key via the a scalar multiplication of a generator: `Q = d*G`. It is vital for the generator `G` to be of prime order, we will denote the order of `G` as `n`. Aside: this problem is usually solved by working with an elliptic curve E of prime order, as a result all points on the curve will also have prime order.
To sign the message `m`, the server calculates the hash: `h = Hash(m)`. A cryptographically secure integer `k` is picked. This value is known as the nonce (aside: the name nonce is used because it denotes n_once, or a number to be used only once!). A random point on the curve is produced from `R = k*G` and an integer `r = R.x mod n` is caluclated. If `r` is zero, a new `k` is generated. Finally the server signs `h` by calculating `s = k^-1(h + r*d) mod n`. The signed message `m` is the tuple `(r,s)`.
For the remaining dicussion, all arithmetic is mod `n`. 
The hardness of the ECDLP means it is infeasible to calculate `d` from `Q` given a curve of a suffiently large order. However if the nonce `k` is innapropriately picked, `d` can be recovered from `h,r,s` through signing multiple messages. When `k` is fixed, the secret `d` can be recovered from only two signings using that the nonce can be recovered from
```pyk = s1^-1*(h1 + r1*d) = s2^-1*(h2 + r2*d)  --> k =  (h1 - h2) / (s1 - s2)```
and that the secret is `d = r^-1*(sk - h)`. This is the famous PS3 attack.
We can do better than this though, we don't need `k1 = k2`, but only that `k1` and `k2` differ by a known number of bits. If an attacker can calculate the difference `k1 - k2`, the secret `d` can be recovered in the following way.
```pyk1 = s1^-1*(h1 + r1*d), k2 = s2^-1*(h2 + r2*d)k1 - k2 = s1^-1*(h1 + r1*d) - s2^-1*(h2 + r2*d)s1*s2*(k1 - k2) = s2*(h1 + r1*d) - s1*(h2 + r2*d)d*(s1*r2 - s2*r1) = (s2*h1 - s1*h2) - s1*s2*(k1 - k2)d = (s2*h1 - s1*h2) - s1*s2*(k1 - k2)*(s1*r2 - s2*r1)^-1```
An implmentation of the lattice attack to recover `k1 - k2` from a set of signed messages is wonderfully described here: [Trail of Bits: ECDSA - Handle With Care](https://blog.trailofbits.com/2020/06/11/ecdsa-handle-with-care/). I originally thought we'd need to use this to solve this challenge but it turns out knowing the difference of `k1,k2` is given for free while trying to recover other data. 
Onto the challenge. We connect to a server, and are able to sign two messages. The server replies with the public key and generates the tuples `(r1,s1)` and `(r2,s2)`. We control the signed message `m1, m2`. The nonces used for the challenge are generated insecurely and we see that their difference is only at most `4096`. This challenge would be easy if not for the next step:
```pysigs = [str(r1),str(s1),str(r2),str(s2)]random.shuffle(sigs)sigs.pop(random.randint(0,3))print(' '.join(sigs))```
We are only given 3 of the four pieces `(r1,s1,r2,s2)` AND we don't know which of these integers is which. We can break down our problem in two questions:
- Case 1: given `(r1,s1,r2)`, can we calculate `d`?- Case 2: given `(r1,s1,s2)`, can we calculate `d`?
For the first case, I have no idea how to solve this. Maybe there's a way, but I can't see it. It might then seems like it's impossible to pass all 100 rounds of teh challenge, but we find that if we can solve one round, the remaining 99 are easier.
For the second case, we know that `r1 = k1*G` and the missing data is `r2 = k2*G`. As `|k1 - k2| < 4096`, we can take `r1`, lift it to find `R1`. We can then generate `2*4096` points such that one of them is `R2 = k2*G`. Once we have `R1` and `R2`, we know `k1 - k2` and we can solve the above equation for `d`. Note the contrast to case 1, where knowing `(r1,s1,r2)` doesn't help you find `s2` (as far as i know).
So if we solve case 2, how can we solve all other rounds? Well, we can use our secret `d` to find `k1` from our data. It is this additional information that allows us to guess every other nonce for the rest of the challenge. As the difference is small, given `k_found` every other `k` will be one of `2*4096` nonces either side of it. 
Our first question is given some data `(?,?,?)` how do we know if we are in case 1 or case 2? By taking the data given, we know that one of them is `r1`. By lifting this onto the curve we can look at the `2*4096` possible `r2` values, if any of these points are in our array, we know we have `r1, r2` and thus it is `s2` which is missing. 
```py# Returns r1, r2, k1 - k2 if both r1,r2 in the data,# otherwise None.def find_r_value(data_array):    for r_guess in data_array[1:]:        try:            R1 = E.lift_x(r_guess)        except:            continue        for i in range(-4096, 4096):            R2 = R1 + i * G            r2_guess = Integer(R2.xy()[0])            if r2_guess in data_array and r2_guess != r_guess:                return r_guess, r2_guess, i    return None```
Note, this also gives `k1 - k2`, but this is not enough to solve, as we do not know what `s2` is.
So we can analyse the data packet on the first connection using this function. If we find both `r1,r2` we quit and try again. When only one `r1` value is in the set, we continue and calculate all possible `r2` values. One of these `r2` will produce a secret `d` such that `d*G == Q`. We implement this like so
```pydef big_brute(guesses, Qx, Qy):    # O(6 * 8192 * 2)    # permutation * k_gap values * pos or neg k_gap    for guess in guesses:        ra, sa, sb = guess        try:            R1 = E.lift_x(ra)        except:            continue        for i in range(-4096, 4096):            print("i = ", i)            R2 = R1 + i * G            rb = int(R2.xy()[0])            k_gap = i
            for kd in [k_gap, -k_gap]:            	# guess the k_gap, use to derive a potential secret                potential_priv_key = (sb * h1) - (sa * h1) - (sa * sb * kd)                potential_priv_key *= inverse_mod((rb * sa) - (ra * sb), n)                potential_priv_key %= n                pG = potential_priv_key * ecG                if pG.x() == Qx and pG.y() == Qy:                    print("found private key!")                    r1_found = ra                    s1_found = sa                    secret = potential_priv_key                    return r1_found, s1_found, secret    exit("Something went wrong, exiting")```
Note that we're now using python rather than sage to do the scalar multiplication on our curve. V01d noticed it was MUCH faster, and the switch to the `ecdsa` package made our script take ~ 30 mins rather than several hours. 
Now we have the secret, we can also calculate the nonce `k1` and send the secret to the server, progressing to round `2`.
We can reduce our search space of the permutations of the data by again checking if `r1,r2` are in `given_data`:
```pyif check_data is None:    print("One r value found, full search space")    guesses = list(itertools.permutations(given_data))else:    print("Both r values found, reduced search space")    ra,rb,_ = check_data    for x in given_data:        if x != ra and x != rb:            sa = x            break    guesses = [[sa, ra, rb], [sa, rb, ra]]```
We see that when both `ri` values appear, we can identify `s1` and reduce our guesses from the 6 permutations to just 2. Given these permutations we guess `2*4096` possible nonces and calculate the secret from them. If the secret produces the public key, we are successful and we move to the next round
```pydef brute_from_nonce(guesses, Qx, Qy):    for guess in guesses:        sa, ra, _ = guess        for i in range(-k_lower, k_upper):            k_guess = k1_found + i            potential_priv_key = inverse(ra, n) * (k_guess * sa - h1) % n            pG = potential_priv_key * ecG            if pG.x() == Qx and pG.y() == Qy:                print("found private key!")                secret = potential_priv_key                print(secret)                return secret, k_guess```
All we have to do is do this 99 times. We can speed it up a bit by using each recovered nonce from the above check to reduce the bound we guess over by recalculating the bounds each round
```pyif k_guess > k1_found:    k_diff = 4096 - (k_guess - k1_found)    if k_diff < k_lower:        k_lower = k_diffelif k_guess < k1_found:    k_diff = 4096 - (k1_found - k_guess)    if k_diff < k_upper:        k_upper = k_diff```
After about 20 rounds the search space halves, which is pretty nice.
Thanks to v01d, who was able to change up my slow script and produce something fairly reasonable. Thanks to hyperreality who ran my slow script and was gonna leave it on overnight until v01d saved us!
### Implementation
```pyimport osos.environ["PWNLIB_NOTERM"] = "True"
from pwn import *import hashlibimport itertoolsfrom Crypto.Util.number import inverseimport gmpy2import ecdsa
ecC = ecdsa.NIST256pecG = ecC.generatorecn = ecC.order
a = -3b = 0x5AC635D8AA3A93E7B3EBBD55769886BC651D06B0CC53B0F63BCE3C3E27D2604Bp = 115792089210356248762697446949407573530086143415290314195533631308867097853951E = EllipticCurve(GF(p), [a, b])n = 115792089210356248762697446949407573529996955224135760342422259061068512044369G = E(    48439561293906451759052585252797914202762949526041747995844080717082404635286,    36134250956749795798585127919587881956611106672985015071877198253568414405109,)
# We'll always send the same message, so let's grab it now.h1 = int(hashlib.sha256(b"password").hexdigest(), 16)
"""For stage one, we have a 50% chance of being able to continueusing the method described above. If we find both r1 and r2in the given data we exit and run the script again"""
# --- REMOTE ---IP = "2020.redpwnc.tf"PORT = 31452r = remote(IP, PORT, level="debug")
r.recvuntil("> ROUND")r.recvline()response = r.recvuntil("Enter", drop=True)
Qs = response.split(b" ")Q = E(Integer(Qs[0]), Integer(Qs[1]))print("Q = ", Q)
r.sendlineafter("message: ", b"password")r.sendlineafter("message: ", b"password")
data = r.recvline().decode().split(" ")r.recvuntil("number?")
given_data = list(map(Integer, data))print("*" * 80)print("Available Data")print("*" * 80)for d in given_data:    print(f"?? = {d}")
# Returns r1, r2, k1 - k2 if both r1,r2 in the data,# otherwise None.def find_r_value(data_array):    for r_guess in data_array[1:]:        try:            R1 = E.lift_x(r_guess)        except:            continue        for i in range(-4096, 4096):            R2 = R1 + i * G            r2_guess = Integer(R2.xy()[0])            if r2_guess in data_array and r2_guess != r_guess:                return r_guess, r2_guess, i    return None
check_data = find_r_value(given_data)
if check_data is not None:    print("Need both s1, s2")    print("Exiting")    exit()
else:    print("r1 or r2 is missing, we can proceed")    guesses = list(itertools.permutations(given_data))
def big_brute(guesses, Qx, Qy):    # O(6 * 8192 * 2)    # permutation * k_gap values * pos or neg k_gap    for guess in guesses:        ra, sa, sb = guess        try:            R1 = E.lift_x(ra)        except:            continue        for i in range(-4096, 4096):            print("i = ", i)            R2 = R1 + i * G            rb = int(R2.xy()[0])            k_gap = i
            for kd in [k_gap, -k_gap]:            	# guess the k_gap, use to derive a potential secret                potential_priv_key = (sb * h1) - (sa * h1) - (sa * sb * kd)                potential_priv_key *= inverse_mod((rb * sa) - (ra * sb), n)                potential_priv_key %= n                pG = potential_priv_key * ecG                if pG.x() == Qx and pG.y() == Qy:                    print("found private key!")                    r1_found = ra                    s1_found = sa                    secret = potential_priv_key                    return r1_found, s1_found, secret    exit("Something went wrong, exiting")
Qx, Qy = map(int, Q.xy())r1_found, s1_found, secret = big_brute(guesses, Qx, Qy)
print("Recovered secret from brute force, found:")print(f"r1_found = {r1_found}")print(f"s1_found = {s1_found}")print(f"secret = {secret}")print("We can now calculate the nonce")k1_found = inverse_mod(s1_found, n) * (h1 + r1_found * secret) % n
# Set generic bounds, which we will lower over each roundk_upper = 4096k_lower = 4096
print(f"Nonce found: {k1_found}")print("Subsequent rounds we can go faster (but still pretty slowly)")r.sendline(str(secret))
"""For every other round, we have the nonce within 8192 guess, so we take the data, permute throughthe guesses to find the pair (r1,r2) and then try all 8000 nonces until the secret works."""
def brute_from_nonce(guesses, Qx, Qy):    for guess in guesses:        sa, ra, _ = guess        for i in range(-k_lower, k_upper):            k_guess = k1_found + i            potential_priv_key = inverse(ra, n) * (k_guess * sa - h1) % n            pG = potential_priv_key * ecG            if pG.x() == Qx and pG.y() == Qy:                print("found private key!")                secret = potential_priv_key                print(secret)                return secret, k_guess
iRnd = 0while True:    print("Round ", iRnd)    print(f"Brute search for nonce between {-k_lower}, {k_upper}")    response = r.recvuntil("message: ")    cut = response.decode().split("\n")    Qx, Qy = map(int, cut[-2].split(" "))    print(Qx, Qy)
    r.sendline("password")    r.recvuntil("message: ")    r.sendline("password")
    data = r.recvline().decode().split(" ")    r.recvuntil("number?")
    given_data = list(map(Integer, data))    print("*" * 80)    print("Available Data")    print("*" * 80)    for d in given_data:        print(f"?? = {d}")
    check_data = find_r_value(given_data)    if check_data is None:        print("One r value found, full search space")        guesses = list(itertools.permutations(given_data))    else:        print("Both r values found, reduced search space")        ra,rb,_ = check_data        for x in given_data:            if x != ra and x != rb:                sa = x                break        guesses = [[sa, ra, rb], [sa, rb, ra]]
    secret, k_guess = brute_from_nonce(guesses, Qx, Qy)    if k_guess > k1_found:        k_diff = 4096 - (k_guess - k1_found)        if k_diff < k_lower:            k_lower = k_diff    elif k_guess < k1_found:        k_diff = 4096 - (k1_found - k_guess)        if k_diff < k_upper:            k_upper = k_diff
    r.sendline(str(secret))    iRnd += 1
#flag{s0m3t1m3s_crypt0gr4ph1c_1mpl3m3nt4t10ns_f41l}```