Cyber Apocalypse 2022

Cyber Apocalyse was an interesting experience. Even though some members of our team, Th3Os, contributed challenges, so they couldn’t work on them, we got a solid 34th placement. Many thanks and congrats especially to my teammate, friend, and mentor Wizard Alfredo for the great crypto challenges. Looking forward to more alfredy :)!

For me personally it was exactly what I wanted, as I hadn’t played seriously a CTF, and epsecially crypto, in some time, so this was a perfect way to get back in shape. Would have played more reversing, but verdic just killed it 🔥

For now I have just the easy, but will add more steadily through the next couple of hours/days.

Crypto | Android-In-The-Middle (479 solves)

Source Code Analysis

This challenge was the easiest, evident by the high number of solves. It implements a Diffie-Hellman Key Exhange protocol, in which we have a man-in-the-middle access, capable of controlling the public key.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

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()

Said public key in turn is used to calculate the shared secret for both communication parties.

1
2
3

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")

After that it asks of us to send an encrypted message (in hex with a length multiple of 16), which then decrypted using a fancy custom decrypt function. What we care about is that shared secret is essentially used as a key for AES, and we are given the plaintext we want our ciphertext to decrypt to

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

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()

Exploitation

So now the fact that we can contorl the public key becomes important in our attempt to control the shared secret. Because if we know the shared secret beforehand, then we can control the key used in AES. What can we give as input M so that M ^ c % p = something we know? The simple trick is to send a simple value, like a 1 or a 0, since we know the result beforehand.

So all we have to do is encrypt Initialization Sequence - Code 0 with an MD5 hash for either 0 or 1, then send the corresponding value to the program running, and it will decrypt it for us, giving us the flag. Below is my solver in python

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

from Crypto.Util.number import *
from Crypto.Cipher import AES
from pwn import *
import hashlib

ip = '188.166.172.138'
port = 31675

io = remote(ip, port)

code = b"Initialization Sequence - Code 0"
shared_secret = 1
key = hashlib.md5(long_to_bytes(shared_secret)).digest()
cipher = AES.new(key, AES.MODE_ECB)
ct = cipher.encrypt(code).hex()

io.recvuntil(b'Enter The Public Key of The Memory: ')
io.sendline(shared_secret)

io.recvuntil(b'Enter The Encrypted Initialization Sequence: ')
io.sendline(ct)

print(io.recvlines(2))

flag: HTB{7h15_p2070c0l_15_pr0tec73d_8y_D@nb3er_c0pyr1gh7_1aws}

Crypto | Jenny From The Block (288 solves)

Source Code Analysis

Jenny was another easy challenge which needed from you to make some simple thoughts to solve it. Essentially we are given a list of 4 allowed commands we can run on the server, allowed_commands = [b'whoami', b'ls', b'cat secret.txt', b'pwd'], with cat secret.txt probably being the one which gives us the flag. After we pass the command and it runs, it encrypts the output with a custom block cipher

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49

BLOCK_SIZE = 32


def encrypt_block(block, secret):
    enc_block = b''
    for i in range(BLOCK_SIZE):
        val = (block[i]+secret[i]) % 256
        enc_block += bytes([val])
    return enc_block


def encrypt(msg, password):
    h = sha256(password).digest()
    if len(msg) % BLOCK_SIZE != 0:
        msg = pad(msg, BLOCK_SIZE)
    blocks = [msg[i:i+BLOCK_SIZE] for i in range(0, len(msg), BLOCK_SIZE)]
    ct = b''
    for block in blocks:
        enc_block = encrypt_block(block, h)
        h = sha256(enc_block + block).digest()
        ct += enc_block

    return ct.hex()


def run_command(cmd):
    if cmd in allowed_commands:
        try:
            resp = subprocess.run(
                cmd.decode().split(' '),  capture_output=True)
            output = resp.stdout
            return output
        except:
            return b'Something went wrong!\n'
    else:
        return b'Invalid command!\n'


