PaperlayerView exact revision on arXiv

Source-linked AI summary

An Approach for Text Steganography Based on Markov Chains

H. Hernan Moraldo

arXiv:1409.0915v1cs.MMcs.CL

TL;DR

Fixed-bits-per-word text steganography can produce syntactically random-looking output because it generates words independently of context. This paper encodes data into Markov-generated text while aiming to preserve the supplied model more accurately; preliminary tests report text sizes about 6–7 times the original data size, with further analysis needed.

  • Problem

    Fixed-bits-per-word text steganography generates words independently of context, producing text that is syntactically random-looking.

    Source: §1 · p. 1

  • Method

    The method encodes input data as text generated from a Markov chain, with encoding and decoding designed to be inverse functions.

    Source: §4 · p. 4, §4.1 · p. 5, §4.2 · p. 7

  • Results

    Preliminary tests with a large Markov chain computed from literary text found encoded data takes about 6–7 times the original data size.

    Source: §6 · p. 14

  • Takeaways & Limitations

    The method avoids much of the probability simplification used by similar models, and a reference implementation is presented.

    Source: §6 · p. 14

    The measured algorithm performance and comparison with existing algorithms in steganalysis remain future research.

    Source: §6 · p. 14

Abstract

from arXiv · show

A text steganography method based on Markov chains is introduced, together with a reference implementation. This method allows for information hiding in texts that are automatically generated following a given Markov model. Other Markov - based systems of this kind rely on big simplifications of the language model to work, which produces less natural looking and more easily detectable texts. The method described here is designed to generate texts within a good approximation of the original language model provided.

1 Introduction

Text steganography hides information in text, but fixed-bits-per-word methods generate words independently of context and can produce syntactically random-looking output. This paper explores Markov-model text generation for encoding hidden messages and includes a reference implementation.

1 Introduction

  • Fixed-bits-per-word methods generate words independently of context, making their output obviously random at the syntactic level.Other approaches modify existing text or use grammar models, which can produce grammatical but not necessarily semantically coherent text.Source: §1 · p. 1
  • The paper explores using Markov models to generate texts that encode hidden messages.Earlier Markov-based approaches are also noted, including work by Weihui Dai et al. and a similar simple implementation.Source: §1 · pp. 1–2
  • The article examines a specific Markov-chain text-steganography method and how it compares with similar methods.It also provides a reference implementation in the open-source program MarkovTextStego.Source: §1 · p. 2

2 Related Work

Prior Markov-chain steganography generates text intended to simulate a supplied chain, but simplifications can alter generated-word frequencies. This paper asks whether those probabilities can be preserved more accurately while keeping the model a good approximation of the supplied chain.

2 Related Work

  • Prior Markov-chain steganography generates text intended to simulate a supplied chain, but simplifying its probabilities can significantly change generated-text quality.One simplification assigns equal probabilities to all outbound states, although phrase-start frequencies can differ, as with “the” and “naturally.”Source: §2 · p. 2
  • Other Markov-based or similar models also simplify chain probabilities, including methods that replace outbound probabilities explicitly or through encoding.The passage cites [8] for these approaches.Source: §2 · p. 2
  • This paper asks whether Markov-model probabilities can be preserved more accurately and aims to approximate the supplied model well.The method is not optimally precise.Source: §2 · p. 2

3 Markov Chain Models

The paper presents Markov chains as state-based models for language, where transition probabilities support phrase calculation and random text generation. Its steganographic approach reduces probability simplification, preserving n-gram frequency proportions for the most part, especially in long texts.

3 Markov Chain Models

  • A Markov chain models a stochastic process with limited memory: transition probabilities depend on the current state, not sequence position.The passage describes the chain as having no memory beyond the last state and time-independent conditional probabilities.Source: §3 · pp. 2–3
  • In a transition diagram, nodes are states and arrows encode conditional transition probabilities; here, states represent words and “start” marks sentence boundaries.Markov models may also use characters or n-grams as states.Source: §3 · p. 3, Figure 1 · p. 3
  • Random text generation starts at “start,” repeatedly samples a next state using its transition probability, and can stop when “start” is reached again.The state sequence can also represent a phrase’s probability; the example sequence [s1, s4, s7] has probability 0.28.Source: §3 · p. 3
  • Although a Markov chain remembers one previous state, using bigrams or longer n-grams as states can represent more language history.The article describes single-word states; its reference implementation supports unigrams and bigrams and can be extended to n-grams with n > 2.Source: §3 · pp. 3–4
  • A word-state language model can be computed from unigram and bigram frequencies, with each bigram count divided by its preceding word’s count.These counts give the conditional probability of the next word given the previous word.Source: §3 · p. 4
  • Earlier steganographic models simplify transition probabilities before encoding, while the paper’s approach reduces such simplification.In the described earlier models, words store fixed or variable amounts of bytes and generated bigrams must have positive conditional probability; decoding reverses encoding.Source: §3 · p. 4
  • The approach avoids much probability simplification, preserving proportions among different n-gram frequencies for the most part, especially in long texts.Some precision loss remains.Source: §3 · p. 4

