Woow

Platform: duckerz | Category: Crypto | Type: Challenge | Difficulty: Medium | OS: NA | Author: XESXOR | Date: 2026-01-09 | Status: Solved Techniques: bipartite_graph_bfs, key_offset_bruteforce, xor_equation_analysis

Summary

Task: XOR encryption with repeating key and repeated plaintext. Solution: Factor ciphertext length to find key_size, build bipartite graph constraints, solve via BFS with single-byte brute-force, decode Base64 result.

Woow - duckerz CTF

Description

"Что-то зашифровано. Что-то нужно расшифровать. Наверное. Или нет. Разберись сам."

(Translation: "Something is encrypted. Something needs to be decrypted. Probably. Or not. Figure it out yourself.")

Files: enc.py, output.txt

Analysis

Encryption Algorithm

 python read-only • copy allowed Copy
import os
import random
from Crypto.Util.strxor import strxor

def read_file(filepath):
    with open(filepath, 'rb') as f:
        return f.read()

def generate_key(size):
    return os.urandom(size)
‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

def repeat_data(data, factor):
    return data * factor

def encrypt(data, key):
    return strxor(data, key)

def write_file(filepath, content):
    with open(filepath, 'w') as f:
        f.write(content.hex())

if __name__ == "__main__":
    input_data = read_file('input.txt')
    key_size = random.randint(12, 44)
    encryption_key = generate_key(key_size)
    expanded_key = repeat_data(encryption_key, len(input_data))
    expanded_data = repeat_data(input_data, key_size)
    encrypted_text = encrypt(expanded_data, expanded_key)
    write_file('output.txt', encrypted_text)

‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

Key Observations

1. Double repetition:

   • expanded_data = input_data * key_size - plaintext is repeated key_size times
   • expanded_key = key * len(input_data) - key is repeated input_len times

2. Ciphertext length:

   • len(encrypted) = len(input_data) * key_size = 988 bytes

3. XOR equation for position i:

   encrypted[i] = input_data[i % input_len] ^ key[i % key_size]
   

Determining Parameters

Factorization of 988:

• 988 = 4 × 247 = 4 × 13 × 19
• 988 = 13 × 76 = 19 × 52 = 26 × 38 = 38 × 26 ‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

Given key_size ∈ [12, 44]:

• Possible values: {13, 19, 26, 38}

Solution

Step 1: Determining the Correct key_size

For positions i and i+input_len we have:

encrypted[i] ^ encrypted[i+input_len] = key[i % key_size] ^ key[(i+input_len) % key_size]

If key_size is correct, then for each pair of key positions (k1, k2) the value key[k1] ^ key[k2] should be constant.

Result: Only key_size=19 (and correspondingly input_len=52) produced consistent equations.

Step 2: Building the Constraint System

‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

We build a bipartite graph:

• Left part: key positions (0..18)
• Right part: plaintext positions (0..51)
• Edges: each ciphertext byte creates an edge between key[i % 19] and plaintext[i % 52] with weight encrypted[i]

Step 3: Solving via BFS

We use BFS to propagate relative values:

• Fix key[0] = k0 (unknown)
• All other values are expressed through k0:
  • key[j] = key[0] ^ (key[0] ^ key[j]) = k0 ^ delta_key[j]
  • plaintext[p] = encrypted[i] ^ key[i % key_size]

Step 4: Brute-force the Offset

‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

We iterate through all 256 possible values of k0, checking the validity of the result.

Step 5: Base64 Detection

With k0 = 253 we get a valid Base64 string:

RFVDS0VSWnt3MFdfN2gxc18xc19YMFJfNnJ1NzNfTG8wbkdzfQ==

Step 6: Decoding

 python read-only • copy allowed Copy
import base64
result = base64.b64decode('RFVDS0VSWnt3MFdfN2gxc18xc19YMFJfNnJ1NzNfTG8wbkdzfQ==')
# b'DUCKERZ{REDACTED}'

Full Solution Code

 python read-only • copy allowed Copy
#!/usr/bin/env python3
"""
Woow - duckerz CTF
XOR with repeated key and repeated plaintext
"""

import base64
from collections import defaultdict, deque
‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

