If you need to securely grant execution privileges, what better way to do it than sexec?
This is running on sexec.pwning.xxx:9999
Summary: attacking a small instance of Ring-LWE based cryptosystem with Babai’s Nearest Vector algorithm.
In this challenge we are given a source code of a service which allows command execution. However, the session is encrypted using a hardcoded public key. Let’s look at the main part:
def connectionMade(self): self.process = None self.secret = uniform(4, 0, 255).astype(np.uint8) self.secret_bits = np.unpackbits(self.secret) self.aes_key = ''.join([chr(x) for x in self.secret]) +\ '\x00\x01\x02\x03\x04\x05\x06\x07\x08\x09\x0A\x0B' sk = uniform(self.factory.param.N) pub = op(self.factory.param.a, sk) \ + uniform(self.factory.param.N) enc = op(self.factory.pk, sk) \ + uniform(self.factory.param.N) \ + (self.secret_bits * (self.factory.param.Q / 2)) pub %= self.factory.param.Q enc %= self.factory.param.Q ct = asn1.Ciphertext() ct.setComponentByName('pub', asn1.ints_to_bitstring(pub, self.factory.param.Q)) ct.setComponentByName('enc', asn1.ints_to_bitstring(enc, self.factory.param.Q)) self.sendString(asn1.encoder.encode(ct)) self.iv1 = os.urandom(12) self.iv2 = 0 self.sendString(self.iv1) def stringReceived(self, data): if len(data) < 4: self.transport.loseConnection() return tag = data[:4] data = data[4:] decryptor = Cipher( algorithms.AES(self.aes_key), modes.GCM(self.iv, tag, min_tag_length=4), default_backend()).decryptor() self.iv2 += 1 try: data = decryptor.update(data) + decryptor.finalize() except InvalidTag: self.transport.loseConnection() return if self.process is None: self.process = ShellProcessProtocol( self.sendString, self.transport.loseConnection) reactor.spawnProcess(self.process, data, [data], {}) self.process_timer = reactor.callLater(5, lambda: self.connectionLost(None)) return else: self.process.transport.write(data) return |
We see that the AES key has only 4 random bytes. But we are not given any plaintext-ciphertext pair, we can only send ciphertext + tag to check it. Thus, we can bruteforce only via network which is unfeasible. We have to attack the asymmetric crypto here.
Mysterious $op(a, b)$
The cryptosystem is based on the op(a, b) method, which uses Discrete Fourier Transform:
def op(a, b): c = np.fft.ifft( np.fft.fft(a, a.size * 2) * np.fft.fft(b, b.size * 2) ).real return (c[0:a.size] - c[a.size:]).astype(np.int) |
If you don’t know the first construction, it is multiplication of polynomials using DFT. Here’s a short explanation: DFT can be seen as transforming an array of a polynomial coefficients into an array of values of that polynomial on particular points. These points are powers of the $n$th root of unity (which is a complex number $e^{i \frac{2\pi}{n}}$). A nice property is that $DFT(p(x)*q(x)) = DFT(p(x))\cdot DFT(q(x))$, where $*$ is multiplication of polynomials and $\cdot$ is componentwise product. Therefore to multiply two polynomials we can compute $DFT^{-1}(DFT(p(x))\cdot DFT(q(x)))$. There exist algorithms for DFT and inverse DFT with complexity $O(n\log{n})$, and this is the final complexity of the described algorithm. Note that naive polynomial multiplication has complexity $O(n^2)$. But here I guess this approach was used for easier coding, since $O(n^2)$ is good enough for the challenge parameters.
In the second part, the most significant half of the coefficients is subtracted from the least significant half. It correspongs to the relation $x^n = -1$, which means that it is a reduction modulo $x^n + 1$.
To sum up, $op(a,b)$ is multiplication of two polynomials $a$ and $b$ of degree $n-1$ modulo $x^n + 1$. Note that numpy.fft uses real and complex numbers and therefore is not precise.
The cryptosystem
First we extract the public parameters:
$N = 32,$
$Q = 929,$
$a = [592, 476, 894, 411, 843, 634, 904, 322, 424, 368, 164, 47, 698,
778, 222, 680, 683, 384, 102, 161, 243, 224, 768, 137, 659, 28,
189, 335, 167, 67, 517, 701].$
They mean that we work with polynomials of degree 31 over $GF(929)$ and the polynomials are taken modulo $x^{32}+1$. Here are the equations from the code:
- $sk,r_0,r_1$ are random “small” polynomials: coefficients are from $[-5,5]$.
- $pub = a*sk + r_0$.
- $enc = pk*sk + r_1 + \lfloor Q/2 \rfloor secret$.
We are given $pub$ and $enc$, and we need to recover $secret$. This is Ring Learning with Errors (Ring-LWE) based cryptosystem. Notably, such cryptosystems are expected to be secure against quantum computers.
Note that in usual public-key cryptosystems on finite fields the norm (magnitude) of the values usually does not matter. While here it plays very important role. The small polynomials added are small errors adding some noise to the values. Also the remainders are taken to be $-q/2,\ldots,-1,0,1,\ldots,q/2$ instead of $0,1,\ldots,q-1$.
But it should be possible to recover the $secret$ (encrypted message) at least by the owner of the private key! How? There is no explanation in the code, but actually there exist small polynomials $s_0$ and $s_1$, such that $pk = a*s_0 + s_1$! These small polynomials form a private key and its owner can decrypt the message as follows:
$pub*s_0 = a*s_0*sk + r_0*s_0 = pk * sk – s_1*sk + r_0*s_0,$
$m = enc – pub*s_0 = r_0*s_0 – s_1*sk + r_1 + \lfloor Q/2 \rfloor secret.$
Note that multiplication of two small polynomials is not large too: it is bounded by $5*5*32 = 800$ but the expected value is much smaller. Therefore if the $i$-th secret bit is 1, we expect $m$ to be closer to $-q/2$ or to $q/2$ than to 0. And with high probability the full message can be recovered without errors.
Attacking the cryptosystem
How can we attack it? First direction is to attack the equation $pub = a*sk + r_0$ to recover $sk$. Then we could compute $pub – pk*sk = r_0 + \lfloor Q/2 \rfloor secret$ which is enough to recover the $secret$. A good thing is that we have randomization ($sk$ is always random) and can get different instances. But we have to mount the attack online, which may take some time. So, let’s try to recover the private key.
That is, we attack the equation $pk = a*s_0 + s_1$. We know $a$ and $pk$ and we need to find suitable small $s_0$ and $s_1$. Finding “small” values usually refers to LLL and Ring-LWE is called “lattice-based” also.
Multiplication by $a$ in the polynomial ring can be described by $32\times32$ matrix $M_a$ over $GF(Q)$. That is, in matrix form we have: $pk = M_a \times s_0 + s_1$. Note that $s_0$ specifies a linear combination of columns from $M_a$. Now we can see how the lattice should look like: columns of $M_a$ form a basis and we want to find a vector which is very close to $pk$. But we also want the coefficients from $s_0$ to be small! To ensure this we can use the following trick: extend the $i$-th basis vector with $n$ zeroes and set $1$ into position $n+i$. Then, in the final vector these positions will be equal to coefficients from $s_0$. Since we want them to be small, we extend the target vector (which is $pk$) with zeroes. Let $m_i$ be the $i$-th column of $M_a$. Then the basis of the lattice looks like this:
$m_0 || 1, 0, \ldots, 0$
$m_1 || 0, 1, \ldots, 0$
$\ldots$
$m_n || 0, 0, \ldots, 1$
However, we forgot about reductions modulo $Q$! Since they are free, we can simply add $n$ vectors where $i$-th vector has $Q$ in position $i$ and zeroes elsewhere. In the matrix form, the lattice is spanned by the rows of the following matrix:
$\begin{bmatrix}
Q[I] & [0] \\
[M_A^T] & [I] \\
\end{bmatrix},$
where $[I]$ is the $n\times n$ identity matrix.
That is, we have a lattice and a target vector. We now need to solve the Closest Vector Problm (CVP). It is hard but feasible because of small $n=32$. Sage has a closest_vector method but it is very slow. I decided to use Babai’s Nearest Plane algorithm, which calls LLL several times. It is approximation algorithm but it is enough for our case.
Here’s the full code for computing private key in Sage:
from sage.all import * from sexec import op import numpy as np Q = 929 R.<x> = PolynomialRing(GF(Q)) S.<y> = R.quotient(x**32 + 1) # numpy multiplication def myop(a, b): a = np.array(list(a), dtype=np.int) b = np.array(list(b), dtype=np.int) return vector(ZZ, op(a, b)) # precise multiplication def mymul(a, b): a = list(a) b = list(b) return vector(ZZ, list(S(a)*S(b))) # Babai's Nearest Plane algorithm def Babai_closest_vector(M, G, target): small = target for _ in xrange(1): for i in reversed(range(M.nrows())): c = ((small * G[i]) / (G[i] * G[i])).round() small -= M[i] * c return target - small a = [592, 476, 894, 411, 843, 634, 904, 322, 424, 368, 164, 47, 698, 778, 222, 680, 683, 384, 102, 161, 243, 224, 768, 137, 659, 28, 189, 335, 167, 67, 517, 701] pk = [558, 630, 505, 864, 186, 509, 81, 752, 167, 254, 907, 484, 279, 762, 200, 810, 640, 402, 549, 850, 310, 376, 48, 306, 158, 178, 497, 254, 21, 259, 329, 564] # Multiplication by a mulA = matrix(ZZ, 32, 32) for i in range(32): tst = [0]*32 tst[i] = 1 mulA.set_row(i, list(S(tst) * S(a))) # Basis for the lattice B = matrix(ZZ, 64, 64) B[:32,:32] = Q * identity_matrix(ZZ, 32, 32) B[32:,:32] = mulA B[32:,32:] = identity_matrix(ZZ, 32, 32) for itr in xrange(100): print "Try #%d" % itr # randomize lattice for i in range(50): ia = randint(0, 63) ib = randint(0, 63) if ib == ia: ib = (ib + 1) % 64 val = randint(-10, 10) B[ia] += val * B[ib] print "= LLL + Gram Schmidt" M = B.LLL() # delta=0.9999999, eta=0.5) G = M.gram_schmidt()[0] print "= Done" target = vector(ZZ, list(pk) + [0] * 32) res = Babai_closest_vector(M, G, target) delta = res - target s0 = vector(ZZ, delta[32:]) s1 = vector(ZZ, target[:32] - res[:32]) print "= s0 =", s0 print "= s1 =", s1 assert list( (mymul(s0, a) + s1) % Q ) == pk assert list( (s0 * mulA + s1) % Q ) == pk # try encrypt/decrypt # random messages to see how good are s0 and s1 def rnd(): return vector(ZZ, [randint(-5, 5) for _ in xrange(32)]) secret = vector(ZZ, [randint(0, 1) for _ in range(32)]) guessed = [0] * 32 for i in xrange(2000): sk = rnd() pub = myop(a, sk) + rnd() enc = myop(pk, sk) + rnd() + secret * (Q // 2) res = (enc - mymul(pub, s0)) % Q recovered = [1 - int(v < Q // 4 or v > Q - Q // 4) for v in res] if list(recovered) == list(secret): print "Full recovery!" quit() for j in range(32): guessed[j] += (recovered[j] == secret[j]) print "= guesses", " ".join("%.2f" % (v / 2000.0) for v in guessed) print |
After a few tries we recover the correct private key (the absoulte values are bounded by 5):
$s_0 = (-2, 4, 0, -5, 2, -4, 4, -5, 0, -2, 0, -1, -1, -4, -2, -3, 4, 4, 5, -5, -4, -2, -5, -4, 0, -2, -5, 4, 4, -3, -1, 2),$
$s_1 = (1, -3, -2, 3, 3, 3, -3, -3, 5, 0, 0, -2, -2, -2, -4, -2, 0, -2, 2, -1, 5, -1, 2, 5, 0, 2, -3, -4, 0, 5, 4, -1).$
Note that even for wrong keys (which have values larger than 5) the decryption yields correct values more often than wrong. (With probability around 55%).
Executing Commands
Now that we have the private key, we can execute arbitrary commands on server side. After figuring out the protocol and Twisted API, the following script was written:
from sage.all import * import asn1 import numpy as np from struct import pack from sock import Sock from sexec import op, Cipher, algorithms, modes, default_backend Q = 929 R = PolynomialRing(GF(Q), name='x') x = R.gen() S = R.quotient(x**32 + 1) a = [592, 476, 894, 411, 843, 634, 904, 322, 424, 368, 164, 47, 698, 778, 222, 680, 683, 384, 102, 161, 243, 224, 768, 137, 659, 28, 189, 335, 167, 67, 517, 701] pk = [558, 630, 505, 864, 186, 509, 81, 752, 167, 254, 907, 484, 279, 762, 200, 810, 640, 402, 549, 850, 310, 376, 48, 306, 158, 178, 497, 254, 21, 259, 329, 564] s0 = [-2, 4, 0, -5, 2, -4, 4, -5, 0, -2, 0, -1, -1, -4, -2, -3, 4, 4, 5, -5, -4, -2, -5, -4, 0, -2, -5, 4, 4, -3, -1, 2] s1 = [1, -3, -2, 3, 3, 3, -3, -3, 5, 0, 0, -2, -2, -2, -4, -2, 0, -2, 2, -1, 5, -1, 2, 5, 0, 2, -3, -4, 0, 5, 4, -1] def read_string(): n = f.read_until_re(r"(\d+):") n = int(n) s = f.read_nbytes(n) assert f.read_nbytes(1) == "," return s def mymul(a, b): a = list(a) b = list(b) return vector(ZZ, list(S(a)*S(b))) f = Sock("sexec.pwning.xxx 9999") # f = Sock("127.1 9999") s = read_string() iv0 = read_string() print "s", s.encode("hex") print "iv0", iv0.encode("hex") res = asn1.decoder.decode(s, asn1Spec=asn1.Ciphertext()) pub, enc = res[0] pub = vector(ZZ, asn1.bitstring_to_ints(pub, Q)) enc = vector(ZZ, asn1.bitstring_to_ints(enc, Q)) print "pub", pub print "enc", enc res = (enc - mymul(pub, s0)) % Q recovered = [1 - int(v < Q//4 or v > Q - Q//4) for v in res] secret = "".join(map(chr, np.packbits(np.array(recovered)))) print "SECRET", recovered, secret.encode("hex") aes_key = secret + '\x00\x01\x02\x03\x04\x05\x06\x07\x08\x09\x0A\x0B' iv1 = 0 def send_enc_string(s): global iv1 iv = iv0 + pack(">I", iv1) encryptor = Cipher( algorithms.AES(aes_key), modes.GCM(iv, min_tag_length=4), default_backend()).encryptor() cipher = encryptor.update(s) + encryptor.finalize() tag = encryptor.tag tosend = tag[:4] + cipher f.send("%d:%s," % (len(tosend), tosend)) iv1 += 1 send_enc_string("/bin/bash") send_enc_string("id\n") send_enc_string("cat flag.txt\n") f.interact() |
Run it:
51:uid=1001(sexec) gid=1001(sexec) groups=1001(sexec) ,20:quantum_was_so_2015 |
So, the flag is “quantum_was_so_2015“.
Links:
On Ideal Lattices and Learning With Errors Over Rings (slides)
The Learning with Errors Problem (survey)
