1 of 5

Crypto

Common Mistake

Common Mod, DIfferent e

In this challenge, we are given two sets of $N$ , $e$ and $c$ .

{'n': '0xa96e6f96f6aedd5f9f6a169229f11b6fab589bf6361c5268f8217b7fad96708cfbee7857573ac606d7569b44b02afcfcfdd93c21838af933366de22a6116a2a3dee1c0015457c4935991d97014804d3d3e0d2be03ad42f675f20f41ea2afbb70c0e2a79b49789131c2f28fe8214b4506db353a9a8093dc7779ec847c2bea690e653d388e2faff459e24738cd3659d9ede795e0d1f8821fd5b49224cb47ae66f9ae3c58fa66db5ea9f73d7b741939048a242e91224f98daf0641e8a8ff19b58fb8c49b1a5abb059f44249dfd611515115a144cc7c2ca29357af46a9dc1800ae9330778ff1b7a8e45321147453cf17ef3a2111ad33bfeba2b62a047fa6a7af0eef', 'e': '0x10001', 'ct': '0x55cfe232610aa54dffcfb346117f0a38c77a33a2c67addf7a0368c93ec5c3e1baec9d3fe35a123960edc2cbdc238f332507b044d5dee1110f49311efc55a2efd3cf041bfb27130c2266e8dc61e5b99f275665823f584bc6139be4c153cdcf153bf4247fb3f57283a53e8733f982d790a74e99a5b10429012bc865296f0d4f408f65ee02cf41879543460ffc79e84615cc2515ce9ba20fe5992b427e0bbec6681911a9e6c6bbc3ca36c9eb8923ef333fb7e02e82c7bfb65b80710d78372a55432a1442d75cad5b562209bed4f85245f0157a09ce10718bbcef2b294dffb3f00a5a804ed7ba4fb680eea86e366e4f0b0a6d804e61a3b9d57afb92ecb147a769874'}
{'n': '0xa96e6f96f6aedd5f9f6a169229f11b6fab589bf6361c5268f8217b7fad96708cfbee7857573ac606d7569b44b02afcfcfdd93c21838af933366de22a6116a2a3dee1c0015457c4935991d97014804d3d3e0d2be03ad42f675f20f41ea2afbb70c0e2a79b49789131c2f28fe8214b4506db353a9a8093dc7779ec847c2bea690e653d388e2faff459e24738cd3659d9ede795e0d1f8821fd5b49224cb47ae66f9ae3c58fa66db5ea9f73d7b741939048a242e91224f98daf0641e8a8ff19b58fb8c49b1a5abb059f44249dfd611515115a144cc7c2ca29357af46a9dc1800ae9330778ff1b7a8e45321147453cf17ef3a2111ad33bfeba2b62a047fa6a7af0eef', 'e': '0x23', 'ct': '0x79834ce329453d3c4af06789e9dd654e43c16a85d8ba0dfa443aefe1ab4912a12a43b44f58f0b617662a459915e0c92a2429868a6b1d7aaaba500254c7eceba0a2df7144863f1889fab44122c9f355b74e3f357d17f0e693f261c0b9cefd07ca3d1b36563a8a8c985e211f9954ce07d4f75db40ce96feb6c91211a9ff9c0a21cad6c5090acf48bfd88042ad3c243850ad3afd6c33dd343c793c0fa2f98b4eabea399409c1966013a884368fc92310ebcb3be81d3702b936e7e883eeb94c2ebb0f9e5e6d3978c1f1f9c5a10e23a9d3252daac87f9bb748c961d3d361cc7dacb9da38ab8f2a1595d7a2eba5dce5abee659ad91a15b553d6e32d8118d1123859208'}

The plaintext encrypted to give $c$ is the same, and we can observe that the choice of $N$ is also the same, meaning the only difference is in the choice of $e$ . Here we can use some cool maffs with $e_1$ and $e_2$ to retrieve the original plaintext $m$ .

