Performance problems in the java layer, Catastrophic Backtracking

15/07/17 — capitol


We discovered that we had a couple of requests that took extreme amounts of time and cpu power on our servers.

After dumping the thread stacks, we found out that the culprit was this regex:


When encountering strings that contains a large number of spaces, for example:

"SUNDEVEIEN                               A"

it uses very large amounts of cpu time to try to match.

After some testing, we determined that the execution time scaled in the order of O(2^n). As seen in this table.

spaces milliseconds
27 13915
28 26509
29 50512
30 106652
31 207174
32 409100
33 824363

The problem class is called catastrophic backtracking, and many regex engines are of the backtracking kind, also the standard one in java.

The problematic regex can be simplified to this in order to better highlight the problem:


What happens here is that the regex engine have multiple paths for matching the spaces it encounters, it can either add it to a the last space in the previous group or it can start a new group with it. When it encounters the ending A in the string it’s obvious for the human eye that the regex will never match, but the engine doesn’t know that without trying all combinations of groups of spaces, so it will backtrack in the string and try another way, which doesn’t work either, until all combinations are exhausted.

There is a number of ways to fix this problem, the most radical might be to replace the regex engine with one that guarantees linear execution, for example RE2J.

Or you could avoid nesting quantifiers (the pluses and stars), but this requires that you can restructure the problem.

Another way would be to rewrite the regex so that there isn’t a choice between different ways to match the string, for example by changing the first * into a +.

Finding side channel attacks in jasypt 1.8

11/07/17 — capitol


While doing an audit of some code for a project, I read through the code that verifies the password hashes.

It looked something like this:

    BasicPasswordEncryptor bpe = new BasicPasswordEncryptor();
    return bpe.checkPassword(clearText, storedPasswordHash);

Where the BasicPasswordEncryptor comes from the org.jasypt package.

After digging through some abstraction layers I found this in the class StandardByteDigester in jasypt.

    byte[] encryptedMessage = this.digest(message, salt);
    return Arrays.equals(encryptedMessage, digest);

This was a red flag, the Arrays.equals implementation is optimized for speed. This means that it’s implemented so that it returns at the first difference in the two arrays, in other words that the loop will take longer the more of the arrays that is equal.

It’s a tiny amount of time, but it’s possible to measure, specially if you are on the same machine or in the same data center, something that’s not so unrealistic when everything is hosted in one of the big cloud providers.

This specific leak compares two hashes with each other, and not two plain text passwords, this means that it leaks bytes from the hash and not from the password. This isn’t as bad, but it’s still not good.

If you want to do a dictionary attack on a user, in order guess what passwords that user is using, then if you manage to leak the first byte of the hash and there isn’t a salt in the algorithm then you can precompile the hash on the attacker side, see if the hashes compare and only send those that match to the server.

