Learning with Exploitation author's writeup

Challange summary

In this challenge, I implemented multibit-variant of Regev's cryptosystem.

Normal Regev's cryptosystem

First, the cryptosystem generates LWE Oracle. The matrix

$A$, vector

$s$, error vector

$e$, and target vector

$t$ that holds:

$$A\cdot s+e=t$$

and

$A,t$ will be a public key.

To encrypt, the cryptosystem generates vector consisting of only 0 or 1

$r$. The ciphertext

$(u,v)$ of

$m\in \{0,1\}$ will be:

$$(u,v)=(r\cdot A,r\cdot t+mq)$$

Note that

$q:=\lceil \frac{p}{2}\rceil$

Decryption will be as follows:

• If
  $v-u\cdot s\approx 0$,
  $m=0$.
• If
  $v-u\cdot s\approx q$,
  $m=1$.

Extended Regev's Cryptosystem in this challenge

I extended this cryptosystem to encrypt multibit rather than single bit. In this challenge, to encrypt 64-bit plaintext

$0\le m<2^{64}$, I defined

$q:=\lceil \frac{p}{2^{64}}\rceil$.

The encryption and decryption are almost the same as the original.

Solution

Unfortunately, this trivial extensions do not work.

In this cipher, the following equation holds.

$$u=r\cdot A$$

$A$ and

$u$ are known and

$r(\in \{0,1{\}}^{100})$ is hidden.

By taking one row from

$A$, recovering the parameter

$r$ is almost the same with attacking Merkle–Hellman knapsack cryptosystem. It is known that, with certain conditions, Low-Density attack works well for attacking knapsack cryptosystem.

In the condition given, The bit length of the element of A is far longer than 100bit (to make the cryptosystem work with 64bit plaintext). Low-density attack can be applied and

$r$ can be recoverd.

After

$r$ is recovered, we can restore the plaintext

$m$ from the equation

$v=r\cdot t+mq$.

Solver

from output import public_key, ciphertext
from sage.modules.free_module_integer import IntegerLattice

p = 0xfffffffffffffffffffffffffffffffeffffffffffffffff
F = GF(p)
d = 100
n = 10
q = p // (2 ** 64)

A, T = public_key
A = matrix(F, A)
T = vector(F, T)

N = 2 ** 64

t = 2

flag = b''

for (U, v) in ciphertext:
  U = vector(F, U)
  v = F(v)

  M = []

  for i in range(d):
    g = [0 for _ in range(d + t)]
    for j in range(t):
      g[j] = int(A[i][j]) * N
    g[i + t] = 2
    M.append(g)

  g = [0 for _ in range(d + t)]
  for i in range(t):
    g[i] = -int(U[i]) * N
  for i in range(d):
    g[i + t] = -1
  M.append(g)

  for i in range(t):
    g = [0 for _ in range(d + t)]
    g[i] = p * N
    M.append(g)

  print('LLL start')
  lattice = IntegerLattice(M, lll_reduce=True)
  print('LLL end')

  E = lattice.reduced_basis

  ok = False
  r_recovered = None
  for g in E:
    if g[0] == 0 and all(x == 1 or x == -1 for x in g[t:]):
      r_recovered = vector([F((x + 1) // 2) for x in g[t:]])
      print(r_recovered)
      print((r_recovered * A)[0:3])
      print(U[0:3])
      if U == r_recovered * A:
        ok = True
        break

  if not ok:
    print('attack failed')
    exit()

  m = (v - r_recovered * T) / q
  flag += int(m).to_bytes(8, 'big')

  print(flag)