Sami Burillon

Appearance

J'éponge donc j'essuie (Moyen) ​

Énoncé ​

En faisant de la plongée sous-marine avec un ami gorfou, je suis tombé sur un animal plutôt réservé mais fort sympathique ! J'ai donc décidé de faire mon propre algorithme de hash. Je vous mets au défi de le casser.

Source et ressources : https://github.com/HackademINT/404CTF-2024/tree/main/Cryptanalyse

Analyse ​

L'énigme suggère un algorithme de hash. Analysons le code de l'énoncé :

python
class Bob:
	def __init__(self, data):
		self.R_size = 32
		self.C_size = 96
		self.OUT_size = 512
		data = long_to_bytes(len(data)%256)+data+long_to_bytes(len(data)%256)
		
		self.data = self.bytes2binArray(data)
		self.state = [[0 for _ in range(self.R_size)],[0 for _ in range(self.C_size)]]

	def bytes2binArray(self,b):
		b = bin(bytes_to_long(b))[2:]
		b = '0'*(8-(len(b)%8))+b
		b = b+'0'*(self.R_size - (len(b)%self.R_size))
		return [int(i) for i in b]

	def binArray2bytes(self,b):
		bytes_in = [b[i:i+8] for i in range(0,len(b),8)]
		bytes_out = []
		for e in bytes_in:
			s = 0
			for i in range(8):
				s += e[i]*2**(7-i)
			bytes_out.append(s)
		return bytes(bytes_out)

	def xor(self,a,b):
		return [i^j for i,j in zip(a,b)]

	def _f(self):
		perm = [65, 107, 53, 90, 67, 35, 17, 100, 37, 103, 41, 92, 23, 120, 70, 11, 34, 73, 16, 29, 7, 91, 127, 69, 81, 26, 0, 98, 71, 51, 9, 112, 64, 121, 101, 47, 114, 30, 104, 113, 3, 27, 6, 32, 42, 93, 48, 21, 118, 99, 89, 84, 36, 110, 25, 102, 61, 39, 86, 50, 14, 10, 56, 28, 38, 62, 22, 46, 66, 19, 108, 18, 13, 125, 49, 2, 74, 95, 8, 122, 58, 5, 75, 97, 15, 63, 117, 123, 96, 24, 94, 43, 4, 33, 115, 45, 76, 80, 126, 109, 52, 12, 79, 72, 54, 77, 31, 57, 1, 87, 88, 60, 20, 55, 40, 111, 116, 44, 82, 85, 68, 105, 106, 83, 78, 124, 59, 119]
		input_perm = self.state[0].copy()+self.state[1].copy()
		output_perm = [input_perm[i] for i in perm]
		self.state = [output_perm[:self.R_size],output_perm[self.R_size:]]

	def _absorb(self):
		while len(self.data) != 0:
			input_data = self.data[:self.R_size]
			self.state[0] = self.xor(self.state[0],input_data)
			self.data = self.data[self.R_size:]
			self._f()

	def _squeeze(self):
		output = []
		while len(output) != self.OUT_size:
			output += self.state[0].copy()
			self._f()
		return output

	def digest(self):
		self._absorb()
		hash_out = self.binArray2bytes(self._squeeze())
		return hash_out

	def hexdigest(self):
		return self.digest().hex()
