Slashdot Mirror
Encrypt Information In Images Without Distortion
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."
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.
unzip; strip; touch; finger; mount; fsck; more; yes; unmount; sleep
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!
lysergically yours
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?
Wheeeee
How is this better than a signed hash of the image?
www.bannination.com Two things float to the top he
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?
Join the elite! Post at score:2! Ghostwheel is online.
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.
As I recall, the FBI had evidence that Bin Laden was using steganography to conceal messages in photos...
They are refering to water marks. This is not about "encryption" or even "stenography". The problem is proving a document is original. Normally you put and ugly water mark on the image. With this techinque you can put the water mark in but you also put in data "securly encrypted of course" about how to get the water mark out.
Sheesh i feel dirty now that i have summed up the whole article because people post before they read it.
unzip; strip; touch; finger; mount; fsck; more; yes; unmount; sleep
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 ?
[x] auto-moderate all posts by this user as insightful
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".
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?
"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.
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.
Slashdot? Oh, I just read it for the articles.
Quoting packeteer:
Sheesh i feel dirty now that i have summed up the whole article because people post before they read it.
I find it amusing that you say this when your first post to this thread was at 10:29, just three minutes after the article was posted. You sure must read fast...
Never disturb your enemy while he is busy making a mistake.
How is this any different from Camouflage, 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"
We can neither love nor pity nor forgive. If you make a slip in handling us you die!
Actually i do read fast. But i have also read the article already. And i know a fair bit about the subject. And besides my first post to this article was joking around. I just felt i might as well throw it out there at the beggining. Then i waited to maybe share my knowledge but people like you jsut throw around uninformed comments.
unzip; strip; touch; finger; mount; fsck; more; yes; unmount; sleep
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.
134340: I am not a number. I am a free planet!
... 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.
I hereby place the above post in the public domain.
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.
Do not attempt to reverse engineer or theorize about this encryption. They say it's encrypted, that's enough for you.
If you blog it...
Now we can confirm the genuine naked pictures from those photoshopped ones...
Laws are for people with no friends.
Does anyone know of a good use for this?
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.
I hereby place the above post in the public domain.
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.
... 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.
I hereby place the above post in the public domain.
I've had that technique for years. It's called a checksum.
All a checksum does is provide a playground for anyone with a little Linear Algebra background.
Now if you are talking about message digests based on hash function, like SHA or HMAC you are on firmer ground.
"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?
Quoth the parent: They are refering to water marks. This is not about "encryption" or even "stenography". The problem is proving a document is original. Actually, it looks like steg to me. Because to prove a document is unaltered without altering it, you just sign it with your private key. This can't be any better: someone could remove the watermark (it's reversible), alter the message, and "authenticate" that, unless there is a digital signature embedded in the image, in which case why not just attach it to the file? Although it would appear that the original paper is not online, so we can't be sure.
I hereby place the above post in the public domain.
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.
"Laugh hard, it's a long way to the bank." --TMBG
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!
This is called digital watermarking.
But unlike Digimarc watermarks, this kind of watermark isn't designed to survive being sent through the analog hole.
Will I retire or break 10K?
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.
Mod me down and I will become more powerful than you can possibly imagine!
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.
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.
Some drink at the fountain of knowledge. Others just gargle.
This stuff is in the process of being patented
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.
- Sam
Well, you can blame the editor, but it's really the article's fault. What they're really talking about is lossless steganography, which is a neater trick. The idea is to hide data in a standard (eg. GIF) image, and be able to extract that data while at the same time preserving the entire image. For the applications they talk about (watermarking), the hidden information is encrpyted, which may be why that word showed up.
;)
.PNG, stick an encrpyted md5 sum at the back, and call it (S)ecurePNG.
I'm curious about their claims. Do they claim to be able to hide the data in an existing image format without image loss? For formats like GIF, it'd be tough, because compressed data (by design) lacks the redundant bits Information Theory demands before you can start cramming extra bits of data into the same space. They certainly wouldn't be able to guarantee that the image was without quality loss before removing and correcting for the watermark.
So I guess I'm not sure what they're claiming.
Though I think for the applications they are stating, actual hiding of the data isn't the point. You don't care if people know that there is some data hidden in the image, you only care that they can't read it or forge it. It'd be much easier then, because you could make a new file format. Shit, all you'd have to do is take a
Which isn't a bad idea, actually... You could do some of the things they talked about.
For digitizing contracts, both parties would put an md5 sum encrpyted with their private keys in the image of the contract. Anyone (e.g. the Court) can read the md5 sums and verify that a copy of the contract is legitimate.
For verifying forensics photos, the camera they used would have to encrypt all the photos it takes with a private key (the Courts, again?) not known to the police officers who do the work. I think this is unworkable.
The only problem with both of these ideas is that they are only worth as much as you can trust that the private keys have not been compromised. If you're going to be convicting people on the basis of signed police photos, you'd better be damn sure that the police couldn't have possibly discovered the private key hidden in the camera's hardware.
But like I said, this doesn't involve hiding data in a photograph. I'm just wondering what the -purpose- of the steganography was actually supposed to be. Why is it important that the information be -concealed-?
The enemies of Democracy are
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.
Kevin Fox
Although it would appear that the original paper is not online, so we can't be sure.
Yeah, but I think you're right anyway, as that is the only reasonable thing the article could be talking about. None of the applications require steg, but it's very clear that the invention involves altering the image itself in some way. So based on that, can you think of what you would possibly use this for?
The enemies of Democracy are
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.
I'm an American. I love this country and the freedoms that we used to have.
I've got a 1 pixel image. Can it detect when I rotate it 360 degrees and perform a mirror translation on it?
Telstar
it's only worth a 1000 words.
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
I see. You could take advantage of redundancy in the source image. Thanks...
Well the problem is you CANT remove the watermark. Its like a pgp key. The watermark can only be removed by the intended recipient. Of course there is always a way but it should be fairly secure if you have a inique ID on a piece of hardware then only that hardware can remove the watermark.
unzip; strip; touch; finger; mount; fsck; more; yes; unmount; sleep
That we're trying to prove an image hasn't been tampered with by tampering with the image?
To make a pun demonstrates the highest understanding of a language
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......
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.
For all those collectors of illegal pr0n...
A)bort, R)etry or S)elf-destruct?
Metadata standards such and DIG35 and EXIF 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?
"God fights on the side with the best artillery." - Napoleon, Marshal of France - speaking truth to power
[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.
_________________________
Spelling and grammar mistakes left as an exercise for the reader.
.
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'
Some copyright schemes rely on the idea of voluntary reporting of your copies of copyrighted material, with the idea that you've already paid, or that the fee only goes so high, but that by reporting which material you have, the fees go to the correct authors.
This type of watermarking is ideal for that. It doesn't distort the image at all. The lack of "security" isn't a problem because the system assumes that if you aren't paying more, you'll be happy to report the copyrighted works you possess because it'll go to supporting the authors whose work you like.