12
$\begingroup$

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.

[Addendum 1, edited] I have in the meantime a scheme named WORDLISTTEXTSTEGANOGRAPHY that should achieve a not large but IMHO practically nonetheless useful efficiency in the range of [0.5, 1.0] bit per word of natural language texts, requiring though that the user does some amount of trial and error work under the guidance of the software. (Use e.g. of an appropriate codebook could highly compress the input stegobit sequence.) The latest Version 2.1 of it, running on Python V.3.6.1, is available at my new home page: http://mok-kong-shen.de. See update notes in it for the differences to the earlier versions. (I regret in particular that in the earlier versions a sentence is missing in the explanation of how to do the examples, with the very unfavourable consequence that new users may fail to do the examples.)

$\endgroup$
  • $\begingroup$ Related: "Steganography to hide text within text" $\endgroup$ – David Cary Dec 21 '14 at 15:30
  • $\begingroup$ If you consider the practicality of such a scheme, it depends highly on what kind of text you expect, and what kind of freedom you have. If you have informal messages, where you can use typos, wrong punctuation, double spacings, line breaks as you wish, ... this gives you a lot of freedom to put information, where a properly edited book would allow for much less without being noticed. And that's just an example of a covert channel, which might exist or not. $\endgroup$ – tylo Oct 6 '16 at 10:17
  • $\begingroup$ @tylo: Opinions may certainly differ and disputes on them are by nature senseless. I personally deem anyway the device of utilizing typos etc. for stego purposes to be too weak in general in the current day context. $\endgroup$ – Mok-Kong Shen Oct 9 '16 at 9:28
  • $\begingroup$ @Mok-KongShen I guess you're right about opinions there. I would just say, that the practicality depends a lot on the context. In some cases, a a stego mechanism works well, in others it is spotted easily. And steganography in texts is much more difficult to hide than e.g. images or sound, because language contains a lot more structure and not much "noise". $\endgroup$ – tylo Oct 10 '16 at 11:53
  • $\begingroup$ [Temporary comment:] Due to differences between Python V.3.5 and the newest Python V.3.6.1, Version 2 of my software, which has been tested on Python V.3.5 can't run on Python V.3.6.1. I'll provide a solution soon. $\endgroup$ – Mok-Kong Shen Apr 15 '17 at 10:12
7
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – Mok-Kong Shen Jan 25 '13 at 9:03
  • $\begingroup$ @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. $\endgroup$ – David Cary Feb 1 '13 at 18:34
  • $\begingroup$ 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. $\endgroup$ – Mok-Kong Shen Feb 1 '13 at 22:40
  • $\begingroup$ 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. $\endgroup$ – Mok-Kong Shen Feb 2 '13 at 8:41
4
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ I doubt your point of 'user friendly'. Could you give some convincing examples or references containing such? $\endgroup$ – Mok-Kong Shen Jan 23 '13 at 10:15
  • $\begingroup$ 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. $\endgroup$ – Michael Jan 23 '13 at 21:27
  • 1
    $\begingroup$ 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.) $\endgroup$ – Mok-Kong Shen Jan 23 '13 at 22:34
  • 1
    $\begingroup$ This steganographic scheme is called an acrostic ( Wikipedia: acrostic ). $\endgroup$ – David Cary Oct 16 '13 at 16:27
3
$\begingroup$

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

$\endgroup$
  • $\begingroup$ After quite some experiments in the said direction, I have found that for easy/conveinent work of the sender one has unfortunately to reduce the bit embedding rate to 1 bit per sentence. Description of the scheme and a code to verify by computer the correctness of the manual work is in: s13.zetaboards.com/Crypto/topic/7338098/1 $\endgroup$ – Mok-Kong Shen Feb 11 '15 at 10:29
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ A grille is commonly classified as a transposition cipher if I don't err. $\endgroup$ – Mok-Kong Shen Mar 26 '13 at 14:16
1
$\begingroup$

I've developed one here:

https://github.com/mjethani/typo

In a nutshell, every 4 bits of the secret message is encoded as a typo in the stegotext. The value of the typo is the 4 least significant bits of the first byte of its SHA-256 hash. For example, the typo "infirmation" (information) carries the value 0xE (0b1110). The recipient simply identifies the typos and hashes them to extract the information.

Why is this great?

Everybody makes typing errors.

On the other hand, fake typos may fool a human, but they won't fool a machine. The main challenge is to generate typos that are resistant to all kinds of analyses.

I'm afraid this encoding scheme does not meet your criterion of 1/50. It's probably closer to 1/100.

$\endgroup$
  • $\begingroup$ Hi, Manish, and welcome to Crypto Stack Exchange. I took a quick look at your scheme, and it looks pretty clever. On the other hand (and with no fault on your part implied), your answer did make me start to wonder if this question might not be a bit too broad for a Q&A site like this one; while your project seems interesting enough, we'd really rather not see dozens of other people following your example and also coming here to post links to their own steganography tools. Thus, I've decided to vote to close this question; we'll see if other people here agree. $\endgroup$ – Ilmari Karonen Apr 8 '15 at 23:52
  • $\begingroup$ Just came across this. If you added a "password" which is appended to the message before hashing, that would make it resistant to computer aided detection. If you could demonstrate that your typo model was a good statistical model for human typos, that should cover the other half of the risk: that a computer will realize there's something up with the typos. (of course, even in that case, you merely detect stenographic content, but can't derive the contents) $\endgroup$ – Cort Ammon Apr 13 '17 at 19:20
0
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ 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? $\endgroup$ – Mok-Kong Shen Feb 2 '13 at 8:12
  • $\begingroup$ 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. $\endgroup$ – Cris Stringfellow Feb 2 '13 at 10:29
  • 1
    $\begingroup$ 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. $\endgroup$ – Mok-Kong Shen Feb 2 '13 at 11:02
0
$\begingroup$

So there is this technique which allows for a cover text quite shockingly smaller than expected! Perhaps some excessive effort may come along with steganography like this; a fair criticism. Null ciphers for doing manual encryption generally do.

The above paragraph contains the hidden word STACKEXCHANGE.

To reveal it, take the first word of the above paragraph, then every 3rd word after it:

So this allows cover shockingly expected! excessive come steganography a Null doing generally

  • Highlight in the first word, and every 3rd word after, the letter at position 11 modulus the word's length.

    Highlight in the second word, and every 3rd word after, the letter at position 5 modulus the word's length.

    Highlight in the third word, and every 3rd word after, the letter at position 25 modulus the word's length.

[S]o [t]his [a]llows [c]over shoc[k]ingly [e]xpected! e[x]cessive [c]ome steganograp[h]y [a] [N]ull doin[g] g[e]nerally

The highlighted letters construct the secret message:

StackexchaNge

The sequence 11, 5, 25 (along with the knowledge to take only every 3rd word beginning with the first) is the key, whose numbers, when translated into the letter at that position in the alphabet, become the string:

KEY

You can verify this by inputting the first paragraph at this page with key set to KEY and word spacing set to 3.

$\endgroup$

protected by e-sushi Oct 6 '16 at 6:25

Thank you for your interest in this question. Because it has attracted low-quality or spam answers that had to be removed, posting an answer now requires 10 reputation on this site (the association bonus does not count).

Would you like to answer one of these unanswered questions instead?

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