Automated Cryptanalysis of Two-Time Pads

Overview

This project implements a two-ciphertext cryptanalysis system inspired by the 2006 paper "A Natural Language Approach to Automated Cryptanalysis of Two-time Pads" by Mason, Watkins, Eisner, and Stubblefield.

The system demonstrates a practical attack on keystream reuse vulnerabilities, automatically recovering plaintexts from two ciphertexts encrypted with the same keystream when their text domain is known. The email workflow is the most developed path today; HTML and book/document corpus support is still preliminary.

Project Status

The core code solves the strict two-time pad case: two ciphertexts, one reused keystream, and one XOR stream x = c1 ⊕ c2 = p ⊕ q. It does not currently implement the easier 3+ ciphertext variant where additional XOR constraints reduce stream switching.

Current strengths:

• Character-level n-gram language model with Witten-Bell backoff.
• Beam-search decoder that keeps the XOR invariant at every recovered byte pair.
• Text-aware candidate alphabet with printable ASCII, common whitespace, and trained vocabulary bytes.
• Switch-aware alignment refinement that can repair local stream swaps after decoding.
• Optional separate models for the two streams, useful for mixed document types.
• Separate evaluation of strict byte accuracy, global-swap-aware byte accuracy, pair accuracy, printable accuracy, word accuracy, and stream switching.
• Repeatable local tests for the model, decoder, evaluator, and training pipeline.

Main limitations:

• Accuracy is strongly limited by the stream-switching problem when both plaintexts come from the same domain and use the same language model.
• Beam search is approximate. Wider beams can help but increase runtime.
• The decoder is tuned for text-like payloads, not arbitrary binary plaintext.
• If both plaintexts use the same model, a full global stream swap is often mathematically indistinguishable. Pair accuracy and best-orientation byte accuracy are more honest than strict byte accuracy alone.
• The README result summaries are based on local experiment artifacts committed in results/; rerun python -m src.analysis to refresh them after model or decoder changes.

Core Cryptographic Problem

The Two-Time Pad Vulnerability

When a keystream k is reused to encrypt two plaintexts p and q, an attacker can compute:

c₁ = p ⊕ k  (ciphertext 1)
c₂ = q ⊕ k  (ciphertext 2)
x  = c₁ ⊕ c₂ = (p ⊕ k) ⊕ (q ⊕ k) = p ⊕ q

The challenge is to recover p and q from x = p ⊕ q alone. This has 2ⁿ solutions for n-bit messages, but when plaintexts follow known statistical patterns (natural language), the solution becomes tractable.

Language Model Approach

The paper's key insight: treat plaintext recovery as a decoding problem using statistical language models. Given x = p ⊕ q and language models for p and q's document types, find the most probable (p, q) pair:

argmax_(p,q) Pr₁(p) · Pr₂(q)   subject to   p ⊕ q = x

Where Pr₁ and Pr₂ are character-level n-gram language models trained on domain-specific corpora.

Character-Level N-Gram Language Model

What Is a Character N-Gram Model?

A character n-gram model is a probability distribution over the next character given the previous n-1 characters. For n=7 (used in this implementation), the model predicts the 7th character based on the preceding 6 characters.

Example: After seeing "hobnob", the model might predict:

• 's' with probability 0.52 (forming "hobnobs")
• space with probability 0.35 (forming "hobnob ")
• 'b' with probability 0.13 (forming "hobnobb")

Mathematical Formulation

For a plaintext string p = (p₁, p₂, ..., pₗ), the 7-gram model defines:

Pr₁(p) = ∏ᵢ₌₁ˡ Pr₁(pᵢ | pᵢ₋₆, ..., pᵢ₋₁)

Each factor represents the probability of character pᵢ given the previous 6 characters, assuming a Markov property - each character depends only on the immediate history.

Training Process

The model is trained by sliding a 7-character window through training texts and counting occurrences:

def train(self, text: bytes):
    # Add BOM (beginning-of-message) padding for proper context
    prefix = bytes([BOM]) * 6  # 6 BOM characters
    suffix = bytes([EOM])      # 1 EOM character
    data = prefix + text + suffix
    
    # Count 7-grams: (context of 6 chars) → (next char)
    for i in range(0, len(data) - 7 + 1):
        context = data[i:i+6]      # 6-byte context
        next_char = data[i+6]      # Character to predict
        self.ngram_counts[context][next_char] += 1

Example: Training on "hobnobs" with BOM padding:

Training window: "h o b n o b s"
Context: "hobnob" (6 chars)
Next char: 's'
Result: ngram_counts[b"hobnob"]['s'] += 1

The Zero-Probability Problem & Witten-Bell Smoothing

