Saturday, December 04, 2010

A PKI based CAPTCHA Implementation

I'm thinking of implementing CAPTCHA verification for an upcoming application, so I decided to check out JCaptcha, which provides libraries for image and sound CAPTCHAs, as well as an implementation you can directly use in your web application. Based on my understanding of the code from its 5-minute tutorial, the way it works is that it generates a random word, sticks it into the session and renders an image of the random word on the browser. When the user types the word back in, it matches the value in the session against the user input.

Most production systems are load balanced across a bank of servers. In such cases, the JCaptcha wiki either advises using either a distributed singleton or sticky sessions. This is because the session is used to hold on to the original generated word.

An alternative approach that eliminates the need for sessions would be to carry an encrypted version of the original word as a hidden field in the CAPTCHA challege form. Various encryption approaches could be used:

  • One-way hash - the original word is encrypted with something like MD5 and put into the hidden field. On the way back, the user's response is also encrypted and the digests compared.

  • Symmetric two-way hash - the original word is encrypted with something like DES and put into the hidden field. On the way back, we can either decrypt the hidden field back and compare to the user input, or encrypt the user input and compare with the hidden field.

  • Asymetric two-way hash - the original word is encrypted with the public part of a RSA keypair (in my case), and on the way back, decrypted with the private part, and compared to the user input.

I guess that any of these approaches would be secure enough to serve as a CAPTCHA implementation, but I hadn't used the Java PKI API before, and I figured that this would be a good time to learn. The code presented here includes a service (that manages the keypair and does the encryption and decryption), a Spring controller (that calls a JCaptcha WordToImage implementation to generate a CAPTCHA image, and methods to show and submit a CAPTCHA challenge form), and a JSPX file that can be used as part of a Spring Roo application.

Service

Asymmetric two-way hashes (around which the PKI API is based) are based on the premise that:

  d(e(m, q), p) == m

  where:
    m = the message body.
    p = private part of a keypair {p,q}.
    q = public part of a keypair {p,q}.
    d = decoding function.
    e = encoding function.

In typical usage, user A sends a message to user B with keypair {p,q} by encrypting it with B's public key q who then decrypts it with his own private key p In our case, there is only keypair, which belongs to the server. On the way out, the generated word is encrypted with the server's public key, and on the way back, the encrypted value in the hidden field is decrypted back with the server's private key.

At startup, each server loads up its keypair from a pair of key files, deployed as part of the web application. That way each server decrypts the encrypted key exactly the same way. Also, since the encrypted version is carried through the request-response cycle, a CAPTCHA generated on any one machine in the cluster can be verified on any other machine.

To generate the word, the service generates a 32 character MD5 checksum of the Date string at the instant the form is called from the browser, then pull a random substring from it between 3 to 5 characters in length. Here's the code for the service:

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
// Source: src/main/java/com/mycompany/ktm/security/CaptchaCryptoService.java
package com.mycompany.ktm.security;

import java.io.File;
import java.security.KeyFactory;
import java.security.PrivateKey;
import java.security.PublicKey;
import java.security.spec.PKCS8EncodedKeySpec;
import java.security.spec.X509EncodedKeySpec;
import java.util.Date;

import javax.crypto.Cipher;

import org.apache.commons.codec.binary.Hex;
import org.apache.commons.io.FileUtils;
import org.apache.log4j.Logger;
import org.springframework.stereotype.Service;
import org.springframework.util.DigestUtils;

@Service("captchaCryptoService")
public class CaptchaCryptoService {

  private final Logger logger = Logger.getLogger(getClass());
  
  private static final File PRIV_KEY_FILE = 
    new File("src/main/resources/captcha.pri");
  private static final File PUB_KEY_FILE = 
    new File("src/main/resources/captcha.pub");
  
  private Cipher cipher;
  private PublicKey publicKey;
  private PrivateKey privateKey;
  
  public CaptchaCryptoService() {
    try {
      byte[] pri = FileUtils.readFileToByteArray(PRIV_KEY_FILE);
      PKCS8EncodedKeySpec priSpec = new PKCS8EncodedKeySpec(pri);
      KeyFactory priKeyFactory = KeyFactory.getInstance("RSA");
      this.privateKey = priKeyFactory.generatePrivate(priSpec);
      byte[] pub = FileUtils.readFileToByteArray(PUB_KEY_FILE);
      X509EncodedKeySpec pubSpec = new X509EncodedKeySpec(pub);
      KeyFactory pubKeyFactory = KeyFactory.getInstance("RSA");
      this.publicKey = pubKeyFactory.generatePublic(pubSpec);
      this.cipher = Cipher.getInstance("RSA/ECB/PKCS1Padding");
    } catch (Exception e) {
      throw new RuntimeException(e);
    }
  }
  
