Meteor: Cryptographically Secure Steganography for Realistic Distributions

Current randomized-payload circumvention tools (obfs4/ScrambleSuit, SkypeMorph, VoIP-tunneling) rely on censors 'defaulting open' — treating unidentified traffic as innocuous. If censors instead block all traffic not explicitly recognizable as meaningful plaintext, these tools fail entirely. The paper notes anecdotal evidence this is already occurring, including blocking of some TLS 1.3 connections.

§1 Introduction detection random-payload-detectfully-encrypted-detectdpi cn

Variable-length sampling (Adaptation 2) achieves a provably secure but impractical encoding: a 16-byte plaintext encoded with GPT-2 requires 502–2994 tokens, produces 2.3–13.6 KiB of stegotext (149×–870× overhead), and takes 42–765 seconds even with GPU acceleration, depending on security parameter k=16–128.

§4 / Table 1 evaluation random-payload-detect generic

Classical public-key steganography (Algorithm 1 from [54]) has a 100% failure rate when encoding a 16-byte message using GPT-2, because GPT-2's per-token entropy drops near zero frequently and standard rejection sampling cannot find an acceptable token. Entropy bounding reduces failure to 0–10% but introduces detectable statistical bias: selected tokens come from a visibly different probability distribution than baseline samples.

§4 Adapting Classical Steganographic Schemes / Figure 2b evaluation random-payload-detectml-classifier generic

Meteor encodes bits by embedding a PRG-masked random value into the token-sampling randomness of a generative model, recovering bits proportional to the shared prefix length of the sampled interval. Expected throughput per sampling event is asymptotically within 1/2 of the Shannon entropy of the channel (proven in Appendix A), so Meteor automatically adapts to high entropy variability without explicit signaling or padding.

§5 Meteor / §5.2 defense random-payload-detectml-classifier generic

Meteor is proven secure against chosen-hiddentext attacks: any PPT adversary distinguishing Meteor output from honest model output can be reduced to breaking the underlying PRG. The scheme produces stegotext provably indistinguishable from the generative model's own output distribution, and requires only a shared public model — not a secret channel — making the model analogous to a common random string. On GPU the encoding overhead is ~1× model-load time; on CPU ~4.6×; on mobile ~49.5×.

§5.2 / §6 / Table 2 defense random-payload-detectml-classifiertraffic-shape cnir