Wie ein Programm Benutzer aus Fleisch und Blut von Bots unterscheiden kann

CAPTCHA – Mensch oder Maschine?

Christoph Amshoff

Jeder kennt sie – die kleinen Bildchen mit verzerrten Buchstaben oder Ziffern auf Webformularen. Die Zeichen sind in ein Formularfeld einzutippen, um eine Registrierung abzuschließen oder bevor man zur gewünschten Seite gelangt. Gedankenlos bis leicht verärgert ist das schnell erledigt und weiter geht’s. Erst wenn man selbst Derartiges implementieren muss, taucht man ein … in die spannende Welt der CAPTCHAs.

In manchen Internet-Anwendungen soll sichergestellt sein, dass nur menschliche Benutzer, aber keine programmierten Bots bestimmte Dienste nutzen können. Dazu gehören zum Beispiel Online-Umfragen, das Registrieren von Accounts oder das Versenden von E-Mails, das Kommentieren von Blogs und Wikis oder auch die Berechnung von Online-Angeboten bei Versicherungen. In all diesen Fällen soll verhindert werden, dass Robots die Dienste missbrauchen – beispielsweise, um Umfragen zu verfälschen, massenhaft Spam-Mails zu versenden bzw. Spam-Links in Foren zu posten oder um Tarifierungsregeln von Versicherungsprodukten der Konkurrenz auszuspähen.

Bots müssen draußen bleiben!

Aus den frühen Zeiten des Internets gibt es einige Beispiele dafür, was Bots anrichten können, wenn sie nicht ausgeschlossen werden. So hatte beispielsweise Yahoo! anfangs damit zu kämpfen, dass Bots tausende freie E-Mail-Konten pro Minute eröffneten, um damit dann Spam-Mails zu versenden. Und als www.slashdot.com im November 1999 eine Online-Umfrage in den USA startete mit der Frage nach der besten Hochschule für Informatik, haben sie zwar die IP-Adresse aller Teilnehmer aufgezeichnet, um Mehrfachstimmen einzelner Teilnehmer zu verhindern, aber es gelang Studenten der Carnegie-Mellon-Universität in Pittsburgh, mit Bots tausendfach für ihre Hochschule zu stimmen. Die Zahlen schnellten in die Höhe, was den Studenten des MIT nicht verborgen blieb – am nächsten Tag schrieben sie ihren eigenen Robot. So wurde aus der Umfrage ein Wettstreit der Bots. MIT siegte mit 21.156 Stimmen vor der Carnegie Mellon mit 21.032; jede andere Hochschule hatte weniger als 1.000 Stimmen [2].

An diesen Beispielen wird deutlich, wie wichtig es sein kann, Bots von Diensten auszuschließen. Aber wie kann man das erreichen? Im Kern geht es darum, programmatisch zu entscheiden, ob der Benutzer des Dienstes ein Mensch oder eine Maschine ist. Dieser Test wird mit CAPTCHA bezeichnet, das ist ein Akronym und steht für Completely Automated Public Turing test to tell Computers and Humans Apart. Dieser Begriff wurde im Jahr 2000 von Wissenschaftlern der Carnegie Mellon University und IBM geprägt [3].

Im Gegensatz zum legendären Turing-Test (siehe Kasten) soll die Entscheidung, ob es sich beim Gegenüber um einen Menschen oder einen Rechner handelt, hier also nicht der Mensch treffen, sondern ein Computer – daher „Completely Automated“.

Dazu wird dem Benutzer eine Aufgabe gestellt, von der man annimmt, dass ein Mensch sie einfach lösen kann, ein Rechner aber nur sehr schwer (das heißt, nicht mit vertretbarem Aufwand und in vernünftiger Zeit). Meistens handelt es sich dabei um Bilder mit Buchstaben- oder Ziffernfolgen, die mit Filtern verzerrt und mit Hintergrundmustern versehen wurden, sodass herkömmliche Texterkennungs-Algorithmen daran scheitern (Abb. 1).

Abb. 1: Eine Auswahl aktueller bildbasierter CAPTCHAs (von links oben nach rechts unten: Google Mail, Microsoft Passport, del.icio.us, Exadel, Paypal und Java Magazin)
Der Turing-Test

