Code Blue 2017 - Common Modulus 1 Writeup

I’m starting off this blog with a super easy writeup. The following problem was (at the time I solved it) the most solved problem in the CTF. In the coming days, I’ll hopefully update with more writeups. I’m currently working through RPISEC’s amazing MBE course and want to eventually post writeups of those labs.

---

Last week, I played for a couple hours in Code Blue CTF 2017 (it ran from Thursday to Friday – a less-than-ideal timing for people who work during the week). My friend 1ce0ear was already working through a pwnable when I hopped on so I chose to look at a crypto problem titled Common Modulus 1, since I have recently been working on improving my crypto skills through the Matasano/Cryptopals Crypto Challenges. The problem gave an archive with two files in it:

problem.py

from Crypto.Util.number import *
from Crypto.Random.random import randint

import gmpy
import key

FLAG = long(key.FLAG.encode("hex"), 16)

def get_random_prime(bits=1024):
  return int(gmpy.next_prime(randint(2**(bits-1), 2**bits)))

def gen_n(bits=1024):
  p = getStrongPrime(bits)
  q = getStrongPrime(bits)
  return p*q, p, q

def encrypt(pk, m):
  assert m < pk[0]
  return pow(m, pk[1], pk[0])

def decrypt(pk, sk, c):
  return pow(c, sk[0], pk[0])

def test(n, p, q):
  e = get_random_prime(20)
  pk, sk = (n, e), (long(gmpy.invert(e, (p-1)*(q-1))), )
  print "[+] RSA Self Test: %r" % (pk, )
  c = encrypt(pk, FLAG)
  print "[+] ciphertext = %d" % c
  m = decrypt(pk, sk, c)
  print "[+] Dec(Enc(m)) == m? : %s" % (m == FLAG)


if __name__ == "__main__":
  n, p, q = gen_n(2048)
  test(n, p, q)
  test(n, p, q)

transcript.txt

[+] RSA Self Test: (791311309087374588934274354916349141233150778762086315374343850126808782284294921228110916322178898551691669133101997907127587121520288166574468605214516304122927763843434653215681360872523253290766297044510870617745122997739814947286892376888776319552516141136363673315815999597035068706744362048480852074989063152333880754375196551355543036200494314973628012006925154168913855587162465714207917714655810265293814697401062934881400969828166519415465439814160673468968009887672546243771190906300544375962002574334018175007498231632240021805593635057187842353840461973449205839419195826992169177108307004404365745462706797969436718212150888171299620800051183755681631250040936288149592343890616920153400691102933966724025765766418338452595218861582008026186067946508221264938736562082192890727980844444978081110599714993030990031363457184296168457089953510500474033234298252385232725393194957086065274263743550741242453140557383981358497807318476777558208795816650619401057283873302725816795298930817307745973266335447938091252055872816232968635169429875153933553733116356920185396530990560434510949092154539711124052490142742567527833751624924993906099869301505096094512729115132147653907827742334805918235749308541981388529841813147L, 813647)
[+] ciphertext = 767202255403494641285723819543278226263601155898823605265497361830705668240032418501494959141449028517100422081272691883369257107388411439611318808983979122090486252578041006071999581282663085495058515958745546211668701835250122032715473014598395050184702983368667972803718169481809394565706175141425650370279775233813674442957760484285820381853600163980060348710028919659329781877491724136976028815641232407109144869660767954119268355348405951052583739555066569345526640029961785158127382321111833599691079949415049786723663210542733655554868327542833053024595895523192888118675763242352407948643537985861448788568550308481655116845634952516676905251579084404308314639717162526798451410767058423619677212069270398132021729448047980766312818656065369023093123058422620085273728481545680423266197847937925342263870309939913221308330842487685037638837340238355192125668409039255551545407800543798158964963358868702135730305156935767426581823180696819366253148799571923731323928995477390559418822575259531941023518182807739949726026157027426545624061195471888653152768495272113769751755053321333829345939391638863918920798107792346015224509118930143010726156407828938941341788657835191853473698010478888928860138978235297618195944868175
[+] Dec(Enc(m)) == m? : True
[+] RSA Self Test: (791311309087374588934274354916349141233150778762086315374343850126808782284294921228110916322178898551691669133101997907127587121520288166574468605214516304122927763843434653215681360872523253290766297044510870617745122997739814947286892376888776319552516141136363673315815999597035068706744362048480852074989063152333880754375196551355543036200494314973628012006925154168913855587162465714207917714655810265293814697401062934881400969828166519415465439814160673468968009887672546243771190906300544375962002574334018175007498231632240021805593635057187842353840461973449205839419195826992169177108307004404365745462706797969436718212150888171299620800051183755681631250040936288149592343890616920153400691102933966724025765766418338452595218861582008026186067946508221264938736562082192890727980844444978081110599714993030990031363457184296168457089953510500474033234298252385232725393194957086065274263743550741242453140557383981358497807318476777558208795816650619401057283873302725816795298930817307745973266335447938091252055872816232968635169429875153933553733116356920185396530990560434510949092154539711124052490142742567527833751624924993906099869301505096094512729115132147653907827742334805918235749308541981388529841813147L, 846359)
[+] ciphertext = 393205642868817442649216793359718556278406137459770244761832906195960432918468617731069456704644789806507809829093842629745066759599286729538728368882491382997337611417441529220397067642218119525968897551289230558627870154984979444195757677411673096443476021362319325097662392808170632471553717355895219405644518503783235536597143112954291157798713583737689125917709618182162360535659223966858707155741267214975141963463832314566520144602105237041672437684177707624423211972004800873375670613148140256099552724408192217550331987310558991433383571470532995856778764797540637679226825577553396934734325550293550389623919904744913990305949697308222046594160302362669510242921299755255790640101006152269619965560742243168099219363626217512940995615730916134775134764069912120583282148219405178065222313607957426887495658080497917440100549199528894874905968298614233827155712422019324710018755792249855902168601927285980197334672067920857960628679370550895555840658121626134216719240409691397735762685349162277111815727100169755960553688569326705249270662470879197234836585418835845237231721910938341557726245940031873345666571751867755961294973426045629909899256967038811807893676700888551318830676356324765330202998096318754445585853694
[+] Dec(Enc(m)) == m? : True

