I was teamed up with @shellphish this time for De1CTF. During the game, I have solved 5 (out of 7) cryptography challenges individually, and a reverse challenge and a misc challenge in cooperation with DuSu and fs0c.

I said that I'll commit the solution scripts to my Github after I have managed to prettify them. It never happened. I will not make the same promise again.

Homomorphic⌗

Challenge Summary⌗

This is a cryptography challenge with 465 points.

The challenge implements an cryptosystem with ring-LWE. At the beginning, we are given a public key and an encrypted flag sealed with the key. Moreover, it exposed us an oracle to encrypt and decrypt.

Solution⌗

I've spent 1.5 hours on this challenge.

Part I: The computation behind⌗

This part briefly describes how a specific case of ring-LWE works. You actually don’t need to know how this works to solve the challenge.

The public key is a pair of polynomials $P_1(x), P_2(x)$ with $P_1(x) := -P_2(x)S(x) + \mathcal{E}_0(x)$. Hereby $S(x)$ is the private key that the coefficients can either be 0 or 1, and $\mathcal{E}_0(x)$ is an small error polynomial that is kept away from our reach.

The ciphertext for an integer $0 \leq m \le 256$ is a pair of polynomial $C_1(x) := P_1(x)U(x) + \mathcal{E}_1(x) + 4m$ and $C_2(x) := P_2(x)U(x) + \mathcal{E}_2(x)$. $U(x)$ is a randomly generated polynomial with coefficients being 0 or 1, and $\mathcal{E}_1(x)$ and $\mathcal{E}_2(x)$ are small error polynomials.

To decrypt... I'll cut the crap.

Part II: The check⌗

During code review, I was curious why it encrypts character by character. There must be some mishaps implementing in this way!

But there is another thing that caught my attention...

def check(self,m):
  m0,m1 = [abs(j) for j in m[0]],[abs(j) for j in m[1]]
  for f in FLAG:
    i0,i1 = [abs(j) for j in f[0]],[abs(j) for j in f[1]]
    if m0 == i0 and m1 == i1:
      return False
  return True

Simply put, you cannot send any of the polynomial pair $(C_1(x), C_2(x))$ that is given by them at the beginning. It bans a bunch of similar polynomials as well.

Note that the cryptosystem runs under modulo $q = 2^{54}$. The value of $q$ doesn't actually matter, but the fact that it is operated under a modulus.

Part III: The bypass⌗

A similar story is: You are given an oracle that decrypts messages encrypted with RSA. You can decrypt every single of them but not $c_0$. What can you do? -- A level zero bypass is to send $c_0 + n$ and hope it worked.

For this challenge, if we are given $C_1(x) = \sum u_ix^i$ and $C_2(x) = \sum v_ix^i$ that is the ciphertext of a character $m$, we can simply send $C'_1(x) = \sum (u_i + q)x^i$ and $C'_2(x) = \sum (v_i + q)x^i$ to the decryption oracle. It just worked.

OV⌗

Challenge Summary⌗

This is a cryptography challenge that worths 800 points.

The challenge implements an oil and vinegar scheme. Under a given public key, an oracle that sign messages (except iwanttoknowflag!) and verify signatures is exposed to us. The objective is to forge the signature for iwanttoknowflag!.

Solution⌗

I've spent around 10 hours to solve it.

Part I: Paper reading session⌗

Kipnis and Shamir had an research paper attacking the oil and vinegar signature scheme. Kipnis has also written an extended version that made the whole thing easier to understand. I've refer to more research papers to implement an working attack... or did I?

For anyone who thinks this is a simple process, the above paragraph simply compresses a 8-hour work session.

Paper II: Shit, what have I done?⌗

After I've implemented a working attack for the scheme, tested with random key pairs, I just can't wait to deploy the attack to the oracle. I am getting "wrong signature". Wait. Wrong signature? I have double checked (or triple, or quadruple, or even more) that my solution is correct.

During debugging, I tried to sign a random message with the signing oracle and send it to the verification oracle. Correct. However, when I pass the same message-signature pair to my own signature verifier, it is incorrect. Did I misunderstood how the signature scheme works?

I've read in more detail on how they verify signatures:

# sign is the signature, and H is the message
def verity(self,sign,H):
  sign = self.IntListDecoder(sign)
  PK = [self.x*self.pk[i]*self.xt for i in range(self.o)]
  images = [i for i in sign]
  phi = self.PR.hom(images,self.K)
  pk_sub = [phi(PK[i][0]) for i in range(self.o)]
  return pk_sub == H

Doesn't it mean that if $P_1, P_2, ..., P_{16}$ is the matrices representing the public key, the message $\vec{m} = (m_1, m_2, ..., m_{16})$ and signature $\vec{s}$ would satisfy

\[\vec{s}^T P_i \vec{s} = m_i\ \text{for all}\ i = 1, 2, ..., 16?\]

Everything looked normal for me... until I look on each variable independently. Especially $H$.

When trying to verify the message testtesttesttest, this is what I get:

H = [0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0]

What? Why? My brain was unable to function and it took me a long while to figure out what happened. -- Looks like the oracle has signing (and verifying) one bit from each of the characters...

That said, signing Iwanttoknowflag! is equivalent to signing [1, 1, 1, 0, 0, 0, 1, 1, 0, 1, 1, 0, 0, 1, 1, 1]. The signature obtained is actually a valid signature for iwanttoknowflag!, as it is simply [1, 1, 1, 0, 0, 0, 1, 1, 0, 1, 1, 0, 0, 1, 1, 1] in disguise.

Part III: Where did it went wrong?⌗ 

def hashFunction(self,m):
  assert(len(m) == o)
  H = [ord(i) for i in m]
  return H

def sign(self,m):
  H = self.hashFunction(m)
  # more operation under GF(2^8)...

At this point, H is an integer within 0 and 255. When converted into $\text{GF}(2^8)$, it becomes 0 or 1. The hashFunction should be patched to avoid the trivial bypass.

def hashFunction(self,m):
-  H = [ord(i) for i in m]
+  H = [K.fetch_int(ord(i)) for i in m]