Rating: 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:

print "Bad input"

exit()

def encryption():

print 'Input your message:'

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"

print open("flag1").read()

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"

print open("flag2").read()

def input_int(prompt):

sys.stdout.write(prompt)

try:

n = int(raw_input())

return n

except ValueError:

return 0

except:

exit()

def menu():

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)

a menu()

```

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

Let's start with 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:

print "Bad input"

exit()

def encryption():

print 'Input your message:'

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.

### Task Recap

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"

print open("flag1").read()

```

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.

### Task Recess

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

def add_to_degree(self,x,y):

while(len(self.coeffs)<=x):

self.coeffs.append(0)

self.coeffs[x]=(self.coeffs[x]+y)%MOD

def add_poly(self,x):

while(len(self.coeffs)