Pseudo Random Journal Generator Predictable permutations on programming, technology, and more.

Silly Encryption Schemes: Part 1

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

adam_25sep2009.plan

So something a bit more interesting this time (at least for the more technically inclined).

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 strange 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. Probably not. 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.

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 to 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!

adam_03may2009.plan

I decided I would begin updating this again, if for no other reason than it helps to organize thoughts 😛

Nothing big this time, just thought this random musing on Ubuntu privacy would interest someone.

So Ubuntu 8.04 and above gives you a Private directory by default. It is an encrypted directory that is only mounted and decrypted when you log in, which makes it ideal for storing things you don't want other users to see.

But it's not as private as it might seem right off the bat. If you are logged in, and thus the directory is mounted and decrypted, any other user logged in at that time can simply navigate to it and browse it's contents!

This isn't really a security hole or anything, it's just how it is designed. The real problem lays with Ubuntu's default permissions for user's home directories.

Let me restate the problem so it's clear: a Private directory should not be able to be browsed at all by other users. It's nice that it is encrypted which protected it from many kinds of prying most of the time, but still, I don't want people to be able to snoop in it ever!

So the fix is simple, when in your user home directory:
chmod 700 Private

Now ONLY someone logged in as you may browse your Private directory. period. But this got me to thinking, and I wanted to take this a step further. It seemed to me, that it didn't make sense that ANYONE could browse my entire user home directory. So next I restricted my entire user directory in a similar fasion, while sitting in: /home I did:
chmod 700 myUser

Which *worked* but gave me the predictable result that now the public_html directory in my user directory was now inaccessible to Apache :/

Clearly not acceptable. But the fix is easy. First, make sure your public_html directory in your user folder is part of apache's group, on my system that is www-data:
While in your user directory: /home/myUser do:
chown myUser:www-data public_html

And make sure it's permissions are: 755
Then, go to the home directory: /home and make your user ditectory part of the www-data group:
chown myUser:www-data myUser

And finally, make sure your user directory has 750 permissions:
chmod 750 myUser

And now your entire user directory is only readable to you and Apache, your public_html directory is still good to go. And your Private directory is completely locked down to JUST you. Privacy catastrophe averted! Or something like that 😛

Hopefully I'll have more interesting things to write about as I go forward here!

- Adam

adam_07may2008.plan

Just typed up a pretty good entry here... then lost it due to stupidity... (and the back button).

But it's been a long time since my last update, and believe it or not, quite a lot has happened in the past 5 months.

Decrypt got quite a bit of attention here and there. It's at a pretty polished v1 stage. And I hope to get some mission 2 stuff going soon as well as a possible graphical make over.

I also wrote some articles, on the left nav bar there. As well as two new projects. Nothing big, just some quick little projects I did on the side.

Thats all fun stuff, but I guess the news is that I'm graduating in less then two weeks.

I haven't really had time to think about it so far. I've had a crushing class load which has been pretty all consuming. Almost done though, so just gotta keep my head down and work hard these last two weeks.

After graduation I'm moving down to Dover to finish up that project. Should be pretty exciting finally releasing one of my babies into the commercial market like that.

I will try to keep this more up to date from now on, so check back if you're interested.

Wish me luck on getting through these last two weeks 🙂

- Adam

adam_20nov2007.plan

Spent a bit of time fixing up some code in Decrypt, killed some show stopper bugs dealing w\ the OS API for the applications which affected progressing through missions. Also upgraded PHPFreeChat to v1.0 final. PHPFreeChat is the software behind the chat application.

Gotten quite a lot done on the console project lately too.

See, in programing you quickly come to two assumptions which are fairly safe to make.

1) The programing language is right, your code is wrong.

2) The 3rd party library you are using is right, your code is wrong.

The first is pretty darn stead fast, and the second isn't far behind (depending on how mature the library is of course).

So you'd think it'd be safe to assume the second when you are using a 20 year old, time tested library put out by the likes of a company such as NewTek (makers of LightWave).

But... you'd be wrong...