Firstly, if the greatest common divisor of $e_1$ and $e_2$ is $1$ , then there exists $a$ and $b$ such that

ae_1 + be_2 = 1

To calculate this, we can use the Extended Euclidean Algorithm. But why is this helpful?

Well if we know that $c_1 \equiv m^{e_1} \mod N$ and $c_2 \equiv m^{e_2} \mod N$ and we know $a,b$ such that $ae_1 + be_2 = 1$ , we can then use this to calculate $m$ like this:

c_1^a \cdot c_2^b = (m^{e_1})^a \cdot (m^{e_2})^b = m^{ae_1} \cdot m^{be_2} = m^{ae_1+be_2} = m^1 = m

In practise $b$ is likely to be negative, and in modular arithmetic we use negative powers using the Modular Multiplicative Inverse. Luckily, Sage can do this for us by default, so we can do even less steps:

from Crypto.Util.number import long_to_bytes

n = 0xa96e6f96f6aedd5f9f6a169229f11b6fab589bf6361c5268f8217b7fad96708cfbee7857573ac606d7569b44b02afcfcfdd93c21838af933366de22a6116a2a3dee1c0015457c4935991d97014804d3d3e0d2be03ad42f675f20f41ea2afbb70c0e2a79b49789131c2f28fe8214b4506db353a9a8093dc7779ec847c2bea690e653d388e2faff459e24738cd3659d9ede795e0d1f8821fd5b49224cb47ae66f9ae3c58fa66db5ea9f73d7b741939048a242e91224f98daf0641e8a8ff19b58fb8c49b1a5abb059f44249dfd611515115a144cc7c2ca29357af46a9dc1800ae9330778ff1b7a8e45321147453cf17ef3a2111ad33bfeba2b62a047fa6a7af0eef
e1 = 0x10001
e2 = 0x23
c1 = Mod(0x55cfe232610aa54dffcfb346117f0a38c77a33a2c67addf7a0368c93ec5c3e1baec9d3fe35a123960edc2cbdc238f332507b044d5dee1110f49311efc55a2efd3cf041bfb27130c2266e8dc61e5b99f275665823f584bc6139be4c153cdcf153bf4247fb3f57283a53e8733f982d790a74e99a5b10429012bc865296f0d4f408f65ee02cf41879543460ffc79e84615cc2515ce9ba20fe5992b427e0bbec6681911a9e6c6bbc3ca36c9eb8923ef333fb7e02e82c7bfb65b80710d78372a55432a1442d75cad5b562209bed4f85245f0157a09ce10718bbcef2b294dffb3f00a5a804ed7ba4fb680eea86e366e4f0b0a6d804e61a3b9d57afb92ecb147a769874, n)
c2 = Mod(0x79834ce329453d3c4af06789e9dd654e43c16a85d8ba0dfa443aefe1ab4912a12a43b44f58f0b617662a459915e0c92a2429868a6b1d7aaaba500254c7eceba0a2df7144863f1889fab44122c9f355b74e3f357d17f0e693f261c0b9cefd07ca3d1b36563a8a8c985e211f9954ce07d4f75db40ce96feb6c91211a9ff9c0a21cad6c5090acf48bfd88042ad3c243850ad3afd6c33dd343c793c0fa2f98b4eabea399409c1966013a884368fc92310ebcb3be81d3702b936e7e883eeb94c2ebb0f9e5e6d3978c1f1f9c5a10e23a9d3252daac87f9bb748c961d3d361cc7dacb9da38ab8f2a1595d7a2eba5dce5abee659ad91a15b553d6e32d8118d1123859208, n)

d, a, b = xgcd(e1, e2)        # calculate a and b

m = c1^a * c2^b
print(long_to_bytes(m))

And we get the flag as HTB{c0mm0n_m0d_4774ck_15_4n07h3r_cl4ss1c}.

Missing Reindeer

Cube Root Attack

