Solution to TUCTF 2017 Future task

27/11/17 — capitol

binary_search_tree

name:

Future

category:

reverse

points:

250

Writeup

We received a small c program that implemented a simple hash funktion.

In the program was a string that represented a hashed password and a simple hash implementation, our task was to find out what input string hashed into the byte array named pass.

The hash algorithm consisted of two steps.

  • A reordering of the original input string into a array in memory. Implemented in the function genMatrix.
  • The creation of the hashed by adding different bytes from the original string together. Implemented in the function genAuthString.

This was the source code of the given problem:

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

void genMatrix(char mat[5][5], char str[]) {
        for (int i = 0; i < 25; i++) {
                int m = (i * 2) % 25;
                int f = (i * 7) % 25;
                mat[m/5][m%5] = str[f];
        }
}

void genAuthString(char mat[5][5], char auth[]) {
        auth[0] = mat[0][0] + mat[4][4];
        auth[1] = mat[2][1] + mat[0][2];
        auth[2] = mat[4][2] + mat[4][1];
        auth[3] = mat[1][3] + mat[3][1];
        auth[4] = mat[3][4] + mat[1][2];
        auth[5] = mat[1][0] + mat[2][3];
        auth[6] = mat[2][4] + mat[2][0];
        auth[7] = mat[3][3] + mat[3][2] + mat[0][3];
        auth[8] = mat[0][4] + mat[4][0] + mat[0][1];
        auth[9] = mat[3][3] + mat[2][0];
        auth[10] = mat[4][0] + mat[1][2];
        auth[11] = mat[0][4] + mat[4][1];
        auth[12] = mat[0][3] + mat[0][2];
        auth[13] = mat[3][0] + mat[2][0];
        auth[14] = mat[1][4] + mat[1][2];
        auth[15] = mat[4][3] + mat[2][3];
        auth[16] = mat[2][2] + mat[0][2];
        auth[17] = mat[1][1] + mat[4][1];
}

int main() {
        char flag[26];
        printf("What's the flag: ");
        scanf("%25s", flag);
        flag[25] = 0;

        if (strlen(flag) != 25) {
                puts("Try harder.");
                return 0;
        }


        // Setup matrix
        char mat[5][5];// Matrix for a jumbled string
        genMatrix(mat, flag);
        // Generate auth string
        char auth[19]; // The auth string they generate
        auth[18] = 0; // null byte
        genAuthString(mat, auth);       
        char pass[19] = "\x8b\xce\xb0\x89\x7b\xb0\xb0\xee\xbf\x92\x65\x9d\x9a\x99\x99\x94\xad\xe4\x00";
        
        // Check the input
        if (!strcmp(pass, auth)) {
                puts("Yup thats the flag!");
        } else {
                puts("Nope. Try again.");
        }
        
        return 0;
}

Looking at the genAuthString method, we noticed that all but two of the equations only added two bytes, and we guessed that the flag only contained ascii characters. Since two ascii characters added are never more than 256 we didn’t have to worry about overflows for those, and if we got an overflow on the bytes with 3 values then we could handle that manually.

This meant that the hashing algorithm could be represented as a system of linear equations, and we knew that the flag was on the format TUCTF{…} so we had a seven characters of plain text.

We wrote a small program that printed the equations:

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

void genMatrix(char mat[5][5], char str[]) {
  for (int i = 0; i < 25; i++) {
    int m = (i * 2) % 25;
    int f = (i * 7) % 25;
    mat[m/5][m%5] = str[f];
  }
}

void printEquations(char mat[5][5], unsigned char auth[]) {
  printf("%c + %c = %u\n", mat[0][0], mat[4][4], auth[0]);
  printf("%c + %c = %u\n", mat[2][1], mat[0][2], auth[1]);
  printf("%c + %c = %u\n", mat[4][2], mat[4][1], auth[2]);
  printf("%c + %c = %u\n", mat[1][3], mat[3][1], auth[3]);
  printf("%c + %c = %u\n", mat[3][4], mat[1][2], auth[4]);
  printf("%c + %c = %u\n", mat[1][0], mat[2][3], auth[5]);
  printf("%c + %c = %u\n", mat[2][4], mat[2][0], auth[6]);
  printf("%c + %c + %c = %u\n", mat[3][3], mat[3][2], mat[0][3], auth[7]);
  printf("%c + %c + %c = %u\n", mat[0][4], mat[4][0], mat[0][1], auth[8]);
  printf("%c + %c = %u\n", mat[3][3], mat[2][0], auth[9]);
  printf("%c + %c = %u\n", mat[4][0], mat[1][2], auth[10]);
  printf("%c + %c = %u\n", mat[0][4], mat[4][1], auth[11]);
  printf("%c + %c = %u\n", mat[0][3], mat[0][2], auth[12]);
  printf("%c + %c = %u\n", mat[3][0], mat[2][0], auth[13]);
  printf("%c + %c = %u\n", mat[1][4], mat[1][2], auth[14]);
  printf("%c + %c = %u\n", mat[4][3], mat[2][3], auth[15]);
  printf("%c + %c = %u\n", mat[2][2], mat[0][2], auth[16]);
  printf("%c + %c = %u\n", mat[1][1], mat[4][1], auth[17]);
  printf("a = 84\n");
  printf("b = 85\n");
  printf("c = 67\n");
  printf("d = 84\n");
  printf("e = 70\n");
  printf("f = 123\n");
  printf("y = 124\n");
}

int main() {
  char* flag = "abcdefghijklmnopqrstuvwxy";
  char mat[5][5];// Matrix for a jumbled string
  unsigned char pass[19] = "\x8b\xce\xb0\x89\x7b\xb0\xb0\xee\xbf\x92\x65\x9d\x9a\x99\x99\x94\xad\xe4\x00";  
  genMatrix(mat, flag);
  printEquations(mat, pass);
}

After we had the equation system we just used this solver: https://quickmath.com/webMathematica3/quickmath/equations/solve/advanced.jsp

And got these results: a=84 b=85 c=67 d=84 e=70 f=123 g=53 h=121 i=53 j=55 k=t1 l=109 m=53 n=94 o=48 p=101 q=95 r=52 s=95 t=100 u=48 v=119 w=111 x=33 y=124

which translates to TUCTF{5y573m5_0f_4_d0wn!}

Performance problems in the java layer, Catastrophic Backtracking

15/07/17 — capitol

regex

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:

"((\\S*[\\s\\.]+)+)([0-9]+)[\\s\\.]*([A-z]([\\s\\.]|$))?(.*)"

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:

"(\\S*[\\s\\.]+)+[0-9]+"

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

stopwatch

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);

        Arrays.sort(correctTimes);
        Arrays.sort(wrongTimes);

        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.

Update

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

blocks

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 185.35.202.212 12348

Happy hacking!

Creating a fast blog

08/05/17 — capitol

dog

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.

Setup

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.

Nginx

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;

        server_name blog.hackeriet.no;

        ssl_certificate /etc/letsencrypt/live/hackeriet.no/fullchain.pem;
        ssl_certificate_key /etc/letsencrypt/live/hackeriet.no/privkey.pem;

        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.

Jekyll

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.