23

One of the drawbacks of traditional steganography is that both parties need to exchange a secret key. Encryption had this problem too but circumvented this with public key cryptography.

Are there any cases where this has been done with steganography, where a message can be encoded with a public key and retrieved with a private one?

Google seems to bring up a few research papers but nothing practical.

Remember steganography is considered broken if the presence of a message is detected.

Edit to explain more

Alice wants to send Bob a message, however Eve is monitoring Alice's communication.

Alice can encrypt a message, but Eve will know that a message was sent and can demand the key from Bob to read the message.

Alice can use a keyless steganography algorithm to embed a message in an image, but Eve can check any images sent for messages using known algorithms.

Alice can encrypt a message and use a keyless steganography algorithm but Eve can check the image, extract the message and then demand the key from Bob

Alice could use a keyed steganography algorithm and Eve would not be able to detect a message even if he was checking. However Alice has no way to get the key to Bob so that he can read the message.

If there is such a thing as public key steganography Alice could embed a message using Bob's public key Eve would not be able to detect a message and Bob could read it without the need to exchange a key. However I don't know if such a thing exists.

Edit 2

This question and it's answer points out the issue with the 'encryption as random noise' suggestion. Encryption is not specifically designed to be indistinguishable from random noise, it is an artifact of some systems but not guaranteed.

Community
  • 1
Jeremy French
  • 537
  • 5
  • 12
  • You can do this, but you still need to share a key some how to get to the message. If a third party can get hold of the key the existence of the message will not be secret – Jeremy French Jul 06 '15 at 22:24
  • The difference is that without a key you would not know there was a message. – Jeremy French Jul 06 '15 at 22:50
  • 9
    Your question seems to assume that there are two mutually exclusive types of steganography: (1) keyless steg, in which it is straightforward to determine, unequivocally, that a message is hidden (and to extract it, although it may be encrypted), and (2) keyed steg, in which it is *impossible* to detect the presence of a hidden message (without the key).  I question that premise; I am not familiar with any such dichotomy.  Can you support it with references?  … … … … …  P.S. When talking about communication between “Alice” and “Bob”, it’s conventional to refer to the **eave**sdropper as “Eve”. – Scott - Слава Україні Jul 07 '15 at 11:50
  • http://www.ws.binghamton.edu/fridrich/Research/Keysearch_SPIE.pdf talks about how to crack stego keys. I'll use Eve in future. Was thinking about the 'old bill'. – Jeremy French Jul 07 '15 at 12:14
  • 3
    I did a Google search and found this paper talking about PKI Steganography: http://www.zurich.ibm.com/~cca/papers/pkstego.pdf So, the answer seems to be "yes". – schroeder Jul 07 '15 at 17:12
  • 4
    When I do a Google search on "public key steganography", the *second* hit is a research paper with the title "[Public-Key Steganography](http://www.cs.cmu.edu/~biglou/pubkeystego.pdf)" explaining that the answer is "yes" and showing how to do it. We expect you to do a significant amount of research before asking, and show us what you've tried or what approaches you've considered/rejected in the question. If 30 seconds with Google shows the answer, you probably haven't done enough research before asking. http://security.stackexchange.com/help/how-to-ask – D.W. Jul 07 '15 at 21:32
  • 1
    This is similar to the subliminal channel technique mentioned at Applied Cryptography sections 23.3 and 4.2. – Pacerier Dec 25 '16 at 01:30
  • 2
    Your EDIT 2 is incorrect. See https://en.m.wikipedia.org/wiki/Distinguishing_attack – Awn May 03 '17 at 13:31
  • I second Awn. A place where you might have encountered this is when setting up linux with LUKS disk encryption; the default is to "overwrite the disk with random data to prevent meta-information leaks" which depends on precisely this property. – J.A.K. Apr 23 '18 at 23:38

8 Answers8

26

One of the draw backs of traditional steganography is that both parties need to exchange a secret key.

Don't infer from the implementation of one specific tool to the limits of steganography itself. Steganography is just the hiding of information within other data. It does not matter if the information you want to hide by itself are unencrypted, rot13, encrypted with a shared key or encrypted with PGP or similar. This means you can encrypt a message with whatever encryption system you like and then hide the encrypted message using steganography.

