[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).

A few hours ago, but two months after the list of finalists announce, the NIST published a long-awaited report on the SHA-3 finalists selection process. The full 32-pages report is available here. In this post, I would like to emphasize and summarize the more salient facts.

The goal of NIST’s report consists in

[...] explaining the evaluation and selection process for the second round of the competition. A summary of the public analyses of each second-round candidate, and justifications for whether or not a candidate is advanced to the third (and final) round of the competition are provided [...].

The NIST mentions some of the information sources used to perform the selection:

For its security evaluations, NIST studied the large amount of feedback received from the cryptographic community via e-mail discussions in the official mailing list, and the SHA-3 Zoo web page, as well as the security arguments presented by the designers. NIST researchers also conducted their own internal cryptanalysis of the candidates.

For its software evaluations, NIST considered various benchmarking comparisons. The primary contributor was the ECRYPT Benchmarking of All Submitted Hashes (eBASH) project that provided speed measurements of the SHA-3 candidates on a wide variety of 32- and 64-bit platforms. Another software-benchmarking project – the eXternal Benchmarking eXtension (XBX) – provided performance results on small devices. [...]

NIST’s foremost selection criterion was security, which is not very surprising:

Security was NIST’s primary criterion in selecting the finalists. None of the second-round candidates was completely broken according to the criteria NIST laid out [...]. NIST received many security observations, including “partial attacks” on several candidates, i.e., cryptanalysis of weakened variants. Absent more conclusive information on the security of these candidates, a principal concern was the potential for extending these cryptanalyses. NIST tried to extrapolate the severity of any partial attacks, and thus to estimate the “security margin”, as an estimate of susceptibility of the full hash algorithms to future attacks.

An important caveat is that this extrapolation is only meaningful when the algorithm has received a significant amount of cryptanalysis, and when there is a good deal of granularity in choosing any tunable parameter that was provided for the algorithm. [...] Algorithms that received very little cryptanalysis, and algorithms without a clearly adjustable security parameter were, therefore, evaluated with more suspicion.

The second main criteria was, also unsurprisingly, performances, with a rather important focus on the software parallelism capabilities of the candidates:

Performance was also important in choosing the finalists. NIST chose finalists that could be implemented on as wide a variety of platforms as possible, while still maintaining reasonably good performance. [...]

Discussions included the implementation possibilities for the algorithms: some algorithms allowed very high levels of fine-grain parallelism that could be realized well with hardware, some exploited parallelism with vector units, and some seemed to fully exploit the considerable parallelism that could be achieved by conventional superscalar arithmetic logic units (ALUs) capable of simultaneously launching several instructions per clock cycle.  NIST also noted that several algorithms exploited the power of 64-bit-wide ALUs. Candidates that performed poorly in hardware or on platforms without a specialized AES instruction, for example, were not selected, since many platforms do not provide this capability.

Another selection criterion was the way how the algorithms were tweaked by their designers during the competition:

Although NIST allowed the designers to tweak (i.e., make minor modifications to) their algorithms for the second round, extensive tweaks in order to avoid certain attacks were a cause for concern. NIST was generally comfortable with tweaks to the number of rounds or to constants, but more suspicious of changes that seemed to affect the structure of the compression functions, since these tweaks made much of the first-round cryptanalysis on the algorithms obsolete. However, NIST did consider whether the best attacks on some of the candidates seemed amenable to mitigation by a simple modification.

Provable security was also considered in a positive way, obviously but it is interesting to note that it was not part of the main selection criteria:

NIST also considered positive security arguments and proofs in making its decision. Since block cipher cryptanalysis appears to be more advanced than hash algorithm cryptanalysis, arguments that link the security of the candidates to a component that can be treated as a block cipher or fixed permutation were especially valuable.

Finally, all the exotic features brought by the candidate algorithms were not so important:

Additional design features, such as a built-in pseudorandom function (PRF) or an authenticated encryption mode were also briefly discussed, but played little part in the selection of the finalists.

Here is a copy-paste of the argumentation for the decisions of (non-)selection for each of the 14 semi-finalists:

BLAKE was selected as a finalist, due to its high security margin, good performance in software, and its simple and clear design.

