Rating: 5.0

# Timisoara-CTF-Finals-2018-Crypto-Write-up
## Write-up for tasks Recap(250p) and Recess(400p)

This was a 2 in one problem. We were given a copy of the code that was running on a server in which the flags were in some files flag1, respectively flag2:
python
import signal
import sys
import os
import binascii
import random

os.chdir(os.path.dirname(os.path.abspath(__file__)))

MAGIC_NUMBER = 11
MSG_LENGTH = 119
CERT_CNT = MAGIC_NUMBER
coeffs = [random.randint(0, MAGIC_NUMBER**128) for i in range(MAGIC_NUMBER)]

def enc_func(msg):
global coeffs
msg = msg * 0x100 + 0xFF
acc = 0
cur = 1
for coeff in coeffs:
acc = (acc + coeff * cur) % (MAGIC_NUMBER**128)
cur = (cur * msg) % (MAGIC_NUMBER**128)
return acc % (MAGIC_NUMBER**128)

def get_hex_msg():
try:
msg = raw_input()
msg = int(msg,16)
return msg % (MAGIC_NUMBER ** (128) )
except:
exit()

def encryption():
msg = get_hex_msg()
ct = enc_func( msg )
print "Encryption >>>> %#x" % ct

def challenge1():
for i in range(CERT_CNT):
msg = random.randint(0, MAGIC_NUMBER**(MSG_LENGTH) )
ct = enc_func( msg )
print 'Encrypt this: %#x' % msg
ct2 = get_hex_msg()
if ct != ct2:
print "Your input %#x should have been %#x" % (ct2, ct)
exit()
print "You win challenge 1"

def challenge2():
for i in range(CERT_CNT):
msg = random.randint(0, MAGIC_NUMBER**(MSG_LENGTH))
ct = enc_func( msg )
print 'Decrypt this: %#x' % (ct)
msg2 = get_hex_msg()
if enc_func(msg) != enc_func(msg2):
print "Your input %#x should have been %#x" % (msg2, msg)
exit()
print "You win challenge 2"

def input_int(prompt):
sys.stdout.write(prompt)
try:
n = int(raw_input())
return n
except ValueError:
return 0
except:
exit()

while True:
print "Horrible Crypto"
print "1. Arbitrary Encryption"
print "2. Encryption Challenge"
print "3. Decryption Challenge"
print "4. Exit"
choice = input_int("Command: ")
{
1: encryption,
2: challenge1,
3: challenge2,
4: exit,
}.get(choice, lambda *args:1)()

if __name__ == "__main__":
signal.alarm(15)

Ok, so let's analyse what we are given and what we have to do:
Running the code we can see a menu:
> Horrible Crypto
> 1. Arbitrary Encryption
> 2. Encryption Challenge
> 3. Decryption Challenge
> 4. Exit

So, we are given an encryption oracle and two challanges, encryption (**task recap**) and decryption (**task recess**)
### Understanding the encryption
python
def enc_func(msg):
global coeffs
msg = msg * 0x100 + 0xFF
acc = 0
cur = 1
for coeff in coeffs:
acc = (acc + coeff * cur) % (MAGIC_NUMBER**128)
cur = (cur * msg) % (MAGIC_NUMBER**128)
return acc % (MAGIC_NUMBER**128)

def get_hex_msg():
try:
msg = raw_input()
msg = int(msg,16)
return msg % (MAGIC_NUMBER ** (128) )
except:
exit()

def encryption():
msg = get_hex_msg()
ct = enc_func( msg )
print "Encryption >>>> %#x" % ct

Inside encryption() the input is a hex number which gets decoded to an int and then actually encrypted in enc_func(msg).
Now, let's focus on how the encryption works:
It takes the message, it multiplies it by 256, adds 255 msg = msg * 0x100 + 0xFF and then computes the polynomial coeffs(msg) modulo 11^128 (MAGIC_NUMBER = 11 is a constant), and that's our ciphertext.
Recap was the first challenge. The adversary is given 11 messages to encrypt. By successfully encrypting the messages, the flag is given to the adversary.
python
def challenge1():
for i in range(CERT_CNT):
msg = random.randint(0, MAGIC_NUMBER**(MSG_LENGTH) )
ct = enc_func( msg )
print 'Encrypt this: %#x' % msg
ct2 = get_hex_msg()
if ct != ct2:
print "Your input %#x should have been %#x" % (ct2, ct)
exit()
print "You win challenge 1"

So basically we need to find the coefficients of the polynomial **coeffs** in order to be able to encrypt. Note that we have an encryption oracle so practically we can find any coefficient of the polynomial **coeffs** right? Well, that's great because we can recreate the original polynomial by creating a **Lagrange polynomial** of degree equal to the degree of the polynomial **coeffs**.
You can read more about it on [Wikipedia](https://en.wikipedia.org/wiki/Lagrange_polynomial), the math is pretty simple, and there's an image that visually describes very well the algorithm.
**NOTE**: since the contest's servers don't work anymore you will have to run the challange code locally.

Now, the second task was the **real deal**. The adversary has to decrypt 11 messages. I didn't solve this task during the contest (I solved it about 4 hours after the contest ended, but I still got goosebumbs when I got the flag). About 3 hours before the end of the contest a hint was added (sadly, i don't remember the exact form of the hint), and eventually I found an article on [Wikipedia](https://en.wikipedia.org/wiki/Hensel%27s_lemma) and a bit of code on [GitHub](https://github.com/gmossessian/Hensel/blob/master/Hensel.py). After a good 30 minutes of reading I implemented the solution, practically for a message **msg** we had to find a root of the polynomial f(x)=coeffs(x)-msg. The mistake I made was that I didn't realize what this line of code was doing:
python
msg = msg * 0x100 + 0xFF

This makes it so that the encription is a bit more complicated, encription isn't just **coeffs(msg)**, it's **coeffs(g(msg))**, where **g** is another ploynomial: g(x) = 256*x+255. That means that Hensel's lemma had to be applied to the polynomial **coeffs(g(x))**. So I wrote a funtion that composes two polynomials.
### The code
Here's my solution to both problems:
`python
from pwn import *
from Crypto.Util.number import inverse

MOD=11**128

def transform(x):
return (x*256+255)%MOD

#Polynomial part
class Polynomial(list):

def __init__(self,coeffs):
self.coeffs = coeffs

def evaluate(self,x,mod):
val = 0
for i in range(len(self.coeffs)):
val = (val + x**i * self.coeffs[i]) % mod
return val

def raise_degree(self,x):
coeffs=[]

for i in range(x):
coeffs.append(0)

for i in range(len(self.coeffs)):
coeffs.append(self.coeffs[i])

self.coeffs=coeffs