CSAW Quals 2018 – holywater

This was my favorite crypto challenge from this year’s CSAW Quals (and probably my favorite crypto challenge that I’ve done in a while). On the surface, it’s relatively standard: we have a flag encrypted with some cryptosystem (along with a Python implementation of this cryptosystem) and we have to decrypt it. The cryptosystem itself is pretty unusual though, and involves some interesting math I haven’t really seen used much in other cryptosystems/crypto challenges (namely, octonion algebras).

Note: I’m sure this is based off of some existing cryptosystem (based on the naming of some of the variables, there seems to be some way to interpret it as a lattice-based cryptosystem, although this is not usually what I think of as a lattice-based cryptosystem). It’s not obvious to me what the “flaw” in the cryptosystem is, however, or how to repair it to get a working cryptosystem.

Reals, Complex Numbers, Quaternions and Octonions

 
As briefly mentioned above, this cryptosystem is based off of something called an octonion algebra. To understand the solution to this challenge it’s useful to understand some relevant properties of these objects.

  1. Real numbers. You’re probably familiar with these.
  2. Complex numbers. You’re likely also familiar with these. You get these by adding a square root of -1 (usually denoted i) to the reals. Every complex number is of the form a + bi, and can therefore be summarized by a pair of real numbers (a, b).
  3. Quaternions. Similar to complex numbers, the quaternions are a number system that can be constructed by adding 3 square roots of -1 to the reals, denoted i, j, and k. Similar to complex numbers, each quaternion is of the form a + bi + cj + dk and can be summarized by a 4-tuple of real numbers (a, b, c, d).

    Where quaternions qualitatively differ from reals and complex numbers is multiplication; multiplication with reals and complex numbers is commutative (xy = yx for all x and y), but multiplication with quaternions is not commutative. Notably, ij = k, but ji = -k (and symmetric identities hold for the other products of elements). This might be reminiscent of matrices, and indeed it is possible to represent quaternions as unitary 2-by-2 matrices (this is related to why quaternions are often used to represent 3-dimensional rotations).

  4. Octonions. Finally, we have octonions, which you can get by adding 7 new square roots of -1 to the real numbers (so they can be represented by 8-tuples of real numbers). Multiplication of octonions is, like quaternions, not commutative. Even worse than this however, is that multiplication of octonions is not even associative; there are x, y, z such that x(yz) \neq (xy)z. You can see the multiplication table for octonions here.

    Despite this, octonions still have a lot of nice structure. One particularly nice property they have (which we will need) is that they are alternative; if you look only at the subset of octonions which can be expressed in terms of (i.e. generated by) two octonions x and y, multiplication of elements in this subset is associative.

In abstract algebra, all of these objects are examples of algebras. An algebra is simply a vector space over some field where you can multiply two elements and get a new element. Complex numbers, quaternions, and octonions, are 2-dimensional, 4-dimensional, and 8-dimensional algebras over the real numbers respectively (the real numbers themselves can be considered as a “1-dimensional algebra over the reals”). It is possible (although there are some technicalities) to define these same number systems over any field, not just the reals. In the case of quaternions and octonions, these are referred to as quaternion algebras and octonion algebras. (For example, as we’ll see later, the objects in the cryptosystem are elements of the octonion algebra over the finite field GF(p) for some large prime p).

These algebras also all share one important property: they are all composition algebras. All this means is that there is some non-trivial quadratic norm function N(x) mapping the algebra to the underlying field such that for all x and y, N(xy) = N(x)N(y). For real numbers, the norm is just the identity map N(x) = x. For complex numbers, you might be familiar with the norm function N(a + bi) = a^2 + b^2. It turns out that quaternions and octonions also have similar norm functions, where N(a + bi + cj + dk) = a^2 + b^2 + c^2 + d^2 is a norm for the quaternions, and the sum of the squares of the coefficients is also a norm for the octonions.

It’s a very deep result in algebra that these examples — the real numbers, the complex numbers, quaternions, and octonions — are essentially the only instances of composition algebras. That is, any 8-dimensional composition algebra is isomorphic (under a “change of basis”) to an octonion algebra, any 4-dimensional composition algebra isomorphic to a quaternion algebra, and so on.

We don’t really need the full strength of this fact, but it does let us quickly reason about octonions and subsets of the octonions. For example, here’s one quick consequence of this fact that we will use later. Remember that the octonions are alternative, which means that multiplication is associative among the set of elements generated by two octonions x and y (which forms a subalgebra of the octonions). Since this subalgebra is still a composition algebra, it must be either 1-dimensional, 2-dimensional, 4-dimensional, or 8-dimensional. Furthermore, since it is associative, it’s not an octonion algebra, so it cannot be 8-dimensional, and must be 1-, 2-, or 4-dimensional (if x and y are linearly independent, it is also not 1-dimensional).

The cryptosystem

Let’s return to the challenge. Here is a snippet of the Lattice class in the provided implementation of the cryptosystem.