class Bob:
	def __init__(self, data):
		self.R_size = 32
		self.C_size = 96
		self.OUT_size = 512
		data = long_to_bytes(len(data)%256)+data+long_to_bytes(len(data)%256)
		
		self.data = self.bytes2binArray(data)
		self.state = [[0 for _ in range(self.R_size)],[0 for _ in range(self.C_size)]]

	def bytes2binArray(self,b):
		b = bin(bytes_to_long(b))[2:]
		b = '0'*(8-(len(b)%8))+b
		b = b+'0'*(self.R_size - (len(b)%self.R_size))
		return [int(i) for i in b]

	def binArray2bytes(self,b):
		bytes_in = [b[i:i+8] for i in range(0,len(b),8)]
		bytes_out = []
		for e in bytes_in:
			s = 0
			for i in range(8):
				s += e[i]*2**(7-i)
			bytes_out.append(s)
		return bytes(bytes_out)

	def xor(self,a,b):
		return [i^j for i,j in zip(a,b)]

	def _f(self):
		perm = [65, 107, 53, 90, 67, 35, 17, 100, 37, 103, 41, 92, 23, 120, 70, 11, 34, 73, 16, 29, 7, 91, 127, 69, 81, 26, 0, 98, 71, 51, 9, 112, 64, 121, 101, 47, 114, 30, 104, 113, 3, 27, 6, 32, 42, 93, 48, 21, 118, 99, 89, 84, 36, 110, 25, 102, 61, 39, 86, 50, 14, 10, 56, 28, 38, 62, 22, 46, 66, 19, 108, 18, 13, 125, 49, 2, 74, 95, 8, 122, 58, 5, 75, 97, 15, 63, 117, 123, 96, 24, 94, 43, 4, 33, 115, 45, 76, 80, 126, 109, 52, 12, 79, 72, 54, 77, 31, 57, 1, 87, 88, 60, 20, 55, 40, 111, 116, 44, 82, 85, 68, 105, 106, 83, 78, 124, 59, 119]
		input_perm = self.state[0].copy()+self.state[1].copy()
		output_perm = [input_perm[i] for i in perm]
		self.state = [output_perm[:self.R_size],output_perm[self.R_size:]]

	def _absorb(self):
		while len(self.data) != 0:
			input_data = self.data[:self.R_size]
			self.state[0] = self.xor(self.state[0],input_data)
			self.data = self.data[self.R_size:]
			self._f()

	def _squeeze(self):
		output = []
		while len(output) != self.OUT_size:
			output += self.state[0].copy()
			self._f()
		return output

	def digest(self):
		self._absorb()
		hash_out = self.binArray2bytes(self._squeeze())
		return hash_out

	def hexdigest(self):
		return self.digest().hex()

Étude de l'algorithme ​

Comment ça marche ? ​

La classe de hachage Bob prend des données en entrée, les transforme en une représentation binaire et les traite à travers une série d'étapes de permutation et de mélange pour produire un hash.

Le constructeur initialise la taille des blocs de données (32 bits pour R_size, 96 bits pour C_size) et formate les données d'entrée en ajoutant des marqueurs de longueur aux extrémités. Les données sont converties en un tableau binaire, puis la classe initialise un état interne composé de deux listes de bits. La méthode _absorb mélange les données dans l'état interne en utilisant la fonction de permutation _f, qui réorganise les bits selon un ordre prédéfini. Ensuite, la méthode _squeeze extrait des bits de l'état interne pour générer un hash de la longueur souhaitée (512 bits).

Enfin, la méthode digest retourne le hash sous forme de bytes, tandis que hexdigest le retourne en format hexadécimal.

Qu'est-ce qui ne vas pas ? ​

Le challenge nous donne l'input et son hash :

python
data = os.urandom(16)
digest = Bob(data).hexdigest()
print("Input of hash :",data.hex())
print("Hash :",digest)
data = os.urandom(16)
digest = Bob(data).hexdigest()
print("Input of hash :",data.hex())
print("Hash :",digest)

Notre objectif est clair : à partir de ces informations, nous devons générer un input de longueur différente permettant de générer le même hash dont voici le circuit de validation :

python
pre_image = input("> ").strip().replace("\n","").lower()

if len(pre_image) == 32:
	print("Don't fool me, they have the same length")
	exit()
if len(pre_image) > 4000:
	print("It's a bit too long, I'm sure you can do better ;)")
	exit()

digest_user = Bob(bytes.fromhex(pre_image)).hexdigest()

if bytes.fromhex(pre_image) == data:
	print("Don't fool me ! It's the same input !")
	exit()
elif digest_user != digest:
	print("Wrong hash, here is your hash :",digest_user)
	exit()
else:
	print("Congratulation ! Here's the flag :",FLAG)
pre_image = input("> ").strip().replace("\n","").lower()

if len(pre_image) == 32:
	print("Don't fool me, they have the same length")
	exit()
if len(pre_image) > 4000:
	print("It's a bit too long, I'm sure you can do better ;)")
	exit()

digest_user = Bob(bytes.fromhex(pre_image)).hexdigest()

if bytes.fromhex(pre_image) == data:
	print("Don't fool me ! It's the same input !")
	exit()
