Undervattensströmmar

Platform: CUSTOM | Category: Crypto | Type: Challenge | Difficulty: Medium | OS: N/A | **Author: XESXOR Techniques: gcd_attack, known_plaintext_attack, lcg_parameter_recovery, modular_inverse

Summary

Walkthrough of the CUSTOM Crypto Undervattensströmmar. Task: LCG-based XOR stream cipher with missing parameters, known file header. Solution: Known plaintext attack to recover keystream, GCD method to crack LCG parameters, decrypt and extract flag from g

Description

Under en utflykt i de mer trasiga delarna av CASCADA har Harriet hittat ett USB-minne, märkt Viktigt!!!. Dra på trissor! Inte mindre än tre utropstecken, så det måste vara något i hästväg! Tyvärr är stickan illa åtgången och har minst ett tydligt bitmärke!

Harriet lyckas få ut två filer från stickan, men det övriga innehållet är bortom räddning. Kan du hjälpa henne att få fram vad det var som var så viktigt?

English summary: A damaged USB drive was found with two recoverable files: ibtool.c (encryption tool source code) and ciphertext (164 bytes of encrypted data). The parameters file needed for decryption is missing. Goal is to recover the encrypted content. ‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

Analysis

The encryption tool (ibtool.c) reveals:

1. LCG-based stream cipher: Uses Linear Congruential Generator for keystream

   • Formula: state = (multiplier * state + increment) % modulus
   • All parameters are 16-bit unsigned integers

2. XOR encryption: Plaintext XORed with keystream in 16-bit words

3. Known header: Files must start with IBTOOLBACKUP\x00\x00 (14 bytes)

4. Missing information:

   • Parameters file (multiplier, increment, modulus) - lost
   • Seed value - unknown ‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

Key vulnerability: LCG is cryptographically weak. With consecutive outputs, all parameters can be mathematically recovered.

Solution

Step 1: Known Plaintext Attack

Since we know the file header, XOR first 14 bytes of ciphertext with known plaintext to recover keystream:

 python read-only • copy allowed Copy
header = b"IBTOOLBACKUP\x00\x00"
ciphertext_start = bytes.fromhex("74595c5c9219b763e25ceb15d601")
keystream_bytes = bytes([p ^ c for p, c in zip(header, ciphertext_start)])
# Convert to uint16 (little-endian): [6973, 4872, 21981, 8949, 6049, 17854, 470]

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

Step 2: Crack LCG Parameters

Using mathematical properties of LCG with consecutive outputs:

For differences t[n] = k[n+1] - k[n]:

• t[n+1] = a * t[n] mod m

Using GCD of t[n] * t[n-2] - t[n-1]^2 values to find modulus:

 python read-only • copy allowed Copy
from math import gcd
from functools import reduce

k = [6973, 4872, 21981, 8949, 6049, 17854, 470]
t = [k[i+1] - k[i] for i in range(len(k)-1)]
# t = [-2101, 17109, -13032, -2900, 11805, -17384]

# Find modulus using GCD method
u = [t[i+1] * t[i-1] - t[i] * t[i] for i in range(1, len(t)-1)]
m = reduce(gcd, [abs(x) for x in u])
# m = 22661

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

Step 3: Find Multiplier and Increment

 python read-only • copy allowed Copy
def modinv(a, m):
    return pow(a, -1, m)

# a = t[1] * modinv(t[0], m) mod m
a = (t[1] * modinv(t[0], m)) % m
# a = 35

# c = k[1] - a * k[0] mod m
c = (k[1] - a * k[0]) % m
# c = 10088

Step 4: Find Seed

The first keystream value (6973) is the state AFTER the first LCG iteration:

 python read-only • copy allowed Copy
# state = (a * seed + c) % m = 6973
# seed = (6973 - c) * modinv(a, m) % m
seed = ((k[0] - c) * modinv(a, m)) % m
# seed = 22572

Step 5: Decrypt

 python read-only • copy allowed Copy
#!/usr/bin/env python3
import struct
‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

# Recovered parameters
a, c, m = 35, 10088, 22661
seed = 22572

# Read ciphertext
with open("ciphertext", "rb") as f:
    ciphertext = f.read()

# Decrypt
state = seed
plaintext = b""
for i in range(0, len(ciphertext), 2):
    state = (a * state + c) % m
    cipher_word = struct.unpack("<H", ciphertext[i:i+2])[0]
    plain_word = cipher_word ^ state
    plaintext += struct.pack("<H", plain_word)

# Save result
with open("plaintext.bin", "wb") as f:
    f.write(plaintext)

Step 6: Extract Flag

The decrypted data contains:

• 14-byte header IBTOOLBACKUP\x00\x00
• gzip-compressed tar archive ‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

 bash read-only • copy allowed Copy
dd if=plaintext.bin bs=1 skip=14 | gunzip | tar -xOf - f2
# Output: undut{REDACTED}

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

Key Takeaways / Lessons

• Mastering gcd_attack, known_plaintext_attack, lcg_parameter_recovery, modular_inverse was key to this challenge.
• Always check for common misconfigurations and verify assumptions.

---

Crafted by XESXOR Research • 2026-03-21 • CUSTOM • Undervattensströmmar • Difficulty: Medium