# bi0s CTF 2024 Write-up

# Cryptography

## challengename

*ECDSA Nonce Reuse Attack due to flawed custom implementation of nonce XOR-ing. Recovering a and b value from two known curve points, the Public Key and Encryption Result*

We were given 2 points from the same curve, Public Key which is equal to dG, and Encrypted Flag which is equal to dF. We can use this two points as (x1,y1) and (x2,y2) to make the curve equation becomes a system of linear equation and solve it to recover a and b.

```
#sagemath
x1=61600024406073885532834502896649726027303457494482891878920198374829497624020
y1=69280030991018570318368009110412171820069942770686554653245684528998534423187
x2=11386122200168342563094845105265538185476210121219961865254382895010249983959
y2=28341196113496012135432397702493634501256271575119131587408850011138765511179
a=Mod(((y1^2 - y2^2)-(x1^3 - x2^3))*inverse_mod((x1-x2),p),p)
b=Mod(y2^2 - x2^3 - a*x2, p)
```

since now we know a, b, and p, we can retrieve the curve order.

```
#sagemath
E = EllipticCurve(GF(p), [a,b])
E.order()
```

With the way the `bigsur`

is implemented, attacker can craft different values of`nonce`

input such that the resulting `nunce`

keeps giving the same value. In this case, we can use `00`

and `0000`

as the 2 inputs for the `nonce`

. It is known that ECDSA is vulnerable to nonce reuse attack (https://notsosecure.com/ecdsa-nonce-reuse-attack). We can use the result of signing 2 different messages with the same `nunce`

to retrieve the Private Key, `d`

. Below is the python script to perform EDSA nonce reuse attack and retrieve `d`

```
from hashlib import md5
from Crypto.Util.number import bytes_to_long
def inverse_mod(a, m):
"""Compute the modular inverse of a modulo m."""
g, x, y = egcd(a, m)
if g != 1:
raise Exception('Modular inverse does not exist')
else:
return x % m
def egcd(a, b):
"""Extended Euclidean Algorithm."""
if a == 0:
return (b, 0, 1)
else:
g, y, x = egcd(b % a, a)
return (g, x - (b // a) * y, y)
def recover_private_key(H_m1, H_m2, r, s1, s2, q):
"""Recover the private key d given two signatures with the same nonce."""
H_m1_int = bytes_to_long(md5(H_m1).digest())
H_m2_int = bytes_to_long(md5(H_m2).digest())
r_inv = inverse_mod(r, q)
d = ((inverse_mod(s1 - s2, q) * (H_m1_int * s2 - H_m2_int * s1) % q) * r_inv) % q
return d
H_m1 = b"Fidethus"
H_m2 = b"Cylabus"
# Example values (these need to be replaced with your actual values)
r = 0x39504995bcf174284cc4013aaae44454d349629d864c4b41456f8ecd1143c4b0 # Example r value from one of the signatures
s1 = 0xa6c917eb8ff4d2b8e5424c6c01ac6e1b2c67bb48a362c3fcb9cde05d252836c3 # s value from signature 1
s2 = 0x5c012f1f87731cec692375afdb56b6b38b80f935ab9d9d29cf531d528fed7703 # s value from signature 2
q = 0xffffffff00000000ffffffffffffffffbce6faada7179e84f3b9cac2fc632551 # Order of the curve
# Recover d
d = recover_private_key(H_m1, H_m2, r, s1, s2, q)
print(f"Recovered private key: {d}")
```

Since we know `Q`

where `Q = dF`

, and the flag is the x value of `F`

, once we have the Private Key `d`

, we can retrieve the flag.

```
#sagemath
d_inverse=inverse_mod(d,E.order())
Q=E.point([16992676324977131273008947657295191567208515683606460326098734497649728555260, 77304532410673092658334096326489354927782847394098654658641557840081762445162])
F=d_inverse*Q
long_to_bytes(F[0])
```

**FLAG: bi0sctf{https://bit.ly/3I0zwtG}**

## lalala

*Using matrix operation in sagemath to solve a big linear equations system*

From the given value of `aa`

, `bb`

, `cc`

, and the summation in out.py, we can create a system consisting of 100 equations (becasue the output consists of 100 sets of `aa`

, `bb`

, `cc`

, and the summation values) with 100 unknowns (ranging from `x0^2 * x0^3, ..., x0^2 * x10^3, ..., x10^2 * x0^3, ..., x10^2 * x10^3`

).
We will have 100 equations in the following form:

```
coefficient0 * unknown0 + ... + coefficient99 * unknown99 = (summation value from output[] ) - (sum of aa[])
```

We can retrieve each value of the unknowns using matrix opertaion:

```
Ax = sum
x = A^-1 sum
```

where A is a 100x100 matrix consisting of the coefficients, x is a 100x1 matrix consisting of the 100 unknowns variable, sum is a 100x1 matrix consisting the value of `summation - constant`

Once we have the value for matrix x, we can use just value of `x0^5`

, `x1^5`

, …, `x9^5`

in which each is represented by x[0], x[11], …, x[99] respectively.

By paying attention to this part of chall.sage:

```
p = random_prime(2**1024)
unknowns = [randint(0, 2**32) for _ in range(10)]
unknowns = [f + i - (i%1000) for i, f in zip(unknowns, search("{(.*)}", flag).group(1).encode())]
```

we can know that:

`x^5`

is always smaller than p, so we do not need to perform root finding in modulo operation.- This operation
`i - (i%1000)`

made the random integer from unknowns have three 0s as their last 3 digits before the addition. This means the value of`f`

(the integer representing the Unicode point of the flag character) can be retrieved from the last 3 digits of `x.

Below is the python script to retrieve the flag.

```
#sagemath
import out
A=[]
L=[]
for i in range (0,400,4):
row = [[0 for _ in range(10)] for _ in range(10)]
const=0
for a, b, c in zip(out.output[i], out.output[i+1], out.output[i+2]):
const+=a
row[b][c]+=1
flattened_row = [element for sublist in row for element in sublist]
A.append(flattened_row)
L.append([out.output[i+3]-const])
A=Matrix(GF(out.p), A)
L=Matrix(GF(out.p), L)
x=A.inverse()*L
flag=""
for i in range(0,100,11):
flag+=chr((Integer(x[i][0])^(1/5))%1000)
print("bi0sctf{%s}" % flag)
```

**FLAG: bi0sctf{8d522ae1a7}**

Thanks for reading! Follow me on **Twitter**