4 Fixed-size Steganography

Section 4 encodes fixed-size data as paths through a Markov chain’s range partitions, with decoding following the same path to recover the input. The method approximates transition probabilities, while a finite-precision moving window reduces the cost of processing long ranges.

4 Fixed-size Steganography

  • Fixed-size encoding requires distinct data inputs of the same length to produce distinct texts; encode is not cryptographically secure and assumes plaintext or independently encrypted input.The full encoding and decoding functions are built from fixed-size versions.Source: §4 · pp. 4–5

4.1 Mapping of Probabilities to Ranges

  • The subranges function partitions a range among a state’s outbound states, aiming for range-size proportions that approximate their transition probabilities.The proportion condition supports texts approximately described by the original Markov language model.Source: §4.1 · pp. 5–6
  • The Condition of Minimal Length requires at least two subranges when a state has multiple outbound states, ensuring termination but sometimes worsening probability fidelity.For transitions of 0.99 and 0.01, the restriction can rule out assigning the full range to the 0.99 state.Source: §4.1 · p. 6

4.2 Encoding Fixed-size Data Using Markov Chains

  • Encoding repeatedly partitions a range by outbound-state probabilities and selects the subrange containing the input, producing a state sequence that distinguishes inputs of the same size.The process stops when the selected range has length 1.Source: §4.2 · p. 7

4.3 Decoding of Fixed-size Data Using Markov Chains

  • Decoding follows the encoded state sequence through the same partitions until the range has length 1, recovering the original input; arbitrary texts are not guaranteed to decode validly.After fixed-size decoding finishes, appending more text does not change the decoded value, allowing encoded texts to be concatenated.Source: §4.3 · p. 10

4.4 Implementation Details

  • A moving bit window avoids processing the full n-bit range at every iteration, while a finite precision limit trades partition accuracy against the number of bits processed.The paper’s example gives an s1 range share of about 0.305 using 8 bits versus about 0.312 using 4 bits.Source: §4.4 · pp. 10–11

5 Variable Size Encoding and Decoding

The variable-size extension avoids requiring recipients to know the hidden data size beforehand by encoding a fixed-size length header before the data. Decoding reads that header and then extracts the data.

5 Variable Size Encoding and Decoding

  • A fixed-size header of shared size m encodes the data length before the data is encoded, allowing variable-size decoding.The header is encoded into c1; the data follows in c2.Source: §5 · p. 13
  • The data text c2 starts from the final symbol of header text c1, preserving flow between the two parts.The complete encoding is the header text followed by the data text.Source: §5 · p. 13
  • Decoding first extracts length information from the header using shared m, then defines decode from that header information.The extension addresses the need for the recipient to know data size beforehand.Source: §5 · pp. 11, 13
  • The decoding process recovers the original data, and a random Markov-generated ending can complete the final sentence without affecting decoding.The optional random text ends with a period.Source: §5 · pp. 13–14
  • For length encoding, little endian or reversed big endian is preferable because big-endian short lengths can produce repetitive starts.This can occur when the encoded length begins with zero bits.Source: §5 · p. 14

6 Conclusions and Future Research

The paper presents a Markov-chain steganography method that avoids precision loss in the language model, together with a reference implementation. Preliminary tests report encoded-text sizes relative to the original data, while fuller performance and steganalysis analysis remains future work.

6 Conclusions and Future Research

  • The method avoids precision loss in the language model and is accompanied by a reference implementation.The implementation is included in MarkovTextStego.Source: §6 · p. 14
  • Capacity depends on the Markov chain: a small chain has low capacity, while a bigger chain typically has higher capacity.The examples in Table 1 may therefore appear to show low capacity because of the chain used.Source: §6 · p. 14
  • About 6–7 times the original data size is required for encoded data with a sufficiently large n; compressed texts are about 2 times the original data size.For very small n, though larger than a few bytes, the factor can be around 9; the results are preliminary and require more thorough analysis.Source: §6 · p. 14
  • Further work includes measuring the algorithm’s performance and comparing it with existing algorithms in steganalysis.The paper also proposes combining the method with other language-based steganographic systems.Source: §6 · p. 14
Loading 1409.0915v1…