Writeup

FlagYard Locker — Writeup

Mohammed-Amine Bouaafia

November 20, 2025

10 min read

reverse-engineering xor permutation glibc

Locker — writeup

This writeup explains the Locker challenge in plain language so anyone can understand what happened and why the file decrypts. I start with the basic idea you must know (XOR), then walk through how the program scrambled bytes, why the scramble is reversible, and finally give a simple script you can run to recover the original file.

If you like hands-on, there are small examples and a compact Python script at the end. Everything is explained step by step.

TL;DR (short summary)

The program shuffles indices using a fixed random seed (srand(0x1337) → deterministic).
For each output byte, it XORs together 123 bytes from the input by “walking” the shuffled indices.
XOR has a useful property: identical values cancel (A ⊕ A = 0). That lets us cancel overlapping parts of two nearby outputs.
By splitting the permutation into cycles and using that canceling trick, we can solve for the original bytes.
I reproduce the shuffle using the system libc (so rand() matches), solve every cycle, and write the decrypted PNG.

Final recovered flag (from the decrypted PNG)

Part 1 — What does ⊕ (XOR) mean? (very plain English)

The symbol ⊕ means XOR, short for exclusive OR.

For single bits:
- 0 ⊕ 0 = 0
- 0 ⊕ 1 = 1
- 1 ⊕ 0 = 1
- 1 ⊕ 1 = 0

Think of XOR as a toggle:

XOR with 0 → does nothing (keeps the bit).
XOR with 1 → flips the bit.

Important properties (why we use XOR in reversals):

a ⊕ a = 0 (XORing a value with itself cancels it).
a ⊕ 0 = a (XOR with zero keeps the value).
XOR is associative and commutative (order doesn’t matter).
These properties let you cancel repeated terms and rearrange XOR sums easily.

Examples:

Byte example: 0x55 ⊕ 0xFF = 0xAA
ASCII example: ‘A’ (0x41) ⊕ 0x20 = ‘a’ (0x61) — toggles uppercase to lowercase.

Tiny Python demo:

1
a = 0x55
2
b = 0xFF
3
print(hex(a ^ b))  # 0xaa
4

5
print(chr(ord('A') ^ 0x20))  # prints 'a'

Part 2 — What the Locker binary does (plain steps)

It creates an array P of indices [0, 1, 2, …, N-1].
It calls srand(0x1337) — a fixed seed. That means the following rand() calls are the same every run (on the same libc).
It shuffles P using a Fisher–Yates style method, where each swap uses rand().
For each output position, it:
- Starts at some index idx.
- Repeats 123 times:
  - XORs the input byte at position P[idx] into an accumulator.
  - Sets idx = P[idx] (so it follows the permutation like a linked list).
- Stores accumulator as the output byte for that position.

Because the seed is fixed, the shuffle is reproducible — we can rebuild P exactly and then reverse the transformation.

Part 3 — Why the transform is reversible (intuition)

Rewrite the behavior on a single permutation cycle:

Look at one cycle of the permutation. Put the input bytes in cycle order: X[0], X[1], …, X[L-1] (L is cycle length).
The program produces outputs Y[i] which equal the XOR of the 123 bytes after position i:

Y[i] = X[i+1] ⊕ X[i+2] ⊕ … ⊕ X[i+123] (indices wrap around modulo L)
Now look at Y[i] and Y[i−1]:
- Y[i−1] = X[i] ⊕ X[i+1] ⊕ … ⊕ X[i+122]
XOR Y[i] with Y[i−1]:
- Y[i] ⊕ Y[i−1] = (X[i+1] ⊕ … ⊕ X[i+123]) ⊕ (X[i] ⊕ … ⊕ X[i+122])
- Every term from X[i+1] to X[i+122] appears twice → they cancel (because A ⊕ A = 0).
- Leftover terms: X[i+123] ⊕ X[i]

So: X[i+123] = X[i] ⊕ (Y[i] ⊕ Y[i−1])

This is a recurrence: it links values separated by 123 positions in the cycle. Jumping repeatedly by 123 splits a cycle into gcd(123, L) independent chains. Each chain can be propagated, but each chain has one unknown constant to solve for. Those constants are found by substituting back into the original Y equations and solving a small linear system (over bytes, using XOR arithmetic). Because the system is small (size = gcd(123, L)), it’s computationally easy.

Short analogy: imagine a long loop of beads. Each bead’s color is defined relative to beads 1..123 ahead. Comparing two neighboring sums cancels the middle beads and leaves only the bead that entered and the bead that left the window. That gives a simple link you can walk along.

Part 4 — A tiny worked example (small numbers so it’s easy)

