## 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 bedef 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!!}`

.

What library are you using that providers PolynomialRing and GF?

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