Advanced searching via Z-Algorithm

I’m actually learning some stuff related to algorithms on sequences. The naive search for a pattern in a long string is of course very slow and comes with a lot of unintelligent compares. The Z-Algorithm improves the searching by preprocessing the pattern.

Naive searching

A simple search algorithm written in java may look like

public void search (String needle, String haystack)
	for (int off = 0; off < haystack.length () - needle.length () + 1; off++)
		boolean found = true;
		for (int p = 0; p < needle.length (); p++)
			if (needle.charAt (p) != haystack.charAt (off + p))
				found = false;
		if (found) System.out.println ("Fount pattern at position " + off);

This code reliably finds any existence of needle in haystack in , with length of needle and length of haystack. That screams for improvements ;)


The first algorithm that I want to present in this series is called Z-Algorithm. First of all we need some definitions.

Definition 1: In the following we denote as the substring of beginning at position and ending at position . We can also leave one of the limits clear, so that is the substring and means .

Definition 2: So is the length of the longest prefix of the suffix that is also prefix of itself. To abbreviate is further on mentioned as .

Definition 3: The set for a is called Z-Box at position .

Definition 4: is the set of limits of all Z-Box’es that start at the left-handed side of . Consider .

Definition 5: If and , defines the rightest Z-Box that starts before respectively at position . Consider .


In the following will denote the actual position we are looking for, and describe the current respectively last found of a Z-Box. First of all we set the values and to zero because we haven’t found any Z-Box yet. of our text is according to Definition 2 the length of the longest prefix of that is also prefix of itself. If we found a first Z-Box and update the limits to and .

Now we have to run through the word , so with defines the length of .

Case 1: Let’s assume position is outside of the last found Z-Box or we didn’t find any Z-Box yet (). We find by comparing the prefixes of and . If we’ve found a new Z-Box and need to update the limits to and .

Case 2: If the current position is inside of a current Z-Box () we try to find the equivalent position at the beginning of . The position we are searching for is steps off the beginning of (we are steps behind and has the same prefix as ). Case 2a: If we don’t break out of the current Z-Box by creating another Z-Box with the length of the box at position (, so position is not behind position ), we can simply apply this Z-Box to the current position and . Case 2b: Otherwise, if we would leave the actual Z-Box () we have to recheck the prefix conditions of and . We know that equals , so we only have to find the length of the longest prefix of that equals the prefix of . Now we can apply the new Z-Box such that and of course we update the Z-Box limits to and .

If we reached the end of all Z-Boxes are found in .

Pseudo code

l = r = 0
Z[2] = prefix (S, S[2 ..]).length
if Z[2] > 0 then
	l = 2
	r = 2 + Z[2] - 1

for i = 3..|S| do
	if i > r then 										'(case 1)'
		Z[i] = prefix (S, S[i ..]).length
		if Z[i] > 0 then
			l = i
			r = i + Z[i] - 1

	else 												'(case 2)'
		k = i - l + 1
		if Z[k] < r - i + 1 then 						'(case 2a)'
			Z[i] = Z[k]

		else											'(case 2b)'
			p = prefix (S[r - i + 2 ..], S[r + 1 ..]).length
			Z[i] = r - i + 1 + p
			l = i
			r = i + Z[i] - 1


Let me demonstrate the algorithm with a small example. Let’s take the word . First we start with and at position 2. is the length of the shared prefix of () and (). Easy to see the prefix is with a length of 1. So , and . At the beginning of our for-loop the program’s status is:


At the first round in the loop , so because . So we meet case 1 and have to find the length of the prefix of () and (). Of course it’s zero, nothing to do.


Next round, we’re at position 4 and again (case 1). So we have to compare and . The longest prefix of both words is with a length of 2. So we start a new Z-Box at 4 with a size of 2, so and .


With and we reach case 2 for the first time. so our similar position at the beginning of is position 2. and so we are in case 2b and have to find the shared prefix of () and (). It’s , so and . and .


Next round brings us , therefor we’re in case 2. Equivalent position is again , but now and we’re in case 2a and can just set .


