• On Tuesday I implemented message metadata.
• On Wednesday I got SSL working (configuring the “server” side to verify the “client’s” cert was difficult.)
• On Thursday I put Cloudy up on blocks, pried out Vortex and my Obj-C wrapper library, and replaced them with BLIP.
• And on Friday (today) I debugged.

Cloudy’s back up and running, and all its features work. So, that makes one week of effort to implement the networking layer from scratch (I started sketching and coding on Saturday). Really makes me regret spending several times that on the previous library—writing an Obj-C API, fixing bugs, adding features. Still, I’m sure all that experience helped me implement BLIP so quickly.

(The code for BLIP is quite separable from Cloudy; but it does use some lower-level utilities and network classes I wrote, so it’s not quite standalone. And it needs documentation before it’ll make sense to anyone. How soon I release it depends on how much interest there is, so let me know if it’s something you’re interested in using.)

What am I talking about? The networking code in Cloudy. From the very beginning I wanted to use BEEP, a generic and flexible protocol for sending request/response messages over a socket. It has good support for parallelism, nice abstractions like multiple channels and feature negotiation, and supports SSL.

The BEEP implementation I’m using is Vortex. It has the benefits of existing (there aren’t a lot of BEEP implementations around), being written in native code, and being within my capabilities to get running on Mac OS X. Unfortunately it’s also got a very complex and unintuitive C API, spawns lots of threads and calls my code from them (so I have to deal with thread-safety), and isn’t quite finished yet. So over the months I’ve put a lot of work into writing an Objective-C API, figuring out how to get that working reliably, and diving into the Vortex code to fix bugs and add new features.

At some point—I think it was last Thursday—I crossed a line and started to wonder whether putting more effort into Vortex was throwing good money after bad. I wanted to use some of BEEP’s MIME features, but found that Vortex only implements a tiny subset, and that even that implementation doesn’t work right. Going down the path of fixing and improving, I found that I would have to break compatibility with any earlier versions of Vortex (which all send wrongly-formatted data), and that every patch I added was exposing more bugs, whether existing ones or newly-added ones of my own. And all this meant hacking on complicated code in plain C, with very long functions, and liberal usage of ‘goto’ statements.

Unfortunately, there are not many BEEP implementations to choose from (it’s hard to compete against HTTP, the hammer everyone reaches for.) There’s a private BEEP.framework inside OS X, but I’d have to be a fool to use it (for legal reasons if not technical.) I found that SubEthaEdit has one, and I’ve asked the developers about it, but I’m sure there will be financial terms.

So yeah, I’m writing my own.

No, I am not writing my own BEEP implementation! Stupid sensationalistic headlines. I thought about it for a few hours on Friday, but BEEP is actually pretty complicated and I knew it would end up taking longer and being harder than I would like.

But then I started to think about what BEEP features I need, and which ones I don’t, and realized I could make do with a subset. Things I need:

• Multiple messages and replies over a single socket
• Parallelism (don’t have to strictly alternate messages and replies)
• Message metadata (some type of MIME-like headers)
• SSL support

But I don’t need:

• Multiple channels (that’s a biggie! Quite complicated.)
• Well-defined schema (“profiles”) with negotiation over which to use
• FIFO message delivery
• Negotiation of whether to use SSL
• SASL and other authentication schemes
• Interoperability with any other clients

On Saturday morning, a bit of pen-and-paper doodling convinced me I could create a simpler protocol that used some of the ideas of BEEP, and would give me just the features I needed. And since I could build on top of the Foundation and CFNetwork classes, in Objective-C, I could do it with a whole lot less code than Vortex.

So I started coding…

BLIP.

It’s almost ready now, Monday night. I don’t have message metadata implemented yet, and flow-control needs work, but the rest is running pretty reliably. I’m calling it BLIP, for “BEEP-LIke Protocol” (or maybe “BEEP-Lite Imitation Protocol”, like some kind of suspect canned food product you might find in a dingy supermarket.)

