[Hard] Permuted

Permuted

​ 5^th Jan 2024 / Document No. D24.102.31

​ Challenge Author(s): ir0nstone

Synopsis

Permuted is a Hard crypto challenge that involves an implementation of the Diffie-Hellman Key Exchange in the symmetric group $S_n$. The player must solve the DLP for that specific group.

Description:

You drop to the ground as a voltaic mist of energy surrounds you; within it are the Aranaya, reflections of your emotions that break into the physical world from the spiritual realm. Love, hate, pain and more writhe and dance before your eyes in an endless storm. As one tears into your soul, a lightning bolt strikes your inner being and the emotion remoulds into another. Startled and wide-eyed, you recognise an undeniable truth: they are all reflections of one another, an ecosystem of your being that you could lose forever. Consciousness leaves you as the psychedelic show whirls on. To retain your self, you must brave the storm: a cyclone of patterns, an infinitude of permutations.

Skills Required

• An understanding of the Diffie-Hellman Key Exchange
• Basic Group Theory

Skills Learned

• Permutation Groups
• Basic Research Skills
• Implementing mathematical algorithms in Python

Enumeration

We are given the following script:

from Crypto.Cipher import AES
from Crypto.Util.Padding import pad
from Crypto.Util.number import long_to_bytes

from hashlib import sha256
from random import shuffle

from secret import a, b, FLAG

class Permutation:
    def __init__(self, mapping):
        self.length = len(mapping)

        assert set(mapping) == set(range(self.length))     # ensure it contains all numbers from 0 to length-1, with no repetitions
        self.mapping = list(mapping)

    def __call__(self, *args, **kwargs):
        idx, *_ = args
        assert idx in range(self.length)
        return self.mapping[idx]

    def __mul__(self, other):
        ans = []

        for i in range(self.length):
            ans.append(self(other(i)))

        return Permutation(ans)

    def __pow__(self, power, modulo=None):
        ans = Permutation.identity(self.length)
        ctr = self

        while power > 0:
            if power % 2 == 1:
                ans *= ctr
            ctr *= ctr
            power //= 2

        return ans

    def __str__(self):
        return str(self.mapping)

    def identity(length):
        return Permutation(range(length))


x = list(range(50_000))
shuffle(x)

g = Permutation(x)
print('g =', g)

A = g**a
print('A =', A)
B = g**b
print('B =', B)

C = A**b
assert C.mapping == (B**a).mapping

sec = tuple(C.mapping)
sec = hash(sec)
sec = long_to_bytes(sec)

hash = sha256()
hash.update(sec)

key = hash.digest()[16:32]
iv = b"mg'g\xce\x08\xdbYN2\x89\xad\xedlY\xb9"

cipher = AES.new(key, AES.MODE_CBC, iv)

encrypted = cipher.encrypt(pad(FLAG, 16))
print('c =', encrypted)

The Mathematics: Permutation Groups

The script creates a class Permutation which models a mathematical permutation. A permutation is essentially a mapping that takes an input and returns an output. They are typically written like this:

$$p = \begin{pmatrix} 1 & 2 & 3\\ 2 & 3 & 1 \end{pmatrix}$$

This means that

$$\begin{align} p(1) &= 2\\ p(2) &= 3\\ p(3) &= 1 \end{align}$$

$p$ is a permutation of the permutation group $S_3$, the group of all permutations that can take a set of 3 different inputs. The set of possible inputs to a permutation in the permutation group $S_n$ is $n$, and the set of possible outputs is also the set of possible inputs - a permutation essentially takes an integer in the range $[1,n]$ and maps it to an integer in the range $[1,n]$ in a one-to-one relationship.

But why does this form a group? Well, the binary operation of $S_n$ is function composition, where we combine two functions. Taking another example from the above link:

$$q = \begin{pmatrix} 1 & 2 & 3\\ 3 & 2 & 1 \end{pmatrix}$$

Note that $2$ can map to $2$! But what is $p \cdot q$? Well, let's see:

$$\begin{align} p(q(1)) &= p(3) = 1\\ p(q(2)) &= p(2) = 3\\ p(q(3)) &= p(1) = 2 \end{align}$$

So we can see that

$$p \cdot q = \begin{pmatrix} 1 & 2 & 3\\ 1 & 3 & 2 \end{pmatrix}$$

Which is also in $S_3$. We can continue this and prove that all $S_n$ are closed (and also fit the other 3 criteria to be a valid group!) but we're going to take it as a given that $S_n$ is a group.

Permutation Groups in Python

But how does the python class represent a permutation group? Well, it inputs the bottom row of the matrices above:

def __init__(self, mapping):
    self.length = len(mapping)

    assert set(mapping) == set(range(self.length))     # ensure it contains all numbers from 0 to length-1, with no repetitions
    self.mapping = list(mapping)

it takes in a mapping variable, and updated the length of the permutation to the length of said mapping, and also checks that the set of the mapping is equal to the set of the range from 0 to length. This is a small check, and it can likely be bypassed, but bypassing it is not part of the challenge - it just gives a better idea to the player of what the class represents.

An important note here is that the Permutation class with a mapping of length $n$ actually has all of its elements in the range $[0, length-1]$ not $[1,length]$. The mathematical principle, however, is the same. Then there is a __call__() magic method:

def __call__(self, *args, **kwargs):
	idx, *_ = args
    assert idx in range(self.length)
    return self.mapping[idx]

