What is the advantage of steganography

Steganography

by Alexandra Weikert

Steganographic procedures were used in the past to hide messages in more innocuous information. For example, you can use citric acid to write a letter invisibly between the lines of a completely different letter and later make the writing visible again with warmth. Or you can mark certain words of the harmless letter with pin pricks, which of course can only be discovered against the light. Another method is described in the "History of Two Cities" by Charles Dickens. The women in the story knit information into left and right stitches - instead of the values ​​0 and 1 as bit values. Today there are electronic methods, which are described here.

Why should one work with steganographic processes today?

The encryption of data is increasingly coming under attack due to misuse (for child pornography, terrorism or general crime). But that shouldn't be a reason to forego encryption, but rather a reason to hide encrypted data.

What conditions should such an algorithm meet?

  1. No obvious changes to the carrier data, i.e. the hidden data should only be minimally perceptible. In principle, one has to distract the viewer from the data, even if it is not visible - like a magician who makes a rabbit disappear before our eyes, although we know for sure that it cannot vanish into thin air.
  2. The hidden data should withstand all changes, regardless of whether it is due to noise, filters, encryption, fuzzy, i.e. lossy, compression, reducing the size of the carrier material, printing, or converting to other file formats.
  3. Encrypting the data with asymmetrical procedures (RSA, PGP) before hiding it is desirable. This hides the data better, as "white noise" remains after encryption, but does not make it more difficult to access (but even if it is found, it is still encrypted!)
  4. Error correction should ensure the correctness of the data.
  5. The hidden data should be stored with enough redundancy that all data can be restored with the help of error correction if a bit is lost.

Applications:

Regardless of the impairment of the carrier material, data can be stored in two different ways: either a lot of data is hidden that is very susceptible to changes, or less that can withstand changes quite well.

But you can't do both at the same time. The value of security in recovery is reciprocal of the amount of data that can be hidden. All systems can be reluctant to change for a wider range. The amount of data hidden and the security of recovery vary from program to program. There are different programs for different applications.

Digital watermarks are hidden data that are not obviously intended to change the carrier material, but which must be easy to find so that the watermark can fulfill its purpose: e.g. prove the origin of an image.

Preparing to hide data

The encryption of the data with RSA, DES creates an absolutely uniform distribution, white noise, also of course PGP 2.6.3i Most steganography algorithms work best when they are fed with white noise. If you use encrypted files without hiding them, you can assume that they arouse curiosity, since they are white noise and can therefore be recognized as encrypted. It is therefore a good option to first encrypt a file and then hide it in another file. Cryptography makes steganography more secure, even if it can do without it.

DES uses a 56-bit key to encrypt 64-bit blocks. In 16 steps, the individual pieces are broken down into two 32-bit parts, encrypted and swapped. However, DES is a linear function with a key that must be known to both parties, the sender and the recipient.

Encryption methods with public keys are better. Two keys are used here, one public and one private. The sender encrypts the message with the public key, while the recipient can decrypt the message with the private key. The public key alone is worthless.

Since you can neither predict exactly what the next letter will look like for DES nor for RSA, e.g. if you know the first 3, you cannot make a prediction about the next one, which is why this is always called white noise. You can only try to crack the key with a direct attack, but not by calculating on the basis of the key. Pure encryption methods like DES and RSA are good at creating white noise that looks very random. If you start by hiding data in other data, this is a good start to fool the world. In addition, there is currently no known way to crack these algorithms, and the corresponding programs are also very easy to use.

Compression of the data

The data to be saved should always be compressed
  • to save space in the carrier file.
  • to keep the original filename.
  • to make plaintext attacks more difficult.
  • in order to be able to use automatic error correction options.

A hiding place in the noise

Noise is a part of our life. The advertising for various digital devices tries to pretend to us that digital circuits are noise-free and therefore better. But that is only half the truth. The digital signal can be copied over and over again without loss thanks to the built-in error correction and well-designed circuitry, but it cannot eliminate the noise that is already there. Digitized images, digitized music, and digitized movies all have a significant amount of noise from their original production. The circuits / programs that convert voices, sounds and images to bits are all not quite perfect. A bit of electrical noise changes the bits a bit and there is no way to prevent it. Noise will always be with us.

But this noise is also an opportunity for us. If it is not important whether the bits are really 100% correct, then anyone who wants to hide information can take advantage of this uncertainty. You can "occupy" these bits. This is the most popular form of steganography and the one that offers the most options.

In the networks of this world there are millions of images, as the background of websites, or within them, and who else knows for what. You can kidnap these bits and use them to transport your own messages.

