Visual Cryptography | Hacker News Reader

Visual Cryptography

datagenetics.com

274 pointsivoflipse40 comments

This visual cryptography method uses a four sub-pixel subdivision method that I haven't seen before, but almost precisely the same effect is achieved when visually demonstrating a Vernam cipher (a.k.a. one-time pad).

1. Create a one-time-pad, or key. This is a set of randomly chosen 1's and 0's. Now, make a bitmap out of this data set, with 1 denoting a white pixel and 0 denoting a black pixel. It will look like static.

2. Distribute a copy of the key to the person you are trying to communicate with via a secure channel. (This is the hard part, security wise).

3. create your message as a black and white (not greyscale) image. It should have the same dimensions as your key.

4. Pixel-wise XOR the key with the message. If the key was well randomized, the resulting cypher will also appear to be perfectly random static.

5. Send the cypher to the person who is holding the copy of the key.

6. When that person receives the cypher, if he XOR's the cypher with the key, out will pop the original message!

The only visual difference to this method vs that in the linked article is that the message won't start to show up when you're a pixel or two out of alignment because there is no four-pixel subdivision. You have to line things up spot-on.

The Vernam cipher was originally published in 1926, so it's defintely older than "Visual Cryptography". However, I don't know if the visual demonstrations of it (I've only seen them in lectures, not surprisingly, with transparent overheads!), predate visual cryptography. I've seen a couple of lecturers use this technique to demonstrate how a one-time-pad works and, crucially, why you can't reuse keys more than once.

Does anyone know if this Visual Cryptography offers anything useful that a one time pad doesn't? The linked page is very cool and all, and I wish one as well constructed existed for one-time-pads! (Possibly one does, but I was too lazy to spend more than a minute searching for it.)

One-time-pads are wonderful. XOR is wonderful too; it's reciprocity is incredibly useful for so many things.

Eyes, however, can't do XOR functions with pixels :)

If you have a computing device, sure XOR is the way to go.

To answer your question, Visual Cryptography allows your eyes to perform the vanilla-OR and decode without the use of any other tools.

You're right. This would work with transparencies, while a straight OTP would not. I was at a lecture where the speaker made it work with transparencies, but he was obviously using a trick...

And step 1 is the key (no pun intended) difference with what is described in the linked post. The scheme described in the post is basically a keyless secret splitting (steganography), not key based encryption. But adding an image with good random pixels provides the key.

The OR-operation of the eye is a really nifty method.

Visual cryptography is fun! I used the idea to make wedding invitations when I got married. We printed out black and white patterns on transparencies along with some other graphics, then when you overlapped the "his" and "hers" transparencies you got the secret message.

It took some fiddling to be effective. I originally wanted a high-resolution image but that made alignment really hard. It ended up being larger pixels at maybe 8 pixels per inch.

Could you send me that invitation? I might be needing that soon if you catch my drift. Email in profile!

Thanks! :)

I've played around with this idea in the past. Here is a demo with three images encrypted in two different images.

use the arrow keys to move the images around or drag them.

If you overlap them perfectly, you see one image. 5 pixels left of that is another image, and 5 pixels right of center is a third image. They were originally photos and end up very high contrast :-)

http://bettermagician.com/topsecret/

Here is a version with only two images though with a better grayscale. due to the method I was trying you can see some information leak through: http://bettermagician.com/topsecret/big.html

The bottom section about surveys is an established technique: http://en.wikipedia.org/wiki/Randomized_response