Inputting a number like 2 will simply return the value corresponding to index 2 in the mapping list, so calling the class instance will just execute the function on the input. For example:

p = Permutation([2, 3, 1])
print(p(2))		# outputs 1

Composition of these permutation functions are dealt with using the __mul__() magic method:

def __mul__(self, other):
    ans = []

    for i in range(self.length):
        ans.append(self(other(i)))

    return Permutation(ans)

The self(other(i)) is equivalent to the $p(q(i))$ from above. If we tried to replicate the example from earlier:

p = Permutation([2, 3, 1])
q = Permutation([3, 2, 1])
comp = p * q
print(comp.mapping)		# [1, 3, 2]

And finally __pow__() allows you to compose the permutation function with itself. The algorithm here is a typical double-and-add algorithm, which is generic for all groups:

def __pow__(self, power, modulo=None):
    ans = Permutation.identity(self.length)
    ctr = self

    while power > 0:
        if power % 2 == 1:
            ans *= ctr
        ctr *= ctr
        power //= 2

    return ans

__str__() just returns the string form of the list, which is helpful for printing it out. identity() returns the identity permutation of a certain length, that is the permutation

$$I = \begin{pmatrix} 1 & 2 & 3 & \dots\\ 1 & 2 & 3 & \dots \end{pmatrix}$$

The Cryptosystem

The crypto part is essentially an implementation of DHKE, but over $S_n$ instead of $\mathbb{F}_p$. The shared secret is then converted into a key for AES, which then encrypts the flag.

g = Permutation(x)
print('g =', g)

A = g**a
print('A =', A)
B = g**b
print('B =', B)

C = A**b
assert C.mapping == (B**a).mapping

# from here it's just calculating a key and encrypting the flag
sec = tuple(C.mapping)
sec = hash(sec)
sec = long_to_bytes(sec)

hash = sha256()
hash.update(sec)

key = hash.digest()[16:32]
iv = b"mg'g\xce\x08\xdbYN2\x89\xad\xedlY\xb9"

cipher = AES.new(key, AES.MODE_CBC, iv)

encrypted = cipher.encrypt(pad(FLAG, 16))
print('c =', encrypted)

output.txt gives us $g,A,B$ and the encrypted ciphertext. Evidently, the point of the challenge is to solve the DLP in $S_n$.

Solution - Solving the DLP

After coming up with the basic idea, I discovered that a group of researchers suggested a cryptosystem based on $S_n$ in this paper in 2008. It seemed logical to me that the DLP is easy in $S_n$ (that was meant to be the point of the challenge!), and I was proven right by this 2018 paper, which provided a DLP algorithm for $S_n$. The actual mathematics of the algorithm are interesting, and they make intuitive sense, but I won't really delve into them here with any depth. Essentially it works on the principle of splitting a permutation into disjoint cycles, which is very common for all sorts of maths. You can then calculate the number of steps taken to get from the part of the cycle an index started at $g$ to the part started at $h = g^\alpha$ and get the modulo the length of the cycle, then combine with CRT to retrieve $\alpha$. I recommend reading the paper for more, but all we need to do is (a) implement a method for calculating cycles and (b) implement the DLP algorithm. The authors do not provide any code, which is good, as it's an excellent exercise.

We will add a cycles() function to the Permutation class:

def cycles(self):
    # naive implementation, but it works!
    cycles = []
    used = set()

    for i in self.mapping:
        if i in used:
            continue

        curr_cycle = [i]
        used.add(i)

        idx = self(i)
        while idx not in used:
            curr_cycle.append(idx)
            used.add(idx)
            idx = self(idx)

        cycles.append(curr_cycle)

    return cycles

And then implement the DLP algorithm:

def dlp(g, h):
    # g is base
    # h is result
    g_cycles = g.cycles()
    h_cycles = h.cycles()

    print('g cycles:', g_cycles)
    print('h cycles:', h_cycles)

    G = []
    H = []

    for i in range(g.length):
        for j, c in enumerate(g_cycles):
            if i in c:
                G.append((j, c.index(i)))

        for j, c in enumerate(h_cycles):
            if i in c:
                H.append((j, c.index(i)))

    print('G:', G)
    print('H:', H)

    First = []
    Second = []

    for c in h_cycles:
        First.append(c[0])
        Second.append(c[1 % len(c)])

    print('first:', First)
    print('second:', Second)

    D = []
    L = []
    for i in range(len(Second)):
        dist = G[Second[i]][1] - G[First[i]][1]
        D.append(dist)
        L.append(len(h_cycles[i]))

    print('D:', D)
    print('L:', L)

    alpha = crt(L, D)

    return int(alpha[0])

And finally we can solve the DLP and retrieve the flag!

with open('output.txt') as f:
    exec(f.read())

g = Permutation(g)
A = Permutation(A)
B = Permutation(B)

a = dlp(g, A)

# decrypt
C = B**a

sec = tuple(C.mapping)
sec = hash(sec)
sec = long_to_bytes(sec)

hash = sha256()
hash.update(sec)

key = hash.digest()[16:32]
iv = b"mg'g\xce\x08\xdbYN2\x89\xad\xedlY\xb9"

cipher = AES.new(key, AES.MODE_CBC, iv)

decrypted = cipher.decrypt(c)
print('Flag:', decrypted)

The DLP solver takes around 70 seconds to run on my computer. We eventually get that a = 839949590738986464, which is far too huge to brute force with such a large permutation group!