To see the idea with small numbers, pretend the code XORs 3 bytes (not 123) and we have a tiny cycle.

Let cycle length L = 5, window = 3 (for example only).

Then: Y[i] = X[i+1] ⊕ X[i+2] ⊕ X[i+3]

Y[i] ⊕ Y[i−1] = (X[i+1] ⊕ X[i+2] ⊕ X[i+3]) ⊕ (X[i] ⊕ X[i+1] ⊕ X[i+2]) = X[i+3] ⊕ X[i]

So X[i+3] = X[i] ⊕ (Y[i] ⊕ Y[i−1]) — same pattern with smaller numbers. If you jump by 3 around the cycle you get chains and can solve.

Part 5 — Practical steps to decrypt (what I did)

Reproduce the permutation P using the same rand() sequence:
- Call srand(0x1337) and the same rand() calls in the same order the binary does.
- I used ctypes to call libc.srand and libc.rand on Linux.
Find cycles in P.
For each cycle:
- Build Y (the known encrypted bytes from the file) placed in cycle order.
- Compute Z[k] = Y[k] ⊕ Y[k−1].
- Propagate X values along each chain defined by stepping +123, using Z to compute relative values.
- Build and solve a tiny XOR linear system (size = gcd(123, L)) to get constants for each chain.
- Reconstruct plaintext bytes and place them back into the output buffer.
Save output as flag.png.

Part 6 — Simple Python solver (run on Linux)

This version is straightforward and commented so you can follow each step. It uses ctypes to call the system libc rand/srand so the shuffle matches the binary’s shuffle on glibc.

1
import ctypes
2
import math
3
import os
4
import sys
5

6
# Load libc to reproduce the exact random sequence used by the binary
7
try:
8
    libc = ctypes.CDLL("libc.so.6")
9
except OSError:
10
    print("Error: Could not load libc.so.6. Please run this on Linux.")
11
    sys.exit(1)
12

13
def get_permutation_table(size):
14
    """
15
    Replicates the shuffle logic from sub_4011e0 using libc rand
16
    """
17
    print(f"[*] Generating permutation table for size {size}...")
18

19
    # Replicate srand(0x1337)
20
    libc.srand(0x1337)
21

22
    # Initialize table with 0..size-1
23
    p_table = list(range(size))
24

25
    # Replicate the Fisher-Yates shuffle loop
26
    # The decompilation shows loop var_30 from 0 to size-2 (inclusive) (arg3 - 1 limit)
27
    for i in range(size - 1):
28
        # int32_t rdx_5 = rand() % (arg3 - (var_30 + 1)) + var_30 + 1;
29
        rand_val = libc.rand()
30
        swap_idx = (rand_val % (size - (i + 1))) + i + 1
31

32
        # Swap
33
        p_table[i], p_table[swap_idx] = p_table[swap_idx], p_table[i]
34

35
    return p_table
36

37
def solve_cycle(cycle_indices, encrypted_data, decrypted_buffer):
38
    """
39
    Solves the XOR summation for a single permutation cycle.
40
    Equation: Y[i] = XOR_SUM( X[i+1] ... X[i+123] ) (indices relative to cycle)
41
    """
42
    L = len(cycle_indices)
43

44
    # Extract the encrypted bytes corresponding to this cycle
45
    Y = [encrypted_data[idx] for idx in cycle_indices]
46

47
    # We derived that: X[(k + 123) % L] = X[k] ^ Y[k] ^ Y[k-1]
48
    # Let Z[k] = Y[k] ^ Y[k-1]
49
    # Then X[(k + 123) % L] = X[k] ^ Z[k]
50

51
    Z = [(Y[k] ^ Y[(k - 1) % L]) for k in range(L)]
52

53
    # The cycle might be split into multiple independent chains if gcd(123, L) > 1
54
    num_chains = math.gcd(123, L)
55

56
    # Temporary buffer for relative values (X_temp)
57
    X_temp = [0] * L
58

59
    # 1. Resolve relative values within each chain
60
    for leader in range(num_chains):
61
        curr = leader
62
        # We assume X_temp[leader] = 0. The real value is 0 ^ Constant_for_this_chain.
63
        # We propagate this assumption through the chain.
64
        while True:
65
            next_idx = (curr + 123) % L
66
            if next_idx == leader:
67
                break
68

69
            # X_next = X_curr ^ Z_curr
70
            X_temp[next_idx] = X_temp[curr] ^ Z[curr]
71
            curr = next_idx
72

73
    # 2. Solve for the unknown Constants (K) for each chain.
74
    # We set up a small linear system: M * K = B
75
    # We assume X[i] = X_temp[i] ^ K[chain_id]
