Skip to content

PatriotCTF : CoruptAAAAd

Jump to bottom
Firas Chaib edited this page May 18, 2022 · 1 revision

Description

We recovered a private PEM key that a spy used to encrypt a secret message, but it appears as though one of the RSA key components got corrupted. Can you find a way to retrieve the message?

Screenshot from 2022-05-17 10-34-45

Files

  • corrupted-privkey.pem
  • encryptedmessage.enc

Solution

Recon

  • the key seems to be missing an integer or some kind of integer overriding

Execution

So the first thing that I did was running the asn1parse command to see the different components of the corrupted key :

┌─[not1cyyy@0x45] - [~/Desktop/PatriotCTF/coruptAAAAd_FINISHED] - [mer. mai 18, 13:26]
└─[$] <> openssl asn1parse -in corrupted-privkey.pem 
    0:d=0  hl=4 l=1187 cons: SEQUENCE          
    4:d=1  hl=2 l=   1 prim: INTEGER           :00
    7:d=1  hl=4 l= 257 prim: INTEGER           :C91C0D55929BB90511C071DE32A9ACAAC27FE205A0604DB9F5FA6B9FF99226F7487A9D7E1414BA7B46D948DEE09B90BF10DB430B12F453298D70E786C5342916BC4DDB05D4117720E4334C5DC17B155E8F7CFFA17F47248CD900FCCE7FEAB9549400F2484C3CD2EFF0300374FC412B5E428A904361FC2C33200F0CA4E99A79CE481E0F0EBE16CB42517C4CB6851FE1FA05B11678EA232F71ECC3ED5E8BEF6E3DC642C4F7488F0C5296284C4FFD1AFD1BCAC024192870AE6C5647DAB7BF71C350483180B08161A48E716788CC3CECEF26F25355C8028E7D24557CFC0F7F11633D0E4B2B2EA8DB2CCBEFBE5F424938554F24B618421A834798F2CB9DCDAA3E37B1
  268:d=1  hl=2 l=   3 prim: INTEGER           :01AAAA
  273:d=1  hl=4 l= 256 prim: INTEGER           :6D03966D15A6245F35A720E3C8FD3C87552465C28C2E609924A08D6AC39BFE67F07736CB69D76EAFF93D465E85CCF67089FF4B531D1B602736555277077C137EBF0BD6AADC627429D8E177A83602B07172D644354E90FDA1536A0F0F5F3A5DF77CB45670BEC6C8EAA3D3B9768DDCBC15C26DC417375EF0706AD98A1BE4AD0F4036B44CD7CEE21C57FF6CC8ABC343AB2AC9531754E2E6BC4E5E2481DEA6345EEDCFAD068DDE83420C49CB30267924062DAD26250473ED2606144F6FA437483636098BD14EFB4EC9E27E7A58224AE58475C365114D9A8F90CAD18C44C75DCC92FF64858AAA9EC037FA298EEA93A8775470E3330EC3E29F74B1879E836D5518090B
  533:d=1  hl=3 l= 129 prim: INTEGER           :F338F9C19E2D2F1715232E3121FD0A3615B9C6F87757A59BB8C507185BA7CDDE90F4DB7B49D4B0A8AD6E492C49E5D3D75FD61ED27C6D714D68D4330596CC08222CC8B641DF4ACF02D9A9D2A1115CDACC1FC2DFFC56308BCCCC4FCBC64CCE95F991C65DE43F56B67F74F7D2877AF7191B97783226B4F2C5E2AB8B67CBE0162BEB
  665:d=1  hl=3 l= 129 prim: INTEGER           :D3ACB64C7F034F4DA31EFC3A1FE6C86AA6536246897D081B4446BEB2A66970EF66962757ED3016E463CCD7077F35347A2AEE37E5B8C2290AA97CC7E1BC84BCECBEF25FFF7C5AF30870E6850100B032BBA6E51C1BFF4CAEB5FDEE46D9DADF1A558E8DAAABAD5191A4EC7929DA109139B7437C36A5B6E911D4EA60E236EB1FCFD3
  797:d=1  hl=3 l= 128 prim: INTEGER           :5B98F6777A0D7792CEEF8B3E8971303E09F826115AE81C9BEDBD2DCBB57BB948F21FD50F4C47205BF7FA30566B19E1F86F6E73B42A956869E31A3295C8CED6E9F0EF9BCB94B26AFBD8996BAF1F3DD506F0DD0CD3819EE89F0303256FDB217BD5979B72CEBE00896413C4BDBE561FD22B909892CFB6047ADE3F7F697688970FFD
  928:d=1  hl=3 l= 128 prim: INTEGER           :23DDF496B79B578A0D1E56BAE6FF17D10DF1C62C9D5FCD5283235CC12DED626EE2DD367CB1D53C3803ADA5B9E7823536FC9AB40993A9E97E5B0257D1ED8EAD92ED88155046205711A6FD6B228AF7E103F3EFBD09742544C02D448E46CC6BE7EFDF65A3B43A7718EC41AF4BA500B886A8DCEC3EA03572DB8485AA07CF22F1B8D5
 1059:d=1  hl=3 l= 129 prim: INTEGER           :B5FE419C7585A617DC2FCED225EAABA4345C3E69CE33823694B1A2FF498A13DA3BD5A3061DD665912149D10E2F08F2199BC1F8B4D62716C6C38BFD16907E6D9F5870A7F19BC3922157C3F60ABCF16AA83248A087A33664E7C91E1398C6EDC85587573C599788E30606F8A5C9706119C3CCEC8EC732A67683F856A414DCAC1C43

