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:
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)
Bravo băieții :)
