Blum-blum-shub

Platform: CUSTOM | Category: Crypto | Type: Challenge | Difficulty: Medium | OS: N/A | **Author: XESXOR Techniques: bbs_state_recovery, known_plaintext_verification, seed_brute_force

Summary

Walkthrough of the CUSTOM Crypto Blum-blum-shub. Task: Break BBS PRNG with weak seed (1-100000) to decrypt multiple sequentially encrypted files. Solution: Brute-force seed using known PNG header as plaintext verification, then decrypt the flag file

Description

A challenge about breaking the Blum-Blum-Shub (BBS) pseudorandom number generator with a weak seed. Multiple files are encrypted sequentially using the same generator.

Analysis

Blum-Blum-Shub PRNG

BBS is a cryptographically secure PRNG based on the difficulty of factorization:

x_{n+1} = x_n² mod N
output = LSB(x_n) or several least significant bits

where N = p × q (product of two Blum primes, p ≡ q ≡ 3 mod 4).

Vulnerabilities in the Challenge

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

1. Weak seed: range 1-100000 — can be brute-forced
2. N is factorizable: N = 31288934228111896268949411962713065973 found on factordb
3. Known plaintext: document.png has a known PNG header
4. Sequential encryption: files are encrypted in order flag → document.png → lorem-ipsum.pdf

Encryption Structure

seed → BBS state
     ↓
flag.enc (first N bytes of keystream)
     ↓
document.png.enc (next M bytes of keystream)
     ↓
lorem-ipsum.pdf.enc (remaining keystream)

Solution

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

Step 1: Factorize N

 bash read-only • copy allowed Copy
# N = 31288934228111896268949411962713065973
# factordb.com → N = p × q

Step 2: BBS Implementation

 python read-only • copy allowed Copy
#!/usr/bin/env python3

class BBS:
    def __init__(self, seed, n):
        self.state = seed
        self.n = n
    
    def next_bit(self):
        self.state = pow(self.state, 2, self.n)
        return self.state & 1
    
    def next_byte(self):
        byte = 0
        for i in range(8):
            byte |= self.next_bit() << i
        return byte
    
    def get_keystream(self, length):
        return bytes([self.next_byte() for _ in range(length)])

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

Step 3: Brute-force Seed with Verification

 python read-only • copy allowed Copy
#!/usr/bin/env python3

N = 31288934228111896268949411962713065973

# Known PNG header
PNG_HEADER = bytes([0x89, 0x50, 0x4E, 0x47, 0x0D, 0x0A, 0x1A, 0x0A])

# Read encrypted files
with open('flag.enc', 'rb') as f:
    flag_enc = f.read()
with open('document.png.enc', 'rb') as f:
    doc_enc = f.read()

flag_len = len(flag_enc)

# Brute-force seed
for seed in range(1, 100001):
    bbs = BBS(seed, N)
    
    # Generate keystream for flag
    flag_keystream = bbs.get_keystream(flag_len)
    
    # Generate keystream for document.png start
    doc_keystream = bbs.get_keystream(len(PNG_HEADER))
    
    # Verify PNG header
    decrypted_header = bytes([a ^ b for a, b in zip(doc_enc[:8], doc_keystream)])
    
    if decrypted_header == PNG_HEADER:
        print(f"[+] Found seed: {seed}")
        
        # Decrypt flag
        flag = bytes([a ^ b for a, b in zip(flag_enc, flag_keystream)])
        print(f"[+] Flag file decrypted")
        
        # Save decrypted flag (it's a JPEG with the flag text)
        with open('flag_decrypted.jpg', 'wb') as f:
            f.write(flag)
        
        break
‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

# seed = 50230

Step 4: Extract the Flag

The decrypted flag_decrypted.jpg is an image containing the flag text.

Concepts

Blum-Blum-Shub Security

BBS is considered cryptographically secure under these conditions:

1. N = p × q is not factorizable (p, q — large primes)
2. Seed is random and secret
3. Only the least significant bits of the state are output

Violating any condition breaks security.

Known Plaintext Attack on Stream Cipher

If plaintext P and ciphertext C are known:

keystream = P XOR C

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

This keystream can be used for:

1. Verifying seed correctness during brute-force
2. Decrypting other parts of the message (if keystream is reused)

Sequential Encryption Vulnerability

When multiple files are encrypted sequentially with the same PRNG:

file1.enc = file1 XOR keystream[0:len1]
file2.enc = file2 XOR keystream[len1:len1+len2]

Knowing the format of file2 (e.g., PNG header), you can verify the seed and decrypt file1. ‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

Key Takeaways / Lessons

• Mastering bbs_state_recovery, known_plaintext_verification, seed_brute_force was key to this challenge.
• Always check for common misconfigurations and verify assumptions.

---

Crafted by XESXOR Research • 2026-03-09 • CUSTOM • Blum-blum-shub • Difficulty: Medium