[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…

Vendredi prochain 4 mars 2011 aura lieu la 4ème édition d’Insomni’Hack, manifestation sympathique organisée par la société SCRT. À cette occasion, en plus du concours de hacking, une série de conférences aura lieu l’après-midi dès 14h sur le site de l’HEPIA à Genève. J’aurai le privilège de donner un exposé intitulé très, mais alors très pompeusement «La cryptographie» (tout un programme…). Les autres interventions seront données par Axelle Apvrille, Dominique Clementi, Sébastien Bombal, Alexandre Herzog et Bruno Kerouanton.

Quelques jours après, le mardi 8 mars 2011, dès 16h30, dans les locaux de la Fédération des Entreprises Romandes à Genève, j’interviendrai dans le cadre d’une manifestation organisée par le CLUSIS et baptisée «Chiffrer ou ne pas chiffrer, telle est la question ! ». Mon exposé est intitulé «Cryptographie: de la théorie à la pratique» et tentera d’expliquer que, «dans le domaine de la cryptographie, le passage de la théorie à la pratique, du monde académique au monde industriel, n’est pas souvent un long fleuve tranquille, que ce soit au niveau de l’apport d’innovations ou de l’implantation de solutions pratiques.» Les autres intervenants seront Grégoire Ribordy (ID Quantique) et Christian Roch (Pictet).

Dans le cadre des activités du Cercle Littéraire de la Société Jurassienne d’Émulation, Didier Müller, professeur de mathématiques et d’informatique au vénérable Lycée Cantonal de Porrentruy, féru de cryptographie, père de l’excellent site web apprendre-en-ligne.net (qui comporte notamment une section « Ars Cryptographica » que je recommande vivement !) et auteur de plusieurs ouvrages de vulgarisation dans le domaine, donnera une conférence intitulée « Les codes secrets dans la littérature » le jeudi 20 janvier 2011 à 20h00, Salle des Hospitalières de l’Hôtel-Dieu, Grand-Rue 5, à Porrentruy. Je ne pourrai malheureusement pas m’y rendre, vu l’éloignement géographique, mais je suis convaincu que cette conférence sera passionnante !