HackVent 2023 - [HV23.17] Lost Key
Difficulty: Hard
Categories: Cryptography, Forensics
Author: darkstar
After losing another important key, the administrator sent me a picture of a key as a replacement. But what should I do with it?
We get a large flag.enc and that picture of a key. Upon running exiftool on the image, we can see the following:
Comment : Key Info: 0x10001
So we’re probably dealing with RSA here, 0x10001 is the most common used public exponent e, probably more common known in decimal: 65537.
When lookin closely at the picture, we notice something:
Looks like we have two suspicious pixels, right at the end of 50% of the image. Maybe the two sections represent p and q? That would also explain why the last pixel is different, to change the numbers to be prime.
Let’s convert the pixels to integers:
#!/usr/bin/python3
from PIL import Image
import sys
sys.set_int_max_str_digits(0)
img = Image.open("stego.png")
width, height = img.size
p1 = img.getpixel((width-1, height-1))
p2 = img.getpixel((width-1, 20))
print(f"p1: {p1}",hex(p1[0]),hex(p1[1]),hex(p1[2]))
print(f"p2: {p2}",hex(p2[0]),hex(p2[1]),hex(p2[2]))
p_image = Image.new('RGB', (width, 21))
q_image = Image.new('RGB', (width, 21))
key_p = key_q =0
for i in range(0, width):
for j in range(0, 21):
p = img.getpixel((i, j))
q_image.putpixel((i, j), p)
for i in range(0, width):
for j in range(21, height):
p = img.getpixel((i, j))
p_image.putpixel((i, j-21), p)
bytes_q = q_image.tobytes()
bytes_p = p_image.tobytes()
int_q = int.from_bytes(bytes_q, 'big')
int_p = int.from_bytes(bytes_p, 'big')
print(f"{int_p=} {int_q=}")
We get two very large numbers. Now for sagemath to do the RSA decryption for us:
import sys
sys.set_int_max_str_digits(0)
with open("flag.enc", "rb") as f:
flag_enc=int(f.read().hex(), 16)
p = <very long p>
q = <very long q>
n = int_p * int_q
e=65537
r = (int_p-1)*(int_q-1)
bezout = xgcd(e, r)
d = Integer(mod(bezout[1], r));
flag_dec = power_mod(flag_enc, d, n)
output = int(flag_dec.hex(), 16).to_bytes(
length=len(flag_hex)
)
with open("out", "wb") as f:
f.write(output)
We can then look at the output:
$ file out
out: PNG image data, 74 x 74, 8-bit/color RGBA, non-interlaced
When scanning the QR code, we get the flag:
HV23{Thanks_for_finding_my_key}