So we notice that the third integer is corrupted : 01AAAA and from the challenge name we can guess we're on the right track !

So here's the thing : the minimum value that this exponent can take is 65536 (0x010000) and the maximum value is 131071 (0x01FFFF)

The idea here is simple then : we have everything including p and q so we need to brute force the public exponent knowing that we have to generate a private exponent that matches the one we have

here's a simple python script that does the job for us :

from Crypto.Util.number import *

p = 170796690670149105967813113382240505264948946083779586225654103308455488484955325942435054455489163709901661752475987135208117710882465445438716967370656724411467295069033290926317928181839183115857695607269318815355418951302758625104112455758674321597170318312608293648437083737653529431390940141417376656363
q = 148642998867368974873367801833129614874516289477879330501274056446035580016863921172640657206956948700028292330318518525531134043765361989080527137024999373411614110609856551202314420763429763536035853618803223901065359478539557924348825167340722079773893879969151857740258435351842073683199730747819312533459 
n = p*q
phi = (p-1)*(q-1)
priv = 13761744353781520241535090155051521309604275579476680716784306044762933961357488224827562217535999947493507674766115812321129673788361142574817557971070748449686502671562600150406609274926237701752769893224204627008072460501416639851704326685417649585674585895088216243892373351458092620189812954760710952411647514051134306291425495198399934563635483021996439038914522228072525917162300334529714139657210200573187092007200148137878796564219640817582728732477620825903532578099970067908169454303632714801798650213786717234256711336277305677096018021695116440207686688923013835576173959490279696050775677855331079686411


for e in range(65536, 131071):
	if GCD(e, phi) == 1:
		d = pow(e, -1, phi)
		if (d == priv):
			print(e)

the script gives the following output :

┌─[not1cyyy@0x45] - [~/Desktop/PatriotCTF/coruptAAAAd_FINISHED] - [mer. mai 18, 13:35]
└─[$] <> python3 dc.py 
79631

perfect ! we can now generate a new private key using the tool rsatool.py

and now for the final part : writing the decryption script :

import base64
from Crypto.Util.number import *
from Crypto.PublicKey import RSA
from Crypto.Cipher import PKCS1_v1_5

ct = open('encryptedmessage.enc', 'r')
m = ct.read()
message_bytes = base64.b64decode(m)

p = 0xF338F9C19E2D2F1715232E3121FD0A3615B9C6F87757A59BB8C507185BA7CDDE90F4DB7B49D4B0A8AD6E492C49E5D3D75FD61ED27C6D714D68D4330596CC08222CC8B641DF4ACF02D9A9D2A1115CDACC1FC2DFFC56308BCCCC4FCBC64CCE95F991C65DE43F56B67F74F7D2877AF7191B97783226B4F2C5E2AB8B67CBE0162BEB
q = 0xD3ACB64C7F034F4DA31EFC3A1FE6C86AA6536246897D081B4446BEB2A66970EF66962757ED3016E463CCD7077F35347A2AEE37E5B8C2290AA97CC7E1BC84BCECBEF25FFF7C5AF30870E6850100B032BBA6E51C1BFF4CAEB5FDEE46D9DADF1A558E8DAAABAD5191A4EC7929DA109139B7437C36A5B6E911D4EA60E236EB1FCFD3 
n = p*q
phi = (p-1)*(q-1)
e = 79631

if GCD(e, phi) == 1:
    # get decryption key
	d = inverse(e, phi)
    # create private key
	privkey = RSA.construct((n, e, d, p, q))
	key = PKCS1_v1_5.new(privkey)
try:
    # attempt to decrypt message with current privkey
    pt = key.decrypt(message_bytes, "").decode()
    print(f"e: {e}")
    print(f"Plaintext: {pt}")
except:
    pass

and voilà ! we get the flag !

Flag

PCTF{g1mm3_th3_e}

Clone this wiki locally