As Cool As Xor
Introduction
Le but de ce challenge easy est de restaurer une vidéo chiffrée avec l’algorithme de feistel.
On a donc deux fichiers, une vidéo chiffrée, et le code ayant servit à la chiffrer.
Algorithme de chiffrement
L’algorithme se découpe en plusieurs parties que voici :
- La vérification du header du fichier, pour savoir si les 8 premiers octets correspondent au fichier original
- La séparation des octets du fichier vidéo en 2, dont la moitié droite est chiffrée, puis son résultat est utilisé dans un XOR avec la moitié gauche.
- On récupère l’ancienne partie droite, et la nouvelle, on les concatène et on écrit tout ça dans un fichier.
Faiblesses de l’algorithme :
Parlons d’abord du moment où la partie de droite est chiffrée avec l’algorithme ci-dessous :
def func_key(word, key):
return bytes([(word[i] * key[i % 4]) % 256 for i in range(len(word))])Le souci de cet algorithme est clair, on utilisera seulement que 4 caractères dans la clé.
Dû à ça, un attaquant pourrait essayer de brute-force la clé en seulement 81.450.625 possibilités
si elle contient tous les caractères visible de la table ascii. Bien souvent, on pourrait
se concentrer uniquement que sur les majuscules, minuscules et les lettres, ce qui réduit
considérablement ce chiffre.
Quoi qu’il en soit, le brute-force de nos jours ne prendrait que tout au plus une trentaine de secondes.
Code :
Avant de passer à la phase d’exploitation, voici le code utile à connaitre :
# [...]
def func_key(word, key):
return bytes([(word[i] * key[i % 4]) % 256 for i in range(len(word))])
def feistel_round(L, R, key):
new_L = R
F = func_key(R, key)
new_R = bytes([L[j] ^ F[j] for j in range(len(L))])
return new_L, new_R
def feistel_cipher(data, key, rounds=1):
if len(data) % 2 != 0:
data += b"\x00" # padding
mid = len(data) // 2
L, R = data[:mid], data[mid:]
for _ in range(rounds):
L, R = feistel_round(L, R, key)
return L + R
# [...]
expected_bits = "0000000000000000000000000001100001100110011101000111100101110000"
# [...]Exploitation :
La première chose à faire pour exploiter le code, c’est de savoir les données que l’on a en notre possession.
- On a les 8 premiers octets du fichier original
- On a également l’ancienne partie de droite du tableau, donc la moitié du fichier.
- Enfin, on a la nouvelle partie de droite, à savoir l’ancienne chiffrée avec la clé, XOR le tableau de gauche que l’on souhaite récupérer.
J’insiste sur ça, notre objectif n’est pas de récupérer la clé, mais de retrouver la vidéo originale.
Pour optimiser le processus de récupération, et éviter un brute-force de 30s, on peut inverser chaque opération.
Retrouver le tableau F
Pour plus de facilité sur la compréhension des données, serons nommés :
old_Letold_Rles parties gauche et droite lors du chiffrement de la vidéo.new_Letnew_Rles parties gauche et droite après le chiffrement de la vidéo.Comme décrit ci-dessus,
old_Rest égal ànew_L.
Dans les données, on a l’ancienne partie de droite du tableau. Mais, il ne faut pas oublier qu’on a les 8 premiers octets de la partie de gauche.
Avec seulement 4 octets, on sera en capacité de reconstituer la clé.
Grâce à l’opération XOR que l’on peut facilement inverser en utilisant de nouveau XOR :
old_L[j] ^ old_F[j] = new_R[j]
<=>
old_L[j] ^ new_R[j] = old_F[j]Nous avons ici une seule inconnu, c’est old_F[j] que l’on peut donc récupérer.
L = b'\x00\x00\x00\x18\x66\x74\x79\x70'
def feistel_round(new_L, new_R):
F = bytes([L[j] ^ new_R[j] for j in range(len(L))])Inverser func_key pour retrouver la clé
Maintenant que nous avons les 8 premiers octets de old_F, on peut essayer d’inverser
l’opération de func_key dessus.
On connait le résultat de func_key, on connait son paramètre, il ne reste plus qu’à découvrir la clé.
def func_key(word, key):
return bytes([(word[i] * key[i % 4]) % 256 for i in range(len(word))])Ici, rien de très compliqué. On peut en effet écrire un script python, qui vient tester toutes les possibilités de
key pour les 4 premières lettres de word (donc old_R).
def feistel_round(new_L, new_R):
F = bytes([L[j] ^ new_R[j] for j in range(len(L))])
for i in range(len(F)):
for key in range(32, 127):
if key * new_L[i] % 256 == F[i]:
print(key)
print("F:", F[i])Pour chaque caractère dans F, on va parcourir les 95 caractères
visibles de la table ascii, et voir si multipliés à l’ancien tableau de droite,
le tout modulo 256, il est égal au résultat de l’opération présent de F.
Encore une fois, ce brute-force n’est pas très long, seulement 760 opérations.
Ce programme nous renvoie ceci :
83
F: 253
72
F: 80
76
F: 156
75
F: 76Ici, ça forme le mot SHLK, ce qui est cohérent par rapport au format des flags.
De ce fait, on sait que la clé est SHLK.
Retrouver la vidéo originale
Maintenant que l’on a la clé, et old_R on peut donc de fait retrouver F en entier:
key = b"SHLK"
def func_key(word):
return bytes([(word[i] * key[i % 4]) % 256 for i in range(len(word))])
def feistel_round(new_L, new_R):
old_R = new_L
F = func_key(old_R)Enfin, il ne reste plus qu’à retrouver la partie gauche du tableau.
Pour celle-ci, il suffit de XOR le new_R avec le résultat de F (égal au F lors du chiffrement).
old_L = bytes([new_R[j] ^ F[j] for j in range(len(new_R))])Et voilà. Une fois fait, il suffit de retourner old_L et old_R, et le tour est joué !
Script final :
import os
key = b"SHLK"
def func_key(word):
return bytes([(word[i] * key[i % 4]) % 256 for i in range(len(word))])
def feistel_round(new_L, new_R):
old_R = new_L
F = func_key(old_R)
old_L = bytes([new_R[j] ^ F[j] for j in range(len(new_R))])
return old_L, old_R
def feistel_decipher(data):
if len(data) % 2 != 0:
data += b"\x00" # padding
mid = len(data) // 2
new_L, new_R = data[:mid], data[mid:]
old_L, old_R = feistel_round(new_L, new_R)
return old_L + old_R
output_file = "L-is-dead.mp4"
input_encrypted = "video_encrypted.mp4"
#Check header MP4
expected_bits = "0000000000000000000000000001100001100110011101000111100101110000"
with open(input_encrypted, "rb") as f:
data = f.read()
ciphered_data = feistel_decipher(data)
with open(output_file, "wb") as f:
f.write(ciphered_data)
print("OK")Une fois la vidéo restaurée, il ne reste plus qu’à en faire son sha256sum:
└─[$] <> sha256sum L-is-dead.mp4
821db7160a76db43d0e7f73d5361939f6c9ee8c95359d8e074473c5353cc1965 L-is-dead.mp4Flag: SHLK{821db7160a76db43d0e7f73d5361939f6c9ee8c95359d8e074473c5353cc1965}