Visiting Xin Che Jian hackerspace in Shanghai

04/04/17 — head

logo

A couple of weeks ago i was in China visiting Shanghai, driven by curiosity. Most of the news i read about China are about the alarming levels of air pollution, the exploitation of labour and of course censorship and lack of civil liberties.

cameras

I found out that although these are all true, Shanghai has also much more to offer. For example some of the best and cheapest food i have ever had, a lively cultural scene and a quite stilish and laid back lifestyle. Also impressive is the offer of services and goods, and how accessible the city is, considering that almost no one speaks English.

High skyscrapers boasting with activities, 4 lanes elevated roads, huge shopping malls and 15 metro lines coexist side by side with quiet and elegant districts, known as the lilongs settlements, an architectural heritage of the pre-communist era, built between 1840 and 1940, coinciding with the western presence in this port city.

Read More

Detect security problems at compile time

02/04/17 — capitol

bits

A large part of modern software engineering consists of standing on the shoulders of other peoples code, this makes us more productive and lets us focus on the solving our business problems rather than reinventing wheels all the time.

But sometimes security problems are discovered in those libraries, if the project is well maintained they request a CVE number, patch the bug and release a new version. CVE numbers are the canonical identifiers for security problems and they are issued by the CVE Numbering Authority.

It’s obvious that we don’t want to use libraries in our projects that have known security holes, but how can we automate this this?

OWASP have solved this problem for us, with their Dependency Check project. It can integrate as a step in your build chain and verify your external dependencies.

For java this is done with a maven plugin, you can easily add this to your pom.xml:

    <build>
        <plugins>
            <plugin>
                <groupId>org.owasp</groupId>
                <artifactId>dependency-check-maven</artifactId>
                <version>1.4.5</version>
                <executions>
                    <execution>
                        <goals>
                            <goal>check</goal>
                        </goals>
                    </execution>
                </executions>
            </plugin>
        </plugins>
    </build>

When I run mvn verify in one of my projects with the above configuration it produces this output:

One or more dependencies were identified with known vulnerabilities in ctlog:

httpclient-4.3.3.jar (cpe:/a:apache:httpclient:4.3.3, org.apache.httpcomponents:httpclient:4.3.3) : CVE-2015-5262, CVE-2014-3577
bcprov-jdk15on-1.49.jar (cpe:/a:bouncycastle:bouncy-castle-crypto-package:1.49, cpe:/a:bouncycastle:bouncy_castle_crypto_package:1.49, org.bouncycastle:bcprov-jdk15on:1.49) : CVE-2015-7940


See the dependency-check report for more details.

And this report is produced.

It’s also possible to configure it to fail the build on any vulnerability, or if a severe enough problem is discovered.

My opinion is that this should be used in all projects, in order to quickly discover security problems and give the developers the possibility to act on them.

CTF: VolgaCTF VC task

27/03/17 — capitol

bits

name:

VC

category:

crypto

points:

50

Writeup

We were given two images, both containing black and white noise. A B

Since it’s a crypto challege with low points, we guessed that it’s a simple XOR.

The quickest way to xor two images is with a command line one liner:

convert A.png B.png -fx "(((255*u)&(255*(1-v)))|((255*(1-u))&(255*v)))/255" C.png

That produced this result: C

Flag: VolgaCTF{Classic_secret_sharing_scheme}

CTF: Shattering Prudentialv2

07/03/17 — capitol

bits

name:

Prudentialv2

category:

web

points:

50

Writeup

During the Boston Key Party CTF 2017 we also solved the Prudentialv2 task.

We were presented with a simple website that asked us to log in, a peek into the html source showed us a link to what looked like the source code of the backend:

<?php
require 'flag.php';

if (isset($_GET['name']) and isset($_GET['password'])) {
    $name = (string)$_GET['name'];
    $password = (string)$_GET['password'];

    if ($name == $password) {
        print 'Your password can not be your name.';
    } else if (sha1($name) === sha1($password)) {
      die('Flag: '.$flag);
    } else {
        print '<p class="alert">Invalid password.</p>';
    }
}
?>

This might have looked like an impossible challenge, if it wasn’t for the fact that google had released an attack on sha1 a few days prior.

