Primary Knowledge Writeup - Cyber Apocalypse 2024

→ 1 Introduction

The description of the challenge is shown below.

→ 2 Key Techniques

The key techniques employed in this writeup are:

• Manual Python source code review
• Exploiting an RSA encryption weakness due to incorrectly chosen parameters.

→ 3 Artifacts Summary

The downloaded artifact had the following hash:

$ shasum -a256 crypto_primary_knowledge.zip
e3b6d0e7d1708cc627ec7150bd390b9bbbeea28176513c0c8a6c5bc6f8758e05  crypto_primary_knowledge.zip

The zip file contained a single Python source code file, source.py, and output.txt:

$ unzip crypto_primary_knowledge.zip
Archive:  crypto_primary_knowledge.zip
   creating: crypto_primary_knowledge/
  inflating: crypto_primary_knowledge/source.py
  inflating: crypto_primary_knowledge/output.txt

$ shasum -a256 crypto_primary_knowledge/*
78dbbfff1b7d1ee4e5938733416121a8121be46048a40df2cd05ec92c22ffb2c  crypto_primary_knowledge/output.txt
4061980e8e15348d71202bb1a2724f4addcc45ced007b95909320f7d6f8459b6  crypto_primary_knowledge/source.py

→ 4 Static Analysis

→ 4.1 output.txt

output.txt contains 3 variables which look suspiciously like components of RSA encryption:

• the modulus n.
• the public exponent e.
• the ciphertext c.

n = 144595784022187052238125262458232959109987136704231245881870735843030914418780422519197073054193003090872912033596512666042758783502695953159051463566278382720140120749528617388336646147072604310690631290350467553484062369903150007357049541933018919332888376075574412714397536728967816658337874664379646535347
e = 65537
c = 15114190905253542247495696649766224943647565245575793033722173362381895081574269185793855569028304967185492350704248662115269163914175084627211079781200695659317523835901228170250632843476020488370822347715086086989906717932813405479321939826364601353394090531331666739056025477042690259429336665430591623215

→ 4.2 source.py

source.py contains Python code that appears to implement the RSA encryption algorithm:

• Line 5: the message, which is the flag, is converted to a large number.
• Line 7: the modulus n is chosen but more on that later.
• Line 8: the public exponent e is a fixed constant.
• Line 9: the ciphertext is calculated by raising the message m to the power e and taking the modulus n.
• Line 11-14: the public parameters and ciphertext are written to output.txt.

import math
from Crypto.Util.number import getPrime, bytes_to_long
from secret import FLAG

m = bytes_to_long(FLAG)

n = math.prod([getPrime(1024) for _ in range(2**0)])
e = 0x10001
c = pow(m, e, n)

with open('output.txt', 'w') as f:
    f.write(f'{n = }\n')
    f.write(f'{e = }\n')
    f.write(f'{c = }\n')

→ 5 Vulnerability analysis

Line 7 is suspicious. It looks like the intention was to calculate the product of prime numbers but actually only returns a single prime number. This can be observed in an IPython session below. The bug is due to 2**0 which equals 1 instead of 2**1 which equals 2.

$ python3 -mvenv venv
$ . ./venv/bin/activate
$ pip install pycryptodome
$ ipython3
/usr/lib/python3/dist-packages/IPython/core/interactiveshell.py:915: UserWarning: Attempting to work in a virtualenv. If you encounter problems, please install IPython inside the virtualenv.
  warn(
Python 3.11.8 (main, Feb  7 2024, 21:52:08) [GCC 13.2.0]
Type 'copyright', 'credits' or 'license' for more information
IPython 8.20.0 -- An enhanced Interactive Python. Type '?' for help.

In [1]: from Crypto.Util.number import getPrime, bytes_to_long

In [2]: import math

In [3]: [getPrime(1024) for _ in range(2**0)]
Out[3]: [129867612338043753784427186349043852544905779365766658645893118181770686490903833118181604952593117723567628000332196905766133290101995136146874275597755257231193270212425471180152555643803216212799500580693243760908122524426394426510284969851527823490671396666644002095223132604256518957020157122778073767829]

In [4]: math.prod(_)
Out[4]: 129867612338043753784427186349043852544905779365766658645893118181770686490903833118181604952593117723567628000332196905766133290101995136146874275597755257231193270212425471180152555643803216212799500580693243760908122524426394426510284969851527823490671396666644002095223132604256518957020157122778073767829

Normally in RSA, the modulus is calculated by multiplying two large prime numbers and thus n itself is not a prime number. This leads to asking what would happen if n was a prime number. An answer was found at StackExchange:

The totient ϕ of a prime number N is trivial to calculate as all integers less than N are
co-prime with N, hence ϕ(N)=N−1. Once we know ϕ(N)=N−1 we can easily recover the private
key d from the public key (e,N), we just calculate d=e−1 mod (N−1).

Euler’s totient function reduces to n - 1 in this case due to the definition of the function being “positive integers up to a given integer n that are relatively prime to n”. Since n is prime, its only factors are itself and 1 and hence every number less than it are relatively prime to n. In other words, they have no common factors with n.

→ 6 Implementing the decryptor

decrypt.py was implemented as below:

• Lines 4-6: contents of output.txt.
• Line 8: calculation of phi, Euler’s totient function.
• Line 9: calculation of d, the private exponent.
• Line 10: decryption of the ciphertext.
• Line 12: convert the message to bytes and print it.

import math
from Crypto.Util.number import getPrime, bytes_to_long, long_to_bytes

n = 144595784022187052238125262458232959109987136704231245881870735843030914418780422519197073054193003090872912033596512666042758783502695953159051463566278382720140120749528617388336646147072604310690631290350467553484062369903150007357049541933018919332888376075574412714397536728967816658337874664379646535347
e = 65537
c = 15114190905253542247495696649766224943647565245575793033722173362381895081574269185793855569028304967185492350704248662115269163914175084627211079781200695659317523835901228170250632843476020488370822347715086086989906717932813405479321939826364601353394090531331666739056025477042690259429336665430591623215

phi = n - 1
d = pow(e, -1, phi)
m = pow(c, d, n)

print(long_to_bytes(m))

→ 7 Obtaining the flag

The script was run and the flag was obtained:

$ python3 -mvenv venv
$ . ./venv/bin/activate
$ pip install pycryptodome
$ python3 decrypt.py
b'HTB{0h_d4mn_4ny7h1ng_r41s3d_t0_0_1s_1!!!}'

→ 8 Conclusion

The flag was submitted and the challenge was marked as pwned