Attacking Elgamal Encryption
500 / variable
We got this task from the game masters at the 34c3 junior ctf:
You can reach a strange authentication system here: nc 18.104.22.168 1337 I'm sure you know what you have to do.
And we got the python source of the program running on the server.
When connecting to the service we got two options, either to provide a name and a role and get
an authentication token. Or to provide an token that contained the role
overlord and get the
flag. It was illegal to generate a token with the role
The token was the name concatenated with
# and the role, and then encrypted with
elgamal. The elgamal encryption scheme
produces two numbers when you encrypt something, and those two numbers where converted to hex
and concatinated with a
Reading the wikipedia article about elgamal we discovered we discovered that you can manipulate the cipher in order to produce another plain text. As described by wikipedia:
ElGamal encryption is unconditionally malleable, and therefore is not secure under chosen ciphertext attack. For example, given an encryption (c1 , c2) of some (possibly unknown) message m, one can easily construct a valid encryption ( c1 , 2 * c2 ) of the message 2 * m.
This means that if we manages to produce a message that when doubled decrypts to something that
ends in the charactes
#overlord we will get the flag.
#overlord is 0x236f7665726c6f7264 when converted to hex so if we send in the byte
values that are half that as role we will get something that we can double and send back and get
We wrote a small python tool to do this for us:
import socket import binascii name = "a" a = int(binascii.hexlify("#overlord"), 16) role2 = binascii.unhexlify("%x"%((a/2))) s = socket.socket(socket.AF_INET, socket.SOCK_STREAM) s.connect(("22.214.171.124", 1337)) s.send("2\n") s.send(name + "\n") s.send(role2 + "\n") data = s.recv(4096) c1_c2 = s.recv(4096) data = s.recv(4096) (c1, c2) = c1_c2.split("_") c1 = c1.split("\n") s = socket.socket(socket.AF_INET, socket.SOCK_STREAM) s.connect(("126.96.36.199", 1337)) data = s.recv(4096) s.send("1\n") data = s.recv(4096) s.send("%s_%x\n" % (c1, int(c2, 16) * 2 )) data = s.recv(4096) data = s.recv(4096) print(data)
What’s happening here is that we first connect and log in, get the token from our specially
crafted role then we split the token in
c2 and sends the token back and get