—————————————————-

In der Geschichte der Computer wurde schon früh deutlich, dass sie in Teilbereichen bessere Leistungen als Menschen erbringen können, zum Beispiel beim Schachspiel oder bei komplexen numerischen Berechnungen. Das kann man sicherlich noch nicht intelligent nennen. Aber könnte es sein, dass Computer irgendwann intelligenter werden als Menschen? Wie stellt man überhaupt fest, ob eine Maschine denken kann?
Zur experimentellen Beantwortung dieser Fragen hat der englische Logiker und Mathematiker Alan Turing (1912-1954) im Jahr 1950 den nach ihm benannten Turing-Test vorgeschlagen. Dabei führt eine menschliche Versuchsperson über Tastatur und Bildschirm (aber ohne direkten Kontakt) eine Unterhaltung mit zwei Gesprächspartnern, von denen einer ein Mensch und der andere eine Maschine ist. Beide versuchen, den Fragesteller davon zu überzeugen, dass sie der Mensch sind. Kann die Versuchsperson nach einer vorgegebenen Zeit nicht eindeutig entscheiden, welcher von beiden die Maschine ist, hat diese den Test bestanden und kann als „intelligent“ bezeichnet werden.

Der Turing-Test beeinflusste die Entwicklung der Künstlichen Intelligenz nachhaltig, gilt heute jedoch als ungeeignet zur Feststellung von Intelligenz – unter anderem, weil Intelligenz zu sehr an menschliche Kommunikation gekoppelt wird und daher auch nicht jeder Mensch (beispielsweise Kleinkinder) diesen Test bestehen würde. Trotzdem hat bis heute kein Computer den Turing-Test bestanden, wenn es auch sehr interessante Ansätze gab wie z.B. ELIZA von Joseph Weizenbaum.

Testablauf

CAPTCHAs sind als Challenge/Response-Test ausgelegt. Dabei wird dem Benutzer eine Aufgabe (Challenge) präsentiert, die er lösen und das Ergebnis (Response) an die Webanwendung zurückschicken muss. Der Ablauf ist wie folgt:

  1. ol Die Webanwendung erzeugt automatisch und per Zufallsgenerator einen neuen Test, etwa ein neues Bild. Die Lösung (in diesem Fall die für die Bilderzeugung verwendete Zeichenfolge) wird intern gespeichert.
  2. Das Bild wird dem Benutzer zusammen mit einem Eingabefeld auf einer Website präsentiert. Der Benutzer löst das CAPTCHA, füllt das Feld aus und sendet die Seite in einer vorgegebenen Zeit zurück an die Webanwendung.
  3. Die Anwendung vergleicht die Eingaben des Benutzers mit der gespeicherten Vorgabe und gewährt dem Benutzer Eintritt, falls seine Lösung richtig war und in der vorgegebenen Zeit erfolgte. Andernfalls wird sie dem Anwender ein neues CAPTCHA präsentieren.
Eigenschaften von CAPTCHAs

Aus diesem generellen Ablauf wird bereits klar, dass ein CAPTCHA eine Reihe von Eigenschaften haben sollte:

  • Es reicht nicht aus, eine kleine Menge von Aufgaben bereitzustellen, aus der dann zufällig eine ausgewählt wird. Der begrenzte Wertebereich führt häufiger zu Wiederholungen und erleichtert einen Angriff durch Bots. Vielmehr sind die Aufgaben zufällig zu erzeugen, sodass der Wertebereich möglichst umfangreich ist.
  • Es wäre unfair, den Dienst bereits nach dem ersten Fehlversuch zu verweigern. Ein menschlicher Anwender kann Tippfehler machen oder die dargestellte zufällige Aufgabe ist eventuell nur schwer lösbar. Daher sollte im Fehlerfall (oder bereits vor der Eingabe auf explizite Anfrage des Benutzers) wiederholt ein neues CAPTCHA präsentiert werden. Die Anzahl möglicher Fehlversuche ist gegenüber den Sicherheitsanforderungen abzuwägen, in der Regel stellen drei bis fünf Versuche einen guten Kompromiss dar.
  • Um einen Angriff zu erschweren, sollte die für die Antwort verfügbare Zeit nicht zu großzügig bemessen sein. Automatische Texterkennung (OCR) ist rechenintensiv, daher wird eine automatische Lösung erschwert, wenn die Lösung des CAPTCHA innerhalb weniger Minuten erfolgt sein muss. Das Session Timeout (meist 30 Minuten und mehr) ist viel zu lang und reicht daher als Kriterium nicht aus.