elif digest_user != digest:
	print("Wrong hash, here is your hash :",digest_user)
	exit()
else:
	print("Congratulation ! Here's the flag :",FLAG)

Ce type d'attaque à un nom, c'est une attaque par extension de longueur

Attaque par extension de longueur ​

On a deux problèmes pour faire ce type d'attaque :

  • L'algorithme ajoute des marqueurs aux extrémités en fonction de la taille de l'input ;
  • L'absorption utilise un mécanisme de permutation.

Étude des marqueurs ​

L'algorithme ajoute des marqueurs de tailles aux extrémités :

python
data = long_to_bytes(len(data)%256)+data+long_to_bytes(len(data)%256)
data = long_to_bytes(len(data)%256)+data+long_to_bytes(len(data)%256)

Mais en regardans de plus prêt, ces marqueurs sont un reflet de la taille de la donnée modulo 256. Donc... En ajoutant 256 de longueur à notre donnée, on tombera sur les mêmes marqueurs !

En considérant que le challenge génère une entrée de 16, pour pratiquer une length extension attack, on pourra cibler une longueur de 256*k+16 avec k un nombre entier positif.

Absorption ​

En étudiant la méthode de permutation _f, on remarque que celle-ci est 448 cyclique.

python
R_size = 32
C_size = 96
OUT_size = 512

state = [[i for i in range(R_size)],[i for i in range(R_size,R_size+C_size)]]
initial_state = [state[0].copy(), state[1].copy()]
def f(state):
    perm = [65, 107, 53, 90, 67, 35, 17, 100, 37, 103, 41, 92, 23, 120, 70, 11, 34, 73, 16, 29, 7, 91, 127, 69, 81, 26, 0, 98, 71, 51, 9, 112, 64, 121, 101, 47, 114, 30, 104, 113, 3, 27, 6, 32, 42, 93, 48, 21, 118, 99, 89, 84, 36, 110, 25, 102, 61, 39, 86, 50, 14, 10, 56, 28, 38, 62, 22, 46, 66, 19, 108, 18, 13, 125, 49, 2, 74, 95, 8, 122, 58, 5, 75, 97, 15, 63, 117, 123, 96, 24, 94, 43, 4, 33, 115, 45, 76, 80, 126, 109, 52, 12, 79, 72, 54, 77, 31, 57, 1, 87, 88, 60, 20, 55, 40, 111, 116, 44, 82, 85, 68, 105, 106, 83, 78, 124, 59, 119]
    input_perm = state[0].copy()+state[1].copy()
    output_perm = [input_perm[i] for i in perm]
    return [output_perm[:R_size],output_perm[R_size:]]

i = 0
while True:
    state = f(state)
    if initial_state[0] == state[0] and initial_state[1] == state[1]:
        break
    i += 1
    if i%1000 == 0:
        print(i)

print(f"Cycle de f en {i+1} iterations")
R_size = 32
C_size = 96
OUT_size = 512

state = [[i for i in range(R_size)],[i for i in range(R_size,R_size+C_size)]]
initial_state = [state[0].copy(), state[1].copy()]
def f(state):
    perm = [65, 107, 53, 90, 67, 35, 17, 100, 37, 103, 41, 92, 23, 120, 70, 11, 34, 73, 16, 29, 7, 91, 127, 69, 81, 26, 0, 98, 71, 51, 9, 112, 64, 121, 101, 47, 114, 30, 104, 113, 3, 27, 6, 32, 42, 93, 48, 21, 118, 99, 89, 84, 36, 110, 25, 102, 61, 39, 86, 50, 14, 10, 56, 28, 38, 62, 22, 46, 66, 19, 108, 18, 13, 125, 49, 2, 74, 95, 8, 122, 58, 5, 75, 97, 15, 63, 117, 123, 96, 24, 94, 43, 4, 33, 115, 45, 76, 80, 126, 109, 52, 12, 79, 72, 54, 77, 31, 57, 1, 87, 88, 60, 20, 55, 40, 111, 116, 44, 82, 85, 68, 105, 106, 83, 78, 124, 59, 119]
    input_perm = state[0].copy()+state[1].copy()
    output_perm = [input_perm[i] for i in perm]
    return [output_perm[:R_size],output_perm[R_size:]]