What does BLIP do? It lets you open a TCP socket and then use it to send messages back and forth. Each message is a data blob of arbitrary length, with an optional set of key/value properties [once I implement that]. Each message can have a reply associated with it, so you can send a message and then wait for the reply. Either peer can send messages, at any time (as opposed to most protocols that only let the “client” who opened the connection send messages, and only the “server” reply.)

Multiple messages can be in flight at once, in either direction: sending a 10MB file doesn’t block the transfer of other data. Messages can request high priority to get more bandwidth, or they can request gzip compression.

And it’s only 1500 lines of code, so far! Vortex is about 34,000. Even my Obj-C wrapper for Vortex is bigger than BLIP is. [All those figures ignore comments and blank lines.]

I’m sure BLIP will end up doubling in size before it’s really ready; and I’m also sure it’ll take a lot more time than I’ve spent on it. But both of those figures are cheap compared to what I’ve invested in something that ultimately wasn’t working for me. So I think in this case re-inventing the wheel is justified.

…Meaning that I’ve answered the implied question of this post’s title, coming down on the side of “clever”. Whew! (What else did you expect? it’s my blog, after all.)

[PS: Yes, if BLIP does work out, I’ll certainly open-source it. I wouldn’t call it a replacement for BEEP, as it’s a lot more limited, but I think it’ll be useful.]

Stickies makes its entrance at 0:53, if you want to skip directly to it, but really the entire video (and song) are excellent. I just wish they’d used Stickies in the opening scenes instead of Word—face it, Word is over the hill, especially that old Office 2004 version. (Did you see the bags under the Office Assistant’s eyes? Stickies told me they dragged it straight out of the Betty Ford Center to shoot those scenes, and it couldn’t remember any of its lines even though they were right up on the screen next to it in giant print. It’s sad, really. At least it hasn’t OD’d yet like that pathetic paperclip.)

This seems to be a fan-made video, by the way; but I think it’s better than the official one. Now the question is: will Apple use this in a commercial? I think they should!

[via 37signals]

I’ve been experimenting this week with coroutines. Typically these are implemented as a type of cooperative thread, since each coroutine needs a separate stack and register set. I adapted Steve Dekorte’s libCoroutine, which basically just uses ucontext, with malloc’ed stacks.

It strikes me that ucontext is basically no lighter-weight than a pthread, in terms of address-space usage and context switch speed. Is that true? Or is there additional overhead to pthreads besides the stack + registers?

If so, then it might be simpler just to use pthreads, since the API is already in place, and existing system facilities (like ObjC and C++ exceptions, and Cocoa autorelease pools) already know how to work with them. But the cooperative scheduling of coroutines is a bonus in some ways, as it makes the flow of control more deterministic and reduces the need for complex locking and synchronization.

So my second question is whether there’s a clean way to implement cooperative scheduling of pthreads¹, i.e. to have a set of threads that transfer control within themselves only via some sort of “yield” call, not by pre-emption? I’ve seen this implemented, for tutorial purposes, in Java using a shared lock. However, a coroutine transfers control to an explicitly-named other coroutine; it’s not at the whim of the thread scheduler. How would one implement that in pthreads? I’m guessing it would involve a lock per thread; but I’m not familiar with the details of the pthreads primitives or API, so advice would be appreciated.

—Jens

¹ Yes, I’m aware that cooperative scheduling means you don’t get all the performance benefits of multicore CPUs. I’m not concerned about that because, frankly, my application code uses minimal CPU time; it’s always waiting for sockets, CoreAudio background threads, or user input. So the benefits of threading my code aren’t worth the complexity and error-prone-ness of thread-safety.

What I’d really like to use are Actors. In a nutshell, an Actor is an object that has its own [cooperative] thread and message queue. Actors interact by message-passing instead of shared state. The idea is to eliminate the need for standard synchronization primitives like semaphors and locks, and get rid of the race conditions and deadlocks that plague multi-threaded programs.

