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 multiplicationwith 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 twomatrices (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!!}
.
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.