def challenge(req):
    req.sendall(b'This is Jenny! I am the heart and soul of this spaceship.\n' +
                b'Welcome to the debug terminal. For security purposes I will encrypt any responses.')
    while True:
        req.sendall(b'\n> ')
        command = req.recv(4096).strip()
        output = run_command(command)
        response = b'Command executed: ' + command + b'\n' + output
        password = os.urandom(32)
        ct = encrypt(response, password)
        req.sendall(ct.encode())

After all the we get the encrypted response. So the question becomes, what can we do here? We obviously have very restricted input control, and we don’t know the password sent. But if we look closely at encrypt_block, we can see that perhaps we can actually retreive it.

1
2
3
4
5
6

def encrypt_block(block, secret):
    enc_block = b''
    for i in range(BLOCK_SIZE):
        val = (block[i]+secret[i]) % 256
        enc_block += bytes([val])
    return enc_block

It iterates through the block, adds the block and secret values at index i, mods the result with 256, and adds that to the encrypted block. But modulo 256 isn’t enough to hide the secret, as 256 <= block[i] + secret[i] < 512. So that way we can not only retreive the encrypted block, but also they secret key, if we solve for it. But to solve for the key, we need to know a 32 bytes plaintext which get’s encrypted with it. Luckily for us, if we look closely at the response variable passed into the encrypt function, we can see that we do in fact have some known plaintext there

1

response = b'Command executed: ' + command + b'\n' + output

And if we look at the length of the response header with the cat secret.txt command concatenated to it, it’s exactly 32. Just what we needed to get the key.

Exploitation

1
2
3
4
5
6
7

leak = b'Command executed: cat secret.txt'
block = ct[:BLOCK_SIZE]

secret = b''
for i in range(BLOCK_SIZE):
    scrt = (block[i]-leak[i]) % 256
    secret += bytes([scrt])

Now all we need to do to decrypt the ciphertext is perform (enc_block[i] - secret[i]) % 256 (and do some other things with the hashes and the keys). Below is my solver

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

from hashlib import sha256
from pwn import *

BLOCK_SIZE = 32

def decrypt_block(block, secret):
    dec_block = b''
    for i in range(BLOCK_SIZE):
        val = (block[i] - secret[i]) % 256
        dec_block += bytes([val])
    return dec_block

def decrypt(ct, secret):
    h = secret
    blocks = [ct[i:i+BLOCK_SIZE] for i in range(0, len(ct), BLOCK_SIZE)]
    flag = b''
    for block in blocks:
        dec_block = decrypt_block(block, h)
        h = sha256(block + dec_block).digest()
        flag += dec_block
    return flag

ip = '138.68.188.223'
port = 31224
io = remote(ip, port)

io.recvuntil(b'> ')
io.sendline(b'cat secret.txt')
ct = bytes.fromhex(io.recvline().rstrip().decode())

leak = b'Command executed: cat secret.txt'
block = ct[:BLOCK_SIZE]

secret = b''
for i in range(BLOCK_SIZE):
    scrt = (block[i]-leak[i]) % 256
    secret += bytes([scrt])
flag = decrypt(ct, secret)
print(flag)

flag: HTB{b451c_b10ck_c1ph3r_15_w34k!!!}

Crypto | The Three-Eyed Oracle (249 solves)

Source Code Analysis

Three-Eyed Oracle is just another typical ECB Padding Oracle. Though it may have a small twist, it doesn’t affect us all that much. Below is the important part of the chall.py file

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

FLAG = b'HTB{--REDACTED--}'
prefix = random.randbytes(12)
key = random.randbytes(16)


def encrypt(key, msg):
    msg = bytes.fromhex(msg)
    crypto = AES.new(key, AES.MODE_ECB)
    padded = pad(prefix + msg + FLAG, 16)
    return crypto.encrypt(padded).hex()