The page I linked to above is from Revactor, a new Actor implementation for Ruby 1.9; Actors are also built into languages like Erlang and Io.

The only hard part about implementing Actors in Obj-C appears to be the underlying dependency on coroutines. Steve Dekorte [author of Io] has a C coroutine implementation ; when I discovered that last year, I then found an Objective-C wrapper for it, but that relies on a HigherOrderMessaging library which is incompatible with OS X 10.5 and hasn’t yet been updated.

So I’ve gone DIY.

I started with Steve Dekorte’s coroutine library, but unfortunately it doesn’t build on 10.5 … and when I got it to build, I then ran into a bug in the system header … and by the time I’d worked around that, I knew the code well enough that I pretty much rewrote it. Doing this made it much shorter and clearer, since Steve’s code is cross-platform and supports three different implementations, while all I care about is OS X 10.5. I got it down to 150 lines of C.

Then I wrote a pretty simple Objective-C wrapper around it, under 200 lines. (Here’s the header.)

Come ‘n’ get it…

The work in progress is in my Mercurial repository if you want to check it out. It’s grandly titled “Actors”, but all that’s in it so far is the coroutine implementation.

Needless to say, this is currently for amusement purposes only; do not use it in real code. In particular, I strongly suspect that there are going to be problems getting Objective-C exceptions and autorelease pools to work correctly in coroutines. I’ll try to explore that next.

The first time you connect to someone, how do you establish that digital identifier you’re communicating with is the human being you think it is? This is surprisingly difficult to do, because it’s prone to what cryptographers call the “man-in-the-middle attack”.

(Those of you already wearing tinfoil hats can skip past the general explanation, down to “What Cloudy Does”.)

1. A Quick Overview Of Verification Attacks.

First, consider the most obvious attack: simple spoofing.

Spoofing.

Let’s suppose there’s an instant-messaging UI, and while working at home you receive a message from someone with an unknown key, whose nickname is “AliceLiddell”, which happens to be the name of a co-worker.

“AliceLiddell”: yo, this is alice
You: hi alice, what’s up?
You add this identity to your friends-list.
Alice: i need the admin password to the web server to fix a template
You: oh ok, it’s wend4743kt
Alice: kthxbye

Fifteen minutes later your company’s website is pwned by the hacker who posed as Alice. All he had to do was create a new identity with her name as the nickname, and pretend to be her.

How do we get around this? You might think that asking questions before accepting someone’s claimed identity would help, and it does help with spoofing, but there are nastier attacks.

Man-In-The-Middle

“AliceLiddell”: yo, this is alice
You: You haven’t contacted me before … how do I know you?
“AliceLiddell”: i’m down the hall next door to brad. i need to ask you a question but you’re not in the office today.
You: yeah, i’m working from home. sorry to be paranoid, but what’s the poster on your wall say?
“AliceLiddell”: it used to say “hang in there baby” but i took it down when lolcats started getting too popular =)
You add this identity to your friends-list.
You: cool … hi alice, what’s up?
…

Having established that this is really Alice, you go on to give her the password … and fifteen minutes later your company’s website gets pwned anyway. What went wrong? Well, it really was Alice you were talking with; but the hacker was able to listen in and read the password. Wasn’t the industrial-strength 2048-bit RSA encryption supposed to prevent this?

The problem is that you and Alice were talking with each other; but you weren’t directly connected to each other. Instead each of you was connected to the hacker, who was relaying your messages back and forth. In this scenario what probably happened was that Alice tried to look you up by your name, found the hacker’s fake account instead, and the hacker’s computer then quickly created an identity with the same nickname as Alice, connected to the real you using that identity, and started forwarding your messages to each other while recording them itself.

What’s even worse: That identity you added to your friend-list as Alice? It’s really the hacker’s identity. From now on the hacker can talk directly to you and you’ll probably assume it’s Alice.

How Do We Solve This?

