Quite happy with the captcha code. It compiles and loads, accepts input faster than 8chan's DNS captcha page even loads.
Here's a summary of how it works (doesn't need cookies, database connection optional):
Create a private key (P) randomly once (this will be used every time the captcha code is called).This can be a passphrase, as long as its sufficiently long and difficult to guess.
Captcha form creation:
Step 1. Make a randomly generated nonce (N) and challenge answer (A) made up of 6 alphabetical characters and a time stamp (T).
Step 2. Create a hash out of the concatenation: H = Hash[{P, T, N, A}]
Step 3. Create a form entry:
Step 4. Create a png of the captcha describing A.
Step 5. Base 64 encode the captcha image, embed in HTML
Step 6. Include N, H, T as hidden variable on a form
Captcha verification:
Assumes entry via POST
Step 1. Check if captchaN/H/T/A exists, if not fail for invalid form
Step 2. Check if timestamp is within expiry, if not, fail.
Step 3. Check if captchaA is n-alphabetical characters long, if not, fail.
Step 4. Change captchaA to lower case.
Step 5. Compute H' = Hash[{P, CaptchaT, CaptchaN, CaptchaA}]
Step 6. Verify captchaH = H', if not, fail for incorrect challenge answer.
There's no need to use a HMAC for the hash because the string has a fixed size, collision is as secure as the hashing function, computing it is more expensive than just guessing the captcha after which the timestamp would expire.
One hole: Repeat attack is possible, but then the chance of getting a hit is equivalent to randomly guessing. For a low-value target this is more than sufficient and can be dealt with using DoS-prevention at the server level. If its really required, a database can keep track of (T,N) pairs and eliminate them each time an attempt is made.