def challenge(req):
    req.sendall(b'Welcome to Klaus\'s crypto lab.\n' +
                b'It seems like there is a prefix appended to the real firmware\n' +
                b'Can you somehow extract the firmware and fix the chip?\n')
    while True:
        req.sendall(b'> ')
        try:
            msg = req.recv(4096).decode()

            ct = encrypt(key, msg)
        except:
            req.sendall(b'An error occurred! Please try again!')

        req.sendall(ct.encode() + b'\n')

It generates a random 16 byte key, asks us for input, and passes that to the encrypt function. In there, the message we added get’s squashed in between the flag and a 12 bytes prefix variable. Then that entire string is padded, and then encrypted. prefix isn’t all that much of a problem, as all it does it just slightly messes up our oracle offsets, but nothing we can’t fix. Before we get into our attack, let’s review an ECB Padding Oracle attack first.

ECB Padding Oracle

The main weakness of ECB is that, for the same key, every time we encrypt the same plaintext, we get the same ciphertext. Now imagine we have an application, like the one above, where it prompts us for input (we can optionally not pass anything), and it appends it to a flag flag{3x4mpl3!?!} (in reality we obviously don’t know the flag). If we pass nothing, then it just encrypts the flag. But let’s say we pass 16 A’s. Then the blocks are like this

1

AAAAAAAAAAAAAAAA    flag{3x4mple!?!}

We split them into two blocks, and now we control the first block. But remember that we want to get the flag. How do we do that? Let’s try and pass 15 A’s instead of 16. Then the blocks will be

1

AAAAAAAAAAAAAAAf    lag{3x4mpl3!?!}\x01

And once encrypted it will be returned to us. And every single time it will be the same. So if we pass 15 A’s and one f, then isn’t that effectively the same thing? Yes it is!

1

AAAAAAAAAAAAAAAf    flag{3x4mpl3!?!}

So we can send a request which returns to us the encrypted first byte of the flag (along with 15 others which we control). Then we go through all printable characters, and send them to the server to get encrypted. Then we check each of them with the correct one, and if we have a match then we found the correct character. Then we decrease the length of the controlled bytes by one, append the known flag character, and we repeat the process till we’re done. Now all we have to do is code the attack.

Exploitation

Let’s start by finding at which offset we can perform the attack (i.e. how many bytes we have to send to control a full block)

1
2
3
4
5
6
7

for count in range(1, 20):
    payload = b'41' * count
    ct = get_ct(io, payload)
    blocks = [ct[i:i+32].decode() for i in range(0, len(ct), 32)]
    print('\n'.join(blocks))
    print(count, len(ct), ct)
    print()

We see that from 20 onwards the second block is the same. So that means that we can start the attack at the 19th byte we send. However we should be a bit smarter about it. With this it means that we have just 19 bytes available to bruteforce. If the flag is more than 19 bytes, it won’t complete properly. So instead of 19, we should go with 35 (19+16). Now that everything is clear, let’s write our solver. Not the prettiest, but it gets the job done :)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

from Crypto.Util.Padding import pad
from Crypto.Cipher import AES
from pwn import *
import string

ip = '134.209.31.115'
port = 32514
io = remote(ip, port)

def get_ct(payload):
    io.recvuntil(b'> ')
    io.sendline(payload)
    ct = io.recvline().rstrip()
    return ct

magic_count = 35
payload = b'41' * magic_count
flag = ''
ALPHABET = string.ascii_lowercase + string.ascii_uppercase + string.digits + '{_}'
count = 0
while '}' not in flag:
    tpayload = b'41' * (magic_count - count)
    target = get_ct(tpayload)
    tblock = target[:96]
    for c in ALPHABET:
        payload = b'41' * (magic_count - count) + flag.encode().hex().encode() + hex(ord(c))[2:].encode()
        ct = get_ct(payload)
        ctblock = ct[:96]
        if ctblock == tblock:
            flag += c
            count += 1
            break