def solve():
    # Read encrypted data
    with open('output.txt', 'r') as f:
        encrypted = bytes.fromhex(f.read().strip())
    
    total_len = len(encrypted)  # 988
    
    # Find valid key_size (must be in [12, 44] and divide 988)
    valid_sizes = []
    for ks in range(12, 45):
        if total_len % ks == 0:
            valid_sizes.append(ks)
    # valid_sizes = [13, 19, 26, 38]
    
    # Test each key_size for consistency
    for key_size in valid_sizes:
        input_len = total_len // key_size
        
        # Build XOR equations: key[k1] ^ key[k2] = constant
        key_xor = defaultdict(set)
        for i in range(total_len - input_len):
            k1 = i % key_size
            k2 = (i + input_len) % key_size
            if k1 != k2:
                xor_val = encrypted[i] ^ encrypted[i + input_len]
                key_xor[(min(k1,k2), max(k1,k2))].add(xor_val)
        
        # Check consistency
        consistent = all(len(v) == 1 for v in key_xor.values())
        if not consistent:
            continue
        
        # Found correct key_size!
        print(f"key_size={key_size}, input_len={input_len}")
        
        # Build bipartite graph and solve with BFS
        # key_rel[j] = key[j] ^ key[0]
        # plain_rel[p] = plaintext[p] ^ key[0]
        key_rel = {0: 0}
        plain_rel = {}
        
        # Build adjacency: for each encrypted byte
        # encrypted[i] = plaintext[i % input_len] ^ key[i % key_size]
        # So: plaintext[p] ^ key[k] = encrypted[i]
        
        edges = defaultdict(list)  # key_pos -> [(plain_pos, enc_byte), ...]
        edges_rev = defaultdict(list)  # plain_pos -> [(key_pos, enc_byte), ...]
        
        for i in range(total_len):
            k = i % key_size
            p = i % input_len
            edges[k].append((p, encrypted[i]))
            edges_rev[p].append((k, encrypted[i]))
        
        # BFS from key[0]
        queue = deque(['k0'])
        visited = {'k0'}
        
        while queue:
            node = queue.popleft()
            
            if node.startswith('k'):
                k = int(node[1:])
                for p, enc in edges[k]:
                    pnode = f'p{p}'
                    if pnode not in visited:
                        # plaintext[p] = encrypted ^ key[k]
                        # plain_rel[p] = enc ^ key_rel[k]
                        plain_rel[p] = enc ^ key_rel[k]
                        visited.add(pnode)
                        queue.append(pnode)
            else:
                p = int(node[1:])
                for k, enc in edges_rev[p]:
                    knode = f'k{k}'
                    if knode not in visited:
                        # key[k] = encrypted ^ plaintext[p]
                        # key_rel[k] = enc ^ plain_rel[p]
                        key_rel[k] = enc ^ plain_rel[p]
                        visited.add(knode)
                        queue.append(knode)
        
        # Brute-force k0
        for k0 in range(256):
            plaintext = bytes([plain_rel[p] ^ k0 for p in range(input_len)])
            
            # Check if valid base64
            try:
                if all(c in b'ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/=' for c in plaintext):
                    decoded = base64.b64decode(plaintext)
                    if b'DUCKERZ{' in decoded or decoded.isascii():
                        print(f"k0={k0}")
                        print(f"Base64: {plaintext.decode()}")
                        print(f"Flag: {decoded.decode()}")
                        return decoded.decode()
            except:
                pass
        
        # Fallback: check for printable ASCII
        for k0 in range(256):
            plaintext = bytes([plain_rel[p] ^ k0 for p in range(input_len)])
            if all(32 <= c < 127 for c in plaintext):
                print(f"k0={k0}: {plaintext}")
‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

if __name__ == "__main__":
    solve()

Mathematical Essence

For position i:

C[i] = P[i mod L] ^ K[i mod S]

where C is ciphertext, P is plaintext (length L), K is key (length S).

XOR of two positions with the same remainder modulo L:

C[i] ^ C[i+L] = K[i mod S] ^ K[(i+L) mod S]

This gives a system of linear equations over GF(2), which can be solved up to one unknown byte.

Lessons

1. Data repetition in XOR creates redundancy that can be exploited
2. Length factorization helps determine encryption parameters
3. BFS on bipartite graph is an efficient way to propagate constraints
4. Base64 is often used for encoding flags - worth checking ‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