This weekend, I participated in the Tokyo Westerns CTF. During this event, I placed relatively poorly due to lack of focus (aka multitasking Deux Ex Mankind Divided and levelling my warlock to 105 in WoW. If I wasn’t on a PvP server I’d probably spec out of Dark Pact for Burning Rush for climbing up the motherfucking Highmountain).

As usual, I’ll document the more interesting solutions in this CTF below, for reference:

Twin Primes

This cryptography challenge was presented as a zip archive (the solution is also inside but whatever). Download here: twinprimes

Upon initial inspection, you can see that this is a reasonably standard RSA-based challenge, with the notable twist that the primes forming the two public n’s (n1, n2) differ by two. This allows us to express one of the primes (p) as a function of both public n’s, as follows:

assert p * q = n
assert (p+2) * (q+2) = m

m - n = (p + 2) * (q + 2) - pq
m - n = pq + 2p + 2q + 4 - pq
m - n = 2p + 2q + 4
m - n - 4 = 2p + 2q
m - n - 4 = 2(p+q)
p+q = (m - n - 4) / 2
let (m - n - 4) / 2 = d, as this is static.
q = d-p
p * (d-p) = n
- p^2 + pd = n

-p^2 + pd - n = 0, solve for p

As you can see, this reduces to a quadratic equation (haven’t seen that since school), which we can easily solve for P – from there, we derive q, and we have enough material to reform both private keys and decrypt the flag:

You can find the solution here.

Reversebox

This challenge was presented as a Linux binary: reverse_box

Along with this, we are provided with the encrypted key:

95eeaf95ef94234999582f722f492f72b19a7aaf72e6e776b57aee722fe77ab5ad9aaeb156729676ae7a23c099b1df4a

I began my analysis with a journey into IDA Pro. I determined that this was a console application which took as input a string, and then output the encoded version of the string. I proceeded to the encryption function, located at 0x0804858D.

Being incredibly lazy and too broke to afford Hex-Rays, I offered a beer to the first person to Hex-Rays’ify this for me in a chat room. Unfortunately, the resulting C code was also a bit of a clusterfuck:

int __cdecl sub_804858D(_BYTE *a1)
{
 unsigned int v1; // eax@1
 int v2; // edx@4
 char v3; // al@5
 char v4; // ST1B_1@7
 char v5; // al@8
 int v6; // eax@10
 int v7; // ecx@10
 int v8; // eax@10
 int v9; // ecx@10
 int v10; // eax@10
 int v11; // ecx@10
 int v12; // eax@10
 int v13; // ecx@10
 int result; // eax@10
 char v15; // [sp+1Ah] [bp-Eh]@3
 char v16; // [sp+1Bh] [bp-Dh]@3
 char v17; // [sp+1Bh] [bp-Dh]@7
 int v18; // [sp+1Ch] [bp-Ch]@2

 v1 = time(0);
 srand(v1);
 do
   v18 = (unsigned __int8)rand();
 while ( !v18 );
 *a1 = v18;
 v15 = 1;
 v16 = 1;
 do
 {
   v2 = (unsigned __int8)v15 ^ 2 * (unsigned __int8)v15;
   if ( v15 >= 0 )
     v3 = 0;
   else
     v3 = 27;
   v15 = v2 ^ v3;
   v4 = 4 * (2 * v16 ^ v16) ^ 2 * v16 ^ v16;
   v17 = 16 * v4 ^ v4;
   if ( v17 >= 0 )
     v5 = 0;
   else
     v5 = 9;
   v16 = v17 ^ v5;
   v6 = *a1;
   LOBYTE(v6) = v16 ^ v6;
   v7 = (unsigned __int8)v16;
   LOBYTE(v7) = __ROR1__(v16, 7);
   v8 = v7 ^ v6;
   v9 = (unsigned __int8)v16;
   LOBYTE(v9) = __ROR1__(v16, 6);
   v10 = v9 ^ v8;
   v11 = (unsigned __int8)v16;
   LOBYTE(v11) = __ROR1__(v16, 5);
   v12 = v11 ^ v10;
   v13 = (unsigned __int8)v16;
   LOBYTE(v13) = __ROR1__(v16, 4);
   result = v13 ^ v12;
   a1[(unsigned __int8)v15] = result;
 }
 while ( v15 != 1 );
 return result;
}

