STANDCON CTF 2021
Space Papaya
Description
I’ve been promised some space payayas but Thanos has encrypted it Could you help me get to my delicious goodness??
Solution
Here’s the source code provided for this challenge:
#!/usr/bin/env python3
from gmpy2 import *
p = next_prime(mpz_random(random_state(), 2**4096))
q = next_prime(p)
e = 65537
n = p * q
m = int(MESSAGE.encode().hex(), 16)
c = powmod(m, e, n)
print('n: {}'.format(n))
print('e: {}'.format(e))
print('c: {}'.format(c))
# n: 194362842708866084215953237234010601714782092068657017473036251138431676671868175490629669131293355984477767779272247912898398003959598463151066327473719826508089049945621257750848449074932994104814837269421034757100838633416457369464538335095187107124930210006276919089438600966775135156325573710403062047464883549122709123350776456864832248893144446427550937016055121611927144077249211333929866196092711899598411273258926755835322801924551532228696950330545602277465654578138211698686416187777914526845287508335161840449532353167124783735356724420020001236913091469220071460852670489823002071147052631961616736127542307774553784213551564976856862680192529610361702034557744944910925361832621941572380183550749898722374949514136460106207058164376880193895095890731337592265596372136311383975505976373658539080754488958878095929819739059683095890843634555379298978595862942651406158169690562827703147073676346785373790083861582561563008369782363501250191378992269292876039816066218709174263118734404595822048356915079954616024173040278438553459313402270428924062608121168067858306151528190868319071885225544108264749925782330560592480215417954913785029628131817946912132072071073028544681943321456215850218595253490676706062275706321000094834565990465219492368108372464243357854880130522009562946069931768188707691738519573044108555326442766896720655950851164470011771898369770346952788889888492093755625144273054698093660448370077627755233718711030066641378367031583966313900302554231887044203179482191397744246669757016815802390996997529280308699365864745829622981997926231390088157384772877949116604666434897004907955030386342793095734076042434116395844774091900169206181916763238708781774871037938343903139193853528470631949004956352291136030226647324347066772397900205516364442447205487793826622232753382956298250824843380629813818205906683470702831540412778050975345092843721732642350276838457054614948850604421694716563394223556916722778907958340426218859169271015308289476166790080639494788055226687567028709925056618087462428702997126125118029596845966551281440608686343474201915276278183257597304657555212877310709706767336727956810525772106318192285540421821451870148936086342692819049576874727321875121881832817291330007033448759929549864436079804109819708577707453355419019938895736691749711920076052148328406790627343167155687496921184728015803775794667189219633138620080230753579310617631968722793155536612115409526848248365291605624225739530401807631
# e: 65537
# c: 48231407940727026948672141996334529816590411386860292966914913052426047651987115807777841403140631401701249166736959609586369772130907665951564333728016264781106888841594995016670252351243877043043931895035854072541505075903498699581537787497372368026387461275304338678342882903111473016523122047215378268701734813840019057484437006734608455311609606589978328615886021809161996407351531878330820646743145761284259656979198538333302516658013752884296025359474328771699801774792040803990528899610805832697102960908000990289217674047087227612100839918274810879461691566218620108094572187135662070276143399213929056836949141685032577775184655073850890039819023606342148129988769179828433133474387630746462392553047809255640475195268000075192882984582676932698012626821016591108454125334943555006192200330741124548142161400440375747011531508789850387965540536344945763731373457679082441847778497960038863971948480784876442032472906163053089647045655001542030261262366802020060960874257117691078438824193893194414541917317612137645261904776291223687776582045621554101330940016490033717225542054294550509723890916037908439996672821935786685430873048747351042450242135132402651504861858744900133079753832853206911330310597784333649988497694115288456557414447667162368132351388665881330668539885411369791455480519780053033578607022175215519541686716889470249651075696960031469802931249420275612918537198815728307645858921412505760969514941201413816870042202876699227452040578555623960644754047671586444437939411346055325470287778116774616418405759426544629377975037932066699294880194784853999718178319023949211409048595187949438738050805752373774067262605283342238201172745181281789835988232279319864794958750383869310348406998847103542030538181779060240394157480926897363819838099821784624349518599583933815726206097153419947746982886708613483961746873726951138409665385485483718572380938222490388874840647413038783667362727632810016605914301245603947756748870162828963959855754534784070704364459621393050570977513255324417271658411232766634623398123418984633536742998705987579502631970588156672642641810685697296750600811292822227321148497030230391951474359873858004455962186711399896745959043999926635601785091266948248579919445401875107488515808513058701412149085423586181153312241453589223174436758137842395277731895460702559785230565410482969668156381371880091047940473364486255074425419927756644949215073309100344302265133911935519226690015718699828070058406043592623
As we can see from the source code, \(p\) and \(q\) are consecutive primes, as the function next_prime was used on \(p\) to find \(q\). Since the values of \(p\) and \(q\) are pretty close together, we can thus use the Fermat’s Theorem to factorise out \(p\) and \(q\).
The Math
The fermat algorithm uses the fact that:
\[\begin{equation} n = pq =(\frac{q-p}{2})^2 - (\frac{p+q}{2})^2 = x^2 - y^2\end{equation}\]where:
\[\begin{equation} x = \frac{q-p}{2}, y = \frac{p+q}{2}\end{equation}\]The algorithm works like this:
- \(a = \sqrt{n}\)
- \(b = a^2 - n\)
- While b is not a perfect square: increment a
- Return \(p = a - \sqrt{b}\)
Here’s my code:
n = 194362842708866084215953237234010601714782092068657017473036251138431676671868175490629669131293355984477767779272247912898398003959598463151066327473719826508089049945621257750848449074932994104814837269421034757100838633416457369464538335095187107124930210006276919089438600966775135156325573710403062047464883549122709123350776456864832248893144446427550937016055121611927144077249211333929866196092711899598411273258926755835322801924551532228696950330545602277465654578138211698686416187777914526845287508335161840449532353167124783735356724420020001236913091469220071460852670489823002071147052631961616736127542307774553784213551564976856862680192529610361702034557744944910925361832621941572380183550749898722374949514136460106207058164376880193895095890731337592265596372136311383975505976373658539080754488958878095929819739059683095890843634555379298978595862942651406158169690562827703147073676346785373790083861582561563008369782363501250191378992269292876039816066218709174263118734404595822048356915079954616024173040278438553459313402270428924062608121168067858306151528190868319071885225544108264749925782330560592480215417954913785029628131817946912132072071073028544681943321456215850218595253490676706062275706321000094834565990465219492368108372464243357854880130522009562946069931768188707691738519573044108555326442766896720655950851164470011771898369770346952788889888492093755625144273054698093660448370077627755233718711030066641378367031583966313900302554231887044203179482191397744246669757016815802390996997529280308699365864745829622981997926231390088157384772877949116604666434897004907955030386342793095734076042434116395844774091900169206181916763238708781774871037938343903139193853528470631949004956352291136030226647324347066772397900205516364442447205487793826622232753382956298250824843380629813818205906683470702831540412778050975345092843721732642350276838457054614948850604421694716563394223556916722778907958340426218859169271015308289476166790080639494788055226687567028709925056618087462428702997126125118029596845966551281440608686343474201915276278183257597304657555212877310709706767336727956810525772106318192285540421821451870148936086342692819049576874727321875121881832817291330007033448759929549864436079804109819708577707453355419019938895736691749711920076052148328406790627343167155687496921184728015803775794667189219633138620080230753579310617631968722793155536612115409526848248365291605624225739530401807631
e = 65537
c = 48231407940727026948672141996334529816590411386860292966914913052426047651987115807777841403140631401701249166736959609586369772130907665951564333728016264781106888841594995016670252351243877043043931895035854072541505075903498699581537787497372368026387461275304338678342882903111473016523122047215378268701734813840019057484437006734608455311609606589978328615886021809161996407351531878330820646743145761284259656979198538333302516658013752884296025359474328771699801774792040803990528899610805832697102960908000990289217674047087227612100839918274810879461691566218620108094572187135662070276143399213929056836949141685032577775184655073850890039819023606342148129988769179828433133474387630746462392553047809255640475195268000075192882984582676932698012626821016591108454125334943555006192200330741124548142161400440375747011531508789850387965540536344945763731373457679082441847778497960038863971948480784876442032472906163053089647045655001542030261262366802020060960874257117691078438824193893194414541917317612137645261904776291223687776582045621554101330940016490033717225542054294550509723890916037908439996672821935786685430873048747351042450242135132402651504861858744900133079753832853206911330310597784333649988497694115288456557414447667162368132351388665881330668539885411369791455480519780053033578607022175215519541686716889470249651075696960031469802931249420275612918537198815728307645858921412505760969514941201413816870042202876699227452040578555623960644754047671586444437939411346055325470287778116774616418405759426544629377975037932066699294880194784853999718178319023949211409048595187949438738050805752373774067262605283342238201172745181281789835988232279319864794958750383869310348406998847103542030538181779060240394157480926897363819838099821784624349518599583933815726206097153419947746982886708613483961746873726951138409665385485483718572380938222490388874840647413038783667362727632810016605914301245603947756748870162828963959855754534784070704364459621393050570977513255324417271658411232766634623398123418984633536742998705987579502631970588156672642641810685697296750600811292822227321148497030230391951474359873858004455962186711399896745959043999926635601785091266948248579919445401875107488515808513058701412149085423586181153312241453589223174436758137842395277731895460702559785230565410482969668156381371880091047940473364486255074425419927756644949215073309100344302265133911935519226690015718699828070058406043592623
from Crypto.Util.number import long_to_bytes
import gmpy2
import math
## Fermat Implemenation
a = gmpy2.isqrt(n)
b2 = a*a - n
b = gmpy2.isqrt(n)
count = 0
while b*b != b2:
a += 1
b2 = a*a - n
b = gmpy2.isqrt(b2) # int(b2**0.5)
count += 1
p=a+b
q=a-b
assert n == p * q
totient = (p-1)*(q-1)
d = gmpy2.invert (e, totient) # d = e^(-1) mod totient
m = gmpy2.powmod (c, d, n)
print (long_to_bytes(m))
And here’s the flag: STC{where_did_my_space_papayas_go}.
Rocket Ship Academy
Description
Oracle: a person or thing regarded as an infallible authority on something.
Do we have one of those here?
Solution
This is a chosen ciphertext attack against RSA. Hence, we can send a certain ciphertext to decipher the message.
I sent this:
\[\begin{equation} c' = c * 2^e\end{equation}\]as a ciphertext to get the flag.
How the Math Works
Basically if you send \(c’\) as a ciphertext, this is what happens.
\[\begin{aligned}(c * 2^e)^d \mod n &= c^d *2^{ed} \mod n \\ &=(c^d \mod n)(2^{ed} \mod n) \mod n \\ &= m *(2^{1+kϕ(n)}) \mod n \\ &= m* 2* (2^{1+kϕ(n)}) \mod n \\ &= 2m * 1 \mod n \end{aligned}\]The Script
from pwn import *
from Crypto.Util.number import long_to_bytes
p = remote('20.198.209.142', 55002)
n = int(p.recvline().strip().lstrip(b"n = "))
e = int(p.recvline().strip().lstrip(b"e = "))
c = int(p.recvline().strip().lstrip(b"c = "))
ct = c * pow(2, e, n) % n
p.recvuntil(b"Enter ciphertext:")
p.sendline(str(ct))
decrypt = int(p.recvline().strip().decode().lstrip("Decrypted: "))
log.info(f"flag is {long_to_bytes(decrypt//2).decode().strip()}")
And the flag is, STC{ch0s3n_c1ph3rt3xt_d7b593cd54baba9e2ffa49215d33e4c657cf230a}.
Mind Reader
Description
So you think you are the best mind reader in the entire galaxy? We shall see about that…
#!/usr/bin/env python
import random
from string import ascii_lowercase
life = 3
def printFlag():
print("[REDACTED]")
exit(0)
def banner():
print(" ╔══════════════════════════════════════════════════════╗")
print(" ║ ║")
print(" ║ ███╗ ███╗██╗███╗ ██╗██████╗ ║")
print(" ║ ████╗ ████║██║████╗ ██║██╔══██╗ ║")
print(" ║ ██╔████╔██║██║██╔██╗ ██║██║ ██║ ║")
print(" ║ ██║╚██╔╝██║██║██║╚██╗██║██║ ██║ ║")
print(" ║ ██║ ╚═╝ ██║██║██║ ╚████║██████╔╝ ║")
print(" ║ ╚═╝ ╚═╝╚═╝╚═╝ ╚═══╝╚═════╝ ║")
print(" ║ ║")
print(" ║ ██████╗ ███████╗ █████╗ ██████╗ ███████╗██████╗ ║")
print(" ║ ██╔══██╗██╔════╝██╔══██╗██╔══██╗██╔════╝██╔══██╗ ║")
print(" ║ ██████╔╝█████╗ ███████║██║ ██║█████╗ ██████╔╝ ║")
print(" ║ ██╔══██╗██╔══╝ ██╔══██║██║ ██║██╔══╝ ██╔══██╗ ║")
print(" ║ ██║ ██║███████╗██║ ██║██████╔╝███████╗██║ ██║ ║")
print(" ║ ╚═╝ ╚═╝╚══════╝╚═╝ ╚═╝╚═════╝ ╚══════╝╚═╝ ╚═╝ ║")
print(" ║ ║")
print(" ╚══════════════════════════════════════════════════════╝")
def printMenu():
print("=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=")
print("1. Play game")
print("2. View Top players")
print("3. Exit")
print("Please select your option")
choice=input("> ")
print("=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=")
return choice
def readFile():
firstName = open('./first-names.txt', 'r')
lastName = open('./last-names.txt', 'r')
game = open('./game.txt', 'r')
fnArr = firstName.read().splitlines()
lnArr = lastName.read().splitlines()
gameArr = game.read().splitlines()
return fnArr, lnArr, gameArr
def gen(initSeed, fnArr, lnArr, gameArr):
genNameArr = []
genHighscoreArr = []
toPredictArr = []
seed = []
r = random.Random()
r.seed(initSeed)
for count in range(730):
x = r.getrandbits(32)
seed.append(x)
if (count < 350):
fnIndex = x & 0xFFFF
lnIndex = x >> 16
Name = " ".join([fnArr[fnIndex], lnArr[lnIndex]])
genNameArr.append(Name)
if (count >= 350 and count < 700):
genHighscoreArr.append(x)
elif(count >= 700):
toPredictArr.append(gameArr[x & 0xFFFF])
return genNameArr, genHighscoreArr, toPredictArr
def hangman(tried_letters):
print ("LIFE: {0}".format(life))
if len(tried_letters) >= 1:
print("Used letters: {}".format(", ".join(letters for letters in tried_letters)))
def print_error(why):
print(why)
def gameLogic(letters, random_word):
global life
tried_letters = []
while True:
try:
hangman(tried_letters)
for letter in letters:
print(letter, end=' ')
letter_input = str(input("\nLetter: ")).lower()
if letter_input == random_word:
print('\nThe word is {0}. You win!'.format(random_word))
return
if len(letter_input) > 1 or letter_input not in ascii_lowercase:
print_error("Invalid Input\nOnly single letters")
continue
if letter_input in tried_letters:
print_error("You already tried this letter!")
continue
else:
tried_letters.append(letter_input)
if letter_input in random_word:
letter_index = [index for index, value in enumerate(random_word) if value == letter_input]
if len(letter_index) > 1:
for i in letter_index:
letters[i] = letter_input
elif letter_input in letters:
print_error("You already tried this letter!")
continue
else:
letters[letter_index[0]] = letter_input
else:
life -= 1
if ''.join(letters) == random_word:
hangman(tried_letters)
for letter in letters:
print(letter, end=' ')
print('\nThe word is {0}. You win!'.format(random_word))
return
elif life == 0:
hangman(tried_letters)
print('\nThe word is {0}'.format(random_word))
print("The Hangman was hanged. You loose!")
exit(0)
except IndexError:
print_error("Invalid Input\nOnly single Letters")
continue
def playGame(toPredictArr):
print("So you think you are a mind reader huh!?")
print("Try to guess what i am thinking 30 times in a row and win the grand prize")
print("I am even going to give u 3 chances, not like that would help >:)")
for idx, words in enumerate(toPredictArr):
letters = []
for _ in range(len(words)):
letters.append("_")
print("=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-")
print("Round " + str(idx+1))
print("=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-")
gameLogic(letters,words)
if idx == 29:
printFlag()
def viewTopPlayers(nameArr, highscoreArr):
print("Now showing the top 350 players!!!")
print("══════════════════════════════════")
print('{0:25} {1}'.format("Name", "ID"))
print("=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-")
for x in range (len(nameArr)):
print('{0:25} {1}'.format(nameArr[x], highscoreArr[x]))
def main():
initSeed = random.getrandbits(32)
fnArr, lnArr, gameArr = readFile()
nameArr, highscoreArr, toPredictArr = gen(initSeed, fnArr, lnArr, gameArr)
banner()
while True:
choice = printMenu()
if(choice == '1'):
playGame(toPredictArr)
elif(choice == '2'):
viewTopPlayers(nameArr, highscoreArr)
elif(choice == '3'):
exit()
if __name__ == "__main__":
main()
Solution
(I didn’t do this challenge, my teammate did.)
Basically, we are making use of the library randcrack, to exploit the weaknesses of the Python random module.
from pwn import *
from warnings import filterwarnings as fw
from randcrack import RandCrack
fw('ignore', category=BytesWarning)
def answer():
xx = rc.predict_randrange(0, 4294967295)
FnIndex = xx & 0xFFFF
LnIndex = xx >> 16
Name = " ".join([firstName[FnIndex], lastName[LnIndex]])
Game = game[xx & 0xFFFF]
return Game
rc = RandCrack()
p = remote('20.198.209.142', 55003)
# p = process('python3 ./mind.py', shell=True)
p.sendline('2')
p.recvuntil('=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-\n')
FnArray = []
LnArray = []
HsArray = []
firstName = open('./first-names.txt', 'r').read().splitlines()
lastName = open('./last-names.txt', 'r').read().splitlines()
game = open('./game.txt', 'r').read().splitlines()
x = []
for i in range(350):
leaderboard = p.recvline().strip().decode().split(' ')
FnArray.append(leaderboard[0])
LnArray.append(leaderboard[1])
HsArray.append(leaderboard[-1])
for i in range(350):
fn = firstName.index(FnArray[i])
ln = lastName.index(LnArray[i]) << 16
x.append(ln | fn)
for i in range(350):
x.append(HsArray[i])
# print(x)
for i in range(700 - 624, 700):
rc.submit(int(x[i]))
p.sendline('1')
for i in range(30):
Game = answer()
for x in list(set(Game)):
p.sendline(x)
p.interactive()
Here’s the flag: STC{w0w_wHa7_An_UneXPec7eD_7Wi57}.
