👾
Elijah's CTF Blog
  • 👋Home
  • 🇲🇾Wargames.MY CTF 2024
    • Credentials (crypto)
    • Stones (rev)
    • Rick'S Algorithm (crypto)
    • Rick'S Algorithm 2 (crypto)
    • Hohoho 3 continue (crypto)
  • 🎄Advent of CTF 2024
    • Jingle Bell ROP (pwn)
    • help (pwn)
  • Backdoor CTF 24
    • [rev] Ratatouille
  • 🇭🇰HKCERT CTF 24
    • Shellcode Runner 3 + Revenge (pwn)
    • ISH (1) (pwn)
    • Cyp.ress (rev)
    • Void (rev)
  • 🇮🇹ECSC 2024
    • ➕OffTopic (crypto)
  • 🎩Greyhats WelcomeCTF 24
    • EE2026 (misc)
  • 🚆UIUCTF 24
    • Syscalls (pwn)
    • Summarize (rev)
    • X Marked the Spot (crypto)
    • Without a Trace (crypto)
    • Determined (crypto)
    • Naptime (crypto)
    • Snore Signatures (crypto)
  • 🪼Jelly CTF 24
    • Cherry (crypto)
    • the_brewing_secrets (crypto)
  • 👨‍🦯vsCTF 24
    • Dream (crypto)
    • Cosmic Ray V3 (pwn)
  • 😎AKASEC CTF 24
    • Warmup (pwn)
    • Good_trip (pwn)
    • Sperm Rev (rev)
    • Paranoia (rev)
    • Grip (rev)
    • Risks (rev)
    • Lost (crypto)
  • 😁L3AK CTF 24
    • oorrww (pwn)
    • angry (rev)
    • Related (crypto)
    • BatBot (web-misc)
    • Matrix Magic (crypto)
  • 🥹CDDC Qualifiers 2024
    • WASM (rev)
    • crashMe (pwn)
Powered by GitBook
On this page
  1. Wargames.MY CTF 2024

Rick'S Algorithm 2 (crypto)

Last updated 4 months ago

We are given the following Python source code:

from Crypto.Util.number import *
import os
from secret import revealFlag
flag = bytes_to_long(b"wgmy{REDACTED}")

p = getStrongPrime(1024)
q = getStrongPrime(1024)
e = 0x557
n = p*q
phi = (p-1)*(q-1)
d = inverse(e,phi)

while True:
	print("Choose an option below")
	print("=======================")
	print("1. Encrypt a message")
	print("2. Decrypt a message (Disabled)")
	print("3. Print encrypted flag")
	print("4. Print flag")
	print("5. Exit")

	try:
		option = input("Enter option: ")
		if option == "1":
			m = bytes_to_long(input("Enter message to encrypt: ").encode())
			print(f"Encrypted message: {pow(m,e,n)}")
		elif option == "2":
			print(f"Disabled decryption to prevent flag leaking!")
		elif option == "3":
			print(f"Encrypted flag: {pow(flag,e,n)}")
		elif option == "4":
			print("Revealing flag: ")
			revealFlag()
		elif option == "5":
			print("Bye!!")
			break
	except Exception as e:
		print("HACKER ALERT!!")

The code does not explicitly give us n. However, since we have an encryption oracle, we can find n by encrypting multiple messages m and getting their ciphertexts c, then getting the GCD of all c-m values.

Other than this there doesn't seem to be any problem with the code.

Each time we connect to the server it uses a different modulus n, and as such although the flag remains the same, flage(mod n)flag^e(mod \space n)flage(mod n) will be different. Since we can obtain multiple distinct (ciphertext, modulus) values with each server connection, we can use Hastad's broadcast attack to retrieve the flag.

import os
import sys
from math import gcd
from Crypto.Random.random import getrandbits

path = os.path.dirname(os.path.dirname(os.path.dirname(os.path.realpath(os.path.abspath(__file__)))))
if sys.path[1] != path:
    sys.path.insert(1, path)

from attacks.rsa import low_exponent
from shared.crt import fast_crt


def attack(N, e, c):
    """
    Recovers the plaintext from e ciphertexts, encrypted using different moduli and the same public exponent.
    :param N: the moduli
    :param e: the public exponent
    :param c: the ciphertexts
    :return: the plaintext
    """
    assert e == len(N) == len(c), "The amount of ciphertexts should be equal to e."

    for i in range(len(N)):
        for j in range(len(N)):
            if i != j and gcd(N[i], N[j]) != 1:
                raise ValueError(f"Modulus {i} and {j} share factors, Hastad's attack is impossible.")

    c, _ = fast_crt(c, N)
    return low_exponent.attack(e, c)

from pwn import *
from Crypto.Util.number import *

e = 0x557


ciphertexts = []
modulus = []

context.log_level = 'debug'

plaintexts = [b"aaaaaaaaaaaaaaaaaaa", b"bbbbbbbbbbbbbbbbbbbbbbbbbbbb", b"ccccccccccccccccccccccccccc", b"dddddddddddddddddddddddddd", b"eeeeeeeeeeeeeeeeeeeeeeeeeeeeee", b"fffffffffffffffffffffffffffffff", b"ggggggggggggggggggggggggggggg", b"hhhhhhhhhhhhhhhhhhhhhhhhhhhhh", b"iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii", b"jjjjjjjjjjjjjjjjjjjjjjjjjj", b"kkkkkkkkkkkkkkkkkkkkkkkkkkkk", b"lllllllllllllllllllllllllllll", b"mmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmm", b"nnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnn", b"oooooooooooooooooooooooooooooooooo", b"ppppppppppppppppppppppppppppp"]

for i in range(0x557):
    print(f"i: {i}")
    # p = process(["python3","server.py"])
    p = remote("43.217.80.203",34955)
    diffs = []
    for j in range(len(plaintexts)):
        p.sendlineafter(b"Enter option: ", b"1")
        p.sendlineafter(b"encrypt: ", plaintexts[j])
        p.recvuntil(b"message: ")
        c1 = int(p.recvline()[:-1].decode())
        diffs.append(c1 - pow(bytes_to_long(plaintexts[j]), e))

    n = int(gcd(diffs[0], diffs[1]))
    for k in range(2, len(diffs)):
        n = int(gcd(n, diffs[k]))
    modulus.append(n)
    p.sendlineafter(b"Enter option: ", b"3")
    p.recvuntil(b"Encrypted flag: ")
    ct = int(p.recvline()[:-1].decode())
    ciphertexts.append(ct)
    p.close()

print(f"c: {ciphertexts}")
print(f"n: {modulus}")

out = open("output.txt", "w")
out.write(f" c: {ciphertexts}")
out.write(f" n: {modulus}")
print(attack(modulus, 0x557, ciphertexts)) # wgmy{1ee240ab7db21db1268c3e1e44fee9a0}

Below is my solve script. I did it within the hastad_attack.py file from .

🇲🇾
crypto-attacks