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."

This has been done forever.

[packeteer]

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.

Re:This has been done forever.

[Valar]

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.

Re:This has been done forever.

[LinuxInDallas]

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.

Re:This has been done forever.

[uncoveror]

What do we need this for anyway? It has already been reported that digital photographs cannot be faked. [uncoveror.com]

porn

[Transient0]

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?

[heliocentric]

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?

[saforrest]

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.

These watermarks vs. Digimarc watermarks

[yerricde]

This is called digital watermarking.

But unlike Digimarc watermarks, this kind of watermark isn't designed to survive being sent through the analog hole.

Yes, it's steganography.

[wirelessbuzzers]

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.

Steganography isn't the point

[Cato the Elder]

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?

[nuntius]

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]

abstact here

[leuk_he]

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

Re:Encryption?

[leuk_he]

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)

Re:Encryption?

[jovlinger]

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.

Re:Why this is important

[WNight]

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.

Re:Encryption?

[heliocentric]

I don't think this quite gets the point across that you want it to, "I'm just a theta(n) person in a theta(log n) world." would work better;)

I'm not so sure you get the point I'm trying to make... Can you ever have an alg. that runs in less time than it takes to read in the entire input? I'm trying to make a statment about difficult demands placed by the world and what I think of my own abilities to keep going at the real physical limit, but it just doesn't match the expectations of the world.

I'm not saying I'm asymptotically similar to something - I'm just talking in the worst case that I'm bounded. I feel the world wants things done in an unrealistic time (in the worst case) and that I just can't seem to provide that...

Signed Hash

[notestein]

How is this better than a signed hash of the image?

Re:Signed Hash

[jonbrewer]

"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

[Xenographic]

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

[packeteer]

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

[Krach42]

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

[notestein]

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

[sharph]

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

[Henry V .009]

Re-sizing is still alteration. As for telling which portions have been changed--hash 50x50 pixel squares, or whatever you want.

Re:Signed Hash

[sinserve]

Or steganography?

Re:Signed Hash

[jsse]

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.

Re:Signed Hash

[Henry V .009]

Then digitally sign it with GnuPG.

Re:Signed Hash

[Henry V .009]

Yes it would. The steganography part comes when you stick the signed hash back into the original image (probably along with the entire original image to make it reversible). Which is kind of silly. But isn't that just what the front page of /. is there for?

mmmm

[standsolid]

mmmm... open-sourced-club encryption.... wait... not open-source.

I don't get it...

[RomikQ]

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

[stratjakt]

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.

Re:I don't get it...

[McCart42]

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.

Is it really encryption?

[verch]

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.

It DOES distort the image!!!

[wirelessbuzzers]

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

Don't let Bin Laden read this...

[TheGreenGoogler]

As I recall, the FBI had evidence [wired.com] that Bin Laden was using steganography [jjtc.com] to conceal messages in photos...

Something doesn't sound right

[plierhead]

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 ?

Re:Something doesn't sound right

[Henry V .009]

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"

[fireboy1919]

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.

Re:"Optimal"

[ebyrob]

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.

Re:Something doesn't sound right

[ebyrob]

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!

[wahay]

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".

once again all the early posters got it wrong

[intuition]

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?

Re:once again all the early posters got it wrong

[wirelessbuzzers]

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.

Re:once again all the early posters got it wrong

[cei]

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.

My bullshit detector is on yellow alert

[Crag]

"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.

Re:My bullshit detector is on yellow alert

[ngoy]

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

Re:My bullshit detector is on yellow alert

[ngoy]

I understand the need for detail, but we are talking changes of one bit in a scattered pattern. I have not researched it, but I think greyscale medical imaging is on the 10 bit level, so 1024 different shades of grey. If you change the first (or even second) bit, I doubt a doctor is going to point to that and make a diagnosis on a laser imaged x-ray.

And thanks to our wonderful health care industry, it probably is immaterial anyways since the doctors get paid NOT to refer you to specialists anyways...

ngoy

Re:My bullshit detector is on yellow alert

[ChristopherLord]

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. "

Re:My bullshit detector is on yellow alert

[Henry V .009]

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.

Re:My bullshit detector is on yellow alert

[wirelessbuzzers]

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.

My technique...

[dsb3]

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

[c.emmertfoster]

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"

Re:Camouflage

[Cheese Cracker]

Sweet... Now I can hide Adobe Photoshop in an image file. Talk about irony.

Re:Camouflage

[c.emmertfoster]

Ah, but the rub here is that the images don't look like random garbage...