Bei Benutzung verzerrter Zeichenfolgen gibt es darüber hinaus weitere Anforderungen:

  • Es ist sicherzustellen, dass die dargestellten Zeichen vom Menschen eindeutig erkannt werden können. Mehrdeutigkeiten etwa zwischen der Ziffer Null und dem Buchstaben O oder der Ziffer Eins und dem Buchstaben L sind auszuschließen.
  • Es muss außerdem gewährleistet sein, dass die dem Benutzer präsentierten Zeichen nicht zufällig ein beleidigendes oder unerwünschtes Wort ergeben. Zum Beispiel wird niemand erfreut sein, wenn er mit den Buchstaben IDIOT konfrontiert wird, und es wäre zumindest seltsam, auf einer Seite etwa der Allianz die Buchstaben huk24 eintippen zu müssen.

Die Lösung für beide Anforderungen besteht darin, dass man entweder einzelne Zeichen ausschließt (beispielsweise Ziffern und Vokale) oder aber auf Basis eines Wörterbuches mit erlaubten Zeichenfolgen arbeitet. Andererseits muss der Vorrat an erlaubten Zeichen oder Wörtern groß genug sein, um Brute-Force-Attacken zu erschweren.

Nicht nur Bilder

Das erste CAPTCHA, das von der Carnegie Mellon University zusammen mit und für Yahoo! entwickelt wurde, beruhte auf der Präsentation eines Bildes mit verschleierten Buchstaben und hieß EZ-Gimpy. Heute hat diese Art von bildbasierten CAPTCHAs die weitaus größte Verbreitung. Dabei macht man sich explizit die Schwächen der OCR zu Nutze, die Schwierigkeiten hat mit gemischten Zeichensätzen und -größen, verzerrten oder sich überlappenden Zeichen, nicht linearen Grundlinien oder störenden Hintergründen.

Allerdings sind bildbasierte CAPTCHAs nicht die einzige Möglichkeit. Grundsätzlich kann jedes schwierige Problem der Künstlichen Intelligenz für ein CAPTCHA verwendet werden, zum Beispiel:

  • die Erkennung der Gemeinsamkeit von mehreren präsentierten Bildern mit Motiven zu einem Thema;
  • das Textverständnis, indem ein Text angezeigt und dazu inhaltliche Fragen gestellt werden;
  • das akustische Verständnis von Sprachausgaben, das heißt, vorgelesenen Wörtern, Buchstaben- oder Zahlenkombinationen.

Diese Varianten sind zwar maschinell schwerer lösbar, haben gegenüber bildbasierten CAPTCHAs jedoch einige Nachteile; sie sind in der Regel aufwendiger zu erzeugen, es gibt teilweise keinen unbegrenzten Wertebereich oder die technischen Voraussetzungen beim Nutzer (Audioausgabe) sind höher.

Allerdings hat auch jedes bildbasierte CAPTCHA einen gravierenden Nachteil: Es ist nicht barrierefrei und kann von Sehbehinderten oder Blinden nicht gelöst werden [4]. Vor allem bei Software für Verwaltungen und Behörden kann die Barrierefreiheit aber Voraussetzung sein. Eine mögliche Lösung besteht darin, das bildbasierte CAPTCHA alternativ vorlesen zu lassen, wie es beispielsweise von Microsoft Passport praktiziert wird.

Besiegt und vereitelt

Inzwischen gibt es eine Reihe von Programmen und Strategien, um CAPTCHAs automatisch zu lösen. Sicher werden viele bildbasierte CAPTCHAs mit steigender Rechengeschwindigkeit und ausgefeilteren OCR-Algorithmen in Zukunft zu knacken sein. Das einfache EZ-Gimpy kann heute mit einer Erfolgsquote von 92 Prozent maschinell gelöst werden [5] und gilt daher nicht mehr als sicher. PWNtcha ist ein Toolkit von grafischen Werkzeugen, das viele der heute üblichen CAPTCHAs mit erstaunlicher Treffsicherheit lösen kann.

