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 , i.e. . Then, the secret becomes . Notably, the first block contains the hash, but encrypted.

Recall how the decryption is defined:

So, what would happen if we input as username? Then, we have encrypted , but we want only . As mentioned before, the hash fits perfectly into a single block. So, by removing the ,  becomes the new  (which has no visible effect on the plaintext anymore!). Then, we have , 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 with the mapping that, for instance, an integer is in binary, which corresponds to a polynomial . The code is doing in .

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 to be the key and the seed. Note that all elements are in . The first stream value is unknown.

So, we can compute the seed and key as and . 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}.

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 with the exception that elements are in 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 matrices (with elements in ), i.e.,
• We start with matrices  and .
• Raising to a power yields has a closed form formula: .
• The nextrand(rand) function takes the integral value of , we call this and computes 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 be the random value fed to the function. Once is computed, it returns

Define . Adding this to the above yields

.

So, . Note that given two elements of the key stream, all these elements are known. Once determined, we compute the (dicrete) to find . And once we have , we also have . Then, all secrets have been revealed!

From the plaintext, we can immediately get the key by XORing the first part of the plaintext with the corresponding part of the ciphertext. This gives .

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 fixed to obtain the flag flag{LCG1sN3ver5aFe!!}.