print(flag)

flag: HTB{345y_53cr37_r3c0v3ry}

Crypto | How The Columns Have Turned (224 solves)

Source Code Analysis

Knowing Wizard Alfredo, this challenge (along with another one) was very much his. We are given 3 files, dialog.txt, source.py, and encrypted_messages.txt. The encrypted_messages.txt has the encrypted plaintext, and dialog.txt has what we are told is a key

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

encrypted_messages.txt
VEOAOTNRDCEEIFHIVHMVOETYDEDTESTHTCHLSRPDAIYAATOSTEGIIIOCIPYLTNOTLRTRNLEEUNBEOSFNANDHTUFTEETREEEEOEDHNRNYA
AAVPDESEETURAFFDUCEDAEECNEMOROCEANHPTTGROITCYSSSETTSKTTRLRIUAVSONOISECNJISAFAATAPATWORIRCETYUIPUEEHHAIHOG
NABPSVKELHRIALDVEHLORCNNOERUNGTAEEEHEHDORLIEEAOTITUTEAUEARTEFISESGTAYAGBTHCEOTWLSNTWECESHHBEIOYPNCOLICCAF
NIRYHFTOSSNPECMPNWSHFSNUTCAGOOAOTGOITRAEREPEEPWLHIPTAPEOOHPNSKTSAATETTPSIUIUOORSLEOAITEDFNDUHSNHENSESNADR
NUTFAUPNKROEOGNONSRSUWFAFDDSAAEDAIFAYNEGYSGIMMYTAANSUOEMROTRROUIIOODLOIRERVTAMNITAHIDNHRENIFTCTNLYLOTFINE

dialog.txt
Miyuki says:
Klaus it's your time to sign!
All we have is the last key of this wierd encryption scheme.
Please do your magic, we need to gather more information if we want to defeat Draeger.
The key is: 729513912306026

Now let’s get into the source file. The source has two interesting things. The first is a PRNG, which is seeded with a random 16 byte number. For every plaintext line we get a different round, and the returned value is passed to twistedColumnarEncrypt, which seems to be a fancy transposition cipher.

So we have two things we need to do:

1. Get the key for every ciphertext. We will analyze the PRNG for that.
2. Reverse the transposition cipher. Let’s start with the PRNG

Reversing the PRNG

First off, this is the source code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

class PRNG:
    def __init__(self, seed):
        self.p = 0x2ea250216d705
        self.a = self.p
        self.b = int.from_bytes(os.urandom(16), 'big')
        self.rn = seed

    def next(self):
        self.rn = ((self.a * self.rn) + self.b) % self.p
        return self.rn
...
seed = int.from_bytes(os.urandom(16), 'big')
rng = PRNG(seed)

cts = ""

for message in SUPER_SECRET_MESSAGES:
	key = str(rng.next())
	ct = twistedColumnarEncrypt(message, key)
	cts += ct + "\n"

One would be inclined to look into Linear Congruential Generator, however the vulnerability is extremely simple. As we can see, a has the same value as the modulus, and is then multiplied with the seed. That in turn is added to a random b value, and then everything is modded by p. This acts both as the new seed, and as the key. So where’s the catch?

The problem lies in a being the same value as p. In modular arithmetic, if you multiply a number by the modulus, then since the given number will be a multiple of the modulus, the result will automatically be 0. So it’s as if the addition is never done. So essentially instead of self.rn = ((self.a * self.rn) + self.b) % self.p we have self.rn = self.b % self.p. The very important thing about this is that now the rn value will always be the same, as both b and p are static. So in fact the number we get in dialog.txt is the same key for every plaintext. Truly a secure PRNG.

Reversing The Transposition Cipher

