Archive Write | Let’s You and Him Fight

Write

cl-bcrypt: A first attempt

First, a disclaimer: I am new to Common Lisp; in fact, this is the first Lisp project in which I’ve completed a working prototype. My previous experience is largely in Python and Ruby. I do not represent that the code below is ready for general use. If I’m doing something wrong, please educate me.

The introduction: What is bcrypt?

I want to write a web application in Common Lisp. Part of this task is implementing authentication. The accepted state of the art for safely storing passwords is bcrypt._[1] Just one little problem; if you click on that link, right at the top you will find links to implementations in many languages, but Common Lisp is not among them. However, I know that most of these implementations are wrappers around the C implementation, and I am informed that Common Lisp has excellent FFI support, so even though I’m not very experienced with C, this shouldn’t be too hard.

The FFI approach

And indeed it wasn’t: here’s the complete code for cl-bcrypt:

It works on my system (Mac OS X 10.6, SBCL 1.0.39) and is compatible with the Python bcrypt library (which I used for testing). There’s just a few ~~small~~ big problems.

The Common Lisp specification defines a random function, but makes no guarantee that this is a cryptographically strong PRNG. In the absence of such a guarantee, I fear I must assume that it is not suitable. The predominant Lisp crypto package, Ironclad, lists “random number generation” in its TODO file. So I use a crude hack: I open /dev/urandom and just read bytes straight from it. This is obviously only feasible on Unix-like systems which have a /dev/urandom. I am open to suggestions for improvements.
The C bcrypt implementations (yes, there are two independent implementations) are poorly packaged._[2] Lisp’s CFFI, much like Python’s ctypes, provides a pure-Lisp method of interacting with shared libraries. The library is simply expected to be present where the system can find it. Unfortunately, both C implementations are designed primarily for integration into libc. One of them, the OpenBSD implementation, is integrated with OpenBSD’s libc. While it seems some wrappers, like py-bcrypt have extracted it, I didn’t feel confident in my ability to do this myself. I chose to use the Openwall implementation. This also provides a glibc integration, but here, the actual bcrypt implementation is already separated out. The Python wrapper targeting this implementation (yes, there are two independent Python bcrypt libraries) was useful in figuring out how to use it, since Openwall’s source lacks docs and helpful comments. Unfortunately, the provided makefile does not even build a shared library, let alone install it, so you presently have to do this yourself. In Python/Ruby, it’s relatively easy to tell the build system to build a C shared library and include it with the native library, but ASDF, the Lisp package system, appears to have no support for this (likely because Lisp so rarely needs the shim C code that Python libraries use to integrate.) For the time being, you will need to build a bcrypt shared library by hand.

How to use it

These directions worked for me on my system. I hope they will work for you.

Download the Openwall bcrypt source, extract it in a directory of your choice, and run make.
Now create a shared library: gcc -shared -W1,-soname,libbcrypt.so.1 -o libbcrypt.so.1.0.4 crypt_blowfish.o x86.o (of course, replace 1 and 1.0.4 with the correct version numbers).
Place the resulting libbcrypt.so.1.0.4 somewhere where Lisp can find it. The *foreign-library-directories* variable may be useful here.
Compile and load the code.
(cl-bcrypt:encode "foo") or, optionally, specify a strength: (cl-bcrypt:encode "foo" 12). The default strength is 10. A strength of 16 takes approximately 6 seconds to process on my 2.66Ghz Intel i7 Macbook Pro. encode produces the hashed password in a format that includes the random salt, so you merely have to pass the hashed password and the candidate into check to verify: (cl-bcrypt:check (cl-bcrypt:encode "foo") "foo"). It returns t or nil.

What about a native approach?

People in freenode’s #lisp kept suggesting that I implement bcrypt myself, perhaps using parts of the blowfish source from Ironclad. I kept trying to explain the First Law of Crypto_[3], but they didn’t think much of this objection. Also, I actually went and looked at the blowfish source; it seems to differ substantially from the eksblowfish algorithm bcrypt uses. About the only thing I could reuse without modification would be the s-box constants. Again, as per the First Law, this would be unwise for me to attempt.

That said, I would gladly donate a bit of money if someone qualified wanted to implement a native version.

[1] As Thomas Ptack puts it, “To optimize Blowfish to run much faster, you’d have to contribute a major advance to cryptography. We security practioners are all ‘betting people’, and we usually like to place our bets on the side that ‘demands major advances in cryptography’.” Colin Percival has presented what may be an even stronger scheme, but as I am not a crypto professional, I don’t think I should adopt scrypt until it’s received more scrutiny. ↩