The man-in-the-middle attack is resistant to nearly any kind of in-band verification. You can ask Alice any personal questions you want, but it won’t reveal that you’re not connected directly to Alice. You can ask Alice to type in her public key, but the hacker can edit her reply and substitute the key he’s connected to you by.

About the only practical way to solve this, unfortunately, is to use an out-of-band channel. You need to talk with the real Alice and compare notes, before you can trust that her digital identity belongs to her. All you have to do, really, is get her real public key and compare it to the key you’re communicating with. (And she has to do likewise, of course.)

The canonical way to do this is to meet Alice in person and swap public keys. (PGP users call this a “key-signing ceremony”.) Or you and Alice can read your keys to each other over the phone (or Skype, or an iChat video conference.) Sending the keys over IM is somewhat less reliable, but enough so for many purposes, since forging centralized IMs is a fairly involved task.

Of course, we don’t want to read 512 hexadecimal digits to each other! One optimization is to compare secure hashes of the keys (as PGP does), but that’s still 40 digits. And those “B”s and “D”s are so easy to mix up over the phone.

2. What Cloudy Does.

Cloudy’s verification scheme is blatantly stolen from the one used in Bryan Ford et al’s Unmanaged Internet Architecture. Instead of making you read a number as a string of digits, Cloudy converts it into a three-word phrase by mapping consecutive chunks of bits into words in an English dictionary, moreover a dictionary that’s been specially constructed of words that are easy to recognize and hard to mix up.

And instead of making you listen to the words and type them in, Cloudy (like UIA) presents a short list of phrases with radio buttons, for you to pick from. One of them is the one that will be correct if the connection is genuine, the others are chosen at random, and there’s a catch-all “None of the above” at the end. If the user didn’t select the expected phrase, something’s wrong.

(An aside: the phrase only encodes 32 bits, which is far less than even the SHA-1 hash. Just hashing the key down to 32 bits would not be secure enough; instead Cloudy creates a one-time 32-bit key by combining the public key with a randomly-chosen integer that’s sent to the other peer at the time of verification.)

Ford points out another benefit of this interface: “its multiple-choice design prevents users from just clicking ‘OK’ without actually comparing the keys”, which defeats the user’s damnable tendency to just dismiss all security-related alerts.

Once this is done, and the user chose the right verification phrase, Cloudy adds the other person’s public key/identity to your “contact list” in its persistent storage. You can then decide to associate that key with an entry in your Address Book. Cloudy also mints a “relationship” certificate attesting that you have verified the other person’s identity; you can choose to annotate the relationship with XFN tags like “friend” or “co-worker”. These certs can be passed to other friends to transitively extend trust.

How well does this user interface work? Cloudy hasn’t seen much real-world use yet, but I’ve gone through the initial setup with a half-dozen people, and the verification (once I debugged it!) is quite easy to follow and takes only ten seconds or so.

3. Is This Too Paranoid?

One of the unpleasant side effects of learning too much about computer security is that you start to become paranoid. You swallow the red pill of the Internet and discover how much we take for granted, how much trust we implicitly place in things that are not trustworthy: domain names, centralized databases, passwords, emails. In severe cases, you start to self-identify as a cypherpunk and refuse to connect to any server through fewer than three anonymizing proxies. It’s a bit like Medical Student Syndrome.

On the other hand, I think a lot of this paranoia is justified. I remember the old days, when “spam” was just a Monty Python sketch and you could trust the “From:” line of an email. Nowadays most of the emails we get have forged senders, and even a message that sounds like it came from a friend might have been sent by some shady social-networking site he foolishly uploaded his address book to. Not too many people worry about domain names yet, but DNS is not hard to mess with, either by hackers or by profit-motivated ISPs.

Eventually, anything that can be subverted, will. And since peer-to-peer software can’t use the standard brute-force obstacles (centralized authority, locked-down servers) to delay attacks, it has to rely on actually being secure. And that means public keys, encryption, webs of trust. As many have pointed out, if you make security an optional add-on to a product, hardly anyone will use it. (How many people you know sign or encrypt their email?) It needs to be built in by default. And the more our privacy is invaded by advertisers, ISPs, search engines, phishers, monopolistic content owners and the like, the more that drives the adoption of actually-secure software by end-users.

