Extending SRP's guarantees to validated registration

This post is about work done jointly with Michael Sanders and Jacob Hurwitz for 6.858 (One of MIT's Computer System's Security courses).

The Stanford Remote Password Protocol is a really amazing little piece of cryptography. Like almost every great crypto-system, it provides seemingly impossible guarantees. Namely, it allows a server to recognize a client without having any real usable information about them.

In most authentication systems, the server is at some point in time privy to sufficient information to impersonate the user: perhaps you send your password to Google, Microsoft, or Facebook, or perhaps you send a hash. Regardless, as some point in the process, the server sees enough information about your password to fake a login later. With SRP, this isn't the case. To quote the SRP website:

SRP is a secure password-based authentication and key-exchange protocol. It solves the problem of authenticating clients to servers securely, in cases where the user of the client software must memorize a small secret (like a password) and carries no other secret information, and where the server carries a verifier for each user, which allows it to authenticate the client but which, if compromised, would not allow the attacker to impersonate the client. In addition, SRP exchanges a cryptographically-strong secret as a byproduct of successful authentication, which enables the two parties to communicate securely.

 Still, there is a slight problem with SRP, if you're willing to crimp down your tinfoil hat a little.

Starting out with ROS

This is going to be a pretty short post with the purpose of motivating future posts on related subjects.

I've got a lot of really cool robotics equipment now; a stock Hexy, a Cyclone Quadrotor, a Kinect, and a MakerBot Thing-O-Matic top the list, at the moment.

Unfortunately, a lot of these pieces of Hardware come with relatively  little software behind them. Hexy, for instance, has the short-but-sweet PoMoCo software to start. PoMoCo is great, but it's not very functional; by default, it allows only for interpolation between pre-programmed sequences of joint angles. It's very easy to pick the wrong combination of moves and get Hexy stuck in some contorted pose ( and you can forget about variable speed gaits ).

This isn't really PoMoCo's fault. Like Hexy, PoMoCo is designed to be a lightweight tool for beginners who can go on to use the platform for other things.

So, what's next for me on the Software side of Hexy? First off, I want to integrate Hexy with ROS (more on ROS in a later post). At first, I'm just going to hook PoMoCo into ROS and control it from the command line, but I plan on splitting PoMoCo into three ROS nodes, with the eventual goal of augmenting one of them with good gait generation and motor planning, and replacing the other with a series of ROS services to utilize Hexy from any ROS interfaced program.

In any case, I'll be working on Hexy when I  don't have to tool, and tooling when I can to get as much work in on Hexy. I'll keep you posted.

Voroni Diagrams and Graphs III: The Dual.

In this post, I'll write about the geometric significance of the dual of the Voroni graph and try to convince you that we can extend our discussion, which has so far focused on two dimensions, up to three-dimensions with only some minor changes ( I'll conjecture that the relationships I'm about to lay out extend much beyond that, but I don't have much proof of this ).


First, though, we need to discuss what a dual is.