The Problem

With 6-character contexts, there are 256⁶ ≈ 2.8×10¹⁴ possible contexts. Even with billions of training characters, most contexts are never seen. Naive frequency estimates give zero probability for unseen sequences, making decoding impossible.

Witten-Bell Solution

Witten-Bell smoothing interpolates between:

1. Maximum Likelihood Estimate (MLE) for observed n-grams
2. Backoff estimate using shorter contexts

For a context c:

• N(c) = total times c appeared
• T(c) = distinct characters following c
• Backoff weight: λ(c) = T(c) / (T(c) + N(c))

Probability calculation:

P_WB(x|c) = (1 - λ(c)) × P_ML(x|c) + λ(c) × P_backoff(x|c')

Where c' = c[1:] (context with oldest character removed)

Recursive Backoff Chain

When computing P('s' | "hobnob"):

1. Try 7-gram: P('s' | "hobnob")
2. If insufficient data, backoff to 6-gram: P('s' | "obnob")
3. Continue backing off until 1-gram: P('s')
4. Base case: uniform over vocabulary

This ensures no probability is ever zero, allowing the decoder to explore all possibilities.

Decoding Algorithm: Beam Search with Viterbi

Problem Formalization

Given x = p ⊕ q and language models for p and q, find:

argmax_(p,q) ∏ᵢ Pr₁(pᵢ | pᵢ₋₆...pᵢ₋₁) × Pr₂(qᵢ | qᵢ₋₆...qᵢ₋₁)
subject to pᵢ ⊕ qᵢ = xᵢ for all i

Beam State Representation

class BeamState:
    __slots__ = ['ctx1', 'ctx2', 'log_prob', 'p1_path', 'p2_path']
    
    def __init__(self, ctx1: bytes, ctx2: bytes, log_prob: float,
                 p1_path: bytearray, p2_path: bytearray):
        self.ctx1 = ctx1  # Last 6 chars of plaintext1
        self.ctx2 = ctx2  # Last 6 chars of plaintext2
        self.log_prob = log_prob  # Cumulative log probability
        self.p1_path = p1_path    # Reconstructed plaintext1 so far
        self.p2_path = p2_path    # Reconstructed plaintext2 so far

Beam Search Algorithm

def decode(self, xor_stream: List[int]) -> Tuple[bytes, bytes]:
    # Initialize with BOM contexts
    beam = [BeamState(bytes([BOM]*6), bytes([BOM]*6), 0.0, bytearray(), bytearray())]
    
    for i, xor_byte in enumerate(xor_stream):
        candidates = []
        
        for state in beam:
            # Generate candidate byte pairs from the text alphabet
            for p1_byte in candidate_alphabet:
                p2_byte = p1_byte ^ xor_byte
                
                if p2_byte in candidate_alphabet:
                    # Score using language models
                    lp1 = model1.log_prob(p1_byte, state.ctx1)
                    lp2 = model2.log_prob(p2_byte, state.ctx2)
                    new_prob = state.log_prob + lp1 + lp2
                    
                    # Update contexts
                    new_ctx1 = (state.ctx1 + bytes([p1_byte]))[-6:]
                    new_ctx2 = (state.ctx2 + bytes([p2_byte]))[-6:]
                    
                    candidates.append(BeamState(new_ctx1, new_ctx2, new_prob,
                                                state.p1_path + [p1_byte],
                                                state.p2_path + [p2_byte]))
        
        # Keep only top-k states (beam width = 100)
        beam = sorted(candidates, key=lambda s: s.log_prob, reverse=True)[:100]
    
    # Return best candidate
    best = max(beam, key=lambda s: s.log_prob)
    return bytes(best.p1_path), bytes(best.p2_path)

Switch-Aware Alignment Refinement

The decoder now runs an optional post-processing pass after beam search. Beam search often recovers the right unordered byte pair but assigns a segment to the wrong stream. The refinement pass treats every recovered pair as two possible orientations:

position i: keep  = (rec1[i], rec2[i])
position i: swap  = (rec2[i], rec1[i])

It then runs a second, much smaller beam/Viterbi pass over those keep/swap choices. Each orientation is scored with the same two language models and a configurable switch penalty. This keeps the XOR invariant intact because swapping a recovered pair does not change rec1[i] ⊕ rec2[i].

This improves local stream assignment when the model evidence is strong enough. It cannot reliably solve a full global swap when both streams use the same language model, because (p, q) and (q, p) are equally plausible without outside identity information.

Computational Complexity

• Full search space: O(256²ˡ) for length l (intractable)
• With n-gram constraint: O(l × 256⁷) (still massive)
• With beam search: O(l × beam_width × 256) (practical)
• Alignment refinement: O(l × alignment_beam_width × 2), because it only chooses keep vs swap for recovered pairs.

Performance: runtime scales roughly with message_length × beam_width × candidate_alphabet_size, plus the smaller alignment pass. Exact throughput depends on model size, corpus domain, and beam width.

Experimental Results

Local experiments train Enron email models and evaluate recovery on held-out email pairs. Similar two-time-pad tools often show either crib-dragging examples or partial plaintext output, while Mason et al. report plaintext accuracy and runtime. For this project, the most useful presentation is a table with metric definitions, corpus size, model settings, and recovery scores.

Metric Definitions

• Strict byte accuracy: recovered bytes match the original file order exactly.
• Best-orientation byte accuracy: best score after allowing one global stream swap. This is important for same-domain two-time pads because (p, q) and (q, p) may be indistinguishable.
• Pair accuracy: unordered byte pair is correct at a position, even if assigned to the wrong stream.
• Switch rate: correct byte pairs that are assigned to the opposite stream.
• Success rate: percentage of tests with pair accuracy above 70%.

Historical Enron Cross-Validation

These larger runs are the committed result artifacts under results/. They predate the new best-orientation metric, but they are still useful for tracking pair recovery as training data grows.

Total Emails	Train Emails	Strict Byte Accuracy	Pair Accuracy	Success Rate
1,250	1,000	29.6%	58.6%	40.4%
6,250	5,000	36.9%	75.2%	64.4%
12,500	10,000	38.1%	80.9%	71.2%

Current Decoder Snapshot

This compact benchmark was run against the current decoder after adding switch-aware alignment refinement:

• Data: res/20k_processed_emails
• Training: 240 emails
• Test set: 5 held-out email pairs
• Plaintext length: 70 bytes per pair
• Model: 4-gram character model
• Beam width: 80
• Seed: 23

Decoder Variant	Strict Byte Accuracy	Best-Orientation Byte Accuracy	Pair Accuracy	Switch Rate
Beam search only	39.1%	81.7%	96.9%	57.7%
Beam + alignment refinement	40.6%	81.7%	96.9%	56.3%

The refinement improves local stream assignment without changing pair recovery. The large gap between strict byte accuracy and best-orientation byte accuracy shows that many same-domain failures are stream-labeling failures rather than missing-character failures.

Key Insights

1. Pair Accuracy Is the Core Deciphering Metric: When pair accuracy is high, the system has often recovered the plaintext characters but may not know which recovered stream belongs to which original ciphertext.

2. Strict Byte Accuracy Measures Stream Identity: This is useful when model 1 and model 2 represent distinct document types. It can look unfairly low when both models are identical.

3. Best-Orientation Byte Accuracy Separates Global Swaps from Real Errors: A globally swapped recovery is still useful to a human analyst, and this metric shows that.

4. Training Data Helps Pair Recovery: The larger local summaries show pair accuracy improving with more email data.

5. Domain Separation Should Improve Stream Assignment: Different document-type models, such as HTML versus email, should reduce switching more than simply adding more same-domain email.

The "Switching Streams" Problem

Problem Description

After decoding errors, the algorithm loses track of which byte belongs to which text. Correct bytes continue to be recovered but are assigned to the wrong plaintext until another correction occurs.

Example:

Original:    p = "Hello world", q = "Secret message"
Recovered:   p' = "Secret Hello", q' = "world message"
Pair Accuracy: 100% (all bytes present)
Byte Accuracy: 50% (bytes in wrong positions)

Why It Happens

Character n-gram models only look at the last 6 characters. When the decoder makes an error, the contexts become corrupted. Once it "gets back on track," it has no memory of which stream the correct bytes belong to.

Accuracy Improvements for Two Ciphertexts

1. Different Document Types

When p is HTML and q is email, their language models differ significantly:

• HTML: High probability for <, >, tags
• Email: High probability for @, : in headers The probability gap makes swapped assignments highly improbable.

2. Switch-Aware Alignment Refinement

Implemented in TwoTimePadDecoder.refine_stream_alignment. The decoder scores each recovered byte pair in both orientations and keeps the highest-scoring stream assignment, with a small penalty for changing orientation too often.

for i in range(len(rec1)):
    keep_score = model1.log_prob(rec1[i], ctx1) + model2.log_prob(rec2[i], ctx2)
    swap_score = model1.log_prob(rec2[i], ctx1) + model2.log_prob(rec1[i], ctx2)
    # A beam/Viterbi pass chooses the best sequence of keep/swap decisions.

3. Better Candidate and Search Strategy

Implemented in the decoder: the candidate alphabet includes printable ASCII, common whitespace, and trained vocabulary bytes. The remaining accuracy work is mostly systematic tuning of beam width, n-gram length, switch penalty, and corpus/domain-specific alphabets.

Running the Project

Installation

git clone https://github.com/Radoslaw-Wolnik/TwoTimePadCracking.git
cd TwoTimePadCracking
pip install -r requirements.txt

Basic Usage

1. Setup Data

# Download and process Enron emails
python -m src.main --setup --type email

# For HTML documents
python -m src.main --setup --type html

# Books are accepted by the CLI, but corpus setup is currently a placeholder
python -m src.main --setup --type books

2. Train Language Models

# Train a new email model
python -m src.main --train --type email --model-name email_model --new

# Continue training on existing model
python -m src.main --train --type email --model-name email_model --open-model-name email_model

3. Perform Cryptanalysis

# Decode two ciphertexts encrypted with same keystream
python -m src.main --decoding \
    --model-name email_model \
    --doc-type email \
    --file1path enc1.bin \
    --file2path enc2.bin

# Decode with two different stream models
python -m src.main --decoding \
    --model1-name email_model \
    --model2-name html_model \
    --doc-type email \
    --file1path enc_email.bin \
    --file2path enc_html.bin

# Tune decoder search/refinement
python -m src.main --decoding \
    --model-name email_model \
    --doc-type email \
    --beam-width 200 \
    --switch-penalty 1.0 \
    --file1path enc1.bin \
    --file2path enc2.bin

Alignment refinement is enabled by default. Add --no-refine-alignment to inspect the raw beam-search output.

4. Run Analysis Experiments

# Analyze with different training sizes
python -m src.analysis --num-emails 1000 --num-runs 3 --num-tests 10
python -m src.analysis --num-emails 5000 --num-runs 3 --num-tests 10
python -m src.analysis --num-emails 10000 --num-runs 3 --num-tests 10

# With custom parameters
python -m src.analysis --num-emails 5000 --n 7 --beam-width 200 --num-runs 5

5. Run Tests

# All tests
python -m pytest src/tests/ -v

# Specific test suites
python -m pytest src/tests/test_char_language_model.py -v
python -m pytest src/tests/test_decoder_integration.py -v

# Slow tests (requires data)
python -m pytest src/tests/ --runslow -v
python -m pytest src/tests/ --runveryslow -v

Expected Output

• Models: Saved to res/models/ directory as binary files
• Analysis Results: JSON, plots, and summaries in res/analysis_results/
• Decoded Text: Recovered plaintexts printed to console and saved to files

References & Citations

1. Primary Reference: Mason, J., Watkins, K., Eisner, J., & Stubblefield, A. (2006). A Natural Language Approach to Automated Cryptanalysis of Two-time Pads. Proceedings of the 13th ACM Conference on Computer and Communications Security (CCS'06).

2. Language Modeling: Witten, I. H., & Bell, T. C. (1991). The zero-frequency problem: Estimating the probabilities of novel events in adaptive text compression. IEEE Transactions on Information Theory.

3. Earlier Work: Dawson, E., & Nielsen, L. (1996). Automated cryptanalysis of XOR plaintext strings. Cryptologia.

4. Historical Context: Kahn, D. (1996). The Codebreakers. Comprehensive history of cryptography including two-time pad vulnerabilities.

5. Dataset: Enron Email Dataset, available at https://www.cs.cmu.edu/~enron/

6. Related Tooling: SpiderLabs cribdrag, an interactive crib-dragging tool for reused or predictable stream cipher keys: https://github.com/spiderlabs/cribdrag

7. Related Tooling: multi_time_pad_breaker, a heuristic same-key OTP breaker that demonstrates space/XOR reasoning and partial plaintext recovery: https://github.com/dszyszek/multi_time_pad_breaker

8. Metric Presentation: Recent cryptanalysis benchmarks commonly report exact-match and normalized text-recovery metrics; this project uses byte/pair/switch metrics because two-time-pad recovery has stream-orientation ambiguity: https://arxiv.org/html/2505.24621v1

License

This project is for educational and research purposes only. Use responsibly and in accordance with applicable laws and regulations.

The code is provided as-is under the MIT License. See LICENSE file for details.

Responsible Disclosure

This project demonstrates a known cryptographic vulnerability (keystream reuse). Use this knowledge responsibly:

• Only test on systems you own or have explicit permission to test
• Never use for unauthorized access to systems or data
• Report security vulnerabilities to vendors through proper channels

---

Author: Radoslaw Wolnik
Contact: radoslaw.m.wolnik@gmail.com
Repository: GitHub Link
Based on: Mason et al. (2006), CCS'06