2024 Cyber Apocalypse: Permuted

Challenge Information

Attribute	Details
Event	2024 Cyber Apocalypse
Category	Crypto
Challenge	Permuted
Difficulty	Hard

Permuted implements a cryptosystem based on Diffie-Hellman key exchange over permutation groups (S_{50000}). While the cryptographic group is mathematically interesting, researchers discovered a polynomial-time discrete logarithm algorithm for permutation groups. The challenge requires implementing this DLP algorithm to recover the private exponent, compute the shared secret, and decrypt the AES-encrypted flag.

Analysis

The challenge structure:

Generator: A permutation g on 50,000 elements
Public Key A: A = g^a (mod the group operation)
Public Key B: B = g^b (mod the group operation)
Shared Secret: C = A^b = B^a = g^(a*b)
Encryption: AES-256-CBC with key derived from SHA256(C)

The vulnerability: A 2018 paper by researchers demonstrated that the DLP is efficiently solvable in permutation groups using cycle decomposition.

Solution

Step 1: Implement Cycle Detection

def cycles(self):
    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

Step 2: Implement DLP for Permutations

from math import gcd
from functools import reduce

def lcm(a, b):
    return a * b // gcd(a, b)

def crt(moduli, remainders):
    """Chinese Remainder Theorem"""
    total = 0
    prod = reduce(lambda a, b: a * b, moduli)
    for mod, rem in zip(moduli, remainders):
        p = prod // mod
        total += rem * p * pow(p, -1, mod)
    return total % prod, prod

def dlp(g, h):
    """Discrete Log Problem solver for permutation groups"""
    g_cycles = g.cycles()
    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)))

    First = []
    Second = []

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

    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]))

    alpha = crt(L, D)
    return int(alpha[0])

Step 3: Decrypt the Flag

from Crypto.Cipher import AES
from hashlib import sha256

# Load the permutation data from output.txt
with open('output.txt') as f:
    exec(f.read())

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

# Solve DLP to find 'a'
a = dlp(g, A)

# Compute shared secret
C = B ** a

# Derive decryption key
sec = tuple(C.mapping)
sec = hash(sec)
sec = long_to_bytes(sec)

h = sha256()
h.update(sec)
key = h.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)

Key Concepts

Permutation Groups

A permutation is a bijection from a set to itself
Group operation is function composition
S_n is the symmetric group of all permutations on n elements

Cycle Decomposition

Every permutation can be decomposed into disjoint cycles
A cycle (1 3 5) means: 1→3, 3→5, 5→1
Cycles are fundamental to the DLP algorithm

DLP in Permutation Groups

The algorithm works by:

Computing cycle decomposition for both g and h
Determining how h’s cycles relate to g’s cycles
Using cycle lengths and position shifts with CRT to recover the exponent

Key Takeaways

Novel cryptographic groups don’t guarantee security
Research papers should be reviewed before deployment
Permutation groups have efficiently computable discrete logarithms
Abstract algebra provides powerful tools for cryptanalysis
Always validate mathematical assumptions in cryptographic constructions