In this challenge, we get a message.eml file containing an email:

Hello Mr Jingles,

We got the reindeer as you requested. There is a problem though. Its nose is so red and bright and makes it very hard to hide him anywhere near north pole. We have moved to a secret location far away. I have encrypted this information with your public key in case you know who is watching.

Applications such as Outlook block downloading the file due to it's "malicious nature", but we can open the .eml file in VS Code easily and extract two things:

Firstly, there is a secret.enc file with base64-encoded ciphertext:

Ci95oTkIL85VWrJLVhns1O2vyBeCd0weKp9o3dSY7hQl7CyiIB/D3HaXQ619k0+4FxkVEksPL6j3wLp8HMJAPxeA321RZexR9qwswQv2S6xQ3QFJi6sgvxkN0YnXtLKRYHQ3te1Nzo53gDnbvuR6zWV8fdlOcBoHtKXlVlsqODku2GvkTQ/06x8zOAWgQCKj78V2mkPiSSXf2/qfDp+FEalbOJlILsZMe3NdgjvohpJHN3O5hLfBPdod2v6iSeNxl7eVcpNtwjkhjzUx35SScJDzKuvAv+6DupMrVSLUfcWyvYUyd/l4v01w+8wvPH9l

Secondly, there is a pubkey.der file containing an RSA public key:

Analysing the Public Key

from Crypto.PublicKey import RSA

with open('pubkey.pem') as f:
    key = RSA.importKey(f.read())

print(key.n)
print(key.e)

Recovering c

We'll use the gmpy2 iroot() function to calculate the cube root:

from Crypto.Util.number import bytes_to_long, long_to_bytes
from base64 import b64decode
from gmpy2 import iroot

c = b64decode(b'Ci95oTkIL85VWrJLVhns1O2vyBeCd0weKp9o3dSY7hQl7CyiIB/D3HaXQ619k0+4FxkVEksPL6j3wLp8HMJAPxeA321RZexR9qwswQv2S6xQ3QFJi6sgvxkN0YnXtLKRYHQ3te1Nzo53gDnbvuR6zWV8fdlOcBoHtKXlVlsqODku2GvkTQ/06x8zOAWgQCKj78V2mkPiSSXf2/qfDp+FEalbOJlILsZMe3NdgjvohpJHN3O5hLfBPdod2v6iSeNxl7eVcpNtwjkhjzUx35SScJDzKuvAv+6DupMrVSLUfcWyvYUyd/l4v01w+8wvPH9l')
c = bytes_to_long(c)

m = iroot(c, 3)
print(long_to_bytes(m[0]))

And bingo bango, we get the flag as HTB{w34k_3xp0n3n7_ffc896}.

Xmas Spirit

We get given challenge.py and encrypted.bin. Analysing challenge.py:

import random
from math import gcd

def encrypt(dt):
	mod = 256
	while True:
		a = random.randint(1, mod)
		if gcd(a, mod) == 1:
			break
	b = random.randint(1, mod)

	res = b''
	for byte in dt:
		enc = (a * byte + b) % mod
		res += bytes([enc])
	return res


dt = open('letter.pdf', 'rb').read()

res = encrypt(dt)

f = open('encrypted.bin', 'wb')
f.write(res)
f.close()

It calculates two random values, $a$ and $b$ . For every byte $k$ in the plaintext file, it then calculates

ak + b \mod 256

And appends the result of that as the encrypted character in encrypted.bin.

Analysis

The plaintext file appears to be letter.pdf, and using this we can work out the values of $a$ and $b$ because we know the first 4 bytes of every PDF file are %PDF. We can extract the first two bytes of encrypted.bin and compare to the expected two bytes:

with open('encrypted.bin', 'rb') as f:
    res = f.read()

print(res[0])
print(res[1])
print(ord('%'))
print(ord('P'))

Gives us

So we can form two equations here using this information:

a \cdot 37 + b \equiv 13 \mod 256 \\ a \cdot 80 + b \equiv 112 \mod 256

We subtract (2) from (1) to get that

43a \equiv 99 \mod 256

And we can multiply both sides by the modular multiplicative inverse of 43, i.e. $43^{-1} \mod 256$ , which is $131$ , to get that

a \equiv 99 \cdot 131 \equiv 169 \mod 256

And then we can calculate $b$ :

b \equiv 13 - 169 * 37 \equiv 160 \mod 256

Solution

So now we have the values for $a$ and $b$ , it's simply a matter of going byte-by-byte and reversing it. I created a simple Sage script to do this with me, and it took a bit of time to run but eventually got the flag.

with open('encrypted.bin', 'rb') as f:
    res = f.read()


final = b''


R = IntegerModRing(256)

for char in res:
    b = bytes([ (R(char) - R(160)) / R(169) ])
    print(b.decode('latin-1'), end='')
    final += b

with open('answer.pdf', 'wb') as f:
    f.write(final)

And the resulting PDF has the flag HTB{4ff1n3_c1ph3r_15_51mpl3_m47h5} within.

Meet Me Halfway

Meet-in-the-middle attack on AES

We are given challenge.py, which does the following:

Creates two keys
- Key1 is cyb3rXm45!@# + 4 random bytes from 0123456789abcdef
- Key2 is 4 random bytes from 0123456789abcdef + cyb3rXm45!@#
Encrypts the flag with Key1 using AES-ECB
Encrypts the encrypted flag with Key2 using AES-ECB

We can use a meet-in-the-middle attack to retreive both keys. The logic here is simple. Firstly, there are 16 possible characters for each of the 4 random bytes, which is easily bruteforceable ( $16^4$ ).

We can also encrypt a given input and get the result - I choose to send 12345678 as the hex-encoded plaintext and receive . For these keys, the encrypted flag is given as:

43badc9cfb6198e97e5c0085eba941043982169877c2ec51995b5527d32244ebf3af4453e73408786a9eb39cd7fbb731afd940617e7ad1484ac017a7c0c3798cdb4a96ed96e816cf2a09fd4b39715064d0bba8bbf37e5d713f0af6a850985644

The Attack

Now we have a known plaintext and ciphertext, we can use both one after the other and bruteforce possible keys. Note that the encryption looks like this:

We do not know what the intermediate value x is, but we can use brute force to calculate it by

Looping through all possibilities for key1 and saving the encrypted version of 12345678
Looping through all possibilities for key2 and saving the decryption of 449e2eb...
Finding the intersection between the encryption with key1 and the decryption with key2

Once we find this intersection, we can use that to work back and calculate key1 and key2, which we can then utilise to decrypt the flag.

Solve Script

from itertools import permutations

from Crypto.Cipher import AES
from Crypto.Util.Padding import pad


key_start = b'cyb3rXm45!@#'
alphabet = b'0123456789abcdef'

enc_flag = bytes.fromhex('43badc9cfb6198e97e5c0085eba941043982169877c2ec51995b5527d32244ebf3af4453e73408786a9eb39cd7fbb731afd940617e7ad1484ac017a7c0c3798cdb4a96ed96e816cf2a09fd4b39715064d0bba8bbf37e5d713f0af6a850985644')

known_text = pad(bytes.fromhex("12345678"), 16)
known_ciphertext = bytes.fromhex('449e2eb3a7f793184ef41a8042739307')

# brute all encryptions
encryption_table = {}           # key : value -> encryption result : key

for key in permutations(alphabet, 4):
    key = key_start + bytes(key)
    cipher = AES.new(key, AES.MODE_ECB)
    encrypted_custom = cipher.encrypt(known_text)
    encryption_table[encrypted_custom] = key


# brute all decryptions
decryption_table = {}           # key : value -> decryption result : key

