pingCTF 2025 - crypto challenges | MindCrafters CTF Team

easy rsa

flag: `ping{R5A_1s_n0t_th4t_hard!}`

We are given the source code:

from Crypto.Util.number import getPrime, bytes_to_long
import os

p = getPrime(1024)
q = getPrime(1024)
n = p*q
e = getPrime(512)
d = pow(e, -1, (p-1)*(q-1))

flag = bytes_to_long(bytes(os.environ["FLAG"], "utf-8"))
encrypted_flag = pow(flag, e, n)

print("Flag ciphertext: ", encrypted_flag)

for i in range(4):
    ciphertext = int(input("Enter ciphertext you want to decrypt: "))
    if ciphertext <= 0 or ciphertext >= n:
        print("0 < ciphertext < n is required!")
        break
    if ciphertext == encrypted_flag:
        print("You serious?")
        break
    print("Your decrypted text: ", pow(ciphertext, d, n))
print("Bye!")

We can't simply ask an oracle to decrypt encrypted_flag. Since provided ciphertext can't be greater than n (which we don't know anyway), we are not able to bypass it by decrypting n + encrypted_flag.

If n and e were known (as they normally are in RSA) or if we had access to encrypting oracle, we could decrypt E(2) * encrypted_flag and get 2 * flag.

We will use somewhat similar method and decrypt 2 * encrypted_flag so that we can calculate flag based on the known value of D(2).

But first, we will decrypt 2, 4, 16 and use gcd() to find a small multiple of n.

from math import gcd
from Crypto.Util.number import long_to_bytes


encrypted_flag = int(input("encrypted_flag > "))


# ----------------------------------------------------------------
# RECOVER N
# ----------------------------------------------------------------


k = 2

ct1 = k
ct2 = k**2
ct3 = k**4

print(f"{ct1 = }")
print(f"{ct2 = }")
print(f"{ct3 = }")

pt1 = int(input("\npt1 > "))
pt2 = int(input("\npt2 > "))
pt3 = int(input("\npt3 > "))

d1 = pt1**2 - pt2
d2 = pt2**2 - pt3

m = gcd(d1, d2)

for i in range(100, 1, -1):
    if m % i == 0:
        m //= i

n = m


# ----------------------------------------------------------------
# RECOVER FLAG
# ----------------------------------------------------------------


ct4 = (encrypted_flag * k) % n

print(f"\n{ct4 = }")
pt4 = int(input("\npt4 > "))

k_to_d = pt1
inv = pow(k_to_d, -1, n)
flag = (pt4 * inv) % n

print(f"{long_to_bytes(flag) = }")

Lost password

flag: `ping{th4nks_f0r_r3c0v3r1ng_"my"_p4ssw0rd}`

We are given the source code:

from Crypto.Cipher import AES
from Crypto.Util.Padding import pad
from secrets import token_bytes
from binascii import hexlify
import hashlib
import os

KEY = token_bytes(32)
IV = token_bytes(16)
BLOCK_SIZE = 16

def xor(a, b):
    return bytes(x ^ y for x, y in zip(a, b))

def hash(data):
    padded = pad(data, BLOCK_SIZE)
    cipher = AES.new(KEY, AES.MODE_CBC, IV)
    h = cipher.decrypt(padded)
    out = b"\x00"*32

    for block in [h[i:i+BLOCK_SIZE] for i in range(0, len(h), BLOCK_SIZE)]:
        out = xor(out, hashlib.sha256(block).digest())
    return out


target = hash(token_bytes(32))
print(f"I have lost my password, all I got is this hash: {hexlify(target).decode('utf-8')}")
print("Can you help me recover it? I will reward you with a flag!")
while True:
    password = bytes(input("Enter password: "), "utf-8")
    hashed = hash(password)
    if target == hashed:
        print("Thank you!")
        print(f"Here is your flag: {os.environ['FLAG']}")
        break
    print("This is not my password, hashes dont match!")
    print(f"Provided password hash: {str(hexlify(hashed).decode('utf-8'))}")

The key to solving this challenge is utilizing XOR properties. XOR is equivalent to addition in GF(2). We can get any "composite hash" by XORing multiple hashes so that the corresponding bits of each hash add up to the corresponding bit in the final hash.

If we have enough hashes, we can construct a system of equations and get a list of coefficients (where 1 means that corresponding hash is chosen).

Because the hash() function uses AES-CBC decryption before each block is passed to SHA-256, changing the order of original blocks irreversibly changes the final output. We can nullify that effect by adding the same exact block at the beginning, at the end and between all other blocks. Because our input is padded, we will use b'\x10' * 16 (it is added automatically at the end by a padding function when input contains only full blocks).

from string import digits
from random import choices
from pwn import xor, remote
from sage.all import *


BLOCK_SIZE = 16
PADDING = b"\x10" * BLOCK_SIZE


# ----------------------------------------------------------------
# COLLECT HASHES FOR RANDOM PASSWORDS
# ----------------------------------------------------------------


HOST = "188.245.212.74"
PORT = 50420

conn = remote(HOST, PORT)


def get_line():
    return conn.recvline().strip().decode("utf-8")


def get_hash(payload):
    conn.recvuntil(b": ")
    conn.sendline(payload)
    get_line()
    h = get_line().split()[-1]
    return bytes.fromhex(h)


def generate_password():
    return "".join(choices(digits, k=BLOCK_SIZE)).encode("utf-8")


target_hash = bytes.fromhex(get_line().split()[-1])
head_hash = get_hash(b"")  # IV XOR D(PADDING)
tail_hash = xor(target_hash, head_hash)

dct = {}

SAMPLE_SIZE = 300

for i in range(SAMPLE_SIZE):
    print(f"{i + 1} / {SAMPLE_SIZE}")
    password = generate_password()
    payload = PADDING + password
    h = get_hash(payload)
    password_hash = xor(h, head_hash)
    dct[password] = password_hash


# ----------------------------------------------------------------
# CHOOSE SUBSET OF PASSWORDS
# ----------------------------------------------------------------


def hash_to_bits(h):
    bit_size = 256
    n = int.from_bytes(h, "big")
    b = bin(n)[2:].zfill(bit_size)
    return [int(e) for e in b]


passwords = dct.keys()
hashes = dct.values()

M_hashes = matrix(GF(2), [hash_to_bits(h) for h in hashes])
v_tail = vector(GF(2), hash_to_bits(tail_hash))

coeffs = M_hashes.solve_left(v_tail)
chosen_passwords = [p for c, p in zip(coeffs, passwords) if c != 0]

# ----------------------------------------------------------------
# COMPOSE THE CHOSEN PASSWORDS INTO A SINGLE PAYLOAD
# ----------------------------------------------------------------


payload = b"".join(PADDING + password for password in chosen_passwords)
conn.sendline(payload)
conn.interactive()

easy rsa

flag: ping{R5A_1s_n0t_th4t_hard!}

Lost password

flag: ping{th4nks_f0r_r3c0v3r1ng_"my"_p4ssw0rd}

flag: `ping{R5A_1s_n0t_th4t_hard!}`

flag: `ping{th4nks_f0r_r3c0v3r1ng_"my"_p4ssw0rd}`