The last round we have to process is , case 2. Equivalent position is and , so case 2a and .


That’s it. The Z-Box’es we’ve found are visualized in the image.


To search for a pattern in a text just calculate the Z-Boxes of with . These calculations are done in . For any : If means is prefix of , so is found at position in .


Of course I’m providing an implementation, see attachment.

Download: Java: (Please take a look at the man-page. Browse bugs and feature requests.)

SSH escape sequences

Such as telnet the SSH protocol also has a control character, it’s the tilde (~).

If you for example want to kill a hanging SSH session just type ~. . With ~^Z you can suspend a running session and get back to your local machine. To reactivate it just type fg (yes, the SSH session is also just a job). All supported escape sequences will be listed with ~? :

me@remote ~ % ~?
Supported escape sequences:
  ~.  - terminate connection (and any multiplexed sessions)
  ~B  - send a BREAK to the remote system
  ~C  - open a command line
  ~R  - Request rekey (SSH protocol 2 only)
  ~^Z - suspend ssh
  ~#  - list forwarded connections
  ~&  - background ssh (when waiting for connections to terminate)
  ~?  - this message
  ~~  - send the escape character by typing it twice
(Note that escapes are only recognized immediately after newline.)

All sequences are of course only understood after a newline ;)

First HTML5 experiences

Although I have too much to do it’s in the nick of time to try some stuff with HTML5.

You should all have heard about HTML5, next generation of web ;) I still saw a lot of new features, some are still not supported in many browsers but all in all I’m looking forward.

Here I played a little bit with the canvas stuff and created a binary clock:

Wasn’t that difficult, just created an HTML element of type canvas with enough space in it to draw the clock:

<canvas id="clock" width="250" height="100"></canvas>

and via JavaScript I draw the clock in it:

/* JS binary clock by Martin Scharm <> */
function init()
function draw (ctx, x, y, stroke)
	ctx.arc(x, y, 9, 0, Math.PI*2,true);
	if (stroke) ctx.stroke();
	else ctx.fill ();
function clock ()
	var canvas = document.getElementById("clock");  
	if (canvas.getContext)
		var offset = 60;
		var ctx = canvas.getContext("2d");;
		var now = new Date();
		var sec = now.getSeconds();  
		var min = now.getMinutes(); 
		var hr  = now.getHours(); 
		for (var i = 0; i < 3; i++)
			for (var x = 0; x < 2; x++)
				for (var y = 0; y < 3; y++)
					draw (ctx, i*offset + x*20 + 20, y*20 + 20, true);
				for (var x = 1; x < 3; x++)
					for (var y = 2; y < 4; y++)
						ctx.arc(x * offset, y * 20, 4, 0, Math.PI*2,true);
						ctx.fill ();
					for (var x = 0; x < 2; x++)
						for (var y = 0; y < 3; y++)
							if (sec & Math.pow (2, (1 - x) * 3 + 2 - y)) draw (ctx, 2*offset + x*20 + 20, y*20 + 20, false);
							if (min & Math.pow (2, (1 - x) * 3 + 2 - y)) draw (ctx, 1*offset + x*20 + 20, y*20 + 20, false);
							if (hr & Math.pow (2, (1 - x) * 3 + 2 - y)) draw (ctx, x*20 + 20, y*20 + 20, false);
						ctx.fillText(hr + ":" + min + ":" + sec, 70, 80);

After wards just called init (); , that calls clock(); once a second to draw the clock. Please tell me whether it works in your browser ;)

If anybody is interested, here is the code: html5_clock. If you also want to deal with it, Mozilla has a good tutorial.

I hope this new age of web will delete all the flash trash out there!

Download: Javascript: html5_clock.js (Please take a look at the man-page. Browse bugs and feature requests.)

Umlauts on English keyboards

Micha is just sitting next to me, writing a new blog post. He’s writing in German with an English keyboard, so he has to encode umlauts like ä with an &auml; . I can not watch any longer, here is the trick.

