Covert Message Passing over Public Internet Platforms Using Model-Based Format-Transforming Encryption

Luke A. Bauer, James K. Howes Iv, Sam A. Markelon, Vincent Bindschaedler, Thomas Shrimpton

Introduction

Traditional steganography often operates in idealized environments, focusing on maximizing information capacity or minimizing statistical divergence from a model's output. However, deploying covert messaging on public internet platforms like Mastodon or X (formerly Twitter) introduces a host of practical challenges that "lab-based" models fail to address. This paper introduces Model-Based Format-Transforming Encryption (MBFTE), a system designed to move model-based steganography into the "wild" by ensuring 100% message reliability and robustness against sophisticated adversarial attacks.

The Practical Gaps in Steganography

Existing research into hiding data within Large Language Model (LLM) outputs typically ignores the "dead-drop" scenario, where a sender (Alice) posts a message to a public forum for a receiver (Bob) to find later. The authors identify three critical barriers to real-world deployment:

  1. Parsing Ambiguity: Modern tokenizers, such as Byte Pair Encoding (BPE), are not prefix-free. A single string can be tokenized in multiple ways. If the receiver's tokenizer interprets the text differently than the sender's, the decoding process fails immediately.
  2. Hardware Non-Determinism: Minor differences in floating-point arithmetic across different CPUs or GPUs can lead to slight variations in the probability distributions generated by the LLM. In a cryptographic context, even a $10^{-10}$ discrepancy can cause the sender and receiver to desynchronize.
  3. The Trial-Decoding Vulnerability: Many current schemes use "top-k" or "top-p" sampling to improve text quality. However, this creates a signature: if an adversary observes a token that the model would never have produced under those restricted settings, they can instantly identify the post as legitimate. Conversely, if the post only uses restricted tokens, the adversary can attempt to "trial-decode" it to see if it contains a hidden message.

The MBFTE Framework

To address these gaps, the authors propose MBFTE, which integrates Authenticated Encryption with Associated Data (AEAD) with arithmetic coding. Unlike prior works, MBFTE is built to withstand active detection and technical discrepancies.

Comparison of MBFTE against prior steganography frameworks across security and functional dimensions.

Key technical innovations include:

  • Checkpoint Decoding: To resolve parsing ambiguity, the sender embeds "checkpoints" (zero-bytes) within the plaintext. If the receiver encounters a path that contradicts a checkpoint, they utilize a backtracking search to identify the correct token sequence.
  • Trusted Subset Filtering: To combat hardware discrepancies, the system only embeds data in tokens whose probabilities exceed a specific threshold ($\delta$). This ensures that both parties agree on the "trusted" token set regardless of minor numerical variations.
  • Sentinel Values: To allow Bob to efficiently find the "needle in the haystack," the system uses a 2-byte sentinel value (a truncated HMAC). This allows the receiver to quickly discard irrelevant public posts without performing a full, computationally expensive decode.

Platform Analysis and Dataset Selection

The effectiveness of a covert messaging system depends heavily on how well it blends into the target environment. The authors analyzed 100,000 posts from Mastodon.social to understand the distribution of hashtags and post lengths.

Analysis of Mastodon tags showing the relationship between post volume and average length, used to select optimal 'overt signals' for covert messaging.

This analysis helped identify "overt signals"—such as specific hashtags—that provide enough cover (number of posts) and capacity (average length) for messaging. For instance, tags like #news or #press offer high volume and length, making them ideal candidates for hiding encrypted payloads. The authors fine-tuned a GPT-2 (124M) model on these specific subsets to ensure the generated covertext matched the platform's linguistic style.

Results and Security Evaluation

The MBFTE system demonstrated significant improvements over baseline steganographic methods:

  • Reliability: While standard tokenizers failed to decode up to 12.5% of messages due to ambiguity, MBFTE achieved 100% reliability through its checkpointing mechanism.
  • Detectability: Using a RoBERTa-based classifier, the authors found that while raw GPT-2 text is easily detectable (AUC 0.998), fine-tuning on platform-specific data reduced the detection AUC to 0.83.
  • Efficiency: On a standard consumer CPU, encoding and decoding a 40-byte plaintext takes approximately 11.5 seconds. While slower than standard encryption, the use of sentinel values reduces the time to scan a batch of 100 posts from 20 minutes to under 60 seconds.

Conclusion

MBFTE represents a shift from theoretical steganography to practical, covert communication. By prioritizing "plausibility" over simple "naturalness" and addressing the technical realities of tokenization and hardware, the authors provide a blueprint for secure, asynchronous messaging on the modern web. Future work remains in scaling these techniques to larger models and addressing metadata-based traffic analysis.

Summary updated

Abstract

We introduce a new type of format-transforming encryption where the format of ciphertexts is implicitly encoded within a machine-learned generative model. Around this primitive, we build a system for covert messaging over large, public internet platforms (e.g., Twitter). Loosely, our system composes an authenticated encryption scheme, with a method for encoding random ciphertext bits into samples from the generative model's family of seed-indexed token-distributions. By fixing a deployment scenario, we are forced to consider system-level and algorithmic solutions to real challenges -- ~such as receiver-side parsing ambiguities, and the low information-carrying capacity of actual token-distributions~ -- that were elided in prior work. We use GPT-2 as our generative model so that our system cryptographically transforms plaintext bitstrings into natural-language covertexts suitable for posting to public platforms. We consider adversaries with full view of the internet platform's content, whose goal is to surface posts that are using our system for covert messaging. We carry out a suite of experiments to provide heuristic evidence of security and to explore tradeoffs between operational efficiency and detectability.
BibTeX
@inproceedings{bauer2021covert,
  author = {Luke A. Bauer and James K. Howes IV and Sam A. Markelon and Vincent Bindschaedler and Thomas Shrimpton},
  title = {{Covert Message Passing over Public Internet Platforms Using Model-Based Format-Transforming Encryption}},
  booktitle = {CODASPY},
  year = {2021},
  url = {https://openreview.net/forum?id=JSuXCpnW4h},
}
Figure