Reminds me a bit of differential privacy too ( http://en.wikipedia.org/wiki/Differential_privacy ). I wonder has anyone looked into connections between visual crypto, steganography, and differential privacy?

I have an idea for using visual cryptography to improve patient safety in healthcare centers. Although it isn't directly related to the type of cryptography mentioned here, I'm interested in sharing it to receive feedback from fellow HN users who know more about visual cryptography. (I'm a layman when it comes to the subject.)

Without further ado: My friend, a nurse, told me that serious medical complications can occur because of breakdowns in communication among patients, nurses and other healthcare professionals. As information changes hands, misspellings and misinterpretations of records can seriously harm patients.

For example, you might have heard the story of a girl in Ohio who overdosed in 2011 because a nurse accidentally prescribed her the wrong dose of medication. It was a simple clerical error; the nurse had been prescribing the same amount for years.

I'm interested in using visual encryption to help validate patient information, especially the types of information (names, contact info, treatment regimens) that remain relatively constant over time.

Imagine if there were an easily recognizable, thumbnail-sized image on patient medical records. The image would pose no security risk because no sensitive data could be deduced from it, but even the slightest change in a patient's record would make it appear entirely different.

I think this might be one extra useful layer of security that would help patients and healthcare professionals safely validate their information. But, as I said, I'm a layperson when it comes to cryptography.

I'm interested in learning more about this approach, as well as the subject in general, and welcome any feedback from people who know more about visual cryptography.

It's a reasonable idea that already has use in displaying cryptographic fingerprints. Typically when servers present a certificate, if the cert is untrusted, a fingerprint (a hash of the public key) is shown to the user. This is meant to caution the user: if all of a sudden they see a fingerprint that they don't recognize, it might be somebody malicious trying to capture your traffic!

Instead of presenting the fingerprint as a big hexadecimal string, some clients instead produce ASCII art and display that instead, on the theory that the human brain is better at memorizing that than a big string of digits. For example, OpenSSH: http://it.toolbox.com/blogs/unix-sysadmin/visual-ssh-fingerp...

I would argue this has even more use in a system that is trying to warn about changes, rather than about possible malicious attackers. After all, in the SSH example above, an attacker just needs to get a certificate that looks close enough to the real one that the user will accept it.

I think what you are actually looking for is hashing[1] mixed with some sort of generative art[2]. For example Identicons [3,4].

Meaning that you could use identicons so that when prescribing a medicine a picture would be displayed next to it which would be completely different for different types and amount of medicine.[5] You could likely go farther, but you would have to read up on hashing and see what information you can and can't use with it. I think the harder problem is getting the system to be used, not how viable it is.

[1]http://en.wikipedia.org/wiki/Hash_function

[2]http://en.wikipedia.org/wiki/Generative_art

[3]http://en.wikipedia.org/wiki/Identicon

[4]https://github.com/blog/1586-identicons

[5]http://i.stack.imgur.com/SfGpg.png

(reposting my comment from the dupe)

The exceptionally cool follow-on to this is David Chaum's work on using visual cryptography for voting --

http://www.constitution2.org/wiki/files/2004_chaum_secret_ba...

People have since built further on that work, but I seem to recall that Chaum's paper is what started a wave of work on end-to-end verifiable voting.

This reminds me a bit of a CAPTCHA experiment that I put together where the idea is that a human would need to position the cursor in a specific place to be able to read the underlying message. I think its a really cool idea [1].

A similar approach could use (a much lower-res) version of this encoding for fun!

[1] http://embed.plnkr.co/LGHrxf/preview

This takes me back to when I was a young boy, and I used to get these James Bond magazines. They used a slightly different technique, but basically there was an image that just looked like random noise like the images shown here, and you'd place a coloured plastic filter over it to reveal a hidden message. Very interesting stuff.

From what I understand, it's hard to known when brute-forced decryption is "done" (i.e., the decryption yielded plain text data that is the original data). As far as I know, machines look for patterns in the potentially decrypted data that look like common formats (or for data that correspond to real letters/words in a certain language). Does visual cryptography make decryption "done-ness" harder to detect?

A properly decrypted message should have sharply less entropy than any improperly decrypted one.

Thanks for that insight, I was missing the entropy lens.

The image is not very random because it only uses a few possible patterns per 2x2 pixel block. If anything, that should give an attacker more information about the plaintext, not less.

I don't think that is correct. The encoding transforms each pixel (1 bit) into one of 4 possible patterns, each of which having an equal chance of being chosen for a given on or off pixel.

Perhaps the information that would leak is the maximum amount of data that could be encoded in a human readable-format. Someone could then make guesses as to the content on that basis. I do not think, however, that the limited choices per 2x2 block leaks information.

In theory, any redundancy in the plaintext helps the attacker. I'll give a contrived example.

Say I encrypt a series of coin flips, tightly packed as bits "0" and "1". If you guess the wrong key (assuming certain encryption schemes), you'll decrypt something that looks very much like a series of random coin flips -- just not the ones I originally encrypted. So you can't "know" if you guessed the key correctly.

HOWEVER, if I encode the same series of coin flips as an UTF-16 string saying "HEADS TAILS HEADS HEADS ...", it's extremely unlikely that a wrong key will decrypt to a correct looking message. So if the decryption result looks good, you know that you've guessed the correct key.

But, if you use one-time pad correctly, then your string "HEADS TAILS HEADS HEADS" will be just as likely as any other string of the same length. "TAILS HEADS TAILS TAILS" would be just as likely, as would "MEETING AT MIDNIGHT. -E". This is because a one-time pad key has just as much entropy as the plaintext.

Yes, there were some unstated assumptions in my argument, like the key being smaller than the plaintext. (For example, a typical symmetric key is 32 bytes long, and a typical plaintext at least several kilobytes.)

This is a dupe of something submitted earlier this morning. Was the original deleted for some reason?

You can say D-H key exchange works the same way with colors as demonstration. But it's cool to see this demonstration. Moral of the story: don't trust your Google logo :) It might have a hidden secret!

Using Gimp http://silveiraneto.net/2013/09/18/one-time-pad-using-gimp/

I thought this was going to be about Russians hiding secret messages in magazines, like that movie where the guy hallucinated he was cracking codes.

That guy won a Noble prize.

You want this other article for that (mentioned at the bottom)

http://www.datagenetics.com/blog/march12012/index.html

The topic is fun (if not terribly useful), but the rest of the blog is full of brain-teasers. I'm really enjoying the read.

Can we use this to Bitcoin paperwallet somehow?

It can be used to create paper wallets for the ultra paranoid.

That would be a great CAPTCHA.

It really wouldn't. Take the average of the puzzle, if it's 75% grey in a wide distribution then move it a bit, repeat until there's some huge change in the histogram. Easier to solve than most I've seen.

Pixels are OR'd, so you'd want 75% grey, not 50% (assuming each of the component images is an even distribution of white and black pixels). Otherwise, yeah.

Good point, I've edited the parent to correct it.

Counting the average size of black-colored connected components would work as well.

Actually it is a terrible CAPTCHA; no normal human will understand why the hell is he supposed to drag those noisy rectangles, while machine will easily find hidden image by scanning and counting entropy.

Yes and no. I'm the inventor of a Google-owned patent (http://www.google.com/patents/US8397275) using N layers of partially transparent images, and JavaScript to generate the offsets between the layers.

The CAPTCHA can be hard to read. (Note that for one of the images in the patent, the lawyer used a Gaussian blur rather than ask me for another screen shot from the prototype.) It might also confuse the user, because they see white noise when the CAPTCHA is first loaded.

The plus side is that it's a simple way to bring JavaScript into the CAPTCHA and force an attacker to create a high fidelity emulation of a browser, hook into a browser, or else take periodic screenshots in hopes of getting the CAPTCHA in its readable state.

Basically, I used to work on JavaScript execution in Google's indexing system, and thought "man, this is a pain to get all of these corner cases just right... how could I force a CAPTCHA attacker to do this?"

Fun use of noise :)

Reply on news.ycombinator.com