Hack.lu 2010 CTF – Breiers deathmatch 150 writeup
Tout comme la première épreuve de ce CTF, “Breiers Deathmatch” nécessite de se connecter à un socket afin de résoudre un petit problème de cryptographie.
Voilà ce que l’on obtient:
zealot@zealot-ubuntu:~$ nc pirates.fluxfingers.net 8007 Hi. This is your friendly 'Decryption Oracle' We have implemented a well-known public-key cryptosystem. Guess which ;) Modulo: 5628290459057877291809182450381238927697314822133923421169378062922140081498734424133112032854812341 Generator: 99 Public Key: 1357444342017783248393087124629116477277548748140968449155264250239122362719894347099351280643528244 Ciphertext: (725621251569095394939579710795330618302309600181914055263604223394765781542656134451324431100895915, 4070115595888194250035977089244744631601569744031270035429895678802594965330866902146638459322313629) Insert your Ciphertext-Tuple for me to decrypt - comma seperated (e.g. 5,6) >>>
Comme l’indique le texte introductif, il s’agit d’un oracle qui permet de déchiffrer tout tuples qui lui sont fournis. Excepté, bien entendu, le tuple Ciphertext, correspondant au texte à déchiffrer:
# Test en fournissant Ciphertext à l'oracle Ciphertext: (725621251569095394939579710795330618302309600181914055263604223394765781542656134451324431100895915, 4070115595888194250035977089244744631601569744031270035429895678802594965330866902146638459322313629) Insert your Ciphertext-Tuple for me to decrypt - comma seperated (e.g. 5,6) >>> 725621251569095394939579710795330618302309600181914055263604223394765781542656134451324431100895915, 4070115595888194250035977089244744631601569744031270035429895678802594965330866902146638459322313629 Duh! This would be too easy, right? # Failed!
Il s’agit alors de trouver un moyen d’exploiter l’oracle afin de déchiffrer Ciphertext. Pour cela, il faut tout d’abord déterminer l’algorithme de chiffrement utilisé.
Comme l’indique le texte introductif, il s’agit d’un algorithme “bien connu”. Bien sûr, en voyant “public key”, on pense tout de suite à RSA mais les informations fournies ainsi que le chiffrement sous forme de tuple ne correspondent pas.
Après un peu de recherche sur les mots clé “modulo generator public key”, on tombe sur cette page de Wikipedia. Les informations fournies sur la clé publique ainsi que la forme de tuple obtenu après chiffrement correspondent bien, on est sur la bonne piste: il s’agit de Elgamal.
En regardant un peu plus loin dans l’article, on apprend que Elgamal est “inconditionnellement malléable”. Cela signifie que si l’on dispose d’un tuple (K,C), correspondant à un texte clair M, et d’une fonction f, il est possible de construire un tuple (K,C’) correspondant au texte clair f(M) et ce, sans même connaître M.
Dans le cadre de l’épreuve, il suffit de construire un tuple (K,C’) à partir du tuple (K,C) puis de le faire déchiffrer par l’oracle et ainsi obtenir le message de départ M à une fonction f, connue, près.
Pour rester simple, on choisit f: x -> 2x. On construit alors (K,2C) que l’on donne à l’oracle. On obtient directement f(M)=2M, le message clair multiplié par 2.
Note: du fait du design de Elgamal, le calcul du tuple (K,C’) permettant d’obtenir f(M) se réduit au calcul de (K,f(C)) lorsque f est linéaire. Pour les fonctions non linéaires, cela n’est pas le cas.
Voila ce que l’on obtient:
zealot@zealot-ubuntu:~$ nc pirates.fluxfingers.net 8007 Hi. This is your friendly 'Decryption Oracle' We have implemented a well-known public-key cryptosystem. Guess which ;) Modulo: 5628290459057877291809182450381238927697314822133923421169378062922140081498734424133112032854812341 Generator: 99 Public Key: 1357444342017783248393087124629116477277548748140968449155264250239122362719894347099351280643528244 Ciphertext: (337481092010668177995521510609737928693656417603643759865031427790665841222592379785408374500639819, 5468791168591665336512621312134042845482772477674869074198327191833117917631701449640781514520928719) Insert your Ciphertext-Tuple for me to decrypt - comma seperated (e.g. 5,6) [1]+ Stopped nc pirates.fluxfingers.net 8007 # Python pour le calcul de 2C zealot@zealot-ubuntu:~$ python >>> i=5468791168591665336512621312134042845482772477674869074198327191833117917631701449640781514520928719*2 >>> print i 10937582337183330673025242624268085690965544955349738148396654383666235835263402899281563029041857438 >>> # Déchiffrement de (K,2C) par l'oracle zealot@zealot-ubuntu:~$ fg nc pirates.fluxfingers.net 8007 337481092010668177995521510609737928693656417603643759865031427790665841222592379785408374500639819,10937582337183330673025242624268085690965544955349738148396654383666235835263402899281563029041857438 Decrypted: 1772769743432258561317602 # Enfin, calcul de 2M/2, toujours avec python :] zealot@zealot-ubuntu:~$ python >>> i=1772769743432258561317602/2 >>> print i 886384871716129280658801 <----- Voilà le flag >> print "%x"%i bbb3052a6d7f0a808d71
La valeur obtenue correspond en fait au flag et ne semble pas avoir de signification particulière…
Remarque: le tuple Ciphertext change à chaque connexion mais le texte clair reste le même. Cela est l’une des particularités de Elgamal.
Outre Wikipédia, un autre article plus complet et relativement abordable est disponible ici. Il présente une approche claire du fonctionnement de Elgamal (d’un point de vu mathématiques) ainsi que l’attaque que l’on a mise en oeuvre sur la propriété de maléabilité (page 22).
Ce writeup, et bien d’autres, est aussi disponible sur le site http://hacklu.fluxfingers.net section challenges.
Bien joué dude ! Très intéressant.
[...] Generator: [...] Nibbles microblog This entry was posted in Sécurité Informatique and tagged 2010, Breiers, deathmatch, Hack.lu, [...]