**CTF Author:** ***Anakin***

**CTF WriteUp:** ***[xMrRobotx](https://twitter.com/MrRobot38159405)***

---
#### **Morphing Time**
> The all revealing Oracle may be revealing a little too much...
```python
# chal.py
#!/usr/bin/env python3
from Crypto.Util.number import getPrime
from random import randint

with open("/flag", "rb") as f:
flag = int.from_bytes(f.read().strip(), "big")

def setup():
# Get group prime + generator
p = getPrime(512)
g = 2

return g, p

def key(g, p):
# generate key info
a = randint(2, p - 1)
A = pow(g, a, p)

return a, A

def encrypt_setup(p, g, A):
def encrypt(m):
k = randint(2, p - 1)
c1 = pow(g, k, p)
c2 = pow(A, k, p)
c2 = (m * c2) % p

return c1, c2

return encrypt

def decrypt_setup(a, p):
def decrypt(c1, c2):
m = pow(c1, a, p)
m = pow(m, -1, p)
m = (c2 * m) % p

return m

return decrypt

def main():
print("[$] Welcome to Morphing Time")

g, p = 2, getPrime(512)
a = randint(2, p - 1)
A = pow(g, a, p)
decrypt = decrypt_setup(a, p)
encrypt = encrypt_setup(p, g, A)
print("[$] Public:")
print(f"[$] {g = }")
print(f"[$] {p = }")
print(f"[$] {A = }")

c1, c2 = encrypt(flag)
print("[$] Eavesdropped Message:")
print(f"[$] {c1 = }")
print(f"[$] {c2 = }")

print("[$] Give A Ciphertext (c1_, c2_) to the Oracle:")
try:
c1_ = input("[$] c1_ = ")
c1_ = int(c1_)
assert 1 < c1_ < p - 1

c2_ = input("[$] c2_ = ")
c2_ = int(c2_)
assert 1 < c2_ < p - 1
except:
print("!! You've Lost Your Chance !!")
exit(1)

print("[$] Decryption of You-Know-What:")
m = decrypt((c1 * c1_) % p, (c2 * c2_) % p)
print(f"[$] {m = }")

# !! NOTE !!
# Convert your final result to plaintext using
# long_to_bytes

exit(0)

if __name__ == "__main__":
main()

```
From the script `chal.py`, we can see that the program uses the ElGamal encryption scheme, which is a public-key cipher. The decryption operation involves computing an inverse modulo the prime number `p`. The decrypt function takes as input two numbers `c1` and `c2` and returns a message `m`. The interesting behavior here is that you can provide the oracle with an encryption of a message and the oracle will return the decrypted message multiplied by the flag.

The goal here is to use this property to your advantage to recover the flag. You can do this by sending an encryption of `1` to the oracle, which will return the decrypted flag itself.

Let's walk through the steps of how to calculate the encrypted `1`:

1. Recall the ElGamal encryption process: to encrypt a message `m`, we choose a random `k` from `[2, p-1]`, compute `c1 = g^k mod p`, `c2 = m * A^k mod p`, and the ciphertext is `(c1, c2)`.
2. To encrypt `1`, we choose `k = 1` to simplify the computation: `c1_ = g^1 mod p = g`, `c2_ = 1 * A^1 mod p = A`.
3. You can then submit `(c1_, c2_)` to the oracle, which is `(g, A)`, to get the flag.

After we obtained the integer `m`, we convert it into bytes and then decode it as a string to obtain the flag. You might need to handle padding or non-ASCII bytes in the decoded string, but those can be usually resolved by ignoring non-ASCII characters or removing the padding.

Here is an example of the final script used to retrieve the flag:
```python
from pwn import *
from Crypto.Util.number import long_to_bytes

def main():
# Connect to the server
conn = remote('morphing.chal.uiuc.tf', 1337)

# Receive initial data, extract g, p, A
conn.recvuntil(b"g = ")
g = int(conn.recvline())
conn.recvuntil(b"p = ")
p = int(conn.recvline())
conn.recvuntil(b"A = ")
A = int(conn.recvline())

# Encrypt '1'
c1_ = g
c2_ = A

# Send c1_ and c2_ to the server
conn.recvuntil(b"c1_ = ")
conn.sendline(str(c1_))
conn.recvuntil(b"c2_ = ")
conn.sendline(str(c2_))

# Get the response, which should be the decrypted flag
conn.recvuntil(b"m = ")
m = int(conn.recvline())

# Convert to bytes
flag = long_to_bytes(m)
print("Flag:", flag)

if __name__ == '__main__':
main()
```
***Flag:***
>uiuctf{h0m0m0rpi5sms_ar3_v3ry_fun!!11!!11!!}

Original writeup (https://ctf-writeups.daishosec.com/crypto/uiuctf23/morphing-time).