  public String getEncodedCaptchaString() {
    byte[] currentTime = new Date().toString().getBytes();
    String md5 = DigestUtils.md5DigestAsHex(currentTime);
    int start = random(0, 32, 100);
    int length = random(3, 5, 10);
    String plainText = slice(md5, start, length);
    return encrypt(plainText);
  }

  public String getDecodedCaptchaString(String encoded) {
    String decoded = decrypt(encoded);
    return decoded;
  }
  
  public boolean validate(String encoded, String response) {
    return response.equalsIgnoreCase(getDecodedCaptchaString(encoded));
  }

  private boolean keyFilesExist() {
    return PRIV_KEY_FILE.exists() && PUB_KEY_FILE.exists();
  }

  private String encrypt(String plainText) {
    try {
      cipher.init(Cipher.ENCRYPT_MODE, this.publicKey);
      byte[] encrypted = cipher.doFinal(plainText.getBytes());
      Hex hex = new Hex();
      return new String(hex.encode(encrypted));
    } catch (Exception e) {
      throw new RuntimeException(e);
    }
  }

  private String decrypt(String encodedText) {
    try {
      cipher.init(Cipher.DECRYPT_MODE, this.privateKey);
      Hex hex = new Hex();
      byte[] encrypted = hex.decode(encodedText.getBytes());
      byte[] decrypted = cipher.doFinal(encrypted);
      return new String(decrypted);
    } catch (Exception e) {
      throw new RuntimeException(e);
    }
  }
  
  private int random(int min, int max, int multiplier) {
    while (true) {
      double rand = Math.round(Math.random() * multiplier);
      if (rand >= min && rand <= max) {
        return (int) rand;
      }
    }
  }

  private String slice(String str, int start, int length) {
    StringBuilder buf = new StringBuilder();
    int pos = start;
    for (int i = 0; i < length; i++) {
      if (pos == str.length()) {
        pos = 0;
      }
      buf.append(str.charAt(pos));
      pos++;
    }
    return buf.toString();
  }
}

To generate the key pair, I just used the following Java code, although you can also use ssh-keygen or something similar to generate them from the command line.

1
2
3
4
5
6
7
8
9
    KeyPairGenerator keyPairGenerator = KeyPairGenerator.getInstance("RSA");
    keyPairGenerator.initialize(1024);
    KeyPair keyPair = keyPairGenerator.generateKeyPair();
    FileUtils.writeByteArrayToFile(
      PRIV_KEY_FILE, keyPair.getPrivate().getEncoded());
    FileUtils.writeByteArrayToFile(
      PUB_KEY_FILE, keyPair.getPublic().getEncoded());
    this.privateKey = keyPair.getPrivate();
    this.publicKey = keyPair.getPublic();

Controller

I want to add the CAPTCHA into a Spring Roo application (which does not exist at the moment), so I just tried to add it into an existing app to test out the code. The controller code consists of three methods:

  1. Load the CAPTCHA form - in real-life, this would be a create/edit form for a domain object with the CAPTCHA stuff added to it. For testing, all it does is show the image and offer a single text box.
  2. Generate the CAPTCHA image - Generates the image using JCaptcha's WordToImage implementation and writes to as a PNG file.
  3. Handle the CAPTCHA form submit - as before, this would be part of another form in real-life. This takes the encrypted string and the user input and validates it against each other.
  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
// Source: src/main/java/com/mycompany/ktm/web/CaptchaController.java
package com.mycompany.ktm.web;

import java.awt.Color;
import java.awt.image.BufferedImage;
import java.net.BindException;

import javax.annotation.PostConstruct;
import javax.imageio.ImageIO;
import javax.servlet.ServletOutputStream;
import javax.servlet.http.HttpServletRequest;
import javax.servlet.http.HttpServletResponse;

import org.apache.commons.lang.StringUtils;
import org.apache.log4j.Logger;
import org.springframework.beans.factory.annotation.Autowired;
import org.springframework.stereotype.Controller;
import org.springframework.validation.BindingResult;
import org.springframework.validation.ObjectError;
import org.springframework.web.bind.ServletRequestUtils;
import org.springframework.web.bind.annotation.ModelAttribute;
import org.springframework.web.bind.annotation.RequestMapping;
import org.springframework.web.bind.annotation.RequestMethod;
import org.springframework.web.bind.annotation.RequestParam;
import org.springframework.web.servlet.ModelAndView;

