Fascinating cryptography. Part 1

Like many information security specialists, I really like to stretch my brain with various puzzles. The ideal format for me is the CTF format, which allows you to test your knowledge and a bit of non-standard thinking on various types of tasks.

Today I want to talk about the first of three tasks from the Crypto category from last year’s CTF HTB “Cyber ​​Apocalypse”. Cryptography tasks are my special love, because they allow an unconventional look at both familiar cryptographic algorithms and unsuccessful attempts to use them. It is especially interesting to look for vulnerabilities in self-written algorithms. The latter is the most dangerous in real life, since some developers are sure that they will be able to at least correctly implement the well-known algorithm, and not drag OpenSSL along with them. Some even try to write their own algorithm and thus ensure reliable data protection!
Many CTF tasks of varying complexity usually allow you to quickly debunk this myth)

Task one. Android-in-the-middle

Why I love CTF from HTB, where each puzzle is both a beautiful story and a little clue in the title.

Let’s start today with a simple task in the “Easy” category. Judging by the name, there is a clear reference to the MITM attack here.

The task code is under the cut. If you want to repeat the solution or find your own version while waiting for the publication of articles – here is the source code of all three tasks on Ya.Disk https://disk.yandex.ru/d/vEvsBwYMnrlzaQ

The task consists of only one file.

source.py
from Crypto.Cipher import AES
from Crypto.Util.number import long_to_bytes
import hashlib
import random
import socketserver
import signal


FLAG = "HTB{--REDACTED--}"
DEBUG_MSG = "DEBUG MSG - "
p = 0x509efab16c5e2772fa00fc180766b6e62c09bdbd65637793c70b6094f6a7bb8189172685d2bddf87564fe2a6bc596ce28867fd7bbc300fd241b8e3348df6a0b076a0b438824517e0a87c38946fa69511f4201505fca11bc08f257e7a4bb009b4f16b34b3c15ec63c55a9dac306f4daa6f4e8b31ae700eba47766d0d907e2b9633a957f19398151111a879563cbe719ddb4a4078dd4ba42ebbf15203d75a4ed3dcd126cb86937222d2ee8bddc973df44435f3f9335f062b7b68c3da300e88bf1013847af1203402a3147b6f7ddab422d29d56fc7dcb8ad7297b04ccc52f7bc5fdd90bf9e36d01902e0e16aa4c387294c1605c6859b40dad12ae28fdfd3250a2e9
g = 2


class Handler(socketserver.BaseRequestHandler):
    def handle(self):
        signal.alarm(0)
        main(self.request)


class ReusableTCPServer(socketserver.ForkingMixIn, socketserver.TCPServer):
    pass


def sendMessage(s, msg):
    s.send(msg.encode())


def recieveMessage(s, msg):
    sendMessage(s, msg)
    return s.recv(4096).decode().strip()


def decrypt(encrypted, shared_secret):
    key = hashlib.md5(long_to_bytes(shared_secret)).digest()
    cipher = AES.new(key, AES.MODE_ECB)
    message = cipher.decrypt(encrypted)
    return message


def main(s):
    sendMessage(s, DEBUG_MSG + "Generating The Global DH Parameters\n")
    sendMessage(s, DEBUG_MSG + f"g = {g}, p = {p}\n")
    sendMessage(s, DEBUG_MSG + "Calculation Complete\n\n")

    sendMessage(s, DEBUG_MSG + "Generating The Public Key of CPU...\n")
    c = random.randrange(2, p - 1)
    C = pow(g, c, p)
    sendMessage(s, DEBUG_MSG + "Calculation Complete\n")
    sendMessage(s, DEBUG_MSG + "Public Key is: ???\n\n")

    M = recieveMessage(s, "Enter The Public Key of The Memory: ")

    try:
        M = int(M)
    except:
        sendMessage(s, DEBUG_MSG + "Unexpected Error Occured\n")
        exit()

    sendMessage(s, "\n" + DEBUG_MSG + "The CPU Calculates The Shared Secret\n")
    shared_secret = pow(M, c, p) 
    sendMessage(s, DEBUG_MSG + "Calculation Complete\n\n")

    encrypted_sequence = recieveMessage(
        s, "Enter The Encrypted Initialization Sequence: ")

    try:
        encrypted_sequence = bytes.fromhex(encrypted_sequence)
        assert len(encrypted_sequence) % 16 == 0
    except:
        sendMessage(s, DEBUG_MSG + "Unexpected Error Occured\n")
        exit()

    sequence = decrypt(encrypted_sequence, shared_secret)

    if sequence == b"Initialization Sequence - Code 0":
        sendMessage(s, "\n" + DEBUG_MSG +
                    "Reseting The Protocol With The New Shared Key\n")
        sendMessage(s, DEBUG_MSG + f"{FLAG}")
    else:
        exit()