Eine mögliche Strategie besteht darin, die CAPTCHAs nicht maschinell, sondern von einem Menschen lösen zu lassen. Dazu delegiert ein Bot die Aufgabe an Menschen, die für die Lösung entweder bezahlt werden oder denen andere Anreize in Aussicht gestellt werden, wie etwa der freie Zugang zu Raubkopien oder einer pornografischen Website. In diesem Fall findet sich meist schnell ein Mensch, der das CAPTCHA – unwissentlich! – für den Spammer löst.

Es ist im Einzelfall zu beurteilen, ob der Aufwand für die automatische Lösung eines CAPTCHAs vom jeweiligen Nutzen aufgewogen wird. In vielen Fällen ist der Schaden, den ein Spammer anrichten kann, eher gering oder kann durch andere organisatorische Maßnahmen begrenzt werden. So machen bildbasierte CAPTCHAs oftmals Sinn, obwohl sie prinzipiell als unsicher gelten.

JCaptcha

Zur Implementierung von CAPTCHAs gibt es eine ganze Reihe von Bibliotheken und Frameworks für verschiedene Sprachen, darunter PHP, Python, Perl und natürlich Java. Im Folgenden soll ein kurzer Blick auf JCaptcha geworfen werden. Dabei handelt es sich um ein Open-Source-Framework (unter der GPL bzw. künftig LGPL) für die Definition und Integration von CAPTCHAs in Java EE-Anwendungen.

JCaptcha kann in der aktuellen Version (1.0-RC3) sowohl die typischen Gimpy-ähnlichen bildbasierten CAPTCHAs erzeugen als auch akustische CAPTCHAs. Einerseits bietet es einige vorkonfigurierte CAPTCHA-Implementierungen, die sehr einfach integriert werden können; andererseits ist JCaptcha aber hochgradig konfigurierbar und erlaubt die Zusammenstellung eines individuellen CAPTCHAs aus einer Vielzahl von Bausteinen. JCaptcha bietet dazu u.a. Komponenten für die Generierung von Zeichenfolgen (zufällig oder basierend auf Wörterbüchern), Fonts und Hintergründen sowie für die Darstellung der Zeichen auf dem Hintergrund unter Verwendung von Farben, Dopplungen oder Verzerrungen.

Für die relevanten Komponenten stellt JCaptcha Interfaces und vielfach abstrakte Basisklassen bereit, sodass eigene Erweiterungen einfach möglich sind. Die Elemente werden über Dependency Injection zusammengefügt, was sehr einfach mithilfe entsprechender Frameworks wie Spring erfolgen kann. Außerdem gibt es noch Module für die Integration mit dem Web-Framework Struts, dem Acegi Security Framework und dem Roller Blog Server.

Beispiel-Implementierung

Im Folgenden sollen die Grundzüge einer Integration von JCaptcha in eine Java-Webanwendung gezeigt werden. Um das Beispiel möglichst einfach zu halten, verwenden wir dabei die Standard-Implementierung DefaultManageableImageCaptchaService, die ein einfaches Gimpy Challenge verwendet. Dieser Service implementiert das zentrale Interface CaptchaService bzw. dessen Erweiterung, ImageCaptchaService, welche die in Abbildung 2 dargestellten Methoden bereitstellen.

Abb. 2: Methoden der CaptchaService Interfaces

Mittels getQuestionForID wird die Frage zum CAPTCHA besorgt, die dem Benutzer in der Webform angezeigt werden kann. getChallengeForID liefert das CAPTCHA selbst, für unsere Service-Implementierung ist das ein BufferedImage -Objekt (ImageCaptchaService stellt die Wrapper-Methoden getImageChallengeForId bereit, welche die Typumwandlung übernehmen). Beiden Methoden wird ein so genanntes Ticket übergeben, mit dem das CAPTCHA eindeutig identifiziert wird (in der Regel die Session-ID), und optional ein Locale. Über die Methode validateResponseForID kann schließlich geprüft werden, ob die Benutzereingabe, d.h. die Lösung des CAPTCHA, korrekt ist. Und das ist auch schon alles, was wir als Schnittstelle zu JCaptcha benötigen!

