National Cyber Security Hackathon 2022 — Cryptography Write Up

---

There’s a saying that gets thrown around a lot in the cybersecurity community, “Never roll your own crypto”, which refers to the idea that it is generally not recommended to create your own cryptographic algorithms or protocols, and instead to use established and well-vetted implementations.

In this writeup, let’s explore the solutions to the cryptography challenges from the National Cyber Security Hackathon 2022 and consider the reasons behind this saying and some common pitfalls to avoid when doing cryptography.

Heads up, the code coming up might not be the prettiest. I’m a hacker first, then a software engineer, so when I’m trying to hack together a solution, aesthetics and best practices often take the backseat.

So without further ado, let’s get started.

Extreme Ratio — Karachi Qualifier

---

This challenge was classified as hard and was worth 200 points. The following source code was provided.

Source Code

#!/usr/bin/env python3

import gzip
import os

from Crypto.Cipher import AES
from Crypto.Util import Counter

ENCRYPT_KEY = os.urandom(16)

FLAG = b'flag{*************************}'

def encrypt_ctr(data):
    ctr = Counter.new(64, prefix=os.urandom(8))
    cipher = AES.new(ENCRYPT_KEY, AES.MODE_CTR, counter=ctr)
    ctxt = cipher.encrypt(data)
    return ctxt

def encrypt_ecb(data):
    cipher = AES.new(ENCRYPT_KEY, AES.MODE_ECB)
    ctxt = cipher.encrypt(data)
    return ctxt

print("(Compress|Encrypt)ion Service\n")
print("Available Options: ")
print("[0] Encryption Only (AES CTR)")
print("[1] Encryption Only (AES ECB)")
print("[2] Compression + Encryption:  (Gzip + AES CTR)")
print("[3] Compression + Encryption:  (Gzip + AES ECB)")

try:
    option = int(input(">> "))
    if option < 0 or option > 3:
        print("Wrong Option")
        exit(1)
except:
    print("Error")
    exit(-1)

while True:
    ptxt_hex = input("Data (hex encoded): ")
    if len(ptxt_hex) < 32:
        continue
    ptxt = FLAG + bytes.fromhex(ptxt_hex)

    if option == 0:
        ctxt = encrypt_ctr(ptxt)
    elif option == 1:
        ctxt = encrypt_ecb(ptxt)
    elif option == 2:
        ptxt = gzip.compress(ptxt)
        ctxt = encrypt_ctr(ptxt)
    elif option == 3:
        ptxt = gzip.compress(ptxt)
        ctxt = encrypt_ecb(ptxt)

    out = ctxt + bytes([len(ctxt)])
    print(out.hex())

Initial Analysis

The code is a simple command-line utility that provides four options:

1. Encryption with AES in CTR mode
2. Encryption with AES in ECB mode
3. Compression with gzip followed by encryption with AES in CTR mode
4. Compression with gzip followed by encryption with AES in ECB mode

The flag is declared at the start of the program along with the randomly generated AES key and IV/Counter. The user is prompted to select an option, and then to input data, which is concatenated with the flag and then encrypted according to the selected option. The result is then printed on the command line.

Initially, the code does not seem to be vulnerable, as it appears to use secure cryptographic practices such as generating random keys and IVs/Counters. However, upon a closer look, we find that the third and fourth options are modeled on the CRIME attack. I was familiar with this attack because I had previously come across and solved a similar problem and had read about the concept. Here’s what Wikipedia has to say about the attack:

CRIME (Compression Ratio Info-leak Made Easy) is a security vulnerability in HTTPS and SPDY protocols that utilize compression, which can leak the content of secret web cookies.[1] When used to recover the content of secret authentication cookies, it allows an attacker to perform session hijacking on an authenticated web session, allowing the launching of further attacks. CRIME was assigned CVE-2012-4929.[2]

Proof of Concept

Here’s how the attack works:

Say we compress three similar strings, Hello World!, Hello Hello World!, Hello There World!

>>> import gzip
>>> len(gzip.compress(b"Hello World!"))
32
>>> len(gzip.compress(b"Hello Hello World!"))
34
>>> len(gzip.compress(b"Hello There World!"))
38

Notice the changes in lengths of compressed input strings? Well, that’s how compression works. It identifies repeating patterns in the input and replaces them with a smaller representation.

Explain Like I’m Five

The first input string is Hello World!, which when compressed, is 32 bytes long. The second input string is Hello Hello World!, which has a slightly longer compressed representation (34 bytes) because it has more repeated characters. The third input string is Hello There World!, which has an even longer compressed representation (38 bytes) because it has fewer repeated characters and more unique characters. In short, the more repetition there is, the shorter the compressed representation will be. And that’s all we need to crack this challenge.

The Attack