i = 0
while True:
    state = f(state)
    if initial_state[0] == state[0] and initial_state[1] == state[1]:
        break
    i += 1
    if i%1000 == 0:
        print(i)

print(f"Cycle de f en {i+1} iterations")

Autrement dit, appelé 448 fois sur la même donnée, la donnée en sortie sera équivalente à la donnée d'entrée.

Génération du hash ​

Bon on sait maintenant que :

  • En ajoutant k*256 à la longueur de la donnée d'entrée, les mêmes marqueurs seront ajoutés ;
  • En ajoutant 448*4*l à la longeur (4 étant la taille de bloc de la méthode de permutation et l un entier positif), les états de state ne seront pas modifiés.

Par ailleurs, on peut remarquer que 448*4 mod 256 = 0 : Eureka ! On peut donc en déduire notre k = (448*4) / 256 = 7.

Que mettons-nous dans notre payload ? ​

La méthode d'absorption utilise la fonction xor, et qu'est-ce qui permet de ne pas modifier la donnée d'entrée avec la fonction xor ? Tout pile, c'est bien 0. On veut donc que notre payload soit constituées de zeroes.

Solution ​

python
# Via pwntools, je récupère l'input "input" et son hash "hash"
# ...

padded_payload = input[:3] + b"\x00"*(4*448) + input[3:] # On ajoute 448 bloques de 4 octets pour un cycle sur f

assert Bob(padded_payload).hexdigest() == hash

solution = padded_payload.hex()

# ... 
# Emission de la solution avec pwntools
# Via pwntools, je récupère l'input "input" et son hash "hash"
# ...

padded_payload = input[:3] + b"\x00"*(4*448) + input[3:] # On ajoute 448 bloques de 4 octets pour un cycle sur f

assert Bob(padded_payload).hexdigest() == hash

solution = padded_payload.hex()

# ... 
# Emission de la solution avec pwntools

Un peu trop simple, ajoutons du piment ! ​

Durant le CTF je me suis posé la question suivante : cet algorithme est-il reversible ? (Oui..)

Voici la solution "hard" de ce challenge (sans trop de commentaires)

Récupération partielle de state ​

python
from Crypto.Util.number import long_to_bytes,bytes_to_long

R_size = 32
C_size = 96
OUT_size = 512

state = [[i for i in range(R_size)],[i for i in range(R_size,R_size+C_size)]]
def f(state):
    perm = [65, 107, 53, 90, 67, 35, 17, 100, 37, 103, 41, 92, 23, 120, 70, 11, 34, 73, 16, 29, 7, 91, 127, 69, 81, 26, 0, 98, 71, 51, 9, 112, 64, 121, 101, 47, 114, 30, 104, 113, 3, 27, 6, 32, 42, 93, 48, 21, 118, 99, 89, 84, 36, 110, 25, 102, 61, 39, 86, 50, 14, 10, 56, 28, 38, 62, 22, 46, 66, 19, 108, 18, 13, 125, 49, 2, 74, 95, 8, 122, 58, 5, 75, 97, 15, 63, 117, 123, 96, 24, 94, 43, 4, 33, 115, 45, 76, 80, 126, 109, 52, 12, 79, 72, 54, 77, 31, 57, 1, 87, 88, 60, 20, 55, 40, 111, 116, 44, 82, 85, 68, 105, 106, 83, 78, 124, 59, 119]
    input_perm = state[0].copy()+state[1].copy()
    output_perm = [input_perm[i] for i in perm]
    return [output_perm[:R_size],output_perm[R_size:]]

reverse = []

while len(reverse) != OUT_size:
    reverse += state[0]
    state = f(state)
    
def to_bin(data_in_hex, target_size=512):
    in_bin = bin(bytes_to_long(bytes.fromhex(data_in_hex)))[2:]
    in_bin = [int(c) for c in in_bin]
    missing_zeroes = [0]*(target_size-len(in_bin))
    return missing_zeroes + in_bin

def retrieve_state(hexdata):
    bined = to_bin(hexdata)
    t = [-1 for _ in range(R_size+C_size)]
    for b, p in zip(bined, reverse):
        t[p] = b
    return t

state_at_absorb = retrieve_state(hash)
from Crypto.Util.number import long_to_bytes,bytes_to_long

R_size = 32
C_size = 96
OUT_size = 512

