[ This post is a bit long, sorry about that 😀 ]
[ I’m more accustom to writing for less technical audiences, so if this comes across as too much hand holding, I apologize, I’ll try to tech it up more in the future 😉 ]
So I have had an interest in Cryptography for a while. Now let me stop you right there, no, I’m not a crazy math genius, so I’m not going to regale you with formulas and number theory. No my interest is more… playful.
My first ever Cryptography related thing I wrote some years back was a super simple cipher tool. My girl friend at the time was giving me notes in a cipher she created (it was a straight forward, 1 for 1, substitution cipher), so I wrote a program to decode them more quickly. I then expanded the program to some other simple ciphers.
Later I wrote a simple XOR encryption program, and also a steganography program which can hide ASCII text in 24bit Bitmap images. (Both projects can be seen here)
Finally I wrote a web based cryptography game called Decrypt that teaches people how to decode ciphers by hand while unveiling a story to them. (Though as browsers have changed and improved, it has falling into a bit of disrepair, though it is still playable I believe.)
Fast forward to a few months ago:
I have been milling around on cryptography sites again, pretending to understand what I’m reading. I can’t see the day when my pseudo understanding of asymmetrical encryption will pay off, but hey, you never know 😉
So with thoughts of lovely encryption algorithms dancing in my head, I turned to another topic I had been mulling about, it had to do with some 3D math I had abandoned in another project: Calculating the intersection points of 3D Spheres (It’s not redundant, look up 4D Spheres, AKA: Quaternions). This oddly enough lead me to a silly idea for an encryption key generation scheme: Distributed Planar Key Encryption
( Or at least that’s what I’m calling it. I don’t know if it’s something that has been done before. It’s kinda pointless, but cool 😛 )
Let me stop right there, I’ll come back to the math in a moment. So the idea for this encryption scheme came (as many ideas of mine do) from the movies. You’ve seen those movies where a super important vault, or missile launch system, or whatever has multiple key holes, and both keys must be inserted at the same time to be able to unlock it? It prevents any single person from misusing their key, as multiple people are required to agree on accessing it.
Well maybe it’s just me, but I think that’s kinda cool 😛
Ok so back to Distributed Planar Key Encryption, that’s exactly what this scheme aims to be. You see, several Child Keys will be generated at encryption time. These keys, Child Keys, will combine to form the single unique Parent Key which is the actual encryption key. That of course will be used to encrypt the data.
Then the encrypted data can be sent to each concerned party along with a single Child Key. Or the encrypted data can be kept in a single place, whatever, that’s not the point. The point is that no single user can decrypt the data with their given key. They must bring together enough keys to pass the Key Threshold. Once that Threshold is passed, the Parent Key can be generated, and the data can be decrypted.
The important part is that ANY combination of Child Keys, as long as you have enough of them, can generate the Parent Key. So you can’t just take the Parent key and break it up into pieces. If you did that, you would have to have specific Child Keys in order to reconstruct the Parent Key. It would also mean that given one Child Key you could begin to solve for the other Child Keys. Needless to say, this would be a bad thing…
OHKAY… So. How do you go about making a scheme that satisfies these requirements! Actually it’s a lot easier than you’d think. And this is where we come back to the 3D Spheres I mentioned earlier. Given 4 unique Spheres (they ALL must overlap) you can calculate a single unique point in 3D space where they all intersect. And use that point as the basis for your encryption key (aka: the Parent Key).
So this was my first attempt at a Distributed Key Encryption Scheme, dubbed: Distributed Spherical Key Encryption
But there were some problems. The first was that the math to intersect Spheres is quite complicated. Though I got that working finally. The next problem is what killed it however. See, on the surface of a sphere, there are, in theory, an infinite number of points, because 1.3 is a different number then 1.33, and so on. (Of course, a computer is a finite machine, so it’s not quite infinite, but still pretty good.) The problem came in how modern computers store decimal (aka: rational) numbers.
They are called “Floating Point” numbers, and computers actually suck at storing them exactly. You can read up more on why that is on Wikipedia if it really interests you. But here is why it’s a problem: when I run these complicated equations to calculate the point of intersection, I get slightly different numbers every time. That is to be expected with Floating Point arithmetic. And we, as computer scientists, have ways of dealing with it. Generally, we look at two numbers that we want to compare, and if the difference between them is under some threshold (epsilon) then we consider them to be the same number.
So the difference between 1.45555 and 1.45556 is less then the threshold of 0.001, we would consider them the same number. I’m pulling these numbers out of you know where, in reality epsilon (aka: 0.001) is much much smaller, but you get the idea.
So it should have worked, right? Wrong. See, the equations are complicated enough, and each time a floating point operation is done (+, -, *, /) there is a slight bit of error. Since so many operations are done in the course of determining the point of intersection, all the different errors add up to quite significant fractions so that the epsilon test would fail ~9 out of 10 times, making it quite unreliable.
What this means is… Given however many Child keys, 9 out of 10 times, you would NOT generate the proper Parent Key. And the Decryption of the data would fail.
My only option was either to round off to, at MOST two decimals, or to use fixed point math and drop decimals all together (sort of).
Neither solution was preferable. The first one, would probably make it reliable to 99 in 100, but that 1 in 100 times when your secret data didn’t decrypt, wouldn’t be a happy day.
The latter method can be refereed to as “Discretizing” the math. Or, making the math use Discrete numbers. The problem with this is that, instead of having theoretically INFINITE points of intersection on the surface of your sphere, you now had a discrete, known number of possible points. Now remember, the point of intersection of 4 Child Keys IS the Parent Key. Thus, the complete Parent Key actually and truly exists on the surface of every single Child Key sphere.
When there were an infinite number of points of the surface of each child, it didn’t matter. But now, by making the numbers discrete, there are a known number of points on each sphere. Thus, given a single Child Key you could brute force through the points on that Sphere alone, and find the Parent Key.
(While there are ways to mitigate this [using particularly massive spheres], it actually reduces the search space in other ways, but that’s for another article.)
Just to reiterate, one of the key points of this encryption scheme is to not be able to determine the Parent Key with any fewer then N Child Keys. N being the Key Threshold as defined by the algorithm.
So this was clearly not an acceptable solution as it violated one of the core tenants of the encryption scheme.
(As a side note. The spherical keys were flawed from the start. See, N (the Key Threshold) for the algorithm was 4. You need 4 spheres to generate a completely unique point. But given just 3 spheres, you can in fact generate exactly 2 unique points. Well you don’t need a computer scientist to tell you that brute forcing 2 possible solutions won’t take you very long… Thus with only 3 of the 4 required Child Keys, the Parent Key could easily be deduced.)
Quite a bit discouraged, I stepped back from it and had some dinner. And it struck me. I was only fixated on using Spheres because it was what I had been working with previously in an unrelated project. And that in fact, as I just mentioned, they are quite poorly suited to the task anyway.
3D Planes however are perfect!
For those who forgot their highscool geometry:
3 Dimensional Plane: A theoretical surface which has infinite width and length, zero thickness, and zero curvature.
- Planes have a theoretically infinite surface area, thus they don’t suffer the same problems from using discrete, fixed point math
- Planar intersection testing is much simpler then Spherical intersection testing.
- It only required 3 planes to determine a unique point of intersection (Thus the Key Threshold is one less then for Spheres)
- Given 2 keys (AKA Planes) an entire line of intersection results with theoretically, infinite points on it, even with discrete math, the security of the algorithm doesn’t degrade as you approach but do not meet the key threshold.
So while 3 keys are the minimum that must be generated, you can generate any number you wish that all intersect at a single unique point, and any 3 keys can be intersected to unlock the Parent Key.
This was exactly what I had been searching for. So I began coding in earnest. (It also occurred to me, that a Linear Key system could work as well, reducing the number of Child Keys required down to 2. But I stuck with the Planar Keys.)
Now. That’s all well and good. Mission accomplished and all that. (No really!) But encryption can be a very boring subject to many people. And it sure doesn’t look as cool as it does in the movies, crazy blocks flying every which way to unlock the secret file. Which got me thinking. I am actually using 3D constructs in the math, so there really is no reason I couldn’t visualize this in a 3D app. Ya know, actually show the different planes (keys) in a 3D view, and show them intersecting, and then highlight the common intersection point. I could even do a little animation with it to make it snazzier.
So that’s what I’m currently working on, and I will be sure to post here about it when it’s done!