This [yahoo.com] Yahoo! Briefcase contains JPEG images which look like the logo of the warez site responsible for uploading them. Within the images is a pirate copy of Paint Shop Pro. The only distingushing characteristic is that they are four megabytes apiece :)

Note that it's not limited to images, either. According to the website, one could conceal things within text files... (!?)

In other news...

[the_other_one]

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.

Re:In other news...

[MadFarmAnimalz]

That's ok.

I use lynx. :-)

Sounds great, sort of...

[wirelessbuzzers]

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

[DougJohnson]

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.

Obligatory DMCA Reference

[no soup for you]

Do not attempt to reverse engineer or theorize about this encryption. They say it's encrypted, that's enough for you.

No fake Brittany or Seven of Nine!

[SunPin]

Now we can confirm the genuine naked pictures from those photoshopped ones...

Pointless?

[interiot]

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?

Re:Pointless?

[Fourier]

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.

Careful what you wish for

[Anonymous Coward]

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.

Re:Careful what you wish for

[wirelessbuzzers]

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.

Court Evidence Verification? No...

[syphoon]

"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?

Hey, if it was hard to write ...

[HealYourChurchWebSit]

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?

[FireMage]

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!

[seanadams.com]

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!

May be I'm a little bit jumpy but...

[jsse]

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!

Information theory?

[captaineo]

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.

Re:You can't.

[captaineo]

I see. You could take advantage of redundancy in the source image. Thanks...

Amazing, nobody here understands the point

[goombah99]

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.

Re:Amazing, nobody here understands the point

[Requiem Aristos]

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.

Re:Amazing, nobody here understands the point

[goombah99]

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)

Some more information I googled

[sambo99]

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.

[KFury]

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.

Re:Misleading title.

[leuk_he]

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. "

2 Faults

[frovingslosh]

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.

manipulations

[telstar]

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

[KidSock]

it's only worth a 1000 words.

Zero Distortion HOWTO

[Effugas]

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

Re:Zero Distortion HOWTO

[leuk_he]

In other words:

-lossless compress it, since real life pictures are always compressable.
-Add Data, upto original size of file.
(-Add a hash/sign it)

Anyone else find it ironic...

[Grip3n]

That we're trying to prove an image hasn't been tampered with by tampering with the image?

Encrypt Images In Information Without Distortion

[Harald74]

For all those collectors of illegal pr0n...

How is this different from EXIF or DIG35?

[N8F8]

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?

And this is hard because ....?

[mr3038]

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.

It's being done the hard way

[oldstrat]

.
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'

Re:No loss of information?

[sashang]

I think this is different. They're modifying the data at the pixel level, not in some file specific field.

Re:No loss of information?

[stellar7]

I wonder just how much you would be able to store in an image. I would think there would only be a certain percentage of the total data that you could store per a certain image size. Anybody know any specifics?

Re:Holy Cow!! This Is Awesome!

[packeteer]

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.

Re:Holy Cow!! This Is Awesome!

[broken_bones]

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 [slashdot.org] to this thread was at 10:29, just three minutes after the article was posted. You sure must read fast...

Re:Holy Cow!! This Is Awesome!

[packeteer]

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.

Re:Holy Cow!! This Is Awesome!

[wirelessbuzzers]

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.

Re:Holy Cow!! This Is Awesome!

[Chris Burke]

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?

Re:Holy Cow!! This Is Awesome!

[packeteer]

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.

Steganography

[Chris Burke]

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.

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 .PNG, stick an encrpyted md5 sum at the back, and call it (S)ecurePNG.

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-?

Re:Steganography

[RockyJSquirel]

It should be REALLY easy to hide data in a JPEG without loss of quality or change in measurable statistics if you're encoding from the original uncompressed source.

When a compressor reduces an image to a JPEG there's a loss of information in the quantization.

Some coefficients will be almost exactly between two quantization levels, so either choice would be equally bad. In those cases you have the freedom of one bit without loss of quality.

Let's say you encode data by grouping coeficients into bundles of 20, and expect to get a single bit of information out of each bundle by xoring all of members together. Odds are that at least one of those coeficients had the freedom to change.

Easy.

No I didn't find the paper listed. I posted this idea on slashdot a long time ago.

Rocky J. Squirrel

Re:Steganography

[Chris Burke]

Except if you care about quality enough to worry about 1-bit errors, then you wouldn't have been using a lossy format in the first place.

JPEG would never cut it for forensics photos.

Not that this also isn't a good idea. I'm just saying it doesn't match what the article suggests. :)

Huh?

[Anonymous Coward]

WTF is this supposed to prove?

Re:New?

[the eric conspiracy]

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.