Steffen Ullrich
  • 190,458
  • 29
  • 381
  • 434
  • 3
    But as I understand without a key you are relying on security through every obscurity. Anyone with an algorithm can check for and extract a message. – Jeremy French Jul 07 '15 at 07:46
  • 8
    @JeremyFrench: Of course steganography works only by obscuring the real data. That's why you better still encrypt the message. But the encryption process is independent from the obfuscation with steganography and can be done with a shared key, PGP or whatever you prefer. This is the same as with email: the transport of the mail is independent of the encryption method used for the contents of the mail. – Steffen Ullrich Jul 07 '15 at 10:45
  • 3
    But the goal of steganography is for the message to be undetectable. For this to be effective you need to have a key to retrieve the payload. Otherwise anyone who is looking can extract it, even if they can't read it. If this has to be a shared key, you have a problem of how to share it without being detected. – Jeremy French Jul 07 '15 at 11:00
  • 5
    @JeremyFrench: Steganography has no goal, you have. Steganography provides you with a way to hide a message from plain view, which can be part of the protection. It does not offer encryption by itself, you need to add this yourself. There might be tools which combine encryption with steganography, but these are specific tools not underlying techniques. – Steffen Ullrich Jul 07 '15 at 11:03
  • 1
    Let me rephrase. "The goal of someone using Steganography is to have the presence of a hidden message not be detected." A stenographic system is considered broken if the presence of a message is detected. I am asking about a type of key based Steganography that I have seen discussed but not seen practical examples of. – Jeremy French Jul 07 '15 at 11:10
  • 4
    @JeremyFrench: Typically steganographic implementations requires that you provide data which is indistinguishable from random data to ensure the hidden message is not detectable. A common property of modern encryption methods is that they output data that is indistinguishable from random data. Steganography does not in itself require encryption, it is however the only practical way of using it, as far as I know. So you are free to use PGP or any other public-key encryption system, as long as it outputs ciphertext which is indistinguishable from random data. – bjarkef Jul 07 '15 at 11:20
  • I've edited to address that point. – Jeremy French Jul 07 '15 at 11:42
  • @JeremyFrench: it might be that the "secret key" you talk about is that the receiver of the message has to know how the sender encoded the message. Sometimes it is enough which algorithm was used, sometimes you also need specific parameters for the algorithms (i.e. the key you talk about). But of course this knowledge must be available for the receiver before it can read the message and thus can not be part of the message. You could use a variety of ways to transport this information, including mails using public key cryptography like PGP. – Steffen Ullrich Jul 07 '15 at 12:03
  • But if you want to keep the fact that you are communicating in secret concealed you can't send encrypted messages to exchange steno keys. You need some way to conceal the messages. catch 22 – Jeremy French Jul 07 '15 at 13:19
  • 2
    @JeremyFrench: you cannot expect to have a protection by using only steganography if you assume that both attacker and recipient have exactly the same knowledge. In this case both might get the same result (i.e. they find a hidden message or not) and thus you have some other kind of protection, like encrypting the message with PGP where only the recipients knows the private key. – Steffen Ullrich Jul 07 '15 at 13:38
  • @JeremyFrench If you never plainly communicate the fact that you want to communicate, how does the intended recipient even know to look for a message? If you communicate your desire to communicate via some side channel, like meeting in person, then the solution is simple: exchange public keys on that side channel. – Kevin Krumwiede Jul 07 '15 at 20:39
  • 1
    @JeremyFrench Just because anybody knowing the steganography algorithm can extract the message, it doesn't mean they can know if there is a message. Using the extraction algorithm on a file with no hidden message is supposed to produce a random output. Before using steganography you just need to encrypt with an algorithm that produces random looking output (so you need an encryption that doesn't use any recognizable headers). – kasperd Jul 07 '15 at 22:15
20

This is the first I've heard of keyed steganography, so I'll recap the article you linked, for the benefit of others who might be confused about it. They have narrowed down the number of steganographic algorithms they're analyzing quite a bit. The message must be embedded in a JPEG image (perhaps any raster image format?), and it can't utilize the entire image. The assumption they've made is that the person putting the message in has selected n pseudo-randomly selected bits, and the selection of these bits starts from a key of some kind.

They state that, given such an image, they can detect the bits that are part of the message. BUT, without the key, all you have is n bits, which has n! permutations (potential messages). You don't know their order, but if you find the key you can figure it out. Obviously, this mimics symmetric-key encryption. The key is kept secret, and the people who put the message in use the same key as the people who take it out.

The trick to getting an algorithm that uses a private/public key then would be to mimic the same algorithms in encryption. I don't have much experience with encryption algorithms, but finding a 'random walk' through some pixels looks an awful lot like elliptic curve cryptography, where the field is the pixels in the image. In fact, searching for 'elliptic curve steganography' yields results that looks promising. I haven't looked at any of them deeply though. At least the ACM hit looks promising.

Most of the steganography-based techniques are within the domain of private key encryption algorithms with the less security level rather than using public key algorithms. An attempt to create the secret code for image steganography for multimedia messaging service or MMS using elliptic curve cryptography has been demonstrated.

There's even a project on github. So it looks like the answer is "Yes, there is such a thing as public key steganography".

S.L. Barth
  • 5,504
  • 8
  • 39
  • 47
Shaz
  • 374
  • 1
  • 4
7

"One of the draw backs of traditional steganography is that both parties need to exchange a secret key."

No, steganography does not require any key (symmetric or asymmetric) as it doesn't use encryption at all. The real drawback of steganography it's that it is just security by obscurity; you hope the adversary won't discover the hidden message (or that you are actually communicating a message). Concerning this last point, often encryption and steganography are used together, to encrypt a message and then protecting the metadata.

EDIT: I wrote this before the OP edited the question. What is said above applies only to keyless steganography.