if __name__ == '__main__':
    socketserver.TCPServer.allow_reuse_address = True
    server = ReusableTCPServer(("0.0.0.0", 1337), Handler)
    server.serve_forever()

Most of the tasks on CTF have a similar structure. They raise the server on port 1337 and wait for a connection. Most do not even require a web browser, a favorite console client like telnet or netcat.

Before jumping into code, I recommend that you always just run the code and enter various data into it, which allows you to get a quick idea of ​​\u200b\u200bhow the program works.

└─$ nc localhost 1337
DEBUG MSG - Generating The Global DH Parameters
DEBUG MSG - g = 2, p = 10177459997049772558637057109490700048394574760284564283959324525695097805837401714582821820424475480057537817583807249627119267268524840254542683041588432363128111683358536204391767254517057859973149680238170237977230020947732558089671785239121778309357814575486749623687357688511361367822815452806637006568922401890961240475060822815400430220536180181951862931844638638933951683988349468373510128406899660648258602475728913837826845743111489145006566908004165703542907243208106044538037004824530893555918497937074663828069774495573109072469750423175863678445547058247156187317168731446722852098571735569138516533993
DEBUG MSG - Calculation Complete

DEBUG MSG - Generating The Public Key of CPU...
DEBUG MSG - Calculation Complete
DEBUG MSG - Public Key is: ???

Enter The Public Key of The Memory: 100000000

DEBUG MSG - The CPU Calculates The Shared Secret
DEBUG MSG - Calculation Complete

Enter The Encrypted Initialization Sequence: 1111111111111111
DEBUG MSG - Unexpected Error Occured

In this case, we are clearly talking about the Diffie–Hellman algorithm. I will refer to a very good and detailed description in the English Wikipedia https://en.wikipedia.org/wiki/Diffie-Hellman_key_exchange. The Russian translation, unfortunately, is inferior to the original. Values ​​in red are secret, blue are public.

Algorithm steps.  I will refer to these steps as I go through the task.
Algorithm steps. I will refer to these steps as I go through the task.

Now let’s take a closer look at how the code works.

We have two known parameters p And g

p = 0x509efab16c5e2772fa00fc180766b6e62c09bdbd65637793c70b6094f6a7bb8189172685d2bddf87564fe2a6bc596ce28867fd7bbc300fd241b8e3348df6a0b076a0b438824517e0a87c38946fa69511f4201505fca11bc08f257e7a4bb009b4f16b34b3c15ec63c55a9dac306f4daa6f4e8b31ae700eba47766d0d907e2b9633a957f19398151111a879563cbe719ddb4a4078dd4ba42ebbf15203d75a4ed3dcd126cb86937222d2ee8bddc973df44435f3f9335f062b7b68c3da300e88bf1013847af1203402a3147b6f7ddab422d29d56fc7dcb8ad7297b04ccc52f7bc5fdd90bf9e36d01902e0e16aa4c387294c1605c6859b40dad12ae28fdfd3250a2e9
g = 2

Then a secret key is generated c and key WITH, which we must give to the second subscriber. However, this key is not given to us here, otherwise the task would be a trivial key exchange using the DH algorithm. In the picture, this is step 2, when Alice has to give us A = g^a mod p. In the task code, this is a variable WITH.

sendMessage(s, DEBUG_MSG + "Generating The Public Key of CPU...\n")
c = random.randrange(2, p - 1)
C = pow(g, c, p)
sendMessage(s, DEBUG_MSG + "Calculation Complete\n")
sendMessage(s, DEBUG_MSG + "Public Key is: ???\n\n")

Next, we are asked to enter our key M (this is step 3 in the algorithm when we have to give B). The value must be an integer, otherwise an error will be returned to us and the program will terminate.

M = recieveMessage(s, "Enter The Public Key of The Memory: ")

try:
   M = int(M)
except:
   sendMessage(s, DEBUG_MSG + "Unexpected Error Occured\n")
   exit()

Now the final part of the DH algorithm. Calculation of the shared secret. This is step 4 of the algorithm.

sendMessage(s, "\n" + DEBUG_MSG + "The CPU Calculates The Shared Secret\n")
shared_secret = pow(M, c, p)
sendMessage(s, DEBUG_MSG + "Calculation Complete\n\n")