state = [[i for i in range(R_size)],[i for i in range(R_size,R_size+C_size)]]
def f(state):
    perm = [65, 107, 53, 90, 67, 35, 17, 100, 37, 103, 41, 92, 23, 120, 70, 11, 34, 73, 16, 29, 7, 91, 127, 69, 81, 26, 0, 98, 71, 51, 9, 112, 64, 121, 101, 47, 114, 30, 104, 113, 3, 27, 6, 32, 42, 93, 48, 21, 118, 99, 89, 84, 36, 110, 25, 102, 61, 39, 86, 50, 14, 10, 56, 28, 38, 62, 22, 46, 66, 19, 108, 18, 13, 125, 49, 2, 74, 95, 8, 122, 58, 5, 75, 97, 15, 63, 117, 123, 96, 24, 94, 43, 4, 33, 115, 45, 76, 80, 126, 109, 52, 12, 79, 72, 54, 77, 31, 57, 1, 87, 88, 60, 20, 55, 40, 111, 116, 44, 82, 85, 68, 105, 106, 83, 78, 124, 59, 119]
    input_perm = state[0].copy()+state[1].copy()
    output_perm = [input_perm[i] for i in perm]
    return [output_perm[:R_size],output_perm[R_size:]]

reverse = []

while len(reverse) != OUT_size:
    reverse += state[0]
    state = f(state)
    
def to_bin(data_in_hex, target_size=512):
    in_bin = bin(bytes_to_long(bytes.fromhex(data_in_hex)))[2:]
    in_bin = [int(c) for c in in_bin]
    missing_zeroes = [0]*(target_size-len(in_bin))
    return missing_zeroes + in_bin

def retrieve_state(hexdata):
    bined = to_bin(hexdata)
    t = [-1 for _ in range(R_size+C_size)]
    for b, p in zip(bined, reverse):
        t[p] = b
    return t

state_at_absorb = retrieve_state(hash)

Reverse de absorb ​