The principle is simple. Digitized images or sounds are represented by numbers that represent the intensity at a specific time and space. A digital photo is just a matrix of numbers that stand for the intent of light, as it was / can be seen at a certain time in a certain place. Digital tones are just lists of the pressure exerted on a microphone in certain time slices.

All of these numbers are imprecise. Digital photo devices that produce images are not perfect because the arrangement of charge-coupled devices that store the photons depends on random effects of physics. In order for these devices to work with normal room lighting, they often have to respond to a few photons. But the randomness of this world ensures that sometimes too many and sometimes too few photons hit. On a long-term average, the number of photons will even out, but the CCD often has to create an image within a split second. So in some places a bit of brightness or color is missing. It's the same with microphones.

The amount of noise available to hide information in an image can be staggering. Many color digital images hold 32 bits for each pixel. The proportions of red, blue and green, or of cyan, magenta and yellow of each pixel are stored in 8 bits each. That makes 24 bits. If only one bit per color value is used to hide information per pixel, 10% of the file size can be used for this. In the best case scenario, I have a Kodak Photo CD with 3072 x 2048 pixels and 18 MB available. This could hide 1.8 MB of information. An ordinary novel about 250 pages long is about 500 KB or half a MB. This could hide a lot of information in addition to the content of a novel in a single picture. But not everyone will want to waste 18MB on a single image. Blurred images often get by with 200 to 600 KB and still offer 10% for hiding data.

But if 10% of the total storage space is available, how much is the image affected? Each byte stores a number between 0 and 255. The last bit in each group of 8 bits is called the "Least Significant Bit" (LSB). The value of this bit is 1. The most important bit, i.e. the first, has the value 128 when the bit takes the value 1. This means that the least important bit (LSB) can change the intensity of a pixel by a maximum of 0.5 - 1%. (1/128 or 1/255). If you accept about 1% change in the original data, you can hide about 10% of the original size in data. A good deal.

There is no reason not to keep more data in the same file. If the last two unimportant bits are used to hide data in it, then each pixel can be changed by a maximum of 3 units. That's still only 1 - 3% of a pixel. But that means that you can occupy about 25% of the image size with other data. A wide range is just waiting to be discovered.

Bug fix

With computers, too, one must reckon with a certain randomness, even if one does not actually assume that. Computer developers have these randomnesses in their grasp with a good mix of precision and math. A decent computer has everything under control to the extent that it is clean, and the rest is cleaned up using mathematical processes. Mathamatics make it possible to create a digital cycle with a certain inaccuracy that would not be possible in the analog world. This inaccuracy can be corrected with the help of appropriate mathematics.

Also, the error correction algorithms for hiding data well can be very important. The simplest method is to deliberately build small errors into a file, and do so in a very orderly manner. If someone else accesses this file with ordinary programs, error correction will strike and nobody would find out. More sophisticated programs could compare the cleaned file with the original or simply use error correction methods to find the appropriate places where data could be hidden.

Another possibility is to insert data in freely available files that are, for example, "floating around" on the Internet. Problems only arise when two or more people come up with the same idea and one message is overwritten by another. To do this, however, one could go over to only describing parts of such files, since the data can be recovered through the error correction even with small overlaps.

Messages can also be distributed over several files and sent in different ways. If parts have been compromised, they can be recovered through error correction.

Splitting secret messages

There are several times when it is useful to divide up the information. Only when all the information carriers come together can the puzzle be put together. (e.g. two keys for the bank vault)

It is possible to split up a message so that not everyone has to be present to receive the whole message, or that everyone is needed.

It is not always desirable to need everyone involved to restore a secret. A better variant can be that several people can restore the whole thing with one part. One possibility is to assume that the secret is a specific number x at the numerical level. This allows you to lay a straight line - and a whole lot more. If you know two of these arbitrarily many straight lines, you can calculate the common point of intersection and thus obtain x. If you only know one of these lines, you are just as smart as before. But you only ever need a second, with the knowledge of another straight line to reveal the secret. If more than two people are needed to decipher a message, for example, you can assume straight lines in space, then you need 3 equations and thus 3 people. If more secret carriers are desired, n-dimensional equations for points in the n-th dimension can be selected and distributed.

Of course, you can also distribute points on the first line (and thus the secrets) that represent the intersection with other straight lines, or points on the y-axis, with corresponding straight lines that intersect the y-axis precisely at these points. This is a very simple way of dividing a secret in such a way that a certain subset of those involved must always be present in order to restore the secret. However, it is not advisable to distribute points over 2 straight lines, as only a few points are necessary for the solution of this system and so the secret can be revealed if only a few participants and not all actually required are present.

Self-denial

