This article is about Visual Cryptography. Visual Cryptography is a technique that allows information (images, text, diagrams …) to be encrypted using an encoding system that can be decrypted by the eyes. It does not require a computer to decode.
The technique I’m going to describe is attributed to two great mathematicians: Moni Naor and Adi Shamir, in 1994. In this implementation, I’m going to show how to split a secret message into two components. Both parts are necessary to reconstruct and reveal the secret, and the possession of either one, alone, is useless in determining the secret.
The basis of the technique is the superposition (overlaying) of two semi-transparent layers. Imagine two sheets of transparency covered with a seemingly random collection of black pixels.
Individually, there is no discernable message printed on either one of the sheets. Overlapping them creates addition interference to the light passing through (mathematically the equivalent of performing a Boolean OR operation with the images), but still it just looks like a random collection of pixels.
Mysteriously, however, if the two grids are overlaid correctly, at just the right position, a message magically appears! The patterns are designed to reveal a message.
Let’s look at couple of examples of this in action, then we’ll describe how the technique works.
Below you will see two random looking rectangles of dots. One is fixed in the center, and the other you can drag around the canvas. As the rectangles intersect, the images merge. If you align the rectangles perfectly, a hidden message will appear. There are three hidden message to see in this demonstration, once you’ve decoded one, click on the square button in the bottom left to advance to the next.
To give you feedback, once the images are perfectly aligned, the advance button will go blank with a red border (don’t worry, your computer will not self-destruct in five seconds)
How does it work?
First we take a monochrome image for the source. Pixels in the image are either white or black. To the right is the source for the first example we saw above.
Next we sub-divide each pixel into four smaller subpixels. We need to shade these four subpixels to represent the source image, then subjectively divide them between the two cypher images we are to create.
We need to distribute the shading such that, if you have just one of the cypher images, it is impossible to determine what is on the other cypher image, and thus, impossible to decrypt the image.
What we do is look at the color of each pixel in the original source image. If the original pixel in the image is set (black), we fill in all four sub pixels then distribute them two per cypher layer. We flip a coin to determine which pattern we place on which layer (so that it is random). It does not matter which pair of pixels goes on which layer, when they are combined, all four pixels will be black.
Conversely, if the source image pixel is white, we shade in just two pixels. This time, however, we make sure that the same pixels are shaded on both layers. In this way, when the two cypher images are combined, only two pixels are shaded. As before, we flip a coin to determine which chiral set we go with, and make sure the same image appears on both layers.
The result of this process is two images (both four times as large as the original) which when combined result in an image with half the contrast of the original. The black of the source remains black in the combined cypher, but the white in the source is changed to a randomly mottled half-tone gray. Luckily this is still sufficiently high enough contrast for the secret message to be easily read.
Someone who has possession of only one of the cypher images will be able to determine the (2 x 2) pattern of each pixel but has no idea if the corresponding pixel cluster on the other image is the same (white space), or opposite (black pixel). Every grid of (2 x 2) sub pixels on both layers contains exactly two pixels.
Of course, the two pixels selected do not have to follow checker-board pattern I used above. As long as two are shaded at random, and the rules followed as to whether the same, or complementary, pixels are shaded on the other layer, the system will work.
Here is a short animation of a some of these (2 x 2) pixel sub-blocks sliding over each other:
Pretty cool, huh? Well hold on, it gets cooler …
Moni Naor, Adi Shamir, and more people …
The original paper by Naor and Shamir talks about how to implement this system in a more generic way. For instance, instead of splitting the image into just two cypher texts, why don’t we split the image between n-cyphertexts; all of which are needed to be combined to reveal the final image? (Or possibly a subset of any k images out of these n).
If you are interested in reading more, you can find a reprint of the original paper here.
As an example, here are some (3 x 3) sub-elements that could be used to distribute an image over four cypher images, all of which are needed to be combined to reveal the secret images:
The top line shows the subpixels used to represent a black pixel in the original images, and the bottom line a white pixel.
Any single share contains exactly five black subpixels.
Any stacked pair contains exactly seven black subpixels.
Any stacked triplet contains eight black subpixels.
However, when all four in each row are combined, the top row contains nine subpixels (all black), whilst the lower row contains only eight (allowing light to shine through and creating the contrast necessary to read the image).
You can see from this how the colluding of any two or any three people is not enough to reveal the secret.
(Mathematically it’s possible to do this with eight, not nine, sub-pixels , but there’s no easy way to sub divide and pack a square array with eight!)
Deeper down the rabbit hole: Visual Steganography
We can use this technique to do something even cooler!
Imagine that, in addition to the two source images, we have a third secret image we want to encode. Let’s say we want to produce two cypher images that look ‘innocent’, but secretly hide the third. The generated two cypher images could be printed on transparencies and made to look like legitimate images of no consequence.
However, these images, when combined in just the correct way, could be used reveal a third message.
The technology of hiding images inside other images is called Steganography.
I’ve done this below. Trust me, you’re not going to believe this at first. You’re going to be convinced that there is some ‘behind the scenes’ script at work that changes the image. I assure you this is not the case. You’re still not going to believe me!
Below, on the left, is my name, encoded from a monochrome image, and also containing partial details of a third hidden image. On the right is the word ‘Fish’, similarly encoded. Now, drag the right image over to the left image and watch what happens when they overlap perfectly. Wham! How cool is that?
How does this magic work?
The hidden image we are encoding has black pixels and white pixels. As before, we sub divide each pixel into (2 x 2) subpixels. When the two images are combined, we want to represent the black pixels of the hidden image by having all four subpixels black. We’ll represent the white pixels has having three subpixels black. This is sufficient contrast for the hidden image to be seen.
For each black or white pixel in the hidden image, there are four possible combinations of black and white pixels of the two source images. For the two source images, we’re going to say that any three black subpixels represents black in that source image, and any two pixels represents white.
Examples of all eight permutations of source, image 1 and image 2 are depicted below:
When the hidden image pixel is BLACK:
The combined two cypher images (OR) have to have all four subpixels set.
When both source images also have a black pixel, this is easy. Both cypher images need to have three out of the four subpixels set. The only constraint is that the missing subpixel is not the same on both layers. One subpixel is randomly selected on the first layer, and one is randomly select from the other three on the second layer.
When the first image has a black pixel (requiring three subpixels set), and the second image has a white pixel (requiring two subpixels set), as above, first, a random single subpixel is selected on the black layer to remove. Next two subpixels are randomly selected on the second layer with the constraint that one of the selected subpixels is the same as the gap in the first layer. In this way, when the two are combined, four black subpixels are displayed.
The opposite happens when the first layer is white, and the second layer is black.
Finally, if both source pixels are white (requiring just two subpixels set), two subpixels are selected at random on the first layer, and the inverse of this selection used for the second layer.
When the hidden image pixel is WHITE:
The combined two cypher images (OR) have to have any three subpixels set.
When both source images have a black pixel, this is easy. Both cypher images need to have three out of the four subpixels set, and these need to be the same subpixels. Three subpixels are randomly selected and these are set on both of the cypher image layers.
When the first image has a black pixel (requiring three subpixels set), and the second image has a white pixel (requiring two subpixels set), as above, first, three random subpixels are selected on the first layer. Next one of these three subpixels is randomly selected for removal and this pattern is used on the second layer.
The opposite happens when the first layer is white, and the second layer is black.
Finally, if both source pixels are white (requiring two subpixels set), two are selected at random on the first layer, then one of these is duplicated on the second layer, and a second random subpixel is selected on the second layer (from the two white subpixels not selected on the first layer). Both layers have two subpixels, and when combined, there are three subpixels visbile.
Other potential uses of the concept
The ability to give an answer, and potentially mask a true answer to a question, tangentially, reminds me of a technique used to get truthful representations in surveys where the subject is potentially embarrassing or where there is incentive to not give a truthful answer.
Imagine you are conducting a survey with the aim of measuring certain characteristics of your audience, and the subject of some of the questions is sensitive (for example, questions about political preference, sexual orientation, whether you have committed fraud, or cheated, or made a mistake that has cost your company thousands of dollars). People might have a motivation to give a non-truthful answers, possible from embarrassment, peer pressure, or fear.
Also, paranoid people might not want to give truthful answers for fear that, even if the survey is anonymous, answers to other questions might be enough to allow an individual to be distinctly identified and thus his answers to the sensitive questions determined.
The solution? Give the people taking your questionnaire a coin. When the question appears e.g. “Have you ever made a mistake that has cost your company thousands of dollars?”, ask the subject to flip a coin. If the coin comes up HEADS, tell the person to answer the question truthfully. If the coin comes up TAILS, tell the person to flip the coin again and if the coin lands HEADS to answer ”Yes” and if the second flip comes up TAILS to answer the question ”No”.
Any person looking at the survey results and seeing a ”Yes” on an answer will not know if any single person’s answer is truthful, or the result of a coin flip. Any person can be free of embarrassment as none of his/her peers will know either.
The law of large numbers, however, will allow a good estimate of the number of people “Who have made a costly mistake”, because you’d be able to subtract the number of expected fake ”Yes” answers, then scale up the remainder of the answers.
Other articles related to this topic
If you liked this article, you might also like this article about Steganography, and this one about Sharing Secrets.
Steganography (US i/ˌstɛ.ɡʌnˈɔː.ɡrʌ.fi/, UK /ˌstɛɡ.ənˈɒɡ.rə.fi/) is the practice of concealing a file, message, image, or video within another file, message, image, or video. The word steganography combines the Greek words steganos (στεγανός), meaning “covered, concealed, or protected”, and graphein (γράφειν) meaning “writing”.
The first recorded use of the term was in 1499 by Johannes Trithemius in his Steganographia, a treatise on cryptography and steganography, disguised as a book on magic. Generally, the hidden messages appear to be (or be part of) something else: images, articles, shopping lists, or some other cover text. For example, the hidden message may be in invisible ink between the visible lines of a private letter. Some implementations of steganography that lack a shared secret are forms of security through obscurity, whereas key-dependent steganographic schemes adhere to Kerckhoffs’s principle.
The advantage of steganography over cryptography alone is that the intended secret message does not attract attention to itself as an object of scrutiny. Plainly visible encrypted messages—no matter how unbreakable—arouse interest, and may in themselves be incriminating in countries where encryption is illegal. Thus, whereas cryptography is the practice of protecting the contents of a message alone, steganography is concerned with concealing the fact that a secret message is being sent, as well as concealing the contents of the message.
Steganography includes the concealment of information within computer files. In digital steganography, electronic communications may include steganographic coding inside of a transport layer, such as a document file, image file, program or protocol. Media files are ideal for steganographic transmission because of their large size. For example, a sender might start with an innocuous image file and adjust the color of every 100th pixel to correspond to a letter in the alphabet, a change so subtle that someone not specifically looking for it is unlikely to notice it.
- 1 History
- 2 Techniques
- 3 Additional terminology
- 4 Countermeasures and detection
- 5 Applications
- 6 See also
- 7 Citations
- 8 References
- 9 External links
The first recorded uses of steganography can be traced back to 440 BC when Herodotus mentions two examples in his Histories. Demaratus sent a warning about a forthcoming attack to Greece by writing it directly on the wooden backing of a wax tablet before applying its beeswax surface. Wax tablets were in common use then as reusable writing surfaces, sometimes used for shorthand.
In his work Polygraphiae Johannes Trithemius developed his so-called “Ave-Maria-Cipher” that can hide information in a Latin praise of God. “Auctor Sapientissimus Conseruans Angelica Deferat Nobis Charitas Potentissimi Creatoris” for example contains the concealed word VICIPEDIA.
Steganography has been widely used, including in recent historical times and the present day. Known examples include:
- Hidden messages within wax tablet—in ancient Greece, people wrote messages on wood and covered it with wax that bore an innocent covering message.
- Hidden messages on messenger’s body—also used in ancient Greece. Herodotus tells the story of a message tattooed on the shaved head of a slave of Histiaeus, hidden by the hair that afterwards grew over it, and exposed by shaving the head. The message allegedly carried a warning to Greece about Persian invasion plans. This method has obvious drawbacks, such as delayed transmission while waiting for the slave’s hair to grow, and restrictions on the number and size of messages that can be encoded on one person’s scalp.
- During World War II, the French Resistance sent some messages written on the backs of couriers in invisible ink.
- Hidden messages on paper written in secret inks, under other messages or on the blank parts of other messages
- Messages written in Morse code on yarn and then knitted into a piece of clothing worn by a courier.
- Messages written on envelopes in the area covered by postage stamps.
- In the early days of the printing press, it was common to mix different typefaces on a printed page due to the printer not having enough copies of some letters in one typeface. Because of this, a message could be hidden using two (or more) different typefaces, such as normal or italic.
- During and after World War II, espionage agents used photographically produced microdots to send information back and forth. Microdots were typically minute (less than the size of the period produced by a typewriter). World War II microdots were embedded in the paper and covered with an adhesive, such as collodion. This was reflective, and thus detectable by viewing against glancing light. Alternative techniques included inserting microdots into slits cut into the edge of post cards.
- During WWII, Velvalee Dickinson, a spy for Japan in New York City, sent information to accommodation addresses in neutral South America. She was a dealer in dolls, and her letters discussed the quantity and type of doll to ship. The stegotext was the doll orders, while the concealed “plaintext” was itself encoded and gave information about ship movements, etc. Her case became somewhat famous and she became known as the Doll Woman.
- Jeremiah Denton repeatedly blinked his eyes in Morse Code during the 1966 televised press conference that he was forced into as an American POW by his North Vietnamese captors, spelling out “T-O-R-T-U-R-E”. This confirmed for the first time to the U.S. Military (naval intelligence) and Americans that the North Vietnamese were torturing American POWs.
- Cold War counter-propaganda. In 1968, crew members of the USS Pueblo intelligence ship held as prisoners by North Korea, communicated in sign language during staged photo opportunities, informing the United States they were not defectors, but captives of the North Koreans. In other photos presented to the US, crew members gave “the finger” to the unsuspecting North Koreans, in an attempt to discredit photos that showed them smiling and comfortable.
Modern steganography entered the world in 1985 with the advent of personal computers being applied to classical steganography problems. Development following that was very slow, but has since taken off, going by the large number of steganography software available:
- Concealing messages within the lowest bits of noisy images or sound files.
- Concealing data within encrypted data or within random data. The message to conceal is encrypted, then used to overwrite part of a much larger block of encrypted data or a block of random data (an unbreakable cipher like the one-time pad generates ciphertexts that look perfectly random without the private key).
- Chaffing and winnowing.
- Mimic functions convert one file to have the statistical profile of another. This can thwart statistical methods that help brute-force attacks identify the right solution in a ciphertext-only attack.
- Concealed messages in tampered executable files, exploiting redundancy in the targeted instruction set.
- Pictures embedded in video material (optionally played at slower or faster speed).
- Injecting imperceptible delays to packets sent over the network from the keyboard. Delays in keypresses in some applications (telnet or remote desktop software) can mean a delay in packets, and the delays in the packets can be used to encode data.
- Changing the order of elements in a set.
- Content-Aware Steganography hides information in the semantics a human user assigns to a datagram. These systems offer security against a nonhuman adversary/warden.
- Blog-Steganography. Messages are fractionalized and the (encrypted) pieces are added as comments of orphaned web-logs (or pin boards on social network platforms). In this case the selection of blogs is the symmetric key that sender and recipient are using; the carrier of the hidden message is the whole blogosphere.
- Modifying the echo of a sound file (Echo Steganography).
- Steganography for audio signals.
- Image bit-plane complexity segmentation steganography
- Including data in ignored sections of a file, such as after the logical end of the carrier file.
- Making text the same color as the background in word processor documents, e-mails, and forum posts.
- Using Unicode characters that look like the standard ASCII character set. On most systems, there is no visual difference from ordinary text. Some systems may display the fonts differently, and the extra information would then be easily spotted, of course.
- Using hidden (control) characters, and redundant use of markup (e.g., empty bold, underline or italics) to embed information within HTML, which is visible by examining the document source. HTML pages can contain code for extra blank spaces and tabs at the end of lines, and colours, fonts and sizes, which are not visible when displayed.
- Using non-printing Unicode characters Zero-Width Joiner (ZWJ) and Zero-Width Non-Joiner (ZWNJ). These characters are used for joining and disjoining letters in Arabic and Persian, but can be used in Roman alphabets for hiding information because they have no meaning in Roman alphabets: because they are “zero-width” they are not displayed. ZWJ and ZWNJ can represent “1” and “0”.
In communities with social or government taboos or censorship, people use cultural steganography—hiding messages in idiom, pop culture references, and other messages they share publicly and assume are monitored. This relies on social context to make the underlying messages visible only to certain readers. Examples include:
- Hiding a message in the title and context of a shared video or image
- Misspelling names or words that are popular in the media in a given week, to suggest an alternate meaning
All information hiding techniques that may be used to exchange steganograms in telecommunication networks can be classified under the general term of network steganography. This nomenclature was originally introduced by Krzysztof Szczypiorski in 2003. Contrary to typical steganographic methods that use digital media (images, audio and video files) to hide data, network steganography uses communication protocols’ control elements and their intrinsic functionality. As a result, such methods are harder to detect and eliminate.
Typical network steganography methods involve modification of the properties of a single network protocol. Such modification can be applied to the PDU (Protocol Data Unit), to the time relations between the exchanged PDUs, or both (hybrid methods).
Moreover, it is feasible to utilize the relation between two or more different network protocols to enable secret communication. These applications fall under the term inter-protocol steganography.
Network steganography covers a broad spectrum of techniques, which include, among others:
- Steganophony — the concealment of messages in Voice-over-IP conversations, e.g. the employment of delayed or corrupted packets that would normally be ignored by the receiver (this method is called LACK — Lost Audio Packets Steganography), or, alternatively, hiding information in unused header fields.
- WLAN Steganography – transmission of steganograms in Wireless Local Area Networks. A practical example of WLAN Steganography is the HICCUPS system (Hidden Communication System for Corrupted Networks)
Digital steganography output may be in the form of printed documents. A message, the plaintext, may be first encrypted by traditional means, producing a ciphertext. Then, an innocuous covertext is modified in some way so as to contain the ciphertext, resulting in the stegotext. For example, the letter size, spacing, typeface, or other characteristics of a covertext can be manipulated to carry the hidden message. Only a recipient who knows the technique used can recover the message and then decrypt it. Francis Bacon developed Bacon’s cipher as such a technique.
The ciphertext produced by most digital steganography methods, however, is not printable. Traditional digital methods rely on perturbing noise in the channel file to hide the message, as such, the channel file must be transmitted to the recipient with no additional noise from the transmission. Printing introduces much noise in the ciphertext, generally rendering the message unrecoverable. There are techniques that address this limitation, one notable example is ASCII Art Steganography.
The art of concealing data in a puzzle can take advantage of the degrees of freedom in stating the puzzle, using the starting information to encode a key within the puzzle / puzzle image.
For instance, steganography using sudoku puzzles has as many keys as there are possible solutions of a sudoku puzzle, which is 6.71×1021. This is equivalent to around 70 bits, making it much stronger than the DES method, which uses a 56 bit key.
Discussions of steganography generally use terminology analogous to (and consistent with) conventional radio and communications technology. However, some terms show up in software specifically, and are easily confused. These are most relevant to digital steganographic systems.
The payload is the data covertly communicated. The carrier is the signal, stream, or data file that hides the payload—which differs from the channel (which typically means the type of input, such as a JPEG image). The resulting signal, stream, or data file with the encoded payload is sometimes called the package, stego file, or covert message. The percentage of bytes, samples, or other signal elements modified to encode the payload is called the encoding density, and is typically expressed as a number between 0 and 1.
In a set of files, those files considered likely to contain a payload are suspects. A suspect identified through some type of statistical analysis might be referred to as a candidate.
Countermeasures and detection
Detecting physical steganography requires careful physical examination—including the use of magnification, developer chemicals and ultraviolet light. It is a time-consuming process with obvious resource implications, even in countries that employ large numbers of people to spy on their fellow nationals. However, it is feasible to screen mail of certain suspected individuals or institutions, such as prisons or prisoner-of-war (POW) camps.
During World War II, prisoner of war camps gave prisoners specially treated paper that would reveal invisible ink. An article in the 24 June 1948 issue of Paper Trade Journal by the Technical Director of the United States Government Printing Office, Morris S. Kantrowitz, describes, in general terms, the development of this paper. They used three prototype papers named Sensicoat, Anilith, and Coatalith. These were for the manufacture of post cards and stationery provided to German prisoners of war in the US and Canada. If POWs tried to write a hidden message, the special paper rendered it visible. The U.S. granted at least two patents related to this technology—one to Kantrowitz, U.S. Patent 2,515,232, “Water-Detecting paper and Water-Detecting Coating Composition Therefor,” patented 18 July 1950, and an earlier one, “Moisture-Sensitive Paper and the Manufacture Thereof”, U.S. Patent 2,445,586, patented 20 July 1948. A similar strategy is to issue prisoners with writing paper ruled with a water-soluble ink that runs in contact with water-based invisible ink.
In computing, steganographically encoded package detection is called steganalysis. The simplest method to detect modified files, however, is to compare them to known originals. For example, to detect information being moved through the graphics on a website, an analyst can maintain known clean-copies of these materials and compare them against the current contents of the site. The differences, assuming the carrier is the same, comprise the payload. In general, using extremely high compression rates makes steganography difficult, but not impossible. Compression errors provide a hiding place for data, but high compression reduces the amount of data available to hold the payload, raising the encoding density, which facilitates easier detection (in extreme cases, even by casual observation).
Use in modern printers
Some modern computer printers use steganography, including HP and Xerox brand color laser printers. These printers add tiny yellow dots to each page. The barely-visible dots contain encoded printer serial numbers and date and time stamps.
Example from modern practice
The larger the cover message (in binary data, the number of bits) relative to the hidden message, the easier it is to hide the latter. For this reason, digital pictures (which contain large amounts of data) are used to hide messages on the Internet and on other communication media. It is not clear how common this actually is. For example: a 24-bit bitmap uses 8 bits to represent each of the three color values (red, green, and blue) at each pixel. The blue alone has 28 different levels of blue intensity. The difference between 11111111 and 11111110 in the value for blue intensity is likely to be undetectable by the human eye. Therefore, the least significant bit can be used more or less undetectably for something else other than color information. If this is repeated for the green and the red elements of each pixel as well, it is possible to encode one letter of ASCII text for every three pixels.
Stated somewhat more formally, the objective for making steganographic encoding difficult to detect is to ensure that the changes to the carrier (the original signal) due to the injection of the payload (the signal to covertly embed) are visually (and ideally, statistically) negligible; that is to say, the changes are indistinguishable from the noise floor of the carrier. Any medium can be a carrier, but media with a large amount of redundant or compressible information are better suited.
From an information theoretical point of view, this means that the channel must have more capacity than the “surface” signal requires; that is, there must be redundancy. For a digital image, this may be noise from the imaging element; for digital audio, it may be noise from recording techniques or amplification equipment. In general, electronics that digitize an analog signal suffer from several noise sources such as thermal noise, flicker noise, and shot noise. This noise provides enough variation in the captured digital information that it can be exploited as a noise cover for hidden data. In addition, lossy compression schemes (such as JPEG) always introduce some error into the decompressed data; it is possible to exploit this for steganographic use as well.
Steganography can be used for digital watermarking, where a message (being simply an identifier) is hidden in an image so that its source can be tracked or verified (for example, Coded Anti-Piracy), or even just to identify an image (as in the EURion constellation).
Alleged use by intelligence services
In 2010, the Federal Bureau of Investigation alleged that the Russian foreign intelligence service uses customized steganography software for embedding encrypted text messages inside image files for certain communications with “illegal agents” (agents under non-diplomatic cover) stationed abroad.
There are distributed steganography methods, including methodologies that distribute the payload through multiple carrier files in diverse locations to make detection more difficult. For example, U.S. Patent 8,527,779 by cryptographer William Easttom (Chuck Easttom).
The online mechanism Cicada 3301 incorporates steganography with cryptography and other solving techniques since 2012.