Any efficient text-based steganographic schemes?

Question

While there are sophisticated and efficient steganographic schemes with images as cover available, I am yet ignorant of the existence of any fairly efficient and secure schemes with texts as cover. This state of affairs is IMHO unsatisfying, since the communication channel may under circumstances only be able to transfer printable natural language texts, and that in rather small volume, due to constraints posed by the warden.

To be concrete on the efficiency issue, I would desire that the ratio of stego bits to covertext bits be no less than, say, 1/50. For references to existing schemes, if any, or else novel basic ideas that could lead to the development of such a scheme (if possible user-friendly and not too hard to implement), I should be very grateful.

Answer 1

My understanding is that the three most popular approaches to "steganography using text as a cover" are:

1 Generate a completely new text by picking one word at a time from a dictionary, using the ciphertext bits to select which word.

• Pick words in ways that, at first glance, look like real English sentences, using Markov chain algorithms. Weihui Dai. "Text Steganography System Using Markov Chain Source Model and DES Algorithm". (2010). H. Hernan Moraldo. "An Approach for Text Steganography Based on Markov Chains". (2012). "Steganographic Markov Chains". (2008). Anna Lysyanskaya and Mira Meyerovich "Provably Secure Steganography with Imperfect Sampling" (2006). Etc.
• For a given dictionary, picking words with uniform distribution gives you the most ciphertext bits per word, but it's pretty obviously not real English text. Still, these schemes are very popular for sending raw bits over systems (like email, voice, etc.) designed for text: NATO phonetic alphabet, PGP word list, the S/KEY dictionary, the Diceware dictionary, etc.

2 Take some fixed text, and send exactly the same series of letters as in the original text, adding the ciphertext bits by modifying the presentation of that text in ways that we hope the warden doesn't notice.

• Use two slightly different typefaces as in Bacon's cipher (1605).
• Add space characters to the end of lines, where they are usually invisible, as in SNOW (1996?).
• Vary the spacing between words; nudge the letters left-right (nonstandard kerning) or up-down.
• Etc.

3 Take some fixed text, and slightly modify the words in ways that we hope the warden doesn't notice.

• The receiver takes each word, looks it up in the agreed-on thesaurus; if the thesaurus shows 4 synonyms, the receiver decodes that word into 2 ciphertext bits. Nanhe, Kunjir, Sakdeo. “Improved Synonym Approach to Linguistic Steganography”. Shirali-Shahreza. "A New Synonym Text Steganography". Chang and Clark. "Practical Linguistic Steganography using Contextual Synonym Substitution and Vertex Colour Coding".
• The receiver looks for certain "key words", ignoring all the other words.
• The receiver decodes a few bits per sentence by noticing which of several ways (all with equivalent meaning) of arranging the words in that sentence were selected. Grothoff; Grothoff; Alkhutova; Stutsman; and Atallah. "Translation-Based Steganography" (2005). a
• Etc.

Answer 2

The most famous text based steganographic scheme is using the first letters of words / sentences. If the mean sentence length is 15-20 words and mean word length is 5 letters, then efficiency is ~1%. You could use shorter than average sentences and/or words to increase the efficiency to within your bounds of >2%.

Obviously this is a specific example of a class of functions that uses the nth letter of the nth word of each sentence as the hidden message.

This scheme certainly meets the user friendly and not too hard to implement category (provided you have some imagination / a good thesaurus), but won't stand up to much cryptanalysis!

Quick thought - base 26 encode the output from a strong authenticated encryption function, then construct sentences with the first letter of the first word as above?

Answer 3

In his answer Michael mentioned a known stego scheme of using the first characters of words/sentences as stego characters and rightly remarked that the scheme can be practically applied ("user-friendly") only when the stego character sequence is in natural language (i.e. not encrypted, in which case the scheme is however evidently very weak) and not when the stego character sequence is a ciphertext of the actual secret message to be transmitted.

It seems to me that, with an appropriate adaptation/modification, the same classically known idea could nonetheless be usefully exploited, if one could accept certain corresponding reduction in transmission efficiency. To illustrate with a concrete construction: Let the 26 characters of the alphabet be suitably divided into 8 groups (in general of different sizes) such that in each group there is at least one character that fairly frequently is the first character of sentences in natural languge communications. Then, given any arbitrary set of 3 stego bits, the user wouldn't have too much difficulty to write a sentence which is sufficiently natural to the given context of communication and which starts with a character that is in one of the said 8 groups that corresponds to an ecoding by these 3 stego bits. This way, each sentence of the covertext can transmit 3 stego bits which, though not a very high rate, is nevertheless something worthy of consideration in the practice IMHO. (Note that, since one exploits only one character of the words and not the entire words, one naturally has flexibility/simplicity that is hardly attainable with schemes that depend on word substitutions.)

Answer 4

You could use a Cardano grille to solve the problem of steganography (not encryption.) Very difficult to identify or even detect, as long as care is taken when hand-lettering the final message. If the mask's letters are too dense, the language of the cover message needed to conform to those letters can get a bit tortuous.

Also note the grille doesn't need to be based on physical coordinates. You could achieve the same results with a list of numbers that look like dates: 3/4/16, 1/2/08, etc., which could mean: 3rd paragraph, 4th sentence, 16th letter is the first character. 1st paragraph, 2nd sentence, 8th letter is the second character. And so on.

If your concern is cells being inspected by the warden, a random list of date-like numbers might be recognized as a code key, but an inexplicably perforated sheet of paper is also suspicious.

Answer 5

You could hide information in a particular Wiki user's Wikipedia edit history. Someone following a trail of single word edits across a range of Wikipedia documents over a chronologically increasing scale could reconstruct an otherwise hidden message. The key would be the Wikipedia users name, and possibly a number representing which edited word per (out of possibly k edited words per) document was significant.

A secret key that keyed a PRNG could also be used to generate the index of the relevant edited words.

The efficiency is possibly much greater than 1 bit in 50 since you know which words you are looking for : exactly those words edited by User X, the order of which is determined by edit time.

Other ideas could be sharing information over a twitter account, where a distribution that tended towards 1 in every 50 tweets being a part of a message, somehow secretly identified.