Another way of dividing information: You can, for example, provide an image on your own website in which information is hidden. However, these cannot be extracted that easily. To do this, you need three other, obvious images from the web - e.g. one on the Disney World website, one from NASA and a vacation photo of a traveler to the Far East from Germany. The LSBs (Least Significant Bits) are extracted from these three images and added to the information from the image from your own website - only then do you receive the secret message.

The advantage of this method is that it is not possible to say exactly who is providing the actual information. From Disney World? Or from NASA? If you provide the information in only 4 pictures, you can perhaps find the cause with a little effort, but with 100 pictures?

However, one should pay attention to how the images that are made available on the web were created. If, for example, a computer-generated image from the "Toy Story" is used, very predictable statements can be made about the LSBs and Disney World is eliminated as the cause. The background noise of the selected images should be very clear.

File Formats, Compression, and Practical Problems

If one really wants to use this channel for the transmission of information, there are a few practical problems. Most image and audio files contain enough natural noise to hide a 3% change. Here you can see an ordinary black and white picture:

The noise can be clearly seen. A change in the LSBs is not noticeable here. So it is very possible to hide information in this picture.

Many image and audio files have enough noise to hide data. There is enough material in the first picture that small changes go unnoticed. But there are also pictures that don't hide the incorporated information as well. Images that were created on the computer, e.g. with Paintbush or Adobe Illustrator or Corel Draw. Large areas are evenly filled with one color. Even if this image is changed just a little, it can be easily discovered because the uniform color is superimposed with a noise. (Actually, these even colors hurt the eyes. That's why artists change these surfaces a bit and overlay them with a texture. This then gives you the opportunity to hide data in them again.)

Data formats are a serious problem for anyone who regularly wants to use bit-level steganography to hide data. Many image and audio file formats are intended to filter out the noise in order to save space. This can be done with a very special and efficient file format like GIF, or with a very aggressive compression program like JPEG that doesn't care if the image is exactly the same after reconstruction as it was before. Both formats make it difficult to simply hide information in the least important bit of the image.

The GIF file format and its 8-bit standard is a major obstacle because 8-bit colors are very different from 24-bit colors. A table with 256 different colors is used here.These selected colors best represent the colors in the picture. The color of each pixel is now described by an entry in this color table, namely the color that comes closest to the actual one. The bits have no relation to the intensity of the color of each pixel. If you change the least important bit, this does not mean that you change the intensity insignificantly by a maximum of 1%, but that you now get entry 17 (dark blue) instead of entry 16 of the color table (light yellow). They only differ in the least important bit, but that can make a serious difference in the result.

There are a ton of different solutions to this problem. One possibility is to use a smaller number of colors.

Instead of choosing 256 colors to represent the colors of the image, one can choose 128 and then 128 others that are very similar to the former. You can even use the same 128 colors, but that would be too suspicious. The table could be arranged so that two very similar colors differ in only one bit. Example:

Number:binary coderedgreenblue
000000000904022
100000001894120
20000001012011375
30000001112310771
400000100318999
500000101289495
...............

If you want to hide the value 1 in a pixel, you can find the most similar color in the table by setting the least important bit to 1. If the most similar color to the original has the color values ​​red = 119, green = 114 and blue = 71 and 1 bit is to be hidden in it, then you select the color with the number 3 from the color table, if you want to hide a 0, use get the colors number 2 from the table.

There is no reason why the least important bit must be used in separate pairs. Any of these bits can be used. The selection can also be made via the 3rd bit. (or via the 1st and 3rd)

Also, there is no need to encrypt only 1 bit per pixel; the same algorithm that is used to select the closest 128 colors out of 256 can also be used to select the next 64 colors. Then 2 bits per pixel could be encrypted. Obviously, this can degrade the quality of the image. E.g. also when trying to hide 4 bits per pixel. This would only have 16 colors available for the actual color table. For example, if a person is shown in the picture, then probably one color is selected for the background, one for the hair color, one for the sweater and maybe only 2 colors for the skin color. That skin color would look rather terrible. Since most attention is paid to the skin color when seeing through the human eyes, it is advisable to use an algorithm that accordingly tries to assign the most (different) colors to the skin.

But each of these two colors would also carry 4 bits of information. And that means that there are a total of 16 spare colors, which are distributed pretty randomly. These naturally give the skin color a surface structure and thereby reduce the conspicuousness of the color distribution.

Another important hurdle for hiding data in image or audio files is compression functions. Compression is so ubiquitous that there are various compression options for different purposes, to accommodate data in smaller files and then, for example, to send them over a network (such as the Internet), or to store large amounts of data on a disk that is actually too small. One compression method is JPEG, MPEG is a very similar standard for moving pictures.