We can do a simple example on how to implement this locally:

    public static void main(String[] args) {
        String correctPassword = "correct";
        String wrongPassword = "wrong";

        BasicPasswordEncryptor bpe = new BasicPasswordEncryptor();
        String correctHash = bpe.encryptPassword(correctPassword);
        String wrongHash = bpe.encryptPassword(wrongPassword);

        int iterations = 10000;

        // warm up
        long[] warmUp1 = getLongs(correctPassword, bpe, correctHash, iterations);
        long[] warmUp2 = getLongs(correctPassword, bpe, wrongHash, iterations);

        long[] correctTimes = getLongs(correctPassword, bpe, correctHash, iterations);

        long[] wrongTimes = getLongs(correctPassword, bpe, wrongHash, iterations);


        System.out.println("correct = " + median(correctTimes));
        System.out.println("wrong   = " + median(wrongTimes));

    private static long[] getLongs(String correctPassword, BasicPasswordEncryptor bpe, String correctHash, int iterations) {
        long[] times = new long[iterations];
        for(int i = 0; i < iterations; i++) {
            long start = System.nanoTime();
            bpe.checkPassword(correctPassword, correctHash);
            long end = System.nanoTime();
            times[i] = end - start;
        return times;

    private static double median(long[] m) {
        int middle = m.length/2;
        if (m.length%2 == 1) {
            return m[middle];
        } else {
            return (m[middle-1] + m[middle]) / 2.0;

Running this on my laptop, with frequency scaling turned of, I get an average time difference of 17 nano seconds between checking a correct password and an incorrect.

In 2009 some scientists managed to measure timing attacks down to 100 ns over a gigabit network and speculated that 50 ns was possible with more sampling, in this paper.

With 10 gigabit being common in modern server hardware it’s not unreasonable to think that it would be possible to execute such an attack against an unguarded target.

After some more digging, it turns out that this vulnerability have been fixed in version 1.9.2 of jasypt, it has been replaced with this code:

    private static boolean digestsAreEqual(byte[] a, byte[] b) {
        if(a != null && b != null) {
            int aLen = a.length;
            if(b.length != aLen) {
                return false;
            } else {
                int match = 0;

                for(int i = 0; i < aLen; ++i) {
                    match |= a[i] ^ b[i];

                return match == 0;
        } else {
            return false;

What happens here is that the bitvise xor operator is used instead, so if there is any difference in the two byte arrays, then the match value will end up with 1’s in some of it bit positions, and the == 0 check will fail.

There is no early escape from the loop, as it compares hashes the size is guaranteed to be equal between the two parameters.

I strongly advise everyone who uses jasypt to upgrade to version 1.9.2.

The maintainers of jasypt was contacted in advance of the publication but were unresponsive. The debian security team was also contacted, as jasypt is packaged by debian. Mitre assigned it CVE-2014-9970.


The author of the code contacted us on twitter and pointed out that this bug was described in the changelog of version 1.9.2.

Blocks Everywhere

11/05/17 — capitol


We have made our own JSON web tokens, with AES and blocks! And without JSON.

Access the puzzle here:

telnet 2a02:ed06::2033 12348

or here

telnet 12348

Happy hacking!

Creating a fast blog

08/05/17 — capitol


Let us go over the stack we use to power this blog and why it’s both easy to use and fast for our visitors.

The goal is to serve the blog as fast as possible, while avoiding the constant stream of security holes that wordpress exposes its users to.

We achieve this by serving static content only, that is updated every time that someone pushes new content to the git repository that backs the blog.

We serve the content over http/2 and both IPv4 and Ipv6, in order to take advantage of the improvements in the new protocols.


Debian Jessie

We use debian jessie as a base distribution, they do a reasonable good job of patching security issues and have almost all the software we need packaged.

In regard to security, we think that the most likely attack is that someone reuse a known exploit rather than burn a 0-day on us. So the most important thing is to not have any unpatched software in our stack. In order to achieve this we have configured apt to automatically download and install security patches, as described here.


We use nginx as our web server of choice. It’s fast and quite flexible, it lacks a good module system but we don’t need any esoteric features.

We installed nginx from the jessie-backports repository, in order to get a version of nginx that supports http/2.

The configuration file for nginx looks like this:

server {
        listen 443 ssl http2;
        listen [::]:443 ssl http2;


        ssl_certificate /etc/letsencrypt/live/;
        ssl_certificate_key /etc/letsencrypt/live/;

        ssl_protocols TLSv1.2;
        ssl_ciphers 'EECDH+AESGCM:EDH+AESGCM:AES256+EECDH:AES256+EDH';
        ssl_dhparam /etc/ssl/certs/dhparam.pem;

        add_header Strict-Transport-Security "max-age=63072000; ";
        add_header X-Frame-Options "DENY";

        root /home/blog/blog-static/;

        location /images/ {
                expires 30d;

We configure the server to listen to both IPv4 and IPv6, supporting IPv6 means that mobile devices doesn’t have to go through a carrier grade NAT (CGN) in order to reach the site. CGN’s can add significant amount of latency when the conditions are bad.

The TLS protocol is limited to only TLSv1.2 as all modern browsers have supported it for a long time, the protocol was released in 2008. If there is someone out there that still can’t use it, they need to seriously rethink how they manage their software.

The list of ciphers are chosen in order to avoid a number of cryptographic attacks.

The Strict-Transport-Security header tells the browser that it should only use https in order to access the site in the future.

We also configure the caching of images to be 30 days, so that returning readers of the blog will have a better experience.

Let’s encrypt

The Let’s encrypt project is our TLS certificate provider, they have enabled the world to move away from the insecure http protocol.

Let’s encrypt lets us automate the signing of the certificate that TLS uses. We use certbot in standalone mode for this.

The openssl package needs to be installed from jessie backports also, since nginx was installed from there.


The engine that powers the blog is jekyll, it takes our blog posts that are written in markdown and compiles them into html pages.

The source of the blog lives on github and each blog post is it’s own file under _posts/ prefixed with the date it will be published.

On the server we have a simple bash script that monitors github for new content and regenerates the static files by running:

jekyll build --source /home/blog/blog --destination /home/blog/blog-static/

Jekyll is installed from source, since the version in debian is too old and there isn’t an updated version in backports.

TOR at hackeriet in 2016

01/05/17 — capitol


We at hackeriet started our tor node one year ago, with help from the NUUG foundation.

The node is still happily churning out encrypted data to different parts of the internet, as can be seen on out network graphs.

Our setup


We started the project with a dedicated 1U rack machine, a HP ProLiant DL160 G5 Server, it had four cores and 20 gig of ram.

This turned out to be way more iron than what we needed in order to power to node, so in september the machine was converted to a virtual machine in our proxmox cluster.


The machine was installed with Debian 8 and setup to automatically install security updates. The tor software was installed with the help of debian packages.

The machine have both ipv4 and ipv6 addresses, and we accept connections to tor from both.

The munin monitoring software ran on a separate machine.

What happened

We had a hardware failure on the machine that hosted the munin graphs, and as those were complimentary we didn’t have backups of them.

We also had a series of 5 power outages in the end of summer, most likely due to faulty hardware in one machine. As the problem was hard to reproduce and intermittent we never managed to conclude that the hardware we suspected was the culprit, but the problems stopped occurring when it was removed.

We opted into becoming a fallback directory mirror as our node is quite stable.

Right now the latest stable version of tor have just been released and we are in the process of upgrading to it.

What we learned

There has been a lot of drama in the tor project during 2016, one of the main activists resigned due to committing acts of sexual harassment.

There has also been multiple different attempts as FUD, mainly due to the fact that a lot of the funding for the development of the project comes from the american military.

There were also an attack on the tor network performed by FBI And Carnegie Mellon University in 2014, more information on the circumstances was published and combed over by the community.

What will happen now

We will continue to host our entry node, as tor is still one of the best projects for ensuring freedom from some of those that want to monitor your network traffic.