The dual of a graph is itself another graph. Basically every face in the graph is a node in the dual, and two nodes in the dual have an edge between them if ( and only if ) their two corresponding faces share an edge (corners don't count).

The dual of a planar graph is itself a planar graph, and I claim that the dual of the dual of a graph is the graph itself (with the caveat that we discuss in the next paragraph). The figure below hints at a proof for this (note the crossing edges), though I'm not going to formalize it.

The Hough Transform I: Finding Lines

I've made reference to the Hough Transform in several previous posts, but I haven't ever done posts on what the transform is in a general sense, and how I've used it (and tried to improve it) in the past. In this series of posts, I'll try to rectify that.

The most basic implementation of the Hough transform is used to find lines in an edge image like the one below.  In this post I'll walk through the basic process of using the Hough transform to find lines in this image.

An image of machinery with edge detection applied. This image would be a good candidate for further processing with the Hough transform. (Source: Wikipedia)

Underlying the Hough transform is the idea that each pixel in an an image tells us something about the chances of there being certain lines in the entire image. If we have a pixel at point p, then it would make sense to look at all the lines that pass through p, and see if any of them happen to pass very close many other points in the image. If a particular line through p passes close to an unusual number of points, then it's a pretty reasonable to assume that this line constitutes an actual feature in the image.

3D Scanning, the Bowyer-Watson Algorithm, and Real Time (maybe) Delaunay triangulation.

 

  Wasn't that a mouthful! I'm taking another look at my 3D scanner. I really haven't talked about this scanner very much on this blog, so I've posted a video of it I made earlier this fall as part of my MIT application above. I'll move a good deal of the content from that portion of my application onto this blog over time, so long as it doesn't become too obsolete.

Cellular Turing Machines(Physics Simulation)

If everything works as planned, we've go our creature all the way manufactured, popped out, everything. It's sitting in the environment, ready to rock and roll. Now what?

Math Puzzler #3

There are six Dudeney numbers, positive integers whose decimal digit sum cubed is equal to the original number. they are
amath 1=1^3=(1)^3 endmath,
amath 512=8^3=(5+1+2)^3 endmath,
amath 4913=17^3=(4+9+1+3)^3 endmath,
amath 5832=18^3=(5+8+3+2)^3 endmath,
amath 17576=26^3=(1+7+5+7+6)^3 endmath,
and amath 19683=27^3=(1+9+6+8+3)^3 amath.

1. Prove there are no larger Dudeney numbers.
2. Find all numbers where the fourth power of the digit sum is equal to the number itself.

Hint: A computer may be useful to check cases, but it is possible to do this problem by hand, albeit with a bit of paper.
Solution 1 after the jump, Solution 2 next week.

TI83+ Programming....

After today's WSJ article about the TI83+'s codes, I have a renewed interest in programming. I'd love to make my own Mathematics and/or Chemistry OS.... I'll keep you posted.

And I made pong on my calculator! Quite neat. Runs better on a TI84 than my TI83+, but still, the code's pretty short, and I'm happy with how it turned out. Perhaps I'll do a separate post with some screenshots. Gonna try PacMan next.

Cellular Turing Machines(Creature Genetics and Development)

Rewritten on 1/12/11
Genetic code for these creatures is going to be an 11 character language based off brainfuck. The commands for the creatures is as follows:

• '<' and '>' increment/decrement the pointer to the primary node.
• 'v' and '^' increment/decrement the pointer to the secondary node.
• '.' link the secondary node and the primary node. If the two already linked, do nothing.
• ',' unlink the primary and secondary nodes if they are linked, else do nothing.
• '+' and '-' increment/decrement the value of the primary node (note that this value is cyclic!).
• '[' and ']' will preform looping functions, as in brainfuck. The loop terminates when the value a the primary node is zero when a check is made.
• '*' is a special character--it does nothing in the developmental code. Instead, it's used to mate creatures, maybe even to speciate them in a later version: '*'s are point of possible crossover. Actually, this command is where I can't wait to see what the program does. How will these characters, which have nothing directly to do with fitness, position themselves in the genome? Will it be random, haphazardly strewn around in the middle of loops and such? Could these start to partition off genes somehow, segments of the program which are independent from each other? I hope it's the latter. It would be really neat to see the evolution of alleles and such--some kind of more complex genetic code.

Cellular Turing Machines(Overview)

One of my other fascinations is evolutionary processes. In the past, I have written simple, computer programs in which short strings compete to become simple words, but I want to try something more complex. One of the big holdups? I've never developed a sufficiently complex and interesting way to representing these creatures before now.
One way I'd like to represent a creature would be as a complex set of nodes and links. Treating nodes as points, and links as springs or pistons between the nodes, creatures could be made to move. This is all really nice on paper, but I've always run into an implementation problem: How to give the creature a simple to implement but functionally meaningful way to manipulate its own movement.
This is where a cellular automata come in. These simple games can work as a method to control movement. If each node is given a state, and alters that state based on a simple set of rules, as in the game of life, the links can change their length based on the states of the nodes they are connected to. Of course, the game played on the creature needs some basic properties that some games just don't have. Conway's game of life assumes that each node has exactly four neighbors, while Langton's ant needs to have an order defined on the nodes. Any game that's to work needs to have coherent and interesting behavior regardless of the number of nodes, and it needs to have consistent behavior regardless of ordering. While not required, I'd love it if it were capable of sending signals down a single strand of nodes, and it'd be nice if it were possible to make some kind of resetting muscle.
I have at least one game that fits this bill: the Cyclic Cellular Automaton. This is what I hope to use in my program. Next post, I'll explain how I plan to build creatures from a linear genetic code.

Cellular Turing Machines(Introduction)

EDIT: I'm going to come back to this project soon and really finish it up, because I think it's worth doing. All my posts are bloated and badly formatted, and I've read up on a lot of relevant material, so I'm going over these with a fine tooth comb and clean them up, post clean code. Basically, I'm going to bring this up to speed, and hopefully release a nice clean application with some features that I really have wanted to see in other programs.

I have known for some time about Conway's game of life, but today I learned two things that surprised me.The first (and less surprising of the two for me) is that the game of life is a Universal Turing machine. In more common terms, it can act as a computer. I guess this doesn't surprise me so much because, in seventh or eighth grade, I remember making something very much like an AND gate in the game of life: Single cell inputs, and a single indicator cell. My gate destroyed itself in computation, but I saw no reason why a stable one could not be constructed (at the time, I was trying to do something other than make a gate, I cannot recall what).

The second, and somehow more surprising discovery (for me at least) was that Conway’s game is not alone. While reading though the book Professor Stewart’s cabinet of mathematical curiosities, I came across a short essay on a mathematical “creature” known as Langton’s Ant. The rules for the ant are simple, arguably simpler than those for the game of life and there is another amazing feature of the ant. Given long enough, the ant always seems to build a “highway” (see the link if you are confused). No one has ever proved this to be true, but no finite configuration of tiles is known that performs otherwise.

Another thing that struck me about the ant: If one imagines the ant to be flipping tiles on a glass plane, then looking at the plane from underneath yield the exact inverse of the view from above. Black tiles are now white, white now black, but the ant obeys the same set of rules. On further investigation of both games, I discovered that even more games exist. Some of these others have similarly interesting properties, like Day & Night, where the inverse of a pattern behaves in exactly the same manner as the original. So anyway, while reading about these various games I had an interesting idea. All the games I have encountered so far are played on a simple grid. As I considered various ways to implement such a grid in a program, one that stood out was a linked data structure, where a node indicated each square, and links showed which squares were adjacent. A second or so later I realized I could construct "loops" from the connections in such a system, and therefore assess the topology to the shape, at least in theory.

For example, most of the games with Langton's ant that I found allowed the ant to roam across the screen, wrapping in both directions as it came to the edge.This describes the topology to a torus: some loops (sets of connections between squares) cannot be "deformed" to a point, in fact, all loops that pass over the edge of the screen cannot be deformed in this manner. If you are confused, try this image, which comes from this page (WARNING: a LOT of math I don't understand EDIT: Oh. Now I do!). The picture shows a grid, which is what is displayed on the screen, and the topological interpretation, a torus. Note that straight lines on the square are circular "loops" on the surface of the torus, and that these loops cannot be moved (imagine rubber bands around a doughnut) in such a way as to squeeze and stretch them down to a point while they remain on the surface.

In any case, I got to thinking about different shapes I could deform the network into, including sphere like shapes, mobius strips (EDIT: I now know I was really thinking of a projective plane here- A kind of double mobius strip that can't be neatly embedded in three space. It's neat. Check it out.), and twisted versions of these shapes (while topology may not care about twists and deformations, the Game of life certainly would), when I had an idea. It will take a while to explain, even on its own, so I will end this post here and pick up the rest later on in another post.Watch for part 2 soon!