Dans ce chall du FCSC2023, on nous demande d’entrer 256 messages maximum au format hexa, dont les sha256 xorés font une certaine valeur donnée, par exemple :
0x937956abdda8f658eb878108d5e77503bb5fd2bc873f3391ddd0c3d309e09b9e
Analyse
N’ayant aucun controle sur les sha256 des messages, l’approche bruteforce est écartée.
Une approche est de tirer au hasard un certain nombres de messages dont on calcule le sha256, puis de selectionner ceux dont le xor donne la valeur recherchée. Pour réaliser cette sélection, l’astuce consiste à générer, dans GF(2), 256 équations à 256 inconnues, soit une equation pour chacun des 256 bits du résultat recherché.
Dans GF(2), xor est équivalent à l’addition, et chacun des bits du résultat ne dépend que des mêmes bits de chaque hash. On peut donc écrire 256 équations indépendantes, et après résolution, chaune des 256 inconnues nous indiquera si le hash correspondant doit être retenu (1) ou non (0)
Exemple simplifié pour des valeurs de 8 bits
Supposons qu’on veuille trouver quelles sont les valeurs dont le xor fait 00000001, parmi les valeurs tirées au hasard suivantes : 00010010, 01000000, 11101111, 01100000, 00101111, 11001010, 11100011, 00100100
hash0 : [0,0,0,1,0,0,1,0] * x0
hash1 : [0,1,0,0,0,0,0,0] * x1
hash2 : [1,1,1,0,1,1,1,1] * x2
hash3 : [0,1,1,0,0,0,0,0] * x3
hash4 : [0,0,1,0,1,1,1,1] * x4
hash5 : [1,1,0,0,1,0,1,0] * x5
hash6 : [1,1,1,0,0,0,1,1] * x6
hash7 : [0,0,1,0,0,1,0,0] * x7
resultat cherché : [0,0,0,0,0,0,0,1]
(en transposant ligne/colonne,) on peut écrire cet ensemble d’equations à résoudre dans GF(2) :
0*x0 + 0*x1 + 1*x2 + 0*x3 + 0*x4 + 1*x5 + 1*x6 + 0*x7 = 0
0*x0 + 1*x1 + 1*x2 + 1*x3 + 0*x4 + 1*x5 + 1*x6 + 0*x7 = 0
0*x0 + 0*x1 + 1*x2 + 1*x3 + 1*x4 + 0*x5 + 1*x6 + 1*x7 = 0
1*x0 + 0*x1 + 0*x2 + 0*x3 + 0*x4 + 0*x5 + 0*x6 + 0*x7 = 0
0*x0 + 0*x1 + 1*x2 + 0*x3 + 1*x4 + 1*x5 + 0*x6 + 0*x7 = 0
0*x0 + 0*x1 + 1*x2 + 0*x3 + 1*x4 + 0*x5 + 0*x6 + 1*x7 = 0
1*x0 + 0*x1 + 1*x2 + 0*x3 + 1*x4 + 1*x5 + 1*x6 + 0*x7 = 0
0*x0 + 0*x1 + 1*x2 + 0*x3 + 1*x4 + 0*x5 + 1*x6 + 0*x7 = 1
La résolution des équations de cet exemple est : x0=0, x1=0, x2=1, x3=0, x4=0, x5=1, x6=0, x7=1 On retiendrait donc les hashs 2, 5 et 7
Statistiquement, on conjecture que la moitié des hashs est nécéssaire pour obtenir le résultat, soit 128 valeurs pour un sha256. On pourra donc répondre au challenge qui autorise 256 messages au maximum.
Solution
Pour l’implémentation on peut utiliser la bibliotheque galois pour les calculs dans GF(2), et numpy pour trouver les solutions des équations.
Le programme suivant permet d’obtenir des chaines aléatoires dont les sha256 xorés correspondent à la valeur passée en paramètre.
import os
import sys
import hashlib
import numpy as np
import galois
GF = galois.GF(2)
plaintext_bytes = 8
hashlen_bytes = 32
hashlen_bits = hashlen_bytes * 8
def xor(a: bytes, b: bytes) -> bytes:
return bytes(x ^ y for x, y in zip(a, b))
## get random plaintext as hex, and sha256 digest
def get_random_hash() -> tuple[bytes, str]:
rand = os.urandom(plaintext_bytes)
hash = hashlib.sha256(rand).digest()
plain = rand.hex()
return (hash, plain)
def hash_as_bits(hash: bytes) -> list:
n = int.from_bytes(hash, "little")
return [1 if n & 1<<pos else 0 for pos in range(hashlen_bits)]
## Getting random values can lead to unsolvable equations.
## Loops until a suitable set of random values is found
print(f"Generating random values")
while True:
hashes = dict(get_random_hash() for _ in range(hashlen_bits))
A = GF([hash_as_bits(h) for h in hashes.keys()]).transpose()
if np.linalg.matrix_rank(A) == hashlen_bits:
break
def find_solutions(target):
print(f"Solving equations")
b = GF(hash_as_bits(target))
# Solve equations
x = np.linalg.solve(A, b)
# x will tell us if value should be included in the solution
value=b"\x00" * 32
solutions=[]
for column, bit in enumerate(x):
if int(bit):
plain=list(hashes.values())[column]
hash=list(hashes.keys())[column]
value = xor(value,list(hashes.keys())[column])
solutions.append(list(hashes.values())[column])
print(f"Final xored value : {value.hex()}")
return solutions
target=sys.argv[1]
if target.startswith("0x"):
target=target[2:]
print(f"Target hash : {target}")
target_hash=bytes().fromhex(target)
solutions = find_solutions(target_hash)
print(f"{len(solutions)} elements solutions")
for solution in solutions:
print(solution)