class Lattice:
  def __init__(self,i0,i1,i2,i3,i4,i5,i6,i7):
    self.v0 = i0
    self.v1 = i1
    self.v2 = i2
    self.v3 = i3
    self.v4 = i4
    self.v5 = i5
    self.v6 = i6
    self.v7 = i7
    self.exp = 4294967279

  def __mod__(self, n):
    return Lattice(self.v0 % n, self.v1 % n, self.v2 % n, self.v3 % n,
                   self.v4 % n, self.v5 % n, self.v6 % n, self.v7 % n)

  def __add__(self, otro):
    return Lattice(self.v0 + otro.v0,
                   self.v1 + otro.v1,
                   self.v2 + otro.v2,
                   self.v3 + otro.v3,
                   self.v4 + otro.v4,
                   self.v5 + otro.v5,
                   self.v6 + otro.v6,
                   self.v7 + otro.v7) % self.exp

  def dilate(self, fact):
    return Lattice(self.v0 * fact,
                   self.v1 * fact,
                   self.v2 * fact,
                   self.v3 * fact,
                   self.v4 * fact,
                   self.v5 * fact,
                   self.v6 * fact,
                   self.v7 * fact) % self.exp

  def __mul__(self, otro):
    x = [self.v0, self.v1, self.v2, self.v3, self.v4, self.v5, self.v6, self.v7]
    y = [otro.v0, otro.v1, otro.v2, otro.v3, otro.v4, otro.v5, otro.v6, otro.v7]
    return Lattice (x[0] * y[0] - x[1] * y[1] - x[2] * y[2] - x[3] * y[3]
                  - x[4] * y[4] - x[5] * y[5] - x[6] * y[6] - x[7] * y[7],
                    x[0] * y[1] + x[1] * y[0] + x[2] * y[4] + x[3] * y[7]
                  - x[4] * y[2] + x[5] * y[6] - x[6] * y[5] - x[7] * y[3],
                    x[0] * y[2] - x[1] * y[4] + x[2] * y[0] + x[3] * y[5]
                  + x[4] * y[1] - x[5] * y[3] + x[6] * y[7] - x[7] * y[6],
                    x[0] * y[3] - x[1] * y[7] - x[2] * y[5] + x[3] * y[0]
                  + x[4] * y[6] + x[5] * y[2] - x[6] * y[4] + x[7] * y[1],
                    x[0] * y[4] + x[1] * y[2] - x[2] * y[1] - x[3] * y[6]
                  + x[4] * y[0] + x[5] * y[7] + x[6] * y[3] - x[7] * y[5],
                    x[0] * y[5] - x[1] * y[6] + x[2] * y[3] - x[3] * y[2]
                  - x[4] * y[7] + x[5] * y[0] + x[6] * y[1] + x[7] * y[4],
                    x[0] * y[6] + x[1] * y[5] - x[2] * y[7] + x[3] * y[4]
                  - x[4] * y[3] - x[5] * y[1] + x[6] * y[0] + x[7] * y[2],
                    x[0] * y[7] + x[1] * y[3] + x[2] * y[6] - x[3] * y[1]
                  + x[4] * y[5] - x[5] * y[4] - x[6] * y[2] + x[7] * y[0]) % self.exp

As we can see, the Lattice class implements some 8-dimensional algebra over GF(p), where p = 4294967279. It is not too hard to check that this algebra is also a composition algebra (the norm just being the sum of the squares of the components). It follows that this must be isomorphic to the octonion algebra over GF(p)! Let’s call this algebra \mathcal{A}.

Now let’s briefly describe what the rest of the cryptosystem does:

  1. The cryptosystem starts by generating two random elements g and p of \mathcal{A}.
  2. The cryptosystem then generates two random (degree ~64) polynomials V_A and V_B, along with random elements e_A, f_A, e_B, f_B of [1, 256].
  3. The cryptosystem then computes

    c = (V_A(g)^{e_A} \cdot p) \cdot V_A(g)^{f_A}

    and

    j = V_B(g)^{e_B} \cdot (p \cdot V_B(g)^{f_B})

    The cryptosystem publicly reveals g, p, c, j to us.

  4. Finally, the cryptosystem computes

    x = V_B(g)^{e_B} \cdot (((V_A(g)^{e_A} \cdot p) \cdot V_A(g)^{f_A}) \cdot V_B(g)^{f_B})

    and uses this value to encrypt the flag.

This might look complicated, but one nice thing is that very few of the details in this protocol actually matter. To begin, note that all of these expressions above are generated by g and p, so they belong to an associative sub-algebra of the octonions. These means we can throw out all parentheses in the above expressions (in particular, the left and right methods of the Whomst class do the exact same thing).

From our analysis above, we know something further; the subalgebra generated by g and p must be either 1, 2, or 4 dimensional; it turns out (unsurprisingly) it is 4-dimensional. This means we can choose some 4-dimensional basis for the sub-algebra and write all our our expressions in this basis. We will return to this in a moment (it turns out we will want to consider two different bases).