for key in permutations(alphabet, 4):
    key = bytes(key) + key_start
    cipher = AES.new(key, AES.MODE_ECB)
    decrypted_custom = cipher.decrypt(known_ciphertext)
    decryption_table[decrypted_custom] = key


# find the intersection between the keys of decryption_table and encryption_table
# if there is an intersection, we can cross-reference the AES key we used
encryption_table_set = set(encryption_table.keys())
decryption_table_set = set(decryption_table.keys())

intersection = encryption_table_set.intersection(decryption_table_set).pop()
encryption_key = encryption_table[intersection]     # set the encryption key now we know which it is
decryption_key = decryption_table[intersection]     # set the decryption key now we know which it is

# now decrypt flag_enc twice
cipher1 = AES.new(encryption_key, AES.MODE_ECB)
cipher2 = AES.new(decryption_key, AES.MODE_ECB)

flag = cipher2.decrypt(enc_flag)
flag = cipher1.decrypt(flag).decode().strip()

print(flag)

And we get the flag as HTB{m337_m3_1n_7h3_m1ddl3_0f_3ncryp710n}!

Missing Reindeer

Cube Root Attack

In this challenge, we get a message.eml file containing an email:

Hello Mr Jingles,

We got the reindeer as you requested. There is a problem though. Its nose is so red and bright and makes it very hard to hide him anywhere near north pole. We have moved to a secret location far away. I have encrypted this information with your public key in case you know who is watching.

Applications such as Outlook block downloading the file due to it's "malicious nature", but we can open the .eml file in VS Code easily and extract two things:

Firstly, there is a secret.enc file with base64-encoded ciphertext:

Ci95oTkIL85VWrJLVhns1O2vyBeCd0weKp9o3dSY7hQl7CyiIB/D3HaXQ619k0+4FxkVEksPL6j3wLp8HMJAPxeA321RZexR9qwswQv2S6xQ3QFJi6sgvxkN0YnXtLKRYHQ3te1Nzo53gDnbvuR6zWV8fdlOcBoHtKXlVlsqODku2GvkTQ/06x8zOAWgQCKj78V2mkPiSSXf2/qfDp+FEalbOJlILsZMe3NdgjvohpJHN3O5hLfBPdod2v6iSeNxl7eVcpNtwjkhjzUx35SScJDzKuvAv+6DupMrVSLUfcWyvYUyd/l4v01w+8wvPH9l

Secondly, there is a pubkey.der file containing an RSA public key:

Analysing the Public Key

We can easily import the public key in Python and read the values for $N$ and $e$ using the Pycryptodome:

from Crypto.PublicKey import RSA

with open('pubkey.pem') as f:
    key = RSA.importKey(f.read())

print(key.n)
print(key.e)

We can throw $N$ into FactorDB to see if the factors are known, but they are not. The more notable observation is that $e=3$ , which allows us to perform a cube root attack on the ciphertext.

The logic here is simple: because the message $m$ is quite short and the public modulus $N$ is quite large, a small value of $e$ such as $3$ may make it such that $m^e < N$ . This makes the modulus ineffective as $m^e = m^e \mod N$ and we can simply take the $e$ th root of the ciphertext to recover the plaintext.

Recovering c

We'll use the gmpy2 iroot() function to calculate the cube root:

from Crypto.Util.number import bytes_to_long, long_to_bytes
from base64 import b64decode
from gmpy2 import iroot

c = b64decode(b'Ci95oTkIL85VWrJLVhns1O2vyBeCd0weKp9o3dSY7hQl7CyiIB/D3HaXQ619k0+4FxkVEksPL6j3wLp8HMJAPxeA321RZexR9qwswQv2S6xQ3QFJi6sgvxkN0YnXtLKRYHQ3te1Nzo53gDnbvuR6zWV8fdlOcBoHtKXlVlsqODku2GvkTQ/06x8zOAWgQCKj78V2mkPiSSXf2/qfDp+FEalbOJlILsZMe3NdgjvohpJHN3O5hLfBPdod2v6iSeNxl7eVcpNtwjkhjzUx35SScJDzKuvAv+6DupMrVSLUfcWyvYUyd/l4v01w+8wvPH9l')
c = bytes_to_long(c)

