Natural Language Steganography Based on Statistical Text Generation

Christian Siefkes

http://www.siefkes.net/nlstego/

2005

Embedding vs. Generating Stego

“Known-cover attack” when embedding into existing images/text

Creation of new cover images/text is expensive, esp. for text

But text is more common (“needle in a haystack”)and less conspicuous than images and can be transmitted on any medium (even print or phone)

Text generation, but grammar-base generation does not completely cover human language and is very hard to adapt to new domains/languages

Statistical text generation – Markov model

Sample Output of Markov Model

Microsoft said Tuesday the court will find Microsoft's goal.

"We will continue to listen to our customers and programming option of taking advantage of Windows features when writing software using the Java Compatibility Logo on its packaging and websites for Internet Explorer and Software using the best tools and programming language. Providing the Java language. Providing the Java programming language to write great software Developers Kit for Java.

"We remain confident that once all the facts are presented in the forefront of helping developers have the option of taking advantage of Windows features when writing software Developers use the Java Compatibility Logo on its packaging and websites for Internet Explorer and Software using the best tools and provide them the tools they need to write cutting-edge applications. The company would comply with this decision, but we will immediately comply with this decision, but we will immediately comply with a preliminary ruling by Federal District Court Judge Ronald H. Whyte that Microsoft is no longer able to use the Java language," added Tod Nielsen, General Manager for Microsoft's goal.

Letter-based order-7 model from www.cs.princeton.edu/courses/archive/fall04/cos126/assignments/markov.html

Letter-based vs. Word-based Models

Typically letter-based Markov models are used

But letter-based Models of realistic size can only capture a very limited context (even order-7 models handle only 1-1.25 words)

Word-based models can capture a larger context

Need way to handle data sparsity (fallback to lower-order model)

Unlimited vocabulary: Need mechanism to keep model size tractable (pruning mechanism)

Prediction by Partial Match

Originally developed for compression – best compression method known (but slow)

Variant developed in my diploma thesis for Web prefetching – URL sequence prediction

Can also be used for text generation –
word (or token) sequence prediction

Combines Markov models of different orders
(e.g. 1-4)

Stateless order-0 model as fallback

Pruning Mechanism: size of the prediction model is controlled through the use of LRU caches

Prediction by Partial Match

Resulting prediction models:

Observed word sequences:

Blending

Predictions of different orders are blended. We assume that each model is twice as likely to be right as the next shorter one and calculate the combined probability:

where is the probability predicted by the
i-order model for the document d;
h the highest order (default: 4) and
n the number of models to blend (default: 2)

Blending

Blended prediction model:

Stand-alone prediction models:

Encoding:

Input:

Shared text model corpus used to built prediction model (must be immutable, e.g. CD/DVD, RFCs, website snap-shot from archive.org, range of Heise news, Spam corpus)

Sequence of (randomly
distributed) bits to encode
(e.g. encrypted message)

Output:

Generated text (stegotext)

Shared initial step:

Built prediction model from model corpus

PPM-based Steganography

Decoding:

Stegotext

Decoded bit sequence

PPM-based Steganography

Encoding:

While there are bits to encode (leftbits > 0):

sort n predictions for current state by frequency

read upto m=min(n-1, leftbits) bits until next 1 and append prediction:
predi for i-1 0s followed by 1
predm if all bits are 0
(prefix-free variable
length coding)

Decoding:

While there are bits to decode (leftbits > 0)

sort n predictions for current state by frequency

read token, look it up in frequency table and append corresponding bit sequence

Probability Thresholding

Which predictions to consider when en/decoding?

Avoid very rare predictions (e.g. typos):
ignore predn+1 and following if

P(predn+1) < P(predn) / 4

Singletons are ignored by each stand-alone model

To avoid repetitions phrases that would arouse suspiction, the decoder/encoder keeps a cache of last 100 five-token phrases and excludes tokens that would complete a cached phrase (unless there are no other options)

If there is only a single prediction above the threshold, it is appended w/o encoding anything

PPM Stego: Start + End Handling

How to start a stegotext?
How to prevent stegotext from ending in the middle of a sentence?

List of end-of-sentence (EOS) tokens: . ! ?

Initial state: after EOS token (begin of sentence)

Finalization: continue generating random text until an EOS token is among the predictions

Prefix bit sequence by number of bytes to encode
(as a VInt)

Stop decoding if sufficient bytes have been decoded

Non-Reversibility Attack

Non-reversibility attack: stegotexts only contain tokens that are among the predictions above the probability threshold of the current model state

If Wendy suspects which model corpus is used, she can find out whether a text is a possible stegotext

Decoder modification: unexpected tokens are silently ignored (no bits are appended, model state is not changed)

Open Issue: how to modify the encoder to output suitable unexpected token?

Does it matter (any text will be a possible stegotext for some suitable chosen corpora, “plausible deniability”)?

Other Open Issues

Will there be a way to automatically discern stegotexts/generated texts from other texts?

Is there a way to prove that a text is a stegotext?
(If crypto is forbidden, will nonsense texts be forbidden too?)

Other issues?

2003-05-08T15:29:26