0ctf’17 – All crypto tasks


Just a simple scheme.
nc 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}.


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"
fake_secret2 = "feeddeadbeefcafefeeddeadbeefcafe"
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')
A = GF2f(num2poly(int(f.readline(), 16)))
B = GF2f(num2poly(int(f.readline(), 16)))
C = GF2f(num2poly(int(f.readline(), 16)))

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}.


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[1]))
G0 = GF2f(num2poly(0x2fe7878d67cdbb206a58dc100ad980ef))

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

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s