m = iroot(c, 3)
print(long_to_bytes(m[0]))

And bingo bango, we get the flag as HTB{w34k_3xp0n3n7_ffc896}.

Common Mistake

Common Mod, DIfferent e

In this challenge, we are given two sets of $N$ , $e$ and $c$ .

{'n': '0xa96e6f96f6aedd5f9f6a169229f11b6fab589bf6361c5268f8217b7fad96708cfbee7857573ac606d7569b44b02afcfcfdd93c21838af933366de22a6116a2a3dee1c0015457c4935991d97014804d3d3e0d2be03ad42f675f20f41ea2afbb70c0e2a79b49789131c2f28fe8214b4506db353a9a8093dc7779ec847c2bea690e653d388e2faff459e24738cd3659d9ede795e0d1f8821fd5b49224cb47ae66f9ae3c58fa66db5ea9f73d7b741939048a242e91224f98daf0641e8a8ff19b58fb8c49b1a5abb059f44249dfd611515115a144cc7c2ca29357af46a9dc1800ae9330778ff1b7a8e45321147453cf17ef3a2111ad33bfeba2b62a047fa6a7af0eef', 'e': '0x10001', 'ct': '0x55cfe232610aa54dffcfb346117f0a38c77a33a2c67addf7a0368c93ec5c3e1baec9d3fe35a123960edc2cbdc238f332507b044d5dee1110f49311efc55a2efd3cf041bfb27130c2266e8dc61e5b99f275665823f584bc6139be4c153cdcf153bf4247fb3f57283a53e8733f982d790a74e99a5b10429012bc865296f0d4f408f65ee02cf41879543460ffc79e84615cc2515ce9ba20fe5992b427e0bbec6681911a9e6c6bbc3ca36c9eb8923ef333fb7e02e82c7bfb65b80710d78372a55432a1442d75cad5b562209bed4f85245f0157a09ce10718bbcef2b294dffb3f00a5a804ed7ba4fb680eea86e366e4f0b0a6d804e61a3b9d57afb92ecb147a769874'}
{'n': '0xa96e6f96f6aedd5f9f6a169229f11b6fab589bf6361c5268f8217b7fad96708cfbee7857573ac606d7569b44b02afcfcfdd93c21838af933366de22a6116a2a3dee1c0015457c4935991d97014804d3d3e0d2be03ad42f675f20f41ea2afbb70c0e2a79b49789131c2f28fe8214b4506db353a9a8093dc7779ec847c2bea690e653d388e2faff459e24738cd3659d9ede795e0d1f8821fd5b49224cb47ae66f9ae3c58fa66db5ea9f73d7b741939048a242e91224f98daf0641e8a8ff19b58fb8c49b1a5abb059f44249dfd611515115a144cc7c2ca29357af46a9dc1800ae9330778ff1b7a8e45321147453cf17ef3a2111ad33bfeba2b62a047fa6a7af0eef', 'e': '0x23', 'ct': '0x79834ce329453d3c4af06789e9dd654e43c16a85d8ba0dfa443aefe1ab4912a12a43b44f58f0b617662a459915e0c92a2429868a6b1d7aaaba500254c7eceba0a2df7144863f1889fab44122c9f355b74e3f357d17f0e693f261c0b9cefd07ca3d1b36563a8a8c985e211f9954ce07d4f75db40ce96feb6c91211a9ff9c0a21cad6c5090acf48bfd88042ad3c243850ad3afd6c33dd343c793c0fa2f98b4eabea399409c1966013a884368fc92310ebcb3be81d3702b936e7e883eeb94c2ebb0f9e5e6d3978c1f1f9c5a10e23a9d3252daac87f9bb748c961d3d361cc7dacb9da38ab8f2a1595d7a2eba5dce5abee659ad91a15b553d6e32d8118d1123859208'}

