Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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.

share|improve this question

5 Answers 5

The most famous text based steganographic scheme is the acrostic: 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?

share|improve this answer
    
I doubt your point of 'user friendly'. Could you give some convincing examples or references containing such? –  Mok-Kong Shen Jan 23 '13 at 10:15
    
By user friendly I meant easy for a human to decode unaided (just read off the relevant letters), and relatively easy for a human to construct unaided (think up appropriate words to start sentences). These properties disappear if you use the encrypted variant I proposed. –  Michael Jan 23 '13 at 21:27
    
Right. But my previous comment was for encrypted stego bits. (Encryption is a necessity if a stego scheme is to be of any non-trivial usage in practice nowadays at least.) –  Mok-Kong Shen Jan 23 '13 at 22:34
1  
This steganographic scheme is called an acrostic ( Wikipedia: acrostic ). –  David Cary Oct 16 '13 at 16:27

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.

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.

share|improve this answer
    
Concerning (2): With careful examination of inserted spaces at line-end etc., the warden can easily detect these. Thus they are insecure IMHO. I have myself designed a scheme using the number of words per line to transmit one stego-bit (EMAILSTEGANO in s13.zetaboards.com/crypto) but its stego-bit rate is very low. Much higher stego-bit rates would IMHO be badly needed in certain practical situations. I'll be very interested in schemes using the 3rd method you listed under (3) above. Do you happen to have a few references to them? –  Mok-Kong Shen Jan 25 '13 at 9:03
    
@Mok-KongShen: Yes, the warden can easily detect trailing whitespace -- but often trailing whitespace accidentally and innocently ends up in files I write and others as well. How can a warden detect a real covert channel without getting false positives from such innocent accidental whitespace? If the warden cannot distinguish innocent random whitespace from a real covert channel, then the steganographic channel is secure IMHO. –  David Cary Feb 1 '13 at 18:34
    
Accidental trailing spaces are by definition rare. If a stego scheme capitlizes on exploiting trailing spaces, there would be lots of them to attract the warden's attention. Of course almost everything in the real world is connected with probabilities. There is barely 100% surety. One knows that even courts sometimes (have to) base their verdicts on the so-called presumptive evidences and thus occassionally innocent people go to jail because of that. –  Mok-Kong Shen Feb 1 '13 at 22:40
    
I guess that a weak point of translation-based stego is: Why should a sender send a (poor quality) translation and not the original so that the recipient could have it translated himself (there being facilities on the Internet) and also have the original to check in case ambiguities arise? That question might lead the warden to wonder under circumstances IMHO. On the other hand poor quality messages presumably could work well, if the sender is known to be fairly poor in language competence, e.g. an immigrant taking yet a language course. –  Mok-Kong Shen Feb 2 '13 at 8:41

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.)

share|improve this answer

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.

share|improve this answer
    
But the editing must have some sense at the superficial level and that would be difficult, wouldn't it? Wouldn't very frequent editing attract suspicions of the warden? –  Mok-Kong Shen Feb 2 '13 at 8:12
    
You could automatically replace words with 'synonyms'. I'm sure it would if it was very frequent. Although there must be lots of activity on there anyway. If you need high thruput...maybe a network of twitter robots faithfully reposting various news articles 24/7....there's enough content and control in such a stream you could set up some stego on it. –  Cris Stringfellow Feb 2 '13 at 10:29
    
IMHO it would be better to avoid frequent modifications of the same piece of text in order not to cause suspicions of the warden, i.e. one simply employs instead other viable channels that transmit new pieces of texts. –  Mok-Kong Shen Feb 2 '13 at 11:02

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.

share|improve this answer
    
A grille is commonly classified as a transposition cipher if I don't err. –  Mok-Kong Shen Mar 26 '13 at 14:16

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.