Still blogged about it, you can create such additional keys with Xmodmap. So choose a key, get its key code for example with xbindkeys -k and create a file $HOME/.Xmodmap with the following syntax:

keycode XXX = YYY

XXX ist the code of your key and YYY is that what should happen. For example:

keycode  137 = adiaeresis Adiaeresis
keycode  139 = udiaeresis Udiaeresis
keycode  141 = odiaeresis Odiaeresis 
keycode  143 = ssharp ssharp

That gives you an ä/Ä on the key with code 137 and so on. To let the file take effect just run xmodmap $HOME/.Xmodmap . Btw xmodmap -pke will give you the actual running keymap. So Micha, no need to type to much ;)

Twitter disabled Basic Authentication

Some of you may have recognized that twitter has disabled the so called Basic Authentication. So my previous twitter-tools don’t work anymore. But don’t bury your head in the sand, here are the newer versions.

Basic Authentication means you send your account information (username/password) unencrypted with your query (status update/timeline request/…) to twitter. Of course this method isn’t a nice way, so twitter disabled this method of authentication.

But the new methods of API calls are more complicated (called “OAuthcalypse”) and I really don’t like them. But whoever listens to me?

If you now want to interact with the twitter API, you have to register your tool as new twitter tool. Don’t ask me why, but you have to choose an unique name (all over the twitter world) for your application and get some random strings. For example for a Perl script you need the ones called Consumer key and Consumer secret.

If you want to interact with twitter, you have to do the following:

<li>send the combination of <em>Consumer key</em> and <em>Consumer secret</em> to the server
<li>receive an URL from the server where the user itself can find a pin code (when (s)he is logged into twitter)
<li>send this code to the server again and the user is verified
<li>receive some more authentication information from the server, store it for the next time, so the user don't have to authenticate again

Very annoying method, but there is no alternative method and at least your account is more save against hijacker.

By the way I found a Perl module called Net::Twitter that helps a lot.

Here is my snippet to solve this authentication stuff:

use Net::Twitter;

my $CRED_FILE = "somefile";