Firstly, if the greatest common divisor of $e_1$ and $e_2$ is $1$ , then there exists $a$ and $b$ such that

ae_1 + be_2 = 1

To calculate this, we can use the Extended Euclidean Algorithm. But why is this helpful?

Well if we know that $c_1 \equiv m^{e_1} \mod N$ and $c_2 \equiv m^{e_2} \mod N$ and we know $a,b$ such that $ae_1 + be_2 = 1$ , we can then use this to calculate $m$ like this:

c_1^a \cdot c_2^b = (m^{e_1})^a \cdot (m^{e_2})^b = m^{ae_1} \cdot m^{be_2} = m^{ae_1+be_2} = m^1 = m

from Crypto.Util.number import long_to_bytes

n = 0xa96e6f96f6aedd5f9f6a169229f11b6fab589bf6361c5268f8217b7fad96708cfbee7857573ac606d7569b44b02afcfcfdd93c21838af933366de22a6116a2a3dee1c0015457c4935991d97014804d3d3e0d2be03ad42f675f20f41ea2afbb70c0e2a79b49789131c2f28fe8214b4506db353a9a8093dc7779ec847c2bea690e653d388e2faff459e24738cd3659d9ede795e0d1f8821fd5b49224cb47ae66f9ae3c58fa66db5ea9f73d7b741939048a242e91224f98daf0641e8a8ff19b58fb8c49b1a5abb059f44249dfd611515115a144cc7c2ca29357af46a9dc1800ae9330778ff1b7a8e45321147453cf17ef3a2111ad33bfeba2b62a047fa6a7af0eef
e1 = 0x10001
e2 = 0x23
c1 = Mod(0x55cfe232610aa54dffcfb346117f0a38c77a33a2c67addf7a0368c93ec5c3e1baec9d3fe35a123960edc2cbdc238f332507b044d5dee1110f49311efc55a2efd3cf041bfb27130c2266e8dc61e5b99f275665823f584bc6139be4c153cdcf153bf4247fb3f57283a53e8733f982d790a74e99a5b10429012bc865296f0d4f408f65ee02cf41879543460ffc79e84615cc2515ce9ba20fe5992b427e0bbec6681911a9e6c6bbc3ca36c9eb8923ef333fb7e02e82c7bfb65b80710d78372a55432a1442d75cad5b562209bed4f85245f0157a09ce10718bbcef2b294dffb3f00a5a804ed7ba4fb680eea86e366e4f0b0a6d804e61a3b9d57afb92ecb147a769874, n)
c2 = Mod(0x79834ce329453d3c4af06789e9dd654e43c16a85d8ba0dfa443aefe1ab4912a12a43b44f58f0b617662a459915e0c92a2429868a6b1d7aaaba500254c7eceba0a2df7144863f1889fab44122c9f355b74e3f357d17f0e693f261c0b9cefd07ca3d1b36563a8a8c985e211f9954ce07d4f75db40ce96feb6c91211a9ff9c0a21cad6c5090acf48bfd88042ad3c243850ad3afd6c33dd343c793c0fa2f98b4eabea399409c1966013a884368fc92310ebcb3be81d3702b936e7e883eeb94c2ebb0f9e5e6d3978c1f1f9c5a10e23a9d3252daac87f9bb748c961d3d361cc7dacb9da38ab8f2a1595d7a2eba5dce5abee659ad91a15b553d6e32d8118d1123859208, n)

d, a, b = xgcd(e1, e2)        # calculate a and b

m = c1^a * c2^b
print(long_to_bytes(m))

And we get the flag as HTB{c0mm0n_m0d_4774ck_15_4n07h3r_cl4ss1c}.

Meet Me Halfway

Meet-in-the-middle attack on AES

We are given challenge.py, which does the following:

Creates two keys
- Key1 is cyb3rXm45!@# + 4 random bytes from 0123456789abcdef
- Key2 is 4 random bytes from 0123456789abcdef + cyb3rXm45!@#
Encrypts the flag with Key1 using AES-ECB
Encrypts the encrypted flag with Key2 using AES-ECB

We can also encrypt a given input and get the result - I choose to send 12345678 as the hex-encoded plaintext and receive . For these keys, the encrypted flag is given as:

43badc9cfb6198e97e5c0085eba941043982169877c2ec51995b5527d32244ebf3af4453e73408786a9eb39cd7fbb731afd940617e7ad1484ac017a7c0c3798cdb4a96ed96e816cf2a09fd4b39715064d0bba8bbf37e5d713f0af6a850985644

The Attack

Now we have a known plaintext and ciphertext, we can use both one after the other and bruteforce possible keys. Note that the encryption looks like this:

We do not know what the intermediate value x is, but we can use brute force to calculate it by

Looping through all possibilities for key1 and saving the encrypted version of 12345678
Looping through all possibilities for key2 and saving the decryption of 449e2eb...
Finding the intersection between the encryption with key1 and the decryption with key2

Once we find this intersection, we can use that to work back and calculate key1 and key2, which we can then utilise to decrypt the flag.

Solve Script

from itertools import permutations

from Crypto.Cipher import AES
from Crypto.Util.Padding import pad


key_start = b'cyb3rXm45!@#'
alphabet = b'0123456789abcdef'

enc_flag = bytes.fromhex('43badc9cfb6198e97e5c0085eba941043982169877c2ec51995b5527d32244ebf3af4453e73408786a9eb39cd7fbb731afd940617e7ad1484ac017a7c0c3798cdb4a96ed96e816cf2a09fd4b39715064d0bba8bbf37e5d713f0af6a850985644')

known_text = pad(bytes.fromhex("12345678"), 16)
known_ciphertext = bytes.fromhex('449e2eb3a7f793184ef41a8042739307')

# brute all encryptions
encryption_table = {}           # key : value -> encryption result : key

for key in permutations(alphabet, 4):
    key = key_start + bytes(key)
    cipher = AES.new(key, AES.MODE_ECB)
    encrypted_custom = cipher.encrypt(known_text)
    encryption_table[encrypted_custom] = key


# brute all decryptions
decryption_table = {}           # key : value -> decryption result : key

for key in permutations(alphabet, 4):
    key = bytes(key) + key_start
    cipher = AES.new(key, AES.MODE_ECB)
    decrypted_custom = cipher.decrypt(known_ciphertext)
    decryption_table[decrypted_custom] = key


# find the intersection between the keys of decryption_table and encryption_table
# if there is an intersection, we can cross-reference the AES key we used
encryption_table_set = set(encryption_table.keys())
decryption_table_set = set(decryption_table.keys())

intersection = encryption_table_set.intersection(decryption_table_set).pop()
encryption_key = encryption_table[intersection]     # set the encryption key now we know which it is
decryption_key = decryption_table[intersection]     # set the decryption key now we know which it is

# now decrypt flag_enc twice
cipher1 = AES.new(encryption_key, AES.MODE_ECB)
cipher2 = AES.new(decryption_key, AES.MODE_ECB)

flag = cipher2.decrypt(enc_flag)
flag = cipher1.decrypt(flag).decode().strip()

print(flag)

And we get the flag as HTB{m337_m3_1n_7h3_m1ddl3_0f_3ncryp710n}!

Crypto

Common Mistake

Missing Reindeer

Contents

Analysing the Public Key

Recovering c

Xmas Spirit

Contents

Analysis

Solution

Meet Me Halfway

Contents

The Attack

Solve Script

Missing Reindeer

Contents

Analysing the Public Key

Recovering c

Common Mistake

Xmas Spirit

Contents

Analysis

Solution

Meet Me Halfway

Contents

The Attack

Solve Script