Encryption on the Internet has come a long, long way from the oft-ignored little yellow key in the lower left corner of your Netscape Navigator status bar. Today, cryptography is a vital part of all of our Internet lives, whether we realize it or not. Now, if you’re reading this article on Nerdland, chances are that you’re well aware of that, and I don’t need to explain why you need to be sure your online banking is done over an HTTPS connection, and why connecting your laptop to an open, unsecured wireless network is usually a bad idea.
But the little stuff can trip you up just as easily, and if you don’t have a solid understanding of the different facets of cryptography, you may well think that a system meets your security requirements when it does not. After all, modern cryptography is just mathematics. There’s no inherent application for it. Security isn’t a tangible property either; it’s an umbrella term for a whole class of goals. Rather, privacy, authentication, identification, trust, and verification — mechanisms of applied cryptography — are what provide the most commonly desired types of security. Understanding what these terms really mean, how they are implemented, and how they are different is essential to a true understanding of how encryption works to assure your security on the Internet, and even within a single computer.
Of the several programming jobs I’ve had in my (still relatively short) career, the one thing I’ve had to do the most frequently is implement networking protocols. I’ve implemented standard protocols defined by RFCs, I’ve implemented in-house proprietary protocols, and I’ve implemented experimental protocols for academic research. I’ve yet to be asked to design my own from the ground up, but I have developed a good feel, from an implementer’s perspective, of what works and what doesn’t when it comes to legible, extensible, and robust protocol design.
The point of this post is not to give a guideline for how to design protocols that work well, or are efficient. That is a topic of much larger scope, and if you’re interested in that, RFC 3117 is a good jumping-off point. Rather, this post aims to give a set of suggestions for how to design protocols that will be the least painful for yourself and other programmers to implement, debug, and apply. There is an underlying assumption here that you have already spent the time to decide what your protocol is trying to accomplish and that you have found a way to make it work well (assuming that it is implemented correctly).
When I was a kid, one of my favorite card games was War. In retrospect, I don’t really understand why I got so much enjoyment out of it, given that there is absolutely no strategy to the game whatsoever. If you happened to miss this game during your childhood, the rules are simple:
The deck is divided evenly between the players face-down. Each player reveals his top card, and the player with the higher card puts both the cards on the bottom of his deck. If the cards are of equal value, each player plays three face-down cards and a fourth face-up card, and the higher-valued card wins all the cards on the table. This is known as a war. In the case of another tie, the process is repeated until there is no tie.
A player wins by collecting all the cards. If a player runs out of cards while dealing the face-down cards of a war, he may play the last card in his deck face-up and still have a chance to stay in the game.
As you can see, since the player has no knowledge of which cards are in their initial hand, and no choice in which cards to play, this game could just as easily be played by a properly trained parakeet. The mechanical gameplay and lack of strategy, however, makes certain questions about the game mathematically interesting.
The other day when this game popped into my head, one of the first things I remembered about it was how many games I left unfinished due to their sheer length. I suddenly became curious about the expected number of turns required to finish a game of War.
It turns out that the answer is “about 277″ (which is considerably less than I expected). You see, people on the Internet tend to be pretty big nerds, and certainly I wasn’t the first one to consider writing a War simulation to figure out these kind of statistics. What I didn’t see discussed, though, is any treatment of the structure of a game of war.
Two new items have been added to Nerdland today.
First, on the left hand side you will see a link to a new section entitled “Unstumping the Internet“. The purpose of this section, as its index page explains, is
This set of pages is for cataloging relatively brief answers to questions that I had to figure out myself after being unable to find the answer on the Internet. [...] When I encounter a question that I cannot find an answer for on the Internet, and especially if in my searching I notice that several other people have asked this question with no satisfactory answer, I will post the answer here when I discover it. The hope is that next time someone searches the Internet for this question, they will find my answer.
So this section is not something that I expect anyone to read frequently, or even at all. I’m not going to be posting to the front page when I add new articles there, as the whole point of this section is to not clutter the front page with items of limited interest and minimal depth. Instead, I hope that these pages will visited primarily as the results of search engine queries.
Secondly, on the right hand side, there is a new section of links entitled “Interesting Items Elsewhere”. This is a listing of the last few items from other weblogs (or other sorts of feeds) that I have found most interesting. This is in fact tied to my Google Reader account, and displays items that I have “shared”, so these may not always be completely serious or computer-related. You can click on the “more” link at the bottom to see everything I’ve shared, as opposed to just the few most recent items.
From the “things that really shouldn’t be difficult, but for some reason are anyway” department comes the following. Do you think you know how to program in C++? Familiar with objects and polymorphism and templates and everything? Then this should be dead easy. Should, I said.
Problem: Write a function that takes in a
std::istream and a size
n and returns a
std::string. The string should contain the first
n characters of the input stream, with all formatting (whitespace, newlines, etc) preserved.
You can ignore all concerns about multi-byte characters for the sake of this problem. Sounds simple, right? You’d be able to crank this out in ten seconds if someone asked you this in an interview, right? Okay, now try it with this caveat.
Caveat: You must do this in a purely C++ “style”. To be precise, you must do this without using any character variables or character arrays. Use only a
std::string object (or some other memory-managed object in the standard library) as your input buffer.
For as much as the C++ STL tries to encourage you to use RAII-oriented containers instead of raw arrays, this seemingly trivial task requires some surprisingly baroque coding. If you want to test yourself, try writing the function before you click more.