76
    # Original Eq: Y[u] = Sum(X[u+j]) for j in 1..123
77

78
    matrix = []
79
    vector = []
80

81
    # We need 'num_chains' equations. We can just use the first 'num_chains' Y values.
82
    for u in range(num_chains):
83
        row = [0] * num_chains
84
        target_val = Y[u]
85

86
        # Reconstruct the summation based on our X_temp and Unknowns K
87
        for j in range(1, 124): # Loop 123 times
88
            cycle_idx = (u + j) % L
89

90
            # The value contributes X_temp[idx] to the XOR sum
91
            target_val ^= X_temp[cycle_idx]
92

93
            # It also contributes K[chain_id] to the XOR sum
94
            chain_id = cycle_idx % num_chains
95
            row[chain_id] ^= 1
96

97
        matrix.append(row)
98
        vector.append(target_val)
99

100
    # 3. Gaussian Elimination to find K values (Constants)
101
    # This solves the system over GF(2)
102
    k_values = [0] * num_chains
103

104
    # Forward elimination
105
    for i in range(num_chains):
106
        # Find pivot
107
        if matrix[i][i] == 0:
108
            for j in range(i + 1, num_chains):
109
                if matrix[j][i] == 1:
110
                    matrix[i], matrix[j] = matrix[j], matrix[i]
111
                    vector[i], vector[j] = vector[j], vector[i]
112
                    break
113

114
        # Eliminate lower rows
115
        if matrix[i][i] == 1:
116
            for j in range(i + 1, num_chains):
117
                if matrix[j][i] == 1:
118
                    for col in range(i, num_chains):
119
                        matrix[j][col] ^= matrix[i][col]
120
                    vector[j] ^= vector[i]
121

122
    # Back substitution
123
    for i in range(num_chains - 1, -1, -1):
124
        if matrix[i][i] == 1:
125
            sum_val = 0
126
            for j in range(i + 1, num_chains):
127
                if matrix[i][j] == 1:
128
                    sum_val ^= k_values[j]
129
            k_values[i] = sum_val ^ vector[i]
130

131
    # 4. Reconstruct final plaintext and write to buffer
132
    for k in range(L):
133
        chain_id = k % num_chains
134
        plaintext_byte = X_temp[k] ^ k_values[chain_id]
135

136
        original_file_index = cycle_indices[k]
137
        decrypted_buffer[original_file_index] = plaintext_byte
138

139
def main():
140
    filename = "flag.png.enc"
141

142
    if not os.path.exists(filename):
143
        print(f"Error: {filename} not found.")
144
        return
145

146
    with open(filename, "rb") as f:
147
        data = bytearray(f.read())
148

149
    filesize = len(data)
150
    print(f"[*] File size: {filesize} bytes")
151

152
    # 1. Regenerate the permutation
153
    p_table = get_permutation_table(filesize)
154

155
    # 2. Decompose permutation into cycles
156
    print("[*] Decomposing cycles...")
157
    visited = [False] * filesize
158
    decrypted_data = bytearray(filesize)
159

160
    cycles_found = 0
161

162
    for i in range(filesize):
163
        if visited[i]:
164
            continue
165

166
        # Trace a new cycle
167
        current_cycle = []
168
        curr = i
169
        while not visited[curr]:
170
            visited[curr] = True
171
            current_cycle.append(curr)
172
            curr = p_table[curr]
173

174
        # 3. Solve this cycle
175
        solve_cycle(current_cycle, data, decrypted_data)
176
        cycles_found += 1
177

178
        if cycles_found % 100 == 0:
179
            print(f"\r[*] Solved {cycles_found} cycles...", end="")
180

181
    print(f"\n[*] Finished. Recovered {cycles_found} cycles.")
182

183
    out_filename = "flag.png"
184
    with open(out_filename, "wb") as f:
185
        f.write(decrypted_data)
186

187
    print(f"[+] Decrypted file saved to: {out_filename}")
188

189
if __name__ == "__main__":
190
    main()

How to run:

Save as decrypt_locker.py.
Put flag.png.enc in the same directory.
Run on Linux: python3 decrypt_locker.py
Open flag.png with an image viewer.

Part 7 — Recap (simple story of what we did)

You saw a binary that shuffled indices with a fixed seed and XORed windows of input bytes.
XOR is a toggling operation that cancels duplicates. That cancellation is the key to reversing the windowed XOR.
By reproducing the permutation and solving along permutation cycles we can recover the original bytes.
The process is fully deterministic and straightforward to automate.

Final note and flag

This method recovers the PNG, which contains the flag:

FlagY{[redacted]}