I’m going to start this by saying something general. One of the best things you can do for challenges is make a copy of the source in which you just print stuff and experiment. Personally I call these files hmm.py. This helped me understand how to decrypt the function. It will help you too. This why the reversing of the function is left to the hacker as an exercise (totally won’t write because I’m not bored to explain it😅) But tldr, you need to convert the ciphertext to the necessary format it was in after the key was used for the transposition. Then you reverse the key transposition, and just bring the plaintext to the correct form. Lastly the derived_key is of no importance to us, just take it as the function deriveKey returns it.

Exploitation

Below is my solver

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64

import os

def deriveKey(key):
    derived_key = []

    for i, char in enumerate(key):
        previous_letters = key[:i]
        new_number = 1
        for j, previous_char in enumerate(previous_letters):
            if previous_char > char:
                derived_key[j] += 1
            else:
                new_number += 1
        derived_key.append(new_number)
    return derived_key


def transpose(array):
    return [row for row in map(list, zip(*array))]


def flatten(array):
    return "".join([i for sub in array for i in sub])

def rev(array):
    array = list(''.join(array))
    n_arr = []
    for i in range(0, len(array), 7):
        n_arr.append(array[i:i+7])
    return n_arr

def detranspose(array):
    arr =[]
    j = 0
    while len(arr) != 7:
        tmp = ''
        for i in range(len(array)):
            tmp += array[i][j]
        j += 1
        arr.append(tmp)
    return arr

def decrypt(ct, key):
    derived_key = deriveKey(key)
    width = len(key)

    blocks = [ct[i:i+width] for i in range(0, len(ct), width)]
    blocks = rev(blocks)
    pt = [blocks[i-1][::-1] for i in derived_key]

    flag = detranspose(pt)
    flag = flatten(flag)
    return flag

with open('encrypted_messages.txt') as f:
    lines = f.readlines()
    cts = [line.rstrip() for line in lines]

key = '729513912306026'
flag = ''
for ct in cts:
    flag += decrypt(ct, key)
    flag += '\n'
print(flag)

A very troll-y and fun challenge.

flag: HTB{THELCGISVULNERABLEWENEEDTOCHANGEIT}

If you liked my writeups be sure to bookmark my blog for future posts, and follow me on Twitter :)!

Crypto | MOVs Like Jagger (103 solves)

I’m going to have to be open about two things here. First off, for about a day I didn’t see the source code. So I thought it was a waaaaaay harder challenge than what it actually is :). Secondly, I didn’t take any screenshots for this challenge, which sported a very nice web UI. But it isn’t really needed for the sake of the writeup.

Source Code Analysis

We are given 3 files, app.py, navigation_system.py, and utils.py which isn’t all that interesting. app.py probably is the main flask application, and navigation_system.py holds the crypto logic. Let’s see for ourselves.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

@app.route('/', methods=['GET', 'POST'])
def index():
    if request.method == 'POST':
        try:
            travel_result = checkDestinationPoint(request.form, P, nQ, E)
            location = generateLocation(travel_result)

            if travel_result:
                return render_template('travel.html', location=location, flag=FLAG)
            else:
                return render_template('travel.html', location=location)
        except ValueError as error:
            return render_template("index.html", error_message=str(error),
                                   departed_x=hex(Q.x()), departed_y=hex(Q.y()),
                                   present_x=hex(P.x()), present_y=hex(P.y()))
    return render_template('index.html', departed_x=hex(Q.x()),
                           departed_y=hex(Q.y()), present_x=hex(P.x()),
                           present_y=hex(P.y()))
...
if __name__ == '__main__':
    Q, nQ, P, nP = calculatePointsInSpace()
    app.run(host='0.0.0.0', port=1337, debug=False, use_reloader=False)

Truly that’s what’s going on. Before the application starts, it calls calculatePointsInSpace, and when a POST request is sent, it checks it’s correctness with checkDestinationPoint. So let’s see whats going on in navigation_system.py

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

a = -35
b = 98
p = 434252269029337012720086440207
Gx = 16378704336066569231287640165
Gy = 377857010369614774097663166640
ec_order = 434252269029337012720086440208