import com.mycompany.ktm.fbo.CaptchaForm;
import com.mycompany.ktm.security.CaptchaCryptoService;
import com.octo.captcha.component.image.backgroundgenerator.EllipseBackgroundGenerator;
import com.octo.captcha.component.image.fontgenerator.TwistedRandomFontGenerator;
import com.octo.captcha.component.image.textpaster.SimpleTextPaster;
import com.octo.captcha.component.image.wordtoimage.ComposedWordToImage;
import com.octo.captcha.component.image.wordtoimage.WordToImage;

@RequestMapping(value="/captcha/**")
@Controller
public class CaptchaController {

  private final Logger logger = Logger.getLogger(getClass());
  
  @Autowired private CaptchaCryptoService captchaCryptoService;

  private WordToImage imageGenerator;
  
  @ModelAttribute("captchaForm")
  public CaptchaForm formBackingObject() {
    return new CaptchaForm();
  }
  
  @PostConstruct
  protected void init() throws Exception {
    this.imageGenerator = new ComposedWordToImage(
      new TwistedRandomFontGenerator(40, 50),
      new EllipseBackgroundGenerator(150, 75),
      new SimpleTextPaster(3, 5, Color.YELLOW)
    );
  }
  
  @RequestMapping(value = "/captcha/form", method = RequestMethod.GET)
  public ModelAndView form(
      @RequestParam(value="ec", required=false) String ec,
      @ModelAttribute("captchaForm") CaptchaForm form,
      BindingResult result) {
    ModelAndView mav = new ModelAndView();
    if (StringUtils.isEmpty(ec)) {
      form.setEc(captchaCryptoService.getEncodedCaptchaString());
    } else {
      result.addError(new ObjectError("dc", "Bzzt! You missed! Try again!"));
      form.setEc(ec);
    }
    mav.addObject("form", form);
    mav.addObject("ec", form.getEc());
    mav.setViewName("captcha/create");
    return mav;
  }

  @RequestMapping(value="/captcha/image", method=RequestMethod.GET)
  public ModelAndView image(HttpServletRequest req, HttpServletResponse res)
      throws Exception {
    String encoded = ServletRequestUtils.getRequiredStringParameter(req, "ec");
    String decoded = captchaCryptoService.getDecodedCaptchaString(encoded);
    BufferedImage image = imageGenerator.getImage(decoded);
    res.setHeader("Cache-Control", "no-store");
    res.setHeader("Pragma", "no-cache");
    res.setDateHeader("Expires", 0);
    res.setContentType("image/png");
    ServletOutputStream ostream = res.getOutputStream();
    ImageIO.write(image, "png", ostream);
    ostream.flush();
    ostream.close();
    return null;
  }

  @RequestMapping(value = "/captcha/validate", method = RequestMethod.POST)
  public ModelAndView validate(
      @ModelAttribute("captchaForm") CaptchaForm form,
      BindingResult result) {
    ModelAndView mav = new ModelAndView();
    String ec = form.getEc();
    String dc = form.getDc();
    if (captchaCryptoService.validate(ec, dc)) {
      mav.setViewName("redirect:/captcha/form");
    } else {
      mav.setViewName("redirect:/captcha/form?ec=" + ec);
    }
    return mav;
  }
}

The form backing object is a plain POJO with only two fields. If we are using a domain object as our form backing object, then I think we can just add these two fields as @Transient, although I haven't tried it. Theres not much to this POJO, I show it below, with getters and setters omitted.

1
2
3
4
5
6
7
8
9
// Source: src/main/java/com/mycompany/ktm/fbo/CaptchaForm.java
package com.mycompany.ktm.fbo;

public class CaptchaForm {

  private String ec; // encrypted string
  private String dc; // plaintext string
  ...  
}

