ngg

#!/usr/bin/env python2

"""
As I'm not confident enough in my own Haskell comprehension skills, I started with reimplementing the whole thing in Python,
checking each function if it does the same thing.

At the end it seemed like it does the following:
- There is some padding of the flag based on its length (which we know, so it will be irrelevant)
- The flag is treated as a bit string
- Each bit position has a value assigned to it based on primes

ngg

#!/usr/bin/env python3
# -*- coding: utf-8 -*-

"""
We know that e*d = 1 (mod phi(n)), so there exists a small c (in the order of e) such that:
e*d = (p-1)*(q-1)*c + 1

Also, for ipmq and iqmp the following equation holds (it can be seen from how they can be calculated from the extended Euclidean algorithm):
ipmq*p + iqmp*q = p*q + 1

ngg

OneLineCalc Part1

• Realized that we can write C code after a ; character.
• We circumvented the character blacklist via trigraphs (<% instead of { et al).
• Tried various syscalls, some of them worked, some did not.
• Leaked files and directory structure one byte at a time.
• We tried to create reverse shell but seccomp prevented us from doing so.
• Used __attribute__((constructor(101)) to execute our code before the already existing constructor that set up seccomp.
• Now the shell worked!
• Realized that we had no permission to read the flag file because the code run with nobody:nogroup permissions.

ngg

diff --git a/block0.cpp b/block0.cpp
index ad99358..e92eb04 100644
--- a/block0.cpp
+++ b/block0.cpp
@@ -83,11 +83,18 @@ void find_block0(uint32 block[], const uint32 IV[])
 		Q[Qoff + 16] = (xrng64() & 0x1ffdffff) | 0xa0000000 | (~Q[Qoff + 15] & 0x40020000);
 
 		MD5_REVERSE_STEP(0, 0xd76aa478, 7);
+		if (!ok_uint32(block[0])) continue;
 		MD5_REVERSE_STEP(6, 0xa8304613, 17);

ngg

There was a RSA-like encryption implemented with polynomials over GF(2^2049) instead of integers. With sage it was easy to factor the public key into its two irreducible factors, from which the size of the multiplicative group modulo the public key can be calculated and that can be used to calculate the inverse of the public exponent.

Python (Sage) implementation:

from sage.all import *
from pubkey import P, n, e

ngg

Given were some kind of combined output from three different LFSRs, the task was to reverse their initial state. This was no match for Z3:

#!/usr/bin/env python3
from z3 import *
import binascii, hashlib
ks = bytes(map(ord, open('keystream', 'rb').read().decode()))
k = int(binascii.hexlify(ks), 16)
n = len(ks)*8

ngg

The task was to create a collision for Keccak where the capacity of the sponge was reduced to 48 bits. This way the rate is 194 bytes which means the text is chunked into 194 byte long parts and these chunks are XORed into the first 194 bytes of the state (out of 200 byte) before the Keccak-f[1600] permutation function is called. First I searched for two 194-byte long chunks for which the last 6 bytes of the state are the same. This needs around 2^24 tries because of the birthday paradox. After this we can append the new states' first 194 byte to each message that will zero these bytes leaving only the last 6 bytes non-zero which we know are identical. This way the inner state of the hash function is the same after 2*194 bytes, the padding will not make a difference.

I used KeccakF from https://github.com/KeccakTeam/KeccakTools to find the first chunks using the following C++ code:

KeccakF keccakF(1600);

ngg

There was a 4-round [SPN][1] implemented in python with 64-bit key and block sizes. We were given 65536 pairs of random plaintexts and corresponding ciphertexts encrypted with a single key. The task was to find the key.

The P-box used in the cipher was a pretty standard transposition, the weak part was the S-box. Our attack followed the great [tutorial][2] on Linear Cryptanalysis. It was possible to find probabilistically biased linear expressions on the input and output bits of the S-box. We used the following script for this part:

ngg

The task was to write a LUA AI that beats the computer in Rock-paper-scissors. The computer had three different strategies, each of them depended on a random seed. The submitted AI had to figure out which strategy it's playing against then somehow recover its inner state and then win at least 90000 out of 100000 times.

The three strategies worked like this python code:

class Slime(object):
    def __init__(self, seed):
        self.state = seed
    def play(self, last):
        self.state = (self.state+1)%3
 return self.state

ngg

I recovered the flag in multiple parts.

The first 7 bytes of the were known: hitcon{

The text (pad('Welcome!!')) was encrypted and sent, this known plaintext-ciphertext pair could be used to produce the encryption of any 1-block message by xoring the IV, I used this to send the get-flag command. Then I could brute-force the first block of the flag byte-by-byte by modifying this message so its decryption starts with a number of spaces and the get-flag command if I could guess the next character correctly. (The get-flag command is 8 bytes and 7 bytes of the flag was already known, so I could start with the 8th). This gave me the first block of the flag: hitcon{Paddin9_1

The next 8 bytes were recovered with a different strategy. I changed the encrypted flags' first block to contain ' '*9+'get-md5' and appended a random extra block to its end. When the server decrypted it the random ending block produced a random padding, so in good cases the stripped command looked like `'get-md5' + someprefixof