Google CTF 2021 Beginners Quest

Written on September 19, 2021

#7 - Buenos Aires Conference

For this challenge we are given a file. Running the file command we can see the file is a Zip archive. The archive contains chall.py and __pycache__.

Inspecting the chall.py script we can see that some string “flag” has been converted into bytes and then passed through a pow() function as a form of encryption. In comments at the end of the script are two long numbers, presumably c and n, generated from the original flag.

from Crypto.Util.number import *

flag = b"REDACTED"

p = getPrime(1024)
q = getPrime(1024)
n = p*q

m = bytes_to_long(flag)

c = pow(m,3,n)

print(c)
print("\n")
print(n)
#15478048932253023588842854432571029804744949209594765981036255304813254166907810390192307350179797882093083784426352342087386691689161026226569013804504365566204100805862352164561719654280948792015789195399733700259059935680481573899984998394415788262265875692091207614378805150701529546742392550951341185298005693491963903543935069284550225309898331197615201102487312122192298599020216776805409980803971858120342903012970709061841713605643921523217733499022158425449427449899738610289476607420350484142468536513735888550288469210058284022654492024363192602734200593501660208945967931790414578623472262181672206606709
#21034814455172467787319632067588541051616978031477984909593707891829600195022041640200088624987623056713604514239406145871910044808006741636513624835862657042742260288941962019533183418661144639940608960169440421588092324928046033370735375447302576018460809597788053566456538713152022888984084306297869362373871810139948930387868426850576062496427583397660227337178607544043400076287217521751017970956067448273578322298078706011759257235310210160153287198740097954054080553667336498134630979908988858940173520975701311654172499116958019179004876438417238730801165613806576140914402525031242813240005791376093215124477

We dont know the original prime numbers used to encrypt the message as the getPrime(1024) function generates a random prime number. However, we do know their product (n) and their remainder from the pow() function (c).

c = pow(m,3,n) is essentially the same as c = m^3 % n

The modulo function (%) gives the remainder of a division so in this case “c” is the remainder. We can use this knowledge to make brute forcing the flag much much faster.

Brute forcing

“m” is a long int created from the bytes that make up the flag. As the flag is turned into an int, it must be a whole number. With this in mind we can write a reverse function to the pow() function which goes a little like this: m^3 = k * n + c where k is a constant coefficient of n.

As we know, the cube root of m^3 should be a whole number so all we need to do to brute force the flag is itterate through different values of k until we get m to be a whole number. We can use the gmpy2 library to find the cube root of long ints and it will also conviniently return a bool depending on whether it is an int or not. Writing the script to bruteforce the flag in python looks like this:

from Crypto.Util.number import *
import gmpy2

c = 15478048932253023588842854432571029804744949209594765981036255304813254166907810390192307350179797882093083784426352342087386691689161026226569013804504365566204100805862352164561719654280948792015789195399733700259059935680481573899984998394415788262265875692091207614378805150701529546742392550951341185298005693491963903543935069284550225309898331197615201102487312122192298599020216776805409980803971858120342903012970709061841713605643921523217733499022158425449427449899738610289476607420350484142468536513735888550288469210058284022654492024363192602734200593501660208945967931790414578623472262181672206606709
n = 21034814455172467787319632067588541051616978031477984909593707891829600195022041640200088624987623056713604514239406145871910044808006741636513624835862657042742260288941962019533183418661144639940608960169440421588092324928046033370735375447302576018460809597788053566456538713152022888984084306297869362373871810139948930387868426850576062496427583397660227337178607544043400076287217521751017970956067448273578322298078706011759257235310210160153287198740097954054080553667336498134630979908988858940173520975701311654172499116958019179004876438417238730801165613806576140914402525031242813240005791376093215124477
k = 0

while not gmpy2.iroot(k*n +c, 3)[1]:
    k+=1;

print(long_to_bytes(gmpy2.iroot(k*n +c, 3)[0]))

Running the script we get the flag to be: CTF{34sy_RS4_1s_e4sy_us3}

Next quest: Google2021Beginners-08