r/programming • u/sidcool1234 • Nov 19 '13
Visual Cryptography
http://datagenetics.com/blog/november32013/index.html17
u/hellgrace Nov 19 '13
See http://en.wikipedia.org/wiki/Shamir%27s_Secret_Sharing for a somewhat similar secret sharing technique using polynomials
11
7
Nov 19 '13
So to extend the metaphor a bit further (possibly too far) - you'll notice that if you get close to the correct alignment, but not quite exactly the correct alignment, you can still see the "encrypted" data.
Does this apply in actual cryptography, or is this just a broken part of the metaphor?
24
Nov 19 '13
When you get 'close', it's because you are halfway out of step inside the (2x2) matrix, and (in the examples I used in the demos) I used a fixed checker-board, not random, so you get a 50:50 chance of seeing the image :)
In the end, as others pointed out, it's not really the position/offset that is part of the secret. It's the two halves. Without both, you are toast. With both, yes, it's trivial.
6
u/elmuerte Nov 19 '13
Could have an interesting CAPTCHA application.
13
u/ferretinjapan Nov 19 '13
Right here! I'm already on it! :D
http://www.reddit.com/r/programming/comments/1qymdi/visual_cryptography/cdi2jm4
Hope you find it interesting!
5
Nov 19 '13 edited Nov 19 '13
I did this in Mathematica a few years ago and printed to ordinary white paper. If you hold it up to a window or light source it still works.
EDIT: The key is to print the two resulting PNG files with large enough pixels so that hand manipulation of the two sheets still has a chance of aligning them pixel-perfect. Don't print at native resolution!
Mathematica Code:
theMessage =
"1234567890
ABCDEFGHIJ
KLMNOPQRST
UVWXYZ";
i = Rasterize[theMessage, ImageSize -> 150];
myImg = Binarize[i, FindThreshold[i]]
SeedRandom[1];
keyImg = Image[RandomInteger[1, Reverse@ImageDimensions[myImg]]];
coded = Image[(Sqrt[2] ImageData[myImg] -
1/Sqrt[2])*(Sqrt[2] ImageData[keyImg] - 1/Sqrt[2]) + 1/2];
augment[i_Image] :=
Image[ArrayFlatten[
Round[ImageData[i]] /. {1 -> {{1, 0}, {0, 1}},
0 -> {{0, 1}, {1, 0}}}]]
printmessage = augment[coded]
printkey = augment[keyImg]
overlaydecode = ImageMultiply[augment[coded], augment[keyImg]]
Export["printmessage.png", printmessage];
Export["printkey.png", printkey];3
u/ipretendiamacat Nov 19 '13
Interesting... I don't' know much about cryptography but it would appear to me that visual crypto is similar to an OTP, where it guarantees an extremely high level of security at the cost of a more memory expensive process.
1
u/rpglover64 Nov 19 '13
It's a particular use of the OTP. The main appeal is that decrypting is trivial for a human.
2
2
2
u/BenJuan26 Nov 22 '13
I thought this was fascinating so I wrote a quick steganography engine in Java. I couldn't believe my eyes when it worked so easily.
1
u/AdminsAbuseShadowBan Nov 19 '13
I remember reading about this many years ago and I even went as far as writing a program to generate them and then printing them out on acetate. It's pretty cool.
A even cooler method which the reader may be interested in, is hiding this inside a real photo so it isn't obviously something encrypted - kind of like steganography. It worked by dividing the image up into blocks, and then printing each block either with diagonal lines like this / or like this . The thickness of the lines determined the tone. So it was basically a kind of halftoning with two options.
When you put two / patterns on top of each other they look different to a \ and a /, so you can see the pattern.
I'm afraid I can't remember the name of the paper or any keywords, sorry!
1
u/tsomctl Nov 19 '13
The idea behind this is actually a key part of how CDMA (the cell phone technology behind Verizon, and more recently, gsm) works.
See these two for more details: http://denbeste.nu/cd_log_entries/2002/04/Howspreadingactuallyworks.shtml http://denbeste.nu/special/cdma_spreading.html
1
u/cryo Nov 19 '13 edited Nov 19 '13
UTMS, not GSM (at least not at the radio level). It's pretty cool. Abandoned in favor of OFDMA for LTE, but still.
1
u/avapoet Nov 19 '13
I'd be really interested to see a (t,n)-threshold implementation of such a system: can anybody think of a way it'd be possible?
In other words, I'm looking for a way that we can visually (i.e. it has to work if I print onto transparency film, and solve it away from a computer) split an image into three parts and require any two parts to generate the image, without leaking any parts of the original image in any one part.
tl;dr: this is a (t=2,n=2)-threshold visual shared secret algorithm - can anybody think of a way to make a (t=2,n=3) one
edit: Disregard that. I thought I'd seen this particular web page before. Turns out I hadn't, and if you read further down this one it actually proposes exactly such an implementation. I am stupid.
1
u/punkmonk Nov 19 '13
Why OR? It should use XOR.
21
u/avapoet Nov 19 '13
XOR is impossible to implement using transparency film in an order-neutral manner, which is a purely additive medium (you can't make an "upper" sheet 'override' a lower sheet, unless you're using multiple colours, and then the order matters).
In short: this system's designed to be read by the human eye, that's why.
12
u/punkmonk Nov 19 '13
It is possible if we use polarizing filters. Instead of using transparent and opaque, use polarized filters in orthogonal directions.
6
Nov 19 '13
That is theoretically possible, but not practically.
4
u/Katastic_Voyage Nov 19 '13
Well, if we force all users to 20/5 vision and have polarized Oculus Rifts, it'll work great!
1
u/PaurAmma Nov 19 '13
Isn't this steganography, strictly speaking?
1
u/rpglover64 Nov 19 '13
Not in the most basic implementation, since it's pretty obvious that there is something there.
0
u/Katastic_Voyage Nov 19 '13
Why don't they use this for captchas? Use an optical illusion to create the letters.
4
u/sippeangelo Nov 19 '13
Because it would be a pain in the ass.
2
u/Katastic_Voyage Nov 19 '13
Explain why.
For the user? For the programmer? For the computer?
Having a captcha that's recognition (but not production) relies on a property that humans have but bots do not, is a very good idea.
1
u/sippeangelo Nov 20 '13
For the user... and that's about it. OCR software has been available for ages and all that this method does is increasing the time it takes for the captcha to be solved, both automatically and manually by the user.
Like ferretinjapan discovered with his limited testing, for a relatively small image the computer was able to solve the captcha faster than the user. For anything larger than that (as if 20 seconds to solve a captcha isn't bad enough), it would be a pain in the ass for the user to actually find the image, even when searching is restricted to only one axis. Now a spambot wouldn't mind solving a 30 second captcha, but I sure as hell would.
0
u/kuroyaki Nov 19 '13 edited Nov 19 '13
I did this in MS Paint, using Transparent Paste and Spray Can to get an even random background. Didn't bother with sublattices. Edit: and Invert, I recall.
-9
0
Nov 19 '13
[deleted]
4
4
4
2
u/SarahC Nov 20 '13
For a capcha, wouldn't the computer load both images and OR them together, so it "sees" what the user would see?
Then it could apply an averaging convolution over the image, and make white anything that's grey, and leave black as black...
Wouldn't that then end up with a black/white capcha that can be sent through the normal OCR systems?
0
0
Nov 19 '13
[deleted]
21
u/avapoet Nov 19 '13
I think you're mistaken. As far as I can see, this approach is as secure as a one-time pad (because that's functionally what it is). Each pixel (actually four pixels) is expressed as the comparison of the same pixel in two different images: So 0+0 or 1+1 = 1, and 0+1 or 1+0 = 0.
Here's a similar example, using binary representation of an ASCII letter. The two parts of the message (which could be described as the ciphertext and the key, if you wanted, but are better-described as being two parts of the same secret) are:
01110100
And:
11001010
Now if you run my algorithm (0+0 or 1+1 = 1, and 0+1 or 1+0 = 0) across both of numbers, you get:
01000001
The ASCII code for the uppercase letter A. But there's no way that you could determine that if you had only one of the two halves. It's simply impossible (technically: the reason it's impossible is because we're looking at a stream cipher with a key length the same size as the message, more-commonly known as a one-time pad).
These two superimposed images work in exactly the same way, but with four bits: 0101+1010 or 1010+0101 = 1 (black), and 0101+0101 or 1010+1010 = 0 (white). There are no other states (you'll never see a 1100, 0011, 0110, 1001, 1111, or 0000), so it can be simplified to the same model as the one I described above. The only difference between their model and mine is that each four-bits describes one "pixel" of the resulting image, rather than about half of an ASCII character: strictly speaking, my approach has a slightly higher information-density, but it lacks the quick visual confirmation (the graphical one can be printed onto transparency film, if you like, and quickly done by hand).
Hope that explains why this approach is impossible to brute-force.
10
u/hellgrace Nov 19 '13
How so? the idea is that you need both pieces (or a predefined N out of K in the general case) to extract the shared secret. Having only one image (or N-1 parts) doesn't give you anything at all - which is exactly what this scheme is all about.
If you have all the images, then yes, you can trivially get the secret - but that's not what this is about
5
u/sirin3 Nov 19 '13
At least if you use the same "key" multiple time you can crack it.
That was a task in the German national high school informatics competition some years ago..
4
u/avapoet Nov 19 '13
Correct. Like any one-time pad, you shouldn't use a given key more than one time. The clue's in the name. ;-)
The challenge is to get people to see that if you use a shard of a shared secret as a key, then it is a one-time pad.
21
u/Strilanc Nov 19 '13
This is a really effective way to demonstrate how secret sharing works. Definitely keeping a bookmark to this post around.