We first tried to url-encode the two pdf’s and upload them as username and password, but the server had a post limit of 8k.

But the effective attack on sha1 is really quite small, so we could use that instead.

One script to generate the username and password files:

#!/usr/bin/env python
# from https://github.com/lxe/shattered/blob/master/shattered.js

import hashlib
a = bytearray([
  0x73, 0x46, 0xdc, 0x91, 0x66, 0xb6, 0x7e, 0x11, 0x8f, 0x02, 0x9a, 0xb6, 0x21, 0xb2, 0x56, 0x0f,
  0xf9, 0xca, 0x67, 0xcc, 0xa8, 0xc7, 0xf8, 0x5b, 0xa8, 0x4c, 0x79, 0x03, 0x0c, 0x2b, 0x3d, 0xe2,
  0x18, 0xf8, 0x6d, 0xb3, 0xa9, 0x09, 0x01, 0xd5, 0xdf, 0x45, 0xc1, 0x4f, 0x26, 0xfe, 0xdf, 0xb3,
  0xdc, 0x38, 0xe9, 0x6a, 0xc2, 0x2f, 0xe7, 0xbd, 0x72, 0x8f, 0x0e, 0x45, 0xbc, 0xe0, 0x46, 0xd2,
  0x3c, 0x57, 0x0f, 0xeb, 0x14, 0x13, 0x98, 0xbb, 0x55, 0x2e, 0xf5, 0xa0, 0xa8, 0x2b, 0xe3, 0x31,
  0xfe, 0xa4, 0x80, 0x37, 0xb8, 0xb5, 0xd7, 0x1f, 0x0e, 0x33, 0x2e, 0xdf, 0x93, 0xac, 0x35, 0x00,
  0xeb, 0x4d, 0xdc, 0x0d, 0xec, 0xc1, 0xa8, 0x64, 0x79, 0x0c, 0x78, 0x2c, 0x76, 0x21, 0x56, 0x60,
  0xdd, 0x30, 0x97, 0x91, 0xd0, 0x6b, 0xd0, 0xaf, 0x3f, 0x98, 0xcd, 0xa4, 0xbc, 0x46, 0x29, 0xb1
])

b = bytearray([
  0x7f, 0x46, 0xdc, 0x93, 0xa6, 0xb6, 0x7e, 0x01, 0x3b, 0x02, 0x9a, 0xaa, 0x1d, 0xb2, 0x56, 0x0b,
  0x45, 0xca, 0x67, 0xd6, 0x88, 0xc7, 0xf8, 0x4b, 0x8c, 0x4c, 0x79, 0x1f, 0xe0, 0x2b, 0x3d, 0xf6,
  0x14, 0xf8, 0x6d, 0xb1, 0x69, 0x09, 0x01, 0xc5, 0x6b, 0x45, 0xc1, 0x53, 0x0a, 0xfe, 0xdf, 0xb7,
  0x60, 0x38, 0xe9, 0x72, 0x72, 0x2f, 0xe7, 0xad, 0x72, 0x8f, 0x0e, 0x49, 0x04, 0xe0, 0x46, 0xc2,
  0x30, 0x57, 0x0f, 0xe9, 0xd4, 0x13, 0x98, 0xab, 0xe1, 0x2e, 0xf5, 0xbc, 0x94, 0x2b, 0xe3, 0x35,
  0x42, 0xa4, 0x80, 0x2d, 0x98, 0xb5, 0xd7, 0x0f, 0x2a, 0x33, 0x2e, 0xc3, 0x7f, 0xac, 0x35, 0x14,
  0xe7, 0x4d, 0xdc, 0x0f, 0x2c, 0xc1, 0xa8, 0x74, 0xcd, 0x0c, 0x78, 0x30, 0x5a, 0x21, 0x56, 0x64,
  0x61, 0x30, 0x97, 0x89, 0x60, 0x6b, 0xd0, 0xbf, 0x3f, 0x98, 0xcd, 0xa8, 0x04, 0x46, 0x29, 0xa1
])