dr_
  • 5,109
  • 4
  • 20
  • 30
  • 2
    That is why you have keyed steganography, without the key you should not be able to detect a message. "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" from wikipedia – Jeremy French Jul 07 '15 at 08:29
  • +1 That's interesting, thanks for the note. AFAIK keyed steganography is not used much in the real world; do you know examples of common usage? – dr_ Jul 07 '15 at 08:35
  • 2
    Not currently, but given some government's desire to ban encryption it may be needed more if citizens wish to communicate privately. – Jeremy French Jul 07 '15 at 09:17
  • @dr01, Are you kidding? Steganography is used all the time. Steganography and obscurity means the same thing and obscurity is used all the time. – Pacerier Dec 25 '16 at 01:35
  • @Pacerier No, that's wrong. Steganography and obscurity, while related (steganography is in fact security by obscurity) are two different things. – dr_ Jan 03 '17 at 10:05
3

You've got a plaintext that you want to send me. Encrypt it with my public key first to generate the ciphertext. Then, using absolutely standard steganography interleave the bits of the ciphertext into the carrier: images, music, and so on.

Had you not used public-key encryption then you'd just intermingle the plaintext into the carrier. To the steganograpy algorithm, its just a string of octets whether encrypted or not.

msw
  • 202
  • 1
  • 7
  • 1
    That is great for encrypting a message, but you are relying on obscurity to hope that the existence of the message is not detected. – Jeremy French Jul 07 '15 at 09:04
  • 2
    @JeremyFrench: No he is not. If the public key encryption generates statistically random ciphertext, which is typically the case, and the steganographic algorithm works as intended, the messages is undetectable except if you have the correct private key. – bjarkef Jul 07 '15 at 11:35
  • 2
    Please see update to question. public key cryptography != white noise. – Jeremy French Jul 07 '15 at 11:43
  • I never expected that the encryption need be random in my answer. If not random, with a goodly amount of work you can probably determine that there is a message in the image. While this could be useful for traffic analysis, the message itself is as hard to decrypt as if I'd sent it as a non-hidden message. – msw Jul 07 '15 at 17:15
2

A cyphertext generated with a proper encryption algorithm is indistinguishable from random noise. That means with most steganography methods, cyphertext might be harder to detect than paintext, because statistic analysis does not work.

However, the details depend on the steganography method used. Implementations vary greatly. For example, it might be suspicious when only the upper third of an image has random noise on the last bit of the blue channel and in the rest of the image it is all zeros. In most implementations it would make sense to pad the cyphertext to the maximum length allowed by the used method.

Philipp
  • 49,017
  • 8
  • 127
  • 158
  • I thought that too. But looking at this question indicates otherwise, especially for public key cryptography https://security.stackexchange.com/questions/61080/what-cryptosystem-makes-the-encrypted-text-look-like-random-noise – Jeremy French Jul 07 '15 at 09:25
  • 1
    Unless the encryption algorithm has been specifically designed to make *every bit* of its output indistinguishable from random noise, it probably has a cleartext "envelope" -- containing things like the message length, the algorithms involved, and the IV -- which are easily distinguishable from randomness, and may be near-constant across messages. If you have a large collection of files that you suspect of containing steganographic messages, detecting the *same* envelope in many of them would be the proverbial smoking gun. – zwol Jul 07 '15 at 17:34
1

The idea of Telex is to circumvent censorship by using a public key to embed an undetectable marker into user’s traffic and then have “friendly” ISPs, who know the secret, detect this marker and redirect the user’s request as appropriate.

Unfortunately, the project appears to be dead.

kirelagin
  • 290
  • 3
  • 5
-2

How about this:

  1. Encrypt message with random symmetric key.
  2. Check randomness of resulting cyphertext, if it is distinguishable from noise, try another random key.
  3. Encrypt key with public-key of Bob
  4. Hide encrypted key + message with steganography.

When the eavesdropper intercepts the message and uses steganography, he will only get the encrypted message which is not distinguishable from random noise resulting from no hidden message. Bob can use his private key to recover the random key from the first x bit and then decode the message with it.

For the symmetric encryption you can use an algorithm which produces fairly random encrypted output and always compare the output to statistical noise from unaltered images - when you can't tell the difference you have found a key which is suitable.

The asymmetrical encrypted random-key at the beginning will not be too long and will most likely also pass as noise, since it didn't have any pattern to begin with and is quite short.

Falco
  • 1,492
  • 10
  • 14
-2

I don't know any standard techniques, but the closest I can think of is the folowing:

If Bob has a public key publicly available, Alice can use it to encrypt the secret message, then send him a link to a specific, detailed stenography technique, in the "hey, look what's interesting" spirit, applying that same technique for embedding the encrypted secret in the overt message (e.g. in an attached picture). Hopefully, Bob would get the clue and specifically check if that technique was used to embed a secret in that very message, encrypted with his public key.

Risky, but might work. Alice may try to tip Bob off with a simple comment that seems mundane except to insiders, e.g. saying "my cat is sick" when only Bob knows Alice hates cats and would never have one. (not a good example, ownership of cats is a pretty leaky secret, but you get the idea)

Emilio M Bumachar
  • 507
  • 2
  • 9