Wie integrieren wir das CAPTCHA nun in eine Webanwendung? Abbildung 3 zeigt die beteiligten Komponenten bzw. Klassen und deren Interaktion. Das Prinzip ist einfach: Neben dem Servlet für unsere Webanwendung gibt es ein zweites Servlet, das ein CAPTCHA erzeugt und an den Browser zurückliefert. Dazu benutzt es die erwähnte JCaptcha-Klasse DefaultManageableImageCaptchaService. Der Zugriff darauf erfolgt über einen Service nach dem Singleton Pattern.

Abb. 3: Schematische Darstellung der Interaktionen bei Verwendung eines CAPTCHA

Im Einzelnen: Der Browser fordert die Registrierungs-Seite an (1), die vom Servlet erzeugt und zurückgeliefert wird (2). Darin befindet sich ein Image Tag der Form <img src="img.captcha">, dessen URL Pattern *.captcha in der web.xml auf das Captcha Servlet gemappt ist (3). Dessen doGet-Methode ruft nun getChallengeForId auf der CaptchaService-Implementierung (über das Singleton) auf, um ein neues CAPTCHA-Image zu erhalten (4). Dieses Image wird in der HttpServletResponse verpackt und an den Browser zurückgeschickt (5), der es dem Benutzer als Bestandteil der Seite darstellt.

Wenn der Anwender nun die Felder ausfüllt und den REGISTER-Button betätigt, wird in Struts zum Beispiel die zugehörige Action (VerifyAction) ausgeführt (6). Diese kann über einen Aufruf von validateResponseForID prüfen, ob die eingegebene Zeichenfolge korrekt ist (7) und entweder auf die Folgeseite verweisen oder die gleiche Seite mit einem neuen CAPTCHA erneut anzeigen bzw. zu einer Fehlerseite verzweigen (falls die zulässige Anzahl an Fehlversuchen erreicht ist).

Listing 1 zeigt das CaptchaServiceSingleton, das statischen Zugriff auf die benutzte ImageCaptchaService-Implementierung bietet. Anstatt sie direkt zu erzeugen, könnte alternativ die gewünschte Implementierung zum Beispiel per Spring konfiguriert und hier geladen werden.

Listing 1
----------------------------------------------
public class CaptchaServiceSingleton {  
    private static ImageCaptchaService instance = new 
                     DefaultManageableImageCaptchaService();
    
    public static ImageCaptchaService getInstance(){
        return instance;
    }
}

Listing 2 enthält die Hilfsmethode getCaptchaChallenge. Sie ruft CaptchaServiceSingleton.getInstance().getImageChallengeForID(), um ein neues CAPTCHA zu erzeugen, und transformiert das erhaltene Image in ein JPEG. Das generierte CAPTCHA wird von JCaptcha an das übergebene Token gebunden, das daher später zur Verifizierung der Benutzereingabe wieder mitzugeben ist. Es bietet sich an, hierzu die Session-ID zu verwenden.

Dies ist in der zentralen doGet-Methode des CaptchaServlet zu sehen, die die Session-ID und das Locale aus dem Request extrahiert und damit getCaptchaChallenge aufruft. Anschließend wird die HttpServletResponse erzeugt. Wir schalten das Caching aus, damit bei jedem Laden der Seite ein neues Image generiert wird.

Listing 2
--------------------------------------
public class CaptchaServlet extends HttpServlet {
    ...

    private synchronized byte[] getCaptchaChallenge(String token, Locale loc) {
        byte[] captchaChallenge = null;

        try {
            // create the captcha challenge
            BufferedImage challenge = CaptchaServiceSingleton.getInstance().
                getImageChallengeForID(token, loc);

            // transform image data into jpeg byte array
            ByteArrayOutputStream jpegOutputStream = new ByteArrayOutputStream();
            JPEGImageEncoder jpegEncoder =
                JPEGCodec.createJPEGEncoder(jpegOutputStream);
            jpegEncoder.encode(challenge);
            captchaChallenge = jpegOutputStream.toByteArray();
        } 
        catch (IOException e) {
        } 
        catch (CaptchaServiceException e) {
        }

        return captchaChallenge;
    }        