Lets examine this piece of code, it comes from lwio.c which wraps all of the I/O functionality that the rest of the files use. In there, there is a specific function which is used to read a NULL terminated string of bytes (not necessarily ASCII characters, but it doesn't really make a difference). We know this is it's purpose because we have read the documentation and looked at the data it is actually called on, it is always NULL terminated.

Now take a look at the function and tell me if you can spot a problem with it:

   for ( i = 1; ; i++ ) {
      c = fp->fgetc();
      if ( c <= 0 ) break;
   }

Ok, the point of this piece of code is to count the size of bytes that the data is so we can allocate memory for it.

First, ew. Ugly code. But lets trace it, we keep reading and incrementing our count variable until... until what? Until it is less then or equal to 0...

HHhhhmmm... does that make any ef-ing sense if what it is we are looking for is NULL ( NULL == 0 btw )?

Assuming we just did not understand the actual point of the code we continued reading the spec, looking at the data it was reading in a Hex editor and running through everywhere the read function was called.

With out a doubt it was looking for a NULL terminated string of bytes, and that chunk of code was meant to count up to the NULL character.

So we quickly replaced the bugged line and came up with the more explicit:

   for ( i = 1; ; i++ ) {
      c = fp->fgetc();
      if ( c == '\0' ) break;
   }

Now on a side note, the most astute of you may notice the file I/O using what appears to be an Object or Struct pointer. Well you are right, we ported the code to C++ and use our FileBuffer and FileIterator classes to emulate std:: file I/O operations. We looked a lot into how our getc() function might have been working differently then std::getc(). But I can assure you, that it works the same.

So back on topic here, it's not hard to see the case in which the original code would fail. Anytime the byte overflowed as an unsigned 8 bit int, it would be negative. The specific byte that was fucking us over was 0x80.

So, with that fixed, we finished porting lwobject and fixing bugs that cropped up in it. Then I went on to extract all the information we needed out of it and create our internal data structure for holding the data how we wanted to render it. Let me tell you, the UV coordinates were a bitch to find.

Just to get the texture file path, it took these two lines of code:

lwClip *clip = lwFindClip( obj->clip,
layer->polygon.pol[ii].surf->color.tex->
param.imap.cindex );

char *texturePath =
clip->source.still.name;

Anyway... With that all done I finished connecting all the dots between all of the supporting systems and the renderer and finally, finally, got Textured, 3D, rendering working.

So the current state of things is and solid complete base with 2D and 3D loading and rendering working.

Next, we start on integrating ODE! I don't want to jinx things, but it should, *fingers crossed* go a lot smoother then the other integrations have.

- Adam

adam_02nov2007.plan

So quite a bit of progress on the console development front.

As always while coding a big project like this, no matter what the actual task at hand is, I always clean up and refactor tons of of little semi or completely unrelated things along the way. So lots of little parts of the engine have been cleaned up, is the sort of central theme of what I'm trying to say I guess...
arrr...

Annnyyy waaayyyy...

The engine now has a fully functional scene graph as well as a fully functional state manager / input handling system.

With all that in the bag, Rob and I working on integrated libPng and LibZ for use as your texture loader, and moved on to getting texture rendering working inside our engine (much more difficult then you'd have thought).

Moving forward we ported some file loading code for .lwo (LightWave Object) files. Let me tell you... not fun.

The code was ~20 years old. It was made when C compilers had almost no type checking apparently. So the first task was just getting it to compile in a modern C compiler. Then the porting could begin. To get it running on the console we had to use a custom File I/O class we have developed to assist with porting libraries. Bringing the old C code in C++ was even more fun.

Ever seen a function call like this?
lwListFree( (void*)texture, reinterpret_cast( lwFreePlugin ) );

I don't know about you, but I'd never seen this arcane syntax before, but this what I had to come up with to get it to compile.

See, most modern code can be ported simply by dropping in our special header file. But some older code is more difficult. So we developed this class them emulated most of the C style file I/O. While we still have to go through and modify many many lines of code, our class is structured to work exactly like the old C style functions, so the structure and flow of the code need not change.

We have been developing good strategies and a good code base for porting libraries. So far we ahve ported libPNG, libZ (required by libPNG), lwobject (LightWave Object code), and partially ODE (Open Dynamics Engine).

While we did in fact get the lwobject code compiling and running, we still dont have the renderer coded to read and render the data from memory yet. Thats the next task. But with all the heavy lifting done by lwobject, it should be a sinch.

The real next task will be getting ODE running, verifying that it works, and plugging it together with everything else.

So starting to get close to some pretty exciting stuff!

- Adam