Forgot your password?
typodupeerror
Encryption Security

Encrypt Information In Images Without Distortion 236

Posted by CowboyNeal
from the practical-steganography dept.
Nomikos writes "C|Net reports: Researchers have created a new way to encrypt information in a digital image and extract it later without any distortion or loss of information. A team of scientists from Xerox and the University of Rochester said that the technique, called reversible data hiding, could be used in situations that require proof that an image has not been altered."
This discussion has been archived. No new comments can be posted.

Encrypt Information In Images Without Distortion

Comments Filter:
  • by packeteer (566398) <packeteer@subdim ... ion.com minus pi> on Wednesday October 23, 2002 @10:29PM (#4518846)
    People have been doing this for some time. You simply print out the data. Take a photo of it. Scanthe photo. Send the photo. No distortion of the image with the data on it.
    • by Valar (167606) on Wednesday October 23, 2002 @10:32PM (#4518864)
      This isn't really feasible if you are trying to extract the data losslessly. The original image file will not match with the extracted file. There is loss in the printing (ink smudge, low resolution printer), loss in the photography (ambient light, noise on the film, thumb in front of lens) and loss in the scanning process. As a result, even if the scanned image is in the same format as the original, there is still loss.
      • I'm assuming that the parent of your message was using a little humor in saying you can simply scan something and retrieve its contents perfectly.

        That being said, depending on the type of data you scan you may very well be able to retrieve it all. As a simple example, you can scan a page of plain text and get it all back via OCR with good reliability. I would guess that with a high enough quality scanner you could get pixel-level-accurate scans of a high quality printing. That equipment is probably out of most of our budgets though.
    • What do we need this for anyway? It has already been reported that digital photographs cannot be faked. [uncoveror.com]
  • porn (Score:5, Funny)

    by Transient0 (175617) on Wednesday October 23, 2002 @10:32PM (#4518861) Homepage
    So I'll finally be able to verify whether or not that's a REAL picture of Britney Spears getting it on with a dalmation?

    SWEET!
  • Encryption? (Score:5, Informative)

    by heliocentric (74613) on Wednesday October 23, 2002 @10:34PM (#4518870) Homepage Journal
    Isn't it more like steganography? I mean, ok, so we can encrypt the message you store using steg. but are we confusing the two?
    • Re:Encryption? (Score:4, Informative)

      by saforrest (184929) on Wednesday October 23, 2002 @10:47PM (#4518919) Homepage Journal
      Basically it is a form of steganography. The only thing unique is that the information isn't an arbitrary message, but just enough to label the image.

      This is called digital watermarking.
    • Although I don't really see the point. It's not really worth much as steg as far as I can see, and if the data you change are redundant anyway, you might as well compress them out unless you want to do steg. Silly.
      • The point isn't to hide the data you're encrypting in, it's to be able to recover the original image. With a naive steganography scheme, you lose information in the original image. This is bad, if for instance, the encrypted information is a time/date/id stamp and the image is a crime scene photo--you could obscure important evidence.
    • Re:Encryption? (Score:5, Informative)

      by nuntius (92696) on Thursday October 24, 2002 @12:54AM (#4519524)
      From reading the paper (college access to IEEE publications sure is nice), the researchers outline two forms of reversible data embedding.

      Type I simply embeds the data into the spectrum of the image and uses modulo addition as necessary to prevent overflow. Unfortunately, this causes "salt-and-pepper artifacts" because this sometimes affects the most significant bits in a pixel's representation.

      Type II uses the traditional method of overwriting the least significant bits or high-frequency coefficients in the image (depending on image encoding).

      What this paper does is describe a method that employs Type II encoding and saves the overwritten bits by compressing them and inserting into the embedded data stream. Unlike simple Type II encodings such as always using the lowest two bits, this paper varies the number of bits which are used in each byte. This value is determined according to their compressibility and other parameters in the image. By doing this, the paper obtains a more efficient tradeoff between storage and distortion.

      The journal article is "Reversible data hiding" in IEEE Internation Conference on Image Processing, 2002, volume 2, pages 157-160 http://ieeexplore.ieee.org/servlet/opac?punumber=8 052 [ieee.org]
      • I cannot read the ieee link (the abstract is for members only) but google found this abstact for me:

        Watermarking :

        We present a novel reversible (lossless) data hiding (embedding) technique, which enables the exact recovery of the original host signal upon extraction of the embedded information......

      • I cannot read the ieee link (the abstract is for members only) but google found this abstact for me:

        Watermarking [icip2002.com]:

        We present a novel reversible (lossless) data hiding (embedding) technique, which enables the exact recovery of the original host signal upon extraction of the embedded information......

        (oops, something went wrong with my previous post)

      • Oh... I get it, I think.

        So the camera is a trusted device. It embeds a secret digital key. When I take a picture proving the existence of little green men, the camera stores, in the watermark signal, a signed md5 sum of the reconstructed(*) image. (I'm assuming just one such signal, several signals tell you how the image has been altered, not just if)

        Someone now questions whether this ufo pic I have is real: all I have to do is calculate the md5sum of the image, get the public half of my camera's key (printed on the bottom?) and verify that this indeed matches the signed image key.

        Kinda neat.

        (*) However, I'm curious. The embedded signal needs to contain the bits it replaces AND some payload data. How can this be a lossless embedding? Did these guys go and invent a recursivly applicable lossless compressor? So I suspect it is not lossless, but merely a lot better than other schemes.
  • Signed Hash (Score:4, Insightful)

    by notestein (445412) on Wednesday October 23, 2002 @10:40PM (#4518887) Homepage Journal
    How is this better than a signed hash of the image?
    • Re:Signed Hash (Score:4, Informative)

      by jonbrewer (11894) on Wednesday October 23, 2002 @10:45PM (#4518913) Homepage
      "How is this better than a signed hash of the image?"

      A signed hash can be separated from an image, while this type of watermarking cannot.
      • Re:Signed Hash (Score:2, Interesting)

        by Xenographic (557057)
        A signed hash can be separated from an image, while this type of watermarking cannot.
        >>>>>

        There must be some way to separate it from the image, as the technique is also supposed to be *reversable*

        I'm not sure just what they're up to, though, the article isn't very detailed...
        • Re:Signed Hash (Score:5, Insightful)

          by packeteer (566398) <packeteer@subdim ... ion.com minus pi> on Wednesday October 23, 2002 @11:35PM (#4519183)
          Thats where the encryption comes in. The watermark can only be reversed on the correct machine. Think like pgp, only the person you want to can read the email you send. They plan to work this into hardware. They would probably give the hardware a unique key and have the picture creator encrypt so only that key can open it. This way if you say wany a secure presentation you can set it so only the one projector in the white house can read it without the watermark.
          • Re:Signed Hash (Score:2, Interesting)

            by Krach42 (227798)
            My interpretation of the article was different. They made it seem that they could sign an image, not encrypt the image. Thus, the image was viewable to all, but it's verifiability was secured through this technique. Being that any alteration done to the picture would cause the signature to fail. It would likely result in the picture being blotched in the area that was altered, as the information that was contained there for both the signature and the previous color value are ruined.

            Thus, all those pr0n sites that steal pictures from each other, and post them on their own site with nifty looking "pr0n.net" marks would be verifiably altered.
      • Re:Signed Hash (Score:2, Interesting)

        by notestein (445412)
        I'm not sure I believe that. If I wanted an image that is guaranteed to not have been tampered with... A missing signed hash would invalidate the image as much as a changed hash. Now to put the equivalent of a signed hashes data back into an image via an algorithm.... that seems like less security.
    • Re:Signed Hash (Score:2, Insightful)

      by sharph (171971)
      Of course I could be completely wrong...but...

      If you resize the image, you get a different hash, but with this, you still get the authentication. And then when you have portions of the image changed you can tell what portions are changed... From what I can tell this is just a special "image hashing" and not Steganography at all.

      Of course, I could be completely wrong.
    • Re:Signed Hash (Score:2, Redundant)

      by sinserve (455889)
      Or steganography?

    • The key is that the information embedded in an image can be extracted "without any distortion or loss of information".

      The extracted information could be digital signature which could faciliate higher level of authentication like PKI that hash function alone cannot offer. Hash function could be used to verify whether a piece of work has be altered, with high confidency; but it can't authenticate the author of this piece of work.
      • Then digitally sign it with GnuPG.
  • mmmm (Score:1, Funny)

    by standsolid (619377)
    mmmm... open-sourced-club encryption.... wait... not open-source.
  • I don't get it... (Score:5, Interesting)

    by RomikQ (575227) <romikq@mail.ru> on Wednesday October 23, 2002 @10:42PM (#4518897) Homepage
    The new technique builds on previous methods but modifies the lowest levels of pixel values using data-embedding algorithms. It allows authorized viewers to extract the embedded authentication message while also removing any distortions created by the embedded information

    So while the encrypted data is in the image, the picture is still distorted, it's only when you take the data out, then you get the original. What's the point of that??? I mean that was what it was like before, wasn't it?

    By the way, adding plain text to the end of a jpeg file doesn't alter the image in any way, no matter how much you add. So you could encrypt the text you want and add it at the end and there you go, lossless data encryption in images :). Do I get a Nobel prize now?

    • Re:I don't get it... (Score:2, Informative)

      by stratjakt (596332)
      Your "James Bond" PDA displays undistorted images, while filtering the secret content somewhere else.

      Or you could embed a ton of secret messages in a simple server-to-server mirroring operation, and still wind up with a 1:1 mirror - never tipping anyone off that anything but the visible content was transferred.

      That way when the bad guys find it they see no distortions, can find no trace that the image was ever altered, and just think you're looking at porn.

    • The goal of steganography is to be one step better than encryption--not only can enemies not read the data, they don't even know there IS data being sent (at least not the data they were looking for). In other words:
      Encryption: "These are not the droids you are looking for."
      Steganography: "What droids? Those aren't droids, those are pictures of Britney Spears." (Perhaps this is a bad analogy.)

      Thus, adding text to the end of an image, even encrypted, shows that you have something to hide. For dissidents in China, this means prison, until you reveal your passphrase--and then they'll probably kill you.
  • by verch (12834) on Wednesday October 23, 2002 @10:43PM (#4518901)
    Sounds like 'encrypt' isnt exactly the right word here. Maybe 'encode' would have been better. From the very tech light article it seems that this is a watermarking technique which somehow embeds the watermark with no distortion of the image whatsoever. Traditional watermarks distort the image, albeit usually not noticeable to the casual naked eye.
    • by wirelessbuzzers (552513) on Wednesday October 23, 2002 @11:10PM (#4519055)
      ... just reversably, so you can get the original back later. And it isn't watermarking! They use only the LSB, so it won't survive recompression, printing, whatever. You can't encode anything without the image without distorting it, except by permuting the color tables. But that is easily detected and can't store much data anyway.
  • by TheGreenGoogler (618700) on Wednesday October 23, 2002 @10:43PM (#4518906) Journal
    As I recall, the FBI had evidence [wired.com] that Bin Laden was using steganography [jjtc.com] to conceal messages in photos...
  • by plierhead (570797) on Wednesday October 23, 2002 @10:47PM (#4518917) Journal
    The article seems utterly light on some key information (about which file formats etc), but simple information theory suggests that this will only work on less-than-optimal image formats.

    Any optimal image format will result in a file only just big enough to store the image and no bigger - and therefore it will not be able to store any additional data without reducing the image quality in some way.

    Without any further information available, could it be they are just talking about taking advantage of flaws in some given format such as jpeg ?

    • Here's a message that you could send to your girlfriend. Take a picture of yourself standing on a steal I-beam with your hand on your heart, with your university sweater emblazoned with U of whatever. Put that in any file format you want.

      But I responded to your comment for another reason. Nobody has ever written an optimal image format. Besides which, optimal for what? Plain-old human vision? You can remove information from an image in such a way that a human couldn't tell the difference (what most optimizing does). But computer processing can tell the difference in a nano-second. Probably, human-optimized images wouldn't even fool all primates.
    • "Optimal" (Score:5, Interesting)

      by fireboy1919 (257783) <[rustyp] [at] [freeshell.org]> on Wednesday October 23, 2002 @11:39PM (#4519205) Homepage Journal
      Have you studied any image compression theory? Have you heard of the famed graduate student method for fractal compression?
      Here it is
      1) Lock a graduate student in a room with an image and a huge collection of mathematical knowledge about fractals
      2) Tell him/her to compress the image by finding and modeling fractal patterns
      3) Wait four days...
      VOILA! 10000x compression is not unheard of with 1% or less degredation.

      Ever image format that we use today is sub-optimal. We don't even have a mathematical formalism to perfectly identify the entropy (i.e. information) encoded within an image (though we can make rough estimates) to determine the maximum compression. Also, consider than even given the techniques we have today, jpeg isn't the best thing out there, though it is the standard. jpeg2000 is better, and there are some even more highly sophisticated and accurate wavelet based approaches. If we can ever get the kind of computing power available to the supercomputers of today we can do even better by modeling our images using more complex basis functions than sinusiods and wavelets.

      Just one final note to sum up: finding optimal compression is definitely an NP-hard problem. Who knows what kind of stuff can be thrown in there without affecting much.
      • VOILA! 10000x compression is not unheard of with 1% or less degredation.

        Don't forget the graduate student will forget to include much of the other "storage" used for his copy of the image, causing the real world results to be multiplied by mu.
    • Actually... it sounded pretty simple:

      Current data-embedding techniques insert additional watermarking information, which inevitably distorts an image. While the distortion is small, it is usually irreversible. The new technique builds on previous methods but modifies the lowest levels of pixel values using data-embedding algorithms. It allows authorized viewers to extract the embedded authentication message while also removing any distortions created by the embedded information, the researchers said.

      They came up with the idea of using a digital watermark in an image, but having the "reader" of the image remove the watermark before it is viewed. Of course, they also claim only "authorized" viewers can remove the watermark... "big woop" and "ya right" all at the same time.

      Definitely patent-worthy in this climate. (move over single click shopping carts!)
  • Wow! Stupid Idea! (Score:2, Insightful)

    by wahay (12517)
    Ok. so we have a picture, which we then sign with a certificate of some sort. So far, so good. You can verify the picture.

    But what do we do next? We corrupt our picture with the signature, tossing it's bits into the picture as noise, and degrading the picure for all the people who open it. Except for the chosen few who have the (proprietary? patented? expensive?) program which chan detect the signiture, read it, and (WOO HOO!) XOR it out of the picture.

    This is not an exciting improvement over "gpg -s".
  • by intuition (74209) on Wednesday October 23, 2002 @10:51PM (#4518939) Homepage
    This is steganography with the original image hidden in the steganography as well. Hence the term, "reversible data hiding." That way, not only does the current image hold the data you are sending, but you get a copy of the original image (before steganography) as well.

    The fact that every poster so far hasn't seen this fact, is a disturbing reminder of what the average poster on slashdot has become.

    does anyone have any suggestions as to where to go next?

    • Well, I'm actually not so sure. It appears to be steg, should be usable as steg, and is pretty much useless as anything but steg, but it is also pretty much useless as steg, too. Reversibility is not an issue with steg: if whomever you're hiding from can see the data in transit, you a) shouldn't xor the message out because they just compare it with the sent message, and b) shouldn't have used an image that exists elsewhere for you to prove it's identical to. If you don't think they will do something like this, why the heck are you stegging at all? Rather, detectability seems to be the hard thing, and not going too well now (a paper [binghamton.edu] broke some of the last remaining good steg algos in Sept this year).

      Note that the article talks about authentication and watermarking. And the paper was presented under the "Watermarking" [icip2002.com] section in the IEEE conference. Too bad we can't ge the actual text, although from the detail-light article, it looks pretty much useless anyway.

      Ho hum.
    • by cei (107343) on Thursday October 24, 2002 @02:07AM (#4519770) Homepage Journal
      Nowhere in the source article does it say the encoded values are of the original image. It specifically refers to an "embedded authentication message."

      While your message has been modded to +5, it is, in fact, wrong.
  • by Crag (18776) on Wednesday October 23, 2002 @10:53PM (#4518951)
    "For instance, a digital camera that carries the new algorithms could be used to gather forensic evidence for use later in a courtroom. Any subsequent manipulations of the pictures could be detected, and the area where they occurred could be pinpointed."

    Whatever the camera is doing at the scene of the crime could be faked in a lab. Even if each camera has its own PGP/GPG key, the picture is only as reliable as the security of the camera and the key.

    What they should do is have the crime scene photographer and his superior digitally sign the images at the crime scene. This would remove the image format from the equation and make the data and the image as secure as the keys of the people involved.
    • In addition to the comments above, Epson (who hasn't put out a new digital camera in quite awhile) has had something called IAS (Image Authentication System). Per their web site:
      Image authentication is provided from the point of capture and thereafter
      EPSON IAS-protected images remain standard JPEG images, viewable with all software programs that read JPEG images
      Image manipulation can be detected down to the level of a single bit
      Verification of image integrity is fast and easy.
      IAS images suffer no visible loss of imaqe quality
      Compatible with the EPSON PhotoPC 700, 750Z, 800, 850Z, 3000Z, and 3100Z digital cameras
      Works with Windows 95, 98, 2000, Me, XP, and Windows NT 4.0 (with Service Pack 3 or higher)

      Not a lot of information, but theirs has been out for a LONG time. It has "non-visible" to the human eye detection, so it should have sufficed for any forensic photographer that could use a 3MP image (which I don't think is sufficient for decent crime scene photography, but I am not a CSI).

      I personally do not see where a "lossless" type of authentication is useful, even in medical imaging, is one shade off going to make a difference?

      ngoy
    • by ChristopherLord (610995) on Wednesday October 23, 2002 @11:09PM (#4519045) Homepage
      Canon does provide support for a "Data Verification Kit" on its latest 1Ds camera. No word on how secure it is, etc.

      from here [vividlight.com]:
      "Finally with a nod toward law enforcement the EOS-1Ds is the first digital camera that offers the ability to verify that images are unaltered originals using the Data Verification Kit DVK-E1, consisting of a dedicated IC card and card reader, together with software for Windows 2000/XP. This package is available to verify that EOS-1Ds image files are absolutely unaltered. "

      • The most secure this could possibly be would be if the camera generated a signed hash with every image using a unique private key. This private key would have to be stored someone. Inside an IC, in other words. That would be hard to break. You would have to a.) take apart the IC and get the key (if it's well designed). Or b.) fool the camera into thinking that it is taking a picture, when you have actually bypassed the CCD and are feeding it information from your home computer. b.) is probably a lot easier.
        • Or b.) fool the camera into thinking that it is taking a picture, when you have actually bypassed the CCD and are feeding it information from your home computer. b.) is probably a lot easier.

          Right. Except what the sig basically says was "this picture was taken with camera ID [blah]." It only means something if you know camera ID blah is the one that took the picture originally, trust its owner not to change things or leave his camera around, trust Canon not to escrow the keys, etc etc etc.
  • Hmmm ... how to embed/encode/encrypt the image within itself? ... I just XOR the image with itself. I also gain a few extra notches of JPEG compression that way.

  • Camouflage (Score:3, Interesting)

    by c.emmertfoster (577356) on Wednesday October 23, 2002 @10:58PM (#4518987) Homepage
    How is this any different from Camouflage [freeserve.co.uk], which is used by some "Warez" sites to hide files within images?

    I've seen this used to keep zip files on free-webservers which do not allow them.

    Quote from their website: "you could create a picture file that looks and behaves exactly like any other picture file but contains hidden encrypted files"
    • Sweet... Now I can hide Adobe Photoshop in an image file. Talk about irony.
  • by the_other_one (178565) on Wednesday October 23, 2002 @11:00PM (#4518995) Homepage

    The RIAA and MPAA have sponsored new legislation to make images illegal on the internet in the United States. Images have been known to carry illegal circumvention devices such as DECSS. Thus images in themselves are also potential circumvention devices under the DMCA.

  • ... but the real measure of steganography is detectability. It is very difficult to make steganography that cannot be detected statistically. Even Outguess is broken now. And I doubt that this method will be "secure," especially if whoever is spying on you watches the image in transit. Then if you subtract the message out you are SCREWED, because they xor and find it, or at least an encrypted version. In any case, they can prove the message is there. However, if they don't have access to your computer until afterward, just erase the images and you're fine, or JPEG them to remove the steg, or whatever. In fact, if nobody is watching your communications, why the heck would you use steg in the first place?? Looks like a proof of principle, not a real steg scheme.
  • Covert Channels (Score:3, Informative)

    by DougJohnson (595893) on Wednesday October 23, 2002 @11:00PM (#4519001)
    This really isn't that new. There's an example that's a picture of a couple of Zebra's, where they changed from some colour bit depth to a somewhat weaker bit depth, then the bits they saved were used to transmit ascii. Essentially a 32 bit pic was switched to 24 bits, leaving tons of room to include 5 of Shakespeares plays.
  • by no soup for you (607826) <.moc.liamg. .ta. .ttomaglow.essej.> on Wednesday October 23, 2002 @11:02PM (#4519004) Homepage
    Do not attempt to reverse engineer or theorize about this encryption. They say it's encrypted, that's enough for you.
  • Now we can confirm the genuine naked pictures from those photoshopped ones...
  • Pointless? (Score:2, Insightful)

    by interiot (50685)
    This seems pointless to me. The image that the common person sees isn't undistorted. To reverse the distortion in the image, you have to run the special program that extracts the hidden data and the original image data as well. If they're planning on everyone having this program that undistorts the image, why don't they just create a new format that's simply {raw image} + {extra data}, and you can run a program that spits out two files from that. If they're planning on having limited usage of the undistorting program to specific people, why don't the authors of the image send two separate files specifically to the intended audience?

    Does anyone know of a good use for this?

    • Here's an application as I see it:

      1) Photographer's camera embeds watermark into the image.

      2) Photographs can be freely distributed to anyone. The watermark distortion is generally small, so the casual user would not notice it.

      3) Anyone who is "authorized" (presumably has been given a key of some sort) is able to extract the watermark and view the original image. If the image has been manipulated (resized, airbrushed, etc.), the watermark will be corrupted and the authorized user will become aware of the alteration.

      In the article's example, the camera belongs to a crime scene investigator, and the authorized user is someone assocated with the court system.

      I'm not really sure why CNet picked up on this paper. I don't think it's particularly groundbreaking, and it's certainly not the only watermarking paper that was discussed at ICIP 2002. Wake me up when someone figures out how to watermark an image in a way that is robust to a wide variety of attacks (resizing, denoising/compression, pixel shifting, etc.), and is still invisible to the eye.
  • by Anonymous Coward on Wednesday October 23, 2002 @11:07PM (#4519038)
    While this approach has many potentially socially useful applications (e.g., getting data out of censorship regimes without getting caught), it also has a more sinister application.

    If you can "watermark" (not sure if that is technically the right term for what these folks are proposing) something in such a way that it is undetectable to the viewer, then that implies that you can attach a unique ID to any given file -- which is exactly what SDMI attempted to do (and failed, thanks to Prof. Felten's work at Princeton).

    But didn't Felten's paper essentially demonstrate that this sort of perfect information hiding was essentially impossible theoretically? If so, then the Xerox/Rochester guys are wrong. If not, then Felten's paper is wrong and it is possible to insert permanent SDMI-style watermarks in files. I sure hope it's the former and not the latter.

    Perhaps this new approach only has to do with psychovisual tricks and not psychoacoustic stuff -- in which case I suppose they could both be right. Anyone more knowledgeable about this care to comment?

    -Garth M.

    • If you can "watermark" (not sure if that is technically the right term for what these folks are proposing) something in such a way that it is undetectable to the viewer... Of course you can't. If it isn't visible, you can make an image with no watermark at all that looks the same, ie remove it. And this is reversible. So you can remove it by definition.
  • "For instance, a digital camera that carries the new algorithms could be used to gather forensic evidence for use later in a courtroom. Any subsequent manipulations of the pictures could be detected, and the area where they occurred could be pinpointed." So if I want to manipulate court evidence, what's stopping me from taking a *screenshot* of the image on screen, manipulating that image, and then re-encoding the hidden data so it appears no editing has taken place?
  • What ever happened to the coder's creed [cleversoul.com] that "If it was hard to write, it should be hard to understand and even harder to modify."?

    Honestly, I'm sure "clean encryption" is a good idea, but the phrase just has the oxymoron quality as "software reliability."

  • Detectable? (Score:2, Interesting)

    by FireMage (110207)
    My main quetion would be if there is any way to discern between a image holding encrypted data and an unmodified "visual only" image file.
  • This is great! (Score:5, Insightful)

    by seanadams.com (463190) on Wednesday October 23, 2002 @11:22PM (#4519117) Homepage
    Researchers have created a new way to encrypt information in a digital image and extract it later without any distortion or loss of information.

    So, if I can add some information to an image without any loss of information in the original, then I don't see any reason why I couldn't use this technique repeatedly, ad inifinitum, on the resulting image. Therefore, they have created a way to turn any one of my pr0n jpegs into an unlimited storage device.

    This really changes everything we thought we knew about computer science and information theory. What an incredible discovery!
  • what if terrorists embed secrete messages in p0rns with this technique? In view of the fact that 90% of the images in the Internet are p0rns, it's extremely difficult to check them all out.

    I know steganography for terrorism is no new news, but used that on p0rns is intolerable!
  • I may be mistaken but I think there is an information theory problem here. How can you add X bits of new information to a Y-bit image without loss (or enlarging the image)?

    Obviously a human viewer isn't going to notice if you just tweak the least significant bits of each pixel, but the article seems to claim that the technique is completely lossless.

    Some people have said "why not just use a separate digital signature?" I think the advantage of this technique is that you could save the image in any lossless format (e.g. BMP or TIFF) and still retain the watermark.
  • by goombah99 (560566) on Wednesday October 23, 2002 @11:53PM (#4519259)
    It's amazing no one is seeing why this is useful.

    Lots of people have suggested digitally signing the image. you that would work. But is it simpler? no. now I have to cart around two images, one people can look at in a computer browser and one "signed one" for evidence. I have to make sure I keep one associated with the other at all times. Yes of course I could decode the signed image when I wanted to view it but that's not a general purpose solution. If I make it act and smell like a jpeg or gif then I can easilty treat it as a single file that all existing image viewers can view. Only when I really want the perfect images and the signature do I have to use my special program.

    In fairness I will note that any image format, e.g. jpeg, that has the capabilit to associated additional infomation with an image, also would make a sutiable means of taking care of this. Though possibly not in a robust manner since some programs tinker with the text info in jpegs.

    Now as for whether the camera should do the embedding or embedding should be done afterwards, it makes more sense to let the camera do the embedding if it can. A simple Jpeg pops out and were done.

    Now about information theory not allowing this. that's piffle. proof by construction. First assume that all uncompressed real world images are compressible. compress it how you wish, lossy or losslessly. there is now room informationwise to squeeze in a small watermark.

    • Wrong!

      You don't have to carry around two images when you digitally sign one. You just need the image and it's signature (~160 chars or so), and can make both as public as you want.
      • What do you mean "wrong!"? you just agreed with my point that you have to cart around two files and somehow keep them associated with each other. That's what I was saying. and it's an unnesseccary pain in the ass. Sure you might have a way of keeing them ogranized, but now say you want to send the image to a defense attourney, or to another jourisdiction. Now they have to have some way of keeping them organized, and mybe their image storage software is different. (maybe they use iPhoto or Adobe Photoshops gallery program)
  • by sambo99 (224628) on Wednesday October 23, 2002 @11:56PM (#4519271) Homepage
    This stuff is in the process of being patented [eurekalert.org]

    The abstract of the paper (Reversible Data Hiding) is: "We present a novel reversible (lossless) data hiding (embedding) technique, which enables the exact recovery of the original host signal upon extraction of the embedded information. A generalization of the well-known LSB (least significant bit) modification is proposed as the data embedding method, which introduces additional operating points on the capacity-distortion curve. Lossless recovery of the original is achieved by compressing portions of the signal that are susceptible to embedding distortion, and transmitting these compressed descriptions as a part of the embedded payload. A prediction-based conditional entropy coder which utilizes static portions of the host as side-information improves the compression efficiency, and thus the lossless data embedding capacity"

    In case anyone is interested.
  • Misleading title. (Score:4, Insightful)

    by KFury (19522) on Thursday October 24, 2002 @12:11AM (#4519326) Homepage
    The title "Encrypt information in images without distortion" is really misleading. It suggests (err, states) that the sego process doesn't change the image. It certainly does. The only interesting bit is that it's reversable.

    So while it's not lossy in the final analysis, and the original version can be reclaimed, it does actually distort the image, while the hidden message is contained within.
    • With our new data embedding algorithm, authorized recipients not only can extract the embedded message but also can recover the original image intact, identical bit for bit to the image before the data was added," he said. "The technique offers a significantly higher capacity for embedding data and/or a lower-distortion than any of the alternatives."

      So i read this as "it can be lossy if you want it to. "

  • Poor story post for at least 2 reasons:

    It claims adding information to an image without distortion, but in reality the story actually tells of distorting the image in a way that, if needed, could later be reversed and removed. But the distortion is there none the less until it is removed, which removes the "signature".

    While it claims that any editing of the image would be detectable (because it modifies the encoded watermark), a reversable system solves this problem nicely: Reverse the process and take out the watermark. Edit the image any way you want (change Britney's dalmation to a poodle, for example). Then apply the watermark to the new image. I saw no proof or even claim that, if the watermake is reversable (which is the whole point of having the technology) then it wouldn't be easy to mark false images with the same watermark.

  • by telstar (236404) on Thursday October 24, 2002 @01:17AM (#4519615)
    I've got a 1 pixel image. Can it detect when I rotate it 360 degrees and perform a mirror translation on it?

    Telstar
  • But (Score:3, Funny)

    by KidSock (150684) on Thursday October 24, 2002 @01:29AM (#4519651)
    it's only worth a 1000 words.
  • by Effugas (2378) on Thursday October 24, 2002 @01:30AM (#4519656) Homepage
    Yes, I originally thought it was impossible.

    Then I sat down, and realized what's going probably on here (the CNet article didn't specify, and I didn't think to track down the original work. Foo on me. So I'm pulling this out of my proverbial ass.)

    Perfectly random images are indeed impossible to add data to without creating some form of irreversable distortion. Suppose you had a "remove transformation" mask embedded in the included transform. This mask itself would take information, which would then need to be added to the transform, which would increase the size of the transform, thus necessitating a bigger mask, ad nauseum. So you could never embed the reversal instructions.

    However, photographs are not perfectly random. Along the light wavelengths that nature selected for humans to sense, significant patterns exist -- edges, gradients, shapes, and so on. Though precise intensities eventually hit perfect randomness at absolute sensitivity, digital photographs (even without JPEG) quantize imagery into 8 bits per channel -- 24 bits total. So those patterns we see actually create significant regions of reduced entropy -- less information in the image than there is otherwise room for.

    And that's the key -- because once there's extra capacity, we can embed both some message and the means to remove that message in the extra space. Then it's just a matter of using one of a thousand ways to share the secret across all the low entropy regions of the image, and you're done.

    No, it doesn't violate information theory. Yes, it's mildly cool. No, it's nothing like a public key steganographic system -- there's nothing inherent about the system that prevents unauthorized removal, or even unauthorized addition of the watermark. But it's a useful adjunct -- concievably, it'd be at the heart of a watermarking system that fingerprinted audio and video in low-entropy segments, then removed the fingerprint before it hit the d/a converter.

    I'm pretty sure the strategy extends to floating point representations as well, though there's likely much less compressability due to noisy capture circuitry and higher raw entropy in the signal.

    Yours Truly,

    Dan Kaminsky
    DoxPara Research
    http://www.doxpara.com
  • by Grip3n (470031) on Thursday October 24, 2002 @01:54AM (#4519732) Homepage
    That we're trying to prove an image hasn't been tampered with by tampering with the image?
  • For all those collectors of illegal pr0n...

  • Metadata standards such and DIG35 [i3a.org] and EXIF [exif.org] are already in place for many image formats. How is this better or different? Microsoft already adds proprietary field to the metadata, how hard would it be to add your own metadata fields for encrypted data?
  • by mr3038 (121693) on Thursday October 24, 2002 @01:20PM (#4523429)
    If this works with lossless image formats, here's a simple way to achieve the same. I haven't read the paper so this could be practically same they're doing. For simplicity I describe a way to embed 8 bits of data in every pixel in a 24bit image.

    1. Extract some LSBs from every pixel from all RGB components (3 from R, 2 from G, 3 from B) and generate a stream from those bits.
    2. Append your secret message in the stream generated in the previous step.
    3. Compress the stream with any algorithm (e.g. bzip2) and make sure you get size in bytes less than or equal to number of pixels in the original image[1]. Pad with zeros if size of compressed stream is less than number of pixels in the image.
    4. Combine the stream with the image inserting bits from the stream to positions where we extracted bits in the first step and save the image any lossless way to want. The image quality will be reduced roughly to the same quality as 16 bit version would be but the original image can be restored from the compressed substream. During decompression, first there'll equally many bytes of image data as there're pixels in the original image and all the remaining data is the embedded message.

    [1] This is possible because all natural images have very little information in the LSBs of every pixel and those should compress well. If the image is truly random down to LSB there's no way any algorithm can embed extra information in those pixels.

    This will be probably patented. At least this is a bit more complicated than sideways swinging.

  • .
    No information needs to be added to an image at all.

    The easy way is to create an algorithm that finds information in a random image that matches your message.
    Transmit the key to that data by some secure means, send the image in the open, or even just a pointer to it.

    Without the key the data cannot be found, and the original image was never changed.

    Think about the Library job of Robert Redfords character in the 1975 movie 'Three Days of the Condor'

The economy depends about as much on economists as the weather does on weather forecasters. -- Jean-Paul Kauffmann

Working...