[2] Percival’s scrypt is also poorly packaged; the only download provided is for a symmetric encryption package designed as example code for the algorithm; there is certainly no easy way for an end-user to install a scrypt library. ↩

[3] The First Law of Crypto reads as follows: “Unless you are a crypto professional, you do not implement your own cryptographic primitives.” (The Second Law is the same as the first law, but with more boldface.) The hazards of violating this law are well known. ↩

Wednesday, July 14th, 2010 Write View Comments

Comet in Erlang with Mochiweb and a Finite State Machine

Comet is a pretty nebulous technology, encompassing everything from really-frequent XHR requests to the cutting-edge WebSocket protocol. Sadly, WebSocket is a bit too cutting-edge for my tastes, so for my app, I’ve chosen a long-polling approach based loosely on the Bidirectional-streams Over Synchronous HTTP protocol. By loosely I mean really loosely; I’ve really only kept the notion of request ids and session ids.

The comet connection consists of two HTTP connections, only one of which is long-polling at any one time. It’ll wait a maximum of a minute for any server-side information. Whenever the client needs to send data to the server, there’s another available connection. I’ve implemented the comet client in Cappuccino, but you can do it with any JavaScript framework.

Mochiweb is a lightweight HTTP toolkit for Erlang. I chose Erlang for this project because it’s rock solid with easy scaling, and the lightweight process / message passing system makes coding Comet easy.

Here’s the Mochiweb request handler:
The io:format calls are unnecessary; they’re just there for me to keep an eye on things while I develop the system. The important bit is the two calls to inet:setops/2. Internet sockets in Erlang can be in either active mode, in which incoming data is sent as messages to the associated Erlang process, or passive mode, which means that process needs to manually request data when it’s ready for it. Mochiweb works in passive mode, which has one major disadvantage; you don’t get notified if the socket dies. So, before we switch into waiting for data, we set the socket into {active, once}. This means that one message will be allowed to be sent to the process before setting it right back into passive mode. We can’t get additional data from the client on this socket at this point in time; we’ve already received the entire request and have yet to send any response. So, the only message we can receive from the socket is {tcp_closed, Socket}. That way we avoid trying to send messages from the server to a socket that’s died.
I use this gen_server (I’ve only shown the internals; the rest of the gen_server is pretty basic) to make session ids both unique and unpredictable.

Finally, here’s the meat of the system: the connection FSM:

I’ll break it down function by function.

handle_json/1 is called by the comet request handler I showed above. It decodes the JSON request body and determines if this is a request to set up a comet connection, or a request on a connection that already exists. handle_setup/1 is pretty obvious, but handle_request/3 is a little more complex. It sends an event to the FSM that there’s a new request and sits down to wait for a message — forever. It also traps that {tcp_closed, Socket} message I mentioned earlier; if that happens it tells the FSM it went away and dies. But otherwise it returns the message back to the client.

Finally, handle_packet/2 will be called by the app logic, once I write it, to deliver messages to the client.

So much for the FSM interface. The internals of the FSM live in the same module, in the callback functions.

start/0 and init/1 are pretty straightforward. I want to mention the dietimer here, though. If 45 seconds elapses without a waiting request from the client, we assume the client’s gone offline and tear down the corresponding FSM. We’ll kill or reset the timer in plenty of event handlers, though.

The next bunch of functions handle events sent with gen_fsm:send_event/2. This is the heart of the FSM. There are three states: waiting (for both requests and packets), have_request (but no packet), and have_packet (but no request). They should also all be pretty straightforward.

This took a bit of time to set up, but I think it’s easy to follow, which is the important part. There’s still a bit of work to be done; I haven’t set up the actual app logic that the messages will be going to or coming from. But this is a good start.

Sunday, January 31st, 2010 Write View Comments

Adding support for a new procedural language to Postgres 8.3

I’m working on implementing a new procedural language for Postgres. The docs have a section on this. Too bad it turns out to cause compiler errors and generally not work.

So, for the benefit of anyone else who’s interested, here’s what I did to get an utterly barebones one working. It’s hardcoded with support for only one function, but once you have the framework in place, you can put in your interpreter or whatever. I’ll blog about that when I get to it.

C source:

Makefile:

SQL setup and use:

Saturday, May 16th, 2009 Write View Comments

Comet for Cappuccino

Comet is a vaguely-defined set of technologies for asynchronously sending data from the server to the client. Cappuccino is a framework for developing apps in Javascript. Once more, we at “Let’s You and Him Fight” are doing science by smushing things together: Cometuccino

Friday, May 8th, 2009 Write View Comments

What I’ve been working on

Grid-o-Matic is a Javascript-based combat grid for D&D 4 and other grid-intensive games. Click the image below for a short QuickTime video showing it off.