# 0ctf’17 – All crypto tasks

## Integrity

Just a simple scheme.
nc 202.120.7.217 8221

The encrypt function in the scheme takes the username as input. It hashes the username with MD5, appends the name to the hash and encrypts with a secret key $k$, i.e. $\textsf{Enc}_k(H_\text{MD5}(\text{username}) \|\text{username})$. Then, the secret becomes $\text{IV} \| C_1 \| C_2 ...$. Notably, the first block $C_1$ contains the hash, but encrypted.

Recall how the decryption is defined: $C_i = \textsf{Dec}_k(C_i) \oplus C_{i-1}, C_0 = \text{IV}$

So, what would happen if we input $u = H_\text{MD5}(\texttt{admin}) \| \texttt{admin}$ as username? Then, we have encrypted $H_\text{MD5}(u) \| u$, but we want only $u$. As mentioned before, the hash fits perfectly into a single block. So, by removing the $\text{IV}$ $C_1$ becomes the new $\text{IV}$ (which has no visible effect on the plaintext anymore!). Then, we have $\textsf{Enc}_k(H_\text{MD5}(\texttt{admin}) \| \texttt{admin})$, which is all what we need.

The flag is flag{Easy_br0ken_scheme_cann0t_keep_y0ur_integrity}.

## OTP1

I swear that the safest cryptosystem is used to encrypt the secret!

We start off analyzing the code. Seeing process(m, k) function, we note that this is actually something performed in $\mathbb F_2[x]/P(x)$ with the mapping that, for instance, an integer $11$ is $\texttt{1011}$ in binary, which corresponds to a polynomial $x^3 + x + 1$. The code is doing $(m \oplus k)^2$ in $GF(2^{256})$.

The keygen function repeatedly calls  key = process(key, seed). The first value for key is random, but the remaining ones does not. seed remains the same. Define $K$ to be the key and $S$ the seed. Note that all elements are in $GF(2^{256})$. The first stream value $Z_0$ is unknown. $Z_0 = K$ $Z_1 = (Z_0 \oplus S)^2 = K^2 \oplus S^2$ $Z_2 = (Z_1 \oplus S)^2 = Z_1^2 \oplus S^2$

So, we can compute the seed and key as $S^2 = Z_2 \oplus Z_1^2$ and $K^2 = Z_1 \oplus S^2 = Z_1 \oplus Z_2 \oplus Z_1^2$. The individual square roots exist and are unique.

def num2poly(num):
poly = R(0)
for i, v in enumerate(bin(num)[2:][::-1]):
if (int(v)):
poly += x ** i
return poly

def poly2num(poly):
bin = ''.join([str(i) for i in poly.list()])
return int(bin[::-1], 2)

def gf2num(ele):
return ele.polynomial().change_ring(ZZ)(2)

P = 0x10000000000000000000000000000000000000000000000000000000000000425L

fake_secret1 = "I_am_not_a_secret_so_you_know_me"
secret = str2num(urandom(32))

R = PolynomialRing(GF(2), 'x')
x = R.gen()
GF2f = GF(2**256, name='a', modulus=num2poly(P))

f = open('ciphertext', 'r')

b = GF2f(num2poly(str2num(fake_secret1)))
c = GF2f(num2poly(str2num(fake_secret2)))

# Retrieve partial key stream using known plaintexts
Y = B + b
Z = C + c

Q = (Z + Y**2)
K = (Y + Q).sqrt()

print 'flag{%s}' % hex(gf2num(A + K)).decode('hex')


This gives the flag flag{t0_B3_r4ndoM_en0Ugh_1s_nec3s5arY}.

## OTP2

Well, maybe the previous one is too simple. So I designed the ultimate one to protect the top secret!

There are some key insights:

• The process1(m, k) function is basically the same as in previous challenge, but it computes the multiplication $m \otimes k$ with the exception that elements are in $GF(2^{128})$ this time.  We omitt the multiplication symbol from now on.
• The process2(m, k) function might look involved, but all that it does is to compute the matrix multplication between two $2 \times 2$ matrices (with elements in $GF(2^{128})$), i.e., $XY = \begin{pmatrix}x_0 & x_1 \\ x_2 & x_3\end{pmatrix}\begin{pmatrix}y_0 & y_1 \\ y_2 & y_3\end{pmatrix}$
• We start with matrices $X = \begin{pmatrix}1 & 0 \\ 0 & 1\end{pmatrix}$ and $Y = \begin{pmatrix}A & B \\ 0 & 1\end{pmatrix}$.
• Raising $A$ to a power yields has a closed form formula: $A^s = \begin{pmatrix}A^s & B(A^{s-1} \oplus A \oplus 1 )\\ 0 & 1\end{pmatrix} =\begin{pmatrix}A^s & B\frac{A^{s} \oplus 1 }{A \oplus 1}\\ 0 & 1\end{pmatrix}$.
• The nextrand(rand) function takes the integral value of $N$, we call this $s$ and computes $Y^s = \begin{pmatrix}A & B \\ 0 & 1\end{pmatrix}^s$ via a square-and-multiply type algorithm. In python, it would be
def proc2(key):
AN = A**gf2num(N)
return key*AN+(AN+1)/(A+1)*B

Let us look at the nextrand(rand) function a little more. Let $R$ be the random value fed to the function. Once $Y^s$ is computed, it returns $Q = R A^s \oplus \frac{A^s \oplus 1}{A\oplus 1} B$

Define $U = \frac{B}{A\oplus 1}$. Adding this to the above yields $Q\oplus U = R A^s \oplus \frac{A^s \oplus 1 \oplus 1}{A\oplus 1} B = A^s(R \oplus \frac{B}{A\oplus 1}) = A^s(R\oplus U)$.

So, $A^s = \frac{Q\oplus U}{R \oplus U}$. Note that given two elements of the key stream, all these elements are known. Once determined, we compute the (dicrete) $\log \frac{Q\oplus U}{R\oplus U}$ to find $s$. And once we have $s$, we also have $N$. Then, all secrets have been revealed!

From the plaintext, we can immediately get the key $K$ by XORing the first part of the plaintext with the corresponding part of the ciphertext. This gives $K =\texttt{0x2fe7878d67cdbb206a58dc100ad980ef}$.


R = PolynomialRing(GF(2), 'x')
x = R.gen()

GF2f = GF(2**128, name='a', modulus=num2poly(0x100000000000000000000000000000087))

A = GF2f(num2poly(0xc6a5777f4dc639d7d1a50d6521e79bfd))
B = GF2f(num2poly(0x2e18716441db24baf79ff92393735345))
G1 = GF2f(num2poly(G))

U = B/(A+1)
Z = (G1+U)/(G0+U)
N = discrete_log(Z, A, K.order()-1)


We can then run the encryption (the default code) with the parameters $N,K$ fixed to obtain the flag flag{LCG1sN3ver5aFe!!}.

## 2 thoughts on “0ctf’17 – All crypto tasks”

1. kevinorr54 says:

What library are you using that providers PolynomialRing and GF?

1. Carl Löndahl says:

I run the Python code in Sage. Simply invoke sage -python mycode.py and it will do the job.