HackDay 2024 | Show me the way | [Crypto]

HackDay 2024 - Write-Up - Show me the way [Crypto]

Statement

L'agent secret 007 nous a donné un fichier classé et nous a donné le moyen de pouvoir le lire, malheureusement, il n'a pas pu le faire pour éviter tout soupçons au sein du Hack107. Déchiffrez les texte contenu dans le fichier pour y lire le nom du protocole secret !

The secret agent 007 gave us a classified file and gave us the means to read it, unfortunately, he could not do it to avoid any suspicion within the Hack107. Decrypt the text in the file to read the flag! 

Récupérez les fichiers et récupérez le nom du protocole activé ! Formatage du drapeau: HACKDAY{PROTOCOLE}

Download the files and get the flag data ! FLAG FORMAT : HACKDAY{PROTOCOL}  

Author : Chelinka
Points : 443
Solves : 20

Files analysis

This challenge consist of two files :

1. encrypt.py : the source of the encryption
2. secretmessage.txt : components of the public key, and the ciphertext

The file encrypt.py

After analyzing the source code, I didn’t find anything interesting except:

• We don’t know how primes are generated, except that their generation doesn’t seem random, so the vulnerability may lie in p and q
• Before the encryption, the flag is reversed (flag = flag[::-1]), but this info is useless as the plaintext is not stereotyped

All in all, this python file doesn’t help that much, but that was predictable based on this message of the chall maker : “Et pour show me the way ça marche sans le chiffrement, c’est du bête RSA derrière normalement” (en: source code is not required for a simple RSA implementation).

The file secretmessage.txt

After analyzing the source code, I’ll now talk about the public key parameters:

About e, the choosen value dosen’t seem to have any weakness (e = 0x10001). Indeed, 0x10001 is a common value and is large enough even four our size of N. We can deduce that the issue has to come from N.

Unfortunetly, about N … this is pretty robust. We are dealing with a 4060-bit long number. I’ve checked quickly its binary/hex representation but I didn’t find anything.

Challange resolution

Following this inconclusive analysis, I’ve deciced to try factoring N, but after tryed the most of more classical factorization algorithm I’ve gave up this option.

I then turned to intensive reading of RSA write-ups on ctftime and after the sixth pages, I’ve found this write up (thanks jack4818). It exploited a technic I was not familiar with it. It involved examining the representations of N in different bases to find a base where N has a lot of 0s.

So, I analyzed N in differents bases using the str(base=i) method on sage integer. When it came to base 7, here what I obtained:

sage: N.str(base=7)
'1000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000030000000000000000000000000000000000000000000000000001000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000030000000000000000000000000000000000000000000000000000000000000010000000000000000000000000000000000000000000010000000000000001000000000000000000000000000000000000000000000000012000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000300000010000000000000000000000000000000000000000000000000000000000331000000000000000000000000000000000000000000000000001000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000100000000000000000000000000000000000000000000000000000000000010000110000000000000000000000000000000000000000000010000000000000011000000000000000000000000000000000000000000000000011'

We can decomposeN in power of $7$ like this : \(N = 7^0 \times 1 + 7^1 \times 1 + 7^{51} \times 1 + ... + 7^{1446}\)

Then, we replace $7$ by the indeterminate $x$ thanks to the following sage code :

sage: poly = sum(e * x^i for i,e in enumerate(N.digits(7)))
sage: poly
x^1446 + 3*x^1198 + x^1146 + 3*x^898 + x^835 + x^790 + x^774 + x^724 + 2*x^723 + 3*x^542 + x^535 + 3*x^476 + 3*x^475 + x^474 + x^423 + x^179 + x^118 + x^113 + x^112 + x^67 + x^52 + x^51 + x + 1

We got know a polynomial wich evaluated in $x = 7$ is equal to N, thanks to the number of 0s in the N representation, the associated polynomial is easy to factorize. Indeed :

sage: factor(poly)
(x^723 + 3*x^475 + x^112 + x^51 + 1)*(x^723 + x^423 + x^67 + x + 1)

We now just have to evaluate each of the factors in $x = 7$ in order to get p and q. Now that we have p and q … this is over!

Final script

sage: from Crypto.Util.number import long_to_bytes, bytes_to_long
sage: p = (x^723 + 3*x^475 + x^112 + x^51 + 1)
sage: q = (x^723 + x^423 + x^67 + x + 1)
sage: p = p(x=7)
sage: q = q(x=7)
sage: assert p * q == N
sage: phi = (p-1)*(q-1)
sage: e = 0x10001
sage: d = pow(e, -1, phi)
sage: C = 2565617200166195847141820928636232303959466722932792435323711473965652085371699818644409256990409854048944[...]31
sage: long_to_bytes(pow(C, d, N))[::-1]
b'DS Bandit pwned - Follow protocol EVE - Brute Ninja'

According to the flag format : HACKDAY{EVE}