AlexCTF 2k17 - Many Times Secret

· 808 words · 4 minute read
Cryptographie
alexctf

Challenge présenté lors du premier CTF organisé par le MSP TechClub, rattaché à la faculté d’ingénierie, à Alexandrie. Many time secrets est le deuxième challenge de la catégorie cryptographie.

Sommaire

  • Indices
  • Python is your friend
  • Expérimentation
  • Trouver la longueur de la clef
  • Casser le code

Indices

Voici la description du challenge

This time Fady learned from his old mistake and decided to use onetime pad as his encryption technique, but he never knew why people call it one time pad!

Et le contenu du fichier, cela ressemble à des données au format hexadécimal car il y a un nombre pair de chiffres hexa.

0529242a631234122d2b36697f13272c207f2021283a6b0c7908
2f28202a302029142c653f3c7f2a2636273e3f2d653e25217908
322921780c3a235b3c2c3f207f372e21733a3a2b37263b313012
2f6c363b2b312b1e64651b6537222e37377f2020242b6b2c2d5d
283f652c2b31661426292b653a292c372a2f20212a316b283c09
29232178373c270f682c216532263b2d3632353c2c3c2a293504
613c37373531285b3c2a72273a67212a277f373a243c20203d5d
243a202a633d205b3c2d3765342236653a2c7423202f3f652a18
2239373d6f740a1e3c651f207f2c212a247f3d2e65262430791c
263e203d63232f0f20653f207f332065262c3168313722367918
2f2f372133202f142665212637222220733e383f2426386b

Ensuite d’après la description et le titre du challenge “Many time secrets” on peut se douter que Fady a utilisé plusieurs fois la même clef pour chiffrer le message. On sait aussi que les flags du CTF sont sous la forme ALEXCTF{ … }. Il reste à supposer que le texte a été chiffré avec un xor.

Python is your friend

Petit rappel sur le xor : prenons A texte clair, B la clef et C le texte chiffré alors on a : A ^ B = C C ^ B = A mais aussi A ^ C = A ^ (A ^ B) = 1 ^ B C’est a dire qu’à partir du texte clair et du texte chiffré on peut retrouver la clef par un simple xor.

Commençons par déchiffrer le texte avec ce que l’on sait, le début de la clef ALEXCTF{

#!/usr/bin/python
import os, sys
import binascii
import re

key="ALEXCTF{"
# sys.argv[1] nom du fichier à déchiffrer
file = open(sys.argv[1], "r") 
# on enlève les retour à la ligne et on converti le tout en caractère
chiffre = binascii.unhexlify(file.read().replace("\n","")) 

# Pour chaque caractère dans le texte on fait un xor avec un caractère de la clef
# lorsqu'on arrive à la fin de la clef on reprend au début d'où le modulo
decode = ""
for i in range(0, len(chiffre)):
	decode += chr(ord(chiffre[i]) ^ ord(key[i%len(key)])) 
# Afficher le texte 
print(decode)

result = open("result.txt","w")
result.write(decode)
result.close()

Et voici ce que l’on obtient : Du bouzin, mais si on regarde bien on est sur la bonne piste, le début est Dear Fri…., je dirais Dear Friend.

Expérimentation

On vient de supposer que le début du message en clair est Dear Friend. On réalise les modifications dans le fichier result.txt

Reprenons notre script, pour faire le xor entre le texte clair et le texte chiffré. Voici le code, qui prend un argument supplémentaire le fichier contenant le texte clair supposé, soit result.txt puisque on vient de le modifier.

#!/usr/bin/python
# -*- coding:utf-8 -*-
import os, sys
import binascii
import re

key="ALEXCTF{"

file = open(sys.argv[1], "r")
chiffre = binascii.unhexlify(file.read().replace("\n",""))
file.close()

# On ouvre le texte clair supposé
file = open(sys.argv[2], "r")
message = file.read()
file.close()

# On xor le clair et le chiffré
keyfound=""
for i in range(0, len(chiffre)):
	keyfound+= chr(ord(chiffre[i]) ^ ord(message[i]))
# On affiche la clef
print(keyfound)

decode = ""
for i in range(0, len(chiffre)):
 	decode += chr(ord(chiffre[i]) ^ ord(key[i%len(key)]))
print(decode)

result = open("result.txt","w")
result.write(decode)
result.close()

Ainsi on obtient en sortie, ALEXCTF{HER… .

Trouver la longueur de la clef

Maintenant pour connaître la taille de la clef on va tester les longueurs possible en rajoutant du padding et examiner la sortie attentivement. On sait que la clef se répète donc avec la bonne taille on va pouvoir déchiffrer certaines zones du message. On modifie le script,

#!/usr/bin/python
# -*- coding:utf-8 -*-
import os, sys
import binascii
import re

key="ALEXCTF{HER"

file = open(sys.argv[1], "r")
chiffre = binascii.unhexlify(file.read().replace("\n",""))
file.close()

# On ouvre le texte clair supposé
file = open(sys.argv[2], "r")
message = file.read()
file.close()

# On xor le clair et le chiffré
keyfound=""
for i in range(0, len(chiffre)):
	keyfound+= chr(ord(chiffre[i]) ^ ord(message[i]))
# On affiche la clef
print(keyfound)

# Brute force taille clef
for k in range(0,16):
	key+="." # Padding	
	decode = ""
	for i in range(0, len(chiffre)):
 		decode += chr(ord(chiffre[i]) ^ ord(key[i%len(key)]))
	print("For key size %d =================" % len(key)) 	
	print(decode) # Afficher le résultat du déchiffrement
	print("=====================================")

result = open("result.txt","w")
result.write(decode)
result.close()

Avec une taille de 26 caractères on remarque des bouts de phrases en anglais,

Casser le code

Maintenant que l’on connaît la taille de la clef, pas besoin de la partie bruteforce, et key vaut pour l’instant ALEXCTF{HER…………..} . Il ne reste plus qu’à compléter le fichier result.txt, lancer le script, mettre à jour la clef et recommencer. A la fin on obtient,

Dear Friend, This time I understood my mistake and used One time pad encryption scheme, I heard that it is the only encryption method that is mathematically proven to be not cracked ever if the key is kept secure, Let Me know if you agree with me to use this encryption scheme always.

Avec la clef ALEXCTF{HERE_GOES_THE_KEY} ;)

Share