The problem’s title gives us a huge hint: there is something called RSA Common Modulus Attack. problem.py shows us some generic code for encryption using RSA. We see our good friends n, p, q, and e. Looking at transcript.txt, we can see that the flag is encrypted twice. Both times, the encryption uses different values for e but the same n (or modulus) for RSA. There are many answers written about this but I found the answer by mikeazo on this stackexchange post most helpful. Basically, we can find two numbers a and b such that a * e₁ + b * e₂ = 1. Then from there, we use this a and b to get back to our plaintext. We can use the gcdext() function in the python gmpy2 package to find this a and b:

import gmpy2
not_used, a, b = gmpy2.gcdext(e1, e2)

Since one of these will be negative, we can also use gmpy2‘s invert() function to produce the i necessary in our final calculation of the plaintext message.

i = int(gmpy2.invert(c2, n))

Finally, don’t forget that we want to use modular exponentiation so we don’t wait days for our python pow() function to compute exponents.

m = (pow(c1, int(a), n)*pow(i, -int(b), n))%n

The reason why we do casting of a and b to ints is due to the return type of gmpy2‘s functions that we use. Putting it all together (along with decoding the final ciphertext in hex format), we get the following script to solve for our original plaintext:

solve.py

import binascii
import gmpy2

n = 791311309087374588934274354916349141233150778762086315374343850126808782284294921228110916322178898551691669133101997907127587121520288166574468605214516304122927763843434653215681360872523253290766297044510870617745122997739814947286892376888776319552516141136363673315815999597035068706744362048480852074989063152333880754375196551355543036200494314973628012006925154168913855587162465714207917714655810265293814697401062934881400969828166519415465439814160673468968009887672546243771190906300544375962002574334018175007498231632240021805593635057187842353840461973449205839419195826992169177108307004404365745462706797969436718212150888171299620800051183755681631250040936288149592343890616920153400691102933966724025765766418338452595218861582008026186067946508221264938736562082192890727980844444978081110599714993030990031363457184296168457089953510500474033234298252385232725393194957086065274263743550741242453140557383981358497807318476777558208795816650619401057283873302725816795298930817307745973266335447938091252055872816232968635169429875153933553733116356920185396530990560434510949092154539711124052490142742567527833751624924993906099869301505096094512729115132147653907827742334805918235749308541981388529841813147L

e1 = 813647
e2 = 846359
c1 = 767202255403494641285723819543278226263601155898823605265497361830705668240032418501494959141449028517100422081272691883369257107388411439611318808983979122090486252578041006071999581282663085495058515958745546211668701835250122032715473014598395050184702983368667972803718169481809394565706175141425650370279775233813674442957760484285820381853600163980060348710028919659329781877491724136976028815641232407109144869660767954119268355348405951052583739555066569345526640029961785158127382321111833599691079949415049786723663210542733655554868327542833053024595895523192888118675763242352407948643537985861448788568550308481655116845634952516676905251579084404308314639717162526798451410767058423619677212069270398132021729448047980766312818656065369023093123058422620085273728481545680423266197847937925342263870309939913221308330842487685037638837340238355192125668409039255551545407800543798158964963358868702135730305156935767426581823180696819366253148799571923731323928995477390559418822575259531941023518182807739949726026157027426545624061195471888653152768495272113769751755053321333829345939391638863918920798107792346015224509118930143010726156407828938941341788657835191853473698010478888928860138978235297618195944868175
c2 = 393205642868817442649216793359718556278406137459770244761832906195960432918468617731069456704644789806507809829093842629745066759599286729538728368882491382997337611417441529220397067642218119525968897551289230558627870154984979444195757677411673096443476021362319325097662392808170632471553717355895219405644518503783235536597143112954291157798713583737689125917709618182162360535659223966858707155741267214975141963463832314566520144602105237041672437684177707624423211972004800873375670613148140256099552724408192217550331987310558991433383571470532995856778764797540637679226825577553396934734325550293550389623919904744913990305949697308222046594160302362669510242921299755255790640101006152269619965560742243168099219363626217512940995615730916134775134764069912120583282148219405178065222313607957426887495658080497917440100549199528894874905968298614233827155712422019324710018755792249855902168601927285980197334672067920857960628679370550895555840658121626134216719240409691397735762685349162277111815727100169755960553688569326705249270662470879197234836585418835845237231721910938341557726245940031873345666571751867755961294973426045629909899256967038811807893676700888551318830676356324765330202998096318754445585853694

not_used, a, b = gmpy2.gcdext(e1, e2)
assert a*e1 + b*e2 == 1

# We need this step since b comes out to be negative
i = int(gmpy2.invert(c2, n))

# Use modular exponentiation for faster computation
m = (pow(c1, int(a), n)*pow(i, -int(b), n))%n

# Print the flag from hex format
print binascii.unhexlify(hex(m)[2:-1])

And we get our flag:

$ python solve.py
CBCTF{6ac2afd2fc108894db8ab21d1e30d3f3}