prefix= bytearray([
  0x25, 0x50, 0x44, 0x46, 0x2d, 0x31, 0x2e, 0x33, 0x0a, 0x25, 0xe2, 0xe3, 0xcf, 0xd3, 0x0a, 0x0a,
  0x0a, 0x31, 0x20, 0x30, 0x20, 0x6f, 0x62, 0x6a, 0x0a, 0x3c, 0x3c, 0x2f, 0x57, 0x69, 0x64, 0x74,
  0x68, 0x20, 0x32, 0x20, 0x30, 0x20, 0x52, 0x2f, 0x48, 0x65, 0x69, 0x67, 0x68, 0x74, 0x20, 0x33,
  0x20, 0x30, 0x20, 0x52, 0x2f, 0x54, 0x79, 0x70, 0x65, 0x20, 0x34, 0x20, 0x30, 0x20, 0x52, 0x2f,
  0x53, 0x75, 0x62, 0x74, 0x79, 0x70, 0x65, 0x20, 0x35, 0x20, 0x30, 0x20, 0x52, 0x2f, 0x46, 0x69,
  0x6c, 0x74, 0x65, 0x72, 0x20, 0x36, 0x20, 0x30, 0x20, 0x52, 0x2f, 0x43, 0x6f, 0x6c, 0x6f, 0x72,
  0x53, 0x70, 0x61, 0x63, 0x65, 0x20, 0x37, 0x20, 0x30, 0x20, 0x52, 0x2f, 0x4c, 0x65, 0x6e, 0x67,
  0x74, 0x68, 0x20, 0x38, 0x20, 0x30, 0x20, 0x52, 0x2f, 0x42, 0x69, 0x74, 0x73, 0x50, 0x65, 0x72,
  0x43, 0x6f, 0x6d, 0x70, 0x6f, 0x6e, 0x65, 0x6e, 0x74, 0x20, 0x38, 0x3e, 0x3e, 0x0a, 0x73, 0x74,
  0x72, 0x65, 0x61, 0x6d, 0x0a, 0xff, 0xd8, 0xff, 0xfe, 0x00, 0x24, 0x53, 0x48, 0x41, 0x2d, 0x31,
  0x20, 0x69, 0x73, 0x20, 0x64, 0x65, 0x61, 0x64, 0x21, 0x21, 0x21, 0x21, 0x21, 0x85, 0x2f, 0xec,
  0x09, 0x23, 0x39, 0x75, 0x9c, 0x39, 0xb1, 0xa1, 0xc6, 0x3c, 0x4c, 0x97, 0xe1, 0xff, 0xfe, 0x01
])

s1 = prefix + a
s2 = prefix + b

with open("user.blob", "w") as fp:
    fp.write(s1)

with open("pw.blob", "w") as fp:
    fp.write(s2)

And one script to upload them to the server and get the flag:

#!/usr/bin/env python

import socket
import urllib

user = open("user.blob").read()
password = open("pw.blob").read()

user = urllib.quote_plus(user)
password = urllib.quote_plus(password)

req = "GET /index.php?name=%s&password=%s HTTP/1.1\r\nHost: 54.202.82.13\r\n\r\n" % (user, password)

conn = socket.create_connection(("54.202.82.13", 80))
conn.send(req)
print conn.recv(2048)

Flag: FLAG{AfterThursdayWeHadToReduceThePointValue}

Image credit

CTF: Eating a nice RSA buffet

27/02/17 — capitol

buffet

name:

RSA Buffet

category:

crypto

points:

150

Writeup

During the 2017 Boston Key Party we were presented with a very nice buffet of RSA keys to crack.

There where 10 different keys and five of them decrypted five other cipher texts. Any three of those five could be combined with the help of secret sharing to get the flag.

We used four different attacks on RSA in order to retrieve five of the keys.

Brute force to find key 2

One of the primes for key number two was really small, only 2758599203. We could have just used brute force to calculate it, but instead we found it in factordb

Greatest common divisor to find both key 0 and 6

Finding out if two numbers have a common divisor is extremely efficient, it’s done with one of the oldest known algorithms: the Euclidean algorithm.

Comparing all the keys with each other takes no time at all:

    private static void findKey0and6(BigInteger[] keys) {
        for(int i = 0; i < keys.length; i++) {
            for(int j = 0; j < keys.length; j++) {
                if(i == j)
                    continue;

                BigInteger gcd = keys[i].gcd(keys[j]);
                if(gcd.compareTo(BigInteger.ONE) > 0)
                    System.out.println("gcd " + i + ":" + j +" = " + gcd);
            }
        }
    }