Although BMW has very good software performance, and good potentials for pipelining and area-efficient high-throughput values, a disadvantage of the algorithm is its irregular and not-well-understood design. Since the compression function of BMW does not have a conventional iterated-round structure, there appears to be no obviously simple way to adjust the security margin, or to trade performance for security. Moreover, the attacks on the algorithm, even after an extensive tweak, did not provide confidence in the security of the algorithm. For these reasons, BMW was not selected as a finalist.

CubeHash is a simple, well-understood design that received extensive third-party analysis. The design is suitable for constrained environments, as it requires a small area in hardware, and little RAM or ROM in software. However, it has poor performance without the use of a vector unit, resulting in a large overhead for short messages. Moreover, no single variant for the 512-bit digest size achieves the required theoretical security with acceptable performance. Another disadvantage of the design is the existence of the symmetric properties that are arguably a potential avenue for future attacks. NIST felt that an additional year of study would not be enough to determine whether or not the symmetric properties pose a threat. Therefore, NIST felt that CubeHash could not be chosen as SHA-3 with confidence, and thus should not be selected as a finalist.

Although ECHO appears to be a simple secure design, it was not selected as a finalist, due to its all-around poor performance.

Fugue is an innovative design and has decent, all-around performance. Its designers also proved that collisions are unlikely to be found using differential cryptanalysis techniques. Nonetheless, Fugue has received only a very small amount of cryptanalysis. The most important published result, Aumasson and Phan’s distinguisher on Fugue’s finalization function, raised some concern. NIST felt that it would not be possible to establish confidence in the hash algorithm after another year of cryptanalysis; therefore, it was not selected as a finalist.

Grøstl was selected as a finalist because of its well-understood design and solid performance, especially in hardware. While Grøstl’s security margin is not ideal, NIST views it in light of the extensive amount of cryptanalysis that has been published, both on Grøstl itself and the larger AES structure on which Grøstl is based. Due to the large amount of existing cryptanalysis, NIST feels that future results are less likely to dramatically narrow Grøstl’s security margin than that of the other candidates.

Hamsi was not selected as a finalist, mainly due to the second-preimage attacks and high ROM requirements.

JH was selected as a finalist because of its solid security margin, good all-around performance, and innovative design.

Keccak was selected as a finalist, mainly due to its high security margin, its high throughput and throughput-to-area ratio and the simplicity of its design.

Although Luffa is an above-average performer, especially in hardware, it has not received as much cryptanalysis as many of the other second-round candidates. The little cryptanalysis there has been on Luffa, however, raises significant questions about its security; the security margin of the compression function is quite small, and full distinguishers on the sub-permutations have also been discovered. In addition, there is no published security proof showing that even strong sub-permutations would lead to a strong hash function. Therefore, Luffa was not selected as a finalist.

Shabal uses a novel design for its mode of iteration and basic building blocks. It was not, however, selected as a finalist, mainly due to security concerns. Although the security of the full hash algorithm was not compromised, the discovery of non-randomness properties with low time complexities raised concerns among NIST’s cryptographers about the possibility of more powerful attacks in the future. While Shabal’s security proof was modified to take known attacks into account, it did not convince NIST’s cryptographers that Shabal would remain secure against future attacks.

SHAvite-3 was not selected as a finalist, due to the lack of security in the key schedule of the underlying block cipher, leading to a relatively low security margin for the 512-bit version of the hash function. In addition, SHAvite-3 has a relatively low throughput-to-area ratio.

SIMD was not selected as a finalist, due to its large area requirements and the existence of the symmetric states.

Skein was selected as a finalist, mainly due to its high security margin and speed in software.

Interestingly, reading this, one can speculate a bit on NIST’s internal discussions based on the length of the justification paragraph: while Blake, JH, Keccak and Skein, as well as ECHO, Hamsi, Shavite-3 and SIMD appear to have been easy candidates for selection and  non-selection, respectively, more justifications are provided for the seemingly borderline candidates BMW, CubeHash, Fugue, Luffa, Shabal and Grøstl, the latter looking like being the more discussed finalist. But this last paragraph is only pure personal speculation, of course !