And finally, the JSPX file. This is a copy of one of the Roo generated JSPX files, with the image generated using an <img> tag, a single text field to get the user input, and a submit button.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
<div xmlns:c="http://java.sun.com/jsp/jstl/core" 
     xmlns:form="http://www.springframework.org/tags/form"
     xmlns:jsp="http://java.sun.com/JSP/Page"
     xmlns:spring="http://www.springframework.org/tags" version="2.0">
  <jsp:output omit-xml-declaration="yes"/>
  <script type="text/javascript">
    dojo.require('dijit.TitlePane');
  </script>
  <div id="_title_div">
    <spring:message var="title_msg" text="Captcha Challenge"/>
    <script type="text/javascript">
      Spring.addDecoration(new Spring.ElementDecoration({
        elementId : '_title_div', 
        widgetType : 'dijit.TitlePane', 
        widgetAttrs : {title: '${title_msg}'}
      })); 
    </script>
    <form:form action="/ktm/captcha/validate" method="POST" 
        modelAttribute="captchaForm">
      <form:errors cssClass="errors" delimiter="&lt;p/&gt;"/>
      <div id="roo_captcha_image">
        <img src="/ktm/captcha/image?ec=${ec}"/>
      </div>
      <div id="roo_captcha_dc">
        <label for="_captcha_dc">
          Enter the characters you see in the image above:
        </label>
        <form:input cssStyle="width:250px" id="_captcha_dc" 
          maxlength="5" path="dc" size="0"/>
        <br/>
        <form:errors cssClass="errors" id="_dc_error_id" path="dc"/>
      </div>
      <div class="submit" id="roo_captcha_submit">
        <spring:message code="button.save" var="save_button"/>
        <script type="text/javascript">
          Spring.addDecoration(new Spring.ValidateAllDecoration({
            elementId:'proceed', 
            event:'onclick'
          }));
        </script>
        <input id="proceed" type="submit" value="${save_button}"/>
      </div>
      <form:hidden id="_roo_captcha_ec" path="ec"/>
    </form:form>
  </div>
</div>

I also had to create a new views.xml for this controller, similar to other Roo custom controllers. It only has a single entry, here it is:

1
2
3
4
5
6
7
8
9
<?xml version="1.0" encoding="UTF-8" standalone="no"?>
<!DOCTYPE tiles-definitions 
  PUBLIC "-//Apache Software Foundation//DTD Tiles Configuration 2.1//EN" 
  "http://tiles.apache.org/dtds/tiles-config_2_1.dtd">
<tiles-definitions>
  <definition extends="default" name="captcha/create">
    <put-attribute name="body" value="/WEB-INF/views/captcha/create.jspx"/>
  </definition>
</tiles-definitions>

Putting it all together

As I said before, a "real" use-case of this would be to embed it into an edit form for a domain object - here, I am only interested in testing the functionality, so its being used standalone. Here are some screenshots demonstrating the flow:

Entering /captcha/form in my browser would take me to the challenge form with a CAPTCHA challenge image generated:

If I enter an incorrect value, it shows me an error message and regenerates the same string into a different CAPTCHA image, hopefully more readable this time. This is not the standard behavior for most CAPTCHA's I've used, they generally give you a new image of a different string in these cases. Notice that the URL now has the ec parameter which contains the encrypted string.

If I enter a correct value, it is silently accepted and the form is regenerated with a new CAPTCHA challenge.

References

Apart from the references above, I found the following links very helpful. All the APIs here (except Spring and Roo) are new to me, so I had to do a bit of reading before everything came together.

  • Bouncy Castle Crypto package - contains lots of code examples to get you started quickly with this encryption stuff. My CaptchaCryptoService is based heavily on the PublicExample.java here.

  • Using Public Key encryption in Java - contains general information about PKI and Java. I found out how to store keypairs into files and load them from my service.
  • JCaptcha and Spring Framework - contains a discussion on how to configure JCaptcha beans with Spring. I ended up building my WordToImage implementation in the Controller's @PostConstruct method, but the information in here was invaluable in figuring out whats available.
at

4 comments:

  1. Unknown12/31/2010 8:10 AM

    This way you make possible to load your page, write down encrypted captcha and recognize it once. Then you can use them multiple times tampering hidden field in the form.

    You should at least use timestamp during encryption to make it safer.

    ReplyDelete
  2. Sujit Pal1/02/2011 10:50 AM

    Hi Pawel, I see what you mean, thanks, good point. With the current implementation, there is nothing to prevent someone from reusing the form to submit multiple data after once recognizing the CAPTCHA. I do use the timestamp to create the initial string (whose MD5 drives the CAPTCHA generated), but what we need for it is to be single use - can't think of a good way to do this ATM without tying it to the session.

    ReplyDelete
  3. jack10/19/2011 5:31 AM

    I think Captcha form is a good option to use on pages for anti spamming.

    ReplyDelete
  4. Sujit Pal10/20/2011 5:53 PM

    Thanks Jack, this is very cool - much less work too :-).

    ReplyDelete

Comments are moderated to prevent spam.