[UPDATE] Les slides de mon intervention lors des conférences de l’après-midi sont désormais en ligne.
Insomni’hack 2011 a vécu et bien vécu ! Les conférences de l’après-midi étaient très variées (cf. le billet de Bruno Kerouanton pour un résumé) et nous ont rapidement amené au concours tant attendu. Je me suis finalement retrouvé à transpirer pour une équipe fort sympathique (les pycured) formée de quelques-uns de mes anciens étudiants du MSE HES-SO. Nous avons terminé à un très honorable cinquième rang, vu la concurrence, après avoir été troisièmes jusqu’à une demi-heure de la fin. Félicitations aux employés de SCRT pour l’organisation parfaite !
Étant données mes penchants techniques personnels, je me suis tout naturellement attaqué en premier aux trois challenges «Crypto», dont je me propose de vous donner ici un aperçu.
Le premier challenge, le plus facile et le moins intéressant à mon goût, consistait à décrypter un texte donné sous la forme d’un fichier ASCII secret.txt. En plus, on nous donnait comme indice une table de fréquence de l’anglais, ce qui faisait immédiatement penser à une substitution simple. À l’aide d’un outil tel que Cryptool v1.4.30 (plus simple à utiliser que la version 2.x, à mon humble avis), il est possible de casser très facilement ce type de cryptogramme en utilisant une méthode statistique, de récupérer la clef, et de déchiffrer ensuite la phrase-challenge, le tout en quelques minutes.
Le second challenge que j’ai résolu était en fait le troisième. On nous donnait un fichier insomniDES.tar.gz, qui contenait une implémentation de l’algorithme DES, ainsi qu’un algorithme de génération de clef «maison» contenu dans le fichier insomniDES.py:
def generateKey():
"Generates a new random DES key"
stage1 = []
for i in range(0, 8):
stage1.append(random.choice(range(0, 256)))
stage2 = map(lambda x: x[0] ^ x[1], zip(stage1, KGEN_IV))
stage3 = map(lambda x: x[0] ^ x[1], zip(map(lambda x: x[0] * x[1], zip(KGEN_XB, stage1)), stage2))
stage4 = [stage3[KGEN_SB[i]] for i in range(0, 8)]
stage5 = [stage4[i] for i in range (0, 8, 2)]
stage5 += [stage5[i] for i in range(3, -1, -1)]
return bytes2str(hexStr2bytes(sha256(bytes2str(stage5)).hexdigest())[0:8])
Finalement, on nous donnait un texte chiffré et encodé en base64 à décrypter:
ma1IblbRhPm1ouBqeSr/Ai3lY16s/lb3bw77fj3h0+BUdUKi2wWAny7dpGtpRtq2
On peut tout de suite penser à un générateur aléatoire faible, mais le fait qu’il utilise les routines standard de Python (qui, soit dit en passant, ne sont pas recommandées à utiliser pour générer des clefs cryptographiques) m’a conduit à regarder la routine generateKey()de plus près. À l’aide de quelques print() judicieusement placés, il est vite apparu qu’avant d’entrer dans le SHA-256, la variable state5 ne possédait qu’une entropie de … 8 bits (ici, les octets sont exprimés en base 10):
[26, x, 149, 14, 14, 149, x, 26]
Quelques lignes de brute-force plus tard
for i in range (256):
key = bytes2str(hexStr2bytes(sha256(bytes2str([26, i, 149, 14, 14, 149, i, 26])).hexdigest())[0:8])
print (decrypt (key, "ma1IblbRhPm1ouBqeSr/Ai3lY16s/lb3bw77fj3h0+BUdUKi2wWAny7dpGtpRtq2"))
on tombait rapidement sur la soluion
J'adore Insomni'hack! Je t'offre une biere!
Le second challenge était plutôt du genre … coriace! On nous donnait l’URL d’un script qui permettait de chiffrer et de déchiffrer des données au moyen d’un clef inconnue avec l’algorithme Triple-DES en mode CBC. Le script de déchiffrement ne retournait évidemment pas le résultat, ni la clef. Par contre, il retournait une information très utile, à savoir si le déchiffrement s’était correctement passé ou si une erreur dans le traitement du padding était apparue. Nous étions donc dans la situation idéale d’une attaque de type “padding-oracle”. Cette attaque a été décrite par Serge Vaudenay (LASEC/EPFL) à Eurocrypt 2002, et est revenue récemment très à la mode (cf. le MS10-070).
L’algorithme Triple-DES en mode CBC est capable de chiffrer des données dont la longueur est un multiple de 8 octets. Si les données à chiffrer ne possèdent pas la bonne longueur, on rajoute du «padding», à savoir des octets additionnels jusqu’à obtenir une longueur multiple de 8 octets. La méthode de «padding» la plus connue est celle standardisée dans PKCS #5: s’il manque un octet, on rajoute l’octet 0x01; s’il manque deux octets, on rajoute deux octets à 0x02, etc. Les valeurs de padding acceptées sont donc
0x?? 0x?? 0x?? 0x?? 0x?? 0x?? 0x?? 0x01
0x?? 0x?? 0x?? 0x?? 0x?? 0x?? 0x02 0x02
0x?? 0x?? 0x?? 0x?? 0x?? 0x03 0x03 0x03
…
0x?? 0x07 0x07 0x07 0x07 0x07 0x07 0x07
0x08 0x08 0x08 0x08 0x08 0x08 0x08 0x08
Si l’on est capable de faire la différence, après le déchiffrement, entre un bloc possédant un «padding» valide et un bloc ne passant pas ce test, on obtient un oracle de déchiffrement qui fonctionne en aveugle, d’une certaine manière.
Grossièrement, l’attaque fonctionne de la manière suivante: on fabrique un texte chiffré de deux blocs formé d’un IV concaténé avec un bloc à décrypter. Pour récupérer le huitième octet (celui de droite) à la sortie du Triple-DES, on itère les 256 valeurs possibles sur le huitième octet du premier bloc (de l’IV, donc). Quand l’oracle nous indique «padding correct», il y a une forte probabilité que l’octet de droite de la sortie du Triple-DES est égal au XOR de 0x01 et de l’octet itéré dans l’IV, ce qui nous permet de récupérer l’octet de droite du bloc à décrypter. Pour attaquer le deuxième octet, on fixe l’octet de droite de l’IV à 0x02 XOR l’octet récupéré précédemment à la sortie du Triple-DES, et on itère le septième octet de l’IV jusqu’à ce que l’oracle indique «padding correct». Cette fois, le septième octet de la sortie du Triple-DES est égal au XOR de 0x02 et du septième octet de l’IV. En répétant ce processus, on est capable de décrypter tout le bloc octet après octet, puis tout le message à casser ! Le script que j’ai écrit pour automatiser l’attaque est le suivant:
# Insomni'Hack 2011
# Second crypto challenge write-up
# by @cryptopathe
import urllib2
# Stolen these useful routines from the third crypto challenge
def hexStr2bytes(hexString):
"Converts '01020304AABB' to [1, 2, 3, 4, 170, 187]"
return [int(extendHexString(hexString)[i: i+2], 16) for i in range(0, len(extendHexString(hexString)), 2)]
def extendHexString(hexString):
"Ensures that the (character-wise) length of an hex string is even"
return ('0' * (len(hexString) % 2)) + hexString
def bytes2hexStr(bytes):
"Converts [0x01, 0x02, 0xAA, 0xFF] to '0102AAFF'"
return ''.join(['%02X' % d for d in bytes])
def bytes2str(byteList):
"Converts [72, 101, 108, 108, 111, 32, 119, 111, 114, 108, 100] to 'Hello world'"
return ''.join([chr(c) for c in byteList])
# End of stolen material
base_url = "http://epreuves2.insomni.hack:8080/dec/?t="
ciphertext = "534EE451C9510604279896DEB97ACE72EE9FA6DCA08FF09B86A37D6BBA3FE272B3CAB385AB0F31D1"
plaintext = ""
for b in range (4):
# We handle each one of the four 8-bytes blocks, forgetting the first one (IV)
block = ciphertext[(16+b*16):(16+(b+1)*16)]
clear = ""
# Perturbation vector
v = [0, 0, 0, 0, 0, 0, 0, 0]
# Recovered bytes at the output of the Triple-DES decryption operation
clear_byte = [0, 0, 0, 0, 0, 0, 0, 0]
# Cracking each byte one after the other
for o in range (8):
# Brute-forcing of the currently cracked byte
for i in range (256):
v[7 - o] = i
hh = bytes2hexStr (v)
# Construction of the url:
# We ask the oracle to decrypt a 2-block ciphertext,
# built as v[] || block[]
# where v[] is the perturbation vector and block[]
# is the ciphertext to be decrypted
u = urllib2.urlopen (base_url + hh + block)
# Checking whether the padding check was successful
if "ussi" in ''.join(u):
# We recover the (7-o)-th byte out of the Triple-DES
clear_byte[7-o] = i ^ (o + 1)
clear = extendHexString (str (hex (clear_byte[7-o])[2:]) + clear)
# We build the next perturbation vector
for i in range (o + 1):
v[7-i] = clear_byte[7-i] ^ (o + 2)
break
plaintext = plaintext + clear
# plaintext_bytes contains the bytes right after the Triple-DES decryption,
# but still XORed with the respective ciphertext blocks
plaintext_bytes = hexStr2bytes (plaintext)
ciphertext_bytes = hexStr2bytes (ciphertext)
decrypted_bytes = []
# We now apply the CBC XOR-feedback
for i in range (32):
decrypted_bytes.append (plaintext_bytes[i] ^ ciphertext_bytes[i])
# Here we go ...
print (bytes2str(decrypted_bytes))
Au final, près de deux heures (!) de travail pour arriver à mes fins, dont au minimum une heure pour me rendre compte qu’il ne fallait pas oublier d’appliquer le XOR de feedback sur la sortie des Triple-DES avant d’obtenir un texte clair, et surtout, pour voir que j’avais mal copié-collé le texte chiffré à casser…
