Flash CTF – Faulty Curves

June 21, 2024
Challenge Writeups
4 min read

Challenge Overview

In “Faulty Curves,” participants work with cryptographic data that has been tampered with through fault injection. The goal is to recover the private key used in the encryption process by exploiting these faults to reverse-engineer the private key bit by bit.

Understanding the Basics

Before tackling the specifics of the challenge, it’s essential to understand some foundational concepts:

Elliptic Curve Cryptography (ECC)

ECC is a type of public-key cryptography that uses the algebraic structure of elliptic curves over finite fields. The difficulty of solving the Elliptic Curve Discrete Logarithm Problem (ECDLP) underpins the security of ECC.

Fault Injection

Fault injection is a technique where errors are deliberately introduced into a system to disrupt its operation. In cryptography, this technique can reveal secrets from secure algorithms by analyzing their faulty behaviors.

The Setup

The challenge employs a specific elliptic curve defined over a finite field. Here are the parameters and setup used (see the provided code snippets for more details):

  • Prime Field ( p ): A large prime defining the finite field.
  • Curve Coefficients ( a, b ): These coefficients define the elliptic curve equation ( y^2 = x^3 + ax + b ).
  • Base Point ( G ): A point on the curve used to generate public keys.
from random import *  
from Crypto.Util.number import * 
flag = b'MetaCTF{F4ult_1nj3ect10n_FTW}'
#DEFINITION
p = 0xffffffffffffffffffffffffffffffff000000000000000000000001
K = GF(p)
a = K(0xfffffffffffffffffffffffffffffffefffffffffffffffffffffffe)
b = K(0xb4050a850c04b3abf54132565044b0b7d7bfd8ba270b39432355ffb4)
E = EllipticCurve(K, (a, b))
G = E(0xb70e0cbd6bb4bf7f321390b94a03c1d356c21122343280d6115c1d21, 0xbd376388b5f723fb4c22dfe6cd4375a05a07476444d5819985007e34)
E.set_order(0xffffffffffffffffffffffffffff16a2e0b8f03e13dd29455c5c2a3d * 0x1)

Fault Injection Mechanism

The challenge script simulates fault injection by manipulating the binary representation of the private key. This is done by flipping specific bits, which alters the behavior of cryptographic operations, allowing for an analysis of discrepancies between expected and actual outputs.

The fault injection is implemented in the fault function, which takes a binary string val representing the private key and an index indicating which bit to flip. If the bit at the specified index is ‘1’, it is changed to ‘0’, and vice versa. This function is crucial for simulating the effect of physical faults that might occur due to environmental factors or deliberate tampering.

Here is the relevant code snippet that demonstrates this mechanism:

def fault(val,index): 
	val = list(val)
	if val[index] == '1': 
		val[index] = '0'
	else: 
		val[index] = '1'
	return ''.join(val)

During the challenge, this function is called to create a faulty version of the private key. Each bit of the private key is flipped in sequence, and the cryptographic operations are performed with both the correct and faulty keys. The outputs are then compared to determine the correct bits of the original private key.

The process of injecting faults and analyzing the results is encapsulated in the main loop of the challenge script, where the fault function is used to generate new private keys with single-bit faults.

while count < len(my_priv):
	try: 
		k = randint(2, G.order()-2)
		Q = int(my_priv,2)*G
		M = randint(2,G.order()-2)
		M = E.lift_x(Integer(M));ms.append((M[0],M[1]))
		
		C1 = k*G;C1s.append((C1[0],C1[1]))
		C2 = M + k*Q;C2s.append((C2[0],C2[1]))

		ind = len(my_priv)-1-count
		new_priv = fault(my_priv,ind)
		new_priv = int(new_priv,2)
		dec = (C2 - (new_priv)*C1);decs.append((dec[0],dec[1]))
		count +=1 
	except: 
		pass

The Recovery Process

Participants are given a series of messages, along with their corresponding encrypted forms using both the correct and faulty private keys. The task is to determine the correct bits of the private key by analyzing these pairs.

The solution involves checking if the difference between the correct and faulty ciphertexts matches a scaled version of a known point on the curve. If it does, the corresponding bit of the private key is ‘1’; otherwise, it’s ‘0’. Looping through each bit of the private key, the script reconstructs the original private key, and thus recovers the flag.

from random import *  
from Crypto.Util.number import * 

#DEFINITION
p = 0xffffffffffffffffffffffffffffffff000000000000000000000001
K = GF(p)
a = K(0xfffffffffffffffffffffffffffffffefffffffffffffffffffffffe)
b = K(0xb4050a850c04b3abf54132565044b0b7d7bfd8ba270b39432355ffb4)
E = EllipticCurve(K, (a, b))
G = E(0xb70e0cbd6bb4bf7f321390b94a03c1d356c21122343280d6115c1d21, 0xbd376388b5f723fb4c22dfe6cd4375a05a07476444d5819985007e34)
E.set_order(0xffffffffffffffffffffffffffff16a2e0b8f03e13dd29455c5c2a3d * 0x1)
with open('../dist/out.txt','rb') as f:
    ff=f.read()
exec(ff)
print(ms[0])
priv=''
for i in range(len(ms)):
    m=E(ms[i])
    c1p=E(C1s[i])
    c2p=E(C2s[i])
    d=E(decs[i])
    dd=d-m
    pp=c1p*(2^i)
    if pp==dd:
        priv+='1'
    else:
        priv+='0'
priv=int(priv[::-1],2)
print(long_to_bytes(priv))

Flag: MetaCTF{F4ult_1nj3ct10n_FTW}

Conclusion

By analyzing the discrepancies caused by fault injection, participants can reconstruct the private key bit by bit. For those interested in diving deeper or tackling similar challenges, researching “ECEG fault injection” offers further insights and opportunities for exploration.

Sign In

Get Started