We know that the flag value starts with flag{, and is likely made up of ASCII letters, digits, and special characters _{}. It’s also very likely that the flag will not consist of the ; character. With that knowledge, we can begin the process of recovering the flag.

Here’s a step by step breakdown of the process:

1. Create a payload by appending an invalid_char to the flag and multiplying the resulting string by 5 (this will ensure that the len(ptxt_hex) > 32 condition is satisfied).
2. Send the payload to the server and store the length of the response in a variable called response_length. (Refer to step 4 and you’ll realize why we’re only interested in length)
3. Repeat the process, but this time append each character that is likely to be in the flag to the flag instead of the invalid_char.

4. Compare the length of the current response to the initial response_length. If the length of the current response is smaller than the initial response, it means that the current character is likely to be part of the flag. This can be best explained by the following example:

    >>> len(gzip.compress(b"flag{test_flag}" + b"flag{;")) # invalid char
    37
    >>> len(gzip.compress(b"flag{test_flag}" + b"flag{t")) # correct char
    36
    >>> len(gzip.compress(b"flag{test_flag}" + b"flag{te")) # correct char
    36
    >>> len(gzip.compress(b"flag{test_flag}" + b"flag{test_flag}")) # correct char
    36
   

5. Add the current character to the flag value.
6. Repeat this process until the flag is fully recovered.

Attack Code

from pwn import *
from string import ascii_letters, digits

flag = "flag{" # known partial flag
chars = ascii_letters + digits + "_" # flag charset
invalid_char = ';' # char that we know will not exist in the flag

io = remote('13.37.13.37', 1337) # make connection with the server

io.recvuntil(b">>")
io.sendline(b"2")
io.recvuntil(b"Data (hex encoded): ")

payload = (flag + invalid_char) * 5 # craft payload with the invalid char willingly

io.sendline(payload.encode().hex().encode()) # send payload
response = io.recvline().decode() # receive response
response_length = len(response) # length of received reponse

known_flag = "flag{******************************}" # useful to calculate length

while len(flag) != len(known_flag) - 1: # loop till found flag < actual flag
    for char in chars: # try all chars
        io.recvuntil(b"Data (hex encoded): ")
        payload = ((flag + char) * 5).encode().hex().encode() # append char with known flag

        io.sendline(payload)
        response = io.recvline().decode()

# If length of current response is less than the response we received for invalid char,
# it means we have found the correct char for the current position.
# Append the char to the flag and continue.
        if len(response) < response_length:
            flag += char
            print(flag)
            break

flag += "}"
print(flag)

┌──(w㉿kali)-[~]
└─$ python3 solve.py
flag{c
flag{co
flag{com
flag{comp
flag{compr
flag{compre
flag{compres
flag{compress
flag{compressi
flag{compressio
flag{compression
flag{compression_
flag{compression_r
flag{compression_ra
flag{compression_rat
flag{compression_rati
flag{compression_ratio
flag{compression_ratio_
flag{compression_ratio_s
flag{compression_ratio_si
flag{compression_ratio_sid
flag{compression_ratio_side
flag{compression_ratio_side_
flag{compression_ratio_side_c
flag{compression_ratio_side_ch
flag{compression_ratio_side_cha
flag{compression_ratio_side_chan
flag{compression_ratio_side_chann
flag{compression_ratio_side_channe
flag{compression_ratio_side_channel
flag{compression_ratio_side_channel}

It took me around 10 minutes to solve this challenge, and approximately two hours to write the explanation for the solution.

Weird — Lahore Qualifier

---

We’re provided with the following parameters for this challenge.

p = 176023127217849634927507644091332103662520798054278045327249238656498565387166410134529055214072955585770692068345570429086751483097092606584061804212765484464710219858985411381151536676964148178819264599826409752010695119522361661128265187444633270601478731133478455869738783525606488878825620612673405443451
q = 112223742839001528812998118414186973172817700984809834685105385564920931672517928021207242740576468083925973443165114290353820217347317026045854850099010720339559464915862999940561296479870088962751450854529450600985614397788176734730474800832462529288309338861856248732919840555336781231835349093136651776199
dp = 30385087538855105185173631572543831910674493438359546631957370965394172444160714756294203320157155777516716569112588031576849314924796304802920730636229236548768238849909313008742374774478823911081516143430774367261518805277000586852931743778506123941097942991716525694686408217996359250833964223155034398849
dq = 16565834851621714934943194340380561354378406645660464449478884583192424151732554179201902353804271636654563551379619523372168111644035752758829399035221380255914879788552481418444975048102550117169468808280550250275236324494363826390413993168761753803593832990575552156785084689157314624226120721693168527045
ct = 12471250728278476973667997300089729054215534203191298445075721390063696581388107032026935036071214619926891164048897398168910187436274670469379883863773864404832345129175958512553655002601862046540235957444868738298616361692115344364105067726967540803482175683177928601460820055610057091618766365214386842148469007862547736382438539960143699747392070571106949826103889774269543672861821736945264589704316771379195593723822149690773183639123458879061206847327965981924555643367839051015699745254023361484614560953387636228877078592886198124833581947075581814292380432723836026412556502710472578640877967731483702882569

Initial Analysis

From the Wikipedia page of RSA cryptosystem, the presence of p, q, dp, dq, and ct is a strong indication that a variant of RSA with Chinese Remainder Theorem is used.

Normally, RSA can take a while to decrypt a ciphertext because it involves raising the ciphertext to the power of the private key modulo the modulus, which can be a pain with big numbers. But with CRT, we can make the whole process a lot faster by taking two modular exponentiations with smaller exponents and moduli. To use RSA with CRT, we have to generate our RSA key a certain way and have a few extra values on hand, like $dp$, $dq$, and $q_{inv}$. Then we can just plug those values in along with the ciphertext and boom, decryption happens a lot quicker.

Solution

Since we have all the necessary parameters, we can just follow the decryption process as described on the Wikipedia page.

\[q_{inv} = q^{-1} \mod p\] \[m_1 = c^{d_P} \mod p\] \[m_2 = c^{d_Q} \mod q\] \[h = q_{inv}(m_1 - m_2) \pmod p\] \[m = m_2 + hq \pmod{pq}\]

I have implemented the following solution in Python

from Crypto.Util.number import *

p = 176023127217849634927507644091332103662520798054278045327249238656498565387166410134529055214072955585770692068345570429086751483097092606584061804212765484464710219858985411381151536676964148178819264599826409752010695119522361661128265187444633270601478731133478455869738783525606488878825620612673405443451
q = 112223742839001528812998118414186973172817700984809834685105385564920931672517928021207242740576468083925973443165114290353820217347317026045854850099010720339559464915862999940561296479870088962751450854529450600985614397788176734730474800832462529288309338861856248732919840555336781231835349093136651776199
dp = 30385087538855105185173631572543831910674493438359546631957370965394172444160714756294203320157155777516716569112588031576849314924796304802920730636229236548768238849909313008742374774478823911081516143430774367261518805277000586852931743778506123941097942991716525694686408217996359250833964223155034398849
dq = 16565834851621714934943194340380561354378406645660464449478884583192424151732554179201902353804271636654563551379619523372168111644035752758829399035221380255914879788552481418444975048102550117169468808280550250275236324494363826390413993168761753803593832990575552156785084689157314624226120721693168527045
ct = 12471250728278476973667997300089729054215534203191298445075721390063696581388107032026935036071214619926891164048897398168910187436274670469379883863773864404832345129175958512553655002601862046540235957444868738298616361692115344364105067726967540803482175683177928601460820055610057091618766365214386842148469007862547736382438539960143699747392070571106949826103889774269543672861821736945264589704316771379195593723822149690773183639123458879061206847327965981924555643367839051015699745254023361484614560953387636228877078592886198124833581947075581814292380432723836026412556502710472578640877967731483702882569

q_inv = inverse(q, p)
m1 = pow(ct, dp, p)
m2 = pow(ct, dq, q)
h = q_inv*(m1 - m2) % p
m = m2 + h*q % (p * q)

print(long_to_bytes(m))

When we run the code, we get the flag: FLAG{Ch!n3z_R3m@!nd3r_the0r3m_!$_U$3d_W!th_RSA_!_}

RSA Tricks — Lahore Qualifier

---

For this challenge, the source code and its output were both provided.

Source Code

from Crypto.Util.number import getPrime, bytes_to_long, inverse

flag = b"Flag{XXXXXXXXXXXXXXXXXX}"

p = getPrime(1024)
q = getPrime(1024)
N = p*q
phi = (p-1)*(q-1)
e = 65537
d = inverse(e, phi)

my_key = (N, d)

keys = [(N, getPrime(16)) for i in range(10)]

cipher = bytes_to_long(flag)

for key in keys:
    cipher = pow(cipher, key[1], key[0])

print("- My private key",my_key)
print("- keys",keys)
print("- Encrypted DATA",cipher)

Output

- My private key (18909558900895372672156824811256265991045063590569226191232596663778841681897127254948673384177564949258183981733845039930038021269357172312824082512373461836016350485677617488414637304277231253190262393267785594036484291990305836587795696393789682736379072984234903176904595412028705422757031938515174955122139225813788578454554534920388492258873319280552513284340011592837218450406177853876475453942250479834504622472801073857140934073199654193170101024653069855430546354617875613752042483103556896551326630710625617338594124873967949453649106318872176809724548259100966707725474321152035379845934513208799372680981, 6687607858232036068102764628763869770365480322599654007055390473672368166120078970889731780497544904312162417086944174061956166089097159465136283083934145573266810680333793401383561399492464805933196541665940377169806871229249258898514253795798667416326565964700803909765395310435346968714809745195915667635297064990795636997497174353498801451968512519467684250340907454722122526744868301815309377979214139209924022710213407189093358499791347140504060386679433394906044887470451126139251537410999047504158074154840567036307276609901744175974470733352724690467371739007984796402241006187231818157691483372021327246081)
- keys [(18909558900895372672156824811256265991045063590569226191232596663778841681897127254948673384177564949258183981733845039930038021269357172312824082512373461836016350485677617488414637304277231253190262393267785594036484291990305836587795696393789682736379072984234903176904595412028705422757031938515174955122139225813788578454554534920388492258873319280552513284340011592837218450406177853876475453942250479834504622472801073857140934073199654193170101024653069855430546354617875613752042483103556896551326630710625617338594124873967949453649106318872176809724548259100966707725474321152035379845934513208799372680981, 47041), (18909558900895372672156824811256265991045063590569226191232596663778841681897127254948673384177564949258183981733845039930038021269357172312824082512373461836016350485677617488414637304277231253190262393267785594036484291990305836587795696393789682736379072984234903176904595412028705422757031938515174955122139225813788578454554534920388492258873319280552513284340011592837218450406177853876475453942250479834504622472801073857140934073199654193170101024653069855430546354617875613752042483103556896551326630710625617338594124873967949453649106318872176809724548259100966707725474321152035379845934513208799372680981, 43997), (18909558900895372672156824811256265991045063590569226191232596663778841681897127254948673384177564949258183981733845039930038021269357172312824082512373461836016350485677617488414637304277231253190262393267785594036484291990305836587795696393789682736379072984234903176904595412028705422757031938515174955122139225813788578454554534920388492258873319280552513284340011592837218450406177853876475453942250479834504622472801073857140934073199654193170101024653069855430546354617875613752042483103556896551326630710625617338594124873967949453649106318872176809724548259100966707725474321152035379845934513208799372680981, 64327), (18909558900895372672156824811256265991045063590569226191232596663778841681897127254948673384177564949258183981733845039930038021269357172312824082512373461836016350485677617488414637304277231253190262393267785594036484291990305836587795696393789682736379072984234903176904595412028705422757031938515174955122139225813788578454554534920388492258873319280552513284340011592837218450406177853876475453942250479834504622472801073857140934073199654193170101024653069855430546354617875613752042483103556896551326630710625617338594124873967949453649106318872176809724548259100966707725474321152035379845934513208799372680981, 61091), (18909558900895372672156824811256265991045063590569226191232596663778841681897127254948673384177564949258183981733845039930038021269357172312824082512373461836016350485677617488414637304277231253190262393267785594036484291990305836587795696393789682736379072984234903176904595412028705422757031938515174955122139225813788578454554534920388492258873319280552513284340011592837218450406177853876475453942250479834504622472801073857140934073199654193170101024653069855430546354617875613752042483103556896551326630710625617338594124873967949453649106318872176809724548259100966707725474321152035379845934513208799372680981, 41333), (18909558900895372672156824811256265991045063590569226191232596663778841681897127254948673384177564949258183981733845039930038021269357172312824082512373461836016350485677617488414637304277231253190262393267785594036484291990305836587795696393789682736379072984234903176904595412028705422757031938515174955122139225813788578454554534920388492258873319280552513284340011592837218450406177853876475453942250479834504622472801073857140934073199654193170101024653069855430546354617875613752042483103556896551326630710625617338594124873967949453649106318872176809724548259100966707725474321152035379845934513208799372680981, 43753), (18909558900895372672156824811256265991045063590569226191232596663778841681897127254948673384177564949258183981733845039930038021269357172312824082512373461836016350485677617488414637304277231253190262393267785594036484291990305836587795696393789682736379072984234903176904595412028705422757031938515174955122139225813788578454554534920388492258873319280552513284340011592837218450406177853876475453942250479834504622472801073857140934073199654193170101024653069855430546354617875613752042483103556896551326630710625617338594124873967949453649106318872176809724548259100966707725474321152035379845934513208799372680981, 49297), (18909558900895372672156824811256265991045063590569226191232596663778841681897127254948673384177564949258183981733845039930038021269357172312824082512373461836016350485677617488414637304277231253190262393267785594036484291990305836587795696393789682736379072984234903176904595412028705422757031938515174955122139225813788578454554534920388492258873319280552513284340011592837218450406177853876475453942250479834504622472801073857140934073199654193170101024653069855430546354617875613752042483103556896551326630710625617338594124873967949453649106318872176809724548259100966707725474321152035379845934513208799372680981, 60859), (18909558900895372672156824811256265991045063590569226191232596663778841681897127254948673384177564949258183981733845039930038021269357172312824082512373461836016350485677617488414637304277231253190262393267785594036484291990305836587795696393789682736379072984234903176904595412028705422757031938515174955122139225813788578454554534920388492258873319280552513284340011592837218450406177853876475453942250479834504622472801073857140934073199654193170101024653069855430546354617875613752042483103556896551326630710625617338594124873967949453649106318872176809724548259100966707725474321152035379845934513208799372680981, 62549), (18909558900895372672156824811256265991045063590569226191232596663778841681897127254948673384177564949258183981733845039930038021269357172312824082512373461836016350485677617488414637304277231253190262393267785594036484291990305836587795696393789682736379072984234903176904595412028705422757031938515174955122139225813788578454554534920388492258873319280552513284340011592837218450406177853876475453942250479834504622472801073857140934073199654193170101024653069855430546354617875613752042483103556896551326630710625617338594124873967949453649106318872176809724548259100966707725474321152035379845934513208799372680981, 61603)]
- Encrypted DATA 17645273145351275595525807073989050948965947318364568960587912808565753550868679400761129493639312107881718704399079296084071662498685695737565304759095440251260751277410423164152439238058543479248616726569219754716569949310088729774754396896206740072798713368055282255138359044165511083329692314841881710654928579684619972781423759855118466981710663456827148741309715289690086375657132843333725276700434878544086599889531450088127607426279698041000280210449286322740624514005407432190062616631972904127404246574154910765957984452167524351965862221718745754696108925882968967217857798769220085678518029334502303515802

Initial Analysis

Initially, the program calculates all the stuff it needs to use RSA, like p, q, N, phi, e, and d. Then it calculates 10 public keys that all use the same N, but each has a different, randomly chosen value for e. After that, it loops through all 10 keys and uses each one to encrypt the flag sequentially, and then it prints out the private key, the 10 public keys, and the final encrypted flag.

Solution

The only missing piece to solve this challenge is the value for phi, which we will need to calculate the private keys for the 10 public keys. There’s no direct way to calculate phi with the given values. However, we can use d to calculate the values of prime factors p and q, and then use that to calculate phi.

This stack exchange post discusses how to recover prime factors p and q using private exponent d. From there, we can proceed with the following calculation to calculate phi

\[\phi(N) = (p - 1) \times (q - 1)\]

After that, we can calculate the private exponents for the 10 public keys using

\[d = e^{-1} \mod \phi(N)\]

The following implementation in python can be used for recovering p, q from d (I reused the code from here) and then calculating phi. It can then be used to sequentially decrypt the ciphertext by looping through the keys in reversed order.

from Crypto.Util.number import *
from sympy import nextprime
import math

keys = [(18909558900895372672156824811256265991045063590569226191232596663778841681897127254948673384177564949258183981733845039930038021269357172312824082512373461836016350485677617488414637304277231253190262393267785594036484291990305836587795696393789682736379072984234903176904595412028705422757031938515174955122139225813788578454554534920388492258873319280552513284340011592837218450406177853876475453942250479834504622472801073857140934073199654193170101024653069855430546354617875613752042483103556896551326630710625617338594124873967949453649106318872176809724548259100966707725474321152035379845934513208799372680981, 47041), (18909558900895372672156824811256265991045063590569226191232596663778841681897127254948673384177564949258183981733845039930038021269357172312824082512373461836016350485677617488414637304277231253190262393267785594036484291990305836587795696393789682736379072984234903176904595412028705422757031938515174955122139225813788578454554534920388492258873319280552513284340011592837218450406177853876475453942250479834504622472801073857140934073199654193170101024653069855430546354617875613752042483103556896551326630710625617338594124873967949453649106318872176809724548259100966707725474321152035379845934513208799372680981, 43997), (18909558900895372672156824811256265991045063590569226191232596663778841681897127254948673384177564949258183981733845039930038021269357172312824082512373461836016350485677617488414637304277231253190262393267785594036484291990305836587795696393789682736379072984234903176904595412028705422757031938515174955122139225813788578454554534920388492258873319280552513284340011592837218450406177853876475453942250479834504622472801073857140934073199654193170101024653069855430546354617875613752042483103556896551326630710625617338594124873967949453649106318872176809724548259100966707725474321152035379845934513208799372680981, 64327), (18909558900895372672156824811256265991045063590569226191232596663778841681897127254948673384177564949258183981733845039930038021269357172312824082512373461836016350485677617488414637304277231253190262393267785594036484291990305836587795696393789682736379072984234903176904595412028705422757031938515174955122139225813788578454554534920388492258873319280552513284340011592837218450406177853876475453942250479834504622472801073857140934073199654193170101024653069855430546354617875613752042483103556896551326630710625617338594124873967949453649106318872176809724548259100966707725474321152035379845934513208799372680981, 61091), (18909558900895372672156824811256265991045063590569226191232596663778841681897127254948673384177564949258183981733845039930038021269357172312824082512373461836016350485677617488414637304277231253190262393267785594036484291990305836587795696393789682736379072984234903176904595412028705422757031938515174955122139225813788578454554534920388492258873319280552513284340011592837218450406177853876475453942250479834504622472801073857140934073199654193170101024653069855430546354617875613752042483103556896551326630710625617338594124873967949453649106318872176809724548259100966707725474321152035379845934513208799372680981, 41333),
        (18909558900895372672156824811256265991045063590569226191232596663778841681897127254948673384177564949258183981733845039930038021269357172312824082512373461836016350485677617488414637304277231253190262393267785594036484291990305836587795696393789682736379072984234903176904595412028705422757031938515174955122139225813788578454554534920388492258873319280552513284340011592837218450406177853876475453942250479834504622472801073857140934073199654193170101024653069855430546354617875613752042483103556896551326630710625617338594124873967949453649106318872176809724548259100966707725474321152035379845934513208799372680981, 43753), (18909558900895372672156824811256265991045063590569226191232596663778841681897127254948673384177564949258183981733845039930038021269357172312824082512373461836016350485677617488414637304277231253190262393267785594036484291990305836587795696393789682736379072984234903176904595412028705422757031938515174955122139225813788578454554534920388492258873319280552513284340011592837218450406177853876475453942250479834504622472801073857140934073199654193170101024653069855430546354617875613752042483103556896551326630710625617338594124873967949453649106318872176809724548259100966707725474321152035379845934513208799372680981, 49297), (18909558900895372672156824811256265991045063590569226191232596663778841681897127254948673384177564949258183981733845039930038021269357172312824082512373461836016350485677617488414637304277231253190262393267785594036484291990305836587795696393789682736379072984234903176904595412028705422757031938515174955122139225813788578454554534920388492258873319280552513284340011592837218450406177853876475453942250479834504622472801073857140934073199654193170101024653069855430546354617875613752042483103556896551326630710625617338594124873967949453649106318872176809724548259100966707725474321152035379845934513208799372680981, 60859), (18909558900895372672156824811256265991045063590569226191232596663778841681897127254948673384177564949258183981733845039930038021269357172312824082512373461836016350485677617488414637304277231253190262393267785594036484291990305836587795696393789682736379072984234903176904595412028705422757031938515174955122139225813788578454554534920388492258873319280552513284340011592837218450406177853876475453942250479834504622472801073857140934073199654193170101024653069855430546354617875613752042483103556896551326630710625617338594124873967949453649106318872176809724548259100966707725474321152035379845934513208799372680981, 62549), (18909558900895372672156824811256265991045063590569226191232596663778841681897127254948673384177564949258183981733845039930038021269357172312824082512373461836016350485677617488414637304277231253190262393267785594036484291990305836587795696393789682736379072984234903176904595412028705422757031938515174955122139225813788578454554534920388492258873319280552513284340011592837218450406177853876475453942250479834504622472801073857140934073199654193170101024653069855430546354617875613752042483103556896551326630710625617338594124873967949453649106318872176809724548259100966707725474321152035379845934513208799372680981, 61603)]
my_key = 18909558900895372672156824811256265991045063590569226191232596663778841681897127254948673384177564949258183981733845039930038021269357172312824082512373461836016350485677617488414637304277231253190262393267785594036484291990305836587795696393789682736379072984234903176904595412028705422757031938515174955122139225813788578454554534920388492258873319280552513284340011592837218450406177853876475453942250479834504622472801073857140934073199654193170101024653069855430546354617875613752042483103556896551326630710625617338594124873967949453649106318872176809724548259100966707725474321152035379845934513208799372680981, 6687607858232036068102764628763869770365480322599654007055390473672368166120078970889731780497544904312162417086944174061956166089097159465136283083934145573266810680333793401383561399492464805933196541665940377169806871229249258898514253795798667416326565964700803909765395310435346968714809745195915667635297064990795636997497174353498801451968512519467684250340907454722122526744868301815309377979214139209924022710213407189093358499791347140504060386679433394906044887470451126139251537410999047504158074154840567036307276609901744175974470733352724690467371739007984796402241006187231818157691483372021327246081
c = 17645273145351275595525807073989050948965947318364568960587912808565753550868679400761129493639312107881718704399079296084071662498685695737565304759095440251260751277410423164152439238058543479248616726569219754716569949310088729774754396896206740072798713368055282255138359044165511083329692314841881710654928579684619972781423759855118466981710663456827148741309715289690086375657132843333725276700434878544086599889531450088127607426279698041000280210449286322740624514005407432190062616631972904127404246574154910765957984452167524351965862221718745754696108925882968967217857798769220085678518029334502303515802

d = my_key[1]
n = my_key[0]
e = 65537


def find_prime_factors(n, e, d):
    k = e * d - 1
    s = 0
    t = k

    while t % 2 == 0:
        t = t // 2
        s += 1

    i = s
    a = 2

    while True:
        b = pow(a, t, n)

        if b == 1:
            a = nextprime(a)
            continue

        while i != 1:
            c = pow(b, 2, n)
            if c == 1:
                break
            else:
                b = c
                i -= 1

        if b == n - 1:
            a = nextprime(a)
            continue

        p = math.gcd(b-1, n)
        q = n // p
        return p, q


p, q = find_prime_factors(n, 65537, d)

assert p * q == n

phi = (p - 1) * (q - 1)

for key in keys[::-1]:
    e2 = key[1]
    d = inverse(e2, phi)

    c = pow(c, d, n)

print(long_to_bytes(c))

When we run the code, it prints out the flag: Flag{N0_M1stak3s_W1th_RSA}

Simple RSA — Peshawar Qualifier

---

The following values were provided with the challenge.

n=16147111734460800396004592670421468929337203190257626881606012921435838643682486839638969919126011524499609044486548371078702382995209772340989167246102495015107720926778322642181742667106589581285868164349155811160988904172418976556526686941401355790760512930187413129387612432578824982589943249726538251843134494371205312446417743116926422296053343015812167511415786346049084785782293317209821769860285282759086233935620489199236381431918736093892708407699240019615286528179061459943754101031540022336347845482100465143834304730276518967143705254840069157949656506425821092281518997158195127056924848015561721144141
e=5
ct=111558645679006394985384019922106344256390245431545304101942130922177467904633500612867289903603121371437773246170390092045034734209187474652129636135263800118498886868963176721482556951317449397588032806400411456314451471867958481146150654899999731639797463584634515914586016365684332024632542448233024172820905812188634527134114383199826766449312686149601042672866478590545407942592434984704530370917178774467061817245773716440844189325157951539629919700395694364926837338497933420304953156481808563506013769102906246159631644750831210893

Initial Analysis

In this challenge, we are given three values: n, e, and ct. These variables are commonly used in the RSA, with n being the modulus (product of two primes p and q), e being the public exponent, and ct being the result of the encryption.

Solution

In RSA, ct is calculated using the equation

\[ct = pt^{e} \mod n\]

It is not practical to find the flag by factoring n, as it is too large. However, we can use the small value of ct to our advantage. A small value of ct indicates that the plaintext pt is also small, meaning that the value of $pt^e$ is unlikely to exceed the modulus n.

Mathematically, this would mean that

\[ct = pt^e\]

We have the values of e and ct. Using the above equation, we can find the value of pt by taking the $e_{th}$ root of ct.

\[pt = \sqrt[e]{ct}\]

The following code in Python can be used to do the heavy lifting and find the flag.

from Crypto.Util.number import *
from gmpy2 import iroot

n=16147111734460800396004592670421468929337203190257626881606012921435838643682486839638969919126011524499609044486548371078702382995209772340989167246102495015107720926778322642181742667106589581285868164349155811160988904172418976556526686941401355790760512930187413129387612432578824982589943249726538251843134494371205312446417743116926422296053343015812167511415786346049084785782293317209821769860285282759086233935620489199236381431918736093892708407699240019615286528179061459943754101031540022336347845482100465143834304730276518967143705254840069157949656506425821092281518997158195127056924848015561721144141
e=5
ct=111558645679006394985384019922106344256390245431545304101942130922177467904633500612867289903603121371437773246170390092045034734209187474652129636135263800118498886868963176721482556951317449397588032806400411456314451471867958481146150654899999731639797463584634515914586016365684332024632542448233024172820905812188634527134114383199826766449312686149601042672866478590545407942592434984704530370917178774467061817245773716440844189325157951539629919700395694364926837338497933420304953156481808563506013769102906246159631644750831210893

pt = iroot(ct, e)[0]

print(long_to_bytes(pt))

When we run the code, we get the flag: FLAG{1_7h1nk_7h3_p4dd1n9_w4sn'7_l00n9_en0ugh}

Weird RSA — Islamabad Qualifier

---

For this challenge, we are given the following values and a hint that suggests using the Tonelli-Shanks algorithm.

N = 139799611644152653629701760688199671817845996420960212837951252403071310661876297820375820252422246921626014752203411034874959269400969108775865662803612855844497453022528516710849383838452964627284555992534657432806346951988469594342508507343895146379695281224818693776589341387464488798959628214836525573161
e = 65536
ct = 109733767844983290765119503489592855170752849288516002088462366789671645002019127220142982310787191296062721220321128553167026956288213764125394547996572709867807285688611358568443800185355352482287419029004226687301106507157859735263440122827975982957716941358479236936850859685064250996530125453414484062042

Initial Analysis

From the use of N and e, we can assume that the cryptosystem used is RSA.

The value of $e$ is $65536$, an even number. Another thing to notice is that $N$, which should have been composite, is actually a prime number.

At this point, my subconscious mind had already crafted the following solution

\[\because N \in\mathbb{P}\] \[\phi(N) = N - 1\] \[d = e^{-1} \mod \phi(N)\] \[pt = ct^{d} \mod N\]

After implementing the above in Python and failing to recover the flag, I realized that $e$ and $N - 1$ are both even numbers, and it is not a property of an even number to be coprime to another even number because they share a common factor of $2$.

This implies that $\gcd(e, \phi(N)) \neq 1$, which means that the usual $pt = ct^d \mod N$ formula of RSA for decryption will not work.

What will work instead is taking the square root modulo $N$.

Solution

At first glance, the solution might seem fairly simple; take $63556_{th}$ root of the ciphertext — which you’ll find to be computationally infeasible.

Another thing we can try is taking consecutive square roots modulo $N$ until we find the correct $65536_{th}$ root, which will be our plaintext. But mind you, this is not regular arithmetic we’re dealing with, taking square root is not the same as taking square root modulo an integer $N$, which we refer to as modular square root in modular arithmetic.

But what does it mean to take the square root modulo an integer $N$? To compute an integer $y$ such that

\[y^2 \equiv x \mod N\]

If we take $x = 3$ and $N = 13$, the modular square root will be $y = 4$

\[4^2 \equiv 3 \mod 13\] \[3 \equiv 16 \mod 13\]

The method described above involves trying different values of $y$ until the correct solution is found, which can be computationally infeasible when working with large integers, and that’s when the Tonelli-Shanks algorithm comes into play.

Tonelli-Shanks

The Tonelli-Shanks algorithm is a method for finding the modular square root of an integer $x$ modulo a prime $p$. In other words, it is a method for finding an integer $y$ such that

\[y^2 \equiv x \mod p\]

I will not go into the specifics of the Tonelli-Shanks algorithm, as it is a complex topic on its own. However, it is worth noting that the algorithm has a time complexity of $O(\log(p)^2)$.

All Hail Sage!

SageMath has a built-in square_root() function that uses Tonelli-Shanks to find the modular square root. We can just recurse through consecutive square roots modulo $N$ until we find one that contains the flag.

from Crypto.Util.number import *

def find_roots(exponent, value):
    if exponent <= 1:
        if b"flag" in long_to_bytes(int(value)):
            return long_to_bytes(int(value))
        return None
    if value ^ ((N - 1) // 2) != 1:
        return
    sqrt1 = value.square_root()
    sqrt2 = -sqrt1
    result = find_roots(exponent // 2, sqrt1)
    if result:
        return result
    return find_roots(exponent // 2, sqrt2)

N = 139799611644152653629701760688199671817845996420960212837951252403071310661876297820375820252422246921626014752203411034874959269400969108775865662803612855844497453022528516710849383838452964627284555992534657432806346951988469594342508507343895146379695281224818693776589341387464488798959628214836525573161
e = 65536
ct = 109733767844983290765119503489592855170752849288516002088462366789671645002019127220142982310787191296062721220321128553167026956288213764125394547996572709867807285688611358568443800185355352482287419029004226687301106507157859735263440122827975982957716941358479236936850859685064250996530125453414484062042

print(find_roots(e, GF(N)(ct)))

When we run the code, it prints out the flag: flag{7h3_3xp0n3n7_5h0uld_b3_odd}

Wadding — Islamabad Qualifier

---

This was another hard challenge worth 200 points. The following source code was provided.

Source Code

#!/usr/bin/env python3

from binascii import hexlify as h, unhexlify as u
from Crypto.Cipher import AES
from flag import FLAG
from os import urandom
import random
from sys import exit
import math

BLOCK_SIZE = AES.block_size
KEY = urandom(BLOCK_SIZE)
SECRET_LENGTH = 64
MAX_TRIES = 5000

def pad(t):
    nb = math.ceil(len(t) / BLOCK_SIZE)
    val = nb * BLOCK_SIZE - len(t)
    return t + bytes([val] * val)

def unpad(t):
    l = len(t) - t[-1]
    res = b""
    for i in range(l):
        res += bytes([t[i]])
    return res

def aes_encrypt(key, pt):
    return AES.new(key, AES.MODE_ECB).encrypt(pad(pt))

def aes_decrypt(key, ct):
    return unpad(AES.new(key, AES.MODE_ECB).decrypt(ct))

def generate_secret(length):
    return bytes(random.randint(ord('0'), ord('?')) for _ in range(length))

SECRET = generate_secret(SECRET_LENGTH)
ENCRYPTED_SECRET = aes_encrypt(KEY, SECRET)

def encrypt():
    pt = u(input("Plaintext (in hex): "))
    key = u(input("Key (in hex): "))
    ct = aes_encrypt(key, pt)
    print(f"Ciphertext (in hex): {h(ct).decode()}")

def decrypt():
    ct = u(input("Ciphertext (in hex): "))
    key = u(input("Key (in hex): "))
    pt = aes_decrypt(key, ct)
    print(f"Plaintext (in hex): {h(pt).decode()}")

def get_flag():
    print(f"Encrypted secret (in hex): {h(ENCRYPTED_SECRET).decode()}")
    secret = u(input("Secret (in hex): "))
    if secret == aes_decrypt(KEY, ENCRYPTED_SECRET):
        print(f"Flag: {FLAG}")
        exit()
    else:
        print("Wrong answer!")

if __name__ == '__main__':
    funcs = [exit, encrypt, decrypt, get_flag]
    tries = 0
    print(f"Leak: {SECRET[SECRET_LENGTH-1]}")
    while tries < MAX_TRIES:
        choice = None
        print("1. Encrypt")
        print("2. Decrypt")
        print("3. Get flag")
        print("0. Exit")
        while choice not in ['1', '2', '3', '0']:
            choice = input("> ")
        funcs[int(choice)]()
        tries += 1

Initial Analysis

---

The code presents us with four options:

1. Encryption with AES in ECB mode.
2. Decryption with AES in ECB mode.
3. Get Flag — try to recover the flag by providing the correct value of SECRET
4. Exit the program.

A leak of the last character of SECRET is provided, and we have up to 5000 tries to guess its remaining characters. If our input matches the value stored on the server, the flag will be printed.

The code implements its own functions for pad and un-pad, which seems a bit weird since Python already has those built-in with its Crypto library. Before we jump into analyzing the these functions, let’s consult ChatGPT to understand padding.

In the field of cryptography, it is often necessary to encrypt messages or other data using a specific block size. For example, a block cipher might require that the message be a multiple of 16 bytes in length. If the message is not a multiple of the block size, it must be padded to fit.

The PKCS#7 padding scheme is a way to pad a message so that it is the correct size for a block cipher. It works by adding a certain number of padding bytes to the end of the message, where the value of each padding byte is equal to the number of padding bytes added. For example, if a message needs to be padded with 3 bytes to fit a block size of 16, the PKCS#7 padding would be the bytes 0x03 0x03 0x03.

To remove the padding, the recipient of the message simply checks the value of the last byte and removes that many padding bytes from the end of the message. For example, if the last byte of the message is 0x03, the recipient would remove the last three bytes of the message (0x03 0x03 0x03) to obtain the original unpadded message.

— ChatGPT

For example, if the last byte of the message is 0x03, the recipient would remove the last three bytes of the message (0x03 0x03 0x03) to obtain the original unpadded message.

Hmm. What if the message’s length is 32 and the last byte of the message is 31?

In that case, the un-pad function would return only the first byte of the message, removing the last 31 bytes of the message when, in fact, 31 is not even a correct padding. The correct paddings are 0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07, 0x08, 0x09, 0xA, 0xB, 0xC, 0xD, 0xE, 0xF. It looks like the un-pad function is missing a crucial check. It just removes the last x bytes without even verifying that padding was actually performed in the first place.

Solution

Remember that we were presented with a leak of the last byte? We can use it to our advantage. We’ll need to run the program multiple times till the last byte is 63 which would mean that the program would un-pad 63 bytes from the 64 byte ciphertext, leaving us with just 1 byte to guess. This leaves us with a probability of $\frac{1}{256}$, which is very achievable.

I wrote the following implementation in Python.

from pwn import *

while True:
    io = process('./chall.py')

    io.recvuntil(b"Leak: ")
    leak = int(io.recvline().decode())

    if leak == 63: # leaves us with 1/256 possibilities
        io.recvuntil(b'>')
        io.sendline(b"3")
        io.recvline()
        io.recv()
        
        io.sendline((hex(54)[2:]).encode()) # taking our guess as 54 (36 in hex)

        response = io.recvline()

        if b"Wrong" not in response:
            print(response)
            break

        io.kill()
    else:
        io.kill()

When we run the code, the flag is printed in $< 2$ minutes.

┌──(w㉿kali)-[~]
└─$ python3 solve.py
b'Flag: flag{essence_precedes_existence}\n'

Note: I did not have the original flag, so I hardcoded my own for demonstration.

Rookie — Final Round

---

Rookie was a hard challenge in final round and was worth 200 points. The following source code was provided.

Source Code

#!/usr/bin/env python3

from binascii import hexlify as h, unhexlify as u
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad, unpad
from flag import FLAG
from os import urandom
from random import seed, randint
from sys import exit

BLOCK_SIZE = AES.block_size

def aes_encrypt(key, pt):
    return AES.new(key, AES.MODE_ECB).encrypt(pad(pt, BLOCK_SIZE))

def aes_decrypt(key, ct):
    return unpad(AES.new(key, AES.MODE_ECB).decrypt(ct), BLOCK_SIZE)

def random_byte(a=urandom(16)):
    seed(a)
    return randint(0, 255)

def encrypt_secret(secret):
    return aes_encrypt(bytes(random_byte() for _ in range(BLOCK_SIZE)), secret)

SECRET = urandom(64)
ENCRYPTED_SECRET = encrypt_secret(SECRET)

def encrypt():
    pt = u(input("Plaintext (in hex): "))
    key = u(input("Key (in hex): "))
    ct = aes_encrypt(key, pt)
    print(f"Ciphertext (in hex): {h(ct).decode()}")

def decrypt():
    ct = u(input("Ciphertext (in hex): "))
    key = u(input("Key (in hex): "))
    pt = aes_decrypt(key, ct)
    print(f"Plaintext (in hex): {h(pt).decode()}")

def get_flag():
    print(f"Encrypted secret (in hex): {h(ENCRYPTED_SECRET).decode()}")
    secret = u(input("Secret (in hex): "))
    if secret == SECRET:
        print(f"Flag: {FLAG}")
        exit()
    else:
        print("Wrong answer!")

if __name__ == '__main__':
    funcs = [exit, encrypt, decrypt, get_flag]
    while True:
        choice = None
        print("1. Encrypt")
        print("2. Decrypt")
        print("3. Get flag")
        print("0. Exit")
        while choice not in ['1', '2', '3', '0']:
            choice = input("> ")
        funcs[int(choice)]()

Initial Analysis

This challenge is very similar to Wadding from Islamabad qualifier with just two differences:

1. The author patched the vulnerability in un-pad function and instead resorted to use the implementation that came built-in with the Crypto library.
2. A new function is added called random_byte.

Let’s begin with analyzing random_byte. The function accepts a random byte string of length 16. It then initializes a seed which takes input the random byte string setting a starting point for the random() function, which ensures that the random function generates the same sequence of random integers each time it’s starting point is the same.

The encrypt_secret function calls the random_byte function 16 times for generating a random key. At first glance, this fooled me to think that a random byte will be generated every 16 times the function is called. Instead, what actually happens is each time the function is called, a same random byte is generated.

>>> def random_byte(a=urandom(16)):
...     seed(a)
...     return randint(0, 255)
...
>>> [random_byte() for _ in range(16)]
[126, 126, 126, 126, 126, 126, 126, 126, 126, 126, 126, 126, 126, 126, 126, 126]

This suggests that this function’s capability is limited to generating a combination of total 256 possible keys:

[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
[2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2]
...
...
...
[253, 253, 253, 253, 253, 253, 253, 253, 253, 253, 253, 253, 253, 253, 253, 253]
[254, 254, 254, 254, 254, 254, 254, 254, 254, 254, 254, 254, 254, 254, 254, 254]
[255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255]

Solution

The idea is to brute-force the key from a total of 256 keys. However, we can not just send the keys to the server for decryption, because if the key is incorrect, the server will crash, and we’ll have to start again. A better way to solve this challenge would be to create a list of all possible keys, loop through them to find the correct key, then decrypt the secret and send it to the server. If our secret matches the one stored on the server, we’ll get the flag.

I wrote the following implementation in Python.

from pwn import *
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad, unpad

def generate_all_keys():
    keys = []

    for i in range(256):
        keys.append(bytes([i]) * 16)

    return keys

def aes_decrypt(key, ct):
    return unpad(AES.new(key, AES.MODE_ECB).decrypt(ct), 16)

possible_keys = generate_all_keys()

io = process('./chall.py')

io.recvuntil(b'>')
io.sendline(b"3")

ct = bytes.fromhex(io.recvline().decode().split(": ")[-1].strip())

io.recv()

for key in possible_keys:
    try:
        secret = aes_decrypt(key, ct)
        io.sendline(secret.hex().encode())

        print(io.recvline())

        break

    except:
        pass

Running this program a few times, we’ll get the flag. (worked for me in $\leq 5$ tries)

┌──(w㉿kali)-[~]
└─$ python3 solve.py
b'Flag: flag{or_existence_precedes_essence?}\n'

Note: I did not have the original flag, so I hardcoded my own for demonstration.

Abstract — Final Round

---

Abstract was a hard challenge worth 200 points. The following source code was provided.

Source Code

from Crypto.Util.number import getPrime, inverse, bytes_to_long
import random
import math

FLAG = b'flag{????????????????????}'

def gen_key():
    q = getPrime(512)
    upper_bound = int(math.sqrt(q // 2))
    lower_bound = int(math.sqrt(q // 4))
    f = random.randint(2, upper_bound)
    while True:
        g = random.randint(lower_bound, upper_bound)
        if math.gcd(f, g) == 1:
            break
    h = (inverse(f, q)*g) % q
    return (q, h), (f, g)

def encrypt(q, h, m):
    assert m < int(math.sqrt(q // 2))
    r = random.randint(2, int(math.sqrt(q // 2)))
    e = (r*h + m) % q
    return e

def decrypt(q, h, f, g, e):
    a = (f*e) % q
    m = (a*inverse(f, g)) % g
    return m

public, private = gen_key()
q, h = public
f, g = private

m = bytes_to_long(FLAG)
e = encrypt(q, h, m)

print(f'Public key: {(q,h)}')
print(f'Encrypted Flag: {e}')

A tale of stolen challenges

I will not do a write-up for this challenge, since this was a stolen challenge from CryptoHack’s Find the Lattice. You may verify this by pasting the provided source code on google, the first returned result is the original source of this challenge. I spent around 2 hours during the competition trying to do the math for this challenge, and failed miserably. Meanwhile, almost every other team solved it by pasting the code on google and finding the solutions.

There’s you putting in an effort and time, trying to solve a challenge on your own, and then there are those who know that the solution is available on the internet. Is this not a waste of effort?

Feedbacks were shared with the organizers right after the online qualifying round (which also consisted of a stolen challenge from Fword CTF), and yet they still did nothing to address the participants’ concerns. This is just one example. There were stolen and repeated challenges throughout the hackathon from the online qualifying round to the city qualifier rounds to the final round. I find it hard to understand how such sloppiness at a national level competition could go unnoticed.

Feedback for Organizers

For future CTF competitions, it’s important for the organizers to do their homework and really understand what goes into creating a CTF. It takes a lot of research, planning, and creativity to come up with fresh ideas for challenges. It’s also important to check and double check that your challenges are actually solvable, making sure the platform is available throughout the whole competition, providing official write-ups after the CTF ends, and that you have a plan for when things go wrong (cheating/flag sharing). Organizers should consider reading this CTF guideline to ensure that the competition runs smoothly and provides a meaningful and enjoyable experience for all participants.

Ending note

---

To wrap things up, cryptography can be a lot of fun to work with, especially when you’re solving challenges like in a CTF. But it’s important to remember that real-world situations are a lot different, and it’s essential to use established, tried-and-true algorithms and libraries to keep your systems secure. I hope that the writeup has provided some insight into the process of dos and don’ts of cryptography and that you feel motivated to try your hand at some CTFs of your own. I’m happy to answer any questions you might have about the techniques discussed in this writeup, so feel free to reach out to me on twitter or discord (wonderchild#3321).

That’s All Folks, Happy Hacking!