From here, I attempted some manual cryptanalysis (by entering various keys in, and inspecting the output). We can quickly determine:

• For a given input, the application does not always produce a given output. Multiple outputs correspond to a single input.
• The output length corresponds to the input length – for each one character of input, two characters of output are generated (hexadecimal output).
• Each character in the input corresponds to two characters in the output, these two characters do not change (i.e. if “1” encodes to “aa”, “11” encodes to “aaaa”).

From here, we can determine that this is a cipher with a key of some sort: that is, a value (generated at runtime) is used to influence the output. We can see this right at the start of the encryption function:

v18 = (unsigned __int8)rand();

This key is cast to an 8-bit integer, meaning that while rand() may return a full DWORD of value, only the last 8 bits are meaningful – the other bits are discarded.

Therefore, we can abuse the program by using it as an encryption oracle: we know that “TWCTF” must encrypt to “95eeaf95ef”, we can brute force through the values of v18 (the result of rand) until the output matches:

From here, we simply ask the program to use the same key to encrypt “TWCTF{%s}” % string.printable. This gives us an “alphabet” with which we can decrypt any printable character. Some simple pattern matching with a Python script later, and we have the key:

(Unfortunately, I didn’t use string.printable, so I was missing a character – but I guessed this would be “-” and I was right).

Super Express

As above, the Super Express challenge was presented as a zip file: super_express

This contained some custom cryptographic code, as well as some ciphertext. I started by inspection of the cryptographic code:

import sys
key = '****CENSORED***************'
flag = 'TWCTF{*******CENSORED********}'

if len(key) % 2 == 1:
    print("Key Length Error")
    sys.exit(1)

n = len(key) / 2
encrypted = ''
for c in flag:
    c = ord(c)
    for a, b in zip(key[0:n], key[n:2*n]):
        c = (ord(a) * c + ord(b)) % 251
    encrypted += '%02x' % c

print encrypted

The content in red was the focal point of the exercise – to me, it appeared that they were running a simple algorithm a number of times:

c = (a * c + b) % 251

I wondered if this operation might be redundant: that is, even though this operation would be performed many times (an unknown number of times, depending on the length of the key), each operation produced a single input to a single output (‘c’): therefore, perhaps only one decryption step was necessary.

To test this theory, I applied brute force (best force):

This quickly identified that a static ‘a’ and ‘b’ could be used (in effect, a single key). Decrypting the actual key was trivial from here:

TWCTF{Faster_Than_Shinkansen!}

You can find the python script here.

Greeting

The Greeting challenge was presented as a Linux binary. You can download this here: greeting

The vulnerability (attack vector) itself is rather simple, as below:

As you can see, user input is wrapped in an sprintf, and passed to an unguarded use of the printf function at 0x0804864F. We can test this with %p:

From here, the traditional wisdom is that we should use this vulnerability as a read-write primitive, and overwrite a function pointer. Unfortunately, the disassembly shows that the program ends right after we call printf, without calling any other functions.

Fortunately, we can still exploit this by overwriting a destructor (in IDA – “.fini_array”). These are called *after* main exits. We then perform a second write, overwriting ‘printf’ to point to ‘system’, so the exploit looks like this:

main()call sprintf
call printf
overwrite .fini_array to point to main
overwrite printf to point to system.fini_array -> call main
call sprintf
call printf -> call system ("Nice to meet you, | ls | (:)")

The overwrites – redirected function calls – are represented in red. Running this exploit against the server gets us an easy flag and a few points:

For those of you who have seen me do a format string before, you’ll note again my preference for “%hn” instead of “%n”. “%hn” performs a two-byte write, resulting in much cleaner attacks with two writes instead of four (due to overlapping %n writes).

As always, thankyou to the TWCTF organisers for a fun and engaging challenge – unfortunately, I didn’t participate as much as I could have.

See you all at ASIS CTF next weekend!