sub restore_cred {#read creds from $CRED_FILE}
sub save_cred {#write creds to $CRED_FILE}

my $nt = Net::Twitter->new(traits => ['API::REST', 'OAuth'], consumer_key => "KEY", consumer_secret => "SECRET",);
my ($access_token, $access_token_secret) = restore_cred();
if ($access_token && $access_token_secret)

unless ( $nt->authorized )
	print "Authorize this app at ", $nt->get_authorization_url, " and enter the PIN: ";
	chomp (my $pin = <stdin>);
	my($access_token, $access_token_secret, $user_id, $screen_name) = $nt->request_access_token(verifier => $pin);
	if (save_cred($access_token, $access_token_secret))
	{ print "successfull enabled this app! credentials are stored in: " . $CRED_FILE . "\\n" }
	{ die "failed\\n"; }
if ($nt->update({ status => $status }))

Ok, you see it’s not impossible to solve this problem. And there is another advantage, with these two scripts I don’t have to provide my username/passwort any more.

Here is the script to tweet from command line and this script dumps the actual news to the console.

To use my tools just download them to your machine, rename them as you want and then just run it:

  • To tweet something call with your status message as argument.
  • To get latest informations from the people you are following just call with an optional argument defining the maximal number of messages you want to see.

For the first time you’ll see a link where you’ll get your pin (open the link with your browser), after wards the tools will store your credentials in [toolname].credentials . Just try it, won’t (hopefully) break anything :P

Download: Perl: (tweet from command line) Perl: (get latest news) (Please take a look at the man-page. Browse bugs and feature requests.)

Userinteraction with Perl

Til today I scripted the user interactions in Perl by my own, but now I’ve learned there is an easier way to interact with the user.

The old way was something like this:

my $input = "";
while ($input ne "yes")
    print "say yes: ";
    chomp ($input = <>); 
print "thanks\\n";

That does what I want it to do, but if you want more complex operations it’s somewhat difficult to hack it. If you want the user to choose something from a menu or to give you an integer, you have to write lots of code and you have to verify the input by your own. There is a Perl module called IO::Prompt to simplify this ( aptitude install libio-prompt-perl ). For example to get an integer from the user you can use this part of code:

use IO::Prompt;
my $integer = prompt ("give me your integer: ", -integer);

The function prompt will print the string and waits for an input. When the user gives an input it will chomp it and verifies the input by your condition (here it tests whether the input is an integer). If the test fails it prints an error and gives the user a new chance to type a correct value until the conditions are complied. So you can be sure that the returned value is definitely an integer! Of course you can tell prompt to check for more difficult conditions, something like a regular expression. For example to get a hexadecimal value you can use this:

use IO::Prompt;
my $hex = prompt ("give me a hex: ",
			 -req => {"Need a *hexadecimal* value!: " => qr/^[0-9A-F]+$/i}
print "decimal value: " . hex($hex) . "\\n";

With -req this function expects a hash, it’s entries must match to the input or it will print the corresponding key as error message. As values you can pass functions that should return true if the input is correct, or a regular expression that must pattern match or something like this (see IO::Prompt). Here I’m using a regular expression that matches to hexadecimal input and if the user enters a correct input it’s converted to base 10. An example run might look like this:

/tmp % ./
give me a hex: NOHEX
Need a *hexadecimal* value!: w00t
Need a *hexadecimal* value!: A6
decimal value: 166

Even menus are simple to realize. For example:

use IO::Prompt;
my $day = prompt ('Whats your favorite day?',
				-menu =>
print "your choice was: " . $day . "\\n";

If you run this program your menu may look like:

/tmp % ./
Whats your favorite day?
     a. Monday
     b. Tuesday
     c. Wednesday
     d. Thursday
     e. Friday
     f. Saturday
     g. Sunday

> f
your choice was: Saturday

The freaks among you will try more complex menus. You are allowed to use hashes in hashes in arrays for your menu and prompt will lead the user through your options. You should know where to find further information about this :P

Show all tags in WP when creating new post

I was annoyed that WordPress by default just shows 45 most used tags on the Add New Post page and found a solution to display all Tags.

After I create a new post in this blog I usually tag it. WordPress provides a very helpful widget that displays the most used tags, but I want to see all tags that I’ve created in the past. Some research through the net doesn’t bring solutions, so I had to walk through the code on my own. Wasn’t very difficult, it was clear that the tags come with Ajax to the site, and I found the code in wordpress/wp-admin/admin-ajax.php on line 616 (WordPress 3.0.1) or wordpress/wp-admin/includes/ajax-actions.php on line 666 (WordPress 3.6, see comments):

$tags = get_terms( $taxonomy, array( 'number' => 45, 'orderby' => 'count', 'order' => 'DESC' ) );

That is what you’ll carry by JavaScript. To get more tags just change this line to something like this:

$tags = get_terms( $taxonomy, array( 'number' => 999, 'orderby' => 'count', 'order' => 'DESC' ) );

You can also edit wordpress/wp-admin/includes/meta-boxes.php , original is:

<p class="hide-if-no-js"><a href="#titlediv" class="tagcloud-link" id="link-<?php echo $tax_name; ?>">< ?php echo $taxonomy->labels->choose_from_most_used; ?></a></p>

If you change it to:

<p class="hide-if-no-js"><a href="#titlediv" class="tagcloud-link" id="link-<?php echo $tax_name; ?>">< ?php echo $taxonomy->labels->all_items; ?></a></p>

the link to get the tags will be called All Tags, not Choose from the most used tags.

I hope this could help some of you. With the next WordPress update these changes will be lost, but you should be able to do it again and maybe I’ll blog about it ;)

Update for WordPress 3.6

You need to edit:

  • wordpress/wp-admin/includes/ajax-actions.php line 666
  • wordpress/wp-admin/includes/meta-boxes.php

(thanks to Gustavo Barreto)

Update for WordPress 3.8.1

You need to edit:

  • wordpress/wp-admin/includes/ajax-actions.php line 691
  • wordpress/wp-admin/includes/meta-boxes.php line 381

(thanks to August for reminder)

Update for WordPress 3.9.1

You need to edit:

  • wordpress/wp-admin/includes/ajax-actions.php line 702
  • wordpress/wp-admin/includes/meta-boxes.php line 410

Update for WordPress 4.1

You need to edit:

  • wordpress/wp-admin/includes/ajax-actions.php line 836
  • wordpress/wp-admin/includes/meta-boxes.php line 431

Increasing anonymity with Tor

Terrified I had to notice, that some of you don’t know Tor!? Here is a little intro, so you don’t have to die stupid.

When you for example request a website, the server that provides this site knows your IP address, with this address it’s able to detect your real location. It also get to know your UserAgent and a lot of other things like that. So the other site of your connection knows quite a lot of you, which system you’re working on, which browser you use, where (which website) do you come from and so on.. But is it essential to let the world know so much about you!? Of course not! By the way, think about the security issue ;)

So what to do!? One option is not to use the internet, only connect to servers you trust. But the better solution is to use Tor! Tor is a software to get anonymous network connection. It works like a big proxy. All around the world are Tor-server. When you try to connect to a webserver you won’t do it directly, but you will connect to a Tor access-node, this node is connecting further nodes, until an exit-node is reached. This exit-node will now send your initial request to the webserver, wait for a response and send this response on a way through the Tor-network back to your machine. The connections between the Tor nodes are encrypted and randomly chosen, so nobody is able to find the way your requests took through the Tor nodes. This process is called onion routing and is much more complicated than I described here, but it’s to much to talk about in detail.

Setting up Tor

The setup is very easy. Just add the Tor repositories to your sources.list:

# for more actual updates (always be careful with experimental) use:
deb experimental-DISTRIBUTION main

I for example added the following to my /etc/apt/sources.list.d/3rdparty.list :

# tor
deb sid main
deb experimental-sid main

After that add the GPG-Key of this repository:

gpg --keyserver --recv 886DDD89
gpg --export A3C4F0F979CAA22CDBA8F512EE8CBC9E886DDD89 | sudo apt-key add -

And install the software:

aptitude update
aptitude install tor tor-geoipdb

If you now start Tor with /etc/init.d/tor start it is listening on . You also need a small proxy like privoxy:

aptitude install privoxy

It’s configuration is very easy, just tell privoxy to send the packages to Tor with the following in /etc/privoxy/config :

forward-socks4a / localhost:9050 .

The rest of this file should be configured correctly.

That’s it! Everything that now reaches your proxy is finding its anonymous way through the Tor-network.

Configuring client software

Now you have to force your software to use the proxy. The most important client software is probably your browser. For example in firefox (or iceweasel) you find the settings in Edit->Preferences->Advanced->Network->Settings and check Manual proxy configuration. Your proxy is (or rather localhost) on port 8118 . Now your more anonymous, just ask a website where you come from. (at the moment I’m using an exit node from Russian Federation and the webserver recognizes me as Windows 7 user with Firefox 3.6 while using a sidux and iceweasel 3.5.11). Here you can verify that you Tor configuration is working. There are also some AddOns for firefox, that makes live easier. For example Torbutton or FoxyProxy. With it you can enable or disable the usage of Tor with a single mouse click.

But Tor is not only designed for browsers. You can configure a lot of software to go through Tor, for example gajim in Edit->Accounts->Your Account->Connection, or in opera with Settings->Preferences->Advanced->Network->Proxy Servers…. Nearly every thing that is able to connect the internet may be able to use your proxy. You can also activate the usage of your proxy by default by including the following line in your .bashrc or .zshrc or what ever:

export HTTP_PROXY=

Problems and imperfections

You have to know that the encryption between the Tor nodes doesn’t mean your request is fully encrypted. The connection between exit-node and webserver isn’t encrypted by default. This part of your connection is just encrypted if your request is encrypted, for example if you use SSL (https) in your browser. Otherwise the exit-node can read your data. So it is possible that bad people or evil governments may provide untold thousands of exit-nodes, so they can read a lot of traffic of people that want to be anonymous! Another thing you may dislike is the speed. Your traffic is passing a lot of additional nodes, so of course your speed decreases. So you have to balance between anonymity and speed. I think the slow down isn’t that hard, it’s acceptable for me. Choose by your own…


Tor is a very nice project, for further reading you may take a look on the projects website. If you hold a server that is contactable for the public you should think about providing an onion node on it! It’s very easy, but you should know about legal stuff.

Cracked next Captcha

Ok, when Micha saw my tiny hack he changed his implementation (as promised) and told me I’m not able to hack it again… Micha, your captcha failed again :P

Lets have another look to his code:

	Lösen Sie bitte die folgende Aufgabe (ggf. <em>x</em> bestimmen) <br />

		<img src=";tex=2%5E%7B%202%20%7D" alt="2^{ 2 }" title="2^{ 2 }"/>
	<p><input name="captvalue" id="captvalue" value="" size="40" tabindex="4" type="text"/></p>
	<input name="captcha" value="kwCci5YUFw27oJWwxYc6JuuDuvhMd+K95V1TYf3vwJrZqZf2fJCdABUx/4pxMb08kkV/" type="hidden"/>

First of all he renamed the fields, so of course my last attack will fail :P The next problem is, that the hash for a 7 isn’t the hash for another 7 of a different calculation. Maybe he’s using the arithmetic problem or the time or other things for his hash calculation. So if we don’t know how his calculation for the hash is, the last attack is senseless… Btw he told me that he’s using encryption. If you’re bored, try to break it, it’s to much for me. But Micha bets three beer that I’m not able. So no chance to quit!

In my last post I had another idea to crack the captcha: Parse the formula. Ok, I wrote about parsing the URI to the external server that produces the picture, of course it’s much easier to parse the title - or alt -tag of the image! These fields are human readable to get the site handicapped accessible. Of course worthy that he provides this fields! So, after some reloads I had a small idea with what kind of problems I have to deal with:

Simple calculations
something like: , just calculate the solution
like , first convert the formula before calculating the solution
for example , first rewrite the sum-symbol, than calculate the solution

That’s the theory, the code is this time a little bit longer:

// ==UserScript==
// @name           micha-captcha-hack-v2
// @namespace      binfalse
// @description    solve michas captchas without human thinking ;)
// @include*
// ==/UserScript==

var capt_field = document.getElementsByName ("captvalue");
if (capt_field)
	//search for the image
	var imgs = document.getElementsByTagName ("img");
	var img = 0;
	for (var i = 0; i < imgs.length; i++)
		if (imgs[i].src && imgs[i].src.indexOf ("") >= 0)
			img = imgs[i];
	if (img != 0)
		var problem = img.title;
		// parse simple math operations
		problem = problem.replace (/\\cos\s*0/, " 1 ");
		problem = problem.replace ("\\div", " / ");
		problem = problem.replace ("\\cdot", " * ");
		problem = problem.replace (/\\sin\s*\\frac\s*{\s*\\pi\s*}\s*{\s*2\s*}/, " 1 ");
		problem = problem.replace (/\\frac\s*{(.+?)}{(.+?)}/, "($1) / ($2)");
		problem = problem.replace (/\\sqrt\s*{(.+?)}/, " Math.sqrt ($1) ");
		problem = problem.replace (/([^m ]+)\s*\^\s*{(.+?)}/, " Math.pow ($1, $2) ");
		if (problem.indexOf ("=") < 0)
			//simpel problem, just calc..
			capt_field[0].value = eval (problem);
		else if (problem.indexOf ("sum") < 0)
			//converting -> very simple scripted ;)
			var tmp = problem.indexOf ("=");
			var left = problem.substr (0, tmp);
			var right = problem.substr (tmp + 1);
			if (right.indexOf ('x') >= 0)
				tmp = right;
				right = left;
				left = tmp;
			// lhs is x -> convert every other shit to rhs ;)
			// kill adds
			var leftpieces = left.split ('+');
			for (var i = 0; i < leftpieces.length; i++)
				if (leftpieces[i].indexOf ('x') < 0)
					right = right + " - " + leftpieces[i];
					left = leftpieces[i];
			// kill subs
			var leftpieces = left.split ('-');
			for (var i = 0; i < leftpieces.length; i++)
				if (leftpieces[i].indexOf ('x') < 0)
					right = right + " + " + leftpieces[i];
					left = leftpieces[i];
			// kill mults
			var leftpieces = left.split ('*');
			for (var i = 0; i < leftpieces.length; i++)
				if (leftpieces[i].indexOf ('x') < 0)
					right = "(" + right + ") / " + leftpieces[i];
					left = leftpieces[i];
			// kill divs
			var leftpieces = left.split ('/');
			for (var i = 0; i < leftpieces.length; i++)
				if (leftpieces[i].indexOf ('x') < 0)
					right = "(" + right + ") * " + leftpieces[i];
					left = leftpieces[i];
			capt_field[0] = eval (right);
			eval (problem.replace (/^.+sum.+?{(.+?)}.+{(.+?)}(.+)$/, "$2;to=$1;s='$3';"));
			var longprob = "";
			for (var i = n; i < to; i++)
				longprob = longprob + " " + s.replace ('n', i) + " +";
			longprob += 0;
			capt_field[0].value = eval (longprob);
		capt_field[0].value = "uuups, no img found!?";
		capt_field[0].style.background = "red";

As you can see, it’s a little bit tricky and just works for some mathematical formulas that are of interest. If he combines the converting problem with brackets or something like that, this code fails.. But the algorithm is easy to modify for such changes ;)

But respect, to crack my captcha you don’t need that intelligence, it’s feasible in much less code. I hope he doesn’t rewrite his plugin again, don’t want to calculate that stuff by brain…

Cracked a captcha

Micha just implemented an own Captcha-Plugin for wordpress, I just cracked it some minutes later ;)