We found a reused prime between key 0 and 6.

Fermat’s Factorization Method to find key 1

If the two primes p and q are clustered close to \sqrt{N}, then we can use the fermat factorization method to find them.

This is the implementation that we used:

public class Fermat {

    public static BigInteger factor(BigInteger n) {
        // Fermat's Factorization Method
        BigInteger A = BigMath.sqrt(n);
        BigInteger Bsq = A.multiply(A).subtract(n);
        BigInteger B = BigMath.sqrt(Bsq);
        BigInteger AminusB = A.subtract(B);

        // c is a chosen bound which controls when Fermat stops
        BigInteger c = new BigInteger("30");
        BigInteger AminusB_prev = A.subtract(B).add(c);
        BigInteger result = null;

        while (!BigMath.sqrt(Bsq).pow(2).equals(Bsq) && AminusB_prev.subtract(AminusB).compareTo(c) > -1) {
            A = A.add(BigInteger.ONE);
            Bsq = A.multiply(A).subtract(n);

            B = BigMath.sqrt(Bsq);
            AminusB_prev = AminusB;
            AminusB = A.subtract(B);
        }

        if (BigMath.sqrt(Bsq).pow(2).equals(Bsq)) {
            result = AminusB;
        }

        // Trial Division
        else {
            boolean solved = false;
            BigInteger p = AminusB.add(BigMath.TWO);

            if (p.remainder(BigMath.TWO).intValue() == 0) {
                p = p.add(BigInteger.ONE);
            }
            while (!solved) {
                p = p.subtract(BigMath.TWO);
                if (n.remainder(p).equals(BigInteger.ZERO)) {
                    solved = true;
                }
            }

            result = p;
        }

        return result;
    }
}
Wiener attack to solve key 3

Key 3 had a really big e, this was a good hint that we could use the wiener attack.

RSA isn’t an algorithm very well suited to run on constrained systems. This has led people to try to speed it up, and one thing that they tried was to have a small d and a large e. Michael J. Wiener was the man who developed an attack against that.

The implementation that we used was this one:

public class WienerAttack {

    //Four ArrayList for finding proper n/d which later on for guessing k/dg
    private List<BigInteger> q = new ArrayList<>();
    private List<Fraction> r = new ArrayList<>();
    private List<BigInteger> n = new ArrayList<>();
    private List<BigInteger> d = new ArrayList<>();

    private BigInteger e;
    private BigInteger N;

    private Fraction kDdg = new Fraction(BigInteger.ZERO, BigInteger.ONE); // k/dg, D means "divide"

    //Constructor for the case using files as inputs for generating e and N
    public WienerAttack(BigInteger e, BigInteger N) throws IOException {
        this.e = e;
        this.N = N;
    }

    public BigInteger attack() {
        int i = 0;
        BigInteger temp1;

        //This loop keeps going unless the privateKey is calculated or no privateKey is generated
        //When no privateKey is generated, temp1 == -1
        while ((temp1 = step(i)) == null) {
            i++;
        }

        return temp1;
    }

