Berlian Gabriel

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