Slashdot is powered by your submissions, so send in your scoop

 



Forgot your password?
typodupeerror
Security Communications Encryption Science

Researchers Calculate Capacity of a Steganographic Channel 114

Posted by timothy
from the intentionally-not-left-blank dept.
KentuckyFC writes "Steganography is the art of hiding a message in such a way that only the sender and receiver realize it is there. (By contrast, cryptography disguises the content of a message but makes no attempt to hide it.) The central problem for steganographers is how much data can be hidden without being detected. But the complexity of this problem has meant it has been largely ignored. Now two computer scientists (one working for Google) have made a major theoretical breakthrough by tackling the problem in the same way that the electrical engineer Claude Shannon calculated the capacity of an ordinary communications channel in the 1940s. In Shannon's theory, a transmission is considered successful if the decoder properly determines which message the encoder has sent. In the stego-channel, a transmission is successful if the decoder properly determines the sent message without anybody else detecting its presence (abstract). Studying a stego-channel in this way leads to some counter-intuitive results: for example, in certain circumstances, doubling the number of algorithms looking for hidden data can increase the capacity of the steganographic channel"
This discussion has been archived. No new comments can be posted.

Researchers Calculate Capacity of a Steganographic Channel

Comments Filter:
  • by ccguy (1116865) * on Tuesday November 04, 2008 @10:33AM (#25626581) Homepage

    The results are interesting and in some cases counter-intuitive (for example, adding noise to channel can increase its steganographic capacity

    How is that counter-intuitive? Many of us regularly backup our stuff here in slashdot, and no one has complained so far (which, being the slashdot crowd what it is, is definite proof that no one has noticed).

    In fact, a port of gmail drive to slashdot is already in beta.

    • by russotto (537200)

      It's not counter-intuitive at all that adding noise to a channel can increase its steganographic capacity, since steganographic data can look like noise.

      • Re: (Score:2, Insightful)

        by ccguy (1116865) *
        That's what I'm saying.

        Slashdot. Noise and redundancy. Backup for nerds.
        • Re: (Score:2, Funny)

          by Anonymous Coward

          Lorem ipsum dolor sit amet, consectetuer adipiscing elit. Maecenas non felis. Cras in ligula in odio pellentesque vehicula. Aliquam metus nulla, venenatis sit amet, feugiat nec, pharetra ut, justo. Fusce tincidunt, massa eu iaculis iaculis, lacus nisi ullamcorper orci, ac sodales arcu massa at urna. Ut mattis nulla interdum urna. Praesent consequat. Fusce pede diam, pretium tempor, egestas eget, rhoncus in, sem. Sed semper. Nam in lorem sed nisl blandit commodo. Donec tempus, eros vel fermentum dictum, nibh

      • Re: (Score:3, Insightful)

        by DarthJohn (1160097)

        That's not what it says (somebody fixed a typo in the summary?).

        in certain circumstances, doubling the number of algorithms looking for hidden data can increase the capacity of the steganographic channel

        More people looking for hidden data makes it possible to hide more data. I find that counter-intuitive.

        • by russotto (537200)
          It says both:

          The results are interesting and in some cases counter-intuitive (for example, adding noise to channel can increase its steganographic capacity and in some cases, mounting two attacks on a channel instead of one can do the same)

          I find the second counterintuitive, but the first not so. Perhaps the article-writers intended for the first to be "interesting" and the second "counter-intuitive", but to be fair to the summary-writer, it's not that clear.

        • Re: (Score:2, Funny)

          by Anonymous Coward

          Is that what they mean? It's very counterintuitive if so.

          I read it to mean that if the user (rather than the interceptor) uses various algorithms to store data he can store more data, which is not counter-intuitive at all.

          Bugger, we're going to have to RTFA.

        • by Golddess (1361003)

          More people looking for hidden data makes it possible to hide more data. I find that counter-intuitive.

          Not more people, different people. IE, say you've got a channel with two sets of hidden data intermingled with each other. One algorithm will decode the one set, while a second algorithm decodes the second.

          At least that's how it sounded to me.

        • It's part of a hidden, encrypted data stream!
    • "Steganography" sounds like what God did with the Bible, leaving various messages "encoded" in the text of Scripture. The method of having only those the message is intended for find it is ironically simple: those who don't credit the Bible for reliability won't look for them in the first place. Those who do, will study the Bible and incidentally find them in that study.
  • by CRCulver (715279) <crculver@christopherculver.com> on Tuesday November 04, 2008 @10:38AM (#25626689) Homepage

    Around the turn of the millennium steganography became a big topic, the idea being that using PGP would only draw attention from the authorities. In my Amazon review of Schneier's Applied Cryptography [amazon.com] I even complained that Bruce didn't talk about how to hide even the use of crypto.

    But now that SSL is everywhere and the use of encrypted VPNs is a typical part of telecommuting, I don't think cryptography suggests the same anti-authoritarian counter-culture rumblings it used to. Do we need to hide crypto anymore?

    • by zappepcs (820751) on Tuesday November 04, 2008 @10:54AM (#25627065) Journal

      Well, there may not be a pressing public need to hide cryptography usage, but if you want your data secure from prying eyes, additional measures are a good idea. Blue-Ray just got hacked (again) and it was supposed to be valid security for a decade... right?

      If what you encrypt with can be broken by others, then it is not doing the intended job. If you use PGP, and the decrypted message between you and another trusted user is encrypted already, the likelihood of your message being decoded is substantially less.

      In south or terse, I touch in kelp. You are wrought on girls, but it's young urine poor obese ladle mate.

      Encrypting is not hard, but if what you decrypt looks like this above, it may be hard to decipher and not worth the effort. BTW, that is decipherable.

      Both the PGP and this encryption (or another) can be decoded quickly on the fly. It's possible that those pesky 'terrorists' could be using v1 aGr4 spam to send messages.

      • by Ironsides (739422) on Tuesday November 04, 2008 @11:25AM (#25627775) Homepage Journal
        Bluray is not a good counterpoint. Bluray is not designed to keep the contents from being read by anyone but the 'appropriate person', it is designed to keep anyone from copying it. However, it still meeds to be readable in the player. As such, it is like trying to keep someone from photocopying something while they still need to be able to read/view it. In encryption, you don't care if the 'appropriate person' copy it, you just don't want anyone else to be able to view it.
        • Re: (Score:3, Interesting)

          by zappepcs (820751)

          While that is all true, I mentioned Blue-ray only because it was supposed to be tough encryption to break. "Supposed to be" is the key part of that sentence, and it demonstrates how fragile simple encryption really is.

          While the hacker can find an unencrypted version of a movie and more or less determine what the encryption should look like when decoded, your common text messages are not much different. There are algorithms that can determine much of what you wrote by looking at repeating characters. Length

          • Re: (Score:3, Insightful)

            by Sancho (17056) *

            What was broken was not encryption. It's a form of DRM which did not rely on encryption.

            BD+ (the DRM component which they claimed would last for 10 years) is a virtual machine on which a disc can run arbitrary code. The disc can run this code to try to guess at the authenticity of the player in which it is being played. The idea is that if a player has been tampered with, it can be detected by the disc. It also means that as new attacks on players become possible, it's possible to update the checks that

            • ... which did not rely on encryption

              Yes, and no. Some of those "traps" that the BDVM code can call are cryptography methods. However the encryption keys used will either be generated by the BDVM code, or are already known from the AACS system.

      • In south or terse, I touch in kelp. You are wrought on girls, but it's young urine poor obese ladle mate

        Looks like the spam I get just about every day! The only thing missing is the cheap c14L15 ;)

      • If what you encrypt with can be broken by others, then it is not doing the intended job.

        WRONG.

        Cryptography only needs to be strong enough to protect the encoded contents for as long as said contents retain value. It does not need to remain unbroken forever.

        In south or terse, I touch in kelp. You are wrought on girls, but it's young urine poor obese ladle mate.

        Encrypting is not hard, but if what you decrypt looks like this above, it may be hard to decipher and not worth

    • by Ngarrang (1023425) on Tuesday November 04, 2008 @10:56AM (#25627107) Journal

      Do we need to hide crypto anymore?

      Yes. There are many places in this world where freedom of information is oppressed. Having a method of communicating in the clear without raising any red flags is a Good Thing(tm).

      For example, let's say you are an evil political dissident in China, trying to spread ideas of democracy and capitalism. If you send an encrypted message to your corrupt imperialist American ally, that seems suspicious. If you have nothing to hide, then why are you hiding it?

      But, if you can send your friend a message about how you are growing corn in relatively poor conditions and how great the local government has been in supporting the effort...with a stego message hidden inside, then that is probably going to slip right through.

      The best way to not get caught is to look like there is nothing to catch.

      • by Anonymous Coward

        China is capitalist. Get your facts straight. It is very very capitalist. It just happens to be run by the new gen Communist Party, which allows capitalism.

      • Of course, you have to pick your carrier carefully or you will still raise suspicion.

        For example, it's obvious that any television show hosted by Bob Saget is nothing more than a carrier for stenographic communication between earth and our intergalactic overlords.

        Don't try to convince me that Full House and America's Funniest Home Videos survive on merit of ratings alone.

      • by Thaelon (250687)

        The best way to not get caught is to look like there is nothing to catch.

        No, the best way to not get caught is to convince those watching you belong.

    • Re: (Score:3, Interesting)

      by lysergic.acid (845423)

      "ordinary" people don't, and never really have. but there will always be people who need to transfer information undetected--spies, for instance.

      if you're an undercover law enforcement agent, you could communicate with your agency without blowing the risk of blowing your cover by using steganography; likewise for whistleblowers who need to get information out of an organization with tight security. steganography would also be useful during wartime when cryptography isn't an option, or isn't enough.

      i'm sure

      • "ordinary" people don't [need steganography], and never really have.

        You're on acid (sorry, couldn't resist).

        "Ordinary" people *do* have a need for encryption and even steganography. I don't particularly want the government, my employer, or anyone else for that matter to know the private details of my life. They don't need to know what medications I take, for what conditions, what my personal finances are, etc. Suppose I am out of town on a trip, and I need to use a credit card that I left at home. Should I have my wife e-mail the number, the expiration dat

        • um, read the post i was replying to. i never said normal people don't need cryptography. i was responding to the comment that there's no longer a need for steganography anymore just because encryption is commonplace.

          also, you gave no examples of when an ordinary person would need steganography instead of encryption.

          • 'Kay...how about this: having data encrypted implies that there is something about the data that the originator doesn't want others to see. Curiosity causes others to want to know what exactly is so secret. Or perhaps, a script-kiddie wants to crack the data, just to see if he can. Or, in a more Orwellian vein, the NSA decides to crack the encryption because 1) "if you are encrypting you obviously have something to hide", or 2) just for practice.

            By hiding the data in your vacation pictures w
    • by Vellmont (569020)


      Do we need to hide crypto anymore?

      Even the strongest crypto implementation and algorithm is still subject to Rubber Host Crypt-analysis, or even "court ordered cryptanalysis". In those cases stego would have some protection against these techniques.

    • Re: (Score:3, Informative)

      by DingerX (847589)
      Don't disrespect it. In fact, steganography has had many many uses over the years. Naming just one case, steganography is the ultima ratio of intellectual property protection. Gulliver's Travels, for example, was published pseudonymously and "signed" steganographically. Even better, it was signed at least two ways, one using a "Soft" method, the other a "Hard" one. Right on the first page, Gulliver states: "Soon after my return from Leyden, I was recommended by my good master, Mr. Bates, to be surgeon to th
      • by Whiteox (919863)

        When was that discovered?
        Strangely (although typically), I did a thesis on Gulliver's Travels pointing out the various attacks on Newton and his physics. This was an historical work.
        At the same time, I modified a subset of it and turned it in as an English Lit. paper. Neither disciplines saw eye-to-eye on the same content!
        I was a bit bemused at the time and realised that truth and objectivity doesn't exist as far as historians and English literature are concerned.
        In my research (mid 1970's), I had never co

        • by DingerX (847589)
          I've got no idea. As an undergraduate, I took a bunch of courses with a crazed philologist (long before I realized that all philologists are crazed, and that I must bury somewhere in the apparatus the note that I am an historian), and he'd spout out random "facts," most of which I found out later were false. But Swift worked pretty well, and I have no idea where he picked that one out. He followed it up with one that claimed that if you take the opening of Lazarillo de Tormes and play acrostic with the firs
    • The people, who really need cryptography, basically need the rest of us to use it even though we don't need it, so we will become the noise that keeps them from standing out.
  • by NotQuiteReal (608241) on Tuesday November 04, 2008 @10:39AM (#25626711) Journal
    hiding a message in such a way that only the sender and receiver realize it is there

    I ignore lots of ads served up by them. They might as well not be there, I can't name one.
  • by Ostracus (1354233) on Tuesday November 04, 2008 @10:39AM (#25626713) Journal

    "Steganography is the art of hiding a message in such a way that only the sender and receiver realize it is there. (By contrast, cryptography disguises the content of a message but makes no attempt to hide it.) "

    There's a secret message in this post. Can anyone find it?

  • by xmarkd400x (1120317) on Tuesday November 04, 2008 @10:50AM (#25626977)

    In the stego-channel, a transmission is successful if the decoder properly determines the sent message without anybody else detecting its presence (abstract).

    When my girlfriend is talking on the phone, I am almost never aware that a message is being sent. She is so effective, in fact, that often when I am the intended recipient I am not aware that a message is being sent!

  • by Anonymous Coward

    "for example, adding noise to channel can increase its steganographic capacity and in some cases, mounting two attacks on a channel instead of one can do the same)."

    Umm. Duh.

    Crypto and compressed data both tend to look like white noise. That makes them ideal stego candidates. When the data itself has a uniform distribution, it's really hard to to spot. It gets even harder if you apply a one time pad of random low-order bits to the stego medium and then modulate your signal in those bits. Thus, the actual ch

  • Studying a stego-channel in this way leads to some counter-intuitive results: for example, in certain circumstances, doubling the number of algorithms looking for hidden data can increase the capacity of the steganographic channel"

    That's not what the paper claims. It claims that when there are multiple detectors, adding noise to the channel between the two detectors can increase the available bandwidth. This isn't really all that counter-intuitive when you think about it.

    • And on page 8 of the arXiv PDF [arxiv.org], "Composite steganalyzers", it says explicitly that the capacity of the composite channel (using multiple steganalyzers) is less than that of channels using any one of the analyzers alone.

      KFC at the arXiv blog got it wrong and the /. eds passed it on.

      Maybe there's a hidden message in the mistake?

      Probably not.

  • Stenography FTW (Score:4, Interesting)

    by yttrstein (891553) on Tuesday November 04, 2008 @11:17AM (#25627581) Homepage
    I've always had a warm spot for stenography, and it's actually much handier for certain types of communications than others. For example, in the two nights preceeding the last Democratic National Convention that was held in Chicago (1996), a subversive media organization, armed with clunky digital cameras and a T-1 on the south side donated by the Teamsters photographed and filmed more than a hundred instances of police brutality, uploading them to the web with about a 30 minute delay.

    You had to actually drive downtown to where the T-1 terminated to upload things in those days, see.

    But how did we communicate our plans and schemes to actually be present at "hotspots" when the shit really went down? Stenography. It went like this:

    I have a number, that number is 356-32395510. I tell you that number. Then I take an image file and UUencode it. (for those who don't remember what that does, it's great for turning a binary file into a flat text file without losing any data). Then I take the message that I want to give you and drop it manually into the UUencoded file, like this:

    Every third character on every second line starting from line 910, (the third, fifth and sixth digits of the are decoys) counting whitespace. The numbers always changed and had to be memorized when received as they were never written down. Everything to the left of the dash tells you what digits to the right of the dash are decoys. Use the number to find the characters and you have the message. Pull them out and you can UUdecode your picture again and look at it. Leave them in and the file looks merely corrupt. Email the stenographed file to the recipient who's memorized your number and there you have it.

    The upside to this method is plausible deniability. If the fuzz finds a corrupt file called "FATLADYSEXHAHA.uue" on your computer, they have nothing. However, if they find a PGP file that you refuse to open for them, there can be issues.

    Of course it's possible to break that kind of thing, but the point of stenography is that the man does not know it's a message of any kind, let alone a radical one all about how awesome cuba is.
    • Re:Stenography FTW (Score:4, Informative)

      by zindorsky (710179) <zindorsky@gmail.com> on Tuesday November 04, 2008 @11:28AM (#25627821)

      I've always had a warm spot for stenography

      ...

      But how did we communicate our plans and schemes to actually be present at "hotspots" when the shit really went down? Stenography.

      ...

      Of course it's possible to break that kind of thing, but the point of stenography

      So you hid your messages with stenography? The action of process of writing in shorthand or taking dictation? This word you keep using ... I do not think it means what you think it means.

      • by yttrstein (891553)
        Wow, what a thoroughly embarrassing error that is. Thank goodness the rest of my post stands quite reasonably on it's own and contains no logical or factual errors, otherwise it may have been relevant to some sort of point to point out my consistent mistake.
        • by yttrstein (891553)
          I don't think I deserve that down-mod along with "zindorsky's" judgment here.

          Let me explain.

          This "zindorsky" person decided to pass no judgment or comment on the content of the post itself, but only stopped to correct my spelling and word usage, implying that not only was he already privy to the information contained in the post, but also that I'd misspelled the word in question--or more probably that I didn't know what the word was to begin with.

          So this next part is for you, "zindorsky":

          I have an agraphia
      • My mom used to hide notes from the rest of the family, in plain sight, using short hand.

        She was a secretary, back in the day. When you saw some scribbling on a note, you knew it was the chrismas shopping list or something, but who the hell knows what it said - even if you had a copy of Gregg's [wikipedia.org] you'd be hard pressed to figure it out, unless you really wanted to spoil the surprise.
    • Sorry try again (Score:3, Informative)

      by shadow_slicer (607649)

      That's not steganography. That's encryption, and a crappy one at that. If you take your PGP file (and remove any unnecessary header stuff), it will also look like a corrupt file, just like your UUencoded image. Steganography is hiding some data inside something else, like hiding a message in an image. For example, the police see an image of kittens, but you hid your child porn in the LSBs of the image, they can't see it.

      • by yttrstein (891553)
        Encryption is the following:

        "encryption is the process of transforming information (referred to as plaintext) using an algorithm (called cipher) to make it unreadable to anyone except those possessing special knowledge"

        What I'm talking about is the following:

        The art and science of writing hidden messages in such a way that no-one apart from the sender and intended recipient even realizes there is a hidden message.

        What I described is *precisely* correct under definition. Let me be more clear, using the exam
        • by Whiteox (919863)

          There are other forms of hidden text or more correctly, 'meanings'.
          One that comes to mind is the Pesher technique which is used to re-interpret holy texts.
          The other is termed 'Legominism' also gnostic, as described by Gurdjieff who showed that missing or incorrectly ordered information, compared to correctly orderd information can also pass on meaning. That using a 'mask'.
          For example as there are 7 days in the week - SMTWTF, and if the message reads SMTTWTFS then a message has passed on.
          Legominisms can be p

        • I just fail to see how having a slightly corrupt uuencoded file is the same as not having a file. In the case of an encrypted file, you also have a file that appears corrupt. And it is obvious to everyone that there is a message (the file), even if they can't decode it. I'm sorry I just fail to see how the scheme you proposed could be considered stenography.
  • by petes_PoV (912422) on Tuesday November 04, 2008 @11:19AM (#25627625)
    Well, I've read the published paper, and I still don't have a clue what the answer is. I suppose hoping for a cut and dried figure like "1%" was too optimistic, afterall.

    If there's going to be a practical use for this (and the conclusions don't say they've calculated "the answer", just that they've developed a framework, gaaah!) then my gut tells me that the answer is "not very much" - somehwere around the rounding-errors of the encoding mechanism.

    So, does anyone know how much data can be stuffed, undetectably, into a 700MB AVI file?

    • Anywhere between 0 and a bit less than 700MB of data, depending on desired quality of video. A one frame video stream with an unrecognized FOURCC tag as an alternate stream is valid AVI - the alternate stream is ignored by players, and can contain encrypted data. It is 'invisible' to non-uber users, and could concievably be an "experimental audio codec" for plausable deniability.

    • So, does anyone know how much data can be stuffed, undetectably, into a 700MB AVI file?

      700 MB, if you do it in the dark.

    • "So, does anyone know how much data can be stuffed, undetectably, into a 700MB AVI file?"

      No idea, but it is probably a lot less than you can stuff undetectably on a 700MB WAV file ;)

      You can hide as much data as there is noise on your file (granted it is compressed and cryptographed), so when you record that WAV file, be sure to do that in a noisy anvironment. By the way, I didn't RTFA, to see what those people really discovered (obviously, not what the sumary say they did), I'm here to see if it is worth i

    • by temcat (873475)

      Well, I've read the published paper, and I still don't have a clue what the answer is.

      That's steganography at work! The answer is hidden.

  • by Binge (780857) on Tuesday November 04, 2008 @11:39AM (#25628075) Homepage
    I always thought Steganography was the act of writing on large, plate-backed dinosaurs. Ya learn something new every day here!
  • Kaylee: Although I'm getting some weird chatter on the the official two-six-two. Sounds like they're talking about... ducks?
  • by PPH (736903) on Tuesday November 04, 2008 @12:44PM (#25629313)
    ... of Pamela Anderson. There appears to be quite a bit of excess capacity available.
  • by bokmann (323771) on Tuesday November 04, 2008 @01:17PM (#25629915) Homepage

    Calculating this with any accuracy would require knowledge of both the width of a Stegasaur (which can be approximated from their fossils), but also how fast they ran. Given other arguments about the unknowns of dinosaurs, the figures we can guesstimate for their speed are just to varied to calculate this capacity to any meaningful value.

  • Simple (Score:3, Funny)

    by TheSync (5291) on Tuesday November 04, 2008 @02:13PM (#25630911) Journal

    The The secure capacity C (W, g, A) of a stego-channel give W [noise], g [steganalyzer], and A [attack] is given by C (W, g, A) = sup I(X;Z) for X an element of S0.

    I is the spectral inf-mutual information rate for the pair of general sequences.

    Z is the stego channel after encoding, noise, and attack (before decoding).

    S0 is the secure input set, the set of encoded data that remains impossible to steganalyze after the addition of noise (but not necessarily attack).

    I think mathematicians like to make their papers overly complex.

  • by CustomDesigned (250089) on Tuesday November 04, 2008 @09:13PM (#25635951) Homepage Journal

    Sometimes people think there is a steganographic message, when there isn't. The Bible Codes [biblecodedigest.com] are an example. The idea is that God hid secret messages in the Bible which are revealed by equidistant letter spacing. Never mind that such "messages" can be found by ELS in any sufficient large work [anu.edu.au]. Practitioners never seem to find the messages until after they become relevant...

    • by mikael (484)

      Those were skip codes. You take a massive large block of text, then set your encoded message to be a particular starting offset from within this text, skip distance (or stride) between characters, and the length of the message.

      From these three values (starting offset skip distance, length) you could extract a message.

      I always wondered whether you could encode/extract an mp3 file from a suitably large ISO file (eg. Linux DVD ISO file) by defining a list of such messages.

Mr. Cole's Axiom: The sum of the intelligence on the planet is a constant; the population is growing.

Working...