# Learning with Exploitation author's writeup
## Challange summary
In this challenge, I implemented multibit-variant of [Regev's cryptosystem](https://en.wikipedia.org/wiki/Learning_with_errors#Public-key_cryptosystem).
### Normal Regev's cryptosystem
First, the cryptosystem generates [LWE Oracle](https://doc.sagemath.org/html/en/reference/cryptography/sage/crypto/lwe.html). 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](https://en.wikipedia.org/wiki/Merkle%E2%80%93Hellman_knapsack_cryptosystem). It is known that, with certain conditions, [Low-Density attack](https://web.stevens.edu/algebraic/Files/SubsetSum/p229-lagarias.pdf) 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
```python
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)
```

SSSS.RNG $p$を512bitの素数、$a,b,x$を$p$未満のランダムな数とする。 以下すべて$\mathbb{Z}/p\mathbb{Z}$上の演算として、 $$ \begin{aligned} g_1&=ax+b\ g_2&=ag_1+b\ g_3&=ag_2+b\

11/7/2021Challenge Summary You are given a website. It is doing some weird job. First, it constructs routes object based on the salt parameter and store it to the session. const setRoutes = async (session, salt) => { const index = await fs.readFile('index.html'); session.routes = { flag: () => '*** CENSORED ***',

10/5/2021Challenge Summary You can create blog post. It is accepting an arbitrary HTML, but it is correctly escaped and sanitized by DOMPurify. const body = document.getElementById('body'); body.innerHTML = DOMPurify.sanitize(body.textContent); hljs.highlightAll(); The goal is to obtain the cookie of admin.

10/4/2021Welcome @moratorium08 :) babycrypto1 @hakatashi We can encode arbitrary block with chosen IV, so we can extend the given block with arbitrary content. from ptrlib import Socket, logger from base64 import b64encode, b64decode from Crypto.Cipher import AES

3/23/2021
Published on ** HackMD**

or

By clicking below, you agree to our terms of service.

Sign in via Facebook
Sign in via Twitter
Sign in via GitHub
Sign in via Dropbox
Sign in with Wallet

Wallet
(
)

Connect another wallet
New to HackMD? Sign up