GFPRNG

Platform: volgactf | Category: Crypto | Type: Challenge | Difficulty: Easy | OS: NA | Author: XESXOR | Date: 2026-03-28 | Status: Solved Techniques: frobenius_endomorphism_periodicity, known_plaintext_attack, stream_cipher_keystream_recovery

Summary

Task: SageMath PRNG using repeated squaring in GF(2^8) to XOR-encrypt a PNG file. Solution: Frobenius endomorphism makes keystream periodic with period 8; recover keystream from known PNG header.

GFPRNG — VolgaCTF 2026

Description

"You only need to know basic math."

Given a SageMath script (main.sage) that encrypts a PNG file using a custom PRNG built on GF(2^8), and the resulting encrypted_flag (20399 bytes). The goal is to decrypt the file and read the flag from the recovered PNG image.

Analysis

The PRNG operates in GF(2^8) — a finite field with 256 elements, constructed with a random irreducible polynomial modulus:

 python read-only • copy allowed Copy
K.<x> = GF(2^8, modulus='random', impl='ntl')

The keystream generator picks a random seed element and produces bytes by repeated squaring: ‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

seed, seed², (seed²)² = seed⁴, (seed⁴)² = seed⁸, seed^16, seed^32, seed^64, seed^128, seed^256, ...

The critical mathematical insight is the Frobenius endomorphism: in any finite field GF(2^k), for every element x:

x^(2^k) = x

Since k = 8, this means seed^(2^8) = seed^256 = seed. Therefore the keystream is periodic with period exactly 8 bytes (or a divisor of 8).

This can also be verified algebraically: the multiplicative group of GF(2^8) has order 255 = 2^8 - 1. The squaring map generates the sequence of exponents 1, 2, 4, 8, 16, 32, 64, 128, 256 ≡ 1 (mod 255). The multiplicative order of 2 modulo 255 is 8, confirming the period. ‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

Key weakness: Regardless of the random modulus polynomial or seed choice, the keystream always repeats every 8 bytes.

Solution

Since the plaintext is a PNG file, the first 8 bytes are the standard PNG signature, which is always:

89 50 4E 47 0D 0A 1A 0A

This gives us a classic known-plaintext attack on a repeating-key XOR cipher:

1. XOR the first 8 bytes of ciphertext with the known PNG header to recover the full 8-byte repeating keystream
2. XOR the entire ciphertext with the repeating keystream to recover the plaintext PNG ‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

 python read-only • copy allowed Copy
#!/usr/bin/env python3
# Solve script for GFPRNG — VolgaCTF 2026

# Standard PNG file signature (first 8 bytes)
png_header = bytes([0x89, 0x50, 0x4E, 0x47, 0x0D, 0x0A, 0x1A, 0x0A])

with open('encrypted_flag', 'rb') as f:
    ciphertext = f.read()

# Recover the 8-byte repeating keystream using known PNG header
keystream = bytes([c ^ p for c, p in zip(ciphertext[:8], png_header)])
print(f"Recovered keystream: {keystream.hex()}")

# Decrypt the entire file by XORing with the repeating keystream
plaintext = bytes([c ^ keystream[i % 8] for i, c in enumerate(ciphertext)])
‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

with open('flag.png', 'wb') as f:
    f.write(plaintext)

print(f"Decrypted {len(plaintext)} bytes -> flag.png")

The decrypted PNG image (1109×450, RGB) contains the flag text. ‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