    protected void doGet(HttpServletRequest request, HttpServletResponse response) 
        throws ServletException, IOException {

        // use the session id as token and the request's locale
        String token = request.getSession().getId();
        Locale loc = request.getLocale();

        // get captcha challenge as JPEG
        byte[] captchaAsJpeg = getCaptchaChallenge(token, loc);

        // if not available, send status code 404 (resource not available)
        if (captchaAsJpeg == null) {
            response.sendError(HttpServletResponse.SC_NOT_FOUND);
            return;
        } 

        // return a response containing the jpeg image
        // (specify to not use a cache, content expires immediately)
        response.setHeader("Cache-Control", "no-store");
        response.setHeader("Pragma", "no-cache");
        response.setDateHeader("Expires", 0);
        response.setContentType("image/jpeg");
        ServletOutputStream responseOutputStream = response.getOutputStream();
        responseOutputStream.write(captchaAsJpeg);
        responseOutputStream.flush();
        responseOutputStream.close();
    }
}

Das CaptchaServlet muss jetzt noch in der web.xml eingetragen und sein Mapping konfiguriert werden (Listing 3). Dabei wird es an das URL Pattern *.captcha gebunden, sodass ein Tag der Form Loading image... zum Aufruf des Servlets führt.

Listing 3
--------------------------------------

    ...
    jcaptchaJCaptchamy.package.CaptchaServlet1
    ...
    jcaptcha*.captcha 
    ...

Nun fehlt lediglich noch die Prüfung, ob die Eingabe des Anwenders für das CAPTCHA korrekt ist. Diese Funktionalität ist Teil der jeweiligen Action und kann über Aufruf der Methode validateResponseForID sehr einfach implementiert werden, wobei wieder das Token (d.h. die Session-ID) anzugeben ist (Listing 4). Damit ist unser Beispiel komplett!

Listing 4
--------------------------------------
public boolean verifyCaptchaAnswer(String token, String userInput) {
    Boolean result = Boolean.FALSE;
    try {
        result = CaptchaServiceSingleton.getInstance().
            validateResponseForID(token, userInput);
    } catch (CaptchaServiceException e) {
        // id is invalid -- should not happen!
    }
    return result.booleanValue();
}
Fazit

Mit wenig Aufwand haben wir ein einfaches CAPTCHA in eine Webanwendung integriert. Darauf kann man nun aufbauen und weitere Anforderungen umsetzen, wie zum Beispiel die individuelle Konfiguration der dargestellten Worte oder Zeichenfolgen (zufällig aus vorgegebenen Zeichenvorräten oder Wörterbüchern), der Farben, Hintergründe, Zeichensätze, Verformungen etc. Abbildung 4 zeigt ein Beispiel für eine spezielle Konfiguration eines CaptchaService mit den beteiligten Interfaces, den gewählten Implementierungsklassen und ihren Abhängigkeiten. Diese Objekthierarchie lässt sich mit Dependency Injection (beispielsweise Spring) sehr einfach erzeugen.

Abb. 4: Beispiel zur Konfiguration eines individuellen JCaptcha Service

JCaptcha bietet vielfältige Möglichkeiten und ist aufgrund seiner sauberen Architektur leicht konfigurierbar und einfach erweiterbar. Da Image-Erzeugung generell ressourcenintensiv ist, schenkt JCaptcha der Performance besondere Aufmerksamkeit und liefert entsprechende Testfälle mit.
Es wird spannend sein, wie sich die Erfolgsquoten bei der maschinellen Lösung und die Verbreitung entsprechender Bots entwickeln werden. Sicher bleiben uns die bildbasierten CAPTCHAs für weniger kritische Anwendungsfälle aber noch lange erhalten.

Christoph Amshoff arbeitet seit neun Jahren mit Java, derzeit als Entwickler, Architekt und technischer Projektleiter im Bereich Front-Office-Systeme bei der FJA Feilmeier & Junker GmbH in Köln. Sein Interesse gilt vor allem Usability-Aspekten, Java EE und Webanwendungen.

Geschrieben von
Christoph Amshoff
Kommentare

Schreibe einen Kommentar

Deine E-Mail-Adresse wird nicht veröffentlicht.