Having to go out-of-band and swap three-word verification codes with your buddies is an inconvenience. But you only have to do it once with any particular person; after that, Cloudy remembers their key. And I will probably, in the future, put in some form of transitive trust: if I haven’t verified you, but I verified Jean-Claude and he’s verified you [and signed a cert to that effect] then I’ll decide to trust you too.

Next: Cloudy Gossip.

WHEREAS most members of Apple developer mailing lists are aware that we are not supposed to discuss anything about the iP•••e SDK on those lists; and

WHEREAS I and almost everyone else have good-naturedly gone along with this annoying ban; but

WHEREAS more than a month has gone by, and there is still no forum for such discussion, not even one lousy mailing list, indicating that the secrecy-obsessed individuals at Apple who decreed this policy have not seen fit to do anything to help solve the problems it created for others; and

WHEREAS it is pretty plainly in Apple’s best interests for iP•••e developers to pool their expertise so as to improve their products; then

THEREFORE be it resolved that I, for one, no longer find it important to humor the wishes of said bureaucrats.

*****

I don’t know that I’m about to start any new threads asking questions, as I’ve put my development for said platform on hold until such time as I am granted the ability to actually install software on it; but I’m not going to hold my tongue if questions come up on mailing lists, which I happen to know the answer to.

If worst comes to worst we can create a mailing list somewhere else and just not publicize it. (Of course, if that’s already been done, then can someone please email me the info?)

But I’ve seen a couple of references now to Dean Allen’s complaint about sites that offer multiple RSS feed formats, but no place to post a comment about it; and since it directly relates to my past job monkeying with feeds, I feel like I should answer.

There are two reasons why a web page would link to multiple feeds.

1. To support feed-readers that don’t understand every format. The XML-syndication-format field has a totally ludicrous history of incompatible versionitis, and the only format that’s actually sanely designed (Atom) is new enough that for a while some major clients, such as BlogLines, didn’t support it. So it’s reasonable during such a transition period to generate both formats.
2. Because there might be feeds with different content. Some sites offer headlines-only feeds and full-content feeds. Some blogs offer a feed of all the comments on one post, as well as the usual feed of all the posts. Some wikis offer a feed of revisions of a single page.

The problem for a client like Safari is that there isn’t a clear way to tell the difference between those two cases. When a site offers multiple feeds (by including multiple LINK tags in its HTML) do they have the same human-readable content or not? Answering that would require, at a minimum, downloading and parsing both feeds and trying to match the contents of the entries.

The first version of Safari RSS (in Mac OS X 10.4) went for simplicity, by indicating in its UI only that there was a feed available, not how many. If the user pressed the “RSS” button, it would pick one of the feeds to switch to. The heuristic was to give priority both to order (picking the first feed listed) but also to format (preferring Atom to RSS, because the format is much better-defined and less prone to nasty ambiguities and parsing problems.)

But some people complained that, on sites that offered multiple feeds with different content (like articles vs. comments) you couldn’t use the button to pick which one you wanted. So in Mac OS X 10.5 we decided to make the button into a pop-up if there were multiple feeds listed.

The problem now is that you more commonly end up being offered a choice between two formats with identical content, which is what Dean and others complain about, because most blog engines are configured to offer both Atom and RSS (and sometimes multiple flavors of each.)

Here’s where I could talk about the design problems of the feed auto-discovery mechanism, and describe better ways it could have been designed to support multiple feed formats [hint: HTTP 1.1 already supports content-type negotiation] or even future improvements that could be made to reduce this annoyance in the future. But you know what? I don’t care about Trendy XML-Based Syndication Formats anymore. OK, all right, I clearly care enough to write a multi-paragraph explanation and post it to my blog. But not any more than that.

Point-to-Point Communications.

When one Cloudy peer wants to communicate with another one, it opens a TCP socket to its IP address —

