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
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.
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!
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!
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...
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.
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.
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!
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!
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
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
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
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.
[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.