Saturday, April 28, 2007

Captcha on Rails

Thinking about how Captcha handling could be implemented in Rails is a good mental exercise. Leaving aside the issue with entry barriers it creates for some people, and possible underlying technology implementations (like not-so-simple mathematical questions), let's formulate typical Captcha assumptions and requirements for a medium-sized Rails application:


  1. Image based
  2. Image/code combination could not be reused
  3. On an unsuccessful attempt, a new Captcha image is displayed
  4. Potentially multiple Rails application servers
  5. The attacker potentially knows the details on how you implemented Captcha

Let's pretend that we know how to generate a perfect Captcha image based on a supplied code string. All we need now is to meet the rest of the requirements.

Image/code combination could not be reused, means a need to prevent a human from entering the correct code, capturing a post sent to a server, and then replaying it many times via a robot.

Another point to remember is that a form with a link is generated on the first browser request, an image is retrieved with another request, and the Captcha validation goes with the third one. Potentially all three might arrive to different application servers.

Now, if you like challenges, try to think about possible solutions. The rest of this post talks about a few I have come up with by myself, though some might have been influenced by brainstorming sessions with the Revolution On Rails team.

In many of the solutions, a shared storage is used to overcome the multiple servers limitation. It could be a DB (ActiveRecord), memcached (Session), or some other solution. There is a clean up issue for cases when users abandon a Captcha form without entering a code. For some storage types (like memcached) it is taken care of by the engine itself, while for others a periodic cleaning job is required.

Unbreakable

Image/Code Generation on Request #1

Request #1. The application generates a code and an image and puts them into a Storage. A unique Captcha id (for example a captcha record id from ActiveRecord) is used in an image URL as well as in a hidden form field.
Request #2. Based on the Captcha id, the image is retrieved and deleted from the Storage. The image is sent to a browser via send_file.
Request #3. The entered code is compared with code retrieved from the Storage, based on the captcha id. Regardless of the result, the record is deleted from the Storage.


Code Generation on Request #1, Image Generation on Request #2

Request #1. The application generates a code and puts it into Storage. A unique captcha id is used in an image URL as well as in a hidden form field.
Request #2. Based on the Captcha id, the code is retrieved from Storage and used for generation of an image. The image is being displayed via send_file.
Request #3. The entered code is compared with one retrieved from the Storage based on the Captcha id. Regardless of the result, the record is deleted from the Storage.


Image/Code Generation on Request #2

Request #1. A unique captcha id is generated and is used in an image URL as well as in a hidden form field.
Request #2. The application generates a code and puts it into a Storage. An image, based on the code, is generated and is being showed via send_file.
Request #3. The entered code is compared with one retrieved from the Storage based on the captcha id. Regardless of the result, the record is deleted from the Storage.


Image/Code Generation on Request #1 with Code Hash

Request #1. The application generates a code and puts a hash of it in a hidden field form. An image is generated and is put into a Storage. A unique Captcha id is used in an image URL as well as in a hidden form field.
Request #2. Based on the Captcha id, the image is retrieved and deleted from the Storage. The image is sent to a browser via send_file.
Request #3. The entered code is compared with the hashed one. Regardless of the result, the record is deleted from the Storage.


Potentially Breakable

Some of the potentially breakable solutions are perfectly acceptable for a practical usage since the risk could be very low while benefits of doing image generation offline or having no storage involved could be significant.

Pre-Generated Code/Image

There are several scenarios with code/image pairs pre-generated off-line but none that can sustain an attack based on calculation of an image hash, noting the correct code, and calling the form till the same image comes again. The volume of images and frequency of their regeneration defines the level of risk.


No Storage

It is probebly not possible to come up with a generic solution involving no storage of any kind, while meeting all the requirements. There are some special cases though, with very low security risk. For example, a two-step login process with a standard login screen presented first, and the captcha next:

Request #1: The login form is sent.
Request #2: The application generates a code, encrypts it is with login name and password, and puts the encrypted string in a hidden field form. The image url generates using an encrypted code with some salt (timestamp.)
Request #3. The code is retrieved from the requested url. An image based on the decrypted code is generated, and is displayed via send_file.
Request #4. The entered code is compared with the decrypted and the account is then verified if the correct code was entered.

The obvious attack vector is to crack/steal the key, though in practice it is a well-understood problem to address.


Conclusion

Most likely there are papers on Captcha describing all the aforementioned solutions and many more, so this post could be seen as reinventing the wheel. Still, it was fun thinking about them. It would be great to hear about a perfect generic no-storage solution, feel free to share if you have an idea.

5 comments:

Anonymous said...

Just found your site from a colleague, there's some good stuff here.

To solve the captcha problem we generate a random image and then do a one way hash of the answer string. This is passed alongside the image as a hidden form element (we also use this name for the image itself). If the user fails the registration form a new image is generated so no need to worry about cross server file serving. If they fill out the form correctly we then hash their answer and compare with the hash passed through from the web form. In theory someone could discover the hashing algorithm but its fairly unlikely given we seed with a secret string and the answer is never a word.

To cleanup images you just need to code to delete the image after a successful registration and then a cronjob for people that fail or backout half way through.

Incidently you might like my presentation on scaling: http://www.slideshare.net/Georgio_1999/how-to-scale-your-web-app/

Eddie said...

Anonymous:

How do you handle the issue of replay?

I assume that you store both the hash and the image name in the form, so what stops an attacker from doing one by hand, preserving the POST, and replaying it?

Eddie

George Palmer said...

We have a lookup in memcached that checks for captchas used in the last x minutes.

Felipe said...

Good point!

Most of the programmers just install some Captca generation plugins, but forget about the Ruby's open-source architecture. This means the Captcha source code can be analyzed and, probably, be "overlapped"! Making our own captcha or changing the prebuilts may be a good practice!

Felipe Giotto
www.inovare.net

This.Is.Eric said...

Hello there,

I've implemented a little helper for Rails that does exactly what one of the other commenters mentioned: generate images off-line and use a one-way hashing function to generate the image filenames based on the captcha string. As an added bonus, the images look good on most background colors and could be adapted to work on very dark ones.

For more details about this plugin see Yacaph. It's pronounced "Yakaf" and stands for "Yet Another CAPtcha Helper".

Cheers