Both methods are very dangerous for storing information at the bit level because they are a lossy Use compression methods. If you take a digital image, compress it with JPEG, and then decompress it again later, the result will not be exactly what you initially had. It will be very similar to the original, but it's not the same. In contrast to lossless methods such as those used for text compression, this is a great contrast. These functions restore the data word by word. Lossy compression methods, however, enable significantly greater compression because they don't give a damn about details. The end result is enough anyway. However, the JPEG algorithm itself is adaptable. You can compress data even further if you accept further losses in accuracy. So you can change the algorithm so far that not only a pixel takes on a certain color, but a whole block.

It is not easy to combat JPEG's handling of image files. If the lossy function does not restore the file correctly, then details and with them information that was embedded in it are lost. This is probably why a lot of people use compression in GIF files. In addition, the disadvantage of the somewhat larger files in contrast to JPEG files is outweighed by ever faster network connections and ever larger storage media (hard drives).

The use of JPEG

At the beginning we complained that JPEG left unwanted effects in images that information was stored in the LSB. Since the compression is not lossless, information that was embedded in this file can vanish into thin air, as JPEG does not restore the file to the original. Although there are problems with data compression with JPEG, that does not mean that the JPEG algorithm is not suitable for successfully storing information in image files.

There are two different ways to use the JPEG algorithm to store information. The first examines the complexity of the image. The second stores information in JPEG files.

The JPEG algorithm is a good tool to identify the level of detail in an image. This level can be used to find the area of ​​the image where the noise level is highest.

The JPEG algorithm automatically divides the image into areas and recognizes the most important or salient areas. After all, it was designed to do just that, to increase the compression factor. The program produces good results, even if some details are lost during compression.

This algorithm makes it possible to identify the important areas of an image. In addition, you can choose the level of accuracy of the image yourself. If you still want the image to look good after hiding the data, then JPEG should be set to large depth of field and after that it may find a small number of bits to store data in. If the depth of field is not so important, JPEG also offers more bits for storage.

The above image as a JPEG with shallow depth of field:

LSBs of this JPEG file show very clearly the areas with a greater level of detail:

The only problem with a non-lossless process like JPEG is that the information cannot be recovered as easily as when data is embedded in a GIF file. In the case of a GIF file, the receiver can simply extract the LSBs and thus restore the data one-to-one. You don't need the original image for this. Since JPEG identifies the areas in the corners and columns of the image where information can lurk, the sender and recipient need the list of the areas used. Both sides need the original image for this. But that leads to problems when you want to exchange information with someone you have never met before. Somehow the person concerned has to get a copy of the original first.

Hiding information in JPEG files

It is an open secret that the approach with the lossy JPEG method to store information confuses the principle method. The noise can be changed in any direction, so you could completely neglect the data format at first. Derek Upham was not satisfied with that and followed up with it. JPEG compresses the files in two steps. First, the image is divided into blocks of 8 x 8 pixels and then cosine functions are applied to these pixels in order to represent them. Then the frequencies / abundances of these cosine functions are stored as a description of these blocks. Upham then found that you can change the least important bits of this frequency in order to store information in them.

But this is not the only reason that speaks for this procedure. Programs like S-Tools and Stego run through the same calculations over and over again to hide information in 8-bit color images. However, these images then contain color tables with very similar neighboring color entries. This works so well so far, but can be seen relatively easily when the color table is searched.

Changing the frequencies of a discrete cosine function that represents an 8 x 8 block has a completely different effect. Even if these changes affect the quality of the final image, these effects are barely noticeable. The discrete cosine functions are inherently approximations and how should one perceive small changes in an approximation? Ultimately, the storage of the bits is controlled by whether the JPEG program rounds up or down. Rounding up means 1, rounding down means 0. These numbers can be restored by looking at the least important bit (LSB) of the frequency.

Upham also has an unusual approach to data hiding. You need a header that shows how many bits have been saved. Usually this is an integer for which 32 bits are required, e.g. 12751. Upham noticed that there are always leading zeros in front of the number. Since the bits are usually randomly distributed, a series of zeros is always suspect: Sixteen zeros in series should appear in one out of 65536 cases.

For this reason, the size of the data to be hidden in JPEG is limited to 1 GB, since the 6th bit in each case is set to 0 in half of all cases, since this is usually a 1.

That is why his header contains two number fields. The first contains the length of the second field, which in turn contains the number of bits in the entire file. This eliminates large blocks of the same bits at the beginning of the number and still maintains the flexibility for extremely large files. He also suggests that the second field be separated from the first with an additional zero every second time. This prevents the 6th bit from always being a 1.