[Hang on, there are two issues I suddenly glossed over in that last phrase. First, how did this peer find out the others’ IP address? These are just random computers, not servers, so they don’t have their own domain names or even stable addresses. This is indeed a problem with any unstructured peer-to-peer network, but the solution involves things I won’t get to until the next installment, in an unfortunately but necessary violation of layering.]

[Oh, and issue #2 is that most home computers are now behind Network Address Translators (usually some kind of WiFi base station or broadband router), which means they don’t have their own real IP addresses and can’t receive incoming connections. Fortunately, most NATs now support protocols that allow clients to open listening ports to the outside world, and doubly fortunately, Mac OS X 10.5 includes an API for making such connections. Cloudy opens such a port whenever it finds itself behind a NAT.]

— and runs a protocol called BEEP over the socket.

BEEP.

BEEP is a sort of generic application protocol that multiplexes a TCP socket into multiple virtual channels, each of which can send and receive binary messages. It’s very handy for designing your own protocols, since it lets you focus on the high-level tasks of defining how your messages are encoded and when to send them and what to send in response.

I’m using an open-source (LGPL) implementation of BEEP called Vortex. Its API is in C, but I’ve written a Foundation-level Objective-C wrapper around it. (I’ll probably open-source that code sometime.)

One nice feature of BEEP and Vortex is that they handle SSL for you. The BEEP protocol lets the two peers negotiate what type of SSL they support, before switching over to it, almost transparently to the application code. Since the first thing that happens in SSL setup is exchanging certificates, each instance of Cloudy immediately learns the identity of the peer it’s connecting to. (In normal HTTP-over-SSL, only the server has a certificate and the browser remains anonymous; but SSL supports bidirectional authentication and Cloudy uses it.) Unlike most client-server protocols, Cloudy has no need for a login: each peer has seen the others’ public key, and the ability to use that public key proves that the other peer owns the private key, and hence that identity.

So now the two peers are connected, they’ve identified and authenticated each other, and their communication channel is encrypted. They can now open BEEP channels and send each other messages across them. The primary types of messages Cloudy sends are signed objects (certificates); I’ll get into those later.

Local Area Discovery (Bonjour).

As you’d expect, Cloudy also uses Bonjour. This is somewhat orthogonal to BEEP —Bonjour’s a discovery protocol, so its main purpose is to let peers on the same LAN find out each others’ names and addresses. But Bonjour does support a thing called a TXT Record, which is a small chunk of arbitrary metadata that a service can associate with itself. For example, iChat stores your availability and status message in its Bonjour TXT record, which is how its Bonjour buddy list can show that information for everyone on your network.

Remember the “CallingCard” I used as an example of a signed object in the last post? Well, that’s what Cloudy puts in its TXT record. The CallingCard contains your availability and status, but what’s really important is that it contains your public key, which is your identity.

So Bonjour solves, at least on a LAN, the discoverability problem I pointed out at the start of this post. At this point, if the peer you want to send messages to is on the same network, Cloudy can easily find it via Bonjour, open a BEEP socket, and authenticate over SSL.

What’s more, Cloudy’s view of who’s on the network is actually trustworthy. The CallingCard is signed with your public key, proving that you created it. iChat’s Bonjour IM has always been insecure in that there’s no way to tell whether anyone else is who they say they are: all you know about someone is their name, which they can easily change to anything they want by editing their address book. In Cloudy, on the other hand, once you’ve communicated with someone once, your app remembers their public key, and it can identify in the future whether a peer appearing on the network is that person or not. (To make this clear in the UI, the name of anyone you haven’t previously vouched for is shown “in quotes”.)

— Oops, I just skipped over a tricky problem again. The first time you connect to someone, how do you establish that the digital identifier you’re communicating with corresponds to the human being you think it is? This is surprisingly difficult to do, because it’s vulnerable to what cryptographers call the man-in-the-middle attack. It’s worth a post by itself…

Next: Verifying Identities>