    //Steps follow the paper called "Cryptanalysis of Short RSA Secret Exponents by Michael J. Wiener"
    private BigInteger step(int iteration) {
        if (iteration == 0) {
            //initialization for iteration 0
            Fraction ini = new Fraction(e, N);
            q.add(ini.floor());
            r.add(ini.remainder());
            n.add(q.get(0));
            d.add(BigInteger.ONE);
        } else if (iteration == 1) {
            //iteration 1
            Fraction temp2 = new Fraction(r.get(0).denominator, r.get(0).numerator);
            q.add(temp2.floor());
            r.add(temp2.remainder());
            n.add((q.get(0).multiply(q.get(1))).add(BigInteger.ONE));
            d.add(q.get(1));
        } else {
            if (r.get(iteration - 1).numerator.equals(BigInteger.ZERO)) {
                return BigInteger.ONE.negate(); //Finite continued fraction. and no proper privateKey could be generated. Return -1
            }

            //go on calculating n and d for iteration i by using formulas stating on the paper
            Fraction temp3 = new Fraction(r.get(iteration - 1).denominator, r.get(iteration - 1).numerator);
            q.add(temp3.floor());
            r.add(temp3.remainder());
            n.add((q.get(iteration).multiply(n.get(iteration - 1)).add(n.get(iteration - 2))));
            d.add((q.get(iteration).multiply(d.get(iteration - 1)).add(d.get(iteration - 2))));
        }

        //if iteration is even, assign <q0, q1, q2,...,qi+1> to kDdg
        if (iteration % 2 == 0) {
            if (iteration == 0) {
                kDdg = new Fraction(q.get(0).add(BigInteger.ONE), BigInteger.ONE);
            } else {
                kDdg = new Fraction((q.get(iteration).add(BigInteger.ONE)).multiply(n.get(iteration - 1)).add(n.get(iteration - 2)), (q.get(iteration).add(BigInteger.ONE)).multiply(d.get(iteration - 1)).add(d.get(iteration - 2)));
            }
        }

        //if iteration is odd, assign <q0, q1, q2,...,qi> to kDdg
        else {
            kDdg = new Fraction(n.get(iteration), d.get(iteration));
        }

        BigInteger edg = this.e.multiply(kDdg.denominator); //get edg from e * dg

        //dividing edg by k yields a quotient of (p-1)(q-1) and a remainder of g
        BigInteger fy = (new Fraction(this.e, kDdg)).floor();
        BigInteger g = edg.mod(kDdg.numerator);

        //get (p+q)/2 and check whether (p+q)/2 is integer or not
        BigDecimal pAqD2 = (new BigDecimal(this.N.subtract(fy))).add(BigDecimal.ONE).divide(new BigDecimal("2"));
        if (!pAqD2.remainder(BigDecimal.ONE).equals(BigDecimal.ZERO))
            return null;

        //get [(p-q)/2]^2 and check [(p-q)/2]^2 is a perfect square or not
        BigInteger pMqD2s = pAqD2.toBigInteger().pow(2).subtract(N);
        BigInteger pMqD2 = BigMath.sqrt(pMqD2s);
        if (!pMqD2.pow(2).equals(pMqD2s))
            return null;

        //get private key d from edg/eg
        return edg.divide(e.multiply(g));

    }
}

public class Fraction {
    public BigInteger numerator;
    public BigInteger denominator;

    //Constructor of the Fraction class which initializes the numerator and denominator
    public Fraction(BigInteger paramBigInteger1, BigInteger paramBigInteger2) {
        //find out the gcd of paramBigInteger1 and paramBigInteger2 which is used for ensuring the numerator and denominator are relatively prime
        BigInteger localBigInteger = paramBigInteger1.gcd(paramBigInteger2);

        this.numerator = paramBigInteger1.divide(localBigInteger);
        this.denominator = paramBigInteger2.divide(localBigInteger);
    }

    //Constructor for the case when calculating (paramBigInteger1 /(paramFraction.numerator / paramFraction.denominator))
    public Fraction(BigInteger paramBigInteger, Fraction paramFraction) {
        this.numerator = paramBigInteger.multiply(paramFraction.denominator);
        this.denominator = paramFraction.numerator;
        BigInteger localBigInteger = this.numerator.gcd(this.denominator);
        this.numerator = this.numerator.divide(localBigInteger);
        this.denominator = this.denominator.divide(localBigInteger);
    }

    //Calculate the quotient of this Fraction
    public BigInteger floor() {
        BigDecimal localBigDecimal1 = new BigDecimal(this.numerator);
        BigDecimal localBigDecimal2 = new BigDecimal(this.denominator);
        return localBigDecimal1.divide(localBigDecimal2, 3).toBigInteger();
    }

    //Calculate the remainder of this Fraction and assign the result to form a new Fraction
    public Fraction remainder() {
        BigInteger floor = this.floor();
        BigInteger numeratorNew = this.numerator.subtract(floor.multiply(this.denominator));
        BigInteger denominatorNew = this.denominator;
        return new Fraction(numeratorNew, denominatorNew);
    }
}

These attacks combined gave us enough plaintext so that we could recover that flag, which was FLAG{ndQzjRpnSP60NgWET6jX}

Image credit