To obtain the second key, you must face a challenge set forth by the creator. The challenge involves a game called PSA, which uses the PKCS#7 padding scheme and generates varying versions of a secret passphrase. Can you uncover the correct passphrase and get the key?
Understanding the challenge
The server side code of this challenge is provided in the form of the following Python script:
from Crypto.Util.number import bytes_to_long, getPrime, GCD
from Crypto.Util.Padding import pad
from secret import FLAG
WELCOME = '''Welcome to my custom PSA cryptosystem!
In this cryptosystem, the message is PKCS#7 padded and then encrypted with RSA.
They say padding makes encryption more secure, right? ;)'''
MENU = '''
[1] Encrypt the flag
[2] Exit
'''
class PSA:
def __init__(self):
self.bit_size = 512
self.e = 11
def gen_modulus(self):
while True:
p = getPrime(self.bit_size // 2)
q = getPrime(self.bit_size // 2)
if GCD(self.e, (p - 1) * (q - 1)) == 1:
break
return p * q
def encrypt(self, msg):
m = bytes_to_long(pad(msg, 16))
n = self.gen_modulus()
c = pow(m, self.e, n)
return c, n
def main():
psa = PSA()
print(WELCOME)
while True:
print(MENU)
opt = input('> ')
if opt == '1':
enc, modulus = psa.encrypt(FLAG)
print(f"\n{hex(enc)}\n{hex(modulus)}")
elif opt == '2':
print('Bye.')
exit(1)
else:
print('\nInvalid option!')
if __name__ == '__main__':
main()
Reading between the lines, we have a PKCS#7 padded flag which is the encrypted with RSA.
Vulnerability identification
The vulnerability here lies in the improper usage of padding. Practical RSA implementations typically embed some form of structured, randomised padding of the message m before encrypting it. The padding ensures that m does not fall into the range of insecure plaintexts, and that a given message, once padded, will encrypt to one of a large number of different possible ciphertexts.
If the same clear-text message is sent to e or more recipients in an encrypted way, and the receivers share the same exponent e, but different p, q, and therefore n, then it is easy to decrypt the original clear-text message via the Chinese Remainder Theorem. In our case, the padded message can basically be considered as the same message, since the padding is the same all the time, even though p and q change.
Exploitation
To decrypt the message using the logic above, all we need is to obtain e - 11, encrypted encrypted messages, and their corresponding n, then we can use the following solver script, based on CRT:
from Crypto.Util.number import bytes_to_long, long_to_bytes
from Crypto import Random
import Crypto
import sys
import libnum
# Moduli
mod = [
0xb475652ecf7e0b4eb5e1688c6c8a15201b654d2b5a0ae23fa6644dba584e61f8d08a47d59ae27dba26c4c3dbf1bef83e7d560abf5bfda7bbf723d77a9930d499,
0x5062de1f2662cc5106d64a9b3b28df5e5994c058d116cc05b368ce692bd27c731496da55e9a1101ebc102b4365ec4362c4eae02049bb946b71711309e9d79223,
0xd328abfa6be5978d9ced86bbfe6692b35780e888143534c9d76e1b6766fb7df0d1a5148590a393fe16823ba42b8bd227418cd97ba16f18ef0a195df991399d7f,
0xbcfc2a5125b0f9999ca41816dfc1df3ccc7d4bcfe264a50597fb3ff716d33e722d02316095d5fbbbf07f99bc1c3ae940855b9f721f0390b719d7e7cb7ed4d525,
0xd1e55437aa250ee08b0d0f00b5a7fd6eb3a7854663ae6efb26f98f302d632e08d5cdd1f718fc556b733ad62f43f33b6adccd4df35cf4b138983fc56ecfe94013,
0xd165da5d7ae80f3496961d7e0724ded2e799c02e5178c1d49f77a59bbede310def16fb57fb33a93b25a33476692fb5ebfbe13d0f55e405f85ac92df0a0bf9b2d,
0x9a4da1290dcf01b48da301cc1c383b885abc4fadc5958614f06018ef1eacf580c23dd7145145116ef79c74c8bb13ad398b7f148ebabbb22198f187a437da8473,
0x8c6bd27bbf435e8705555b00beae3f5af0e104eea6d63829b9e6457f76aa6a1e16f735e82b4b0737d38c6dec04d2f51c036dc2068993febc2f9e05c77ef00a21,
0x93b897cdf9a42f4131395b9478971ab0f6d8192215eb0354d0c76a3880eb9549539938dca3999afa3421d048dfb7751f2255ffb185ed9fccdaf8072ef2dfaa4f,
0x9bd7a828232bead6769c5d96b68090b92a3cf9d62269c6719e5b8b126a2649f5aa6f499c0efe02f9bda1ce88a889f8fb908f4402642827d4544069ac8e0d36b1,
0x971b77900d298726678e2b419a515b1f457d9675d7a719db8c989b57b7e2d3de5514d4517c3812ed1c276f6cbf594e8a9aecef96f103284325235fd1641d6ee7
]
# Ciphertexts
rem = [
0x966680baa9620f53964d7180c5078189f0c2dd1629410e86ac3c8e3f54f119df996789f7cb6856798bd5d6c1b0ad4633e8e14fd6ed1090968a33f0c0bc655f3c,
0x33a68fb770bd593b86e92812ddf71fe5088564c8757239c798cf68e8932eac9d8987b5127fedaf5843e9fa69054ae838b37213959870c774656bae3eb86bce7a,
0x3c54104fc3b08c97285eda33299fafb80e88c95dcedc5a2e6c4181b9a0012a0b8f166c5f0111a1911a50c5961c064b7b935117679fbe60e758d4c82601bd119c,
0xa1423b2a3592e79f455a66f357399730cd8559dd34774179ad3540314f4a276b112dadd2420393df413293aadd42e3c2ef278a398333f5eb9b1f75713462e26a,
0x62909c4e065c9d8de305d1a293f7d0550016a63298c424540f29150824eacaa86ad10d41a1e899d40e61c67be0ffc28ae6b202099f5f5aad397a2d9793b418cd,
0x42705b085031ce46399c7268315fc2373a4c139d6b5bc84f9706360ec0566c8dbb291aa45339d33c48d944115178e30db622c04604215cf128111243e1e47df5,
0x1913ae6b74dd3e9bd9c16c9fb34d868d49807af317c1136978ea33169f2a98094bfaad122a6801ca8f78769d160e2ece9cb04fa4524f8dfe971ee007f1a727eb,
0x37d5ea81d9fa45391fbb8c6abf8339c13380f430be192b0ac23e3f0679630b4010b990cf9bdaad689e4477ca4e0daf5914398c61d0e7b3d3c9fca2e5113c097f,
0x10f136a0a9cfab48f376bf88219e06ca927a934390329975eb1a9cb03aa22b638200cbdbfd6c21306c42823899399fe16038da17d818a88f42d45fa61afbe327,
0x92c2a0791ff65f0d9d5cfa35fe580ee9721d1b0803d7e87b0c239255ee8bcbf4a5983f5b25d3e9a0e6eade99e86815f1da9f242010297fb1e07e217f1e489ed3,
0x3e9d7f2ce6ef8177488d4c52fecadb591117b3a391efc03cbd029f8b687ca058558a817d8982dc68cef1df9163ebd2d20860ba9c8f8f12c9693faa9cf09eee2f
]
# Exponent
e = 11
res = libnum.solve_crt(rem, mod)
print("Solve M^e using CRT")
val = libnum.nroot(res, e)
print(b"Padded plaintext: " + long_to_bytes(val))
We get the solution straight away:
~ python3 solver.py
Solve M^e using CRT
b'Padded plaintext: HTB{why_w0u1d_43$_P4dd1nG_k33p_m3$$4g3_s3cur3}\x02\x02'