Here, in an ideal world, we would also have to calculate the shared secret, but we were not given the key. WITH, so we can only guess about its meaning) This is the task of CTF. How to influence the DH algorithm to get the value of the shared secret? Then we need it to get the flag.

The flag is very simple. We must give the phrase “Initialization Sequence – Code 0” encrypted with the AES algorithm in ECB mode on a shared encryption key. If, as a result of decryption on a public key (which we do not know), the phrase matches the expected one, the server will return the flag value to us. Everything seems to be simple, but you need to somehow find out the key C, which we were not given. Or not?

def decrypt(encrypted, shared_secret):
    key = hashlib.md5(long_to_bytes(shared_secret)).digest()
    cipher = AES.new(key, AES.MODE_ECB)
    message = cipher.decrypt(encrypted)
    return message

...........

encrypted_sequence = recieveMessage(
	s, "Enter The Encrypted Initialization Sequence: ")

try:
	encrypted_sequence = bytes.fromhex(encrypted_sequence)
	assert len(encrypted_sequence) % 16 == 0
except:
	sendMessage(s, DEBUG_MSG + "Unexpected Error Occured\n")
	exit()

sequence = decrypt(encrypted_sequence, shared_secret)

if sequence == b"Initialization Sequence - Code 0":
	sendMessage(s, "\n" + DEBUG_MSG +
				"Reseting The Protocol With The New Shared Key\n")
	sendMessage(s, DEBUG_MSG + f"{FLAG}")
else:
	exit()

Let’s go back to the code and the DH algorithm. The only parameter (apart from the encrypted message) that we can influence is the key M.

shared secret shared_secretand it is also the encryption key, is considered as M to the extent c modulo p.

sendMessage(s, "\n" + DEBUG_MSG + "The CPU Calculates The Shared Secret\n")
shared_secret = pow(M, c, p)
sendMessage(s, DEBUG_MSG + "Calculation Complete\n\n")

However, the parameter c we don’t know since it is a random number in the range (2, p-1)

c = random.randrange(2, p - 1)
C = pow(g, c, p)

DH protection is based on the fact that the key M counts the same as a key WITH, those. this number g raised to an unknown large power modulo p. However, here we can directly manipulate this value!

There are only 2 values ​​that predictably behave when raised to any (unknown to us) degree. These are 0 (zero) and 1 (one). Those. if as a key M we will give value 0 or 1That shared_secret will always be equal 0 or 1!

It remains to solve the problem of encrypting the desired string and getting it in the form of hex_encoded, as the program expects.

To make it clearer, where in the end we get shared_secretthe code is a bit redundant and includes the original parameter generation c.

from Crypto.Cipher import AES
from Crypto.Util.number import long_to_bytes
import hashlib
import random

p = 0x509efab16c5e2772fa00fc180766b6e62c09bdbd65637793c70b6094f6a7bb8189172685d2bddf87564fe2a6bc596ce28867fd7bbc300fd241b8e3348df6a0b076a0b438824517e0a87c38946fa69511f4201505fca11bc08f257e7a4bb009b4f16b34b3c15ec63c55a9dac306f4daa6f4e8b31ae700eba47766d0d907e2b9633a957f19398151111a879563cbe719ddb4a4078dd4ba42ebbf15203d75a4ed3dcd126cb86937222d2ee8bddc973df44435f3f9335f062b7b68c3da300e88bf1013847af1203402a3147b6f7ddab422d29d56fc7dcb8ad7297b04ccc52f7bc5fdd90bf9e36d01902e0e16aa4c387294c1605c6859b40dad12ae28fdfd3250a2e9
g = 2

def encrypt(text, shared_secret):
    key = hashlib.md5(long_to_bytes(shared_secret)).digest()
    cipher = AES.new(key, AES.MODE_ECB)
    enc_message = cipher.encrypt(text)
    return enc_message

c = random.randrange(2, p - 1)
M = 1
shared_secret = pow(M, c, p)

shared_sequence = encrypt(b"Initialization Sequence - Code 0", shared_secret)
print("Encrypted Initialization Sequence is: " + shared_sequence.hex() + '\n\n')

After starting, we get a value that we just need to give to the server and get the flag!

What conclusions can be drawn from this? When implementing even very well-known algorithms, do not forget to add checks for the validity of the resulting values. In the DH algorithm, the key should never degenerate and be equal to 1 or 0. If such a check existed in the code, then the problem would already be unsolvable.

Similar Posts

Leave a Reply

Your email address will not be published. Required fields are marked *