This version is deprecated, see Cracked next Captcha…

Micha was annoyed of his previous Captcha-Plugin, neither valid nor beautiful, so he decided to write his own tool for killing bots.

When I saw his new captchas I was wondering wheter he will get further comments. His captchas ask for solution of mathematical problems like or or .. Who the hell wants to calculate that stuff!? Me not! ;)

So I developed a little userscript that solves this problem. When you take a look to the source code of his website you’ll find something like this:

Lösen Sie bitte die folgende Aufgabe (ggf. <em>x</em> bestimmen) <br />

		<img src=";tex=228%20%5Cdiv%2019" alt="228 \div 19" title="228 \div 19"/>
	<p><input name="captvalue" id="captvalue" value="" size="40" tabindex="4" type="text"/></p>
	<input name="sercret" value="c9679a3b8ab5151bdf143c43091e59a757cb15ce" type="hidden"/>

So you see, there is an image created by an external server, an input field where you can put the solution and an input field of the type hidden with a crypt value (seems like a hash^^). The most of you will see several ways to hack this:

  1. Parse the string of the image like the external server does to create the -image. So you’ll get an arithmetic problem, easy to solve.
  2. Find out what kind of hash is in the value of the secret hidden input-field and try to find a number that matches that hash, maybe via brute force.
  3. Solve one captcha and fake the rest ;)

Of course the last solution is the easiest one. So I solved on captcha, solution was 7 and the secret key was 9ee4251f80923e6239ae66ab50a357daa6039f04 , hack done!

The development of the userscript was more than simple:

// ==UserScript==
// @name           micha-captcha-hack
// @namespace      binfalse
// @description    solve michas captchas without thinking ;)
// @include*
// ==/UserScript==

var hidden_field = document.getElementsByName ("sercret");
var capt_field = document.getElementsByName ("captvalue");
if (hidden_field && capt_field)
	capt_field[0].value = 7;
	hidden_field[0].value = '9ee4251f80923e6239ae66ab50a357daa6039f04';

I think that this script won’t work for a long time, so there is no download available ;) If you want to use it, copy&paste, you know.

Ähm, before anybody starts to blame me, a similar workaround kills also my captcha-solution… :P