absorb est partiellement reversible. J'ai choisi comme solution :

  • Créer un mapping sur GF(2) des équations de state=aborb(data) pour chaque bit
  • Résoudre par Sagemath (ca aurait été plus simple avec Z3, mais j'avais des petit problème système durant le CTF)
  • Reconstruire la donnée d'entrée
python
from Crypto.Util.number import long_to_bytes,bytes_to_long

R_size = 32	
C_size = 96

def xor(a,b):
		return [i^^j for i,j in zip(a,b)]

def f(state):
    perm = [65, 107, 53, 90, 67, 35, 17, 100, 37, 103, 41, 92, 23, 120, 70, 11, 34, 73, 16, 29, 7, 91, 127, 69, 81, 26, 0, 98, 71, 51, 9, 112, 64, 121, 101, 47, 114, 30, 104, 113, 3, 27, 6, 32, 42, 93, 48, 21, 118, 99, 89, 84, 36, 110, 25, 102, 61, 39, 86, 50, 14, 10, 56, 28, 38, 62, 22, 46, 66, 19, 108, 18, 13, 125, 49, 2, 74, 95, 8, 122, 58, 5, 75, 97, 15, 63, 117, 123, 96, 24, 94, 43, 4, 33, 115, 45, 76, 80, 126, 109, 52, 12, 79, 72, 54, 77, 31, 57, 1, 87, 88, 60, 20, 55, 40, 111, 116, 44, 82, 85, 68, 105, 106, 83, 78, 124, 59, 119]
    input_perm = state[0].copy()+state[1].copy()
    output_perm = [input_perm[i] for i in perm]
    return [output_perm[:R_size],output_perm[R_size:]]

def absorb(data, state):
    while len(data) != 0:
        input_data = data[:R_size]
        for i, (el_state, el_data) in enumerate(zip(state[0], input_data)):
                state[0][i].append(f"{el_data}")
        #self.state[0] = self.xor(self.state[0],input_data)
        data = data[R_size:]
        state = f(state)
    return state[0].copy()+state[1].copy()

def bytes2binArray(b):
		b = bin(bytes_to_long(b))[2:]
		b = '0'*(8-(len(b)%8))+b
		b = b+'0'*(R_size - (len(b)%R_size))
		return [int(i) for i in b]

state = [[[] for i in range(R_size)],[[] for i in range(R_size, R_size+C_size)]]

data = [ f"d{i}" for i in range(8*20) ]

mapping = absorb(data, state)
mapping = [ (i, f"s{i}={'^'.join(state_mapping)}") for i, state_mapping in enumerate(mapping) if len(state_mapping) > 0]

def equations_from_state(state):
        equations = [""] * len(mapping)
        for i in range(len(mapping)):
            if state[mapping[i][0]] != -1:
                equations[i] = mapping[i][1].replace(f"s{mapping[i][0]}", str(state[mapping[i][0]]))
        equations = [eq for eq in equations if len(eq) > 0]
        return equations

equations_str = equations_from_state(state_at_absorb)

start = [
    #d0 -> d7 = 0x10 (prefix)
    '0=d0',
    '0=d1',
    '0=d2',
    '1=d3',
    '0=d4',
    '0=d5',
    '0=d6',
    '0=d7',

    # d136 -> d143 = 0x10 (suffix)
    '0=d136',
    '0=d137',
    '0=d138',
    '1=d139',
    '0=d140',
    '0=d141',
    '0=d142',
    '0=d143',

    # d144 -> d159 = 0 (pad)
    '0=d144',
    '0=d145',
    '0=d146',
    '0=d147',
    '0=d148',
    '0=d149',
    '0=d150',
    '0=d151',
    '0=d152',
    '0=d153',
    '0=d154',
    '0=d155',
    '0=d156',
    '0=d157',
    '0=d158',
    '0=d159',
    ]

for s in start:
    equations_str.append(s)
from Crypto.Util.number import long_to_bytes,bytes_to_long

R_size = 32	
C_size = 96

def xor(a,b):
		return [i^^j for i,j in zip(a,b)]

def f(state):
    perm = [65, 107, 53, 90, 67, 35, 17, 100, 37, 103, 41, 92, 23, 120, 70, 11, 34, 73, 16, 29, 7, 91, 127, 69, 81, 26, 0, 98, 71, 51, 9, 112, 64, 121, 101, 47, 114, 30, 104, 113, 3, 27, 6, 32, 42, 93, 48, 21, 118, 99, 89, 84, 36, 110, 25, 102, 61, 39, 86, 50, 14, 10, 56, 28, 38, 62, 22, 46, 66, 19, 108, 18, 13, 125, 49, 2, 74, 95, 8, 122, 58, 5, 75, 97, 15, 63, 117, 123, 96, 24, 94, 43, 4, 33, 115, 45, 76, 80, 126, 109, 52, 12, 79, 72, 54, 77, 31, 57, 1, 87, 88, 60, 20, 55, 40, 111, 116, 44, 82, 85, 68, 105, 106, 83, 78, 124, 59, 119]
    input_perm = state[0].copy()+state[1].copy()
    output_perm = [input_perm[i] for i in perm]
    return [output_perm[:R_size],output_perm[R_size:]]

def absorb(data, state):
    while len(data) != 0:
        input_data = data[:R_size]
        for i, (el_state, el_data) in enumerate(zip(state[0], input_data)):
                state[0][i].append(f"{el_data}")
        #self.state[0] = self.xor(self.state[0],input_data)
        data = data[R_size:]
        state = f(state)
    return state[0].copy()+state[1].copy()

def bytes2binArray(b):
		b = bin(bytes_to_long(b))[2:]
		b = '0'*(8-(len(b)%8))+b
		b = b+'0'*(R_size - (len(b)%R_size))
		return [int(i) for i in b]

state = [[[] for i in range(R_size)],[[] for i in range(R_size, R_size+C_size)]]

data = [ f"d{i}" for i in range(8*20) ]

mapping = absorb(data, state)
mapping = [ (i, f"s{i}={'^'.join(state_mapping)}") for i, state_mapping in enumerate(mapping) if len(state_mapping) > 0]

def equations_from_state(state):
        equations = [""] * len(mapping)
        for i in range(len(mapping)):
            if state[mapping[i][0]] != -1:
                equations[i] = mapping[i][1].replace(f"s{mapping[i][0]}", str(state[mapping[i][0]]))
        equations = [eq for eq in equations if len(eq) > 0]
        return equations

equations_str = equations_from_state(state_at_absorb)

start = [
    #d0 -> d7 = 0x10 (prefix)
    '0=d0',
    '0=d1',
    '0=d2',
    '1=d3',
    '0=d4',
    '0=d5',
    '0=d6',
    '0=d7',

    # d136 -> d143 = 0x10 (suffix)
    '0=d136',
    '0=d137',
    '0=d138',
    '1=d139',
    '0=d140',
    '0=d141',
    '0=d142',
    '0=d143',

    # d144 -> d159 = 0 (pad)
    '0=d144',
    '0=d145',
    '0=d146',
    '0=d147',
    '0=d148',
    '0=d149',
    '0=d150',
    '0=d151',
    '0=d152',
    '0=d153',
    '0=d154',
    '0=d155',
    '0=d156',
    '0=d157',
    '0=d158',
    '0=d159',
    ]

for s in start:
    equations_str.append(s)

Résolution de state ​

python
# Résolution des équations

from sage.all import *

F = GF(2) 

n_vars = 8*20 

A = Matrix(F, len(equations_str), n_vars)
b = vector(F, len(equations_str))

for i, equation in enumerate(equations_str):
    # Extraction des données
    res, operands = equation.split("=")
    operands = operands.replace("d", "").split("^")

    # Conversion en nombre
    res = int(res)
    operands = [int(operand) for operand in operands]

    # Complétion de la matrice
    b[i] = res
    for operand in operands:
        A[i,operand] = 1

solution = A.solve_right(b)

print(f"{solution = }")
# Résolution des équations

from sage.all import *

F = GF(2) 

n_vars = 8*20 

A = Matrix(F, len(equations_str), n_vars)
b = vector(F, len(equations_str))

for i, equation in enumerate(equations_str):
    # Extraction des données
    res, operands = equation.split("=")
    operands = operands.replace("d", "").split("^")

    # Conversion en nombre
    res = int(res)
    operands = [int(operand) for operand in operands]

    # Complétion de la matrice
    b[i] = res
    for operand in operands:
        A[i,operand] = 1

solution = A.solve_right(b)

print(f"{solution = }")

Génération de la payload ​

python
# Test de la solution

def hash_bob(p):
    return Bob(p).hexdigest()

def binArray2bytes( binary_array):
    bin_str = ''.join(str(bit) for bit in binary_array)
    len_mod_R_size = len(bin_str) % R_size
    if len_mod_R_size != 0:
        bin_str = bin_str[:-len_mod_R_size]
    byte_data = int(bin_str, 2).to_bytes((len(bin_str) + 7) // 8, byteorder='big')
    first_one_index = bin_str.find('1')
    if first_one_index != -1:
        byte_data = byte_data[first_one_index // 8:]
    
    return byte_data[1:1+16]

rev_payload = binArray2bytes(solution)

assert hash_bob(rev_payload) == hash

## Et comme avant, let's go length extension attack

padded_payload = rev_payload[:3] + b"\x00"*(4*448) + rev_payload[3:] # On ajoute 448 bloques de 4 octets pour un cycle sur f

assert hash_bob(padded_payload) == hash_bob(rev_payload) and hash_bob(padded_payload) == hash

padded_payload.hex()
# Test de la solution

def hash_bob(p):
    return Bob(p).hexdigest()

def binArray2bytes( binary_array):
    bin_str = ''.join(str(bit) for bit in binary_array)
    len_mod_R_size = len(bin_str) % R_size
    if len_mod_R_size != 0:
        bin_str = bin_str[:-len_mod_R_size]
    byte_data = int(bin_str, 2).to_bytes((len(bin_str) + 7) // 8, byteorder='big')
    first_one_index = bin_str.find('1')
    if first_one_index != -1:
        byte_data = byte_data[first_one_index // 8:]
    
    return byte_data[1:1+16]

rev_payload = binArray2bytes(solution)

assert hash_bob(rev_payload) == hash

## Et comme avant, let's go length extension attack

padded_payload = rev_payload[:3] + b"\x00"*(4*448) + rev_payload[3:] # On ajoute 448 bloques de 4 octets pour un cycle sur f

assert hash_bob(padded_payload) == hash_bob(rev_payload) and hash_bob(padded_payload) == hash

padded_payload.hex()

Et voilà !