Rick'S Algorithm 2 (crypto)

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, $flag^e(mod \space 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.

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

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}