Analyse préliminaire
Avant toute chose, on se permettra de gracieusement dézipper le fichier du challenge avec la méthode de votre choix.
On se retrouve avec
Takeout/
├── archive_browser.html
└── Mail
└── All mail Including Spam and Trash.mbox
1 directory, 2 files
Il n’y a absolument rien dans archive_brower.html
donc notre recherche se portera sur le fichier au format MBOX.
J’ai d’abord essayé de l’ouvrir avec Thunderbird, mais on ne peut visualiser que le mail de Google Community Team, alors qu’on veut lire la conversation de Dumb et Dumby 😞. Un grep
rapide nous montre qu’ils se sont dit des petites choses…
From: Google Community Team <googlecommunityteam-noreply@google.com>
From: Dumby Dumb <ecs.dumb@gmail.com>
From: Dumb Dumber <ecsc.dumber@gmail.com>
From: Dumby Dumb <ecs.dumb@gmail.com>
From: Dumb Dumber <ecsc.dumber@gmail.com>
From: Dumby Dumb <ecs.dumb@gmail.com>
J’ai donc tout simplement ouvert le fichier MBOX avec un éditeur de texte classique et j’ai parcouru le fichier. Sachant que les messages anciens sont en bas et les récents en haut, on va partir du bas du fichier et reconstruire petit à petit la conversation. Finalement on obtient ceci après nettoyage (à lire de bas en haut).
Strange... I thought =F0=9F=92=AD you were strong enough... I put a clue inside, you
will find! =F0=9F=98=89=E2=9C=8C=EF=B8=8F
> I can see your file but I did not find your secret =F0=9F=98=AD
>
>
>> Whaoouaaaou...
>>
>> your cryptosystem is so nice, I want to understand, plz explain more...
>> oh no wait, I prefer to not understand, I trust you!
>> So you will find my secret in the attached ciphered file. I hide my
>> secret a little bit in the file, Im pretty sure youll find it easily, you
>> are so strong =F0=9F=92=AA
>>
>> Cheers
>> Dumby
>>
>>
>>
>>> Hi Dumby,
>>>
>>> I clearly understand your problems, actually crypto guys do not
>>> understand security, me too I can not understand crypto at all but I work
>>> in security.
>>> So trust me... I am better than all of them... proof: I designed a super
>>> cryptosystem that can not be broken =F0=9F=98=81
>>> It is based on a mixed of RSA and DLP, it is super easy to use just
>>> follow the following scrypt. I will decrypt your message using my secret
>>> keys (in particular factorizzation of the modulus and the asiatic
>>> theorem... I do not remember the exact name).
>>>
>>> Cheers
>>> Dumb
>>>
>>> -----------SCRYPT------------
>>> #Public keys
>>> N=3D5363123171977038839829609999282338450991746328236957351089424577488
705612044020173173575291509673672285608288454891765407838828250154229321971
3052500317361
>>> #N=3Dp*q with primes p and q that are part of my secret key
>>>
>>> g1=3D278884196109310089326016641946358633629347952688157111918315643354
813112818757758857829769603871288017018107645861846068743282597523289534896
10371824189861
>>> #g1=3Dg^(r1*(p-1)) mod N where r1 is a secret random
>>> g2=3D480992647393073940870619060635069988411786755872316356061369229874
851039003588578011441990744601060654436135884908772517214394998464485662204
73205526148817
>>> #g2=3Dg^(r2*(q-1)) mod N where r2 is a secret random
>>>
>>> #To encipher the message m of same size as N
>>> #Choose two nounces s1 and s2 (plz keep them secret) and send me c1 and
>>> c2 given by:
>>>
>>> import random
>>> def encipher(m,g1,g2,N):
>>> s1 =3D random.randrange(2**127,2**128)
>>> s2 =3D random.randrange(2**127,2**128)
>>> return (m*pow(g1,s1,N))%N, (m*pow(g2,s2,N))%N
>>>
>>> #To encipher a data use this code and send me the cipher file
>>>
>>> nb_car_block=3D64
>>>
>>> def BlobToIntSeq(m,nb_car_block):
>>> m =3D m + bytes([71,82,114])
>>> l =3D len(m)
>>> r =3D l % nb_car_block
>>>
>>> if not(r =3D=3D 0):
>>> m =3D m + (nb_car_block-r)*bytes([114])
>>> l =3D len(m)
>>>
>>> out =3D []
>>> i =3D 0
>>> j =3D nb_car_block
>>>
>>> while j<=3Dl:
>>> tmp =3D int.from_bytes(m[i:j], "big")
>>> out =3D out + [tmp]
>>> i,j =3D i+nb_car_block,j+nb_car_block
>>>
>>> return out
>>>
>>> import sys
>>>
>>> plainbin =3D open(sys.argv[1], 'rb')
>>> plain =3D plainbin.read()
>>> plainbin.close()
>>>
>>> l =3D len(plain)
>>> plainint =3D BlobToIntSeq(plain,nb_car_block)
>>> cipher =3D open(sys.argv[1]+'.cipher', 'w')
>>>
>>> i =3D 0
>>> for m in plainint:
>>> c1,c2=3Dencipher(m,g1,g2,N)
>>> cipher.write((str(c1)) + '\n')
>>> cipher.write((str(c2)) + '\n')
>>> i=3Di+1
>>>
>>> cipher.close()
>>>
>>>
>>>> Hi Dumb,
>>>>
>>>> I want to send you a secret message.
>>>> It is the expression of what I think I am =F0=9F=98=9C
>>>> But I do not understand nothing in crypto... would please help me!
>>>>
>>>> Cheers
>>>> Dumby
Plusieurs choses à noter :
- les
3D
du scrypt correspondent à=
en hexadécimal, donc il suffit de les enlever pour retrouver le script de chiffrement. Je ne sais pas pourquoi ils se sont incrustés cependant :/ - le chiffrement se base sur RSA et DLP, mais aussi sur le théorême des restes chinois
- et le plus utile…
=F0=9F=98=89=E2=9C=8C=EF=B8=8F
-> 😉✌️=F0=9F=98=9C
-> 😜=F0=9F=98=81
-> 😁=F0=9F=92=AA
-> 💪=F0=9F=92=AD
-> 💭=F0=9F=98=AD
-> 😭
Récupération de la pièce jointe
Ils mentionnent également un fichier. Si vous ouvrez le fichier MBOX vous y trouverez un énorme pavé en Base64 ; il s’agit du fichier WIM.mp4.cipher
. Pour le récupérer j’ai procédé de cette manière :
- nettoyer manuellement pour ne laisser que le pavé en Base64 et on enregistre dans un autre fichier qu’on appellera temporairement
WIM.mp4.cipher.b64
- il faut ensuite enlever les sauts de lignes ainsi que les carriage return avec cette commande :
cat WIM.mp4.cipher.b64 | tr -d '\n' | tr -d '\r' | base64 -d > WIM.mp4.cipher
Vous devez impérativement avoir un fichier tel que :
- la commande
file
retourneASCII text, with very long lines, with no line terminators
- la taille du fichier soit un multiple de 64 ; en l’occurrence de cette taille-ci
24508160 octets
Ainsi vous avez un fichier WIM.mp4.cipher
ayant un type WIM.mp4.cipher: ASCII text
. Il s’agit en fait d’une liste de grands nombres.
Analyse du scrypt
Voici le scrypt utilisé :
import sys, random
##Public keys
N=53631231719770388398296099992823384509917463282369573510894245774887056120440201731735752915096736722856082884548917654078388282501542293219713052500317361
##N=p*q with primes p and q that are part of my secret key
g1=27888419610931008932601664194635863362934795268815711191831564335481311281875775885782976960387128801701810764586184606874328259752328953489610371824189861
##g1=g^(r1*(p-1)) mod N where r1 is a secret random
g2=48099264739307394087061906063506998841178675587231635606136922987485103900358857801144199074460106065443613588490877251721439499846448566220473205526148817
##g2=g^(r2*(q-1)) mod N where r2 is a secret random
##To encipher the message m of same size as N
##Choose two nounces s1 and s2 (plz keep them secret) and send me c1 and c2
def encipher(m,g1,g2,N):
s1 = random.randrange(2**127,2**128)
s2 = random.randrange(2**127,2**128)
return (m*pow(g1,s1,N))%N, (m*pow(g2,s2,N))%N # renvoie c1,c2
##To encipher a data use this code and send me the cipher file
nb_car_block=64
def BlobToIntSeq(m,nb_car_block):
m = m + bytes([71,82,114])
l = len(m)
r = l % nb_car_block
if not(r == 0):
m = m + (nb_car_block-r)*bytes([114])
l = len(m)
out = []
i = 0
j = nb_car_block
while j<=l:
tmp = int.from_bytes(m[i:j], "big")
out = out + [tmp]
i,j = i+nb_car_block,j+nb_car_block
return out
plainbin = open(sys.argv[1], 'rb')
plain = plainbin.read()
plainbin.close()
l = len(plain)
plainint = BlobToIntSeq(plain,nb_car_block)
cipher = open(sys.argv[1]+'.cipher', 'w')
i = 0
for m in plainint:
c1,c2=encipher(m,g1,g2,N)
cipher.write((str(c1)) + '\n')
cipher.write((str(c2)) + '\n')
i=i+1
cipher.close()
Les commentaires nous signalent des formules intéressantes.
$$N = p \cdot q \space \text{ avec p et q premiers}$$ $$g_1 \equiv g^{r_1 \cdot (p-1)} \pmod N$$ $$g_2 \equiv g^{r_2 \cdot (q-1)} \pmod N$$ On se retrouve avec deux générateurs biaisés :O
Petit théorème de Fermat
En effet, d’après le petit théorème de Fermat, pour un nombre premier $p$ et un entier $a$ non multiple de $p$ : $$a^{p-1} \equiv 1 \pmod p$$ Donc pour n’importe quel générateur non multiple de p (ce qui est le cas) : $$g^{p-1} \equiv 1 \pmod p$$ Dès lors, on se retrouve avec ceci : $$g_1 \equiv 1^{r_1} = 1 \pmod p$$ Idem pour $g_2$ par symmétrie.
De la même manière on trouve les coefficients $c_1$ et $c_2$ : $$c_1 = m \cdot g_1^{s_1} \equiv 1 \pmod p$$ $$c_2 = m \cdot g_2^{s_2} \equiv 1 \pmod q$$
Pour retrouver $p$ et $q$, il faut factoriser $N$. Comme $g_1 \equiv 1 \pmod p$ mais pas forcément $\pmod q$, on a : $$p = \gcd(g_1 - 1, N)$$ $$q = \gcd(g_2 - 1, N)$$
Le théorème asiatique
Il ne nous reste plus qu’à récupérer la valeur de $m$. Pour cela on va utiliser le théorème des restes chinois ! Dans le scrypt, le chiffrement se fait par bloc de 64 octets chacun. Sur chaque bloc clair $m$ : $$c_1 = m \cdot g_1^{s_1} \pmod N$$ $$c_2 = m \cdot g_2^{s_2} \pmod N$$ Avec les formules trouvées dans la section du dessus, on peut faire une réduction au modulo $p$ (resp. $q$ pour $c_2$) : $$c_1 = m \cdot g_1^{s_1} \equiv m \cdot 1^{s_1} \equiv m \pmod p$$ Donc directement : $$m_p \equiv c_1 \pmod p$$ Dès lors pour un même entier $m$ on se retrouve avec deux congruences : $$m \equiv m_p \pmod p$$ $$m \equiv m_q \pmod q$$ Et voilà :D Sachant $N = p \cdot q$, on tombe sur une formule pas très jolie à mon goût… $$m = m_p + p \cdot ((m_q - m_p) * (p^{-1} \pmod q)) \pmod N$$ Notes :
- $p^{-1} \pmod q$ est l’inverse de $p$ dans $\mathbb{Z}/q\mathbb{Z}$.
- le tout est pris dans un modulo $N$ donc solution unique dans $[0,N-1]$.
padding ?!
Le script de chiffrement :
- découpe en blocs de 64 octets
- ajoute
b"GRr"
(octets[71,82,114]
) à la fin du message - puis padde avec des
b"r"
jusqu’à un multiple de 64
Il nous suffira donc de procéder à l’inverse pour le déchiffrement.
Exploit du script
Avec tout ce qu’on a trouvé, on peut facilement déchiffrer notre fichier :D Sans rentrer dans les détails voici mon script :
from math import gcd
## Clés de chiffrement
N=53631231719770388398296099992823384509917463282369573510894245774887056120440201731735752915096736722856082884548917654078388282501542293219713052500317361
g1=27888419610931008932601664194635863362934795268815711191831564335481311281875775885782976960387128801701810764586184606874328259752328953489610371824189861
g2=48099264739307394087061906063506998841178675587231635606136922987485103900358857801144199074460106065443613588490877251721439499846448566220473205526148817
len_block = 64
mark_block = b"GRr"
def crt(m_p, m_q, p, q):
inv_p_mod_q = pow(p, -1, q)
t = ((m_q - m_p) * inv_p_mod_q) % q
return (m_p + p * t) % (p * q)
def unpad(data):
i = len(data)
while i > 0 and data[i-1] == 114:
i -= 1
data = data[:i]
return data[:-len(mark_block)]
cipher_path = "WIM.mp4.cipher"
p = gcd(g1 - 1, N)
q = gcd(g2 - 1, N)
pairs = []
with open(cipher_path, "rb") as f:
lines = [line.strip() for line in f if line.strip()]
if len(lines)%2 != 0:
raise ValueError("Nb de lignes impair")
for i in range(0, len(lines), 2):
c1 = int(lines[i])
c2 = int(lines[i+1])
pairs.append((c1, c2))
out = bytearray()
for (c1, c2) in pairs:
m_p = c1 % p
m_q = c2 % q
m = crt(m_p, m_q, p, q)
block = m.to_bytes(len_block, "big")
out += block
plain = unpad(bytes(out))
out_path = cipher_path.replace(".cipher", "")
with open(out_path, "wb") as f:
f.write(plain)
print("FINITO")
Ps : si vous avez un overflow à la ligne m.to_bytes(len_block, "big")
cela vient nécessairement de votre fichier WIM.mp4.cipher
. Référez-vous plus haut pour corriger le problème ;)
Enfin du forensics :D
Maintenant on qu’on en a terminé avec cette fichue crypto, on va pouvoir se régaler !
On se retrouve donc avec un fichier WIM.mp4
: WIM.mp4: ISO Media, MP4 v2 [ISO 14496-14]
.
Comme d’habitude mon premier réflexe est de lancer la commande exiftool
dessus :
ExifTool Version Number : 12.76
File Name : WIM.mp4
Directory : .
File Size : 3.8 MB
[...]
Handler Description : CLUE->JACKET ;-)
[...]
Description : LSooRkxBRyA6IEVDU0N7c2hhMjU2KHNvbmcncyB0aXRsZSBpbiBsb3dlciBjYXNlIHdpdGhvdXQgc3BhY2UpfSkqLQo=
[...]
On remarque un champ Description
avec du Base64 dedans ! En le décodant on obtient
-*(FLAG : ECSC{sha256(song's title in lower case without space)})*-
Ouais, ç’aurait été trop facile sinon…
Personnellement, je n’ai pas vraiment compris ce que nous amenait le Handler Description
, et je crois qu’on en a pas besoin pour terminer ce challenge selon moi.
Il existe de nombreux outils pour lire des fichiers MP4. J’ai utilisé la commande ffplay
vu que c’est juste pour regarder ce qu’il y a dedans. On remarquera qu’on n’a pas de son :(
Bref. On cherche le titre de la musique. Je ne connais pas ce clip donc je vais devoir chercher… Ce que j’ai fait est relativement simple :
- j’extraie une frame de la vidéo avec la commande
ffmpeg -ss 00:00:05 -i WIM.mp4 -frames:v 1 frame.png
- je fais un une recherche inversée sur internet
Et rien qu’avec ça on tombe très vite sur cette chanson du groupe 2EN1. Il semblerait qu’on ai affaire à un auteur fan de k-pop ^^.
On récupère donc le titre : I Am The Best
.
Et le hash se récupère directement : echo -n "iamthebest" | sha256sum
Attention ! L’option -n
est très importante car la commande echo
rajoute automatiquement un \n
à la fin du string.
On a plus qu’à recomposer le flag : ECSC{hash}
NB : Il y a un fichier PNG caché dans le MP4… Et il est vrai que 2EN1 y est écrit, donc a priori cela peut ouvrir des pistes.
Merci pour le sympathique challenge :)