Solution to TUCTF 2017 High Source

29/11/17 — capitol

high_noon

name:

High Source

category:

web

points:

25

Writeup

This was easier than trivial, only 2 steps:

  • Look at source, get password; I4m4M4st3rC0d3rH4x0rsB3w43
  • enter password be redirected to this:

curl ‘http://highsource.tuctf.com/flagdir/flagdir/flagdir/flagdir/flagdir/flagdir/flagdir/flagdir/flagdir/flagdir/flagdir/flagdir/flagdir/flagdir/flagdir/flagdir/flagdir/flagdir/flagdir/flagdir/flagdir/flagdir/flagdir/flagdir/flagdir/flagdir/flagdir/flagdir/flagdir/flagdir/flagdir/flagdir/flagdir/flagdir/flagdir/flagdir/flagdir/flagdir/flagdir/flagdir/flagdir/flagdir/flagdir/flagdir/flagdir/flagdir/flagdir/flagdir/flagdir/flagdir/flagdir/flagdir/flagdir/flagdir/flagdir/flagdir/flagdir/flagdir/flagdir/flagdir/flagdir/flagdir/flagdir/flagdir/flagdir/flagdir/flagdir/flagdir/flagdir/flagdir/flagdir/flagdir/flagdir/flagdir/flagdir/flagdir/flagdir/flagdir/flagdir/flagdir/flagdir/flagdir/flagdir/flagdir/flagdir/flagdir/flagdir/flagdir/flagdir/flagdir/flagdir/flagdir/flagdir/flagdir/flagdir/flagdir/flagdir/flagdir/flagdir/flagdir/flag’

flag was TUCTF{H1gh_S0urc3_3qu4ls_L0ng_F4ll}

Solution to TUCTF 2017 The Neverending Crypto

28/11/17 — capitol

CipherDisk

name:

The Neverending Crypto

category:

crypto

points:

50

Writeup

We where presented with a server that encrypted strings with a substitution cipher.

You where also able to give up to twenty characters that the server gave the solution for.

The server didn’t use the complete byte range and it was a hassle to find out what characters that was included in the substitution. The server leaked the plain texts from time to time, and the number of plain text strings that was encrypted was small, only nine different ones.

This meant that we could write some simple heuristics to decide which of the strings to send back, the same plain text character always encrypts to the same encrypted character, so we could look at what characters in the ecrypted text are equal to determine what plain text to send back.

Implemented like this:

import socket
import re
import string
 
sobj = socket.socket(socket.AF_INET,socket.SOCK_STREAM)
sobj.connect(("neverending.tuctf.com",12345))
sobj.recv(1024)
 
re_question = re.compile(r"is (?P<question>.*) decrypted")
re_match = re.compile(r"a encrypted is (?P<chr>.)")

def workit():
    sobj.send("a\n")
 
    hint =  sobj.recv(1024)
    print "hint", repr(hint)
    c = re_match.match(hint).groupdict()["chr"]
 
# What is :BB7RJBE>^R@BE8 decrypted?
    question = re_question.findall(hint)[0]
    print "Question is", question
    answer = ""
    if question[1] == question[10]:
        answer = "how many more??"
    if question[11] == question[13]:
        answer = "something here."
    if question[1] == question[5]:
        answer = "you got lucky.."
    if question[12] == question[13]:
        answer = "you have skills"
    if question[1] == question[2]:
        answer = "good work, more"
    if question[1] == question[9]:
        answer = "you crypto wiz!"
    if question[13] == question[14] and question[1] == question[10]:
        answer = "how many more??"
    if question[1] == question[13]:
        answer = "welcome, hacker"
    if question[1] == question[6] and question[1] == question[13] and question[3] == question[10]:
        answer = "dont forget to "
    if answer == "":
        print "I DO NOT KNOW"
        import sys
        sys.exit()
    print answer
    sobj.send(answer + "\n")

while True:
    workit()
    print sobj.recv(1024)

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.