JustCTF 2020

General Comments {#justctf2020}

Back for another CTF after Christmas depression.

(CTF apparently called 2020 because it was rescheduled even though it took place in 2021.)

Overall seemed like an okay mid-tier CTF. “Decent, but not great.” The tasks I looked at were a bit on the easy side, there were only two crypto, one of them very meh, and pretty much all of the misc was meh-adjacent.

I only actively played the first day (Saturday) so can’t really say that much about the tasks released late¹.

Also, one complaint poiko had that I fully agree with and can forward: all flags outputted by tasks should be consistent. (C.f. reklest.) It’s such a basic thing it should be considered a cardinal sin to violate it. If the nature of a task requires a different format, there should be a big note describing it in mathematically precise English. (C.f. the convoluted description on ABNF.)

25519

Trivial crypto task where you get the private key. The hardest part is simply to mentally parse the script to see what it expects.

The goal is to pass this check with 8 different parameter sets:

def verify(signature, P, m):
  I, e, s = signature
  return e == hashs(m, s*G + e*P, s*hashp(P) + e*I)

You provide I, e, s and you’re given everything else: P, m, G, x, where $x$ is the private key in $P = x G$ . hashp(P) can be treated as a new random point on the curve.

Thus, to generate however many solutions you want:

x = ... # the given private key, P=xG
Q = hashp(P) # treat hashp(P) as a novel point

# random nonces
t = <random>
h = <random>

# the target hash that we will construct
e = hashs(m, t*G, h*Q)

# set s such that t*G == s*G + e*P
s = (t - e*x) % ec_order

# set I such that h*Q == s*Q + e*I
I = (h - s) * pow(e, -1, ec_order) * Q

# e, s, I is a solution

Do this 8 times and get the flag.

Oracles

Web-ish crypto where you’re given the code for a nodejs server. (Whose instances are gated behind a 28-bit PoW.)

It vaguely involved a quadfecta of things I dislike (web, javascript, remote, docker), so I dragged my feet a lot before I was bribed with pizza to properly look at it.

But so: the instance gives you three ciphertexts, two being of known plaintexts, the third being the flag. Each is encrypted with RSA_OAEP from asmcrypto.js.

(Note: the first iteration of this problem, and the one I wasted the most time on had the public key redacted, so you didn’t know the modulus (normal exponent of 65537 was implied). Which I felt was pretty sadistic and painful. I realize you could technically recover it from the given ciphertexts, doing GCD on 64MB numbers, but that’s pretty painful… (Either reimplement OAEP or use noedjs, probably need to use a good bigint library like GMP and not Python’s slow-ints, etc.) They later updated the task to provide the pubkey, but they only noted this on the “news” page and not on in task description itself so I totally missed it until poiko pointed it out to me. I feel that’s sort of bad communication.)

On the server there’s an oracle query that does this:

const oracle = new asmCrypto.RSA_OAEP(privkey, new asmCrypto.Sha256(), fs.readFileSync('./oracles_stuff/' + oracleName));

var response = "I won't answer.";
try {
    const result = oracle.decrypt(question);
    asmCrypto.bytes_to_string(result);
} catch(err) {
    //
}

res.render('index', {response: response});

That is, you give it some data, it attempts to decrypt it and simply discards everything, ignoring errors.

It was easy to guess that it would be a timing attack problem, but because you have to actually do non-trivial stuff (i.e. web) to test your guess I was still loath to commit.

However there were two factors that severely strengthened my guess that it’s a timing attack problem.

Inspecting the asmcrypto.js source strengthens the guess tho:

// ...
this.rsa.decrypt(new BigNumber(data));

const z = this.rsa.result[0];
const seed = this.rsa.result.subarray(1, hash_size + 1);
const data_block = this.rsa.result.subarray(hash_size + 1);

if (z !== 0) throw new SecurityError('decryption failed');

const seed_mask = this.RSA_MGF1_generate(data_block, seed.length);
for (let i = 0; i < seed.length; i++) seed[i] ^= seed_mask[i];

const data_block_mask = this.RSA_MGF1_generate(seed, data_block.length);
for (let i = 0; i < data_block.length; i++) data_block[i] ^= data_block_mask[i];

const lhash = this.hash
  .reset()
  .process(this.label || new Uint8Array(0))
  .finish().result as Uint8Array;
for (let i = 0; i < hash_size; i++) {
  if (lhash[i] !== data_block[i]) throw new SecurityError('decryption failed');
}
// ...

I.e. it checks immediately if the first byte is 0 and fails early if not. Only after this check does it hash the label data. And note in the oracle source you can provide whatever file you want for the label. (I found the largest file on the docker, which was something like ../../opt/yarn-v1.22.5/lib/cli.js and used that.)

Second and final hint that it’s a straightforward timing attack: the server explicitly gives its response-time in the HTTP headers so you don’t actually have to time it yourself.

It turns out the difference between a valid decryption and an invalid one was something like ~7ms vs ~40ms, so yes, now you have a decryption oracle (on the first byte).

From there, finally!, there’s actual math. The basic idea is that you can multiply the message $m$ by a number $k$ (because $(m \cdot k)^{e} = c \cdot k^{e}$ ) and have the decrypt method tell you whether the first byte (in big endian) is 0 or not, meaning that $l \cdot n \leq k \cdot m < l \cdot n + 2^{1024 - 8}$ for some $l$ . I use this as an invariant.

This was all napkin math I did at the time but hopefully correct.

Set $B = 2^{1024 - 8}$ because we’re checking on high 8 bits. First we need to discover a $k$ to start with, i.e. where $l = 1$ in the above case. This is $k = ⌈ n / m ⌉$ . I used $⌈ n / B ⌉$ as an estimate and brute force it, even though there’s better ways, this is simpler.

The idea is to keep multiplying the values by 2 and readjusting based on what the oracle tells us. We always want $k$ (named a in the code below) to be the least possible so that $k \cdot m$ “barely” overflows on the modulus. When we multiply all values by 2, we then have to figure out if we’re in $[0, B)$ or $[B, 2 B)$ based on what the oracle tells us. Code like so: (comments and cleanup added after-the-fact.)

def discover(n, B, oracle):
  # First discover a = ceil(n//T)

  # Use a more efficient techinque here if (n//B)*T < B
  assert not oracle(n//B)

  a = n//B + 1
  while not oracle(a):
    a += 1

  # assert a == n//T + 1
  for i in count(0):
    # assert 2**i*n <= a*T < 2**i*n + B

    if B//a == 0:
      return (2**i * n + B)//a

    a = 2*a - 1
    if not oracle(a):
      a += 1

It failed the first time I tried it against the live server, but that might have been a timing glitch. I didn’t have any error detection stuff in my code, for when the ranges have become invalid. It might be possible to do something more clever and robust here, but eh, c’est la vie de CTF.

So now you have $m$ and I need to decrypt it with this OAEP nonsense. I just copy pasted the bytes of $m$ into an array and used nodejs so I could apply asmcrypto.js directly by copy-pasting the latter half of the decrypt function. I didn’t really feel like reimplementing anything or looking up more APIs.

All in all I have to admit it’s a pretty well-made crypto task from a certain perspective. If you’re the sort of person who cares about practical applicability and the real world then it’s A+. Unfortunately I’m not and kept whining over the fact that I had to actually read js code.

That’s not crypto

Listed as reverse so I only discovered it by accident. Python byte code that contains a list of big numbers. These numbers are used as coefficients in a polynomial $P (x)$ and there’s a check that does something like all(c*P(d*x) == c*c for x in accumulate(flag)) for some fixed literals c and d. In other words, the cummulative sums of flag’s bytes are the roots of $P (x) - c$ divided by $d$ . Instead of trying to factor this polynomial, I just did this in REPL:

>>> n = lambda l: [i for i in range(1,256) if p(d*(l + i)) == c][0]
>>> r = [n(0)]
>>> while True: r.append(n(sum(r)))

It will stop on exception and then print(bytes(r)) gives the flag.

PDF is broken, and so is this file

Put off this task till late because I vibed from the description that it would be some stupid rabbit hole thing. poiko did some preliminary analysis and told me I was right.

The “PDF” file you get can be intrepreted as a Ruby script; and as such a script it starts a web server on localhost where you can download the file itself but now with a .zip extension. I.e. the zip file is identical to the original file. I have to admit that already had me going “wtf.” (It’s weird that unzip doesn’t even complain, even though it obivously needs to skip large parts of the file to reach the zip data stream.) There was also some false(?) hint like "readelf -p .note might be useful later" that never became relevant for me.

In the zip file there’s a meme link to a YouTube video talking about how stupid these “broken PDF” tasks are and asking CTFs to please stop running them, together with a mutool binary for repairing broken PDFs, and a script to run said command in a docker (should you need it). Running the command gives a PNG that’s full of conspiracy theory spoofs, references to Tonybee tiles, Frank Chu, and the like, and other stuff that treads the line between tragic schizophrenia and memetic mystery. Oh, and also a reference to the “it’s a trap” meme and something blah blah about PDF bombs.

That is when I sort of just bailed out and took a more brute force approach:

def streams(dat):
  j = 0
  while True:
    try:
      i = dat.index(b'\x06stream\x0a', j)
    except ValueError:
      return
    j = dat.index(b'\x0aendstream', i)
    yield dat[i+8:j]

I.e. I gave up on trying to make challenge.pdf play nice with any other program and simply extracted the streams in a “dumb” way, saving them all as files, deflating those that needed deflating.

Here there’s various images (the ones rendered in the conspiracy PNG above), font data, and random stuff like another false(?) hint about pip install polyfile and so on.

But one of the streams has a lot of hex codes listed as text data. Converting it to binary (it had the JPEG magic bytes) and opening it gives the flag.

I’m lowkey impressed by the work that probably went into creating the task, and of course the memes, but it’s still a “thanks, I hate it” sort of thing.

of which only Steganography 2.0 was relevant for me anyway. Tho regarding that task: a pickled 5GB numpy array? Bitch, please, does it look like I’m made of RAM?↩

a soft spiracle