Next, let’s look at our polynomials of g like V_{A}(g)^{e_A}. These elements belong to the sub-algebra generated by g. Note that in addition to being associative, this algebra is also commutative (since powers of g commute with themselves), so it cannot be a quaternion algebra, and must be 1 or 2 dimensional. It turns out to be 2-dimensional (since g is not a multiple of 1). This means that we can write a general expression V_{A}(g)^{e_A} as \ell_0 + \ell_1 g for some \ell_0, \ell_1 \in GF(p).

Finally, let’s generalize j slightly, and define

J(u) = V_B(g)^{e_B} u V_B(g)^{f_B}

(We’ve removed parens since everything is associative). Note that j = J(p) and x = J(c). Furthermore, J(u) is a linear function of u.

It turns out we have enough information to specify J precisely. Write V_B(g)^{e_B} as \ell_0 + \ell_1g and write V_B(g)^{f_B} as r_0 + r_1 g. Then

J(u) = (\ell_0 + \ell_1g) u (r_0 + r_1 g) = \ell_0r_0 u + \ell_0r_1 ug + \ell_1r_0 gu + \ell_1r_1 gug

Since J is linear, it suffices to specify how it acts on a basis. It is easy to check that \mathcal{B}_1 = \{1, g, p, gp\} is a valid basis, so we’ll figure out how J acts on this basis. Note that (since things generated by g commute), J(g) = gJ(1), and J(gp) = gJ(p). We also know that J(p) = j (which we are given) so it suffices to find J(1).

Well, from the above formula, we know that

J(1) = \ell_0r_0 + (\ell_0r_1 + \ell_1r_0) g + \ell_1r_1 g^2

Therefore, if we can find the values of \{\ell_0r_0, \ell_0r_1, \ell_1r_0, \ell_1r_1\}, we can compute J(1) and we’ll be done. But note that

j = J(p) = \ell_0r_0 p + \ell_0r_1 pg + \ell_1r_0 gp + \ell_1r_1 gpg

By writing j in the \mathcal{B}_2 = \{p, pg, gp, gpg\} basis (and we can confirm it is indeed a basis), we immediately obtain these desired values, and can compute J(1).

Finally, once we have this description of J, it is straightforward to write c in the \mathcal{B}_1 basis and compute x = J(c) and decrypt the flag.

Included below is some SAGE code which implements this algorithm (note: some of the notation in the below code is swapped from that used in the above exposition).

from cryptography.fernet import Fernet
from lattice import Lattice

GHEX = 'e002af4dec89cd6c063bca41ac24cb0636a23dcd00641990a58aafa89a62e386'
PHEX = '5e91a05d58e23a1d891f576040ff7bc37bfbfd1d1fcf92c02cbd0f4cdc8ea284'
CHEX = '15ff1eda110c670bdd76dc28e222d80aedaa5c6f82ec15758d8f04e4508b34fb'
JHEX = '41ea7e0f2d4e4491fac0aabdd8cb1d4613bef7a29ab7fe0d60b971d3f61ad918'

CIPHERTEXT = 'gAAAAABbm_jeozf2NnpedlvFzatVxOqhalOf5w1aZzgOLZ2Qx9sBakb9CK_hAAPbfjD0GDXQUrdnl_0SGQw1U1c4oTRJfO_awTloqXVUTBpHGxhP0BGWeN0='
P = 4294967279

def write_in_basis(basis, v):
    mat = matrix(GF(P), basis)
    assert mat.rank() == 4
    b = matrix(GF(P), [v])    
    return list(mat.solve_left(b)[0])
    

def solve():
    g = Lattice.from_str(GHEX)
    p = Lattice.from_str(PHEX)
    c = Lattice.from_str(CHEX)
    j = Lattice.from_str(JHEX)
    one = Lattice.absolute()
    
    basis = [p.coords(), (g*p).coords(), (p*g).coords(), (g*(p*g)).coords()]
    
    a = write_in_basis(basis, c.coords())
    c1 = one.dilate(a[0]) + g.dilate(a[1] + a[2]) + (g*g).dilate(a[3])
    
    basis2 = [one.coords(), g.coords(), p.coords(), (g*p).coords()]
    b = write_in_basis(basis2, j.coords())
    ans = (one.dilate(b[0]) + g.dilate(b[1]))*c1 + (one.dilate(b[2]) + g.dilate(b[3]))*c

    key = str(ans).decode('hex').encode('base64')
    f = Fernet(key)
    msg = f.decrypt(CIPHERTEXT)
    print msg
    

if __name__ == '__main__':
    solve()
Advertisements

2 thoughts on “CSAW Quals 2018 – holywater

  1. It’s based on HK17, from the NIST PQC. The lattice stuff (and the isogeny stuff) is a deliberate red herring, you can’t interpret it that way afaik

    Like

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s