Digital watermarks

Robust marking methods as copy protection for image and audio files

Watermarks have been incorporated into paper for around 2000 years, until around the Middle Ages. The watermark was the trademark of the manufacturer and often said something about the composition of the paper. In the digital age, the watermark is used to mark files, e.g. to record the author, such as a photographer.

One application that hides a minimal amount of data is digital watermarks. The inserted data provide information about the owner of the carrier material. They serve the same purpose as the signature of the author (or photographer) or a company logo. Since this information is important and can be subject to intelligent and deliberate attacks to remove or destroy the watermark, the method by which the information is hidden must be immune to a variety of changes.

Another application is resistant to changes in the carrier material. It is used to indicate attempted changes in the original carrier signal. A change in the hidden data automatically induces that the carrier signal has been changed.

A third application is the storage of background information in images. This data is embedded in special areas. These data are not typical targets of Intentional Change. Pictures are often changed, reduced in size, cut off, or the color nuances changed. This is why this data must also withstand changes.

Image or audio file headers and footers can take up a lot of space. Therefore, additional channels are required for their storage. This additional information is lost if the file format is changed, e.g. from TIFF (Tagged Image File Format) to GIF (Graphic Interchange Format). These problems are circumvented by incorporating this additional information directly into the data structure of the carrier signal.

This side of the steganography is mainly used commercially - the programs for inserting watermarks alone show that: there is no shareware ... The aim of the industry is, for example, to sell pieces of music via the Internet to a known buyer (customer number, billing, etc. ), which can copy this file exactly once. Then a specific copy bit is set to prevent the file from being copied again. This actually contradicts the previous approach, since LPs, CDs or MCs could always be copied several times and also lend out. In addition: who already has enough disk space to save a lot of music, e.g. on his hard drive?

The copy bit is part of a watermark that must be woven into the original file. In contrast to hidden data, the watermark should of course be able to be found, but not impair the enjoyment of the picture or piece of music.

Requirements for a marking method:

  • It must be possible to extract the label without the original image.
  • The method should be able to be applied directly to compressed data so that the insertion and extraction of the marking can be carried out in real time.
  • The marking should be neither visible nor audible.
  • The marker must be able to withstand JPEG / MPEG compression to some extent, which can be determined beforehand.
  • The method must be able to withstand changes which do not seriously degrade the quality, such as filtering, clipping, reducing or enlarging.
  • Hundreds of bits can be stored in an image.

The resistance is reciprocal to the size of the marking: the larger the watermark, the less it can be protected from destruction by JPEG compression.

Possible methods of embedding watermarks:

  1. The patchwork method: A set of pairs of picture elements (ai, bi) are chosen at random and the brightness of ai um 1 increased, while that of Bi by 1 is reduced. At n changed points you get a difference of 2n. If a quality of more than 75% is obtained with a JPEG compression, there is an 85% probability that the embedded data can be restored.
  2. The picture is split in half with the help of a random number generator. In the case of a subset, the brightness is around k elevated. k is calculated by the difference between two random samples of the two subsets. To check for watermarks, the mean of the two subsets is calculated. Is he k, the file contains a watermark, is k = 0 then not. However, this type of watermark is only retained with JPEG compression with a quality of at least 90%. k is called the level of the marking. The picture is first broken down into blocks and k determined for each block, the watermark can be larger and more resistant. The level for each block is calculated using a second, lower quality JPEG copy.

    The two methods hardly influence each other, so you can use both methods on one and the same image, so that the size of the watermark can be doubled. If DCT is applied to the file first, then the patchwork method, the watermark will not be visible. Even with a JPEG compression of 75%, the watermark can still be extracted again well.

    Another possibility to insert a watermark into an image is to work a watermark into one of the three color layers. So it is only visible when you look at the layers of paint separately, but not when you look at the whole picture.

    Commercial products for embedding watermarks: PictureMarc (incl. SpiderMarc) from DigiMarc, the digital DNA from the Californian company Solena, the program from Liquid Audi, SureSign from Signum Technologies and EIKON Amark, TigerMark from NEC, or SysCoP (TM) des Fraunhofer Institute for Computer Graphics in Darmstadt. In the audio sector: Musicode from ARIS Technologies (Cambridge, MA)

    Each program works with a different method, so that one cannot read the watermarks one below the other. The algorithms for this are of course not disclosed, otherwise the watermarks could be deleted from the carrier files.

    But there are already programs like StirMark or unZign that completely destroy electronic watermarks in images without affecting the image itself. These programs have so far been able to remove the watermarks of all commercial programs.

    In the area of ​​digital watermarks, a great deal will have to change before it can be used effectively.