E = ecc.CurveFp(p, a, b)
G = ecc.Point(E, Gx, Gy, ec_order)


def generateKeyPair():
    private = randint(1, 2**64)
    public = G * private
    return(public, private)


def calculatePointsInSpace():
    Q, nQ = generateKeyPair()
    P, nP = generateKeyPair()
    return [Q, nQ, P, nP]
...
def checkDestinationPoint(data: dict, P: ecc.Point, nQ: int, E: ecc.CurveFp) -> list:
    destination_x, destination_y = checkCoordinates(data)
    destination_point = ecc.Point(E, destination_x, destination_y, ec_order)
    secret_point = P * nQ
    same_x = destination_point.x() == secret_point.x()
    same_y = destination_point.y() == secret_point.y()

    if (same_x and same_y):
        return True
    else:
        return False

The app initializes an Elliptic Curve, and creates two key pairs. In checkDestinationPoint, it takes our points (does some simple checks in checkCoordinates and then compares them with the discrete log of P and nQ. Even though we know P, we don’t know nQ, it’s the private key. The elliptic curve discrete logarithm problem is trying to find this nQ. There are different attacks to do this, but those familiar with crypto ECC challenges have already taken a hint form the title. It is a direct refference to the MOV attack. Though there are scripts ready to implement the attack, I will try to explain it at the best of my ability.

MOV Attack

For starters, what does the MOV attack even do? When we compute the discrete logarithm problem in Elliptic curves, we do it over an Elliptic Curve E(Fp). A curve with a 256-bit p, such as ours, usually offers 128 bits of security. So computing the discrete logarithm problem is out of the question as even the fastest algorithms for solving the ECDLP are of order O(sqrt(p)). But the same can’t be said for the DLP (Discrete Logarithm Problem). So is there a way to MOVe the discrete log problem from the elliptic curve to a finite field? Yes that’s why we’re here. To quote directly from this post because it said it the best, “The MOV attack uses a bilinear pairing, which (roughly speaking) is a function e that maps two points in an elliptic curve E(Fp) to a element in the finite field Fp^k, where k is the embedding degree associated with the curve.”

Again standing on the shoulders of more capable people, “Informally, you can think of the embedding degree as the smallest integer k that lets you transform or embed an instance of the elliptic curve discrete logarithm problem (ECDLP) over an elliptic E(Fp) into an instance of the discrete log problem (DLP) over the field Fp^k.”. Usually k is as big as the modulus. Bot for some curves (especially supersingular curves where k <= 6), the embedding degree is so small that it enables the MOV attack. The way we find the embedding degree k with respect to the order n of our Elliptic Curve #E(Fp) is we find the smallest integer k such that (p^k - 1) % n == 0. So let’s write a small loop for this and find k. We can even check if the curve is supersingular beforehand just to be sure.

1
2
3
4

if E.is_supersingular():
	for k in range(1, 7):
		if (p ** k - 1) % n == 0:
			print(f'MOV Attack feasible, ECDLP can be moved to finite field GF(p^{k})')

For us it’s k=2. This new field offers just 60 bits of security. So we know that we can move from one field to another. But what about that bilinear function? This is the Weil Pairing which I don’t understand and I’d propably need to watch a couple of videos and read a couple of papers before I could understand it. But the important things are that it works, and it works as such. If let’s say e() is the Weil Pairing, and P, Q are points of a curve linearly independent to one another (no x such that Q = xP), then e(P,Q) and e(npP,nqQ) = e(P,Q)^npnq. Thereforce to compute the dlog npP, we can compute u = e(P,Q) and v = e(npP,Q) for any Q. Then we have v = e(P,Q)^np = u^np. So we have effectively mapped the ECDLP to the DLP. Now the question becomes, how do we turn this into code?

Let’s start this one by one. First off, we have already found the embedding degree. And we already have our point P which belongs in Fp. After this, we need to define the new finite field Fp^k, which is just an extension of Fp. Then we need to generate a point in Fp^k Q such that P and Q are linearly independent. The way we do this is we can follow these slides right here, specifically page 6 steps 1, 2, 3. Then we create the Weil Pairings, and we just perform dlog on them. That’s the MOV attack. There are still a lot of things under the hood I didn’t touch, but still I think this is enough. Working on the above took time and was tiresome, but it was very rewarding.

Exploitation

Below is the script I wrote. It’s not 100% mine as there were some points where I was unsure what I needed to give the algorithmm, but it follows the above flow. Also it didn’t communicate with the API endpoints, so I needed to manually enter them. But once entered the flag was given to us

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45

# Define curve
a = -35
b = 98
p = 434252269029337012720086440207
Fp = GF(p)
E = EllipticCurve(Fp, [a, b])

# Find embedding degree
Gx = 16378704336066569231287640165
Gy = 377857010369614774097663166640
G = E((Gx,Gy))
n = G.order()
if E.is_supersingular():
    for k in range(1, 7):
        if (p ^ k - 1) % n == 0:
            break
Px = 0x233893fa708a11f4807bfa720
Py = 0x4e4ebd78d6bcf5559a675970a
P = E((Px,Py))

# Define new curve
Fpk = GF(p^k)
Ek = EllipticCurve(Fpk, [a, b])
Gk = Ek((Gx,Gy))
Pk = Ek((Px,Py))

# Generate new point
T = Ek.random_point()
M = T.order()
d = gcd(M, G.order())
Q = (M // d) * T

assert G.order() == Q.order()

# Define Weil Pairings
n = G.order()
u = Gk.weil_pairing(Q,n)
v = Pk.weil_pairing(Q,n)

# Calculate dlog & Find new point
nQ = v.log(u)
P = E((0x5d1a2f1544be278ff8491966, 0x4fd156cd8317c50715cf32946))
point = nQ * P
print(hex(point[0]))
print(hex(point[1]))

flag: HTB{I7_5h0075_,1t_m0v5,_wh47_15_i7?}

Crypto | Find Marher’s Secret (68 solves)

This was a challenge I had seen before, but hadn’t really solved. So it was nice that I got around it this time :eyes:.

Source Code Analysis

We are given a chall.py which imports FLAG and KEY variables from secret.py. It checks that the length of key is 27, and provides two options we can send to the server. We can:

1. Encrypt a plaintext we send with a predefined key and an IV we also provide

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

def encrypt(key, iv, pt):
    	return ARC4.new(iv + key).encrypt(pt).hex()
...
if response['option'] == 'encrypt':
	iv = bytes.fromhex(response['iv'])
	pt = bytes.fromhex(response['pt'])
	ct = encrypt(key, iv, pt)
	payload = {'response': 'success',
		   'pt': response['pt'], 'ct': ct}
	payload = json.dumps(payload)
	req.sendall(payload.encode())

2. We can try and claim the flag by providing our key and comparing it to the one used by the server

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

elif response['option'] == 'claim':
	answer = bytes.fromhex(response['key'])
	if hashlib.sha256(answer).hexdigest() == hashlib.sha256(key).hexdigest():
	    payload = {'response': 'success', 'flag': FLAG}
	    payload = json.dumps(payload)
	    req.sendall(payload.encode())
	else:
	    payload = {'response': 'fail',
		       'message': 'Better luck next time.'}
	    payload = json.dumps(payload)
	    req.sendall(payload.encode())

So the only way to get the flag is to pass that check. To pass that check the only way it by finding the key the server uses. So how do we do that? To answer this, we need to go back to our first option and think what might be interesting there? And the most interesting thing seems to be the usage of something called ARC4 :eyes:.

RC4

A quick google search will land us on the wikipedia page. As it says, RC4 is a stream cipher that although it’s simple and fast, a lot of vulnerabilities have been found for it. I’m not going to explain how RC4 works, if you want to know consult the wiki page. But here’s the general gist of it.

As with every stream cipher it generates a keystream which is then xored with the plaintext to produce the ciphertext. The algorithm is split into two parts, the Key Scheduling Algorithm (KSA), which initializes the SBOX (the state of the cipher), and the Pseudo-Random Generation Algorithm (PRGA) which generates the keystream (and also modifies the state). Let’s go look at the security vulnerabilities it has 👀

Going through them, we find the Fluhrer, Mantin and Shamir attack which says “If the nonce and long-term key are simply concatenated to generate the RC4 key, this long-term key can be discovered by analysing a large number of messages encrypted with this key.”. This looks more promising, so let’s look a bit more into it. The attack states that if the attacker knows the first m bytes of the key and the first byte of the keystream, he can derive the (m + 1)th byte due to a weakness in the PRNG. And we control the IV which is the first bytes of the key. Even though we don’t have the first byte of the keystream, we can perform three rounds of ksa() to initialize the SBOX.

The attack will start with 3 bytes in the IV, with it being in the form (a + 3, n − 1, x). a is the key index equal to 0 at first, element value space n equal to 256 (from 8 bits), and x iterates from 0 to 255 for every mth byte. After we initialize the SBOX, we can derive the fourth key byte (aka the first) using the keystream output O by computing (O - j - S[i]) mod n = K[i]. We get a keystream for every value, and the character that appears the most out of all 255 inputs is most probably our key byte. We do this for the key length. That’s why we get the key length to be 27, to know for how long we will run the attack.

Exploitation

Personally I found a ready script for the attack. All I had to do is replace the encryption oracle with a function that sends an encryption request to the server. Generally look at this repo to either get a ready solver or to read a bit more on the attack to write your own solver.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47

from collections import Counter
from pwn import *
import json


def encrypt_oracle(iv, pt):
    io.recvuntil(b'> ')
    payload = json.dumps({"option": "encrypt", "iv": iv.hex(), "pt": pt})
    io.sendline(payload)
    resp = json.loads(io.recvline().rstrip())
    ct = bytes.fromhex(resp['ct'])
    return ct

def possible_key_bit(key, c):
    s = [i for i in range(256)]
    j = 0
    for i in range(len(key)):
        j = (j + s[i] + key[i]) % 256
        tmp = s[i]
        s[i] = s[j]
        s[j] = tmp

    return (c[0] - j - s[len(key)]) % 256


def attack(key_len):
    key = bytearray([3, 255, 0])
    for a in range(key_len):
        key[0] = a + 3
        possible = Counter()
        for x in range(256):
            key[2] = x
            c = encrypt_oracle(key[:3], b"\x00".hex())
            possible[possible_key_bit(key, c)] += 1
        key.append(possible.most_common(1)[0][0])
    return key[3:]


ip = '138.68.183.64'
port = 31532

io = remote(ip, port)
# key = '1fec0787bd1a52ade63a379a203c2be92b981eb117dac4034ecce0'
key = attack(27)
io.recvuntil(b'> ')
io.sendline(json.dumps({"option": "claim", "key": key.hex()}))
print(io.recvline())

flag: HTB{f1uhr3r_m4n71n_p1u5_5h4m1r_15_4_cl4ss1c_0n3!!!}

Reference

• https://crypto.stackexchange.com/questions/37302/elliptic-curve-and-embedding-degree
• https://crypto.stanford.edu/pbc/notes/elliptic/movattack.html
• https://crypto.stackexchange.com/questions/1871/how-does-the-mov-attack-work
• https://people.cs.nctu.edu.tw/~rjchen/ECC2009/19_MOVattack.pdf
• https://sectt.github.io/writeups/Volga20/crypto_keygreed/README
• https://math.stackexchange.com/questions/824123/what-is-an-embedding-degree-of-elliptic-curve